第 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
【分析】静态查不涉及插入和删除操作，而动态查涉及插入和删除操作。
⑵二叉树的深度为k 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查和折半查与给定值相等的元素，比较次数分别是s和b，在查成功的情况下，s和b的关系是（ ）；在查不成功的情况下，s和b的关系是（ ）。
A s=b B s>b C s<b D 不一定
【解答】D，B
【分析】此题没有指明是平均性能。例如，在有序表中查最大元素，则顺序查比折半查快，而平均性能折半查要优于顺序查，查不成功的情况也类似。
⑶ 长度为 12的有序表采用顺序存储结构，采用折半查技术，在等概率情况下，查成功时的平均查长度是（ ），查失败时的平均查长度是（ ）。
A 37/12 B 62/13 C 3 9/12 D 49/13
【解答】A，D
【分析】画出长度为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)，采用拉链法处理冲突，试构造开散列表，并计算查成功的平均查长度。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。