数据结构与算法第十一单元测试题（判断+多选）测试题

1、数据结构与算法第十一单元测试题（判断+多选）复制1.在使用除留余数法时，对p的选择很重要。若p选的不好，容易产生同义词。 判断题 *对(正确答案)错2.二叉排序树的后序序列是指，按后序(左子树 右子树 根结点)的方式遍历该二叉排序树得到的序列。 判断题 *对(正确答案)错3.动态查找的常用方法是二叉排序树。 判断题 *对(正确答案)错4.静态查找与动态查找并没有什么区别。 判断题 *对错(正确答案)5动态查找表属于树形结构，因为这里涉及二叉排序树。 判断题 *对错(正确答案)6.装填因子是哈希表的一个重要参数，它反映哈希表的装满程度。 判断题 *对(正确答案)错7.若哈希表的装填因子1，则可避

2、免冲突的产生。 判断题 *对错(正确答案)8.负载因子(装填因子)是哈希表的一个重要参数,它反映哈希表的装满程度，该值越大则发生冲突可能性越大。 判断题 *对(正确答案)错9.哈希函数是一个映像。 判断题 *对(正确答案)错10.二叉排序树的左子树也应该不一定是棵二叉排序树。 判断题 *对错(正确答案)11.哈希表的平均查找长度与处理冲突的方法无关。 判断题 *对错(正确答案)12.二叉排序树的右子树也应该一定是棵二叉排序树。 判断题 *对(正确答案)错13.静态查找与动态查找主要区别在于是否改变表内的元素。 判断题 *对(正确答案)错14.二叉排序树的左子树也应该是棵二叉排序树。 判断题 *

3、对(正确答案)错15.二叉排序树的右子树也应该是棵二叉排序树。 判断题 *对(正确答案)错16.二叉排序树的查找方式跟顺序表的折半查找类似。 判断题 *对(正确答案)错17.中序遍历二叉排序树是降序序列。 判断题 *对错(正确答案)18.对不同的关键字可能得到同一哈希地址，即keykey2面f(key1)=f(key2)这种现象称冲突(collision)。具有相同函数值的关键词对该哈希来说乘坐同义词。(对) 单选题 *A 对(正确答案)B 错19.如果哈希表的长度足够大，就可以避免发生冲突。 判断题 *对错(正确答案)20.若对于关键字集合中的任何一个关键字，经哈希函数映像到地址集合中任何一

4、个地址的概率是相等的。则称此类哈希函数为均匀的(Uniform)哈希函数。 判断题 *对(正确答案)错21.直接定址法就是取关键字或关键字的某个线性函数值为哈希地址。 判断题 *对(正确答案)错22.关于二叉排序树描述有误的是（）。 *A.二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案)B.二叉排序的左子树上结点的关键字小于右子树上的结点的关键字C.二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)D.二叉排序的根节点的关键大于左子树上结点的关键字23.二叉排序的的哪些遍历序列，不能得到一个升序序列，或非递减有序序列。（） *A.先序序列(正确答案)B.中序遍历C.

5、后序遍历(正确答案)D.按层次遍历序列(正确答案)24.已知一棵树是二叉排序树，则该树具有（）的特点。 *A.若左子树不为空，则左子树上的所有结点的值(关键字)都小于根节点的值；(正确答案)B.若右子树不为空，则右子树上的所有结点的值(关键字)都大于根节点的值；(正确答案)C.左、右子树都分别为二叉排序树。(正确答案)D.其中序序列是一个非递减有序序列。(正确答案)25.动态查找表：边查找，边改变集合中的元素，改变的方式可以是（）。 *A.增加(正确答案)B.删除(正确答案)C.交换D.移动26.关于二叉排序树描述正确的是（）。 *A.二叉排序的右子树上结点的关键字小于左子树上的结点的关键字B

6、.二叉排序的左子树上结点的关键字小于右子树上的结点的关键字(正确答案)C.二叉排序的根节点的关键大于右子树上结点的关键字D.二叉排序的根节点的关键大于左子树上结点的关键字(正确答案)27.二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK；中序遍历HFIEJKG。该二叉树根的左子树的根不可能是:()。多选题 *A.E(正确答案)B.FC.G(正确答案)D.H(正确答案)28.下面属于构造散列函数的方法是（） *A.直接定址法(正确答案)B.数字分析法(正确答案)C.除留余数法(正确答案)D.平方取中法(正确答案)29.下面属于处理冲突的方法是（） *A.开放定址法(正确答案)B.再哈希法

7、(正确答案)C.除留余数法D.直接定址法30.关于装填因子，以下说法正确的是（）。 *A.哈希表的平均查找长度与处理冲突的方法无关。B.若散列表的负载因子(装填因子)1，则可避免冲突的产生。C.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。(正确答案)D.负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。(正确答案)31.哈希表的平均查找长度与哪些（）因素有关。 *A.处理冲突的方法(正确答案)B.哈希函数(正确答案)C.装填因子(正确答案)D.待存记录的大小32.装填因子的计算方法是（）。 *A.1-(表中未填入记录的数目/哈希表的总长度)

8、(正确答案)B.表中未填入记录的数目/哈希表的总长度C.(表中未填入的记录数-1)/哈希表的总长度D.表中填入的记录数/哈希表的总长(正确答案)33.关于二叉排序树相关描述正确的是（）。 *A.二叉排序树是应用于动态查找的结构(正确答案)B.二叉排序树的中序列是升序序列(正确答案)C.二叉排序树的左子树也是二叉排序树(正确答案)D.二叉排序树的定义具有递归性(正确答案)34.动态查找概念不正确的是（）。 *A.动态查找只查找不改变集合内的元素(正确答案)B.动态查找边查找，边改变集合内的元素C.动态查找与静态查找都是不改变集合内的元素(正确答案)D.上面没有正确的说法(正确答案)35.二叉排序

9、树的查找方式和（）相似，请将不是这个答案的选项选上。 *A.折半查找B.顺序查找(正确答案)C.随机查找(正确答案)D.跳跃式查找(正确答案)36.动态查找的典型工具是（），请将不是这个答案的选项选上。 *A.二叉排序树B.栈(正确答案)C.数组(正确答案)D.队列(正确答案)37.下列关于查找表描述正确的是（）。 *A.查找表分为静态查找表和动态查找表(正确答案)B.动态查找表边查找，边改变集合内的元素(正确答案)C.静态查找表只查找不改变集合中的元素(正确答案)D.其它选项说法都正确(正确答案)38.下面属于构造哈希函数的方法是（）。 *A.平方取中法(正确答案)B.再哈希法C.除留余数法

10、(正确答案)D.数字分析法(正确答案)39.查找哈希表，不是解决冲突的方法包括（）。 *A.数字分析法(正确答案)B.除留余数法(正确答案)C.直接地址法(正确答案)D.线性探测再散列法40.数据结构与算法里，设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度错误的是()。 *A.4(正确答案)B.3(正确答案)C.20/9D.23/9(正确答案)41.数据结构与算法里，关于哈希表的装填因子，以下正确的有（）。 *A.装填因子的值越小，发生冲突的概率越小(正确答案)B.装填因子越大，表中填入的记录越多，在填入的时候发生冲突的可能性就越大，在进行查找时候，查找的次数也就越多。(正确答案)C.装填因子=