数据结构c语言版复习提纲及重点.pptVIP

* 例题 设哈希函数H(key)＝key % 9，哈希地址空间为0 ~10，对关键字序列（31，12，48，54，21，33，22，60）。 （1）用线性探查法解决冲突构造哈希表，并计算在等概率情况下查找成功和不成功的平均查找长度（写出算式）； 12 21 33 22 1 2 3 4 5 6 7 8 60 9 10 54 0 31 48 解： ASL成功= (1+1+3+1+4+2+5+4) / 8 = 21/8 ASL不成功= (2+1+1+8+7+6+5+4+3) / 9 = 37/9 * 例题 设哈希函数H(key)＝key % 9，哈希地址空间为0 ~10，对关键字序列（31，12，48，54，21，33，22，60）。 （2）用拉链法解决冲突构造哈希表，并计算在等概率情况下查找成功和不成功的平均查找长度。 ^ ^ ^ ^ ^ 1 2 3 4 5 6 7 8 ^ ^ 9 10 0 解： ASL成功= (1+1+1+1+2+2+2+3) / 8= 13/8 31 12 48 54 ^ 21 ^ 33 22 ^ 60 ^ ASL不成功= (1+3+2+2) / 9= 8/9 * 第十章 内部排序 本章内容： 10.1 概述 10.2 插入排序 10.1.1 直接插入排序 10.1.2 其他插入排序 10.1.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.2 树型选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的比较 * 第十章 排序 本章学习要点： 了解各种排序方法的过程和特点。能从”关键字间的比较次数”分析排序算法在最坏情况和平均情况时的时间性能。 按平均时间复杂度划分，内部排序可分为：O(n2)的简单排序方法，O(nlogn)的高效排序方法和O(d*n)的基数排序方法。 理解排序方法”稳定”或”不稳定”的含义。 掌握简单的排序方法（直接插入排序、冒泡排序、简单选择排序）。 掌握快速排序算法，理解堆排序、归并排序算法。 * 例题 1. 排序方法的稳定性是指（ ）。 2. 对于直接插入排序, 当待排序列中记录按关键字（ 有序 ）排列时, 所需进行关键字间比较的次数达最小值n-1, 记录不需移动。 3. 每趟排序都是从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为（直接插入）排序法。 4. 直接插入排序用监视哨的作用是（）。 * 例题 1. 在希尔排序、冒泡排序、选择排序、直接插入排序、快速排序、基数排序等方法中，关键字比较的次数与记录的初始排列次序无关的排序方法是（选择排序、基数排序）。 2. 设有序列（503，87，512，61，908，170，897） （1）写出增量为3时进行一趟希尔排序的结果； （2）建成一个小顶堆； （3）给出执行一趟快速排序的结果； （4）写出进行3路归并排序的过程。 * 例题 8. 设有序列（503，87，512，61，908，170，897） （1）写出增量为3时进行一趟希尔排序的结果； 503，87，512，61，908，170，897 503 61 897 87 908 512 170 61 , 87, 170 , 503, 908, 512, 897 例题 6. 设有序列（503，87，512，61，908，170，897） （2）建成一个小顶堆； 503 512 87 908 61 897 170 (a) 503 170 87 908 61 897 512 (b) 503 170 61 908 87 897 512 (c) 61 170 503 908 87 897 512 (d) 61 170 87 908 503 897 512 (e) 例题 6. 设有序列（503，87，512，61，908，170，897） （3）给出执行一趟快速排序的结果； 503，87，512，61，908，170，897 170，87，61，503，908，512，897 （4）3路归并排序过程； 503，87，512，61，908，170，89