顺序查找、折半查找和分块查找算法的适用范围

数据结构练习（三）参考一、选择题1.顺序查找法适合于存储结构为的线性表A）哈希存储C）压缩存储D）索引存储2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较________次。

A）9 B）8 C）73.采用顺序查找方法查找长度为n的线性表时，平均比较次数为。

A）n B）n/2 n+1）/2 D）（n-1）/24.对线性表进行折半查找时，要求线性表必须。

A）以顺序方式存储C）以链表方式存储D）以链表方式存储，且结点按关键字有序排列5.采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度为。

A）O（n2）B）O（nlog2n）C）O（n）（log2n）6.有一个长度为12的有序表R[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为。

A）35/12 C）39/12 D）43/127.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，99}，当采用折半查找法查找关键字为82的元素时，次比较后查找成功。

A）1 B.2 D）88.当采用分块查找时，数据的组织方式为。

A）数据分成若干块，每块内存数据有序每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D）数据分成若干块，每块（出最后一块外）中的数据个数需相同9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳。

A）10 C）6 D）62510.不能生成右图所示二叉排序树的关键字序列是_____。

B）42531 C）45213 D）4231511.按____遍历二叉排序树，可以得到按值递增或递减次序的关键码序列。

A）先序C）后序D）层序12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是。

查找与排序部分习题一、选择题1.设有100个元素，用折半查找法进行查找时，最大比较次数是______。

Ａ、25 B、8 C、10 D、72.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值82的结点时，______次比较后查找成功。

（注：计算中间位置时取下整）A、1B、2C、4D、83.顺序查找法适合于存储结构为______的线性表。

A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储4.某顺序存储的表格中有90000个元素，以按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同，用顺序查找法查找时，平均比较次数约为______；最大比较次数约为______。

A、25000B、30000C、45000D、900005.设散列地址空间为0到m-1，k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）=k%p。

为了减少发生冲突的频率，一般取p为______。

A、小于m的最大奇数B、小于m的最大偶数C、小于m的最大素数D、大于m的最大素数6.设有9个数据记录组成的线性表，它们的排序关键字的取值分别是（11，15，20，27，30，35，46，88，120），已将它们按照排序关键字递增有序的方式存放在一维结构数组a[0..8]中从下标0开始到下标8结束的位置，则当采用折半查找算法查找关键字值等于20的数据记录时，所需比较的元素下标依次是：______。

（注：计算中间位置时取下整）A、0，1，2B、4，1，2C、4，2D、4，3，27.顺序查找一个共有n个元素的线性表，其时间复杂度为______。

A、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)8.设有100个元素，用折半查找法进行查找时，最小比较次数是______。

A、7B、4C、2D、19.哈希法中，除了考虑构造“均匀”的哈希函数外，还要解决冲突的问题，以下选项中______不是解决冲突的办法。

查找表结构查找表介绍在⽇常⽣活中，⼏乎每天都要进⾏⼀些查找的⼯作，在电话簿中查阅某个⼈的电话号码；在电脑的⽂件夹中查找某个具体的⽂件等等。

本节主要介绍⽤于查找操作的数据结构——查找表。

查找表是由同⼀类型的数据元素构成的集合。

例如电话号码簿和字典都可以看作是⼀张查找表。

⼀般对于查找表有以下⼏种操作：在查找表中查找某个具体的数据元素；在查找表中插⼊数据元素；从查找表中删除数据元素；静态查找表和动态查找表在查找表中只做查找操作，⽽不改动表中数据元素，称此类查找表为静态查找表；反之，在查找表中做查找操作的同时进⾏插⼊数据或者删除数据的操作，称此类表为动态查找表。

关键字在查找表查找某个特定元素时，前提是需要知道这个元素的⼀些属性。

例如，每个⼈上学的时候都会有⾃⼰唯⼀的学号，因为你的姓名、年龄都有可能和其他⼈是重复的，唯独学号不会重复。

⽽学⽣具有的这些属性（学号、姓名、年龄等）都可以称为关键字。

关键字⼜细分为主关键字和次关键字。

