2022年数据结构查找 .pdf

《2022年数据结构查找 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构查找 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、练习九一.单选题1.成功的折半查找其时间复杂度为_ 。A)O(log2n) B)O(log2n/2) C)O(n)D)O(n/2) 2.成功的折半查找所需最少时间为_ 。A)O(1)B)O(2) C)O(n-1) D)O(n+1) 3.在使用散列法存储时，碰撞（冲突）是指_ 。A)不同的关键码值对应到相同的存储地址B)两个元素具有相同序号C)两个元素的关键码值不同，而非码属性相同D)负载因子太大4.从理论上讲，将数据以_ 结构存放，则查找一个数据所用时间不依赖于数据的个数。A)散列 B)二叉查找树 C)链表 D)二叉树5.对线性表采用折半查找法，该线性表必须_。A)采用顺序存储结构，且元素按值

2、有序B)采用顺序存储结构C)采用链式存储结构D)采用链式存储结构，且元素按值有序6.设哈希表长m=14,哈希函数H(key)=key%11 。表中已有4 个结点 : 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49 的结点的地址是 _。A）8B）9C）5 D）3 7.采用顺序查找方法

3、查找长度为n 的线性表时 ,每个元素的平均查找长度为 _。A)n/2 B)(n+1)/2 C)nD)(n-1)/2 8.有一个有序表 (2，5，9，14，36，54，68，72，77，82，95，99)，当采用折半查找值为82 的结点时， _次比较后查找成功。A)2 B)4 C)6 D)8 9.在线性表的散列存储中，添装因子是哈希表装满程度的标志。若用 m 表示哈希表的长度， n 表示待存储元素的个数，则等于_。A)m/nB)n/mC)m/(n-1)D)(n-1)/m 10.设哈希表的表长为14，哈希函数为 H(key)=key%13 ，表中已有 4 个结点: H(15)=2, H(16)=3

4、, H(43)=4, H(83)=5 ， 其余地址为空 ,如用二次探测再散列处理冲突，关键字为28 的结点的地址是 _。A)0 B)1 C)6 D)7 11.以下术语，不属于存储结构的是_。A)顺序表 B)有序表 C)Hash表 D)单链表12.在线性表的散列存储中，下面_不是处理冲突的方法。A)开放地址法 B)再哈希法 C)折半查找法 D)公共溢出区法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 13.以下说法错误的是 _。

5、A)哈希存储的基本思想是由关键字的值决定数据的存储地址B)填装因子是哈希法的一个重要参数，它反映哈希表的填装程度C)哈希表的结点中只包含数据元素本身的信息，不包含任何指针D)哈希表的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法14.下面_不是静态查找表的表示方法。A)顺序表 B)有序表 C)线性表 D)静态树表15.下面_是动态查找表的表示方法。A)顺序表 B)散列表 C)平衡二叉树 D)静态树表16.动态查找表的表示方法是_。A)顺序表 B)散列表 C)静态树表 D)二叉排序树二、判断题1.查找表中数据元素的任何数据项都可以作为关键字。2.动态查找表适合用于检索与修改(插入和

6、删除 )交叉进行的场合。3.Hash表的平均查找长度与处理冲突的方法无关。4.折半查找法的查找速度一定比顺序查找法快。(注意特例 ) 5.二叉树排序树中插入一个新结点，总是插入到叶结点下面。6.二叉树排序树删除一个结点后，仍是二叉树排序树。三、填空题1.由 1000 个数据元素组成的有序表，假设比较表中一个元素所需时间为0.5 毫秒，则顺序查找时，平均查找一个元素的时间约为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - _ 毫秒

