A.该中间位置 B.该中间位置-1 C.该中间位置+1 D.该中间位置1/2 17.二叉排序树（ ）遍历序列是从小到大有序的。 A. 先序 B.中序 C. 后序 D.层序 二、填空题

1.查找表是由同一类型的数据元素 ( 或记录 ) 组成的 , 是查找所依

赖 。

2. 如果对查找表只进行查询某个\特定的\数据元素是否在查找表中, 以及查找某 \特定的\数据元素的各种属性两种类型的基本操作,而不进行插入和删除数据元素的查找表称为 。

3. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者 查找表中删除已存在的某个数据元素，则称此类查找表为 。 4. 关键字是数据元素(或记录)中某个 ，用它可以标识(识别)一个查表中

5. 在一个查找表中，能够惟一的标识一个数据元素(或记录)的关键字称为 。 6. 次关键字也称为 或 ，是在查找表中可以标识 的关键字。 7. 查找又称 ，它是根据给定的某个值，在查找表中确定是否有元素(或记 录)的关键字的操作。若操作之后确定表中存在这样的记录，则称为查找 的，否则称为 。

8. 平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。

9. 最大查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。最大查找长度随所查找的 、 和 都有关系。最大查找长度通常是在考虑查找给定值在查找表中的情况。

10. 是一种最简单、最基本的查找方法，它的基本思想是：从表的一端开始，依次顺序扫描线性表，将扫描到记录的关键字逐个与给定值进行比较，若某个记录的关键字和给定的值相等，则说明找到所要的记录，查找成功；若扫描结束后，仍未找到关键字等于给定值的记录，则说明表中没有所查找的记录，查找不成功。

11. 折半查找( Binary Search)又称为 ， 是一种效率较高的一种查找算法。

12. 折半查找的思路是：每次将给定值与查找表中所要查找区域 的关键字进行比较，而不是查找表中的第一条或最后一条。

13. 分析折半查找的性能可以用二叉树来进行描述。把当前查找区间的中间位置上的结点作为根结点，左半区间和右半区间中结点分别作为左子树和右子树，由此得到的二叉可称为 。

14.分块查找(Blocking Search)又称为 ，是一种以 的形式来来进行的查找方法。分块查找是 的一种改进，它是一种介于 和折半查找之间的查找方法。

15. 二叉排序树(Binary Sort Tree)，又称为 ，它或者是一棵空树，或者是具有下列性质的一棵二叉树：

(1) 若左子树不空，则左子树上所有结点的值 。 (2) 若右子树不空，则右子树上所有结点的值 。 (3) 左右子树又分别是 。

16.平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树:它的左子树和右

子树都是 且左子树和右子树的深度之差的绝对值 。

17. 我们称在构造平衡二叉排序树的过程中，离插入结点最近，且以平衡因子绝对值大 于1 的结点作为根结点的子树为 。

18. 哈希表查找就是一种通过某种映射建立起 之间的对应关系，希望 或经过很少次比较即可获得所要查找的记录。

19. 哈希(Hash)表查找又称为 查找，它是一种重要的查找技术。哈希表查找因使用哈希函数(又称为 ) 而得名。哈希函数是一种 的函数。

20. 利用哈希函数可以实现记录关键字和关键字所对应记录存储地址的转换或映像，这种映像过程称为 或 ，映像结果产生的哈希函数值h (key)作为存储位置称为 或 ，利用哈希函数映像哈希地址，所得到的存储表称为

21. 有时候在向哈希表中存储关键字的时候，会出现一个待插入关键字的记录已经被占用的情况，这种 的现象称为冲突 ( Collision) 。

22.具有相同哈希函数值的关键字对相应的哈希函数来说称为 ，由同义词产生的冲突称为 。

23. 构造哈希函数的 是取关键字或关键字的某个线性函数作为哈希地址。 24. 构造哈希函数的 是对关键字中数字进行分析，然后用提取其中一部分分布较为均匀的数字位作为哈希地址的方法。

25. 构造哈希函数的 是用关键字key除以某个正整数p，所得余数作为哈希地址的方法。

26. 构造哈希函数的 是取关键字平方的中间几位作为哈希地址的方法。

27. 构造哈希函数的 是先将关键字分割成位数相等的几段(其中最后一段的位数可以不相等)，然后取这几位的叠加和作为哈希地址。 中数位的叠加可以分为移位叠加和间界叠加两种。所谓移位叠加是 ，然后相加；间界叠加是 然后对齐相加。

28. 构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生。一旦冲突发生了， 就必须寻求合适的方法来解决冲突。通常解决冲突可以采用 和 。

29. 开放定址法(Open Addressing)是指将哈希表中的空单元向处理冲突开放。开放定址法解决冲突，形成下一个地址的形式是：Hi=(h(key)+di)%m, i=1,2, ? ,k(k≤m-l)其中，h (key) 为哈希函数，m为哈希表长，di为增量序列。根据上式形成增量序列di的不同，开放定址法又可以分成如下三种形式： 、 、 。

