当前位置：问答库＞考研试题

一、应用题

1． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

2． 设阶稀疏矩阵A 有t 个非零元素，其三元组表示为

表示A 才有意义？

的个存储单元，用二维数组存储时占用

试问：非零元素的个数t 达到什么程度时用，共占用三元组表

元组）时，用【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三个单元，

只有当表示A 才有意义。解不等式得

3． 快速排序的最大递归深度是多少? 最小递归深度是多少？

【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为

4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

最大递归深度n 。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。

（3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。

所以由上面三棵树转换得到的二叉树如图2所示：

图2

5． （1）对于有向无环图，叙述求拓扑有序序列的步骤；

（2）对于图1，写出它的四个不同的拓扑有序序列。

图1

【答案】（1）对有向图，求拓扑序列步骤为：

1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。

2）在图中删除该顶点及所有以它为尾的弧。

3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

（2）拓扑有序序列如图2:

图2 拓扑有序序列

6． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。

【答案】删除P 后

删除D 后