第4章数据结构基础_3(习题课)

1、章节名称第4章数据结构基础 4.5查找与排序的基本策略（习题课）教学目的与要求 掌握查找的基本概念和查找的常用方法;掌握排序的基本概念和常用的排序方法。教学内容(1)查找的基本策略(2)排序的基本策略重点(1)掌握查找的基本策略(2)掌握排序的基本策略难点各种排序算法的基本思想作业P110 一、填空题：6 二、选择题：13教学手段ppt电子课件、板书、课堂练习、问答教学过程（组织与方法）回顾上次课内容介绍本次课重点、难点 讲解本次课内容(ppt+板书举例)小结作业课堂练习第 7 次课教案第4章 算法与数据结构n4.5 查找与排序的基本策略n习题课n本次课重点：(1)掌握查找的基本策略(2)掌握

2、排序的基本策略n本次课难点：各种排序算法的基本思想本次课说明：4.5.1 查找1.查找的定义n检索，即根据给定的值在一组数据中寻找其数值等于给定值的数据元素，若存在这样的数据元素说明查找成功，否则查找不成功。2.查找的基本策略n顺序查找、二分查找n顺序查找的平均查找长度是（n+1）/24.5 排序与查找基本策略n二分查找n要求：线性表是有序表；以顺序存储方式n最坏情况下的查找长度不超过log2n 4.5 排序与查找基本策略例如当给定的k值为21时，二分查找的过程：4.5 排序与查找基本策略4.5.2 排序1.排序的定义2.排序的基本策略（1）简单选择排序法选择排序法的基本思想是：扫描整个序列，

3、从中选出最小的元素，将它交换到序列的最前面；然后对剩下的序列采用同样的方法，直到序列中只剩一个元素为止。 4.5 排序与查找基本策略简单选择排序法在最坏情况下需要比较n(n-1)/2次。 8 4 3 6 9 2 7 2 4 3 6 9 8 7 2 3 4 6 9 8 7 2 3 4 6 9 8 7 2 3 4 6 9 8 7 2 3 4 6 7 8 9 2 3 4 6 7 8 9原数据：第1遍第2遍第3遍第4遍第5遍第6遍4.5 排序与查找基本策略（2）交换排序法所谓交换排序是指借助数据元素之间的互相交换进行排序的一种方法。最简单的交换排序方法是冒泡排序法，它和气泡从水中往上冒的情况有些类似。

4、设一组数据初始关键字值为：20 30 10 45 33 22 55 50 则第一趟冒泡的过程为： 4.5 排序与查找基本策略20 30 10 45 33 22 55 50 (20与30比较,未交换)20 10 30 45 33 22 55 50 (30与10比较,交换)20 10 30 45 33 22 55 50 (30与45比较,未交换)20 10 30 33 45 22 55 50 (45与33比较,未交换)20 10 30 33 22 45 55 50 (45与22比较,交换)20 10 30 33 22 45 55 50 (45与55比较,未交换)20 10 30 33 22 45

5、50 55 (55与50比较,交换) 冒泡排序法在最坏情况下需要比较n(n-1)/2次。4.5 排序与查找基本策略（3）插入排序法 类似玩牌时整理手中纸牌的过程。 插入排序：将一个待排序的元素按其数值的大小插到前面已经排序的序列中的适当位置，直到全部元素插入完毕为止。 插入排序最坏情况下需要比较n(n-1)/2次。 4.5 排序与查找基本策略46 58 15 45 90 18 10 6246 58 15 45 90 18 10 6215 46 58 45 90 18 10 6215 45 46 58 90 18 10 6215 45 46 58 90 18 10 6215 18 45 46 5

6、8 90 10 6210 15 18 45 46 58 90 6210 15 18 45 46 58 62 9046 58 15 45 90 18 10 62i=1i=2i=3i=4i=5i=6i=7i=8小结1.掌握基本排序方法的思想2.掌握基本排序方法的时间复杂度作业P110一.填空题：6二.选择题：13习题课前期作业中的问题基本概念不清晰进制转换规则不熟练课堂练习一、选择题：1.链表不具有的特点是A) 不必事先估计存储空间B) 可随机访问任一元素C) 插入删除不需要移动元素D) 所需空间与线性表长度成正比2.算法的时间复杂度是指A) 执行算法程序所需要的时间B) 算法程序的长度C) 算法

7、执行过程中所需要的基本运算次数D) 算法程序中的指令条数3. 数据的存储结构是指_。A) 存储在外存中的数据B) 数据所占的存储空间量C) 数据在计算机中的顺序存储方式D) 数据的逻辑结构在计算机中的表示4.下列关于栈的描述中错误的是_。A) 栈是先进后出的线性表B) 栈只能顺序存储C) 栈具有记忆作用D) 对栈的插入与删除操作中，不需要改变栈底指针5.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_。A)冒泡排序为n/2 B)冒泡排序为nC)快速排序为n D)快速排序为n(n-1)/26.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。A)log2n B)n/2 C)n D)n+17.下列对于线性链表的描述中正确的是_。A)存储空间不一定是连续，且各元素的存储顺序是任意的B)存储空间不一定是连续，且前件元素一定存储在后件元素的前面C)存储空间必须连续，且前件元素一定存储在后件元素的前面D)存储空间必须连续，且各元素的存储顺序是任意的二.填空题：1.对长度为10的线性表进行冒泡