北邮数据结构1993.doc

文档介绍：试题六北京邮电学院1993年硕士研究生入学试题
一、回答下列问题:(15分)
快速排序是在所有情况下,排序速度最快吗?为什么?在何种情况下使用此排序法最好?
顺序检索,二分检索,哈希(散列)检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法,为什么低效的方法还不放弃?
已知某二叉树的前序序列和后序序列,能否唯一的构造一棵二叉树。是举例说明之。
二、分析或推导下列各题:(18分)
若一棵树中有度数为1至m的各种结点数为n1,n2,…nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。
在改进了的(无回溯)字符串模式匹配中,要先要求next数组的值。下面是求nextval值的算法。
TYPE SAR=ARRAY[1..m] OF INTEGER;
PTY=ARRAY[1..m] OF CHAR;
PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR);
{在模式P中求nextval数组的值}
BEGIN
J:=1;NEXTVAL[1]:=0;K:=0
REPEAT
IF (K = 0)OR(P[J]=P[K])
THEN [J:=J+1;K:=K+1;
IF P[J]=P[K]
THEN NEXTVAL[J]:=NEXTVAL[K]
ELSE NEXTVAL[J]:=K
ELSE K:=NEXTVAL[K]
UNTIL J=M
END;
算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。两出比较语句相同。请分析说明此两处比较语句的含义是什么?
分析此算法在最坏情况下的时间复杂度是多少?
举例分析堆排序方法是否稳定。
三、对下述问题中,简述每一个问题较优的解决方法。(解决问题的基本思想)(17分)
有如图1的二叉树,简述前序遍历非递归算法的较优方法。
在已见好的堆中(父结点值≤左,右结点值),再插入两个元素,较好的方法是什么?
在你