广东工业大学2015数据结构复习题

19. 已知序列67,65,20,61,10,2,7，该序列____（是或不是）堆，如果是，是（大

顶堆或小顶堆）____。

20. 已知序列8,10,29,63,23,9,31，试将其调整为一个大顶堆的结果是____。写出

输出最大数63后，经调整后的大顶堆序列是____。

21. 已知序列40,51,39,52,10,78,21，试将其调整为一个小顶堆的结果是____。写

出输出最小数10后，经调整后的小顶堆序列是____。

22. 堆排序算法的平均时间复杂度是____，最坏情况时间复杂度是____，辅助

存储空间是____。

23. 画出平衡二叉树失衡的四种类型，并指出相应的调整方法 ( 不需要写算法)

第九章 树

1. 已知树T如图所示，试画出其双亲表示法的存储结构。

2. 已知树T如图所示，试画出其孩子表示法的存储结构。

3. 一棵m阶（m>3）B树，若不为空树，则树中的每个结点至多有____棵子树。

A.m-1 B.m C.m+1 D.以上都不是

4. 并查集的合并操作所需的时间主要取决于树的____________；有两种方法可

优化算法效率，分别是_________和__________；

5. 在一棵m阶B树中，若某结点的原有关键字个数等于______________，则

插入一个新关键字将导致该结点分裂；若某结点及相邻兄弟结点的原有的关键字的个数等于______________，则删除一个关键字而导致结点合并。

第十章 图

1. 任何一个带权的无向连通图的最小生成树___

A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在

2. 具有N个顶点的无向图至多有（）条边。___

A. N B. N*(N—1) C. N*(N—1)/2 D. 2N

3. 有n个顶点的无权无向图, 采用邻接数组表示, 图中的边数与邻接矩阵中非

零元素之和的关系是________

A. 1 / 2 B. 相等 C. 2倍 D. 不确定

4. 不带权的有向图中顶点Vi的度等于其邻接矩阵中______；

A . 第i行中的非0元的个数； B. 第i列中的非0元的个数；

C. 第i行中的非0元的个数 + 第i列中的非0元的个数； D. 不能确定

5. 已知无向图G如图所示，从顶点A开始，分别写出深度优先搜索序列和广

度优先搜索序列。

6. 包含8个顶点的连通图的生成树有____个顶点，____条边。

7. 已知某无向图对应的邻接矩阵如下所示，可得该图有____个顶点, ____条边，

其中顶点E的度是____。

8. 已知某有向图对应的邻接矩阵如下所示，可得该图有____个顶点____条边，

其中顶点F的出度是____，入度是____，度是____。

9. 已知图G如图所示，其对应的邻接表共有____个头结点，____个表结点。

10. 已知某图的邻接矩阵如图所示，从顶点A出发对图进行深度优先搜索，得

到的顶点序列为____。从顶点A出发对图进行广度优先搜索，得到的顶点序列为____。分别写出DFS和BFS用C语言描述的算法。

11. 已知某图的邻接表如图所示，从顶点A出发对图进行广度优先搜索，得到的

顶点序列为____。从顶点A出发对图进行深度优先搜索，得到的顶点序列为______。分别写出DFS和BFS用C语言描述的算法。

12. 已知图G如图所示，写出用Kruscal算法求图G最小生成树的过程: (如有权

值相等边，请根据结点从小到大优先原则,如AB=1,BC=1,则选AB!)

13. 已知图G如图所示，初始化顶点A为生成树上的顶点，写出用Prim算法求

图G最小生成树的过程:

14. 已知图G如图所示，图G的全部拓扑排序序列是____。