下面是小编为大家整理的聊一聊查找技术,供大家参考。
第 7 章 查找技术
课后习题讲解
1. 填空题
⑴ 顺序查找技术适合于存储结构为（
）的线性表，而折半查找技术适用于存储结构为（
）
的线性表，并且表中的元素必须是（
）
。
【解答】
顺序存储和链接存储， 顺序存储， 按关键码有序
⑵ 设有一个已按各元素值排好序的线性表， 长度为 125， 用折半查找与给定值相等的元素， 若查找成功， 则至少需要比较（
）
次， 至多需比较（
）次。
【解答】
1， 7 【分析】
在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少， 为 1 次， 最多不超过判定树的深度。
⑶ 对于数列{25， 30， 8， 5， 1， 27， 24， 10， 20，21， 9， 28， 7， 13， 15}， 假定每个结点的查找概率相同， 若用顺序存储结构组织该数列， 则查找一个数的平均比较次数为（
）
。
若按二叉排序树组织该数列， 则查找一个数的平均比较次数为（
）
。
【解答】
8， 59/15 【分析】
根据数列将二叉排序树画出， 将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数， 即为二叉排序树的平均查找长度。
⑷ 长度为 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 D 不能确定 【解答】
D， D 【分析】
此题没有指明是平均性能。
例如， 在有序表中查找最大元素， 则顺序查找比折半查找快， 而平均性能折半查找要优于顺序查找， 查找不成功的情况也类似。
⑶ 长度为 12 的有序表采用顺序存储结构，采用折半查找技术， 在等概率情况下， 查找成功时的平均查找长度是（
）
， 查找失败时的平均查找长度是（
）
。
A 37/12 B 62/13 C 3 9/12 D 49/13 【解答】
A， B
【分析】
画出长度为 12 的折半查找判定树， 判定树中有 12 个内结点和 13 个外结点。
⑷ 用 n 个键值构造一棵二叉排序树， 其最低高度为（
）
。
A n/2 B n C log2n D log2n+1 【解答】
D 【分析】
二叉排序树的最低高度与完全二叉树的高度相同。
⑸ 二叉排序树中， 最小值结点的（
）
。
A 左指针一定为空 B 右指针一定为空 C 左、 右指针均为空 D 左、 右指针均不为空 【解答】
A 【分析】
在二叉排序树中， 值最小的结点一定是中序遍历序列中第一个被访问的结点， 即二叉树的最左下结点。
⑹ 散列技术中的冲突指的是（
）
。
A 两个元素具有相同的序号 B 两个元素的键值不同， 而其他属性相同 C 数据元素过多 D 不同键值的元素对应于相同的存储地址 【解答】
D
⑺ 设散列表表长 m=14，散列函数 H(k)=k mod 11。表中已有 15、 38、 61、 84 四个元素， 如果用线性探侧法处理冲突， 则元素 49 的存储地址是（
）
。
A 8 B 3 C 5 D 9
【解答】
A 【分析】
元素 15、 38、 61、 84 分别存储在 4、 5、6、 7 单元， 而元素 49 的散列地址为 5， 发生冲突，向后探测 3 个单元， 其存储地址为 8。
⑻ 在采用线性探测法处理冲突所构成的闭散列表上进行查找， 可能要探测多个位置， 在查 找成功的情况下， 所探测的这些位置的键值（
）
。
A 一定都是同义词 B 一定都不是同义词 C 不一定都是同义词 D 都相同 【解答】
C 【分析】
采用线性探测法处理冲突会产生堆积， 即非同义词争夺同一个后继地址。
3. 判断题
⑴ 二叉排序树的充要条件是任一结点的值均大于其左孩子的值， 小于其右孩子的值。
【解答】
错。
分析二叉排序树的定义， 是左子树上的所有结点的值都小于根结点的值， 右子树上的所有结点的值都大于根结点的值。
例如图 7-7 所示二叉树满足任一结点的值均大于其左孩子的值， 小于其右孩子的值， 但不是二叉排序树。
⑵ 二叉排序树的查找和折半查找的时间性能相同。
【解答】
错。
二叉排序树的查找性能在最好情况和折半查找相同。
⑶ 若二叉排序树中关键码互不相同， 则其中最小元素和最大元素一定是叶子结点。
【解答】
错。
在二叉排序树中， 最小元素所在结点一定是中序遍历序列中第一个被访问的结点， 即是二叉树的最左下结点， 但可能有右子树。
最大元素所在结点一定 是中序遍历序列中最后一个被访问的结点， 即是二叉树的最右下结点， 但可能有左子树。
如图 7-8 所示， 5 是最小元素， 25 是最大元素，但 5 和 25 都不是叶子 结点。
⑷ 散列技术的查找效率主要取决于散列函数和处理冲突的方法。
【解答】
错。
更重要的取决于装填因子， 散列表的平均查找长度是装填因子的函数。
⑸ 当装填因子小于 1 时， 向散列表中存储元素时
不会引起冲突。
【解答】
错。
装填因子越小， 只能说明发生冲突的可能性越小。
4． 分别画出在线性表（ a， b， c， d， e， f， g）
中进行折半查找关键码 e 和 g 的过程。
【解答】
查找关键码 e 的过程如图 7-9 所示， 查找关键码 g 的过程如图 7-10 所示。
5． 画出长度为 10 的折半查找判定树， 并求等概率时查找成功和不成功的平均查找长度。
【解答】
参见 7.2.1。
6． 将数列（ 24， 15， 38， 27， 121， 76， 130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。
【解答】
二叉排序树如图 7-11 所示， 其平均查找长度=1+2×2+3×2+4×2=19/7
7． 一棵二叉排序树的结构如图 7-12 所示， 结点的值为 1～ 8， 请标出各结点的值。
【解答】
二叉排序树中各结点的值如图 7-13 所示。
8． 已知散列函数 H(k)=k mod 12， 键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)， 采用拉链法处理冲突， 试构造开散列表， 并计算查找成功的平均查找长度。
【解答】
H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10 构造的开散列表如下：
平均查找长度 ASL=(8×1+4×2)/12=16/12 9. 算法设计 ⑴ 设计顺序查找算法， 将哨兵设在下标高端。
【解答】
将哨兵设置在下标高端， 表示从数组的低端开始查找， 在查找不成功的情况下， 算法自动在哨兵处终止。
具体算法如下：
⑵ 编写算法求给定结点在二叉排序树中所在的层数。
【解答】
根据题目 要求采用递归方法， 从根结点开始查找结点 p， 若待查结点是根结点， 则深度为 1，否则到左子树（ 或右子树）
上去找， 查找深度加 1。
具体算法如下：
⑶ 编写算法， 在二叉排序树上找出任意两个不同结点的最近公共祖先。
【解答】
设两个结点分别为 A 和 B， 根据题目 要求分下面情况讨论：
⑴ 若 A 为根结点， 则 A 为公共祖先；
⑵ 若 A->datadata 且 root->datadata，root 为公共祖先；
⑶ 若 A->datadata 且 B->datadata，则到左子树查找；
⑷ 若 A->data>root->data 且 B->data>root->data，则到右子树查找。
具体算法如下：
⑷ 设计算法判定一棵二叉树是否为二叉排序树。
【解答】
对二叉排序树来讲， 其中序遍历序列为一个递增序列。
因此， 对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小， 则说明该二叉树是二叉排序树。
具体算法如下：
序列。
学习自测及答案
1． 已知一个有序表为（ 12， 18， 24， 35， 47， 50，62， 83， 90， 115， 134）
， 当折半查找值为 90 的元素时， 经过（
）
次比较后查找成功。
A 2 B 3 C 4 D 5 【解答】
A
2． 已知 10 个元素（ 54， 28， 16， 73， 62， 95，60， 26， 43）
， 按照依次插入的方法生成一棵二叉排序树， 查找值为 62 的结点所需比较次数为（
）。
A 2 B 3 C 4 D 5 【解答】
B
3． 已知数据元素为（ 34， 76， 45， 18， 26， 54，92， 65）
， 按照依次插入结点的方法生成一棵二叉排序树， 则该树的深度为（
）
。
A 4 B 5 C 6 D 7 【解答】
B
4． 按（
）
遍历二叉排序树得到的序列是一个有序A 前序 B 中序 C 后序 D 层次
【解答】
B
5． 将二叉排序树 T 按前序遍历序列依次插入初始为空的二叉排序树 T "中， 则 T 与 T"是相同的， 这种说法是否正确？
【解答】
正确
6. 一棵高度为 h 的平衡二叉树，最少含有 个结点。
A 2h B 2 h -1 C 2 h +1 D 2 h -2 【解答】
D
7． 在散列函数 H(k)= k mod m 中， 一般来讲， m应取（
）
。
A 奇数 B 偶数 C 素数 D 充分大的数 【解答】
C
8． 已知关键码序列为（ Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec）
， 散列表的地址空间为 0~16， 设散列函数为 H(x)= ， 其中 i 为关键码中第一个字母在字母表中的序号， 采用线性探测法和链地址法处理冲突， 试分别构造散列表， 并求等概率情况下查找成功的平均查找长度。
【解答】
H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2
采用线性探测法处理冲突， 得到的闭散列表如下：
平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12 采用链地址法处理冲突， 得到的开散列表如下：
平均查找长度=(1×7+2×4+3×1)/12=18/12 9. 试推导含有 12 个结点的平衡二叉树的最大深度， 并画出以棵这样的树。
【解答】
令 Fk 表示含有最少结点的深度为 k 的平衡二叉树的结点树目 ， 则：
F1=1， F2=2， …， Fn= Fn-2+Fn-1+1。
含有 12 个结点的平衡二叉树的最大深度为 5， 例如：