北京邮电大学 1992-1993年硕士研究生入学考试试题

《北京邮电大学 1992-1993年硕士研究生入学考试试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、试题五北京邮电大学1992年硕士研究生入学考试试题一.回答下列问题：1．利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。2．现有n*n阶对角矩阵M，非零元素集中在以主对角线为中心的带状区域，其示意图如图1所示。试问：(1)该对角矩阵有多少非零元素?(2)带状区域的非零mij的下标i，j与a之间有何关系?试题5图13.设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，试问：（1）T树的最大深度Kmax=?最小可能深度Kmin=?（2）T树中共有多少非叶结点？（

2、3）若叶结点的权值分别为1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的权路径长度wpl。二、图2中两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该集合中的元素仍保持递增有序。且要利用A和B的原有结点空间。（15分）三、写出下列各题的结果：（25分）1．用无回溯法的模式匹配法（KMP法）及快速的无回溯的模式匹配法求模式串T的next[j]值，添入下面表中：j1234567taabbaabKmp法求得的next[j]值快速无回溯法求得的next[j]值2．已知广义表L=((((a)))

3、,((b)),(c),d)，试利用head和tail运算把原子项c从L中分离出来。3．现有一组关键字序列为(13,29,23,44,55,87,25,21,10,79)。利用除留余数法(即H（key）=keyMODp)构造哈希表,并用线性探测再散列的方法解决冲突。设P=15，填装因子a=0.7(1)画出构造出的哈希表。(2)求在查找此哈希表的元素时，在等概率的情况下，查找成功的平均查找长度ASL=?4．写出图3双链表中对换值为23和l5的两个结点相互位置时修改指针的有关语句。四、已知二叉树的中序遍历序列为GFBEANHM，后序遍历的结点序列为G

4、EBFHNMA。(20分)(1)画出此二叉树的形态。(2)写出根据二叉树的中序和后序遍历的结点序列，建立它的二叉链表存储结构的递归算法。五、某工程的AOE网络如图4所示。(15分)图中弧上的权值分别为a1~a10的t个活动的期限。1.画出该AOE网络的十字链表存储结构。2.求各事件的最早发生时间ve和最迟发生时间vl，以及各项活动的最早开始时间e和最迟开始时间l.填于下面表中。事件vevl活动el123456a1a2a3a4a5a6a7a8a9a103.完成该项工程最少需要多少天？哪些活动为关键活动？关键路径是哪一条？六、编写一个双向气泡排序的

5、算法，即相邻两边向相反方向起泡。（10分）试题六北京邮电学院1993年硕士研究生入学试题一、回答下列问题：（15分）1．快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？2．顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？3．已知某二叉树的前序序列和后序序列，能否唯一的构造一棵二叉树。是举例说明之。二、分析或推导下列各题：（18分）1.若一棵树中有度数为1至m的各种结点数为n1,n2,…nm(nm表示度数为m的结点个数)请推导出该

6、树中共有多少个叶子结点n0的公式。2.在改进了的（无回溯）字符串模式匹配中，要先要求next数组的值。下面是求nextval值的算法。TYPESAR=ARRAY[1..m]OFINTEGER;PTY=ARRAY[1..m]OFCHAR;PROCEDUREnext2(P:PTY;VARNEXTVAL:SAR);{在模式P中求nextval数组的值}1BEGIN2J:=1;NEXTVAL[1]:=0;K:=03REPEAT4IF(K=0)OR(P[J]=P[K])5THEN[J:=J+1;K:=K+1;6IFP[J]=P[K]7THENNEXTVA

7、L[J]:=NEXTVAL[K]8ELSENEXTVAL[J]:=K9ELSEK:=NEXTVAL[K]10UNTILJ=M11END;算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。两出比较语句相同。请分析说明此两处比较语句的含义是什么？分析此算法在最坏情况下的时间复杂度是多少？3．举例分析堆排序方法是否稳定。三、对下述问题中，简述每一个问题较优的解决方法。（解决问题的基本思想）（17分）1.有如图1的二叉树，简述前序遍历非递归算法的较优方法。2.在已见好的堆中（父结点值≤左，右结点值），再插入两个元素，较好的方法是什么？3

8、.在你所学的数据结构算法中，对某算法提出一个较好的改进设想（思路）。四、某二叉树采用链接存储，其结点结构是：lcdatarcLc和rc分别指向左子树根