数据结构与算法复习题10（C语言版）

习

判断题：

9解答

1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。)

2.有n个数据放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL要比有序表的ASL小。)

3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE

4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE

5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE

单选题：

6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。

A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次?(1?18)/2? = 9,第二次?(1?8)/2? = 4，第三次

?(1?3)/2? = 2, (第四次?(3?3)/2? = 3，故选D.

7. 顺序查找法适合于存储结构为____________的线性表。

A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B

8.对线性表进行二分查找时，要求线性表必须( )。

A．以顺序方式存储 B. 以链接方式存储 C．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C

9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图

1

所示)，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是( )。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 A．8 B. 3 C．5 D. 9 答：D (计算H(k)，即H(49)=49 mod 11 = 5,冲突，进行二次探测再散列。而二次探测再散列的增量序列为：di=12，-12，22，-22，32，…，土k2，(k≤m/2), 沿着增量序列选择不同的增量按照开放定址公式：

Hi＝( H(key)+di) MOD m i＝1，2，…，k (k≤m-1)

寻找新的地址(构造后继散列地址)。

计算Hi＝( H(49)+di) MOD 14 ＝ (5+di) MOD 14, 可知当( 5+22)

MOD 14 = 9 MOD 14 = 9时不再发生冲突，故选择D).

10.以下说法错误的是( )。

A．散列法存储的基本思想是由关键码值决定数据的存储地址 B. 散列表的结点中只包含数据元素自身的信息，不包含任何指针 C．装填因子是散列法的一个重要参数，它反映了散列表的装填程度

D. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法

答：B (散列表也可以用单链表存储，故选择B.)

11.以下说法正确的是( )。 A．数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字分布情况，并且键值的位数比散列地址的位数多 B．除余法要求事先知道全部键值

C．平方取中法需要事先掌握键值的分布情况 D．随机数法适用于键值不相等的场合 答：A.

12.设有一个用线性探测法解决冲突得到的散列表如下图所示，散列函数为H(k)= k % 11，若要查找元素14，探测的次数是( )。

T： 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 A．8 B. 9 C．3 D. 6 答：D

13.散列表的平均查找长度( )。

A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关

2

C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 答：C

14.在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值( )。 A．一定都是同义词 B. 一定都不是同义词 C．都相同 D. 不一定都是同义词 答：D

(例如，当H(k)=k mod 7且输入的关键字为3、4、10时所构造的散列表如下图所示：

0 1 2 3 4 5 6 3 4 10 当查找关键字成功时，所探测3、4、5位置上的键值：3和10是同义词而4不是同义词。)

15.在采用线性探测法处理冲突的闭散列表上，假定装填因子α的值为0.5，则查找任一元素的平均查找长度为( )。

A．1 B. 1.5 C. 2 D. 2.5

答：B (注：线性探测再散列的哈希表查找成功时的平均查找长度为

Snl ≈

11(1 + ) (9-27) 21?a参见严蔚敏等《（c语言版）数据结构》P.261公式9-27。 )

16.在采用链接法处理冲突的散列表上，假定装填因子α的值为4，则查找任一元素的平均查找长度为( )。

A．3 B. 3.5 C. 4 D. 2.5

答：A (链地址法处理冲突的哈希表查找成功时的平均查找长度为

a Snc ≈ 1+ (9-29)

2参见严蔚敏等《（c语言版）数据结构》P.261公式9-29。)

填空题：

17.二分查找的存储结构仅限于 ，且是 。 答：顺序存储结构 有序的 18.

* 在n个记录的有序顺序表中进行折半查找，最大的比较次数

是 。

答： ?log2n?+1 (相当于走了一个完全二叉树根到树叶的长度，即?log2n?+1；故填?log2n?+1.)

3

19.构造哈希(Hash)函数的方法有 、 、 、

、 和 。

答：直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 20. 法构造的哈希函数肯定不会发生冲突。 (重大2000年研究生试题。) 答：直接定址 (参见严蔚敏等《（c语言版）数据结构》P.253)

21.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 答：哈希表查找法

22.在散列存储中，装填因子α的值越大，则 ；α的值越小，则 。 答：存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小

简答题：

23.比较线性探测、随机探测和链地址法解决冲突的优缺点。

解：线性探测：简单，但可能导致记录的聚集而使探测效率降低；此外记录的个数必须在哈希表允许的范围内。

随机探测：可以克服记录聚集的现象，但需要选取合适的随机函数且记录的个数也有限制。

链地址法：只要空间允许就可插入任意多个记录，并且链表的插入和删除都很方便。

24.在哈希表存储中，发生哈希冲突的可能性与哪些因素有关？为什么？ 答：在哈希表存储中，发生哈希冲突的可能性与装填因子α、所采用的哈希函数、解决冲突的哈希冲突函数三个因素有关。

