第一部分查找二分查找,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、试用于折半查找的表的存储方式及元素排列要求是顺序存储,按关键字有序。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个元素的散列表进行检索,平均检索长度是（）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+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查找时比较次数2141211111查找成功时的平均搜索长度：（2+1+4+1+2+1+1+1+1+1）/10=1.5第二部分排序•各种排序算法的特性–时间性能（最好、最坏、平均情况）–空间复杂度–稳定性•常见排序算法–堆排序-堆的定义,创建堆,堆排序（厦大3次,南航2次,南大3次）–快速排序–基数排序–插入排序–希尔排序–冒泡排序–简单选择排序–归并排序一、基于选择的排序1.简单选择排序2.堆排序（HeapSort）算法关键部分：for(i=1;i
31443135<313...
