数据结构查找与排序.ppt

第一部分 查找 二分查找,Hash表 二分查找考点 条件：顺序存储,按关键字有序 时间复杂度分析（log2n） 最多要比较的次数（?㏒2n? +1 ）,理由：n个结点的判定树的深度与n个结点的完全二叉树深度相同。 折半查找的二叉判定树 Hash查找和Hash表的创建 常用Hash函数和解决冲突方法 Hash表的创建与平均查找长度的计算 时间复杂度的分析（不依赖问题的规模,与解决冲突的方法以及hash表的装填因子有关） 第二部分 排序 各种排序算法的特性 时间性能（最好、最坏、平均情况） 空间复杂度 稳定性 三、基于交换的排序 冒泡排序（Bubble Sort） 快速排序（Quick Sort） 快速排序的平均性能为O(n·log2n),在同数量级算法中综合考虑,是最好的一种内部排序方法 快速排序算法在最坏情况下（待排序列正序或逆序）,每次划分只得到比上一次少 一个记录的子序列,另一个子序列却为空,即划分得极不均匀,此时需要执行n-1次递归调用,且比较的次数是n(n-1)/2, 所以快速排序收到序列初始状态的影响,在最坏情况下算法时间复杂度为O(n2) 算法分析 直接插入排序 在一个已有序的序列中，将待排序的元素关键字逐个与该有序序列中的元素的相应关键字作比较，确定该元素在序列中的正确位置，然后在该位置插入这个元素，形成一个新的有序序列。 归并排序思想 ① 初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列； ② 对所有有序子序列进行两两归并，得到?n/2?个长度为2或1的有序子序列——一趟归并； ③ 重复② ，直到得到长度为n的有序序列为止。 以上方法由于每次进行两两归并，因此称为2-路归并排序 Shell排序的思想： 1）每一趟排序设定一个步长，每次对序列中间隔这个步长的元素子序列进行直接插入排序 2）每一趟排序完之后，在下一趟的排序中，缩短步长再次进行排序，直至排完 * 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.试画出对其进行折半有哪些信誉好的足球投注网站时的判定树,并计算有哪些信誉好的足球投注网站成功的平均有哪些信誉好的足球投注网站长度。 例如 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,…）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找长度。 4 7 2 2 1 6 5 1 查找时比较次数 3 6 1 1 0 5 4 0 冲突次数 49 71 38 15 4 27 60 33 关键字 10 9 8 7 6 5 4 3 2 1 0 位置 查找成功的平均查找长度=（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 1 1 1 1 1 2 1 4 1 2 查找时比较次数 0 0 0 0 0 1 0 3 0 1 冲突次数 19 98 17 46 75 63 53 49 61 79 关键字 109 108 107 106 105 104 103 102 101 100 位置 查找成功时的平均有哪些信誉好的足球投注网站长度：（2 + 1 + 4 + 1+ 2