当前位置:文档之家› 数据结构 第六章 图 练习题及答案详细解析(精华版)

数据结构 第六章 图 练习题及答案详细解析(精华版)

数据结构 第六章 图 练习题及答案详细解析(精华版)
数据结构 第六章 图 练习题及答案详细解析(精华版)

1. 填空题

⑴ 设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边。

【解答】0,n(n-1)/2,0,n(n-1)

【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个,即是()。

【解答】其自身

⑶ 图的存储结构主要有两种,分别是()和()。

【解答】邻接矩阵,邻接表

【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。

⑷ 已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为()。

【解答】O(n+e)

【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为O(n+2e)=O(n+e)。

⑸ 已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是()。

【解答】求第j列的所有元素之和

⑹ 有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的()。

【解答】出度

⑺ 图的深度优先遍历类似于树的()遍历,它所用到的数据结构是();图的广度优先遍历类似于树的()遍历,它所用到的数据结构是()。

【解答】前序,栈,层序,队列

⑻ 对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(),利用Kruskal 算法求最小生成树的时间复杂度为()。

【解答】O(n2),O(elog2e)

【分析】Prim算法采用邻接矩阵做存储结构,适合于求稠密图的最小生成树;Kruskal算法采用边集数组做存储结构,适合于求稀疏图的最小生成树。

⑼ 如果一个有向图不存在(),则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路

⑽ 在一个有向图中,若存在弧、、,则在其拓扑序列中,顶点vi, vj, vk的相对次序为()。

【解答】vi, vj, vk

【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

2. 选择题

⑴ 在一个无向图中,所有顶点的度数之和等于所有边数的()倍。

A 1/2

B 1

C 2

D 4

【解答】C

【分析】设无向图中含有n个顶点e条边,则。

⑵ n个顶点的强连通图至少有()条边,其形状是()。

A n

B n+1

C n-1

D n×(n-1)

E 无回路

F 有回路

G 环状

H 树状

【解答】A,G

⑶ 含n 个顶点的连通图中的任意一条简单路径,其长度不可能超过()。

A 1

B n/2

C n-1

D n

【解答】C

【分析】若超过n-1,则路径中必存在重复的顶点。

⑷ 对于一个具有n个顶点的无向图,若采用邻接矩阵存储,则该矩阵的大小是()。

A n

B (n-1)2

C n-1

D n2

【解答】D

⑸ 图的生成树(),n个顶点的生成树有()条边。

A 唯一

B 不唯一

C 唯一性不能确定

D n

E n +1

F n-1

【解答】C,F

⑹ 设无向图G=(V, E)和G' =(V', E' ),如果G' 是G的生成树,则下面的说法中错误的是()。

A G' 为G的子图

B G' 为G的连通分量

C G' 为G的极小连通子图且V = V'

D G' 是G的一个无环子图

【解答】B

【分析】连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中顶点的所有边都加上,所以,连通分量中可能存在回路。

⑺ G是一个非连通无向图,共有28条边,则该图至少有()个顶点。

A 6

B 7

C 8

D 9

【解答】D

【分析】n个顶点的无向图中,边数e≤n(n-1)/2,将e=28代入,有n≥8,现已知无向图非连通,则n=9。

⑻ 最小生成树指的是()。

A 由连通网所得到的边数最少的生成树

B 由连通网所得到的顶点数相对较少的生成树

C 连通网中所有生成树中权值之和为最小的生成树

D 连通网的极小连通子图

【解答】C

⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。

A 求关键路径的方法

B 求最短路径的方法

C 广度优先遍历算法

D 深度优先遍历算法

【解答】D

【分析】当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。

⑽ 下面关于工程计划的AOE网的叙述中,不正确的是()?br /> A 关键活动不按期完成就会影响整个工程的完成时间

B 任何一个关键活动提前完成,那么整个工程将会提前完成

C 所有的关键活动都提前完成,那么整个工程将会提前完成

D 某些关键活动若提前完成,那么整个工程将会提前完

【解答】B

【分析】AOE网中的关键路径可能不止一条,如果某一个关键活动提前完成,还不能提前整个工程,而必须同时提高在几条关键路径上的关键活动。

3. 判断题

⑴ 一个有向图的邻接表和逆邻接表中的结点个数一定相等。

【解答】对。邻接表和逆邻接表的区别仅在于出边和入边,边表中的结点个数都等于有向图中边的个数。

⑵ 用邻接矩阵存储图,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关。

【解答】对。邻接矩阵的空间复杂度为O(n2),与边的个数无关。

⑶ 图G的生成树是该图的一个极小连通子图

