数据结构与算法模拟试题
1.以下属于哈希函数的构造方法的是（）。
A:直接定址法(正确答案)
B:哈希再散列法
C:线性探测再散列法
D:二次探测再散列法
2.下列关于二叉排序树中说法正确的是（）。
A:二叉排序树的定义具有反复性
B:二叉排序树的定义具有递归性(正确答案)
C:二叉排序树的定义具有回溯性
排序题D:二叉排序树的定义具有反弹性
3.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）。
A:k-1次
B:k次
C:k+1次
D:k(k+1)/2次(正确答案)
4.哈希表的查是依靠（）来计算出元素的存储地址的。
A:哈希函数(正确答案)
B:逐一比对
C:折半比较
D:集合
5.在各种查方法中，平均查长度ASL与结点个数n无关的查方法是（）。
A:顺序查
B:折半查
C:哈希查(正确答案)
D:分块查
6.装填因子又称为（）。
A:负载因子(正确答案)
B:平衡因子
C:外力因子
D:合力因子
7.先序遍历一颗二叉排序树的顺序是（）。
A:左子树根结点右子树
B:根结点左子树右子树(正确答案)
C:左子树右子树根结点
D:都不对
8.关于二叉排序树的遍历顺序说法正确的是（）。
A:中序遍历一颗二叉排序树的顺序是：左子树根结点右子树(正确答案)
B:中序遍历一颗二叉排序树的顺序是：根结点左子树右子树
C:中序遍历一颗二叉排序树的顺序是：左子树右子树根结点
D:无正确答案
9.关于二叉排序树的结点个数为0时称为什么描述正确的是（）。
A:二叉排序树可以含有0个结点，这时它是一棵空二叉排序树(正确答案)
B:二叉排序树可以含有0个结点，这时它是一棵满二叉排序树
C:二叉排序树可以含有0个结点，这时它是一棵完全二叉排序树
D:无正确答案
10.关于二叉排序树的作用描述正确的是（）。
A:二叉排序树是应用于静态查的结构
B:二叉排序树是应用于动态查的结构(正确答案)
C:二叉排序树是应用于随机查的结构
D:无正确答案
11.动态查表：边查，边改变集合中的元素，改变的方式可以是（）。
A:增加(正确答案)
B:删除(正确答案)
C:交换
D:移动
12.数据结构与算法里，关于哈希表的装填因子，以下正确的有（）。
A:装填因子的值越小，发生冲突的概率越小(正确答案)
B:装填因子越大，表中填入的记录越多，在填入的时候发生冲突的可能性就越大，在进行查时候，查的次数也就越多。(正确答案)
C:装填因子=表中填入的记录数/哈希表的总长度(正确答案)
D:装填因子的值越小，就可以避免冲突的发生
13.数据结构与算法里，设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查成功平均查长度错误的是()。
A:4(正确答案)
B:3(正确答案)
C:20/9
D:23/9(正确答案)
14.关于二叉排序树描述有误的是（）。
A:二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案)
B:二叉排序的左子树上结点的关键字小于右子树上的结点的关键字
C:二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)
D:二叉排序的根节点的关键大于左子树上结点的关键字
15.下列关于查表描述正确的是（）。
A:查表分为静态查表和动态查表(正确答案)
B:动态查表边查，边改变集合内的元素(正确答案)
C:静态查表只查不改变集合中的元素(正确答案)
D:其它选项说法都正确(正确答案)
16.装填因子是哈希表的一个重要参数，它反映哈希表的装满程度。
对(正确答案)
错
17.动态查表属于树形结构，因为这里涉及二叉排序树。
对
错(正确答案)
18如果哈希表的长度足够大，就可以避免发生冲突。
对
错(正确答案)
19.二叉排序树的右子树也应该一定是棵二叉排序树。
对(正确答案)
错
20.哈希函数是一个映像。