查找-题库

一、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。

2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；

比较四次查找成功的结点数为；平均查找长度为。

4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。

6. 散列法存储的基本思想是由决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n

8.一个无序序列可以通过构造一棵( )树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程.

9.在一棵有n个结点的非平衡二叉树中进行查找,平均时间复杂度的上限(即最坏情况平均时间复杂度)为( ).

已知有序表为(12,18,24,35,47,50,62,83,90,115,134),当用二分法查找90时,需进行( )次查找可确定成功;查找47时需进行( )次查找可确定成功;查找100时,需进行( )次查找才能确定不成功.

10.假设有n个关键字,它们具有相同的Hash函数值,用线性探测方法解决冲突,把这n个关键字散列到大小为n的地址空间中,共计需要做( )次插入和探测操作.

11.( )法构造的哈希函数肯定不会发生冲突.

12.在分块检索中,对256个元素的线性表分成( )块最好,每块的最佳长度是( );若每块的长度为8,其平均检索长度为( ).

13.在顺序表上施行的三个查找算法,就平均查找长度来看,( )最小,( )最大.

14.在一棵二叉树排序树上实施( )遍历后,其关键字序列是一个有序表.

15.对长度为n的查找表进行查找时,假定查找第i个元素的概率为P i,查找长度(即在查找过程中依次同有关元素比较的总次数)为C i,则在查找成功情况下的平均查找长度的计算公式为( ).

16.一棵深度为h的B-树,任一个叶子结点所处的层数为( ),当向B-树插入一个新关键字时,为检索插入位置需读取( )个结点.

17.二分查找的存储结构仅限于( ),且是( ).

18.对闭散列表来说,( )的方法就是处理冲突的方法.

19.平衡二叉排序树上任一结点的平衡因子只可能是( ),( )或( ).

20.顺序查找不要求关键字( ),其ASL(平均查找长度)为( );折半查找要求关键字( ),其ASL为( ).

21.用二叉排序树查找,在最坏情况下,ASL为( );当二叉排序树是一棵平衡二叉树时,ASL为( ).

22.在B-树上进行查找的过程是一个( )和( )交叉进行的过程.

23.( )查找法的平均查找长度与元素个数n无关.

24．对有17个元素的有序表A[1。。17]作二分查找，在查找其等于A[8]的元素时，被比较的元素下标依次是__________________。

25.假定有K个关键字互为同义词，若用线性探测再散列法把这个K个关键字存入散列表中，至少要进行______次探测。25．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____次。

27．构造哈希(Hash)函数的方法有_______、________、_________等。

28．一棵m阶B-树插入操作时，当结点的关键字数为_______时，则要分裂该结点；删除时，结点中关键字数为________时，可能需要同左或右兄弟合并。

29．高度为5（除叶子层之外）的三阶B-树至少有________个结点。

30．高度为8的平衡二叉树的结点数至少有_______个。

31 具有n 个关键字的B-树的查找路径长度不会大于_______。

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

33.用二分法查找一个线性表时，该线性表必须具有的特点是______；而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间___________

34.分块检索中，若索引表各块内均用顺序查找，则有900个元素的线性表分成_____块最好；若分成25块，其平均查找长度为________。

35.对于二叉排序树的查找，若根结点元素的健值大于被查元素，则应该在二叉树的_______上继续查找。

36.若一个待散列存储的线性表长度为n ，用于散列的散列表长度为m ，则m 应_____n ，装填因子a 为______。

37.在二叉排序树上插入新结点时，不必移动其他结点，仅需使树叶结点的指针由______指向新结点即可。

38.设线性表（a1,a2,…,a 500）元素的值由小到大排列，对一个给定的K 值用二分法查找线性表，在查找不成功的情况下至多需比较________次。

39.二叉排序树的查找效率与树的形态有关。当二叉排序树退化为单枝树时，查找算法退化为______查找，其平均查找长度上升为_______。

40.设有两个散列函数H1(K)=K%13和H2(K)=K%11+1散列表为T[0…12]，用双重散列解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址增量，假定在某一时刻表T 的状态如图所示：

0 1 2 3 4 5 6 7 8 9 10 11 12 80 85 34