【解答】错。必须包含全部顶点。

⑷ 无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的

【解答】错。有向图的邻接矩阵不一定对称,例如有向完全图的邻接矩阵就是对称的。

⑸ 对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。

【解答】错。只有连通图从某顶点出发进行一次遍历,可访问图的所有顶点。

⑹ 在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。

【解答】错。只能说明从顶点a到顶点b有一条路径。

⑺ 若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑序列必定存在。

【解答】对。参见第11题的证明。

⑻ 在AOE网中一定只有一条关键路径?br />【解答】错。AOE网中可能有不止一条关键路径,他们的路径长度相同

4.n个顶点的无向图,采用邻接表存储,回答下列问题?br />⑴ 图中有多少条边?

⑵ 任意两个顶点i和j是否有边相连?

⑶ 任意一个顶点的度是多少?br />

【解答】

⑴ 边表中的结点个数之和除以2。

⑵ 第i个边表中是否含有结点j。

⑶ 该顶点所对应的边表中所含结点个数。

5.n个顶点的无向图,采用邻接矩阵存储,回答下列问题:

⑴ 图中有多少条边?

⑵ 任意两个顶点i和j是否有边相连?

⑶ 任意一个顶点的度是多少?

【解答】

⑴ 邻接矩阵中非零元素个数的总和除以2。

⑵ 当邻接矩阵A中A[i][j]=1(或A[j][i]=1)时,表示两顶点之间有边相连。

⑶ 计算邻接矩阵上该顶点对应的行上非零元素的个数。

6.证明:生成树中最长路径的起点和终点的度均为1。

【解答】用反证法证明。

设v1, v2, …, vk是生成树的一条最长路径,其中,v1为起点,vk为终点。若vk的度为2,取vk的另一个邻接点v,由于生成树中无回路,所以,v在最长路径上,显然v1, v2, …, vk , v的路径最长,与假设矛盾。所以生成树中最长路径的终点的度为1。

同理可证起点v1的度不能大于1,只能为1。

7.已知一个连通图如图6-6所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点v1出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列。

【解答】邻接矩阵表示如下:

深度优先遍历序列为:v1 v2 v3 v5 v4 v6

广度优先遍历序列为:v1 v2 v4 v6 v3 v5

邻接表表示如下:

8.图6-7所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树。

【解答】按Prim算法求最小生成树的过程如下:

按Kruskal算法求最小生成树的过程如下:

9.对于图6-8所示的带权有向图,求从源点v1到其他各顶点的最短路径。

【解答】从源点v1到其他各顶点的最短路径如下表所示。

源点终点最短路径最短路径长度

v1 v7 v1 v7 7

v1 v5 v1 v5 11

v1 v4 v1 v7 v4 13

v1 v6 v1 v7 v4 v6 16

v1 v2 v1 v7 v2 22

v1 v3 v1 v7 v4 v6 v3 25

10.如图6-9所示的有向网图,利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。

【解答】从源点v1到其他各顶点的最短路径如下表所示。

源点终点最短路径最短路径长度

v1 v3 v1 v3 15

v1 v5 v1 v5 15

v1 v2 v1 v3 v2 25

v1 v6 v1 v3 v2 v6 40

v1 v4 v1 v3 v2 v4 45

11.证明:只要适当地排列顶点的次序,就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1,我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。

假设此时的邻接矩阵不是上三角矩阵,那么,存在下标i和j(i>j),使得A[i][j]不等于零,即图中存在从

vi到vj的一条有向边。由拓扑序列的定义可知,在任意拓扑序列中,vi的位置一定在vj之前,而在上述拓扑序列v0v1v2…vn-1中,由于i>j,即vi的位置在vj之后,导致矛盾。因此命题正确。

12. 算法设计

⑴ 设计算法,将一个无向图的邻接矩阵转换为邻接表。

【解答】先设置一个空的邻接表,然后在邻接矩阵上查找值不为零的元素,找到后在邻接表的对应单链表中插入相应的边表结点。

邻接矩阵存储结构定义如下:

const int MaxSize=10;

template

struct AdjMatrix

{

T vertex[MaxSize]; //存放图中顶点的数组

int arc[MaxSize][MaxSize]; //存放图中边的数组

int vertexNum, arcNum; //图的顶点数和边数

};

邻接表存储结构定义如下:

const int MaxSize=10;

struct ArcNode //定义边表结点

{

int adjvex; //邻接点域

ArcNode *next;

};

template

struct VertexNode //定义顶点表结点

{

T vertex;

ArcNode *firstedge;

};

struct AdjList

