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的全部拓扑排序序列是____。
相关推荐：
loading