下一个被插入的关键字是42，则其插入的位置是______。

41.二叉排序树的查找长度不仅与________有关，也与二叉排序树的_______有关。

42.按13、24、37、90、53的次序形成二叉平衡树，则该二叉平衡树的高度是_______，其根为_______，左子树中的数据是________，右子树中的数据是________。

43.在平衡二叉树上删除一个结点后可以通过旋转使其平衡，最坏情况下需_______次旋转。

44． 用二分法查找一个线性表，该线性表必须具有的特点是____________;而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间_______。

45.在分块检索中，对256个元素的线性表分成 块最好，每块的最佳长度是 ，若每块的长度为8，其平均检索长度为

46．最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度∑最小树，其中对最优二叉树，n 表示______，对

最优查找树，n 表示______，构造这两种树均为_________。

=n i i i h

w 11）结点数2）叶结点数3）非叶结点数4）度为2的结点数5）需要一张n 个关键字的有序表6）需要对n 个关键字进行动态插入7）需要n 个关键字的查找概率表8）不需要任何前提

47．散列函数有一个共同的性质，即函数值应按 取其值域的每一个值。

二、单项选择题

1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;

Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

2． 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。

A ．20，70，30，50

B ．30，88，70，50

C ．20，50

D ．30，88，50

3． 对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。

A ．3

B ．4

C ．5

D ． 6

4. 链表适用于 查找

A ．顺序

B ．二分法

C ．顺序，也能二分法

D ．随机

5. 折半搜索与二叉搜索树的时间性能

A. 相同

B. 完全不同

C. 有时不相同

D. 数量级都是O（log2n）

6．要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。

某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。

供选择的答案：

A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储

④既可以以顺序方式，也可以以链表方式存储

⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好

⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好

D，E：① 25000 ② 30000 ③ 45000 ④ 90000

答案： A= B= C= D＝ E＝

7.数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。

供选择的答案：

A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表

B：①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针

③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针

C：①顺序查找②循环查找③条件查找④二分法查找

D：①顺序查找②随机查找③二分法查找④分块查找

E：①效率较低的线性查找②效率较低的非线性查找③效率较高的非线性查找④效率较高的线性查找

答案：A＝ B＝ C＝ D＝ E＝

8. 在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C 。供选择的答案

A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小

②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大

③比左右子树的所有结点的关键码值都大

④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系

B: ①前序遍历②中序（对称）遍历③后序遍历④层次遍历

C：①除最下二层可以不满外，其余都是充满的②除最下一层可以不满外，其余都是充满的

③每个结点的左右子树的高度之差的绝对值不大于1 ④最下层的叶子必须在最左边

答案：A＝ B＝ C＝

9. 散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。供选择的答案

A，B：①存储地址②元素的符号③元素个数④关键码值

⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间

C: ①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同

③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多

D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法

③除余法和折叠法④拉链法和开地址法

答案：A＝ B＝ C＝ D＝

10. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。

现把9个数1，2，3，…，8，9填入下图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把

10放入此树并使该树保持前述性质，增加的一个结点可以放在 D 或 E 。

供选择的答案

A ～C ： ① 1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6

⑦ 7 ⑧ 8 ⑨ 9

D ～

E ： ① n7下面 ② n8下面 ③ n9下面

④ n6下面 ⑤ n1与n2之间 ⑥ n2与n4之间

⑦ n6与n9之间 ⑧ n3与n6之间

答案：A ＝ B ＝ C ＝

D ＝

E ＝

11．散列表的平均查找长度_________。

a. 与处理冲突方法有关而与表的长度无关

b. 与处理冲突方法无关而与表的长度有关

c. 与处理冲突方法有关且与表的长度有关

d. 与处理冲突方法无关且与表的长度无关

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

a. 一定都是同义词

b. 一定都不是同义词

c. 都相同

d. 不一定都是同义词

13．M 路B +树是一棵_______，其结点中关键字最多为_____个，最少为________个。

a. m 路平衡查找树

b. m 路平衡索引树

c. m 路Ptrie 树

d. m 路健树

e. m-1

f. m

g. m+1

h.

12/?m i.

