习题9解答
判断题：
1．用向量和单链表表示的有序表均可使用折半查方法来提高查速度。 答：FALSE (错。链表表示的有序表不能用折半查法。)
2.有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 (第一次⎣⎦2/)181(+ = 9，第二次⎣⎦2/)81(+ = 4，第三次⎣⎦2/)31(+ = 2, (第四次⎣⎦2/)33(+ = 3，故选D.
7. 顺序查法适合于存储结构为____________的线性表。
A.散列存储
B.顺序存储或链式存储
钛复合板C.压缩存储
D.索引存储
答：B
8.对线性表进行二分查时，要求线性表必须( )。
A ．以顺序方式存储 B. 以链接方式存储
C ．以顺序方式存储，且结点按关键字有序排序
D. 以链接方式存储，且结点按关键字有序排序
答：C
9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图
所示)，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是( )。
答：D (计算H(k)，即H(49)=49 mod 11 = 5，冲突，进行二次探测再散列。
而二次探测再散列的增量序列为：d
i
=12，-12，22，-22，32，…，土k2，(k
≤m/2), 沿着增量序列选择不同的增量按照开放定址公式：
H
i ＝( H(key)+d
声乐艺术心理学
i
) MOD m i＝1，2，…，k (k≤m-1)
寻(构造后继散列地址)。
计算H
i ＝( H(49)+d
i
) MOD 14 ＝(5+d
i
) 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
A
答：D
13.散列表的平均查长度( )。
A．与处理冲突方法有关而与表的长度无关
一颗颗星星都是爱
B．与处理冲突方法无关而与表的长度有关
C ．与处理冲突方法有关且与表的长度有关
D ．与处理冲突方法无关且与表的长度无关
答：C
14.在采用线性探测法处理冲突所构成的闭散列表上进行查，可能要探测多个位置，在查成功的情况下，所探测的这些位置上的键值( )。
A ．一定都是同义词 B. 一定都不是同义词
C ．都相同 D. 不一定都是同义词
答：D
(例如，当H(k)=k mod 7且输入的关键字为3、4、10时所构造的散列表如下图所示：
当查关键字成功时，所探测3、4、5位置上的键值：3和10是同义词而4不是同义词。)
15.在采用线性探测法处理冲突的闭散列表上，假定装填因子α的值为0.5，则查任一元素的平均查长度为( )。
A ．1 B. 1.5 C. 2 D. 2.5
答：B (注：线性探测再散列的哈希表查成功时的平均查长度为
S nl ≈ 21(1 + a
-11) (9-27) 参见严蔚敏等《（c 语言版）数据结构》P.261公式9-27。 )
16.在采用链接法处理冲突的散列表上，假定装填因子α的值为4，则查任一元素的平均查长度为( )。
A ．3 B. 3.5 C. 4 D. 2.5
答：A (链地址法处理冲突的哈希表查成功时的平均查长度为
S nc ≈ 1+2
a (9-29) 参见严蔚敏等《（c 语言版）数据结构》P.261公式9-29。)
填空题：
17.二分查的存储结构仅限于 ，且是 。 答：顺序存储结构 有序的
18.* 在n 个记录的有序顺序表中进行折半查，最大的比较次数是 。
答： ⎣⎦n 2log +1 (相当于走了一个完全二叉树根到树叶的长度，即⎣⎦n 2log +1；故填⎣⎦n 2log +1.)
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．请问：对有序的单链表能否进行折半查？为什么？
答：有序的单链表不能进行折半查的。因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，
还不如顺序查，而且，用链存储结构将无法判定折半的过程是否结束，因此无法用链表实现折半查。
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]
solflow=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
HODGKINHUXLEY模型
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
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议