数据结构错题收录(十三)

2022-11-27  本文已影响0人  程序员丶星霖

1、已知带权连通无向图G=(V,E),其中V={v_1v_2,v_3,v_4,v_5,v_6,v_7},E={(v_1,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,v_7)7,(v_6,v_7)3}(注:顶点偶对括号外的数据表示边上的权值),从源点v_1到顶点v_7的最短路径上经过的顶点序列是()。

解析
在这里插入图片描述

题干内容所述的图G如上图所示。A,B,C,D对应的路径长度分别为18,13,15,24。应用Dijkstra算法求出最短路径为B所示路径。

答案:B

2、下面的()方法可以判断出一个有向图是否有环(回路)。

Ⅰ、深度优先遍历
Ⅱ、拓扑排序
Ⅲ、求最短路径
Ⅳ、求关键路径

解析

使用深度优先遍历,若从有向图上的某个顶点u出发,在DFS(u)结束之前出现一条从顶点v到u的边,由于v在生成树上是u的子孙,则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。

拓扑排序时,当某顶点不为任何边的头时才能加入序列,存在环时环中的顶点一直是某条边的头,不能加入拓扑序列。也就是说,还存在无法找到下一个可以加入拓扑序列的顶点,则说明此图存在回路。

求最短路径是允许图有环的。

关键路径能否判断一个图有环,则存在一些争议。关键路径本身虽然不允许有环,但求关键路径的算法本身无法判断是否有环,判断是否有环是求关键路径的第一步——拓扑排序。

答案:A

3、若一个有向图的顶点不能排在一个拓扑序列中,则可判定该有向图()。

解析

若不存在拓扑排序,则表示图中必定存在回路,该回路构成一个强连通分量(顶点数目大于1的强连通分量中必然存在回路)。

答案:D

4、以下关于拓扑排序的说法中,错误的是()。

Ⅰ、若某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ、在拓扑排序算法中为暂存入度为零的顶点,可以使用栈,也可以使用队列
Ⅲ、若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1

解析

Ⅰ中,对于一个存在环路的有向图,使用拓扑排序算法运行后,肯定会出现有环的子图,在此环中无法再找到入度为0的结点,拓扑排序也就进行不下去。

Ⅱ中,注意,若两个结点之间不存在祖先或子孙关系,则它们在拓扑序列中的关系是任意的(即前后关系任意),因此使用栈和队列都可以,因为进栈或队列的都是入度为0的结点,此时入度为0的所有结点是没有关系的。

Ⅲ中,若拓扑有序序列唯一,则很自然地让人联想到一个线性的有向图(错误),下图的拓扑序列也是唯一的,但度却不满足条件。

在这里插入图片描述
答案:D

5、若一个有向图的顶点不能排成一个拓扑序列,则判定该有向图()。

解析

一个有向图中的顶点不能排成一个拓扑序列,表明其中存在一个顶点数目大于1的回路,该回路构成一个强连通分量,从而答案选D。

答案:D

6、下图所示有向图的所有拓扑序列共有()个。

在这里插入图片描述
解析

本图的拓扑排序序列有ABCFDEG,ABCDFEG,ABCDEFG,ABDCFEG和ABDCEFG。

答案:C

7、若一个人有向图具有有序的拓扑排序序列,则它的邻接矩阵必定为()。

解析

对有向图中的顶点适当地编号,使其邻接矩阵为三角矩阵且主对角元素全为零的充分必要条件是,该有向图可以进行拓扑排序。

若一个有向图的邻接矩阵为三角矩阵(对角线上元素为0),则图中必不存在环,因此其拓扑序列必然存在。

答案:C

8、下列关于图的说法中,正确的是()。

Ⅰ、有向图中顶点V的度等于其邻接矩阵中第V行中1的个数
Ⅱ、无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵
Ⅲ、在图G的最小生成树G_1中,某条边的权值可能会超过未选边的权值
Ⅳ、若有向无环图的拓扑序列唯一,则可以唯一确定该图

解析

有向图邻接矩阵的第V行中1的个数是顶点V的出度,而有向图中顶点的度为入度与出度之和,Ⅰ错。

无向图的邻接矩阵一定是对称矩阵,但当有向图中任意两个顶点之间有边相连,且是两条方向相反的有向边(无向图也可视为有两条方向相反的有向边的特殊有向图)时,有向图的邻接矩阵也是一个对称矩阵,Ⅱ错。

最小生成树中的n-1条边并不能保证是图中权值最小的n-1条边,因为权值最小的n-1条边并不一定能使图连通。在下图中,左图的最小生成树如右图所示,权值为3的边并不在其最小生成树中。

在这里插入图片描述
有向无环图的拓扑序列唯一并不能唯一确定该图。在下图所示的两个有向无环图中,拓扑序列都为V_1V_2V_3V_4,Ⅳ错。 在这里插入图片描述
答案:C

9、若某带权图为G=(V,E),其中V={v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_10},E={<v_1,v_2>5,<v_1,v_3>6,<v_2,v_5>3,<v_3,v_5>6,<v_3,v_4>3,<v_4,v_5>3,<v_4,v_7>1,<v_4,v_8>4,<v_5,v_6>4,<v_5,v_7>2,<v_6,v_10>4,<v_7,v_9>5,<v_8,v_9>2,<v_9,v_{10}>2}(注:边括号外的数据表示边上的权值),则G的关键路径的长度为()。

解析

画出题目所表示的图如下,可得到关键路径的长度为21.图中所示的两条路径都是关键路径。

在这里插入图片描述
答案:C

10、下面关于求关键路径的说法中,不正确的是()。

解析

一个事件的最迟发生时间等于Min{以该事件为尾的弧的活动的最迟开始时间,最迟结束时间与该活动的持续时间的差}。

答案:C

学海无涯苦作舟

上一篇下一篇

猜你喜欢

热点阅读