2025年吉林省专升本数据结构习题及答案——第六章.pdfVIP

士不可以不弘毅，任重而道远。仁以为己任，不亦重乎?死而后已，不亦远乎?——《论语》

吉林省专升本考试数据结构分章习题及参考答案———选择题

（第六章）

1、在一个有向图中，所有顶点的度入之和等于所有顶点的出度之和的()倍。

A、1/2

B、1

C、2

D、4

2、一个具有n个顶点的有向图最多有（）条边。

A、n×(n-1)/2

B、n×(n-1)

C、n×(n+1)/2

D、n2

3、在一个具有n个顶点的无向图中，要连通全部顶点至少需要()条边。

A、n

B、n+1

C、n-1

D、n/2

4、在一个图中，所有顶点的度数之和等于图的边数的()

A、1/2

B、1

C、2

D、4

5、为便于判别有向图中是否存在回路，可借助于（）。

A、广度优先有哪些信誉好的足球投注网站算法

B、最小生成树算法

C、最短路径算法

D、拓扑排序算法

6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2

B、1

C、2

D、4

7、对于有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其

算法的时间复杂度是()。

A、O(n)

B、O(e)

C、O(n+e)

D、O(nxe)

8、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出

现的是（）。

A、G中有弧Vi，Vj

B、G中有一条从Vi到Vj的路径

C、G中没有弧Vi，Vj

英雄者，胸怀大志，腹有良策，有包藏宇宙之机，吞吐天地之志者也。——《三国演义》

D、G中有一条从Vj到Vi的路径

9、用邻接表表示图进行深度优先遍历时，通常借助()来实现算法。

A、栈

B、队列

C、树

D、图

10、具有n个顶点的有向图最多有()条边。

A、n

B、n(n-1)

C、n(n+1)

D、n2

11、下面哪一方法可以判断出一个有向图是否有环（回路）：

A、深度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

12、3下列关于AOE网的叙述中，不正确的是（）。

A、关键活动不按期完成就会影响整个工程的完成时间

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

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

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

13、图的BFS生成树的树高比DFS生成树的树高()

A、小

B、相等

C、小或相等

D、大或相等

14、任何一个无向连通图的最小生成树。

A、只有一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

15、一个有n个结点的图，最多有（）个连通分量。

A、0

B、1

C、n-1

D、n

16、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是