2/m j.

12/+m 14．在构造哈希表的过程中，不可避免地会出现冲突，通常解决它的办法有_________。

a. 平方取中法

b. 开放地址法

c. 随机探查法

d. 再哈希法

e. 拉链分散法（链地址法）

15．散列函数是指定关键字与存储地址间的映射关系，常用的构造方法有_________.

a. 自身函数（直接定址）法

b. 折叠函数法

c. 平方取中法

d. 链接表法

e. 除留余数法

16．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是_______.

a. 分块查找

b. 顺序查找

c. 折半查找

d. 基于属性查找

17．有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入____________。

a. 45，24，53，12，37，96，30

b. 37，24，12，30，53，45，96

c. 12，24，30，37，45，53，96

d. 30，24，12，37，45，96，53

18．利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行_______元素之间的比较。

a. 4次

b. 5次

c. 7次

d. 10次

19．在非空m 阶B-树上，除根结点以外的所有其他非终端结点__________。

a. 至少有棵子树

2/m b. 至多有棵子树

2/m c. 至少有棵子树

2__m d.

至多有棵子树 2__m 20．在顺序表(n 足够大)中进行顺序查找，其查找不成功的平均长度是_______。

a. (n+1)/2

b. (n/2)+1

c. n

d. n+1

21．采用二分检索方法检索长度为n 的有序表，检索每个元素时的平均比较次数与对应的判定树高度（设高度≥2）相比较为_________。

a. 小于

b. 大于

c. 等于

d. 大于等于

22．对线性表进行二分检索时，要求线性表必须_________。

a. 以顺序存储方式存储

b. 以链式存储方式存储

c. 以顺序存储方式存储且数据有序

d. 以链式存储方式存储且数据有序

23．在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为_______。

a. n

b. log2n

c. (h+1)/2

d. h

24．在一棵平衡二叉树中，每个结点的平衡因子取值范围是__________。

a. -1~1 b -2~2 c 1~2 d 0~1

25．在散列查找中，平均查找长度主要与______有关。

a. 散列表长度

b. 散列元素个数

c. 装填因子

d. 处理冲突方法

26．若根据查找表建立长度为m的闭散列表并采用二次探测处理冲突，假定对一个元素第一次计算的散列地址为d，则第4次计算的散列地址为______。

a.（d+1）%m

b. (d-1)%m

c. (d+4)%m

d. (d-4)%m

27．以下说法正确的是______。

a. 数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字分布情况，并且键值的位数比散列地址的位数

多

b. 除余法要求事先知道全部键值

c. 平方取中法需要事先掌握键值的分布情况

d. 随机数法适用于键值不相等的场合

28．分块查找的时间效率________。

a. 低于二分查找

b. 高于顺序查找而低于二分查找

c. 高于顺序查找

d. 低于顺序查找而高于二分查找

29．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较_____个结点。

a. n

b. n/2

c. (n-1)/2

d. (n+1)/2

30．下述命题______是不成立的。

a m阶B-树中的每一个结点的子树个数都小于或等于m

b.m阶B-树中的每一个结点的子树个数都大于或等于 2/m

c.m阶B-树中的任何一个结点的子树高度都相等

d.m阶B-树具有K个子树的非叶子结点含有K-1关键字

31．假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（）次探测。

A K-1

B K

C K+1

D K(K+1)/2

32. 设有一个按各元素的值排好序的线性表且长度大于2，对给定的值K，分别用顺序查找法和二分查找法查找一个与K相等的元素，比较次数分别是s和b；在查找不成功的情况下，正确的s和b的数量关系是：

A 总有s＝b

B 总有s>b

C 总有s

D 与K值大小有关

33、关于杂凑查找说法不正确的有（）个

（1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的；

（3）采用链地址法解决冲突易引起聚集现象

（4）再哈希法不易产生聚集

34、对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为

A 1、2、3

B 9、5、2、3

C 9、5、3

D 9、4、2、3

35、若在线性表中采用折半查找法查找元素，该线性表应该是

A 按元素值有序

B 采用顺序存储结构

C 元素按值有序，且采用顺序存储结构

D 元素按值有序，且采用链式存储结构