30. 分析哈希表的查找过程可以知道，造成哈希表冲突的首要因素是 ，第二个因素是 ，第三个因素是 。

31. 在有序表A[1..18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。

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

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

34. 一个无序序列可以通过构造一个 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 35. 在有序表a [1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比较过的元素的下标依次为 。

36. 对于长度为 n 的线形表 , 若进行顺序查找 , 则时间复杂性为 ；若用二分法

查找，则复杂性为 ；若用分块法查找(假定总块数和每块长度均接近 )，则时间复杂性为 。

37. 对长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找程 为 。

38. 对有序表 (25,30,32,38,47,54,62,68,90,95) 用二分查找法查找32，则所需的比较次数为 。

1. 集合、数据结构 2. 静态查找表 3. 动态查找表

4. 数据项的值、数据元素（或记录） 5. 主关键字

6. 从关键字、辅助关键字、若干条记录 7. 检索、等于给定值、成功、查找不成功 8. 期望值

9. 最大值、内容、所查找的表、所用的查找算法、最坏情况下 10. 顺序查找（Sequential Search） 11. 二分查找、有序表 12. 中间那条记录 13. 折半查找判定树

14. 索引顺序查找、索引顺序表、顺序查找、顺序查找

15. 二叉查找树、均小于根结点的值、均大于根结点的值、二叉排序树 16. AVL树、平衡二叉树、不超过1 17. 最小不平衡树

18. 关键字和关键字所在记录的存储地址、不经过比较 19. 散列表、散列函数、把关键字映射成记录存储地址

20. 哈希造表、散列、哈希地址、散列地址、哈希表、散列表 21. 不同的关键字具有相同地址 22. 同义词、同义词冲突

23. 直接定地址法（或Immediately allocate） 24. 数字分析法（或Digital Analysis method） 25. 除留余数法（或Division Method） 26. 平方取中法（或Mid-square method） 27. 折叠法（或Folding Method）、折叠法（或Folding Method）、将分割后的每一部分的最低位对齐、从每段的一端向另一端沿分割界来回折叠

28. 开放定址法、链地址法等方法

29. 线性探测再散列、二次探测再散列、随机探测再散列 30. 哈希函数、处理冲突的方法、装填因子 31. 9 4 6 7

32. 9，4，6，7，8

33. 1+2+??+k=k(k+1)/2 34. 二叉排序 35. 10,15,12

36. O(n);O(log2n);O(n) 37. L+1

38. 3

39. 左子树

三、判断题

1. 用向量表示的有序表可以使用折半查找。 ( )

2. 用单链表表示的有序表可以使用折半查找。（×） 3. 顺序查找的平均查找长度ASL与数据的排列有关。（×） 4. 在任意非空的二叉排序树中，删除某个结点之后，再将该结点插入在二叉排序树中，则所得到的二叉排序树与原二叉排序树相同。（×） 5. 哈希表的装载因子越小则发生冲突的可能性越大。（×）

6. 二叉排序树中，关键字最小的结点必然无右孩子，关键字最大的结点必然无左孩子。（×）

7. 在分块查找、折半查找和顺序查找中，分块查找平均查找长度最大、折半查找平均查找长度最小。（×）

8. 顺序查找的方法适合于顺序存储结构而不适合于链接存储结构。（×） 9. 前序遍历一棵二叉排序树的结点 , 就可以得到排好序的结点序列。（×）10. AVL树是一棵二叉树，该树上的任意一个结点的平衡因子的绝对值均不大于1。 （ ）

11. 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素的个数有关。 ( )

12. 对一个堆按层次遍历，不一定能得到一个有序序列。（ ）

1. 正确。

2. 错误：用单链表表示的有序表不可以使用折半查找。

3. 错误：顺序查找的平均查找长度ASL与数据的排列无关。 4. 错误：由于二叉排序树插入结点均在二叉排序树的叶子结点上，因此若删除的结点不是叶子结点则删除再重新插入后是不同于原来二叉树的。

5. 错误：哈希表的负载因子越小则发生冲突的可能性越小。

6. 错误：二叉排序树中，关键字最小的结点必然无左孩子，关键字最大的结点必然无右孩子。

7. 错误：在分块查找、折半查找和顺序查找中，顺序查找平均查找长度最大、折半查找平均查找长度最小。

8. 错误：顺序查找的方法适合于顺序存储结构和链接存储结构。

9. 错误：中序遍历一棵二叉排序树的结点，就可以得到排好序的结点序列。 10. 正确。 11. 正确。 12. 正确。

四、综合题

l. 用 C 语言写出顺序查找算法。 2. 用 C 语言写出折半查找算法。 3. 用 C 语言写出分块查找算法。

4. 写出二叉排序树的插入结点的递归算法，并利用插入算法写出建立一个有n个结点的二叉排序树算法。

5. 简述平衡二叉树调整平衡的具体方法。