西大 2001 年试题与分析
试题部分
一、问答题
1 二叉树中序遍历非递归算法．不限制 GOTO ，会带来什么问题。说明 GOTO 与结构化程序设计的关系。
2 ．面向对象的程序设计方法的特点是什么？说明封装的含义。
3 ．什么是函数的副作用？
4 ．简述数组与字符串属于线性表的理由。
二、选择题
1 ．在下列算法中， __________ 算法可能出现下列情况；在最后一趟开始之前，所有的元素都不在其
最终的位置上。
A ．堆排序 B ．冒泡排序 C ．插入排序 D ．快速排序
2 ．堆排序是 __________ 类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是
__________ 。
A ．插入 B ．交换 C ．归并 D ．基数 E ．选择
F ． O(n 2 ) 和 O(1) G ． O(nlog 2 n) 和 O(1) H.O(nlog 2 n) 和 O(n) I.O(n 2 ) 和 O(n)
三、写出结果
1 ．已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？
2 ．在后序线索树中，要出 X 结点的前驱结点，请写出相关语句。
Ltag
Lc
Data
Rtag
Rc
3 ．带权结点为 {5 ， 6 ， 7 ， 8 ， 9} ，构造 Huffman 树，计算带权路径长度。
4 ．对一个堆，按二叉树层次进行遍历，是否可以得到一个有序序列，为什么？
5 ．在快速排序算法中能否用队列代替栈，说明原因。
6 ．已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序序列中的第一个结点的指针，是否可
不用递归且不用栈来完成？请简述原因。
7 ．对下面过程写出调用 P(3) 的运行结果。
PROCEDURE p(w:integer);
BEGIN
IF w>0 THEN GEGIN
p(w-1);
writeln(w); { 输出 w}
p(w-1)
END;
END;
8 ．已知长度为 12 的表（ Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec ），按
表中顺序依次插入初始为空的二叉排序树中。画出整个插入后的二叉排序树，并求出在等概率情况下的
查成功的平均查长度。
四、二叉树采用二叉链表存储；
1 ．编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。
2 ．编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
五、已知某哈希表 HT 的装填因子小于 1 ，哈希函数 H(key) 为关键字的第一个字母在字母表中的序
号。
1 ．处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的
程序。
2 ．处理冲突的方法为链地址法。编写一个计算在等概率情况下查不成功的平均查长度的算法。注
意，此算法中规定不能用公式直接求解计算。
六、二叉树采用二叉链表方式存放，对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右
孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的
遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。
七、设计算法，求出无向连通图中距离顶点 V 0 的最短路径长度（最短路径长度以边数为单位计算）为
K 的所有的结点，要求尽可能地节省时间。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。