这是因为：(1)装填因子α是哈希表中已存入的数据元素n与哈希地址空间大小m的比值，即n/m，显然，当α越小时，冲突的可能性就越小，α越大(最大可取1)时，冲突的可能性就越大；(2)若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生；(3)若哈希冲突函数选择得当，可以减少再次发生哈希冲突的可能性。

25. 对含有n个数据元素的集合，要找出最大元素和最小元素，请问最少需要多少次比较运算（执行if语句的次数）。

答：我们可以设立两个变量max和min用于存放最大元素和最小元素的位置，第一次取两个元素进行比较，大的放入max，小的放入min,从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下来都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元素和最小元素。（最坏情况下，要进行2n-3次比较才能结果）

26．请问：对有序的单链表能否进行折半查找？为什么？

答：有序的单链表不能进行折半查找的。因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，

4

还不如顺序查找，而且，用链存储结构将无法判定折半的过程是否结束，因此无法用链表实现折半查找。

27．设有序表为(1、23、34、55、56、57、77、87、99)请分别画出对给定值23，56，98进行折半查找的过程。（并注明每次循环的各参数变量的结果） 答：

23的查找过程如下（其中括号表示当前查找区间，圆括号表示当前比较的关键字）

下标： 1 2 3 4 5 6 7 8 9 第一次比较：[ 1 23 34 55（56）57 77 87 99] low=1 high=9 mid=5

第二次比较：[ 1（23）34 55] 56 57 77 87 99] low=1 high=4 mid=2

56的查找过程如下（其中括号表示当前查找区间，圆括号表示当前比较的关键字）

下标： 1 2 3 4 5 6 7 8 9 第一次比较：[ 1 23 34 55（56）57 77 87 99] low=1 high=9 mid=5

98的查找过程如下（其中括号表示当前查找区间，圆括号表示当前比较的关键字）

下标： 1 2 3 4 5 6 7 8 9 第一次比较：[ 1 23 34 55（56）57 77 87 99] low=1 high=9 mid=5

第二次比较： 1 23 34 55 56 [57 (77) 87 99] low=6 high=9 mid=7

第三次比较： 1 23 34 55 56 57 77[(87) 99] low=8 high=9 mid=8

5

第四次比较： 1 23 34 55 56 57 77 87[(99)] low=9 high=9 mid=9

第五次比较： 1 23 34 55 56 57 77 87 99 low=9 high=8

low>high 查找不成功。

计算题：

28.设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数H(key)=key % 13，采用开放地址法(开放定址法)的二次探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造哈希表。 解：依题意，n=19，二次探测再散列的下一地址计算公式为：

其计算如下： H(19)=19 % 13 =6 H(01)=01 % 13 =1 H(23)=23 % 13 =10

H(14)=14 % 13 =1(冲突) H(14)=(1+1*1) % 19 =2 H(55)=55 % 13 =3 H(20)=20 % 13 =7

H(84)=84 % 13 =6(冲突)

H(84)=(6 + 1*1) % 19 =7(仍冲突) H(84)=(6 - 1*1) % 19 =5 H(27)=27 % 13 =1(冲突)

H(27)=(1+1*1) % 19 =2(冲突) H(27)=(1-1*1) % 19 =0 H(68)=68  =3(冲突) H(68)=(3+1*1)  =4 H(11)=11 % 13 =11

H(10)=10 % 13 =10(冲突)

H(10)=(10+1*1) % 19 =11(仍冲突) H(10)=(10-1*1) % 19 =9 H(77)=77  =12

因此：各关键字的记录对应的地址分配如下： addr(27) = 0 addr(01) = 1 addr(14) = 2

6

addr(55) = 3 addr(68) = 4 addr(84) = 5 addr(19) = 6 addr(20) = 7 addr(10) = 9 addr(23) = 10 addr(11) = 11 addr(77) = 12 其他地址为空。

算法设计题：

29.已知某哈希函数的装载因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母(小写)在字母表中的序号，处理冲突的方法为线性探测开放定址法，试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

参考解法：(开放定址哈希表的存储结构参见《(c语言版)数据结构P.259》.) void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法 {

for(i=1;i<=26;i++)

for(j=i; H.elem[j].key; j=(j+1) % hashsize[H.sizeindex]) //线性探测 if( H(H.elem[j].key)= =i) printf(\; } // Print_Hash

int H(char *s) // 求Hash函数值 {

if(s) return s[0]- 96; // 求关键字第一个字母的字母序号(小写)

// s[0]的值为关键字的第一个字母，000~096为ASCII码表中前部非小写字母 // 部分的字符编码。字母a的ASCII编码是097，字母b的ASCII编码是098，…，。 else return 0; } // H

7

本文来源：https://www.bwwdw.com/article/wzyd.html