下载文档原格式
《二分查找》作业一、选择题1. 二分查找算法要求待查找的数组必须是（）。
A. 无序的B. 有序的C. 循环的D. 不确定答案：B解析：二分查找算法基于有序数组进行操作。
它通过不断将查找范围减半来定位目标元素，这要求数组必须是有序的。
2. 在二分查找中，如果查找的元素不存在于数组中，算法会返回（）。
A. 第一个大于目标元素的值的位置B. 最后一个小于目标元素的值的位置C. -1或类似的标识符D. 数组的长度答案：C解析：当二分查找无法找到目标元素时，通常会返回一个特殊值（如-1）来表示查找失败。
这是因为二分查找算法无法确定目标元素应该插入的位置。
3. 二分查找的时间复杂度是（）。
A. O(1)B. O(log n)C. O(n)D. O(n^2)答案：B解析：二分查找算法每次将查找范围减半，因此其时间复杂度是对数级别的，即O(log n)。
4. 对于长度为n的有序数组，二分查找最坏情况下的比较次数大约是（）。
A. log₂(n)B. n/2C. nD. 2n答案：A解析：在最坏情况下，二分查找需要比较log₂(n)次才能找到目标元素或确定目标元素不存在。
这是因为每次比较都将查找范围减半。
5. 如果一个有序数组是升序排列的，使用二分查找算法来查找一个不存在的元素，比较次数可能会（）。
A. 减少B. 不变C. 增加D. 不确定答案：A解析：虽然二分查找算法不直接利用数组的升序或降序排列特性，但在查找不存在的元素时，由于数组是有序的，一旦某个区间内的所有元素都大于或小于目标元素，就可以立即排除该区间，从而减少比较次数。
6. 在二分查找算法中，如果数组中存在多个相同的目标元素，那么（）。
A. 只能找到一个目标元素B. 可以找到所有目标元素的位置C. 只能找到第一个目标元素的位置D. 只能找到最后一个目标元素的位置答案：C解析：二分查找算法在找到目标元素后会停止搜索，并返回该元素的位置。
如果数组中存在多个相同的目标元素，算法只会返回第一个找到的元素的位置。
题目：有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。
选项A：26/10选项B：29/10选项C：29/9选项D：31/10答案：29/10题目：已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。
选项A：3选项B：6选项C：5选项D：4答案：5题目：有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。
选项A：45,24,53,12,37,96,30选项B：37,24,12,30,53,45,96选项C：30,24,12,37,45,96,53选项D：12,24,30,37,45,53,96答案：37,24,12,30,53,45,96题目：对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是（）。
选项A：5选项B：3选项C：6选项D：4答案：4题目：在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。
选项A：直接插入排序选项B：希尔排序选项C：冒泡排序选项D：直接选择排序答案：直接选择排序题目：对线性表进行二分查找时，要求线性表必须（）。
选项A：以顺序存储方式，且数据元素有序选项B：以链接存储方式选项C：以顺序存储方式选项D：以链接存储方式，且数据元素有序答案：以顺序存储方式，且数据元素有序题目：采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。
选项A：(n+1)/2选项B：n/2选项C：(n-1)/2选项D：n答案：(n+1)/2题目：从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。
将其放入已排序序列的正确的位置上，此方法称为（）。
选项A：交换排序选项B：归并排序选项C：选择排序选项D：插入排序答案：插入排序题目：依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。
第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m-1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
《数据结构》大作业
数据结构是计算机科学中构建可靠计算机系统所必需的基础知识。
它主要是用来处理
非常大的量级的数据，并为用户快速访问，高效的解决计算机问题。
由于中央处理机的特
点是高速而有效，起到了极大的性能提升。
数据结构有很多不同的结构，其中最重要的是线性结构和非线性结构。
线性结构又可
以分为数组、单向链表、双向链表和循环链表；非线性结构可以分为二叉树、二叉搜索树、B树、堆、红黑树和图。
在实际计算机程序中，数据结构一般被用来搜索和排序存储的数据，这些操作有助于
提高计算机的运行效率。
如果用户想要查找某一个数据，可以在合适的存储结构中找到它；如果用户希望把一系列数据按照某种顺序排列起来，也可以使用数据结构进行排序。
同时数据结构还可以用于实现数据结构间的转换，使得用户可以较为方便的获得数据。
它的运用，更加方便了计算机的工作，更加提高了计算机的性能。
总之，数据结构是计算机科学中重要的组成部分，它为计算机的工作提供了重要的基础，更加方便了用户的操作，也帮助用户更好地完成计算机系统中的各种工作和解决方案。
作业1. 线性表编程作业：1．将顺序表逆置，要求用最少的附加空间。
参考答案#include <>#include <>#include <>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ ElemType *elem;int length;int listsize;}SqList;立单链表 ");printf("2.取元素值 ");printf("3.查找 \n");printf("4.插入 ");printf("5.删除 ");printf("6.显示\n");printf("7.删除大于mink且小于maxk的元素值 ");printf("8.就地升序排序\n");printf("9.就地逆置 ");printf("a.有序表插入 ");printf("q.退出\n");printf("\n请选择操作：");fflush(stdin);scanf("%c",&choice);switch(choice){case '1': printf("请输入单链表中结点个数：");scanf("%d",&n);Create_L2(L,n);break;case '2': printf("请输入元素位序：");scanf("%d",&i);GetElem_L(L,i,e);printf("元素值为：%d\n",e);break;case '3': printf("请输入要查找的元素：");scanf("%d",&e);if(dlbcz(L,e))printf("查找成功！");elseprintf("查找失败。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m -1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
数据结构作业——分块查找算法分块查找算法（Block Search Algorithm）是一种基于数据分块的查找算法，用于在一个有序数据集合中进行查找。
该算法把数据集合划分为若干个块（block），每个块中的数据是有序的。
通常情况下，每个块的数据量较小，比如每个块只包含100个数据。
块之间的数据是无序的。
在进行查找操作时，首先确定目标数据所在的块。
然后在确定的块中使用二分查找等方法进行查找。
这样一来，通过一次定位和一次块内查找操作，就可以实现整个数据集合的查找。
与传统的二分查找相比，分块查找的优势在于它减少了查找的次数。
首先，通过确定目标数据所在的块，剔除了绝大部分数据。
接下来，只需要在确定的块中进行查找，而不需要遍历整个数据集合。
因此，分块查找的时间复杂度较低。
在使用分块查找算法时，需要根据实际情况选择合适的块大小。
如果每个块的数据量过大，会导致块内查找的时间复杂度增加；如果每个块的数据量过小，可能会增加块定位的时间。
因此，需要权衡块内查找和块定位的效率，选择一个合适的块大小。
此外，分块查找还可以通过建立辅助索引来优化查找效率。
例如，可以在数据集合的每个块中保存一个最小值和一个最大值，作为块的索引。
这样，在进行查找时，可以先通过辅助索引定位到合适的块，再进行块内查找，进一步提高查找的效率。
总的来说，分块查找算法通过对数据进行分块，结合块定位和块内查找，实现了高效的查找操作。
它是一种满足实际应用需求的查找算法，常被用于静态和动态数据集合的查找任务。
同时，分块查找也为其他高级查找算法（如B树）提供了一种重要的基础。
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
一、第一次作业
①写一个函数find，实现从数组a[n]查找元素x，返回x在数组中的序号，如果找不到则返回-1。
②当a[n]递增有序时，有没有高效的算法？
③以Niklus Wirth的观点，程序是什么?
④算法有什么特性？
⑤好算法应该满足哪些标准？
⑥数据结构主要在哪些层面上讨论问题？
⑦按增长率由小至大的顺序排列下列各函数（严蔚敏题集1.10）
⑧试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z 的值（严蔚敏题集1.16）
二、第二次作业
1)题集2.2（严蔚敏）
2)题集2.10（严蔚敏）
3)题集2.12（严蔚敏）
4)题集2.7（严蔚敏）
5)题集2.15（严蔚敏）
三、第三次作业
第二章题集1、9、10（于津、陈银冬）
四、第四次作业
第三章题集1、2、3、4、5（于津、陈银冬）
五、第五次作业
①第四章题集2、5（于津、陈银冬）
②实现以下C库函数：
(1)strlen(cs)
(2)strcpy(s, ct)
(3)strcmp(cs, ct)
③完成对称矩阵、三角矩阵、对角矩阵在压缩存储下的输入输出算法
④第五章题集1、2、3（于津、陈银冬）
六、第六次作业
第六章题集1、2、10（于津、陈银冬）
七、第七次作业
第六章题集3、8、12、13（于津、陈银冬）
八、第八次作业
第六章题集6、7、9、15（于津、陈银冬）
九、第九次作业
第七章题集1、7（另加上“十字链表”存储）（于津、陈银冬）。
24秋学期《数据结构》作业参考1.堆的形状是一棵()选项A：二叉排序树选项B：满二叉树选项C：完全二叉树选项D：平衡二叉树参考答案：C2.用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的选项A：栈选项B：队列选项C：树选项D：图参考答案：A3.栈中元素的进出原则是（）选项A：先进先出选项B：后进先出选项C：栈空则进选项D：栈满则出参考答案：B4.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()选项A：79,46,56,38,40,84选项B：84,79,56,38,40,46选项C：84,79,56,46,40,38选项D：84,56,79,40,46,38参考答案：B5.有8个结点的无向图最多有（）条边选项A：14选项B：28选项C：56选项D：112参考答案：B6.链表是一种采用存储结构存储的线性表选项A：顺序选项B：链式选项C：星式选项D：网状参考答案：B7.下列关键字序列中，()是堆选项A：16,72,31,23,94,53选项B：94,23,31,72,16,53选项C：16,53,23,94，31,72选项D：16,23,53,31,94,72参考答案：D8.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
选项A：20，70，30，50选项B：30，88，70，50选项C：20，50选项D：30，88，50参考答案：A9.已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（）选项A：0 2 4 3 1 5 6选项B：0 1 3 5 6 4 2。
东北农业大学网络教育学院数据结构作业题(一)一、选择题（每题2分,共20分）1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( ）。
A、O（n)B、O（n/2)C、O (1)D、O（n2）2．带头结点的单链表first为空的判定条件是（）。
A、first == NULL;B、first->link == NULL；C、first-〉link == first；D、first != NULL；3．在一棵树中,（）没有前驱结点.A、分支结点B、叶结点C、树根结点D、空结点4．在有向图中每个顶点的度等于该顶点的( ）。
A、入度B、出度C、入度与出度之和D、入度与出度之差5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )的值除以9。
A、20B、18C、25D、226．下列程序段的时间复杂度为( ）。
s=0；for(i=1;i<n;i++)for(j=1；j〈n；j++）s+=i*j；A、O（1)B、O (n)C、O（2n）D、O（n2）7．栈是一种操作受限的线性结构，其操作的主要特征是（）。
A、先进先出B、后进先出C、进优于出D、出优于进8．假设以数组A[n］存放循环队列的元素，其头、尾指针分别为front和rear.若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。
A、（rear-front—1)％nB、(rear—front)％nC、(front-rear+1）%nD、(rear—front+n)％n9．高度为5的完全二叉树中含有的结点数至少为（）。
A、16B、17C、31D、3210．如图所示有向图的一个拓扑序列是( )A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空题(每空1分,共20分)1．n (n﹥0）个顶点的无向图最多有条边,最少有条边。
2．在一棵A VL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过.3．已知8个数据元素为(34，76,45,18，26，54，92,65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为。
数据结构实验报告三题目：试编写利用折半查找确定记录所在块的分块查找算法。
提示：1)读入各记录建立主表；2)按L个记录/块建立索引表；3)对给定关键字k进行查找；测试实例：设主表关键字序列：{12 22 13 8 28 33 38 42 87 76 50 63 99 101 97 96}，L=4 ，依次查找K=13， K=86，K=88算法思路题意要求对输入的关键字序列先进行分块，得到分块序列。
由于序列不一定有序，故对分块序列进行折半查找，找到关键字所在的块，然后对关键字所在的块进行顺序查找，从而找到关键字的位置。
故需要折半查找和顺序查找两个函数，考虑用C++中的类函数实现。
因为序列一般是用数组进行存储的，这样可以调用不同类型的数组，程序的可适用性更大一些。
折半查找函数：int s,d,ss,dd;//声明一些全局变量，方便函数与主函数之间的变量调用。
template <class T>int BinSearch(T A[],int low,int high,T key)//递归实现折半查找{int mid;// 初始化中间值的位置T midvalue;// 初始化中间值if (low>high){s=A[high];d=A[low];ss=high;dd=low;return -1;}// 如果low的值大于high的值，输出-1，并且将此时的low与high的值存储。
else{mid=(low+high)/2;// 中间位置为低位与高位和的一半取整。
midvalue=A[mid];if (midvalue==key)return mid;else if (midvalue < key) //如果关键字的值大于中间值return BinSearch(A,mid+1,high,key);// 递归调用函数，搜索下半部分elsereturn BinSearch(A,low,mid-1,key);// 否则递归调用哦个函数，搜索上半部分}}以上为通用的折半查找的函数代码，这里引入了几个全局变量，主要是方便在搜索关键字在哪一个分块中时，作为判断条件。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m -1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
数据结构第九章查找作业及答案第九章查找一、填空题1.在数据的存放无规律而言的线性表中进行检索的最佳方法是2.线性有序表（a1，a2，a3，，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。
设有100个结点，用二分法查找时，最大比较次数是3.假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为,其下标从小到大依次是____，平均查找长度为4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。
5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是6.散列法存储的基本思想是由决定数据的存储地址。
7.有一个表长为m的散列表，初始状态为空，现将n（n8、设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P<=M）,为使函数具有较好性能，P应选9、在各种查找方法中，平均查找长度与结点个数无关的是10、对线性表进行二分查找时，要求线性表必须以方式存储，且结点按关键字排列。
11在分块查找方法中，首先查找索引，然后再查找相应的12．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为___次；当使用监视哨时，若查找失败，则比较关键字的次数为__ 13．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为14.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是___。
15.已知二叉排序树的左右子树均不为空，则__上所有结点的值均小于它的根结点值，上所有结点的值均大于它的根结点的值。
16、中序遍历二叉排序树得到的序列是序列（填有序或无序）。
17、从有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素时，其查找长度分别为和·二、单项选择题1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为（）Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝n＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
1.设有序表为(1、23、34、55、56、57、77、87、99)请分别画出对给定值23，56，98进行折半查找的过程。
（并注明每次循环的各参数变量的结果）23的查找过程如下（其中括号表示当前查找区间，圆括号表示当前比较的关键字）
下标： 1 2 3 4 5 6 7 8 9
第一次比较：[ 1 23 34 55（56）57 77 87 99]
low=1
high=9
mid=5
第二次比较：[ 1（23）34 55] 56 57 77 87 99]
low=1
high=4
mid=2
56的查找过程如下（其中括号表示当前查找区间，圆括号表示当前比较的关键字）
下标： 1 2 3 4 5 6 7 8 9
第一次比较：[ 1 23 34 55（56）57 77 87 99]
low=1
high=9
mid=5
98的查找过程如下（其中括号表示当前查找区间，圆括号表示当前比较的关键字）
下标： 1 2 3 4 5 6 7 8 9
第一次比较：[ 1 23 34 55（56）57 77 87 99]
low=1
high=9
mid=5
第二次比较： 1 23 34 55 56 [57 (77) 87 99]
low=6
high=9
mid=7
第三次比较： 1 23 34 55 56 57 77[(87) 99]
low=8
high=9
mid=8
第四次比较： 1 23 34 55 56 57 77 87[(99)]
low=9
high=9
mid=9
第五次比较： 1 23 34 55 56 57 77 87 99
low=9
high=8
low>high 查找不成功。
2
设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数
H(key)=key % 13，采用开放地址法(开放定址法)的二次探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造哈希表。
解：依题意，n=19，二次探测再散列的下一地址计算公式为：其计算如下：
H(19)=19 % 13 =6 H(01)=01 % 13 =1 H(23)=23 % 13 =10 H(14)=14 % 13
=1(冲突) H(14)=(1+1*1) % 19 =2 H(55)=55 % 13 =3 H(20)=20 % 13 =7 H(84)=84 % 13 =6(冲突) H(84)=(6 + 1*1) % 19 =7(仍冲突) H(84)=(6 -
1*1) % 19 =5 H(27)=27 % 13 =1(冲突) H(27)=(1+1*1) % 19 =2(冲突) H(27)=(1-1*1) % 19 =0 H(68)=68 %13 =3(冲突) H(68)=(3+1*1) %19 =4 H(11)=11 % 13 =11 H(10)=10 % 13 =10(冲突) H(10)=(10+1*1) % 19 =11(仍
冲突) H(10)=(10-1*1)%19=9 H(77)=77 %13 =12 因此：各关键字的记录对应的地址分配如下：addr(27) = 0addr(01) = 1addr(14)
= 2addr(55) = 3addr(68) = 4addr(84) = 5addr(19) = 6addr(20) = 7addr(10)
= 9addr(23) = 10addr(11) = 11addr(77) = 12其他地址为空。
