数据结构查找与排序.ppt

第一部分 查找 二分查找,Hash表 二分查找考点 条件：顺序存储,按关键字有序 时间复杂度分析（log2n） 最多要比较的次数（2n +1 ）,理由：n个结点的判定树的深 度与n个结点的完全二叉树深度相同。 折半查找的二叉判定树 1、请问,满足什么条件的顺序表可以实施二分查找,在满足该条件的n个 记录的顺序表中进行二分查找,最大的比较次数是多少？ 答：数据元素初始状态按关键字有序 最大比较次数应为2n +1 2、设顺序表为4, 6, 12, 38, 40, 67, 80用二分法查找72,需要进行的比较次数为（ ） A、3 B、n-1 C、n+1 D、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、不直接依赖于N D、上述三者都不是 答案：C 2、已知待散列存储的关键字序列为（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.5 3、已知关键码 集合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.堆排序（Heap Sort ） 算法关键部分： for (i=1; i 31 44 3135 0，O(N4/3