王贰家

第一题、单项选择题（每题1分，5道题共5分）
1、对线性表进行折半查找时，要求线性表必须＿＿＿C＿＿＿＿。
A、以顺序方式存储 B、以链式方式存储
C、以顺序方式存储且表中元素按关键字有序排列 D、以链式方式存储且表中元素按关键字有序排列
2、用线性探测法解决冲突问题时，所产生的一系列后继散列地址＿＿＿A＿＿＿＿。
A、可以大于或小于但不能等于原散列地址 B、必须大于或等于原散列地址
C、必须小于或等于原散列地址 D、无具体限制
3、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿D＿＿＿查找方法。
A、折半 B、顺序
C、分块 D、散列
4、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中折半查找值为82的结点时，＿＿＿＿C＿＿＿次比较后查找成功。
A、1 B、2
C、4 D、8
5、高度为5的二叉平衡树至少有＿＿＿B＿＿＿＿个结点。
A、10 B、12
C、15 D、17
第二题、多项选择题（每题2分，5道题共10分）
1、构造散列函数时通常考虑的因素有＿＿＿ABCD＿＿＿＿。
A、计算函数的工作量
B、关键字的长度
C、散列表长
D、关键字的分布情况
2、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿ACEH＿＿＿＿＿。
A、1
B、2
C、3
D、4
E、6
F、7
G、8
H、9
3、下列关于n个结点的m阶B树的说法中，正确的是＿＿＿CDE＿＿＿＿。
A、树中每个结点最多有m个关键字
B、树中叶子结点的个数为n+1
C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。
D、树中所有叶子结点都在同一层，并且不带任何信息
E、树中每个结点最多有m-1个关键字
F、树中每个结点最多有m+1个关键字
4、影响散列表的平均查找长度的因素有＿＿＿ACD＿＿＿＿。
A、散列函数
B、散列表长
C、装填因子
D、处理冲突的方法
5、在下列各种查找方法中，平均查找长度与表长有关的查找方法是＿＿＿BCD＿＿＿＿。
A、散列表查找
B、顺序查找
C、折半查找
D、排序树查找
第三题、判断题（每题1分，5道题共5分）
1、散列表的装填因子越小，发生冲突的可能性越大。 F
正确 错误
2、在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。 F
正确 错误
3、二叉树为二叉排序树的充要条件是，其任意结点的值均大于其左孩子的值且小于其右孩子的值。 F
正确 错误
4、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。T
正确 错误
5、若散列表的装填因子小于1，则可避免冲突的产生 F
正确 错误