第7章+查找技术习题解析（答）

查找技术-----习题解析课后习题讲解 1 1. 填空题

⑴ 顺序查找技术适合于存储结构为（顺序存储和链接存储）的线性表，而折半查找技术适用于存储结构为（顺序存储）的线性表，并且表中的元素必须是（按关键码有序）。 ⑵ 设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ 1）次，至多需比较（7）次。

⑷ 长度为20的有序表采用折半查找，共有（ 4）个元素的查找长度为3。

⑸ 假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（62）。

⑹ 在散列技术中，处理冲突的两种主要方法是（开放定址法）和（拉链法）。 ⑺ 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（散列查找）。 ⑻ 与其他方法相比，散列查找法的特点是（通过关键码计算记录的存储地址，并进行一定的比较）。 2. 选择题

⑴ 静态查找与动态查找的根本区别在于（ ）。

A、 它们的逻辑结构不一样 B、 施加在其上的操作不同 C、 所包含的数据元素的类型不一样 D、 存储实现不一样

⑵ 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（ ）。

A、 s=b B、 s>b C、 s

⑶ 长度为 12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（A），查找失败时的平均查找长度是（B ）。

A、 37/12 B、 62/13 C、 3 9/12 D、 49/13

⑹ 散列技术中的冲突指的是（ ）。

A、 两个元素具有相同的序号 B、 两个元素的键值不同，而其他属性相同 C、 数据元素过多 D、 不同键值的元素对应于相同的存储地址

⑺ 设散列表表长m=14，散列函数H(k)=k mod 11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（ ）。 A、 8 B、 3 C、 5 D、 9

⑻ 在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测的这些位置的键值（ ）。

A、一定都是同义词 B、一定都不是同义词 C、不一定都是同义词 D、都相同 应用题：

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

算法设计：

⑴ 设计顺序查找算法，将哨兵设在下标高端。

【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下：

查找技术-----习题解析课后习题讲解 2 一、选择题

1、静态查找表与动态查找表二者的根本差别在于 C 。 A、它们的逻辑结构不一样 B、 施加在其上的操作不同 C、所包含的数据元素的类型不一样 D、 存储实现不一样 2、下面的查找方式中，可以对无序表进行查找的是 A 。 A、顺序查找 B、二分查找 C、二叉排序树 D、B－树上的查找

3、长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是 B 。 A、 37/12 B、 62/13 C、 39/12 D.、49/13

4、二分查找算法要求被查找的表是 C 。

Ａ、键值有序的链表 Ｂ、键值不一定有序的链表 Ｃ、键值有序的顺序表 Ｄ、键值不一定有序的顺序表 5、堆（Ｈeap）是 B 。

Ａ、完全二叉树 Ｂ、线性表 Ｃ、二叉排序树 Ｄ、平衡二叉树

6、在下面的排序方法中，不需要通过比较关键字就能进行排序的是 A 。 A、堆排序 B、 快速排序 C、插入排序 D、 希尔排序

7、从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较 D 个结点

A、 n B、 n/2 C、 (n-1)/2 D、 (n+1)/2

8、设散列函数为H(k)=k mod 7,一组关键码为23，14，9，6，30，12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为 B 。 A、

0 1 2 3 4 5 6 14 B、

0 1 2 3 4 5 6 14 C、

0 1 2 3 4 5 6 14 D、

0 1 2 3 4 5 6 6 23 30 14 18 12 9 12 9 23 30 18 6 18 23 9 30 12 6 6 23 9 18 30 12 9、散列表的目的是 C 。

A、插入 B、删除 C、快速查找 D、排序

10、在Hash函数 H（k）=k MOD m 中，一般来讲，m应取 C 。 A、奇数 B、偶数 C、素数 D、充分大的数

11、如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次