目录
一、选择题
1、对一个长度为 10 的排好序的表用二分法查找，若查找不成功，
至少
需要比较的次数是（
B
）。A.4
B.3
C.5
D.6
折半查找在
查找不成功
和给定值进行比较的关键字的
比较次数最多
为
（向下取整） [log2n]+1次
，即判定树的最大层次数
2
、设有一组关键字 { 92，81， 58，21，57，45，161，38，117 }，散列函数为 h(key)=key%13，采用下列双散列探测方法解决第 i 次冲突：h(key)=(h(key)+i×h2(key))%13，其中 h2(key)=(key%11)+1。试在 0 到 12 的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为 __
A
A.1.67
B.1.56
C.1.44
D.1.33
3
、将关键字序列 { 7，8，30，11，18，9，14 }，散列存储到散列列表中，散列表的存储空间是一个下标从 0 开始的一维数组。处理冲突采用线性探测法。散列函数为 h(key)=(key×3)% 表长，要求装入因子为 0.7。则成功查找的平均查找长度为A.1.57
B.1.00
C.1.14
D.1.29
4、散列冲突可以被描述为：
C
A.两个元素除了有不同键值，其它都相同
B.两个有不同数据的元素具有相同的键值
C.两个有
不同键值
的元素具有
相同的散列地址
D.两个有相同键值的元素具有不同的散列地址
5、 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(
C
)。A.(n-1)/2
B.n/2
C.(n+1)/2
D.n
首先，有最好和最坏两种情况：
1、最好：第一个元素就是你要找的元素，即找了1次
2、最坏：顺序表中没有你要找的元素，也就是找了n次
故ASL=（1+n）/2
或 (1+2+3+……+n) / n =（1+n）/2
6、对线性表进行二分查找时，要求线性表必须（
B
）A.以顺序方式存储
B.以顺序方式存储,且数据元素有序
C.以链接方式存储
D.以链接方式存储,且数据元素有序
7、在散列存储中，装填因子α的值越大，则(
A
)。A.存取元素时发生冲突的可能性就越大
B.存取元素时发生冲突的可能性就越小
C.存取元素时不可能发生冲突
D.毫无影响
二、填空题
1、在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是
5
2、可以唯一的标识一个记录的关键字称为
主关键字
3、设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表。计算查找成功,失败的平均查找长度。 依次给出哈希表地址0–9单元的值。
14 1 9 23 84 0 55 20 27 0
平均查找长度：ASLsucc= （1×4+2×2+3+5）/ 8 =
2
平均查找失败长度：ASLunsucc=
4