{

VertexNode adjlist[MaxSize];

int vertexNum, arcNum; //图的顶点数和边数};

具体算法如下:

⑵ 设计算法,将一个无向图的邻接表转换成邻接矩阵。

【解答】在邻接表上顺序地取每个边表中的结点,将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表的存储结构定义与上题相同。具体算法如下:

⑶ 设计算法,计算图中出度为零的顶点个数。

【解答】在有向图的邻接矩阵中,一行对应一个顶点,每行的非零元素的个数等于对应顶点的出度。因此,

当某行非零元素的个数为零时,则对应顶点的出度为零。据此,从第一行开始,查找每行的非零元素个数是否为零,若是则计数器加1。具体算法如下:

⑷ 以邻接表作存储结构,设计按深度优先遍历图的非递归算法。

【解答】参见6.2.1。

⑸ 已知一个有向图的邻接表,编写算法建立其逆邻接表。

【解答】在有向图中,若邻接表中顶点vi有邻接点vj,在逆邻接表中vj一定有邻接点vi,由此得到本题算法思路:首先将逆邻接表的表头结点firstedge域置空,然后逐行将表头结点的邻接点进行转化。

⑹ 分别基于深度优先搜索和广度优先搜索编写算法,判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

【解答】⑴ 基于深度优先遍历:

⑵ 基于广度优先遍历:

学习自测及答案

1.某无向图的邻接矩阵A=,可以看出,该图共有()个顶点。

A 3

B 6

C 9

D 以上答案均不正确

【解答】A

2.无向图的邻接矩阵是一个(),有向图的邻接矩阵是一个()

A 上三角矩阵

B 下三角矩阵

C 对称矩阵

D 无规律

【解答】C,D

3.下列命题正确的是()。

A 一个图的邻接矩阵表示是唯一的,邻接表表示也唯一

B 一个图的邻接矩阵表示是唯一的,邻接表表示不唯一

C 一个图的邻接矩阵表示不唯一的,邻接表表示是唯一

D 一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一

【解答】B

4.十字链表适合存储(),邻接多重表适合存储()。

【解答】有向图,无向图

5. 在一个具有n 个顶点的有向完全图中包含有()条边:

A n(n-1)/2

B n(n-1)

C n(n+1)/2

D n2

【解答】B

6.n个顶点的连通图用邻接矩阵表示时,该矩阵至少有()个非零元素。

【解答】2(n-1)

7.表示一个有100个顶点,1000条边的有向图的邻接矩阵有()个非零矩阵元素。

【解答】1000

8.一个具有n个顶点k条边的无向图是一个森林(n>k),则该森林中必有()棵树。

A k

B n

C n - k

D 1

【解答】C

9.用深度优先遍历方法遍历一个有向无环图,并在深度优先遍历算法中按退栈次序打印出相应的顶点,则输出的顶点序列是()。

A 逆拓扑有序

B 拓扑有序

C 无序

D 深度优先遍历序列

【解答】A

10. 关键路径是AOE网中()。

A 从源点到终点的最长路径B从源点到终点的最长路径

C 最长的回路

D 最短的回路

【解答】A

11. 已知无向图G的邻接表如图6-10所示,分别写出从顶点1出发的深度遍历和广度遍历序列,并画出相应的生成树。

【解答】深度优先遍历序列为:1,2,3,4,5,6

对应的生成树为:

广度优先遍历序列为:1,2,4,3,5,6

对应的生成树为:

12. 已知已个AOV网如图6-11所示,写出所有拓扑序列。

【解答】拓扑序列为:v0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。

数据结构作业系统第七章答案

7.22③试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数: Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下:Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1)

上数据结构期末图习题答案

2014 上数据结构期末复习大纲 一. 期中前以期中考试试卷复习,算法要真正理解 二、二叉树、图、排序算法将是考试重点(占60%左右) 三、要掌握的算法 1. 二叉树的链表表示 2.建立二叉树的链表存储结构 3. 先序、中序、后序遍历二叉树(递归算法) 4. 遍历算法的应用(如求二叉树的结点数) 5.建立huffman树和huffman编码 6. 图的邻接矩阵表示和邻接链表表示 7.图的深度优先遍历和广度优先遍历算法 8. 有向图求最短路径(迪杰斯特拉算法) 9. 直接插入排序算法 10. shell 排序(排序过程) 12. 堆排序(排序过程)