36、在关键字随机分布情况下，用二叉排序树的方法进行查找，其查找长度与量级相当。

A 顺序查找

B 折半查找

C 前两者均不正确

37、一棵深度为K的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有个结点

A 2k-1-1

B 2k-1

C 2k-1+1

D 2k-1

E 2k

F 2k+1

38、假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行次探测

A k-1

B k

C k+1

D k(k+1)/2

39、设散列地址空间0~m-1,k为关键字，用P去除k，将余数作为k的散列地址，即h(k)=k%P,为了减少发生冲突的可能性，一般取P为

A 小于m的最大奇数

B 小于m的最大素数

C 小于m的最大偶数

D 小于m的最大合数

40、设散列表的长m＝14，散列函数为h(k)=k%11，表中已有4个记录，如果用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是

A 8

B 3

C 5

D 9

0 1 2 3 4 5 6 7 8 9 10 11 12 13

15 38 61 84

41、下面关于二叉排序树论述中，错误的是

A 当所有结点的权值都相等时，用这些节点构造的二叉排序树除根节点外只有右子树

B 中序遍历二叉排序树的结点就可以得到排好序的结点序列

C 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间

D 对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列是一样的

42、以下说法错误的是

A 散列法存储的基本思想是由关键码值决定数据的存储地址

B 散列表的结点中只包含数据元素自身的信息，不包含任何指针

C 装填因子是散列法的一个重要参数，它反映了散列表的装填程度

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

43、设有一个用线性探测法解决冲突得到的散列表如图所示

0 1 2 3 4 5 6 7 8 9 10

13 25 80 16 17 6 14

散列函数为h(k)=k%11,若要查找元素14，探测的次数是

A 8

B 9

C 3

D 6

44、设散列函数为h(k)=k%7，一组关键码为23、14、9、6、30、12、18，散列表T的地址空间为0～6，用线性探测法解决冲突，依次将这组关键字插入T中，则得到的散列表为

A B

0 1 2 3 4 5 6 0 1 2 3 4 5 6

14 6 23 9 18 30 12 14 6 23 9 18 30 12

C D

0 1 2 3 4 5 6 0 1 2 3 4 5 6

14 12 9 23 30 18 6 6 23 30 14 18 12 9

45、散列表的平均查找长度

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

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

C 与处理冲突方法有关而与表的长度有关

D 与处理冲突方法无关而与表的长度无关

46.若在线性表中采用折半查找法查找元素，该线性表应该（）

A．元素按值有序 B.采用顺序存储结构

C.元素按值有序，且采用顺序存储结构

D．素按值有序，且采用链式存储结构

47.在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与量级相当。

A．顺序查找 B.折半查找 C.前两者均不正确

三、简答题

1. 对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

2. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树；

（2）若查找元素54，需依次与哪些元素比较？

（3）若查找元素90，需依次与哪些元素比较？

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

3. 用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?

4. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（10，24，32，17，31，30，46，47，40，63，49）

造出Hash表，试回答下列问题：

（1）画出哈希表的示意图；

（2）若查找关键字63，需要依次与哪些关键字进行比较？

（3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

5.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

6. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。

7. 已知如下所示长度为12的表：

（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下

查找成功的平均查找长度。

