数据结构习题及答案(6)

（ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序

?0?1??1??1?1??0??1111101?001001??000100??100110?011010??001101?100010??A．0 2 4 3 1 5 6

B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 0 3 6 1 5 4 2

建议：0 1 3 4 2 5 6

列是

（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是

A． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5

6

（ B ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

A． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5

6

（建议：0 1 2 3 4 5 6）

（ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

A． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6

（ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是

A．0 1 3 2 B. 0 2 3 1

C. 0 3 2 1 D. 0 1 2 3

（ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是

A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

（ A ）14. 深度优先遍历类似于二叉树的

A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

（ D ）15. 广度优先遍历类似于二叉树的

A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

（ A ）16. 任何一个无向连通图的最小生成树

A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 （注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）

二、填空题（每空1分，共20分）

1. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。

2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 3. 如果n个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到n-1条边）

4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。 5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。 6. 设有一稀疏图G，则G采用 邻接表 存储较省空间。 7. 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。 8. 图的逆邻接表存储结构只适用于 有向 图。

9. 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。

10. 图的深度优先遍历序列 不是 惟一的。

11. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；

若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。

12. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；

若采用邻接表存储，该算法的时间复杂度为 O(n+e) 。 13. 图的BFS生成树的树高比DFS生成树的树高 小或相等 。

14. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为

O(n2) ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。 15. 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。 16. 若要求一个稠密图G的最小生成树，最好用 普里姆(Prim) 算法来求解。

17.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。

18. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 三、简答题（每题6分，共24分）

1. 【严题集7.1①】已知如图所示的有向图，请给出该图的:

（1） 每个顶点的入/出度； 顶点 （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。

答案：

入度 出度 1 2 3 4 5 6

2. 【严题集7.7②】请对下图的无向带权图：

（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成

树；

（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成

树。

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）! 邻接矩阵为：

??04? ?403????? ?3555??5?9???506?5? 最小生成树→ ???507?34?????9?700?52???? ????6???554?3??2066? 0??

PRIM算法（横向变化）： V b c d e f g h U V-U Vex a a a a a a a {a} {b,c,d,e,f,g,hlowcos4 3 ∞ ∞ ∞ ∞ ∞ } t Vex a 0 c a a a c {a,c} {b, lowcos4 5 ∞ ∞ ∞ 5 d,e,f,g,h} t Vex 0 0 c b a a c {a,c,b} {d,e,f,g,h} lowcos5 9 ∞ ∞ 5 t Vex 0 0 0 d d d d {a,c,b,d } {e,f,g,h}

lowcost Vex lowcost Vex lowcost Vex lowcost Vex lowcost 邻接表为： a b c d e f g h 0 0 0 0 7 0 0 d 7 0 0 d 7 0 0 f 3 0 0 0 6 5 4 d d 0 6 5 g 0 0 2 0 0 0 {a,c,b,d ,h{e,f,g } } {a,c,b,d ,h{ f,e } ,g} {a,c,b,d ,h{e } ,g, f } 0 0 0 {a,c,b,d ,h{ } ,g, f, e } → b 4 → c 3

5 5 7 3 2 6 6 → a 4 → c 5 → d → a 3 → b 5 → d → b 5 → c 5 → e → b 9 → d 7 → f → d 6 → e 3 → g → d 5 → f 2 → h → c 5 → d 4 → g → e → h → f ^ ^ ^ ^

9 ^ 5 ^ 6 → g 5 → h 4^

(按边归并,堆排序)：

克鲁斯卡尔算法步骤先罗列：f---2---g a—3--c f—3—e a—4---b d—4—h

(a,b,c) (e,f,g) (d,h) 取b—5—d, g—5--d 就把三个连通分量连接起来了。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题及答案(6)在线全文阅读。