假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

问答题设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

参考答案： 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63&rdquo...

点击查看完整答案

您可能感兴趣的试卷

你可能感兴趣的试题

1.问答题设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：若查找关键字60，需要依次与哪些关键字比较？

参考答案：查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次...

点击查看完整答案

2.问答题设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：若查找关键字63，需要依次与哪些关键字进行比较？

参考答案：查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配; 然后顺移，与46,47,32...

点击查看完整答案

3.问答题设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：画出哈希表的示意图

参考答案：

4.问答题 对如图所示的3阶B-树，依次执行下列操作，画出各步操作的结果。
①插入90
②插入25
③插入45
④删除60

参考答案：

5.问答题已知如下所示长度为12的表：（Jan， Feb， Mar， Apr， May， June， July， Aug， Sep， Oct， Nov， Dec）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

参考答案：

6.问答题已知如下所示长度为12的表：（Jan， Feb， Mar， Apr， May， June， July， Aug， Sep， Oct， Nov， Dec）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

参考答案：

7.问答题已知如下所示长度为12的表：（Jan， Feb， Mar， Apr， May， June， July， Aug， Sep， Oct， Nov， Dec）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

参考答案：

8.问答题在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。

参考答案：

9.问答题 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树；
② 若查找元素54，需依次与哪些元素比较？
③ 若查找元素90，需依次与哪些元素比较？
④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

参考答案：

10.单项选择题采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）。

A.不一定都是同义词
B.一定都是同义词
C.一定都不是同义词
D.都相同

点击查看答案&解析