北邮数据结构1993.docVIP

试题六 北京邮电学院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的二叉树，简述前序遍历非递归算法的较优方法。 在已见好的堆中（父结点值≤左，右结点值），再插入两个元素，较好的方法是什么？ 在你所学的数据结构算法中，对某算法提出一个较好的改进设想（思路）。 四、某二叉树采用链接存储，其结点结构是： lc data rc Lc和rc分别指向左子树 根和右子树根的指针域。Data为结点数据域。试写出判断该二叉树是否为二叉排序树的算法（不许另设空间，但可以设一些辅助指针）。设二叉排序树，左子树每个结点值根结点值，右子树每个结点的值≥根结点的值）。二叉树是递归定义的。按此定义写出判断某二叉树是否为二 叉排序树的算法。（20分） 五、图2是有向图按出度建立的邻接表，试写一算法，将此处度邻接表改称入度建立的邻接表。（15分） 六、线性表中有n个元素，每个元素是一个自负，现存于向量R[1..n]中，是写一算法，使R中的字符按字母自负，数字字符和其他字符的顺序排列。要求利用原来的空间，元素移动次数最小。（15分）