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

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

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

3、.排序的定义 2.排序的基本策略 （1）简单选择排序法 选择排序法的基本思想是：扫描整个序列，从中选出最小 的元素，将它交换到序列的最前面；然后对剩下的序列采 用同样的方法，直到序列中只剩一个元素为止。 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

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

6、46 58 45 90 18 10 62 15 45 46 58 90 18 10 62 15 45 46 58 90 18 10 62 15 18 45 46 58 90 10 62 10 15 18 45 46 58 90 62 10 15 18 45 46 58 62 90 46 58 15 45 90 18 10 62 i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 小结 1.掌握基本排序方法的思想 2.掌握基本排序方法的时间复杂度 作业 P110 一.填空题：6 二.选择题：13 习题课 前期作业中的问题 基本概念不清晰 进制转换规则不熟练 课堂练习 一、选择题： 1

7、.链表不具有的特点是 A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比 2.算法的时间复杂度是指 A) 执行算法程序所需要的时间 B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数 3. 数据的存储结构是指_。 A) 存储在外存中的数据 B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示 4.下列关于栈的描述中错误的是_。 A) 栈是先进后出的线性表 B) 栈只能顺序存储 C) 栈具有记忆作用 D) 对栈的插入与删除操作中，不需要改变栈底

8、指针 5.对于长度为n的线性表，在最坏情况下，下列各排 序法所对应的比较次数中正确的是_。 A)冒泡排序为n/2 B)冒泡排序为n C)快速排序为n D)快速排序为n(n-1)/2 6.对长度为n的线性表进行顺序查找，在最坏情况下 所需要的比较次数为_。 A)log2n B)n/2 C)n D)n+1 7.下列对于线性链表的描述中正确的是_。 A)存储空间不一定是连续，且各元素的存储顺序是任意的 B)存储空间不一定是连续，且前件元素一定存储在后件元素的 前面 C)存储空间必须连续，且前件元素一定存储在后件元素的前面 D)存储空间必须连续，且各元素的存储顺序是任意的 二.填空题： 1.对长度为10的线性表进行冒