7、。 250 2.设线性表（ a1,a2, ,a500）中所有元素的值由小到大排列，对一个给定的值 k，用二分法查找表中与k 相等的元素，在查找不成功的情况下，至多需要比较 _ 次。9 3.在用散列表进行检索时，处理冲突的方法有几种，它们是_、再哈希法、链地址法和建立公共溢出区法。开放地址法4.在用散列表进行检索时，处理冲突的方法有几种，它们是开放地址法、再哈希法、 _ 和建立公共溢出区法。链地址法5.查找表按其所包含的不同运算，可以分为_查找表和动态查找表。静态6.查找表按其所包含的不同运算，可以分为静态查找表和_查找表。动态7.在关键字序列（ 07，12，15，18，27，32，41，92）

8、中用二分法查找和给定值 07 相等的关键字时，查找过程中依次和“07”比较的关键字是 _ 。18 12 07 8.以折半查找方法查找一个线性表时，此线性表必须是顺序存储的_表。有序9.在索引查找方法中， 首先查找 _ ， 然后再查找相对应的块。索引10.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_ 。有序序列11.以顺序查找方法从长度为n 的线性表中查找一个元素的时间复杂名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - -

9、度为_。O(n) 四、应用题1简述顺序查找法、折半查找法和索引顺序表查找法对被查找表中元素的要求，每种查找法对长度为n 的表的等概率平均查找长度是多少？1参考答案：(1)顺序查找：表中元素可以任意存放，查找成功平均查找长度为( n+1)/2 (2)折半查找：表中元素必须以关键字值的升序或降序进行有序排列，并且只能存放在顺序表中。查找成功平均查找长度为log2( n+1)-1。(3)索引查找：索引表有两部分组成， 一个索引表和一个顺序表。 顺序表中元素被划分成一些子表（块） ，子表内数据不要求有序 ;但对于任意两个子表块来说， 排在前面的子表中的任意数据的键值不能大于或小于排在后面的子表中的所有

10、数据元素的键值。若用顺序查找确定所在的块，每块含 s个元素。平均查找长度为( n/s+ s)/2+1。四、应用题1已知一个散列表如下图所示：其散列函数为H(key)=key%13 ，即d0=H(key)； 处 理 冲 突 的 方 法 为 双 重 散 列 法 ， 探 查 序 列 为 ：di=(H(key)+i*H1(key)%13 ，i=1,2,12 其中H1(key)=key%11+1 ，回答下列问题：(1)写出对表中关键字8，15，21 和 34 进行查找时的操作过程，所需名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精

11、心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 进行的比较次数各为多少？(2)该散列表在等概率查找时查找成功的平均查找长度为多少？1582123340123456789101112 参考答案：di=(H(key)+i*H1(key)%13, i=1,2,12 8 ：d0=H(8)=8, d1=(8+1*(8%11+1)%13 =4, 查找成功，比较 2 次。15：d0=H(15)=2, 查找成功，比较 1 次。21：d0=H(21)=8, 查找成功，比较 1 次。34：d0=H(34)=8, d1=(8+1*(34%11+1)%13=10, d2

12、=(8+2*(34%11+1)%13=12, 查找成功，比较 3 次。23：d0=H(23)=10 ，查找成功，比较1 次AVL=(2+1+1+1+3)/5=1.6 1582123340123456789101112 四、应用题2. 设散列函数为 H(k)=k%7 ，散列表的地址空间为0-6；对关键字序列32，13，49，55，22，38，21按线性探测法解决冲突的方法构造散列表，并指出查找每个关键字要进行几次比较？参考答案495522383221130123456 关关键字49552238322113 比较次数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

13、- - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 1 3 2 1 1 6 1 五、编程用折半查找法在有序表ST中查找某一关键值，若找到，则返回该元素在顺序表中的位置；否则，返回0。请用 C语言编制实现该算法的函数。有序表的结点类型定义为：typedefstruct KeyType key; Element; typedefstruct Element *elem; int length; SSTable; 函数首部为：intSearch_Bin(SSTable ST, KeyType key) 参考答案：int

14、Search_Bin(SSTable ST, KeyType key) low=1；high = ST.length ；while(low = high) mid =(low + high)/2；if(key = = ST.elemmid.key) return mid ；else if (key ST.elemmid.key ) high=mid-1 ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - else low = mid + 1 ； return 0； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -