北邮数据结构1992.docVIP

试题五 北京邮电大学1992年硕士研究生入学考试试题 回答下列问题： 1．利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空 运算。请简述这些运算的算法思想。 2．现有n*n阶对角矩阵M，非零元素集中在 以主对角线为中心的带状区域，其示意图 如图1所示。试问： (1)该对角矩阵有多少非零元素? (2)带状区域的非零mij的下标i，j与a之 间有何关系?试题5图1 3.设T是一棵二叉树，除叶子结点外，其 它结点的度数皆为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]值 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的两个结点相互位置时修改指针的有关语句。 四、已知二叉树的中序遍历序列为GFBEANHM，后序遍历的结点序列为GEBFHNMA。 (20分) (1)画出此二叉树的形态。 (2)写出根据二叉树的中序和后序遍历的结点序列，建立它的二叉链表存储结构的递归 算法。 五、某工程的AOE网络如图4所示。(15分) 图中弧上的权值分别为a1~a10的t个活动的期限。 1.画出该AOE网络的十字链表存储结构。 2.求各事件的最早发生时间ve和最迟发生时间vl，以及各项活动的最早开始时间e和最迟开始时间l.填于下面表中。 事件 ve vl 活动 e l 1 2 3 4 5 6 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 3. 完成该项工程最少需要多少天？哪些活动为关键活动？关键路径是哪一条？ 六、编写一个双向气泡排序的算法，即相邻两边向相反方向起泡。（10分）