第7章查找技术习题课.ppt
《第7章查找技术习题课.ppt》由会员分享,可在线阅读,更多相关《第7章查找技术习题课.ppt(18页珍藏版)》请在课桌文档上搜索。
1、第7章 查找技术习题课,填空,1、在数据的存放无规律而言的线性表中进行检索的最佳方法是。,顺序查找(线性查找),2、线性有序表(a1,a2,a3,a256)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索 次。设有100个结点,用二分法查找时,最大比较次数是。,8,7,填空,3、假设在有序线性表a20上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为;比较四次查找成功的结点数为;平均查找长度为。,2,8,显然,平均查找长度O(log2n)5次(25)。但具体是多少次,则不应当按照公式,来计算(即(21log221)/
2、204.6次并不正确!)。因为这是在假设n2m-1的情况下推导出来的公式。应当用穷举法罗列:全部元素的查找次数为(122438455)74;ASL74/20=3.7!,3.7,填空,4、折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素 比较大小。,28,6,12,20,5、在各种查找方法中,平均查找长度与结点个数n无关的查找方法是。,散列查找,6、散列法存储的基本思想是由 决定数据的存储地址。,关键字的值,填空,7、有一个表长为m的散列表,初始状态为空,现将n(nm)个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法。如
3、果这n个关键码的散列地址都相同,则探测的总次数是。,n(n-1)/2=(12n-1),选择,1、在表长为的链表中进行线性查找,它的平均查找长度为。A)ASL=nB)ASL=(n+1)/2C)ASL=+1D)ASLlog2(n+1)-1,B,2、折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中 比较大小,查找结果是失败。A)20,70,30,50B)30,88,70,50C)20,50D)30,88,50,A,选择,3、对22个记录的有序表作折半查找,当查找失败时,至少需要比较 次关键字。A)3B)4C)5D)6,C,4、链表适用于
4、 查找。A)顺序B)二分法C)顺序,也能二分法D)随机,A,5、折半搜索与二叉搜索树的时间性能。A)相同B)完全不同C)有时不相同D)数量级都是O(log2n),C,简答,1、对分(折半)查找适不适合链表结构的序列,为什么?用二分查找的查找速度必然比线性查找的速度快,这种说法对吗?,不适合!虽然有序的单链表的结点是按从小到大(或从大到小)顺序排列,但因其存储结构为单链表,查找结点时只能从头指针开始逐步搜索,故不能进行折半查找。二分查找的速度在一般情况下是快些,但在特殊情况下未必快。例如所查数据位于首位时,则线性查找快;而二分查找则慢得多。,简答,2、假定对有序表:(3,4,5,7,24,30,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 查找 技术 习题

链接地址:https://www.desk33.com/p-750653.html