数据结构查找与排序

《数据结构查找与排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一部分查找二分查找,Hash表二分查找考点条件：顺序存储,按关键字有序时间复杂度分析（log2n）最多要比较的次数（㏒2n+1）,理由：n个结点的判定树的深度与n个结点的完全二叉树深度相同。折半查找的二叉判定树1、请问,满足什么条件的顺序表可以实施二分查找,在满足该条件的n个记录的顺序表中进行二分查找,最大的比较次数是多少？答：数据元素初始状态按关键字有序最大比较次数应为㏒2n+12、设顺序表为{4,6,12,38,40,67,80}用二分法查找72,需要进行的比较次数为（）A、3B、n-1C、n+1D、n答案：A例如：3、试用于

2、折半查找的表的存储方式及元素排列要求是顺序存储,按关键字有序。4、对有10个元素的有序表,采用二分查找,需要比较4次方可找到的元素个数为3。5、设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908.试画出对其进行折半搜索时的判定树,并计算搜索成功的平均搜索长度。Hash查找和Hash表的创建常用Hash函数和解决冲突方法Hash表的创建与平均查找长度的计算时间复杂度的分析（不依赖问题的规模,与解决冲突的方法以及hash表的装填因子有关）例如1、对包含N个元素

3、的散列表进行检索,平均检索长度是（）A、O(log2N)B、O(N)C、不直接依赖于ND、上述三者都不是答案：C2、已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71）,哈希函数为H（key）=keyMOD11,哈希表HT的长度为11,采用二次探测再散列法（d=12,-12,22,-22,32,…）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找长度。位置012345678910关键字336027415387149冲突次数04501163查找时比较次数15612274查找成功的平均查找长度=（1+5+

4、6+1+2+2+7+4）/8=28/8=3.53、已知关键码集合{53,17,19,61,98,75,79,63,46,49}要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内,若发生冲突则用开地址法的线索探测法解决,要求写出的选用的散列函数,形成的散列表：计算查找成功的平均搜索长度。（设等概率情况）答：选用的散列函数为：H(K)=100+K%10位置100101102103104105106107108109关键字79614953637546179819冲突次数1030100000查找时

5、比较次数2141211111查找成功时的平均搜索长度：（2+1+4+1+2+1+1+1+1+1）/10=1.5第二部分排序各种排序算法的特性时间性能（最好、最坏、平均情况）空间复杂度稳定性常见排序算法堆排序-堆的定义,创建堆,堆排序（厦大3次,南航2次,南大3次）快速排序基数排序插入排序希尔排序冒泡排序简单选择排序归并排序一、基于选择的排序简单选择排序堆排序（HeapSort）算法关键部分：for(i=1;i

6、键字最小的记录所在位置if(min!=i)交换A[i]与A[min]；}1.简单选择排序算法思想：每一趟从当前待排序的记录中选择关键字最大（小）的记录,然后与末尾（首）记录进行交换稳定性：不稳定。反例如下：221122不稳定！排序前2领先于22落后于2排序后简单选择排序算法性能整个算法是二重循环：外循环控制排序的趟数,对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。进行第i趟排序时,关键字的比较次数为n-i,则：比较次数：∑(n-i)=n-1i=1n(n-1)2与数据的初始状态无关时间复杂度是：T(n)=O(n2)空间复杂

7、度是：S(n)=O(1)堆排序的算法思想：Step1：（初始建堆）把待排序元素保存在数组的1至n位置上,把这个元素集合（不包括位置0）做成一个最大堆Step2：交换堆顶元素与当前集合的最后一个元素,然后把堆的范围看做1至n-1（即这时候堆的最后一个元素为n-1,而非n）进行“筛选”,再构造成一个最大堆Step3：重复Step2,直至堆的大小为1,排序完成堆是一棵完全二叉树,它的每一个结点满足：若其有孩子,则该结点的值大于（或小于）孩子的值。若每一个结点大于孩子结点,则称为最大堆（大顶堆）,反之称为最小堆（小顶堆）。堆(Heap)取出根

8、结点（最大值）元素,与最后一个位置的元素交换。58443525[1][2][3][4]31[5]为了保持完全二叉树的结构特性,移去的是该结点。把31移至根31找出31的较大的