文档介绍：试题五北京邮电大学1992年硕士研究生入学考试试题
回答下列问题:
,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空
运算。请简述这些运算的算法思想。
*n阶对角矩阵M,非零元素集中在
以主对角线为中心的带状区域,其示意图
如图1所示。试问:
(1)该对角矩阵有多少非零元素?
(2)带状区域的非零mij的下标i,j与a之
间有何关系?试题5图1
,除叶子结点外,其
它结点的度数皆为2,若 T中有6个叶结点,试问:
T树的最大深度Kmax=?最小可能深度Kmin=?
T树中共有多少非叶结点?
若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树,并计算该哈曼夫树的权路径长度wpl。
二、图2中两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法
求A和B的并集AUB。要求该集合中的元素仍保持递增有序。且要利用A和B的原有结点空间。(15分)
三、写出下列各题的结果:(25分)
用无回溯法的模式匹配法(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]值

=((((a))),((b)),(c),d),试利用head和tail运算把原子项c从L中分离出来。
(13,29,23,44,55,87,25,21,10,79)。利用除留余数法(即H(key)= key MOD p)构造哈希表,并用线性探测再散列的方法解决冲突。设P=15,填装因子
a=
(1)画出构造出的哈希表。
(2)求在查找此哈希表的元素时,在等概率的情况下,查找成功的平均查找长度ASL=?
。
四、已知二叉树的中序遍历序列为GFBEANH