试题五 北京邮电大学 1992 年硕士研究生入学考试试题
一. 回答下列问题：
1．利用两个栈 sl,s2 模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空
运算。请简述这些运算的算法思想。
2．现有 n*n 阶对角矩阵 M，非零元素集中在
以主对角线为中心的带状区域，其示意图
如图 1 所示。试问：
(1)该对角矩阵有多少非零元素?
(2)带状区域的非零 m
ij
的下标 i，j 与 a 之
间有何关系?试题 5 图 1
3.设 T 是一棵二叉树，除叶子结点外，其
它结点的度数皆为 2，若 T 中有 6 个叶结点，试问：
（1） T 树的最大深度 Kmax=?最小可能深度 Kmin=?
（2） T 树中共有多少非叶结点？
（3） 若叶结点的权值分别为 1，2，3，4，5，6。请构造一
棵哈曼夫树，并计算该哈曼夫树的权路径长度 wpl。
二、图 2 中两线性表 A 和 B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法
求 A 和 B 的并集 AUB。要求该集合中的元素仍保持递增有序。且要利用 A 和 B 的原有结
点空间。（15 分）
三、写出下列各题的结果：（25 分）
1．用无回溯法的模式匹配法（KMP 法）及快速的无回溯的模式匹配法求模式串 T 的
next[j]值，添入下面表中：
j 1 2 3 4 5 6 7
t a a b b a a b
Kmp 法 求 得 的
next[j]值
快速无回溯法求
得的 next[j]值
2．已知广义表 L=((((a))),((b)),(c),d)，试利用 head 和 tail 运算把原子项 c 从 L 中分
离出来。
3．现有一组关键字序列为(13,29,23,44,55,87,25,21,10,79)。利用除留余数法(即
H（key）= key MOD p)构造哈希表,并用线性探测再散列的方法解决冲突。设 P=15，
填装因子
a=0.7
(1)画出构造出的哈希表。
(2)求在查找此哈希表的元素时，在等概率的情况下，查找成功的平均查找长度 ASL=?
4．写出图 3 双链表中对换值为 23 和 l5 的两个结点相互位置时修改指针的有关语句。
