16顺序查找和对分查找

16顺序查找和对分查找 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。 2. 线性有序表(a，a，a，…，a)是从小到大排列的， 123256 对一个给定的值k，用二分法检索表中与k相等的元素， 在查找不成功的情况下，最多需要检索 log256 + 1 次。 2 设有100个结点，用二分法查找时，最大比较次数是 log100 取整 + 1 。 2 3. 假设在有序线性表a[20]上进行折半查找， 则比较一次查找成功的结点数为__1(中间的)_; 比较两次查找成功的结点数为 2(左右中间的) ; 比较四次查找成功的结点数为 ;平均查找长度为 。 问:有n个元素的线性表， 比较k次查找成功的节点数有___个, 平均查找长度是:_____? 4( 折半查找有序表(4，6，12，20，28，38，50，70，88，100)， 若查找表中元素20，它将依次与表中元素 28, 6 , 12, 20 比较大小。 二、单项选择题 ( )1(在表长为,的链表中进行线性查找，它的平均查找长度为 ,. ,,,,,; ,. ,,,,(,，,),,; n,. ,,,,，,; ,. ,,,?,,,(,，,),, , ( )2( 折半查找有序表(4，6，10，12，20，30，50，70，88，100)。若查找表中元素58，则它 将依次与表中 比较大小，查找结果是失败。 A(20，70，30，50 B(30，88，70，50 C(20，50 D(30，88，50 ( )3( 对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A(3 B(4 C(5 D( 6 ( )4. 链表适用于 查找 A(顺序 B(二分法 C(顺序，也能二分法 D(随机 5. 数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法;而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案: A:?顺序存储线性表 ?非顺序存储非线性表 ?顺序存储非线性表 ?非顺序存储线性表 B: ? 不需要移动结点，不需改变结点指针 ?不需要移动结点，只需改变结点指针 ?只需移动结点，不需改变结点指针 ?既需移动结点，又需改变结点指针 C:? 顺序查找 ?循环查找 ?条件查找 ?二分法查找 D:? 顺序查找 ?随机查找 ?二分法查找 ?分块查找 1 E:? 效率较低的线性查找 ?效率较低的非线性查找 ?效率较高的非线性查找 ?效率较高的线性查找 答案:A, B, C, D, E, 三、简答题 1. 对分(折半)查找适不适合链表结构的序列，为什么,用二分查找的查找速度必然比线性查找的速度快，这种说法对吗, 2. 假定对有序表:(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题: (1) 画出描述折半查找过程的判定树; (2) 若查找元素54，需依次与哪些元素比较, (3) 若查找元素90，需依次与哪些元素比较, (4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 2