吉林大学96考研题
数据结构部分
[四]解答下列各题(20分)
(1)假定a和b是二叉树形的两个叶节点,如果在先根次序遍历下,节点a 排在节点b的前面,试回答在中根次序遍历下a是否一定排在节点b的前面?并回答为什么!
(2)设T是一棵高度平衡树(又称平衡树),给定关键词K,如果在T中查找K失败,且查找路径上的任一节点的平衡系数皆为零,试回答用高度平衡树插入算法在T中插入关键词为K的新节点后,树T的高度是否一定增加?并回答为什么!
(3)设与记录R1,R2,..,Rn对应的关键词分别是K1,K2,…,Kn。如果存在Ri和Rj使得j<i且尚(Ki<Kj成立,试证明经过一趟起泡后,一定有记录与Ri进 行交换.
[五](15分)假定T是一课三叉树,即树T的每个节点的次数最多为3并且T是有序树.在内存中T以链接方式存储,每个节点的结构为
ILlink Info Mlink Rlinlk
其中,Info为该节点的信息字段,Llink,Mlink和Rlink都是链接字段,分别存储该节点的三个儿子的地址(如果相应的儿子不存在用空链接^表示)请解答:
(1)如果T有n(n>0)个节点,则T的所有节点中空链接 共有多少个?
(2)给出按照森林的后根次序遍历树T的非递归算法;
(3)回答你的算法中所使用的辅助空间的大小(表成n的函数,其中n是T
的节点个数,n>0).
[六](15分)直接两路合并排序算法的一种改进方法叙述如下:首先对输入的文件进行一趟扫描以确定所有可能的有序段;然后合并有序段以实现整个文件的排序。例如,输入的文件为(6 7 4 5 9 2 3 1 8 0)经过一趟扫描后所得到的有序段为(6 7)(4 5 9)(2 3)(1 8)(0);合并有序段的过程如下:
假定文件(R1,R2,..,Rn)中与记录Ri(0<i<n+l)对应的关键词为Ki,算法Merge(R,m,s,t,X)是合并算法,该算法合并两个已经排序的文件(Rm,Rm+1,Rm+1,…,Rs)和(Rs+1,Rs+2,..,Rt),并得到排好序的大文件(Xm,Xm+l,..,Xt).请解答:
(1)按照先扫描后合并的策略给出文件(R1,R2,••,Rn)的排序算法,该算法可直接调用算法Merge.要求算法在最坏情况下的时间复杂性为O(n )
(2)如果一趟扫描后得到的有序段共有L个,试回答你的算法调用算法Merge的次数,并回答为什么?