算法大视界答案2023

第九章测试

1.

普里姆算法是用来解决

A:最小生成树 B:关键路径 C:最短路径 D:拓扑结构
答案:A
2.

设某有向图中有n个顶点，则该有向图对应的邻接表中有（  ）个表头结点

A: 2n-1 B:

 n

C:n-1 D: n+1  3.

设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为

A:2e B:e C:2n D:n 4.

具有6个顶点的无向图至少应该有（      ）条边才能确保是一个连通图

A:6 B:5 C:7 D:8 5.

对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为

A:n×(n+1) B:(n-1)× (n-1) C:n ×n D:(n-1)×n 6.

在对图进行深度优先搜索时，一般需要用到下列哪个数据结构？

A:队列 B:栈 C:二叉树 D:单向链表 7.

下列关于最小生成树的说法中，正确的是(  )。

(1)最小生成树的代价唯一

(2)权值最小的边一定会出现在所有的最小生成树中

(3)用Prim算法从不同顶点开始得到的最小生成树的形态一定相同

(4) Prim算法和Kruskal算法得到的最小生成树的形态总不相同

A:仅(2)  (4) B:仅(2) C:仅(1) D:仅(1)  (3) 8.

求图的最小生成树有两种算法，Kruskal算法适合于求稀疏图的最小生成树

A:错 B:对 9.

6个顶点的连通图的最小生成树，其边数为（）

A:5 B:6 C:4 D:7 10.

设完全无向图中有n个顶点，则该完全无向图中有多少条边

A:(n-1)/2 B:n(n-1)/2 C:n(n+1)/2 D:n(n-1)