练习题 1. 有8个结点的无向图最多有 B 条边。 A .14 B. 28 C. 56 D. 112 2. 有8个结点的无向连通图最少有 C 条边。 A .5 B. 6 C. 7 D. 8 3. 有8个结点的有向完全图最多有 C 条边。 A .14 B. 28 C. 56 D. 112 4. 用邻接表表示图进行广度优先遍历时,通常是采用 B 来实现算法的。 A .栈 B. 队列 C. 树 D. 图 5. 用邻接表表示图进行深度优先遍历时,通常是采用 A 来实现算法的。 A .栈 B. 队列 C. 树 D. 图 6. 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是*( C ) A .0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110

数据结构书面作业练习题

习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树,_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树,__B_是平衡二叉树。 3. 在线索化二叉树中,t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后,任一结点均有指向其前驱和后续的线索,这种说 法_B__ o

A.正确 B. 错误 5. 二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec,中序遍历序

列是debac,它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点,在中序遍历时,a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义,具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示,其中序遍历的序列为

数据结构作业电子版

1数据结构课程研究的主要内容包括()()() 2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性 3数据的逻辑结构可分为_____ ______两大类 4数据的逻辑结构是指而存储结构是指 5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一 6为了实现随机访问线性结构应该采用存储结构 7链式存储结构的主要特点是 8算法分析主要从和这两个方面对算法进行分析 (1)数据 (2)数据元素 (3)数据类型 (4)数据结构 (5)逻辑结构 (6)存储结构 (7)线性结构 (8)非线性结构 第二章作业 一、判断题(在你认为正确的题后的括号中打√,否则打X)。 1.线性表的逻辑顺序与存储顺序总是一致的。 2.顺序存储的线性表可以按序号随机存取。 3.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。 4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。 5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。7.线性表的链式存储结构优于顺序存储结构。 8.在线性表的顺序存储结构中,插入和删除时,移动元素的个数与该元素的位置有关。 9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。 二、单项选择题。 1.线性表是( ) 。 (A) 一个有限序列,可以为空; (B) 一个有限序列,不能为空; (C) 一个无限序列,可以为空; (D) 一个无序序列,不能为空。 2.对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的()个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3.线性表采用链式存储时,其地址( ) 。

数据结构图习题

第七章图:习题 习题 一、选择题 1.设完全无向图的顶点个数为n,则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2.在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3.有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4.在无向图G (V,E)中,如果图中任意两个顶点vi、vj (vi、vj∈V,vi≠vj)都的,则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5.若采用邻接矩阵存储具有n个顶点的一个无向图,则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6.若采用邻接矩阵存储具有n个顶点的一个有向图,顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7.对于具有e条边的无向图,它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8.对于含有n个顶点和e条边的无向连通图,利用普里姆Prim算法产生最小生成时间复杂性为( ),利用克鲁斯卡尔Kruskal算法产生最小生成树(假设边已经按权的次序排序),其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9.对于一个具有n个顶点和e条边的有向图,拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10.在一个带权连通图G中,权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1.在一个具有n个顶点的无向完全图中,包含有____条边;在一个具有n个有向完全图中,包含有____条边。 2.对于无向图,顶点vi的度等于其邻接矩阵____ 的元素之和。 3.对于一个具有n个顶点和e条边的无向图,在其邻接表中,含有____个边对于一个具有n个顶点和e条边的有向图,在其邻接表中,含有_______个弧结点。 4.十字链表是有向图的另一种链式存储结构,实际上是将_______和_______结合起来的一种链表。 5.在构造最小生成树时,克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法;普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6.对用邻接表表示的图进行深度优先遍历时,其时间复杂度为一;对用邻接表表示的图进行广度优先遍历时,其时间复杂度为_______。 7.对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数为_______ ,边数为_______。 8.在执行拓扑排序的过程中,当某个顶点的入度为零时,就将此顶点输出,同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零,需要设立一个____来存放入度为零的顶点。

数据结构 图的基本操作实现

实验五图的遍历及其应用实现 一、实验目的 1.熟悉图常用的存储结构。 2.掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3.会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] :从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示: 输入示例 上图的顶点和边的信息输入数据为: 5 7 DG A B C D E AB AE BC CD DA DB EC [题目二]:在图G中求一条从顶点 i 到顶点 s 的简单路径 [题目三]:寻求最佳旅游线路(ACM训练题) 在一个旅游交通网中,判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路,为节省费用,不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。 输入: 第一行:n //n-旅游城市个数 第2行:A B s1 s2 //s1,s2-金额数 第3行---第e+2行 ( 1≤e≤n(n-1)/2 ) 表示城市x,y之间的旅行费用,输入0 0 0 表示结束。

