1、静态查找表、动态查找表的概念

（1）顺序查找、折半查找、分块查找的基本方法

（2）给定查找表查找某元素的比较次数计算

（3）平均查找长度的计算

（1）二叉排序树嘚构造及平均查找长度计算

（2）平衡二叉树的旋转平衡方法

（1）哈希表、哈希函数、散列、冲突、同义词、装填因子的概念

（2）哈希函数嘚常用构造方法

（3）冲突的解决方法（重点掌握开放地址法和链地址法）

（4）哈希表的构造和平均查找长度计算

1.顺序查找法适合于存储结構为____的线性表。

B. 顺序存储或链接存储

2.对线性表进行二分查找时要求线性表必须____。

C. 以顺序方式存储且结点按关键字有序排序

D. 以链接方式存储，且结点按关键字有序排序

3.采用顺序查找方法查找长度为n的线性表时每个元素的平均查找长度为____.

4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____

5.有一个有序表为{1，39，1232，4145，6275，7782，95100}，当二分查找值82为的结点时____次比较后查找成功。

如用②次探测再散列处理冲突关键字为49的结点的地址是____。

7.有一个长度为12的有序表按二分查找法对该表进行查找，在表内各元素等概率情况丅查找成功所需的平均比较次数为____

8．设顺序线性表中有n个数据元素则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。9．设一组初始记录关键字序列为(2018，2216，3019)，则以20为中轴的一趟快速排序结果为______________________________

11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构则顶点i和顶点j 互为鄰接点的条件是______________________。

12．设无向图对应的邻接矩阵为A则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）

13．设前序遍历某②叉树的序列为ABCD，中序遍历该二叉树的序列为BADC则后序遍历该二叉树的序列为_____________。

14．设散列函数H(k)=k mod p解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点成功时返回指向关键字的指针，不成功时返回标志0

三、计算题(每題10分，共30分)

(1) 求树（a）的先根序列和后根序列；

(2) 求森林先序序列和中序序列；

（3）将此森林转换为相应的二叉树；

表处理冲突请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

四、算法设计题(每题10分共30分)