1.1

关于哈希表装填因子的问题。一组长度为11 的整形关键字为｛11，21，12，34，43，45，54，65，67，78，89｝，通过哈希函数H（key） = key Mod 11 映射到长度为11 的哈希表中，装填因子为_____(A)

A.1 B.2 C.3

装填因子 = 数据总数/存储空间的长度= 11/11 = 1
装填因子 a 的定义知道，a=n/m 其中n 为关键字个数，m为表长。

2.1

26 mod 13 = 0
25 mod 13 = 1 ...12
72 mod 13 = 5 ...7
38 mod 13 = 2 ...12  因为12号位置被占用了，所以顺序来到了0位置，也被占用了，所以来到了1号位置
8  mod 13 = 0 ...8
18 mod 13 = 1 ...5 
59 mod 13 = 4 ...7  因为7号位置被占用了，所以来到了8号位置，8号位置也被占用了，所以来到了9号位置

2.2

2.3

散列存储

又称hash存储，是一种力图将数据元素的存储，位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。

2.4

设散列表长度8，散列函数H（k）=k%7,用线性探测解决冲突，则根据一组初始关键字序列（8,15,16,22,30,32）构造出的散列表平均查找长度为什么是8/3呢？

0        1        2        3        4        5        6        7
         8        15       16       22       30       32
以上是数据在散列表中的分布
计算如下
（1+2+2+4+4+3）/6=8/3
括号里那6个数，从左到右分别是初始关键字序列中的每一个所需查找次数，从左到右

线性探测就是一旦冲突，向后移动寻找新位置，8占了位置1,15%7=1，但被8占了，所以只能移到2，以后查找15时也需要比较2次，即比较位置1和位置2，位置1内容为8，不为空，然后比较位置2，位置2为空；16%7=2，但位置2被15占了，16只能移到位置3，以后查找需比较2次，22%7=1，但位置1被占了，向后移，位置2,3都被占了，结果最终移到位置4，以后需要比较4次，即从1开始比较，直到比较第4位置，共为4次，如此推理，可得结果

3

4

5

6