45) 8090 2535)(50(6070(85(95 55)(70(95 (b) 10-12对于一棵有199999个关键码的199阶B树,试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点) 10-13给定一组记录,其关键码为字符。记录的插入顺序为C,S,DTA,MPLB,W,N,G U,R,K,E,HO,L,丹},给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录 10-14设有一棵B+树,其内部结点最多可存放100个子女,叶结点最多可存储15个记录。 对于1,2,3,4,5层的B+树,最多能存储多少记录,最少能存储多少记录。 10-17设散列表为H∏13],散列函数为H(kgy)=key%13。用闭散列法解决冲突,对下列关 键码序列12,23,45,57,20,03,78,31,15,36造表 (1)采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度。 (2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*key)%10+1,寻找下 个空位的公式为H1=(H1-1+RH(key)%13,H=H(key)。画出相应的散列表,并计算等概 率下搜索成功的平均搜索长度 【解答】 使用散列函数H(key)= key mod13,有 H(12)=12, H(45)=6 H(57)=5, H(20)=7, H(03)=3, H(78)=0, H(31)=5, H(36)=10 (1)利用线性探查法造表 搜索成功的平均搜索长度为 ASL=-(1+1+1+1+1+1+4+1+2+1)=14 搜索不成功的平均搜索长度为 SLm=1(+1+3+2+1+5+43+2+1+5+4+3)=36 (2)利用双散列法造表: Hi=(Hi-1+ RH (key)mod 13, H1=H(key) 15|03 574520313623 (1)(1)(1)(3)(5)(1) 搜索成功的平均搜索长度为 ASLsu= I 1+1+1+1+1+1+3+5+1+1)=16 10 10-18设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所 需记录的平均比较次数不超过2次。试问散列表需要设计多大?设a是散列表的装载因子(a) (b) 10-12 对于一棵有 1999999 个关键码的 199 阶 B_树，试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点)。 10-13 给定一组记录，其关键码为字符。记录的插入顺序为{C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J}，给出插入这些记录后的 4 阶 B+树。假定叶结点最多可存放 3 个记录。 10-14 设有一棵 B+树，其内部结点最多可存放 100 个子女，叶结点最多可存储 15 个记录。 对于 1, 2, 3, 4, 5 层的 B+树，最多能存储多少记录，最少能存储多少记录。 10-17 设散列表为 HT[13], 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关 键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的 平均搜索长度和搜索不成功的平均搜索长度。 (2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下 一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概 率下搜索成功的平均搜索长度。 【解答】 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. (1) 利用线性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索长度为 ASLsucc = 1 10 (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14 10 搜索不成功的平均搜索长度为 ASLunsucc = 1 13 (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 13 (2) 利用双散列法造表： Hi = (Hi-1 + RH (key)) mod 13, H1 = H (key) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 36 23 12 (1) (1) (1) (1) (1) (1) (3) (5) (1) (1) 搜索成功的平均搜索长度为 ASLsucc = 1 10 (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 16 10 10-18 设有 150 个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所 需记录的平均比较次数不超过 2 次。试问散列表需要设计多大？ 设是散列表的装载因子