在数据的存放无规律而言的线性表中进行检索的最佳方法

《在数据的存放无规律而言的线性表中进行检索的最佳方法》由会员分享，可在线阅读，更多相关《在数据的存放无规律而言的线性表中进行检索的最佳方法（5页珍藏版）》请在装配图网上搜索。

1、第7章查找自测卷姓名 班级一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法。2. 线性有序表(a1，a2, a3,，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相 等的元素，在查找不成功的情况下，最多需要检 次。设有100个结点，用二分法查找时，最大比 较次数是。3. 假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。4. 折半查找有序表(4, 6, 12, 20，28, 38, 50，70，88, 100)，若查找表中元素20，它将依次与表中 元素比较大小。5.

2、 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。6. 散列法存储的基本思想是由决定数据的存储地址。7. 有一个表长为m的散列表，初始状态为空，现将n(nm)个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数。二、单项选择题()1.在表长为n的链表中进行线性查找，它的平均查找长度为A. ASL = n;B. ASL=(n+l)/2;C. ASL= n +1 ； D. AS Lr lo&2(n+1)1()2.折半查找有序表(4,6,10,12,20,30,50,70,88, 100)。若查找表中元素58,则它将依次与表中 比较

3、大小，查找结果是失败。A. 20,70,30，50 B.30，88，70,50C.20,50 D.30,88,50()3.对22个记录的有序表作折半查找，当查找失败时，至少需要比 次关键字。A. 3B. 4C. 5D. 6()4.链表适用于查找人.顺序B.二分法C.顺序，也能二分法D.随机()5.折半搜索与二叉搜索树的时间性能A.相同 B.完全不同C.有时不相同D.数量级都是O (log2n)6. 要进行线性查找，则线性表A ；要进行二分杳找，则线性表B:要进行散列查找，则线性表C_。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同

4、的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D，最大比较次数为。供选择的答案：AC：必须以顺序方式存储必须以链表方式存储必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 必须以链表方式存储且数据元素已按值递增或递减的次序排好D, E： 25000 30000 45000 90000答案： A= B= C= D= E=7. 数据结构反映了数据元素之间的结构关系。链表是一种一A，它对于数据元素的插入和删除 。通常杳找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序 存储结构

5、但 E 的方法；而是一种对顺序和链式存储结构均适用的方法。供选择的答案： 顺序存储非线性表非顺序存储线性表不需要移动结点，只需改变结点指针 既需移动结点，又需改变结点指针二分法查找分块查找A：顺序存储线性表非顺序存储非线性表B：不需要移动结点，不需改变结点指针 只需移动结点，不需改变结点指针C：顺序查找循环查找条件查找D：顺序查找随机查找二分法查找E：效率较低的线性查找效率较低的非线性查找效率较高的非线性查找效率较高的线性查找 答案：A= B= C= D= E=8. 在二叉排序树中，每个结点的关键码值A，一棵二叉排序，即可得到排序序列。同一个结点 集合，可用不同的二叉排序树表示，人们把平均检索

6、长度最短的二叉排序树称作最佳二叉排序，最佳二叉 排序树在结构上的特点是C 。供选择的答案A：比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 比左右子树的所有结点的关键码值都大 与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系B:前序遍历 中序（对称）遍历 后序遍历层次遍历C：除最下二层可以不满外，其余都是充满的除最下一层可以不满外，其余都是充满的每个结点的左右子树的高度之差的绝对值不大于1最下层的叶子必须在最左边答案：A= B= C=9. 散列法存储的基本思想是根据_ 来决定，碰撞（冲突）指的是C，处理

7、碰撞的两类主要方法是D 。供选择的答案A，B：存储地址元素的符号元素个数关键码值 非码属性平均检索长度负载因子散列表空间C:两个元素具有相同序号两个元素的关键码值不同，而非码属性相同不同关键码值对应到相同的存储地址 负载因子过大数据元素过多D： 线性探查法和双散列函数法 建溢出区法和不建溢出区法除余法和折叠法拉链法和开地址法答案：A= B= C= D=10. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小 于等于其右子树上的一切结点的值。现把9个数1，2, 3，8, 9填入下图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是4，n2的值是

8、，n9的值是 _。现欲把&0放入此树并使该树保持前述性质，增 加的一个结点可以放在_ D或_。供选择的答案AC：123456789DE：n7下面n8下面n9下面n6下面n1与n2之间n2与n4之间答案：A= B= C=D= E=n6与n9之间n3与n6之间三、简答题1. 对分(折半)查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度 快，这种说法对吗？2. 假定对有序表：(3,4,5, 7, 24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题:(1) 画出描述折半查找过程的判定树；(2) 若查找元素54,需依次与哪些元素比较？(3) 若查找元

9、素90,需依次与哪些元素比较？(4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。3. 用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么？如果要求时 间复杂度更小，你采用什么方法？此方法的时间复杂度是多少？4.设哈希(Hash)表的地址范围为017，哈希函数为：H (K)=K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： (10,24,32,17,31,30,46,47,40,63,49)造出Hash表，试回答下列问题：(1) 画出哈希表的示意图；(2) 若查找关键字63,需要依次与哪些关键字进行比较？(3) 若查找关键字60,需要依次与哪些关键字比较？(4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。四、分析题1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。2. 在一棵空的二叉查找树中依次插入关键字序列为12,7,17,11，16,2,13,9,21，4,请画出所得到的二叉查找树。五、算法设计题1. 已知11个元素的有序表为(05 13 19 21 37 56 64 75 80 88 92),请写出折半查找的算 法程序，查找关键字为key的数据元素(建议上机调试)。2. 编写判定给定的二叉树是否是二叉排序树的函数。