《查找技术习题》PPT课件

《《查找技术习题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章查找技术习题课填空1、在数据的存放无规律而言的线性表中进行检索的最佳方法是。顺序查找（线性查找）2、线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。87填空3、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。28显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，

2、则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！3.7填空4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。28，6，12，205、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。散列查找6、散列法存储的基本思想是由决定数据的存储地址。关键字的值填

3、空7、有一个表长为m的散列表，初始状态为空，现将n（n

4、30，88，70，50C）20，50D）30，88，50A选择3、对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A）3B）4C）5D）6C4、链表适用于查找。A）顺序B）二分法C）顺序，也能二分法D）随机A5、折半搜索与二叉搜索树的时间性能。A）相同B）完全不同C）有时不相同D）数量级都是O（log2n）C简答1、对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查

5、找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。简答2、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：1）画出描述折半查找过程的判定树；2）若查找元素54，需依次与哪些元素比较？3）若查找元素90，需依次与哪些元素比较？4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。1）先画出判定树如下（注：mid=(1+12)/2=6）：（判定树略

6、）2）查找元素54，需依次与30,63,42,54等元素比较；3）查找元素90，需依次与30,63,87,95,72等元素比较；4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08简答3、用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?查找某个元素的时间复杂度下限，如果理解为最短查找时间，

7、则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。简答4、设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，并回答下列问题：1）画出哈希表的示意图；2）若查找关键字63，需要依次与哪些关键字进行比较？3）若查找关键字60，需要依次与哪些关键字比较？4）假定每个关键字的查找概率相等，求

8、查找成功时的平均查找长度。（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,4