若某个关键字可以唯⼀地识别⼀个数据元素时，称这个关键字为主关键字，例如学⽣的学号就具有唯⼀性；反之，像学⽣姓名、年龄这类的关键字，由于不具有唯⼀性，称为次关键字。

如何进⾏查找？不同的查找表，其使⽤的查找⽅法是不同的。

例如每个⼈都有属于⾃⼰的朋友圈，都有⾃⼰的电话簿，电话簿中数据的排序⽅式是多种多样的，有的是按照姓名的⾸字母进⾏排序，这种情况在查找时，就可以根据被查找元素的⾸字母进⾏顺序查找；有的是按照类别（亲朋好友）进⾏排序。

在查找时，就需要根据被查找元素本⾝的类别关键字进⾏排序。

具体的查找⽅法需要根据实际应⽤中具体情况⽽定。

顺序查找算法(C++)静态查找表既可以使⽤顺序表表⽰，也可以使⽤链表结构表⽰。

虽然⼀个是数组、⼀个链表，但两者在做查找操作时，基本上⼤同⼩异。

顺序查找的实现静态查找表⽤顺序存储结构表⽰时，顺序查找的查找过程为：从表中的最后⼀个数据元素开始，逐个同记录的关键字做⽐较，如果匹配成功，则查找成功；反之，如果直到表中第⼀个关键字查找完也没有成功匹配，则查找失败。

数据结构中的查找算法总结静态查找是数据集合稳定不需要添加删除元素的查找包括：1. 顺序查找2. 折半查找3. Fibonacci4. 分块查找静态查找可以⽤线性表结构组织数据，这样可以使⽤顺序查找算法，再对关键字进⾏排序就可以使⽤折半查找或斐波那契查找等算法提⾼查找效率，平均查找长度：折半查找最⼩，分块次之，顺序查找最⼤。

顺序查找对有序⽆序表均适⽤，折半查找适⽤于有序表，分块查找要求表中元素是块与块之间的记录按关键字有序动态查找是数据集合需要添加删除元素的查找包括： 1. ⼆叉排序树 2. 平衡⼆叉树 3. 散列表 顺序查找适合于存储结构为顺序存储或链接存储的线性表。

顺序查找属于⽆序查找算法。

从数据结构线形表的⼀端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相⽐较，若相等则表⽰查找成功 查找成功时的平均查找长度为： ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 顺序查找的时间复杂度为O(n)。

元素必须是有序的，如果是⽆序的则要先进⾏排序操作。

⼆分查找即折半查找，属于有序查找算法。

⽤给定值value与中间结点mid的关键字⽐较，若相等则查找成功；若不相等，再根据value 与该中间结点关键字的⽐较结果确定下⼀步查找的⼦表 将数组的查找过程绘制成⼀棵⼆叉树排序树，如果查找的关键字不是中间记录的话，折半查找等于是把静态有序查找表分成了两棵⼦树，即查找结果只需要找其中的⼀半数据记录即可，等于⼯作量少了⼀半，然后继续折半查找，效率⾼。

根据⼆叉树的性质，具有n个结点的完全⼆叉树的深度为[log2n]+1。

尽管折半查找判定⼆叉树并不是完全⼆叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为[log2n]+1，最好的情况是1次。

时间复杂度为O(log2n)； 折半计算mid的公式 mid = (low+high)/2;if(a[mid]==value)return mid;if(a[mid]>value)high = mid-1;if(a[mid]<value)low = mid+1; 折半查找判定数中的结点都是查找成功的情况，将每个结点的空指针指向⼀个实际上不存在的结点——外结点，所有外界点都是查找不成功的情况，如图所⽰。

Java常见的七种查找算法1. 基本查找也叫做顺序查找，说明：顺序查找适合于存储结构为数组或者链表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。

从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。

