1-1
在散列表中,所谓同义词就是被不同散列函数映射到同一地址的两个元素。
F
1-2
若用平方探测法解决冲突,则插入新元素时,若散列表容量为质数,插入就一定可以成功。
F
1-3
将M个元素存入用长度为S的数组表示的散列表,则该表的装填因子为M/S。
T
1-4
在散列中,函数“插入”和“查找”具有同样的时间复杂度。
T
O(1)
1-5
即使把2个元素散列到有100个单元的表中,仍然有可能发生冲突。
T
2-1
已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素,则关键字的比较次数最多是:
A.4
B.5
C.6
D.7
B!
2-2
用二分查找从100个有序整数中查找某数,最坏情况下需要比较的次数是:
A.7
B.10
C.50
D.99
A
2-3
在下列查找的方法中,平均查找长度与结点个数无关的查找方法是:
A.顺序查找
B.二分法
C.利用哈希(散列)表
D.利用二叉搜索树
C
2-4
散列冲突可以被描述为:
A.两个元素除了有不同键值,其它都相同
B.两个有不同数据的元素具有相同的键值
C.两个有不同键值的元素具有相同的散列地址
D.两个有相同键值的元素具有不同的散列地址
C
2-5
将10个元素散列到100000个单元的哈希表中,是否一定产生冲突?
A.一定会
B.可能会
C.一定不会
D.有万分之一的可能会
B
2-6
设散列表的地址区间为[0,16],散列函数为H(Key)=Key%17。采用线性探测法处理冲突,并将关键字序列{ 26,25,72,38,8,18,59 }依次存储到散列表中。元素59存放在散列表中的地址是:
A.8
B.9
C.10
D.11
D
2-7
下列二叉树中,可能成为折半查找判定树(不含外部结点)的是:
A B C D
A
mid的取值向上向下要统一
2-8
给定散列表大小为17,散列函数为H(Key)=Key%17。采用平方探测法处理冲突:h
i
(k)=(H(k)±i
2
)%17将关键字序列{ 6, 22, 7, 26, 9, 23 }依次插入到散列表中。那么元素23存放在散列表中的位置是:
A.0
B.2
C.6
D.15
B