数据结构错题收录（十三）

作者: 程序员丶星霖 | 来源:发表于2022-11-27 10:42 被阅读0次

数据结构错题收录（十三）
数据结构错题收录（四）
数据结构错题收录（五）
数据结构错题收录（六）
数据结构错题收录（七）
数据结构错题收录（八）
数据结构错题收录（三）
数据结构错题收录（一）
数据结构错题收录（二）
数据结构错题收录（十）

1、已知带权连通无向图G=（V，E），其中V={ $v_1$ ， $v_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$ 的最短路径上经过的顶点序列是（）。

A： $v_1$ , $v_2$ , $v_5$ , $v_7$
B： $v_1$ , $v_3$ , $v_4$ , $v_6$ , $v_7$
C： $v_1$ , $v_3$ , $v_4$ , $v_5$ , $v_7$
D： $v_1$ , $v_2$ , $v_5$ , $v_4$ , $v_6$ , $v_7$

解析

在这里插入图片描述

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

答案：B

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

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

A：Ⅰ、Ⅱ、Ⅳ
B：Ⅰ、Ⅲ、Ⅳ
C：Ⅰ、Ⅱ、Ⅲ
D：全部可以

解析

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

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

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

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

答案：A

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

A：是一个有根的有向图
B：是一个强连通图
C：含有多个入度为0的顶点
D：含有顶点数目大于1的强连通分量

解析

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

答案：D

4、以下关于拓扑排序的说法中，错误的是（）。

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

A：Ⅰ、Ⅲ
B：Ⅱ、Ⅲ
C：Ⅱ
D：Ⅲ

解析

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

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

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

在这里插入图片描述

答案：D

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

A：含有多个出度为0的顶点
B：是个强连通图
C：含有多个入度为0的顶点
D：含有顶点数大于1的强连通分量

解析

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

答案：D

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

在这里插入图片描述

A：4
B：6
C：5
D：7

解析

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

答案：C

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

A：对称
B：稀疏
C：三角
D：一般

解析

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

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

答案：C

8、下列关于图的说法中，正确的是（）。

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

A：Ⅰ、Ⅱ和Ⅲ
B：Ⅲ和 Ⅳ
C：Ⅲ
D：Ⅳ

解析

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

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

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

在这里插入图片描述
有向无环图的拓扑序列唯一并不能唯一确定该图。在下图所示的两个有向无环图中，拓扑序列都为

V_1

，

V_2

，

V_3

，

V_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的关键路径的长度为（）。

A：19
B：20
C：21
D：22

解析

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

在这里插入图片描述

答案：C

10、下面关于求关键路径的说法中，不正确的是（）。

A：求关键路径是以拓扑排序为基础的
B：一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同
C：一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差
D：关键活动一定位于关键路径上

解析

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

答案：C

学海无涯苦作舟

数据结构错题收录（十三）
1、已知带权连通无向图G=（V，E），其中V={，,,,,,}，E={(,)10,(,)2,(,)2,(,)11,...
数据结构错题收录（四）
1、已知表头元素为c的单链表在内存中的存储状态如下表所示。现将f存放于1014H处并插入单链表，若f在逻辑上位于a...
数据结构错题收录（五）
1、若用数组A[0...5]来实现循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素，再...
数据结构错题收录（六）
1、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。 A：h B：2h-1 ...
数据结构错题收录（七）
1、在二叉树中有两个结点m和n，若m是n的祖先，则使用（）可以找到从m到n的路径。 A：先序遍历 B：中序遍历 C...
数据结构错题收录（八）
1、已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（）。 A：115 ...
数据结构错题收录（三）
1、求出下列算法的时间复杂度。解析基本语句k=k+10*i宫执行了n-2次，所以T(n)=O(n)。 2、求出...
数据结构错题收录（一）
1、以下属于逻辑结构的是（） A：顺序表 B：哈希表 C：有序表 D：单链表解析顺序表、哈希表和单链表是三种不...
数据结构错题收录（二）
1、下列函数的时间复杂度是____。 A：O() B：O() C：O(n) D：O() 解析 “sum+=++i;...
数据结构错题收录（十）
1、下列关于广度优先算法的说法中，正确的是（）。 Ⅰ.当各边的权值相等时，广度优先算法可以解决单源最短路径问题 Ⅱ...

数据结构错题收录（十三）

1、已知带权连通无向图G=（V，E），其中V={，,,,,,}，E={(,)10,(,)2,(,)2,(,)11,(,)1,(,)4,(,)6,(,)7,(,)3}（注：顶点偶对括号外的数据表示边上的权值），从源点到顶点的最短路径上经过的顶点序列是（）。

解析

答案：B

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

解析

答案：A

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

解析

答案：D

4、以下关于拓扑排序的说法中，错误的是（）。

解析

答案：D

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

解析

答案：D

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

解析

答案：C

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

解析

答案：C

8、下列关于图的说法中，正确的是（）。

解析

答案：C

9、若某带权图为G=（V，E），其中V={,,,,,,,,,}，E={<,>5,<,>6,<,>3,<,>6,<,>3,<,>3,<,>1,<,>4,<,>4,<,>2,<,>4,<,>5,<,>2,<,>2}（注：边括号外的数据表示边上的权值），则G的关键路径的长度为（）。

解析

答案：C

10、下面关于求关键路径的说法中，不正确的是（）。

解析

答案：C

学海无涯苦作舟

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读