示例代码：public class A01_BasicSearchDemo1 {public static void main(String[] args){//基本查找/顺序查找//核心：//从0索引开始挨个往后查找//需求：定义一个方法利用基本查找，查询某个元素是否存在//数据如下：{131, 127, 147, 81, 103, 23, 7, 79}int[] arr ={131,127,147,81,103,23,7,79};int number =82;System.out.println(basicSearch(arr, number));}//参数：//一：数组//二：要查找的元素//返回值：//元素是否存在public static boolean basicSearch(int[] arr,int number){//利用基本查找来查找number在数组中是否存在for(int i =0; i < arr.length; i++){if(arr[i]== number){return true;}}return false;}}2. 二分查找也叫做折半查找，说明：元素必须是有序的，从小到大，或者从大到小都是可以的。

如果是无序的，也可以先进行排序。

但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。

基本思想：也称为是折半查找，属于有序查找算法。

用给定值先与中间结点比较。

比较完之后有三种情况：•相等说明找到了•要查找的数据比中间节点小说明要查找的数字在中间节点左边•要查找的数据比中间节点大说明要查找的数字在中间节点右边代码示例：package com.itheima.search;public class A02_BinarySearchDemo1 {public static void main(String[] args){//二分查找/折半查找//核心：//每次排除一半的查找范围//需求：定义一个方法利用二分查找，查询某个元素在数组中的索引//数据如下：{7, 23, 79, 81, 103, 127, 131, 147}int[] arr ={7,23,79,81,103,127,131,147};System.out.println(binarySearch(arr,150));}public static int binarySearch(int[] arr,int number){//1.定义两个变量记录要查找的范围int min =0;int max = arr.length-1;//2.利用循环不断的去找要查找的数据while(true){if(min > max){return-1;}//3.找到min和max的中间位置int mid =(min + max)/2;//4.拿着mid指向的元素跟要查找的元素进行比较if(arr[mid]> number){//4.1 number在mid的左边//min不变，max = mid - 1；max = mid -1;}else if(arr[mid]< number){//4.2 number在mid的右边//max不变，min = mid + 1;min = mid +1;}else{//4.3 number跟mid指向的元素一样//找到了return mid;}}}}3. 插值查找在介绍插值查找之前，先考虑一个问题：为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？二分查找中查找点计算如下：mid=(low+high)/2, 即mid=low+1/2*(high-low);我们可以将查找的点改进为如下：mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，这样，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

形考作业四及答案（本部分作业覆盖教材第8-9章的内容）一、单项选择题1、顺序查找方法适合于存储结构为（）的线性表。

A．散列存储B．索引存储C．散列存储或索引存储D．顺序存储或链接存储2、对线性表进行二分查找时，要求线性表必须（）。

A．以顺序存储方式B．以链接存储方式C．以顺序存储方式，且数据元素有序D．以链接存储方式，且数据元素有序3、对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（）。

A．以顺序存储方式B．以链接存储方式C．以索引存储方式D．以散列存储方式4、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

A．n B．n/2C．(n+1)/2 D．(n-1)/25、哈希函数有一个共同的性质，即函数值应当以（）取其值域的每个值。

A．最大概率B．最小概率C．平均概率D．同等概率6、有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

A．29/10 B．31/10 C．26/10 D．29/97、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。

A．3 B．4 C．5 D．68、顺序查找法与二分查找法对存储结构的要求是（）。

A．顺序查找与二分查找均只是适用于顺序表B．顺序查找与二分查找均既适用于顺序表，也适用于链表C．顺序查找只是适用于顺序表D．二分查找适用于顺序表9、有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

A．45,24,53,12,37,96,30 B．37,24,12,30,53,45,96C．12,24,30,37,45,53,96 D．30,24,12,37,45,96,5310、对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标可能为（）。

算法设计与分析各种查找算法的性能测试目录摘要 (2)第一章：简介（Introduction） (3)1.1 算法背景 (3)第二章：算法定义（Algorithm Specification） (4)2.1 数据结构 (4)2.2顺序查找法的伪代码 (4)2.3 二分查找（递归）法的伪代码 (5)2.4 二分查找（非递归）法的伪代码 (6)第三章：测试结果（Testing Results） (8)3.1 测试案例表 (8)3.2 散点图 (9)第四章：分析和讨论 (11)4.1 顺序查找 (11)4.1.1 基本原理 (11)4.2.2 时间复杂度分析 (11)4.2.3优缺点 (11)4.2.4该进的方法 (12)4.2 二分查找（递归与非递归） (12)4.2.1 基本原理 (12)4.2.2 时间复杂度分析 (13)4.2.3优缺点 (13)4.2.4 改进的方法 (13)附录：源代码（基于C语言的） (15)摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。

查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。

我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。

比较的指标为关键字的查找次数。

经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。

这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。

关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction）1.1 算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。

对于查找问题来说，没有一种算法在任何情况下是都是最优的。

有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。

吉首大学硕士研究生入学考试自命题考试大纲考试科目代码：[827]一、考试形式与试卷结考试科目名称：计算机学科专业基础（自命题）构1)试卷成绩及考试时间：本试卷满分为150分，考试时间为180分钟。

2)答题方式：闭卷、笔试3)试卷内容结构a:客观题部分40%b:主观题部分60%4)题型结构a:单项选择题，10小题，每小题2分，共20分b:填空题，5空，每空2分，共10分c:程序填空题，10空，每空3分，共30分d:综合应用题，6小题，每小题10分，共60分e:编程题，2小题，每题15分，共30分二、考试内容与考试要求考试内容一、绪论1、掌握数据结构的基本概念2、了解抽象数据类型3、理解算法五个要素的确切含义4、掌握算法时间复杂度和空间复杂度的分析方法二、线性表1、理解线性表的逻辑结构特性2、掌握线性表顺序存储结构的基本操作及实现3、掌握线性表链式存储结构的基本操作及实现4、理解链表中的头结点、头指针和首元结点的区别5、理解循环链表、双向链表的特点6、能根据具体问题选择顺序或链式存储方式，掌握表的逆置、合并等操作的实现方法三、栈和队列1、理解栈和队列的基本概念2、掌握栈和队列的顺序存储结构的基本操作及实现3、理解栈和队列的链式存储结构的基本操作及实现4、了解栈和队列的应用四、串1、理解串的基本定义2、掌握串的定长顺序存储、堆分配存储和块链存储的表示及其实现方法3、掌握串的模式匹配算法五、数组和广义表1、掌握数组的地址计算方法2、了解稀疏矩阵的两种压缩存储方法的特点和适用范围3、了解广义表的结构特点及其存储方法六、树和二叉树1、理解树和森林的概念，包括树的定义、树的术语2、掌握二叉树的概念、性质及表示方法3、掌握二叉树的遍历算法，并且能灵活运用递归遍历方式实现二叉树的其他操作4、理解树的存储、树和森林与二叉树的转换方法5、掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算七、图1、掌握图的基本概念及相关术语和性质2、掌握图的邻接矩阵和邻接表表示法3、掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法4、掌握构造最小生成树的两种算法及拓扑排序算法的思想5、掌握迪杰斯特拉算法和弗洛伊德算法八、查找1、理解查找在数据处理中的重要性，掌握查找表的相关概念2、掌握线性表的查找方法，能根据问题选择顺序查找、折半查找及分块查找方法求解3、掌握树表的查找方法，能构造二叉排序树，并将其调整为平衡二叉树4、理解散列表的基本概念，了解常用的散列函数构造方法和冲突解决办法九、排序1、掌握排序的基本概念，了解排序方法的分类2、理解插入排序、交换排序、选择排序、归并排序及基数排序的基本思想3、掌握直接插入排序、冒泡排序、简单选择排序的实现方法十、分治法1、掌握分治法的基本思想2、掌握归并排序、快速排序、折半查找、二叉树遍历、大整数乘法和矩阵相乘、棋盘覆盖等问题的分治设计方法3、了解排序问题的复杂性下限十一、回溯法1、掌握回溯法的基本思想2、掌握N皇后、最优装载、图的着色、0/1背包等问题的回溯法设计方法3、掌握剪枝函数的设计，能准确分析回溯法的效率十二、动态规划法1、掌握动态规划的主要思想和基本要素2、掌握矩阵连乘、最优二叉查找树、最长公共子序列、图像压缩、电路布线等问题的动态规划设计方法3、了解自顶向下的动态规划方法设计策略十三、贪心法1、掌握贪心算法的主要思想和基本要素2、掌握最小代价生成树、单起点最短路路径、自由前缀码编码等问题的贪心算法策略3、了解数据结构在程序效率分析的重要性考试要求1、掌握数据结构的基本概念、基本原理和基本方法。