(3)按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。 解 (1)求得的二叉排序树如下图所示,在等概率情况下查找成功的平均查找长度为 ASLm=1(1×1+2×2+3×3+4×3+5×2+6×1)≈42 (2)经排序后的表及在折半查找时找到表中元素所经比较的次数对照如下: Apr Aug Dec Feb Jan July. June Mar May Nov Oct Sept 4 2 等概率情况下查找成功时的平均查找长度为 ASLm=12(×1+2×2+3×4+4×5)=2 (3)按教科书9.2.1节所述求得的平衡二叉树为 June)(May (Apr 它在等概率情况下的平均查找长度为 Asl 12(1×1+2×2+3×4+4×4+5×1)=38 4.选取散列函数H(key)=(3*key)%,用线性探测法处理冲突 地址|值 链接指针 对下列关键码序列构造一个散列地址空间为0~10,表长为1的散列表 0123 解:由题意知,m=11刚好为素数) 08 4.7 则(22+3)%11=6…0 (413)%ll=11…2 53 6 (53*3)%11=14…5 46 701 106 地址 值 链接指针 0 22 1 1 66 2 41 3 3 08 4,7 4 30 5 53 6 46 7 01 8 31 9 10 (3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 解： 4. 选取散列函数 H（key）=（3*key）%11，用线性探测法处理冲突， 对下列关键码序列构造一个散列地址空间为 0～10，表长为 11 的散列表， {22，41，53，08，46，30，01，31，66}。 解：由题意知，m=11(刚好为素数) 则(22*3)%11=6……0 (41*3)%11=11……2 (53*3)%11=14……5