第8章查找自测卷 姓名 班级 四 总分 题分 10 27 16 24 100 填空题(每空1分,共10分) 1.在数据的存放无规律而言的线性表中进行检索的最佳方法是 2.线性有序表(a,a,a,…,as6)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相 等的元素,在查找不成功的情况下,最多需要检索次。设有100个结点,用二分法查找时,最大比 较次数是 3假设在有序线性表a20上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结 点数为 ;比较四次查找成功的结点数为 ;平均查找长度为 4.折半查找有序表(4,6,12,20,28,38,50,70,88,100,若查找表中元素20,它将依次与表中 元素 比较大小。 5.在各种查找方法中,平均查找长度与结点个数n无关的查找方法是 6.散列法存储的基本思想是由 决定数据的存储地址。 7.有一个表长为m的散列表,初始状态为空,现将n(n<m)个不同的关键码插入到散列表中,解决冲突 的方法是用线性探测法。如果这n个关键码的散列地址都相同,则探测的总次数是 、单项选择题(每小题1分,共27分) )1.在表长为n的链表中进行线性查找,它的平均查找长度为 A. ASL=n: B.ASL=(n+1)/2; C.ASL=Ⅶn+1;D.ASL≈1og2(n+1)-1 ()2.折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它 将依次与表中 比较大小,查找结果是失败。 20,70,30,50 B.30,88,70,50 C.20,50D.30,88,50 ()3.对22个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字。 ()4.链表适用于 查找 顺序 B.二分法C.顺序也能二分法D.随机 ()5.折半搜索与二叉搜索树的时间性能 A.相同 B.完全不同 C.有时不相同 D.数量级都是O(log2n) 6.要进行线性查找,则线性表A_;要进行二分查找,则线性表 要进行散列查找,则线性表 某顺序存储的表格,其中有9000元素,已按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同的,并且各个元素的关键项的值皆不相同。当用顺序查找法查找时,平均比较次数约为 D,最大比较次数为E 供选择的答案:1 第 8 章 查找 自测卷 姓名 班级 题号 一 二 三 四 五 总分 题分 10 27 16 24 23 100 得分 一、填空题（每空 1 分，共 10 分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值 k，用二分法检索表中与 k 相 等的元素，在查找不成功的情况下，最多需要检索 次。设有 100 个结点，用二分法查找时，最大比 较次数是 。 3. 假设在有序线性表 a[20]上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结 点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。 4． 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素 20，它将依次与表中 元素 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数 n 无关的查找方法是 。 6. 散列法存储的基本思想是由 决定数据的存储地址。 7. 有一个表长为 m 的散列表，初始状态为空，现将 n（n<m）个不同的关键码插入到散列表中，解决冲突 的方法是用线性探测法。如果这 n 个关键码的散列地址都相同，则探测的总次数是 。 二、单项选择题（每小题 1 分，共 27 分） （ ）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. 数量级都是 O（log2n） 6． 要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。 某顺序存储的表格，其中有 90000 个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案：