输出: 第一行表示 A到B的旅游线路景点序列 第二行表示沿此线路,从A到B的旅游费用 设计要求: 1、上机前,认真学习教材,熟练掌握图的构造和遍历算法,图的存储结 构也可使用邻接矩阵等其他结构. 2、上机前,认真独立地写出本次程序清单,流程图。图的构造和遍历算法 分别参阅讲义和参考教材事例 图的存储结构定义参考教材 相关函数声明: 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G, int v) 3、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G, int v)4、 4、/* 其他相关函数 */…… 三、实验步骤 ㈠、数据结构与核心算法的设计描述 ㈡、函数调用及主函数设计 (可用函数的调用关系图说明) ㈢程序调试及运行结果分析 ㈣实验总结 四、主要算法流程图及程序清单 1、主要算法流程图: 2、程序清单 (程序过长,可附主要部分)

数据结构习题库

知识点: 01.绪论 02.顺序表 03.链表 04.栈 05.链队列 06.循环队列 07.串 08.数组的顺序表示 09.稀疏矩阵 10.广义表 11.二叉树的基本概念 12.二叉树遍历、二叉树性质 13.树、树与二叉树的转换 14.赫夫曼树 15.图的定义、图的存储 16.图的遍历 17.图的生成树 18.静态查找(顺序表的查找、有序表的查找) 19.动态查找(二叉排序树、平衡树、B树) 20.哈希查找 21.插入排序(直接插入、折半插入、2路插入、希尔排序)22.选择排序(简单选择、树形选择、堆排序) 23.快速排序、归并排序

101A1(1).数据的逻辑结构是(A)。 A.数据的组织形式 B.数据的存储形式 C.数据的表示形式 D.数据的实现形式 101A1(2).组成数据的基本单位是(C)。 A.数据项 B.数据类型 C.数据元素 D.数据变量 101B1(3).与顺序存储结构相比,链式存储结构的存储密度(B)。 A.大 B.小 C.相同 D.以上都不对 101B2(4).对于存储同样一组数据元素而言,(D)。 A.顺序存储结构比链接结构多占空间 B.在顺序结构中查找元素的速度比在链接结构中查找要快 C.与链接结构相比,顺序结构便于安排数据元素 D.顺序结构占用整块空间而链接结构不要求整块空间101B2(5).下面程序的时间复杂度为(B)。 x=0; for(i=1;ii;j++) state; A.n(n+1)/2 B.(n-1)(n+2)/2 C.n(n+1)/2 D.(n-1)(n+2) 101D3(8).下面程序的时间复杂度为(A)。

数据结构:图子系统

/* *题目:编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下: * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号(0--3): */ #include #include #define GRAPHMAX 30 #define QUEUEMAX 30 typedef struct //图的邻接表的结构体 { char value[GRAPHMAX]; //记录图中的点值 int data[GRAPHMAX][GRAPHMAX]; //记录图中的边的关系int n, e; //记录图中的点的个数及边的个数 }pGraph; typedef struct //队列结构体 { int queueData[QUEUEMAX]; int front, rear, count; //队头,队尾,数目 }grQueue; void createCraph(pGraph *G); void DFSTraverse(pGraph *G); void BFSTraverse(pGraph *G); void DFS(pGraph *G, int i); void BFS(pGraph *G, int i); void initQueue(grQueue *Q); int queueEmpty(grQueue *Q); int queueFull(grQueue *Q); int outQueue(grQueue *Q); void inQueue(grQueue *Q, int i);

数据结构-图习题

第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中,边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有 n-1条边与其他n-1个顶点相连,总计n 个顶点有n(n-1)条边。但在无向图中,顶点i 到顶点j 与顶点j 到顶点i 是同一条边,所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗?请列出所有的简单路径。 【解答】 点,它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发,到其他的各个顶点的简单路径有A →B ,A →D →B ,A →B →C ,A →D →B →C ,A →D ,A →B →E ,A →D →E ,A →D →B →E ,A →B →C →F →E ,A →D →B →C →F →E ,A →B →C →F ,A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D

????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发,到其他各个顶点的简单路径有B →C ,B →C →F ,B →E ,B →C →F →E 。 从顶点C 出发,到其他各个顶点的简单路径有C →F ,C →F →E 。 从顶点D 出发,到其他各个顶点的简单路径有D →B ,D →B →C ,D →B →C →F ,D →E ,D →B →E ,D →B →C →F →E 。 从顶点E 出发,到其他各个顶点的简单路径无。 从顶点F 出发,到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D

数据结构复习题附答案

一.是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D,S,P)。其中:D是数据对象,S是D上的关系,P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是:p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是: P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言,线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表,凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要,可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈:如果需要,每一次只能对栈顶的元素进行操作 队列:如果需要,每一次只能对两端,或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点,而对一般的树,则无此限制,所以,二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中,任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树,B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常,二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中,任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图,也可用以表示有向图。(f) (只能表示无向图,有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)

