8. 次优查找树(Nearly Optimal Search Tree)：构造一棵二叉树，使这棵二叉树的

带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小。

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

树:

a) 若它的左子树不空，则左子村上所有结点的值均小于它的根结点的值。

b) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

c) 它的左、右子树也分别为二叉排序树。

10. 平衡二叉树(Balanced Binary Tree)：又称AVL树，它或者是一棵空树，或者是

具有下列性质的二叉树，它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

11. 平衡因子BF(Balance Factor)：为该结点的左子树深度减去它的右子树的深度，

则平衡二叉树上所有结点的平衡因子只能是-1，0，1，只要二叉树上一个结点的平衡因子的绝对值大于1，则该二叉树是不平衡的。

12. 哈希表(Hash Table)：根据设定的哈希函数和处理冲突的方法将一组关键字映射到

一个有限的连续的地址集上，并以关键字在越来越集中的像作为记录在表中的存储位置，这种表便称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称哈希地址或散列地址。

13. 冲突(Collision)：对不同的关键字可能得到同一哈希地址，这种现象称为冲突，具

有相同函数值的关键字对该哈希函数来说称做同义词。

14. 常用的构造哈希函数的方法有：

a) 直接定址法：取关键字或关键字的某个线性函数值为哈希地址。

b) 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事

先知道的，则可取关键字的若干位组成哈希地址。

c) 平方取中法：取关键字平方的后的中间几位做为哈希地址。

d) 折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和为哈希地址。 e) 除留余数法：取关键字被某个不大于哈希表表长m的数p除后的余数为哈希地址。 f) 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址。

15. 常用的处理冲突的方法：

a) 开放定址法：其中增量序列有线性探测再散列，二次探测再散列，随机探测再散列。 b) 再哈希法：即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发

生。

c) 链地址法：将所有关键字为同义词的记录存储在同一线性链表中。

d) 建立一个公共溢出区。

16. 二次聚集：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后

继哈希地址的现象。

17. 装填因子：是表中填入的记录数与哈希表的长度之商，哈希表的平均查找长度是装填

因子的函数，不是规模n的函数。

1. 排序(Sorting)：是指将一个数据元素的任意序列重新排列成一个按关键字有序的序

列。

2. 假设Ri=Rj,且在排序前的序列中Ri领先于Rj，若在排序后的序列中Ri仍领先于Rj，则

称所用的排序方法是稳定的，反之称所用的排序方法是不稳定的。

3. 由于待排序的记录的数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为

两大类：

a) 内部排序：指的是待排序记录放在计算机随机存储器中进行的排序过程

b) 外部排序：指的是待排序记录的数量很大，以致内在一次不能容纳全部记录，在

排序过程中尚需对外存进行访问的排序过程。

4. 直接插入排序(Straight Insertion Sort)：它的基本操作是将一个记录插入到

已排好序的有序表中，从而得到一个新的，记录数增1的有序表。

5. 希尔排序(Shell’s Sort)：又称缩小增量排序，基本思想是先将整个记录序列分

割成若干子序列分别进行直接插入排序，待整个序列中记录基本有序时，再对全体记录进行一次直接插入排序。

6. 起泡排序(Bubble Sort)：首先将第一个记录的关键字同第二个记录的关键字进行

比较，或为逆序，则交换，依此类推，直至第n-1个记录和第n个记录的关键字进行比较为止。判别起泡排序结束的条件应该是在一趟排序过程中没有进行交换记录的操作。

7. 快速排序(Quick Sort)：它的基本思想是，通过一趟排序将待排记录分割成独立的

两部分，其中一部分记录的关键字均比另一部分的关键字小，分别对这丙部分继续进行快速排序，直至整个序列有序。

8. 选择排序：它的基本思想是每一趟在n-i+1个记录中选取关键字最小的记录作为有序

序列中第i个记录。

9. 堆排序(Heap Sort)：若在输出堆顶的最小值之后，使得剩余的n-1个元素的序列重

新又构成一个堆，则得到n个元素中的次小值，如此反复，便能得到一个有序序列，称这个过程为堆排序。

10. 归并排序(Merging Sort)是将两个或两个以上的有序表组合成一个新的有序表，其

中2-归并中的核心操作是将一维数组中前后相信的两个有序序列归并为一个有序序列。