自测题解答
二 综合应用题
1. 树中任意两结点之间都存在一条路径，两结点
的距离即定义为路径的长度。距离最远的两个
结点的距离定义为树的“直径”。给定一棵用
二叉链表存储的二叉树，其结点构造为如图。
指针Root指向根结点。请设计时间复杂度为
O(n)的算法（n为树中结点的个数）求二叉树
的直径。
Left_Child
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
自测题解答
2. 某线性表中最常用的操作是在最后一个元素之 后插入一个元素和删除第一个元素，则采用什 么存储方式最节省运算时间？
A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表
自测题解答
3. 设一个栈的输入序列是 1，2，3，4，5,则下 列序列中，是栈的合法输出序列的是？
A. n – k B. n – k + 1 C. n – k – 1 D. 不能确定
每棵有m个结点的树必有m-1条边 n = m k = m – t （t是树的个数） t=?
自测题解答
8. 已知有向图G=(V, E)，其中V = {v1, v2, v3, v4, v5, v6}，E = {<v1,v2>, <v1,v4>, <v2,v6>,
自测题解答
5. 对二叉排序树进行什么遍历可以得到从小到大 的排序序列 ？
A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历
自测题解答
6. 12个结点的AVL树的最大深度是？
A. 3 B. 4 C. 5 D. 6
等价问题：深度 为h的AVL树的最
少结点数是？
自测题解答
7. 对于一个共有n个结点、k条边的森林，共有几 颗树？
A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4
自测题解答
4. 三叉树中，度为1的结点有5个，度为2的结点3 个，度为3的结点2个，问该树含有几个叶结点？
A. 8 B. 10 C. 12 D. 13
N1 = 5; N2 = 3; N3 = 2 N = N0 + 10 N – 1 = 5*1 + 3*2 + 2*3
自测题解答
1.考研大纲中例题（15分）
2.已知一棵二叉树采用二叉链表存储。现定义二叉树中结 点X0的根路径为从根结点到X0的一条路径，请编写算法 输出该二叉树中最长的根路径（多条最长根路径中只输出 一条即可。算法可用C或C++或JAVA语言实现）。
3.参考答案： 4.计算树的深度，同时记住最深的结点p。 5.然后用非递归先序遍历找到p，此时路径上的结点都在 堆栈中。
<v3,v1>, <v3,v4>, <v4,v5>, <v5,v2>, <v5,v6>}。G的拓扑序列是?
A. v3, v4, v1, v5, v2, v6 B. v1, v3, v4, v5, v2, v6 C. v3, v1, v4, v5, v2, v6 D. v1, v4, v, f
B. a, e, d, f, c, b C. a, c, f, e, b, d
c
b
e
D. a, e, b, c, f, d
f d
自测题解答
12. 以下哪个命题是正确的？
A. 对于带权无向图G = (V, E)，M是G的最小生 成树，则M中任意两点V1到V2的路径一定 是它们之间的最短路径。
Data Right_Child
直径 = max( 左树深度 + 右树深度 )
自测题解答
int BinaryTreeHeight( tree T, int &maxHeightSum ) {
if (!T) return 0; int leftHeight = BinaryTreeHeight(T->Left_Child, maxHeightSum); int rightHeight = BinaryTreeHeight(T->Right_Child, maxHeightSum);
B. P是顶点s到t的最短路径，如果该图中的所 有路径的权值都加1，P仍然是s到t的最短路 径。
C. 深度优先遍历也可用于完成拓扑排序。 D. 以上都不是。
自测题解答
13. 假定有k个关键字互为同义词，若用线性探测 法把这k个关键字存入散列表中，至少要进行 多少次探测？
A. k-1 B. k C. k+1 D. k(k+1)/2
maxHeightSum = max(leftHeight+rightHeight, maxHeightSum); return max(leftHeight, rightHeight) + 1; }
int findRadOfTree( tree Root) {
int maxHeightSum = 0; BinaryTreeHeight(Root, maxHeightSum); return maxHeightSum; }
自测题解答
14. 就排序算法所用的辅助空间而言，堆排序、快 速排序、归并排序的关系是
A. 堆排序 < 快速排序 < 归并排序 B. 堆排序 < 归并排序 < 快速排序 C. 堆排序 > 归并排序 > 快速排序 D. 堆排序 > 快速排序 > 归并排序
自测题解答
15. 下面四种排序算法中，稳定的算法是 A. 快速排序 B. 归并排序 C. 堆排序 D. 希尔排序
数据结构考研辅导 – 例题详解
浙江大学计算机学院
内容提纲
1
自测题解答
2
分类测试
A 线性表、堆栈、队列、数组
B
树与图
C
查找与排序
自测题解答
一 单项选择题：在每小题给出的四个选项中， 请选出一项最符合题目要求的。
1. 从一个具有n个结点的单链表中查找其值等于x 结点时，在查找成功的情况下，需平均比较多 少个结点？
1
3
24
6
5
自测题解答
9. 任何一个带权无向连通图的最小生成树
A. 是唯一的 B. 是不唯一的 C. 有可能不唯一 D. 有可能不存在
自测题解答
10. 判定一个有向图是否存在回路，除了拓 扑排序，还可以用
A. 图的遍历 B. 求最小生成树 C. 最短路径 D. 求关键路径
自测题解答
11. 在图中自a点开始进行深度优先遍历算法可能 得到的结果为