算法大视界章节测试课后答案2024春

第九章测试

1.普里姆算法是用来解决
A:最短路径 B:关键路径 C:拓扑结构 D:最小生成树
答案:D
2.设某有向图中有n个顶点，则该有向图对应的邻接表中有（  ）个表头结点
A: n+1  B: 2n-1 C:n-1 D: n 3.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为
A:2e B:n C:2n D:e 4.具有6个顶点的无向图至少应该有（      ）条边才能确保是一个连通图
A:8 B:5 C:6 D:7 5.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为
A:(n-1)×n B:(n-1)× (n-1) C:n×(n+1) D:n ×n 6.在对图进行深度优先搜索时，一般需要用到下列哪个数据结构？
A:二叉树 B:队列 C:单向链表 D:栈 7.下列关于最小生成树的说法中，正确的是(  )。(1)最小生成树的代价唯一(2)权值最小的边一定会出现在所有的最小生成树中(3)用Prim算法从不同顶点开始得到的最小生成树的形态一定相同(4) Prim算法和Kruskal算法得到的最小生成树的形态总不相同
A:仅(2)  (4) B:仅(1) C:仅(2) D:仅(1)  (3) 8.求图的最小生成树有两种算法，Kruskal算法适合于求稀疏图的最小生成树
A:对 B:错 9.6个顶点的连通图的最小生成树，其边数为（）
A:5 B:4 C:7 D:6 10.设完全无向图中有n个顶点，则该完全无向图中有多少条边
A:n(n+1)/2 B:n(n-1) C:(n-1)/2 D:n(n-1)/2