查找技术-----课后习题解析

课后习题讲解
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