简答题
- 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次；当使用监视哨时，若查找失败，则比较关键字的次数为____。
n n+1 - 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
4 - 一个无序序列可以通过构造一棵________树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
二叉排序 - 哈希表是通过将查找码按选定的______和 ______，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_____和 ______。一个好的哈希函数其转换地址应尽可能_______，而且函数运算应尽可能_______。
(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单 - 在哈希函数H（key）=key%p中，p值最好取__________。
小于等于表长的最大素数 - 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
插入 删除 - 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数:H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1^2,2^2,3^2,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 关键字 | 14 | 1 | 9 | 23 | 84 | 27 | 55 | 20 | ||
| 比较次数 | 1 | 1 | 1 | 2 | 3 | 4 | 1 | 2 |
平均查找长度：ASL=（1+1+1+2+3+4+1+2）/8=15/8
以关键字23为例子：
H（23）=23%7=2（冲突）
采用二次探测再散列
（H（23）+1）%10=（2+1）%10=3
以关键字84为例子：
H（84）=84%7=0（冲突）
采用二次探测再散列
H1=（H（84）+1）%10=（0+1）%10=1（冲突）
H2=（H（84）+ 2^2）%10=（0+4）%10=4
以关键字27为例：
H（27）=27%7=6（冲突）
H1=（6+1）%10=7（冲突）
H2=（6+2^2）%10=0（冲突）
H3=（6+3^2）%10=5
所以比较了4次。