吉大数据结构11996.docVIP

吉林大学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使得ji且尚(KiKj成立，试证明经过一趟起泡后，一定有记录与Ri进 行交换. [五](15分)假定T是一课三叉树，即树T的每个节点的次数最多为3并且T是有序树.在内存中T以链接方式存储，每个节点的结构为 ILlink Info Mlink Rlinlk 其中，Info为该节点的信息字段，Llink,Mlink和Rlink都是链接字段,分别存储该节点的三个儿子的地址(如果相应的儿子不存在用空链接^表示)请解答: (1)如果T有n(n0)个节点，则T的所有节点中空链接 共有多少个? (2)给出按照森林的后根次序遍历树T的非递归算法; (3)回答你的算法中所使用的辅助空间的大小(表成n的函数，其中n是T 的节点个数，n0). [六](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(0in+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的次数，并回答为什么?