《数据结构：查找期末单元测试与答案.docx》由会员分享，可在线阅读，更多相关《数据结构：查找期末单元测试与答案.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、单项选择题1、对n个元素的表做顺序查找时，假设查找每个元素的概率相同，那么 平均查找长度为()。A.(n+l)/2B.(n-l)/2C.nD.n/2正确答案：A2、适用于折半查找的表的存储方式及元素排列要求为()。A.顺序方式存储，元素有序B.链接方式存储，元素无序C.链接方式存储，元素有序D.顺序方式存储，元素无序正确答案：A3、如果要求一个线性表既能较快的查找，又能适应动态变化的要求， 最好采用()查找法。A.哈希查找B.顺序查找C.折半查找D.分块查找正确答案：D4、折半查找有序表(4, 6, 10, 12, 20, 30, 50, 70, 88, 100)。假设查找表中元素58,那
2、么它将依次与表中（）比拟大小，查找结果 是失败。A.20, 70, 30, 50B.30, 88, 50C.20, 50D.30, 88, 70, 50正确答案：A5、对22个记录的有序表作折半查找，当查找失败时，至少需要比拟 （）次关键字。A.6B.5C.4D.3正确答案：C6、折半搜索与二叉排序树的时间性能（）0A.有时不相同B.完全不同C.相同D.数量级都是O（log2n）正确答案：A7、分别以以下序列构造二叉排序树，与用其它三个序列所构造的结 果不同的是（）oA. （100,120,110,130,80,60,90）B.（100, 80, 60, 90, 120, 130, 110）C
3、. （100,60,80,90,120,110,130）（100,80,90,60,120,110,130）正确答案：C8、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡 结点为A,并A的左孩子的平衡因子为0右孩子的平衡因子为1, 那么应作（）型调整以使其平衡。A.RLB.RRC.LLD.LR正确答案：A9、以下关于m阶B-树的说法错误的选项是（）oA.非叶结点至少有m/2 （m为偶数）或m/2+1 （m为奇数）棵子树B.根结点至多有m棵子树C.所有叶子都在同一层次上D.根结点至少有m-2棵子树正确答案：D10、下面关于B-和B+树的表达中，不正确的选项是（）oA.B-树和B+树都能
4、有效地支持随机检索B.B-树和B+树都可用于文件的索引结构C.B-树和B+树都能有效地支持顺序检索D.B-树和B+树都是平衡的多叉树正确答案：C11 m阶B-树是一棵（）。A.m+1叉平衡排序树B.m叉平衡排序树C.m叉排序树D.m-1叉平衡排序树正确答案：B12、下面关于哈希查找的说法，正确的选项是（）。A.不存在特别好与坏的哈希函数，要视情况而定B.哈希表的平均查找长度有时也和记录总数有关C.哈希函数构造的越复杂越好，因为这样随机性好，冲突小D.除留余数法是所有哈希函数中最好的正确答案：A13、下面关于哈希查找的说法，不正确的选项是（）。A.用链地址法处理冲突，适合表长不确定的情况B.采用
5、链地址法处理冲突时，假设插入规定总是在链首，那么插入任一个元素的时间是相同的C.采用链地址法处理冲突时，查找一个元素的时间是相同的D.用链地址法处理冲突，不会引起二次聚集现象正确答案：C14、设哈希表长为14,哈希函数是H（key）二key%ll,表中已有数据的 关键字为15, 38, 61, 84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，那么放入的位置是（）oA.9B.5C.8D.3正确答案：A15、采用线性探测法处理冲突，可能要探测多个位置，在查找成功的 情况下，所探测的这些位置上的关键字（）oA渚防目同B.一定都是同义词C.不一定都是同义词D.一定都不是同义词正确答案：C二、判断题1、在顺序表中进行顺序查找时，其查找成功的平均查找长度因各元 素无序或有序排列的情况不同而不同。正确答案：X2、进行折半查找的表既可以采用顺序存储结构，也可以采用链表结 构。正确答案：X3、对二叉排序树的查找都是从根结点开始的，如果查找失败，那么查 找指针一定落在叶结点上。正确答案：X4、对于两棵具有相同关键码集合而形状不同的二叉排序树，按中序 遍历它们得到的序列的各元素的顺序是一样的。正确答案：V5、在AVL树中，向某个平衡因子不为零的根结点的子树中插入一个 新结点，必引起平衡旋转。正确答案：X