(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

(3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

8.选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。

9．设有如下关键码{2，4，5，9，11，17}，将其放在长度为8下标从0到7的数组当中，若采用除留余数法（其中除数为表长）构造哈希函数，并结合的二次探测再散列法处理冲突，试画出其存储图。

10. 有一组数据：27、56、19、40、9、31、20，构建一棵二叉排序树，在此二叉查找树中，（1）使用二叉树查找法查找节点31，按顺序写出查找过程中访问的结点；（2）使用前序遍历查找算法查找节点45，按顺序写出查找过程中访问的结点。11．有一棵二叉查找树如下图，在二叉树中分别删除节点11、9、5、19，使得删除后的二叉树仍保持二叉查找树的特性，分别画出删除相应节点后的二叉树。

12.使用散列函数hashf(x)=x MOD 11,把一个整数值转换成散列表下标，现要把数据1、13、12、34、38、33、27、22插入到散列表中。

（1）使用线性探查再散列法来构造散列表。

（2）使用链地址法来构造散列表。

（3）针对这种情况，确定其装填因子，查找成功所需的平均查找次数以及查找不成功所需的平均探查次数。

13．已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49），要求散列到地址区间（100，101，102，103，104，105，106，107，108，109）内，若产生冲突则用开型寻址法的线性探测法解决，要求写出选用的散列函数、形成的散列表、计算从出查找成功时平均查找长度与查找不成功的平均查找长度（设等概率情况）。

14、有关键字集合K＝{15,22,50,13,20,36,28,48,35,31,41,18} 采用散列存取，散列表为HT[0..14]。设散列函数H（K）＝K MOD 13,解决冲突采用开放定址法中的二次探测再散列的方法。试将K值填入HT表中，并把查找每个关键字所需的比较次数m填入表7.2中，并计算出查找成功时的平均查找长度。

表 HT表

I 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

KM

15、若杂凑表的地址范围为[0,9],杂凑函数为H（key）＝（key2＋2）MOD 9，并采用链地址法处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入杂凑表以后该杂凑表的状态。

16、设有12个数据{25、40、33、47、12、66、72、87、94、22、5、58}，他们存储在散列表中，利用双散列解决冲突，要求插入新数据的平均查找次数不超过3次。

（1）该散列表的大小m应设计多大？

（2）试为该散列表设计相应的散列函数并计算寻找下一个空位时向前跨步步长的散列函数。

（3）顺次将各个数据散列到表中。

（4）计算查找成功的平均查找次数。

17、设a、b、c、d和e这5个字符的编码分别为1、2、3、4、5，并设标识符依以下次序出现ac、bd、aa、be、ab、ad、cd、bc、ae和ce。要求用哈希方式将他们存放在具有10个位置的表中。

（1）对上述关键字构造一个哈希函数，使得发生冲突尽可能的少。

（2）用线性探测再散列法解决从冲突。

写出上述歌关键字在表中的位置。

18、编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树，假设每次查找时的给定值为随机数，且查

找成功和不成功的概率也相等，试求进行每一次查找时，与给定值进行比较的关键字个数的期望值。

19．设有5个数do 、for 、if 、repeat 和while ，他们排在一个有序表中，其查找概率分别为p1＝0.2、p2＝0.15、p3＝0.14、p4＝0.03、p5＝0.01，而查找他们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。

1） 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。

2） 分别计算顺序查找时的成功和不成功的平均查找长度以及折半查找时的查找成功和不成功的平均查找长度。

3） 判定是顺序查找好，还是折半查找好。

19． 试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，对长度为n 的表来说，三种查找法在查找成功时的查找长度各是多少？

设有一组数据black 、blue 、green 、purple 、red 、white 、yellow ，他们的查找概率分别是0.1、0.08、0.12、0.05、0.20、0.25、0.2，试以他们的查找概率为权值，构造一棵次优二叉树，并计算其查找成功的平均查找长度。

20．在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助与一棵平衡二叉树来模拟，树中结点的值为记录在文件中的位置序号。

1） 若文件中有19个记录，请画出这颗判定树

2） 当文件中有n 个记录时，求出该判定树的深度。

21．解答下面的问题：

1） 画出在递增有序表A[1..21]中进行折半查找的判定树

2） 当实现插入排序过程中，可以用折半查找来确定第I 个元素在前I －1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂性？为什么？

3） 折半查找的平均查找长度是多少？

22．对长度为12的有序表(a1,a2,…,a12)(其中aia12,以及ai

23. 今有一颗BST 树，如下图所示。求ASL 成功＝？和ASL 不成功＝？

．已知下图中二叉排序树的各结点的值依次为32～40，请标出结点的值。

.已知序列17，31，13，11，20，35，25，8，4，11，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后9

R o o t

24

25的二叉树。

1） 插入数据

2） 删除结点17

3） 再删除结点13

如下图所示，p 指向待删除结点，试给出两种删除该结点并仍能满足二叉排序树性质的方法。 K1>K2>K3，请画出按不同的输入顺序建立相应的二叉排序树。

．设有关键码A 、B 、C 和D ，按照不同的输入顺序，共可能组成多少不同的二叉排序树，请画出其中高度较小的6种。

中的元素组成 point p;keyt k)

p=p->lchild;

d;

“%d ”,p->data);

e printf(“no find ”);

}

