1、图模拟试卷 2 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 下列关于广度优先算法的说法正确的是（ ）。I 当各边的权值相等时，广度优先算法可以解决单源最短路径问题 II 当各边的权值不等时，广度优先算法可用来解决单源最短路径问题 III 广度优先遍历算法类似于树中的后序遍历算法实现图的广度优先算法时，使用的数据结构是队列（A）I、（B） II、III 、（C） II、（D）I、III 、Iv2 一个有向图 G 的邻接表存储如图所示，从顶点 1 出发，对图 G 调用深度优先遍历所得顶点序列是（ ）；按广度优先遍历所得顶点序列是（ ）。（A）125436（B） 124
2、536（C） 124563（D）3625143 无向图 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）acfdeb（B） aebd（C） aedb（D）abecdf4 设无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生成树，则下列说法中错误的是（ ）。（A）G为 G 的子图（B） G为 G 的连通分量（C） G为 G 的极小连通子图且 V=V（D）G是 G 的一个无环子图5 图的广度优先生成树的树高比深度优先生成树的树高（
3、）。（A）小或相等（B）小（C）大或相等（D）大6 判断有向图中是否存在回路，除了可以利用拓扑排序外，还可以利用（ ）。（A）求关键路径的方法（B）求最短路径的 Diikstra 算法（C）深度优先遍历算法（D）广度优先遍历算法7 使用 DFS 算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是（ ）。（A）逆拓扑有序（B）拓扑有序（C）无序的（D）都不是8 对图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。（A）4（B） 3（C） 2（D）19 任何一个无向连通图的最小生成树（ ）。（A）有一棵或多棵（B）只有一棵（C）一定有多棵（D）可能不存在10 用 P
4、rim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树（ ）。（A）相同（B）不相同（C）可能相同，可能不同（D）无法比较11 以下叙述中正解的是（ ）。（A）只要无向连通图中没有权值相同的边，则其最小生成树唯一（B）只要无向图中有权值相同的边，则其最小生成树一定不唯一（C）从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树（D）设连通图 G 含有 n 个顶点，则含有 n 个顶点 n-1 条边的子图一定是 G 的生成树12 以下叙述正确的是（ ）。（A）最短路径一定是简单路径（B） Diikstra 算法不适合求有回路的带权图的最短路径（C） Diik
5、stra 算法不适合求任意两个顶点的最短路径（D）Floyd 算法求两个项点的最短路径时，path k-1 一定是 pathk 的子集13 已知带权连通无向图 G=(V，E)，其中 V：v 1， v2，v 3，v 4，v 5，v 6，v 7)，E=(v1，v 2)10，(v 1，v 3)2，(v 3，v 4)2，(v 3，v 6)11，(v 2，v 5)1，(v 4，v 5)4，(v 4，v 6)6，(v 5， v7)7， (v6，v 7)3(注：顶点偶对括号外的数据表示边上的权值)，从源点 v1到顶点 v7 的最短路径上经过的顶点序列是（ ）。（A）v 1，v 2，v 5，v 7（B） v1
6、，v 3，v 4，v 6，v 7（C） v1，v 2，v 3，v 4，v 5，v 7（D）v 1，v 2，v 5，v 4，v 6，v 614 求解最短路径的 Floyd 算法的时间复杂度为（ ）。（A）O(n)（B） O(n+c)（C） O(n2)（D）O(n 3)15 设某个有向无环图中有 n 个顶点，e 条边，采用邻接表存储，进行拓扑排序时的时间复杂度为（ ）。（A）O(nlog 2e)（B） (n+e)（C） (elog2n)（D）(en)16 若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图（ ）。（A）含有多个出度为 0 的顶点（B）是个强连通图（C）含有多个入度为 0 的顶点
7、（D）含有顶点数大于 1 的强连通分量17 下面哪一方法可以判断出一个有向图是否有环(回路)（ ）。I,深度优先遍历 II,拓扑排序 III,求最短路径 ,求关键路径（A）I、II（B） I、III、（C） I、II、 I（D）全部可以18 在有向图 G 的拓扑序列中，若顶点 vi 在顶点 vj 之前，则下列情形不可能出现的是（ ）。（A）G 中有弧 i，v j（B） G 中有一条从 vi 到 vj 的路径（C） G 中没有弧 i，v j（D）G 中有一条从 vi 到 vj 的路径19 如图所示有向图的所有拓扑序列共有（ ）个。（A）4（B） 6（C） 5（D）720 若一个有向图具有有序的拓
8、扑排序序列，那么它的邻接矩阵必定为（ ）。（A）对称（B）稀疏（C）三角（D）一般21 以下关于拓扑排序的说法中错误的是（ ）。I，如果某有向图存在环路，则该有向图一定不存在拓扑排序 II，在拓扑排序算法中，为暂存入度为零的顶点可以使用栈，也可以使用队列 III，若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1（A）I、III（B） II、I（C） II（D）In22 若某带权图为 G=(V， E)，其中 V=v1，v 2，v 3，v 4，v 5，v 6，v 7，v 8，v 9，v 10)，E=(v1，v 2)5，(v 1，v 3)6， (v2，v 5)3，(v 3，v 5)6
9、，(v 3，v 4)3，(v 4，v 5)3，(v 4，v 7)1，(v 4， v8)4， (v5，v 6)4， (v5，v 7)2，(v 6，v 10)4，(v 7，v 9)5，(v 8，v 9)2，(v 9，v 10)2)(注：边括号外的数据表示边上的权值)，则 G 的关键路径的长度为（ ）。（A）19（B） 20（C） 21（D）2223 下面关于求关键路径的说法不正确的是（ ）。（A）求关键路径是以拓扑排序为基础的（B）一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同（C）一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差（D）关键活动一定位
10、于关键路径上24 能有效缩短关键路径长度的方法是（ ）。（A）缩短任意一个活动的持续时间（B）缩短关键路径上任意一个关键活动的持续时间（C）缩短多条关键路径上共有的任意一个关键活动的持续时间（D）缩短所有关键路径上共有的任意一个关键活动的持续时间二、综合题25 对一棵结点数为 n 的满二叉树，回答下面问题：(1)有多少个叶结点 ?(2)有多少个非终端结点?(3)二叉树的深度为多少?26 可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请分析对于循环单链表实现的队列，用哪种方案更合适。27 一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少?28 快速排序的最大递归
11、深度是多少?最小递归深度是多少?图模拟试卷 2 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 A【试题解析】 广度优先遍历，是一层一层向外层扩展遍历图顶点，因此无法考虑到边权值，只适合求边权值相等的图的单源最短路径。【知识模块】 图2 【正确答案】 A【知识模块】 图3 【正确答案】 D【试题解析】 画出 V 和 E 对应的图 G，然后再根据搜索算法求解。【知识模块】 图4 【正确答案】 B【试题解析】 连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路，这样就不是生成树了。【知识模块】 图
12、5 【正确答案】 A【试题解析】 对于无向图的广度优先搜索生成树中，起点到其他顶点的路径是图中对应的最短路径，也即是所有生成树中树高最小的。此外，深度优先总是尽可能“深”地搜索图，因此其路径也是尽可能的长，故深度优先生成树的树高总是大于或等于广度优先生成树的树高。【知识模块】 图6 【正确答案】 C【试题解析】 对每个访问的顶点做标记，若深度优先遍历访问到已标记的顶点，说明存在回路。【知识模块】 图7 【正确答案】 A【试题解析】 DFS 算法对一个有向图做深度优先遍历，并未专门判断有向图是否有环(有向回路) 存在，无论图中有环还是无环，都得到一个顶点序列。如果无环，这个顶点序列就是一个拓扑有
13、序的序列。在退出递归过程中输出的应是逆拓扑有序序列。如果有环，这个顶点序列不是拓扑有序序列。【知识模块】 图8 【正确答案】 B【试题解析】 可以得到 3 种不同的拓扑序列 abced，abecd，aebcd，故选 B。【知识模块】 图9 【正确答案】 A【试题解析】 当无向连通图存在权值相同的多条边时，最小生成树可能是不唯一的，另外，由于这是一个无向连通图，故而最小生成树必定存在。从而选 A。【知识模块】 图10 【正确答案】 C【试题解析】 由于无向连通图的最小生成树可能唯一，可能不唯一，所以用不同的算法生成的最小生成树可能不同，但当无向连通图的最小生成树唯一时，不同的算法生成的必定是相同
14、的最小生成树。【知识模块】 图11 【正确答案】 A【试题解析】 选项 A 显然正确；选项 B，如果无向图本身就是一棵树，则最小生成树就是它本身，这个时候就是唯一的；选项 C，选取的 nl 条边可能构成回路：选项 D，含有 n 个顶点 n 一-1 条边的子图可能构成回路，也可能不连通。【知识模块】 图12 【正确答案】 A【试题解析】 Dijkstra 算法适合求解有回路的带权图的最短路径问题，也可以求任意两个顶点的最短路径。在用：Floyd 算法求两个顶点的最短路径时，当最短路径发生更改时，pathk 就不是 pathk 的子集。【知识模块】 图13 【正确答案】 B【试题解析】 A、B、C
15、、D 对应的路径长度分别为 18、13、15、24。应用Dijkstra 算法不难求出最短路径为 v1-v2-v3-v4-v5-v6-v7。【知识模块】 图14 【正确答案】 D【试题解析】 因为 Floyd 算法是基于图的邻接矩阵存储表示的，由前面的考点讲解部分，不难得出选 D。【知识模块】 图15 【正确答案】 B【试题解析】 拓扑排序需要修改每个顶点的入度，采用邻接表存储时对应的时间复杂度为 O(n+e)，故选 B。【知识模块】 图16 【正确答案】 D【试题解析】 一个有向图中的顶点不能排成一个拓扑序列，则表明其中存在一个顶点数目大于 1 的回路(环)，该回路构成一个强连通分量。从而答
16、案选 D。【知识模块】 图17 【正确答案】 A【试题解析】 使用深度优先遍历算法，如果从有向图上某个顶点 u 出发，在DFS(u)结束之前出现一条从顶点 v 到 u 的边，由于 v 在生成树上是 u 的子孙，则图中必定存在包含 u 和 v 的环，因此深度优先遍历的方法可以检测出一个有向图是否有环。拓扑排序时，当某顶点不为任何边的头时才能加入序列，存在环路时环路中的顶点一直是某条边的头，不能加入拓扑序列。也就是说，还存在顶点但无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路。最短路径是允许有环的，而关键路径虽然不允许有环，但求关键路径的算法本身无法判断是否有环。【知识模块】 图18 【
17、正确答案】 D【试题解析】 如果图 G 中存在一条 vivj 的路径，中间的“”表示中间路径所经过的结点，从而 vj 的入度比 vi 的入度更早地为 0，从而拓扑序列中必然是先输出 vj，再输出 vi，这显然与题意矛盾。【知识模块】 图19 【正确答案】 C【知识模块】 图20 【正确答案】 C【试题解析】 此题一直以来争议较大，是因为有些书中漏掉了“有序”二字，可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。如果这个题目把“有序”二字去掉，显然应该选 D。但此题题干中已经指出是“有序的拓扑序列 ”，从而应该选 C。需要注意
18、的是，如果一个有向图的邻接矩阵为三角矩阵(对角线上元素为 0)，则它的拓扑序列必然存在。【知识模块】 图21 【正确答案】 D【试题解析】 I 中，对于一个存在环路的有向图，使用拓扑排序算法运行后，肯定会出现有环的子图，在此环中就无法再找到入度为 0 的结点了，拓扑排序也就进行不下去了。II 中，注意，如果两个结点之间不存在祖先或子孙关系的话，则它们在拓扑序列中的关系是任意的(即前后关系任意)，从而使用栈和队列都可以，因为进栈或队列的都是入度为 0 的结点，此时入度为 0 的所有结点是没有关系的。I 中，可假设两个孤立的顶点，虽满足题设要求，但拓扑排序不唯一。【知识模块】 图22 【正确答案】
19、 C【知识模块】 图23 【正确答案】 C【试题解析】 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间相同，或者等于最迟结束时间与该活动的持续时间的差。【知识模块】 图24 【正确答案】 D【试题解析】 关键路径是始点和终点间的最长路径，只有所有关键路径的长度都缩短，整个图的关键路径才能有效缩短，但也不能任意缩短，一旦缩短到一定程度，该关键活动可能变成非关键活动了。【知识模块】 图二、综合题25 【正确答案】 (1)由满二叉树的性质可知叶子结点只能出现在第 i 层，叶子结点的个数为(n+1)2。 (2)由于结点总数为 n，叶子结点数 n0 为(n+1) 2，二叉树中的非终端结点个数
20、为 n1=n01 所以非终结点为(n1)2。 (3)满二叉树中的结点个数就为 1+2+4+2i-1=n，因此树的深度为 i=log2(n+1)。 树的深度为 log2(n+1)。【知识模块】 图26 【正确答案】 循环单链表若只设头指针，则出队操作时间因为要更新尾节点的指针，入队操作也需要操作尾结点，而由于查找队尾结点必须从队头开始，所以时间复杂度均为 O(n)。循环单链表若只设尾指针，则出队和入队操作的时间复杂度均 O(1)。【知识模块】 图27 【正确答案】 左右子树均不空的二叉树先序线索化后，空指针域为 1 个(最后访问结点的右链为空)。【知识模块】 图28 【正确答案】 设待排序记录的个数为 n，则快速排序的最小递归深度为log 2n+1，最大递归深度 n。【知识模块】 图
