第八章 查找(8)

第八章 查找

请写出查找过程中依次和给定值"92"比较的关键字。
(5) 利用关键码分别为10, 20, 30, 40的四个结点，能构造出（ ⑧ ）种不同的二叉搜索树。



28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是
　hi = (h(key) + i(key%5+1))%7 0≤i≤6
（1）画出构造所得的散列表；
（2）求出在等概率情况下查找成功时的平均查找长度。
32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分）
（1）构造散列表；
（2）求查找数34需要的比较次数。
32．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）

元素下标12345678910比较次数八、设有一个关键码的输入序列 { 55, 31, 11, 37, 46
, 73, 63, 02, 07 },
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。