查找技术-----习题解析课后习题讲解 1 1. 填空题 ⑴ 顺序查找技术适合于存储结构为（ ）的线性表，而折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是（ ）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵ 设有一个已按各元素值排好序的线性表，长度为 125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为 1 次，最多不超过判定树的深度。 ⑷ 长度为 20 的有序表采用折半查找，共有（ ）个元素的查找长度为 3。 【解答】4 【分析】在折半查找判定树中，第 3 层共有 4 个结点。 ⑸ 假定一个数列{25，43，62，31，48，56}，采用的散列函数为 H(k)=k mod 7，则元素48 的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6 ⑹ 在散列技术中，处理冲突的两种主要方法是（ ）和（ ）。 【解答】开放定址法，拉链法 ⑺ 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（ ）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数 n 的函数。 ⑻ 与其他方法相比，散列查找法的特点是（ ）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较 2. 选择题 ⑴ 静态查找与动态查找的根本区别在于（ ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵ 有一个按元素值排好序的顺序表（长度大于 2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是 s和 b，在查找成功的情况下，s和 b 的关系是（）；在查找不成功的情况下，s和 b 的关系是（ ）。 A s=b B s>b C s
