1 第8 章 查找 测试题 及答案 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值 k，用二分法检索表中与 k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100 个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解 ： 显 然 ， 平 均 查 找 长 度 ＝ O（ log2n） <5次 （ 25）。但 具 体 是 多 少 次 ， 则 不 应 当 按 照 公 式 )1(lo g12nnnASL来 计 算 （ 即 （ 21×log221） /20＝ 4.6次 并 不 正 确 ！）。因 为 这 是 在 假 设 n＝ 2m-1的 情 况 下推 导 出 来 的 公 式 。应 当 用 穷 举 法 罗 列 ： 全 部 元 素 的 查 找 次 数 为 ＝ （ 1＋ 2×2＋ 4×3＋ 8×4＋ 5×5） ＝ 74； ASL＝ 74/20=3.7 ！！！ 4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素 20，它将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为 m 的散列表，初始状态为空，现将 n（n