void s read(k);

nd(t,k)

序树用中序遍历时输出的信息是由小到大排序的。

{3，5，7，9，11，13，15，17}

入完成后的二叉排序树，并求在等概率情况下查找成功

26．已知二叉排序树

27．设K1，K2，K3，是三个不同的关键字且2829．在一颗表示有序集S 的二叉搜索树中，任意一条从根到叶结点的路径将S 分为3部分；在该路径左边结点的集合S1，在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。3S 2S 1S S ∪∪＝，若对于任意的1S a ∈，2S b ∈，3S c ∈，是否总有a<=b<=c ？为什么？

30．下面是对任意二叉排序树的查找算法，请分析时间复杂度：

void find(var er ype {

while(p<>NULL) and (p->data<>k)

{if(p->data

else p=p->rchil }

if(p==NULL) printf(els orttree(pointer t;int n)

{

fi }

31．证明二叉排32．给定序列1） 按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插的平均查找长度；

2） 按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与1)比较，可得出什么结论？ 33．比较线性探测、随机探测和链地址法解决冲突的优缺点。

四、算法设计题

1. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算法程序，查找关

据元素 (建议上机调试)。

2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 查找成功的平均查找长度不超过3。

希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方

法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

五、 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度.( )

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

二叉树排序树相同.( )

不小于该结点

7. 点必无左孩子,关键字最大的结点必无右孩子.( )

总是实施一系列和

10. 的信息,不包含任何指针.( )

的序列顺序是一样的.( )

的父结点的相应指针域置空即可.( )

叉排序树才是

15. 要取决于哈希表造表时选取的哈希函数和处理冲突的方法.( )

)

树是一样的.( )

最佳二叉排序树.( )

数的排列有序或无序其平均查找长度不同。（） 键字为key 的数

3．已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下

4. 已知某哈希表的装载因子小于1，哈

判断题

1.2. 有n 个数存3. 在任意一棵非空二叉树中,删除某结点后又将其插入,则所得二叉树与删除前原4. 若散列表的负载因子a<1,则可避免碰撞的产生.( )

5. 二叉树中除叶子结点外,对于任一结点X,其左子树根结点的值小于该结点(X)的值, 其右子树根结点的值(X)的值,则此二叉树一定是二叉排序树.( )

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

二叉排序树的任意一棵子树中,关键字最小的结8. 无论是顺序表还是树表,其结点在表中的位置与关键字之间存在着唯一的对应关系;因此进行查找时,关键字的比较操作来体现.( )

9. 就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大.( )

散列表的结点中包含数据元素自身11. 对二棵具有相同关键字集合而形状不同的二叉排序树,按中序遍历它们得到12. 在二叉排序树上删除一个结点时,不必移动其他结点,只要将该结点13. 在所有结点的权都相等的情况下,只有最下面两层结点的度数可以小于2,其他结点的度数必须等于2的二最佳二叉树.( )

14. 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.( )

哈希表的查找效率主16. 在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻.( )

17. 对二叉排序树的查找都是从根结点开始的,则查找失败一定落在叶子上.( )

18. 顺序查找法适用于存储结构为顺序或链接存储的线性表.( )

19. 负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度.( )20. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列.( 21. AVL 树是一棵二叉树,该树上任一结点的平衡因子的绝对值不大于1.( )

22. 二叉排序树的查找和折半查找时间的性能相同.( )

23. 散列法存储的基本思想是由关键码的值决定数据的存储地址.( )

24. 虽然关键字序列的顺序不一样,但依次生成的二叉排序25. 在所有结点的权都相等的情况下,具有平衡特性的二叉排序树一定是26. m 阶B-树具有K 个子树的非叶子结点含有K-1个关键字.( )

27. 负载因子是散列表的一个重要参数，他反映散列表的装满程度。（）

28. 有n 个数存放在一维数组A[1..n]中，进行顺序查找时，这n 个