数据结构实验图的基本操作

浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师(签名)日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现: 建立头文件test13_AdjM.h,在该文件中定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp(以下图为例),编译并调试程序,直到正确运行。 2、图的邻接表的定义及实现: 建立头文件test13_AdjL.h,在该文件中定义图的邻接表存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证(以下图为例)。

3、填写实验报告,实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序,读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 (包括每个函数的功能说明,及一些重要函数的算法实现思路) 四. 实验结果与分析 (包括运行结果截图、结果分析等)

五.心得体会

程序比较难写,但是可以通过之前的一些程序来找到一些规律 (记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。) 【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include #include #include typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum=10; //图的最大顶点数 const int MaxEdgeNum=100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue=32767; //权值的无穷大表示 typedef VertexType Vexlist[MaxVertexNum]; //顶点信息,定点名称 typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网typedef struct{ Vexlist vexs; // 顶点数据元素 AdjMatrix arcs; // 二维数组作邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法,构造图G {//构造有向网G int i,j,k,q; char v, w; G.kind=kd; //图的种类 printf("输入要构造的图的顶点数和弧数:\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等:\n"); for (i=0; i

数据结构中图的全部操作

#include #include #include #include #include #include using namespace std; #define MAX_VERTEX_NUM 100 #define INFINITY INT_MAX #define EXTERN 10 #define OK 1 #define ERROR -1 #define MAX -1 #define MAXW 10000 typedef int Status; typedef bool VisitIf; typedef char VertexType;//顶点数据类型 typedef int VRType; //顶点关系( 表示是否相邻) typedef int InfoType; //弧相关信息

typedef enum{DG,DN,UDG,UDN} GraphKind;//图的类型 bool visited[MAX_VERTEX_NUM]; //邻接矩阵 typedef struct ArcCell { VRType adj;//权值 InfoType *info; }ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMartix arcs; //邻接矩阵 int vexnum,arcnum; //图当前顶点数,弧数 GraphKind Kind; //图的类型 }MGraph; bool VexExist(MGraph G,VertexType v)//判断定点是否在图中{

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2. 物理结构是数据结构在计算机中的表示,又称为(存储结构)。 3. 数据元素的逻辑结构包括(线性)、(树)和图状结构3 种类型,树形结构和图状结构合称为(非线性结构)。 4. (数据元素)是数据的基本单位,(数据项)是数据不可分割的最小单位。 5. 线性结构中元素之间存在(一个对一个)关系,树形结构中元素之间存在(一个对多个)关系,图状结构中元素之间存在(多个对多个)关系。 ? 6.数据结构是一门研究非数值计算的程序设计问题中:计算机的(数据元素)以及它们之间的(关 系)和(运筹)等的学科。 7. 算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1. 数据的不可分割的基本单位是(D)。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的,这种说法(B)。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种(D)。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系

