《查找技术习题课》PPT课件.ppt

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

1、第7章查找技术习题课Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.填空1、在数据的存放无规律而言的线性表中进行检索的最佳方法是。顺序查找（线性查找）2、线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。87Evaluationonly.CreatedwithAspose.Slidesfo

2、r.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.填空3、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。28显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！3

3、.7Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.填空4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。28，6，12，205、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。散列查找6、散列法存储的基本思想是由决定数据的存储地址。关键字的值Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5Clie

4、ntProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.填空7、有一个表长为m的散列表，初始状态为空，现将n（n

5、L=（n+1）/2C）ASL=+1D）ASL≈log2（n+1）-1B2、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。A）20，70，30，50B）30，88，70，50C）20，50D）30，88，50AEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.选择3、对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A）3B）4C）

6、5D）6C4、链表适用于查找。A）顺序B）二分法C）顺序，也能二分法D）随机A5、折半搜索与二叉搜索树的时间性能。A）相同B）完全不同C）有时不相同D）数量级都是O（log2n）CEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.简答1、对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点

7、时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.简答2、假定对有序表：（3，4，5，7，24，30，42，54，63，7