第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 。 供选择的答案：
AC:①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储 ④既可以以顺序方式,也可以以链表方式存储 ⑥必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好 D, E ①25000 ③4500 ④90000 谷案: 7.数据结构反映了数据元素之间的结构关系。链表是一种 它对于数据元素的插入和删除 B。通常查找线性表数据元素的方法有C和D两种方法,其中C是一种只适合于顺序 存储结构但E的方法;而D是一种对顺序和链式存储结构均适用的方法。 供选择的答案 A:①顺序存储线性表②非顺序存储非线性表⑧顺序存储非线性表④非顺序存储线性表 B:①不需要移动结点,不需改变结点指针②不需要移动结点,只需改变结点指针 ③只需移动结点,不需改变结点指针④既需移动结点,又需改变结点指针 C:①顺序查找②循环查找 ③条件查找④二分法查找 D:①顺序查找②随机查找 ③二分法查找④分块查找 E:①效率较低的线性查找②效率较低的非线性查找③效率较高的非线性查找④效率较高的线性查找 谷案 8.在二叉排序树中每个结点的关键码值A,B一棵二叉排序,即可得到排序序列。同一个结点 集合,可用不同的二叉排序树表示,人们把平均检索长度最短的二叉排序树称作最佳二叉排序,最佳二叉 排序树在结构上的特点是C 供选择的答案 A:①比左子树所有结点的关键码值大,比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小,比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B:①前序遍历②中序(对称)遍历⑧后序遍历 ④层次遍历 C:①除最下二层可以不满外,其余都是充满的 ②除最下一层可以不满外,其余都是充满的 ⑧每个结点的左右子树的高度之差的绝对值不大于1④最下层的叶子必须在最左边 答案:A= 9.散列法存储的基本思想是根据_A_来决定_B_,磁撞(冲突)指的是C_,处理碰撞的两类主 要方法是D。 供选择的答案 A,B:①存储地址②元素的符号③元素个数④关键码值 ⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间 C:①两个元素具有相同序号 ②两个元素的关键码值不同,而非码属性相同 ③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多 D:①线性探查法和双散列函数法 ②建溢出区法和不建溢出区法 ⑧除余法和折叠法 ④拉链法和开地址法 答案:A DE 10.考虑具有如下性质的二叉树:除叶子结点外,每个结点的值都大于其左子树上的一切结点的值。并小 于等于其右子树上的一切结点的值 现把9个数1,2,3,…,8,9填入下图所示的二叉树的9个结点中,并使之具有上述性质。此时
2 A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储 ⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好 D，E： ① 25000 ② 30000 ③ 45000 ④ 90000 答案： A= B= C= D＝ E＝ 7. 数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序 存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案： A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表 B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针 ③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针 C：① 顺序查找 ②循环查找 ③条件查找 ④二分法查找 D：① 顺序查找 ②随机查找 ③二分法查找 ④分块查找 E：① 效率较低的线性查找 ②效率较低的非线性查找 ③效率较高的非线性查找 ④效率较高的线性查找 答案：A＝ B＝ C＝ D＝ E＝ 8. 在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点 集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉 排序树在结构上的特点是 C 。 供选择的答案 A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 C： ① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的 ③ 每个结点的左右子树的高度之差的绝对值不大于 1 ④ 最下层的叶子必须在最左边 答案：A＝ B＝ C＝ 9. 散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主 要方法是 D 。 供选择的答案 A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同 ③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法 答案：A＝ B＝ C＝ D＝ 10. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小 于等于其右子树上的一切结点的值。 现把 9 个数 1，2，3，…，8，9 填入下图所示的二叉树的 9 个结点中，并使之具有上述性质。此时
n1的值是A_,n2的值是B,m的值是C现欲把√0放入此树并使该树保持前述性质,增 加的一个结点可以放在D或E。 供选择的答案 A~C:①1②2⑧3④4⑤5回6 ⑧8 D~E:①n7下面②n8下面 ③n9下面 ④n6下面⑤n1与n2之间@n2与n4之间 ⑦n6与n9之间 ⑧n3与n6之间 谷案:A B: n7 、简答题(每小题4分,共16分) 对分(折半)查找适不适合链表结构的序列,为什么?用二分查找的查找速度必然比线性查找的速度 快,这种说法对吗? 2.假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题: (1)画出描述折半查找过程的判定树; (2)若查找元素54,需依次与哪些元素比较? (3)若查找元素90,需依次与哪些元素比较? (4)假定每个元素的查找概率相等,求查找成功时的平均查找长度。 3.用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?如果要求时 间复杂度更小你采用什么方法?此方法的时间复杂度是多少? 4.设哈希(Hash)表的地址范围为0~17,哈希函数为:H(K)=KMOD16。 K为关键字,用线性探测法再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出Hash表,试回谷下列问题: (1)画出哈希表的示意图; (2)若查找关键字63,需要依次与哪些关键字进行比较? (3)若查找关键字60,需要依次与哪些关键字比较? (4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度
3 n1 的值是 A ，n2 的值是 B ，n9 的值是 C 。现欲把 10 放入此树并使该树保持前述性质，增 加的一个结点可以放在 D 或 E 。 供选择的答案 A～C： ① 1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9 D～E： ① n7 下面 ② n8 下面 ③ n9 下面 ④ n6 下面 ⑤ n1 与 n2 之间 ⑥ n2 与 n4 之间 ⑦ n6 与 n9 之间 ⑧ n3 与 n6 之间 答案：A＝ B＝ C＝ D＝ E＝ 三、简答题（每小题 4 分，共 16 分） 1. 对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度 快，这种说法对吗？ 2. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1） 画出描述折半查找过程的判定树； （2） 若查找元素 54，需依次与哪些元素比较？ （3） 若查找元素 90，需依次与哪些元素比较？ （4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 3. 用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时 间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 4. 设哈希（Hash）表的地址范围为 0～17，哈希函数为：H（K）＝K MOD 16。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出 Hash 表，试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字 63，需要依次与哪些关键字进行比较？ （3） 若查找关键字 60，需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度
四、分析题(每小题6分,共24分) 1.【严题集93②】画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查 找长度 2.在一棵空的二叉查找树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得 到的二叉查找树。 3.【严题集99③】已知如下所示长度为12的表 (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其 在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平 均查找长度。 (3)按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度 4.选取散列函数H(key)=(3~key)%l,用线性探测法处理冲突,对下列关键码序列构造一个散列地 址空间为0~10,表长为11的散列表,{22,41,53,08,46,30,01,31,66} 五、算法设计题(4中选3,第1题7分必选,其余每题8分,共23分) 1.已知11个元素的有序表为(0513192137566475808892),请写出折半查找的算 法程序,查找关键字为key的数据元素(建议上机调试 2.【严题集93④】试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不同。 3.【严题集92④】已知一个含有1000个记录的表,关键字为中国人姓氏的拼音,请给出此表的一个哈 希表设计方案,要求它在等概率情况下查找成功的平均查找长度不超过3 4.【严题集944④】已知某哈希表的装载因子小于1,哈希函数H(key)为关键字(标识符)的第一个字 母在字母表中的序号,处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出 哈希表中所有关键字的算法
4 四、分析题（每小题 6 分，共 24 分） 1. 【严题集 9.3②】画出对长度为 10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查 找长度。 2. 在一棵空的二叉查找树中依次插入关键字序列为 12，7，17，11，16，2，13，9，21，4，请画出所得 到的二叉查找树。 3. 【严题集 9.9③】已知如下所示长度为 12 的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其 在等概率的情况下查找成功的平均查找长度。 (2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平 均查找长度。 (3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 4. 选取散列函数 H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地 址空间为 0～10，表长为 11 的散列表，{22，41，53，08，46，30，01，31，66}。 五、算法设计题（4 中选 3，第 1 题 7 分必选，其余每题 8 分，共 23 分） 1. 已知 11 个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算 法程序，查找关键字为 key 的数据元素 (建议上机调试)。 2. 【严题集 9.31④】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不同。 3. 【严题集 9.22④】已知一个含有 1000 个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈 希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过 3。 4. 【严题集 9.44④】已知某哈希表的装载因子小于 1，哈希函数 H(key)为关键字（标识符）的第一个字 母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出 哈希表中所有关键字的算法