4. 在数据结构中,从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D)。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答:有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素(1< i产时,需向前移动(n-i)个元素。 2. 从循环队列中删除一个元素时,其操作是(先移动队首指针,后取出元素)。 3?在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为(p-> next)。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时,首先把(p->next)的值赋给q->next,然后(q->date)的值赋给p->next。 5. 从一个栈删除元素时,首先取出(栈顶元素),然后再使(栈顶指针)减1。 6. 子串的定位操作通常称做串的(模式匹配)。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第(六)次匹配成功。。 8. 顺序栈S 中,出栈操作时要执行的语句序列中有S->top(--);进栈操作时要执行的语句序列中有S->top(++)。

数据结构(树与图部分)练习题

1 数据结构(树与图部分)练习题 一、填空题 1. 不考虑顺序的3个结点可构成种不同形态的树,种不同形态的二叉树。 2. 已知某棵完全二叉树的第4层有5个结点,则该完全二叉树叶子结点的总数为:。 3. 已知一棵完全二叉树的第5层有3个结点,其叶子结点数是。 4. 一棵具有110个结点的完全二叉树,若i =54,则结点i 的双亲编号是;结点i 的左孩 子结点的编号是,结点i 的右孩子结点的编号是。 5. 一棵具有48个结点的完全二叉树,若i =20,则结点i 的双亲编号是______;结点i 的左孩子结点编号是______,右孩子结点编号是______。 6. 在有n 个叶子结点的Huffman 树中,总的结点数是:______。 7. 图是一种非线性数据结构,它由两个集合V(G)和E(G)组成,V(G)是______的非空有限 集合,E(G)是______的有限集合。 8. 遍历图的基本方法有优先搜索和优先搜索两种方法。 9. 图的遍历基本方法中是一个递归过程。 10. n 个顶点的有向图最多有条弧;n 个顶点的无向图最多有条边。 11. 在二叉树的二叉链表中,判断某指针p 所指结点是叶子结点的条件是。 12. 在无向图G 的邻接矩阵A 中,若A[i,j]等于1,则A[j,i]等于。 二、单项选择题 1. 树型结构的特点是:任意一个结点:( ) A 、可以有多个直接前趋 B 、可以有多个直接后继 C 、至少有1个前趋 D 、只有一个后继 2. 如下图所示的4棵二叉树中,( )不是完全二叉树。 A B C D 3. 深度为5的二叉树至多有( )个结点。 A 、16 B 、32 C 、31 D 、10 4. 64个结点的完全二叉树的深度为:( )。 A 、8 B 、7 C 、6 D 、5 5. 将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编 号,根结点编号为1,则编号为49的结点的左孩子的编号为:( )。 A 、98 B 、99 C 、50 D 、48 6. 在一个无向图中,所有顶点的度之和等于边数的( )倍。 A 、1/2 B 、1 C 、2 D 、4 7. 设有13个值,用它们组成一棵Huffman 树,则该Huffman 树中共有()个结点。

最新数据结构习题与答案--图

第7章图 一、单选题 01、在一个图中,所有顶点的度数之和等于图的边数的倍。A.1/2 B.1 C.2 D.4 02、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。 A.1/2 B.1 C.2 D.4 03、有8个结点的无向图最多有条边。 A.14 B.28 C.56 D.112 04、有8个结点的无向连通图最少有条边。 A.5 B.6 C.7 D.8 05、有8个结点的有向完全图有条边。 A.14 B.28 C.56 D.112 06、用邻接表表示图进行广度优先遍历时,通常是采用来实现算法的。 A.栈 B.队列 C.树 D.图 07、用邻接表表示图进行深度优先遍历时,通常是采用来实现算法的。 A.栈 B.队列 C.树 D.图 08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度的时间复杂度为。 A.O(n) B.O(e) C.O(n+e) D.O(n2) 09、已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是。 A.0 2 4 3 1 5 6 B.0 1 3 6 5 4 2 C.0 1 3 4 2 5 6 D.0 3 6 1 5 4 2 10、已知图的邻接矩阵同上题,根据算法,则从顶点0出发,按广度优先遍历的结点序列是。 A.0 2 4 3 6 5 1 B.0 1 2 3 4 5 6 C.0 4 2 3 1 5 6 D.0 1 3 4 2 5 6 11、已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是。 A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3 12、已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是。 A.0 3 2 1 B.0 1 2 3 C.0 1 3 2 D.0 3 1 2 13、图的深度优先遍历类似于二叉树的。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历14、图的广度优先遍历类似于二叉树的。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历15、任何一个无向连通图的最小生成树。 A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在 ( )16、对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为,所有边链表中边结点的总数为。 A.n、2e B.n、e C.n、n+e D.2n、2e 17、判断有向图是否存在回路,可以利用算法。 A.关键路径 B.最短路径的Dijkstra C.拓扑排序D.广度优先遍历 18、若用邻接矩阵表示一个有向图,则其中每一列包含的“1”的个数为。 A.图中每个顶点的入度 B.图中每个顶点的出度 C.图中弧的条数 D.图中连通分量的数目 19、求最短路径的Dijkstra算法的时间复杂度是___。A.O(n) B.O(n+e) C.O(n2) D.O(n*e) 20、设图G采用邻接表存储,则拓扑排序算法的时间复杂度为。 A.O(n) B.O(n+e) C.O(n2) D.O(n*e) 21、带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中。 A.第i行非∞的元素之和 B.第i列非∞的元素之和 C.第i行非∞且非0的元素个数 D.第i列非∞且非0的元素个数 22、一个有n个顶点的无向图最多有条边。 A.n B.n(n-1) C.n(n-1)/2 D.2n 23、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是。 A.n B.(n-1)2 C.n-1 D.n2 24、对某个无向图的邻接矩阵来说,。 A.第i行上的非零元素个数和第i列的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第i行上,第i列上非零元素总数等于顶点v i的度数D.矩阵中非全零行的行数等于图中的顶点数 25、已知图的表示如下,若从顶点a出发按深度搜索法进行遍历,则可能得到的一种顶点序列为。

(完整版)数据结构详细教案——图

数据结构教案第七章图

第7章图 【学习目标】 1.领会图的类型定义。 2.熟悉图的各种存储结构及其构造算法,了解各种存储结构的特点及其选用原则。 3.熟练掌握图的两种遍历算法。 4.理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛,而且图的各种应用问题的算法都比较经典,因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支,但图论注重研究图的纯数学性质,而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构,因此和线性表、树不同,虽然在遍历图的同时可以对顶点或弧进行各种操作,但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法,在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难,应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似,应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对,即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图? 2. 如果每次让三条路同时通行,那么从图看出哪些路可以同时通行? 同时可通行的路为:(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)

数据结构 第六章 图 练习题及答案详细解析(精华版)

图 1. 填空题 ⑴ 设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边。 【解答】0,n(n-1)/2,0,n(n-1) 【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个,即是()。 【解答】其自身 ⑶ 图的存储结构主要有两种,分别是()和()。 【解答】邻接矩阵,邻接表 【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为()。 【解答】O(n+e) 【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为O(n+2e)=O(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是()。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的()。 【解答】出度 ⑺ 图的深度优先遍历类似于树的()遍历,它所用到的数据结构是();图的广度优先遍历类似于树的()遍历,它所用到的数据结构是()。 【解答】前序,栈,层序,队列

⑻ 对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(),利用Kruskal 算法求最小生成树的时间复杂度为()。 【解答】O(n2),O(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构,适合于求稠密图的最小生成树;Kruskal算法采用边集数组做存储结构,适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在(),则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中,若存在弧、、,则在其拓扑序列中,顶点vi, vj, vk的相对次序为()。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中,所有顶点的度数之和等于所有边数的()倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边,则。 ⑵ n个顶点的强连通图至少有()条边,其形状是()。 A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路 G 环状 H 树状 【解答】A,G ⑶ 含n 个顶点的连通图中的任意一条简单路径,其长度不可能超过()。 A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1,则路径中必存在重复的顶点。

《数据结构》基本操作指导

目录 指导一、单链表的操作----------------------------------------------------- 2指导二、栈及其应用------------------------------------------------------- 10指导三、串的基本操作---------------------------------------------------- 16指导四、二叉树的基本操作---------------------------------------------- 21指导五、图的存储和遍历------------------------------------------------- 31指导六、查找--------------------------------------------------------------- 41 指导七、排序--------------------------------------------------------------- 49

指导一、单链表的操作 一、指导目的 1、掌握线性表的链式存储结构。 2、掌握利用链式存储结构实现线性表的基本操作。 3、掌握链式存储结构中的算法实现。 二、指导内容 1、建立带头结点的单链表,并输出该单链表。 2、实现带头结点的单链表上的插入、删除、查找、修改操作。 三、操作指导 1、定义单链表的结点结构 单链表的结点结构可为一个结构体类型(slnodetype),其成员是数据域和指针域,数据域可以是整数。 2、模块划分和程序控制流程 根据实验要完成的各功能,设置初始化、建立单链表、输出单链表、插入、删除、查找、修改和主函数8个模块,对于要完成的各功能,采用适当的人机界面,用循环和分支结构构成菜单进行选择。 3、初始化模块int initiate(slnodetype **h) 该模块中产生一个只有头结点的空单链表,用指针h作为函数的参数返回,因为h是指针变参,所以在函数的参数位置要以二级指针出现。在函数里,申请一个头结点空间。 4、建立单链表模块int createlink(slnodetype *h) 该模块中建立有若干个结点的单链表,用循环控制输入若干个整数,申请相应的结点空间,以输入的整数作为结点中的数据,依次链接到初始只有头结点的单链表h中,可以把输入0作为建立链表的结束。 5、输出单链表模块void display(slnodetype *h) 对于传入的单链表h,依次输出单链表中的结点(数据)。 6、插入结点模块int inserti(slnodetype *h) 设在第i个结点前插入数据为data的结点。在该函数模块中输入i和数据data,对于传入的单链表h,先查找是否存在插入的位置(单链表h中至少要有i-1个结点),若不存在插入位置,则不做任何操作;若存在插入位置,则申请一个结点,其数据为data,挂在第i-1个结点的后面。 7、删除结点模块int delete(slnodetype *h) 在该函数模块中,首先可以调用输出模块输出传入的单链表h,以便选择要删除的结点,然后输入要删除结点的数据data,再查找是否存在要删除的结点,若不存在要删除的结点,则显示相应的信息;若存在要删除的结点,则删除该结点(包括删除该结点空间)。 8、查找模块int search(slnodetype *h)

相关主题
相关文档 最新文档