一、选择题
1、有6个结点的有向完全图有（）条弧。
A、36
B、28
C、30
D、15
2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。
A、栈
B、队列
C、树
D、图
3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。
A、栈
B、队列
C、树
D、图
4、任何一个无向连通图的最小生成树（）
A、只有一棵
B、一棵或多棵
C、一定有多棵
D、可能不存在
5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。
A、1/2
B、1
C、2
D、4
6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A、1/2
B、1
C、2
D、4
7、一个有n个顶点的无向图最多有（）条边。
A、n
B、n(n-1)
C、n(n-1)/2
D、2n
8、具有5个顶点的无向完全图有（）条边。
A、6
B、8
C、10
D、20
9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
A、n
B、n+1
C、n-1
D、n/2
10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）
A、(n+1)*(n-1)
B、(n-1)*(n-1)
C、n
D、n*n
11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）
(1)A、n B、n+1 C、n-1 D、n+e
(2)A、e/2 B、e C、2e D、n+e
12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）
A、求关键路径的方法
B、求最短路径的方法
C、宽度优先遍历算法
D、深度优先遍历算法
15、关键路径是AOE网中的（）
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最短的回路
D、活动的最早开始时间与最迟发生时间相等
二、填空题
1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。
2、设有一稀疏图G，则G采用（邻接表）存储较省空间。
3、设有一稠密图G，则G采用（邻接矩阵）存储较省空间。
4、图的邻接表存储结构只适用于（）图。
5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I 行）。
6、图的深度优先遍历序列（不是）唯一的。
7、n个顶点e条边的图，若用邻接表存储，深度优先遍历算法的时间复杂度为（n+e）。
8、n个顶点e条边的图，若用邻接矩阵存储，广度优先遍历算法的时间复杂度为（n2）。
9、图的BFS生成树的树高比DFS生成树的树高（小）。
10、若要求一个稀疏图G的最小生成树，最好用（克鲁斯卡尔）算法来求解。
11、若要求一个稠密图G的最小生成树，最好用（普里姆）算法来求解。
12、n个顶点的连通图至少（N-1）条边。
13、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是（求第I列的和）。
14、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是（将第I行和第I列的值全部更新为零）。
15、设有向图G有n个顶点e条边，进行拓扑排序的总的计算时间为（N+E）。
友情提示：部分文档来自网络整理，供您参考！文档可复制、编辑，期待您的好评与关注！
《数据结构》期末复习题及参考答案- 第7章图 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 注意：做复习题时，请结合阅读教材，钻研教材，参考课件 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 一、选择题 1、以下数据结构中，哪种具有非线性结构？ A．栈B．队列C．双向链表D．十字链表 2、下面关于图的存储的叙述中正确的是（）。 A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。 B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。 C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。 D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（） A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历 4、图的广度优先遍历算法类似于树的（）。 A. 中根遍历 B. 先根遍历 C. 后根遍历 D. 按层次遍历 5、设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 6、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A．n-1 B．n C．n+1 D．nlogn； 7、一个含有n个顶点的非连通图，则（）： A．它的边一定不大于n-1 B．它的边一定不大于n C．它的边一定小于n-1 D．它的边一定大于0 8、要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 9、下列说法不正确的是（）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 10、无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进 行深度优先遍历，得到的顶点序列正确的是（）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,b,e,d,f,c
第7章 《图》习题参考答案 一、单选题（每题1分，共16分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。 A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 （ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点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 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3
第7章树和森林 树形结构是一类重要的非线性结构。树形结构的特点是结点之间具有层次关系。本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。 重点提示： ●树的存储结构 ●树的遍历 ●树和森林与二叉树之间的转换 7-1 重点难点指导 7-1-1 相关术语 1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，T m，其中每个子集本身又是一棵树，并称为根的子树。 要点：树是一种递归的数据结构。 2．结点的度：一个结点拥有的子树数称为该结点的度。 3．树的度：一棵树的度指该树中结点的最大度数。如图7-1所示的树为3度树。 4．分支结点：度大于0的结点为分支结点或非终端结点。如结点a、b、c、d。 5．叶子结点：度为0的结点为叶子结点或终端结点。如e、f、g、h、i。 6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。 7．兄弟结点：具有同一父亲的结点为兄弟结点。如b、c、d；e、f；h、i。 8．树的深度：树中结点的最大层数称为树的深度或高度。 9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。 10．森林：是m棵互不相交的树的集合。 7-1-2 树的存储结构 1．双亲链表表示法 以图7-1所示的树为例。
（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。 （2）存储示意图: -1 data: parent: （3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。 下面的存储是不正确的： -1 data: parent: 2．孩子链表表示法 （1）存储思想： 将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。 （2）存储示意图: 1 2 3 4 5 6 7 8 图7-2 孩子链表存储示意图 （3）需注意的问题： ①每个结点的孩子结点的child域存放该孩子的存储序号，而不是存放其结点的值。 ②孩子链表的最后一个结点的next域置入空指针。 ③叶子结点的firstchild域也要置入空指针。 3．双亲-孩子兄弟链表表示法 将双亲表示和孩子兄弟链表表示法结合起来。 4．孩子兄弟链表表示法 （1）存储思想是：树中每个数据元素存储为一个结点，结点的结构如下： 其中：data为该数据元素的信息；
数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧
(4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径
一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在 5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、1/2 B、1 C、2 D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、1/2 B、1 C、2 D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（） A、(n+1)*(n-1) B、(n-1)*(n-1) C、n D、n*n 11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1 C、n-1 D、n+e (2)A、e/2 B、e C、2e D、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（） A、求关键路径的方法 B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀疏图G，则G采用（邻接表）存储较省空间。 3、设有一稠密图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I 行）。 6、图的深度优先遍历序列（不是）唯一的。 7、n个顶点e条边的图，若用邻接表存储，深度优先遍历算法的时间复杂度为（n+e）。
1.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关答案：C 2.对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。 A:e-1B:e C:2(e-1)D:2e 答案：D，（vi,vj）以vi作为头结点保存一次，以vj作为头结点保存一次。 3.图的深度优先搜索类似于树的（ A ）次序遍历。 A:先序B:中序 C:后序D:层次 4.设无向图的顶点个数为n，则该图最多有（）条边。 A: n-1 B: n(n-1)/2 C: n(n+1)/2 D: n(n-1) 答案：最多边时：完全图。选B 完全有向图: n(n-1) 5.对于有向图，其邻接矩阵表示比邻接表表示更易于( )。 A: 求一个顶点的度B: 求一个顶点的邻接点 C: 进行图的深度优先遍历D: 进行图的广度优先遍历 答案：B 6.与邻接矩阵相比，邻接表更适合于存储( )。 A: 无向图B连通图 C稀疏图D稠密图 答案：C 7.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（） A．图中每个顶点的入度B．图中每个顶点的出度 C．图中弧的条数D．图中连通分量的数目 答案：A 8.设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n2
9.一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn； 答案：极小连通图，A 10.n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１）C．n／2 D．n*（n－l） 11.在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中， 所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 12.在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 答案：C 1.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任 一顶点度数的时间复杂度分别为__O（n）______和____O(e/n)___。 2.图的__________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需 要使用队列。 3.假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{
第7章图 二.判断题 部分答案解释如下。 2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵 14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值 21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上 权值之和相等 26. 是自由树，即根结点不确定 35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。 42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。 45. 能求出关键路径的AOE网一定是有向无环图 46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩 短工期。 48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关 键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。 三．填空题 1.有n个顶点，n-1条边的无向连通图 2.有向图的极大强连通子图 3. 生成树 9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N 16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e
21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈 22. 深度优先 23.宽度优先遍历 24.队列 25.因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。 25题（1） 25题（2） 26.普里姆（prim ）算法和克鲁斯卡尔（Kruskal ）算法 27.克鲁斯卡尔 28.边稠密 边稀疏 29. O(eloge ） 边稀疏 30.O(n 2 ） O(eloge) 31.(1）（V i ，V j ）边上的权值 都大的数 （2）1 负值 （3）为负 边 32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增 负值 35.160 36.O(n 2 ） 37. 50，经过中间顶点④ 38. 75 39.O(n+e ） 40.(1）活动 （2）活动间的优先关系 （3）事件 （4）活动 边上的权代表活动持续时间 41.关键路径 42.（1）某项活动以自己为先决条件 （2）荒谬 （3）死循环 43.（1）零 （2）V k 度减1，若V k 入度己减到零，则V k 顶点入栈 （3）环 44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc 45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j (11)firstadj(g,v 0) (12)not visited[w] (13)nextadj(g,v 0,w) 46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1 (8)indegree[i]==0 47.(1)p^.link:=ch[u ].head (2)ch[u ].head:=p (3)top<>0 (4)j:=top (5)top:=ch[j].count (6)t:=t^.link 48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。) （2） ① top==-1 ② top=graph[j].count ③ graph[k].count==0 四.应用题 1．（1）G1最多n(n-1)/2条边，最少n-1条边 (2) G2最多n(n-1)条边，最少n 条边 (3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的) 2．n-1，n 3.分块对称矩阵 4．证明：具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。
第 7 章 1. 填空题 ⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。 ⑶对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。 【解答】8，59/15 【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。 ⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。 【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。 ⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6 ⑹在散列技术中，处理冲突的两种主要方法是（）和（）。 【解答】开放定址法，拉链法 ⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。
第7章习题 一、单项选择题 1. 在无向图中定义顶点的度为与它相关联的（ ）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2. 在无向图中定义顶点 v i 与v j 之间的路径为从v i 到达v j 的一个（ ）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3. 图的简单路径是指（ ）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4. 设无向图的顶点个数为n ，则该图最多有（ ）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5. n 个顶点的连通图至少有（ ）条边。 A. n-1 B. n C. n+1 D. 0 6. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7. 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8. 图的深度优先搜索类似于树的（ ）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9. 图的广度优先搜索类似于树的（ ）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10. 在用Kruskal 算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（ ）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 11. 在用Dijkstra 算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）。 A. 非零 B. 非整 C. 非负 D. 非正 12. 设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 V2，E1 E2，则称（ ）。 A. G 1是G 2的子图 B. G 2是G 1的子图 C. G 1是G 2的连通分量 D. G 2是G 1的连通分量 13. 有向图的一个顶点的度为该顶点的（ ）。 A. 入度 B. 出度 C. 入度与出度之和 D. (入度﹢出度))／2 14. 一个连通图的生成树是包含图中所有顶点的一个（ ）子图。 A. 极小 B. 连通 C. 极小连通 D. 无环 15. n (n ＞1) 个顶点的强连通图中至少含有（ ）条有向边。 A. n-1 B. n n(n-1)/2 D. n(n-1) 16. 在一个带权连通图G 中，权值最小的边一定包含在G 的（ ）生成树中。 A. 某个最小 B. 任何最小 C. 广度优先 D.深度优先 17. 对于具有e 条边的无向图，它的邻接表中有（ ）个结点。 A. e-1 B. e C. 2(e-1) D. 2e 18. 对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（ ）。 , 4, 5 B. 1, 2, 3, 5 C. 1, 4, 3, 5 D. 1, 2, 4, 3, 5 5412 3
第七章 图 一、选择题 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】 A ．由顶点和相邻顶点序偶构成的边所形成的序列 B ．由不同顶点所形成的序列 C ．由不同边所形成的序列 D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 E ．n 2 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】 3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4 分)】 A ．n-1 B ．n C ．n+1 D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、 6(2分）】 A ．n-l B ．n C ．n+l D ．2n 5．n 个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】 A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A ．0 B ．1 C ．n-1 D ．n 【北京邮电大学 2000 二、5 （20/8分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2 分）】 A ．1/2 B ．2 C ．1 D ．4 8．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。【中山大学 1999一、14】 A ．5 B ．6 C ．8 D ．9 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点 序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 【中科院软件所 1998】 10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A ．邻接矩阵 B ．逆邻接表 C ．邻接多重表 D ．十字链表 E ．邻接 表 【北京工业大学 2001 一、3 (2分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】 A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12． 从邻接阵矩⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101 010 A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确
第7章图 部分答案解释如下。 2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵 14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值 21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上 权值之和相等 26. 是自由树，即根结点不确定 35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。 42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。 45. 能求出关键路径的AOE网一定是有向无环图 46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可 缩短工期。 48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关 键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。 三．填空题 1.有n个顶点，n-1条边的无向连通图 2.有向图的极大强连通子图 3. 生成树 4. 45 5. n(n-1)/2 6 . 7. 9 8. n 9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N 16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e 21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈 22. 深度优先 23.宽度优先遍历 24.队列 25.因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。
25题（1） 25题（2） 26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 27.克鲁斯卡尔 28.边稠密边稀疏 29. O(eloge）边稀疏 30.O(n2） O(eloge) 31.(1）（V i，V j）边上的权值都大的数（2）1 负值（3）为负边 32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增负值 35.160 36.O(n2） 37. 50，经过中间顶点④ 38. 75 39.O(n+e） 40.(1）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续 时间 41.关键路径 42.（1）某项活动以自己为先决条件（2）荒谬（3）死循环 43.（1）零（2）V k度减1，若V k入度己减到零，则V k顶点入栈（3）环 44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc 45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j (11)firstadj(g,v0) (12)not visited[w] (13)nextadj(g,v0,w) 46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1 (8)indegree[i]==0 47.(1)p^.link:=ch[u].head (2)ch[u].head:=p (3)top<>0 (4)j:=top (5)top:=ch[j].count (6)t:=t^.link 48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所 以结果是不唯一的。本答案是按邻接点升序排列给出的。) （2）①top==-1 ②top=graph[j].count ③graph[k].count==0 四.应用题 1．（1）G1最多n(n-1)/2条边，最少n-1条边 (2) G2最多n(n-1)条边，最少n条边 (3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时， 仍是连通的) 2．n-1，n 3.分块对称矩阵 4．证明：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结 点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两 个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回 路的连通图）。 5．证明：该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许 从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分 条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素（A[i][j]=1） 自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号 大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点
第七章图 1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索 算法写出从C开始的深度优先搜索序列。 0 A 1 3 ^ 1 B 3 5 ^ 2 C 3 0 ^ 3 D 4 ^ 4 E ^ 5 F 4 ^ 【解答】 A B F C D E C开始的深度优先搜索序列：CDEABF（唯一的结果） 2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J之间有可能 通过道路连接，则Wij表示这条路的长度。要求每个镇都通公路且所修公路总里 程最短，那么应选择哪些线路来修。 I11112233445 J23564546566 1239102626474 W ij (1).画出该图。 (2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量的实际含义。 (3).图示你所定义的数据结构。 (4).标识出你选择的线路。 【解答】 （1）
（2） #define MAX 6 typedef struct { char vexs[MAX]; // 顶点信息 int arcs[MAX][MAX]; // 边的信息 int vexnum, arcnum; // 顶点数，边数 } MGraph; （3）略 （4）{(1,3), (3,4), (2,4), (4,5), (5,6)} 3．图G 如下所示。 (1).给出该图的所有强连通分量。 (2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。 【解答】 (1) 共4个强连通分量： (2) 1,3,2,6,5,4 一、选择题 1、有6个结点的有向完全图有（）条弧。 A 、36 B 、28 C 、30 D 、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 5 4 6 1 3 2 4 15 10 2 15 20 30 4 10 10
第七章图（参考答案） 7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数； （2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通； （3）任一顶点I的度是第I行非0元素的个数。 7．2（1）任一顶点间均有通路，故是强连通； （2）简单路径V4 V3 V1 V2; （3） 0 1 ∞ 1 ∞ 0 1 ∞ 1 ∞ 0 ∞ ∞∞ 1 0 邻接矩阵 邻接表
（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1 （3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V2 7．4（1）①adjlisttp g; vtxptr i,j; //全程变量 ② void dfs(vtxptr x) //从顶点x开始深度优先遍历图g。在遍历中若发现顶点j，则说明顶点i和j间有路径。{ visited[x]=1; //置访问标记 if (y= =j) { found=1;exit(0);}//有通路，退出 else { p=g[x].firstarc;//找x的第一邻接点 while (p!=null) { k=p->adjvex; if （!visited[k]）dfs(k); p=p->nextarc;//下一邻接点 } } ③ void connect_DFS (adjlisttp g) //基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。设 1<=i ,j<=n,i<>j. { visited[1..n]=0;found=0; scanf (&i,&j); dfs (i); if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）； else printf （” 顶点”,i,”和顶点”,j,”无路径”）； }// void connect_DFS (2)宽度优先遍历 全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。 void bfs(vtxptr x) // { initqueue(q);enqueue(q,x); while (!empty(q)); { y=delqueue(q); if (y= =j) { found=1;exit(0);}//有通路，退出 else {p=g[x].firstarc;//第一邻接点 while (p!=null) {k=p->adjvex; if (! Visted[k]) enqueue(q,k); p=p->nextarc } }// if(y= =j) }//while(!empty(q))
国开放大学数据结构(本科)单元7图 单元测试题含答案 试题1在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。选择一项： A.4 B.1/2 C.2 D.1 反馈 正确答案是：2 试题2邻接表是图的一种（）。 选择一项： A.索引存储结构 B.链式存储结构 C.顺序存储结构 D.散列存储结构 反馈 正确答案是：链式存储结构
试题3如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。 选择一项： A.完全图 B.一棵树 C.连通图 D.有回路 反馈 正确答案是：连通图 试题4下列有关图遍历的说法不正确的是（）。 选择一项： A.连通图的深度优先搜索是一个递归过程 B.图的遍历要求每一顶点仅被访问一次 C.非连通图不能用深度优先搜索法 D.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 反馈 正确答案是：非连通图不能用深度优先搜索法 试题5无向图的邻接矩阵是一个（）。 选择一项：
A.对角矩阵 B.上三角矩阵 C.对称矩阵 D.零矩阵 反馈 正确答案是：对称矩阵 试题6图的深度优先遍历算法类似于二叉树的（）遍历。 选择一项： A.后序 B.层次 C.中序 D.先序 反馈 正确答案是：先序 试题7已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 选择一项： A.V1V2V4V5V8V3V6V7 B.V1V2V4V8V3V5V6V7
C.V1V2V4V8V5V3V6V7 D.V1V3V6V7V2V4V5V8 反馈 正确答案是：V1V2V4V8V5V3V6V7 试题8已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 选择一项： A.abcefd B.aebcfd C.abcedf D.acfdeb 反馈 正确答案是：abcefd 试题9已知如图3所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 选择一项： A.aebcfd B.aedfcb C.acfebd
第七章图 一、选择题 1图中有关路径的定义是（）。【北方交通大学 A由顶点和相邻顶点序偶构成的边所形成的序列 C由不同边所形成的序列D 2.设无向图的顶点个数为n,则该图最多有（）条边。 2 E . n A n-1 B.n(n-1)/2 C . n(n+1)/2D.0 【清华大学1998、5 （2分）】【西安电子科技大1998、6 ( 2分）】 【北京航空航天大学1999 、7 ( 2 分)】 3. 一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学1999 四、4 (4分）】 A n-1 B . n C.n+1D.nlogn ; 4. 要连通具有n个顶点的有向图，至少需要（) 条边。【北京航空航天大学2000 6( 2分）】 A n-1 B . n C.n+l D . 2n 5. n个结点的完全有向图含有边的数目（）。【中山大学1998 二、9（2分）】 A n*n B . n ( n+1) C.n / 2D.n* ( n —l) 6. 一个有n个结点的图，最少有（个连通分 量，最多有（）个连通分量。 A 0 B . 1 C n-1 D . n 【北京邮电大学2000 二、5 （20/8 分）】 7.在一个无向图中，所有顶点的度数之和等于所有边数（ A 1/2 B . 2 C . 1 D . 4 &用有向无环图描述表达式(A+B)* ( (A+B /A ) ［，至少需要顶点的数目为（）。【中山大学1999 、14】 A 5 B . 6 C . 8 D . 9 9. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点 序列是（）。 1998 】 10.下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（） A邻接矩阵B . 逆邻接表 C .邻接多重表 D .十字链表E.邻接 表 【北京工业大学2001、3 (2分）】 11 . 下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2001 、11（2 分）】A有向图B.无向图C.AOV网 D . AOE网 0 1 0 A =10 1 2001 一、24 （2 分）】 B .由不同顶点所形成的序列 .上述定义都不是 ）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的 （分）】 ）倍。【哈尔滨工业大学2001 二、3 （2 A.逆拓扑有序 B .拓扑有序 C .无序的【中科院软件所
第七章图 一、选择题 1．图中有关路径的定义是（）。【北方交通大学2001 一、24 （2分）】A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n2 【清华大学1998 一、5 （2分）】【西安电子科技大1998 一、6 （2分）】 【北京航空航天大学1999 一、7 （2分）】 3．一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学1999 四、4 (4分)】 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（）条边。【北京航空航天大学2000 一、6(2分）】 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（）。【中山大学1998 二、9 （2分）】A．n*n Ｂ．n（n＋１）C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 【北京邮电大学2000 二、5 （20/8分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学2001 二、3 （2分）】 A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。【中山大学1999一、14】 A．5 B．6 C．8 D．9 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序B．拓扑有序C．无序的【中科院软件所1998】 10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。 A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表 【北京工业大学2001 一、3 (2分)】 11．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2001 一、11 （2分）】A．有向图B．无向图C．AOV网D．AOE网12．从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。【中科院软件所1999 六、2（3分）】 ①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确