给定一组记录,其关键码为字符,记录的插人顺序为(C,S,D,T,A,M,P,I,B,W,N,G,U,R,K,E,H,O,L,J),给出插入这些记录后的4阶B+树。
解决问题的一种方法是使用2-d树。2-d树类似于二叉搜索树,不同之处在于:
◇偶数层用keyl来比较:在该层上每一结点的keyl都大于共左子树中任一结点的key1,都不大于其右子树中任一结点的keyl。
◇奇数层用key2来比较:在该层上每一结点的key2都大于其左子树中任一结点的key2,都不大于其右子树中任一结点的key2.
◇树的根结点处于第0层。每次插入或搜索都从根结点出发,逐层比较。新结点应作为叶结点插入,
臂如,可以将不同人的姓和名(假设没有同名同姓者)分别为keyl和key2,建立一棵2-d树.作为例子,图7-27就是将清华大学的历任校长,按共任职年代的先后次序(周白齐、唐国安、周春、金邦正、曹云祥、严鹤龄、罗家伦、梅贻琦、叶企孙、蒋南翔、高景德、张孝文、王大中、顾秉林),顺序插人而形成的一棵2-d树。
(1)若命名树结点的类名为kdTNode,树的类名为kdTrce,关键码keyl的数据类型为T1,关键码key2的数据类型为T2,试写出2-d树的模板类结构定义,包括构造函数、复制构造函数、求树高、按给定值搜索、查找左子女、查找右子女、查找父结点、插人、删除等函数。此外,还要定义对树结点私有数据成员的存取函数(只要求写出函数的原型,不必给出代码实现)。
(2)基于上述定义,写出其中一个成员函数的实现代码:从根开始搜索关键码keyl和
key2与给定值vall和val2匹配的结点。函数的形式为:
若搜索成功,则函数返回true值,同时引用参数pt指向搜索到的结点,另引用参数pr指向结点*pt的父结点。此时,若树中只有一个结点,pr为NULL。
若搜索不成功或树为空,则函数返回false值,同时参数pt为NULL,在树非空时,pr则指向搜索失败前指针pt最后到达的结点;当树为空时,pr为NULL。
(1)设计散列表的类。
(2)设计在散列表中搜索具有指定关键码值表项的算法.
(3)设计在散列表中册除具有指定关键码值表项的算法.
(4)设计在散列表中插人具有指定关键码值表项的算法。
(5)设计出一组关键码值建立散列表的算法。
(6)设计输出散列表的算法。
(7)求搜索成功时的平均搜紫长度的算法。
(8)求搜索不成功时的平均搜索长度的算法。
插入初始为空的二叉搜索树中,请画出所得到的树T。然后画出删除for之后的二叉搜索树T',若再将for插人T'中得到的二叉搜索树T''是否与T'相同?
A、3,5,12,8,28,20,15,22,19
B、3,5,12,19,20,15,22,8,28
C、3,8,12,5,20,15,22,28,19
D、3,12,5,8,28,20,15,22,19
设散列表为,即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为:
其中,函数Rev(x)表示颠倒10进制数x的各位,如Rev(37)=73,Rev(7)一7等。若插入的关键码值序列为(2,8,31,20,70,59,25,28)。
(1)试画出插人这8个关键码值后的散列表。
(2)计算搜索成功的平均搜索长度。
利用B树作文件索引时,若假设磁盘页块的大小是4000字节(实际也许是4096字节,为了计算方便,此处取成4000字节),指示磁盘地址的指针需要5个字节。现在有20000000个记录构成的文件,每个记录为200字节,其中包括关键码5个字节。试问在此采用B树作索引的文件中,B树的阶数应为多少?假定文件数据部分来按关键码有序排列,则索引部分需要占用多少磁盘页块?