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

第4章 算法与数据结构 4.5 查找与排序的基本策略 习题课 本次课重点： (1)掌握查找的基本策略 (2)掌握排序的基本策略 本次课难点： 各种排序算法的基本思想 4.5.1 查找 1.查找的定义 检索，即根据给定的值在一组数据中寻找其数值等于给定值的数据元素，若存在这样的数据元素说明查找成功，否则查找不成功。 2.查找的基本策略 顺序查找、二分查找 顺序查找的平均查找长度是（n+1）/2 二分查找 要求：①线性表是有序表；②以顺序存储方式 最坏情况下的查找长度不超过log2n 4.5 排序与查找基本策略 4.5.2 排序 1.排序的定义 2.排序的基本策略 （1）简单选择排序法 选择排序法的基本思想是：扫描整个序列，从中选出最小的元素，将它交换到序列的最前面；然后对剩下的序列采用同样的方法，直到序列中只剩一个元素为止。 4.5 排序与查找基本策略 简单选择排序法在最坏情况下需要比较n(n-1)/2次。 4.5 排序与查找基本策略 （2）交换排序法 所谓交换排序是指借助数据元素之间的互相交换进行排序的一种方法。最简单的交换排序方法是冒泡排序法，它和气泡从水中往上冒的情况有些类似。 设一组数据初始关键字值为： 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 50 55 (55与50比较,交换) 冒泡排序法在最坏情况下需要比较n(n-1)/2次。 4.5 排序与查找基本策略 （3）插入排序法 类似玩牌时整理手中纸牌的过程。 插入排序：将一个待排序的元素按其数值的大小插到前面已经排序的序列中的适当位置，直到全部元素插入完毕为止。 插入排序最坏情况下需要比较n(n-1)/2次。 4.5 排序与查找基本策略 小结 1.掌握基本排序方法的思想 2.掌握基本排序方法的时间复杂度 作业 P110 一.填空题：6 二.选择题：13 习题课 前期作业中的问题 基本概念不清晰 进制转换规则不熟练 课堂练习 一、选择题： 1.链表不具有的特点是A) 不必事先估计存储空间B) 可随机访问任一元素C) 插入删除不需要移动元素D) 所需空间与线性表长度成正比 2.算法的时间复杂度是指A) 执行算法程序所需要的时间B) 算法程序的长度C) 算法执行过程中所需要的基本运算次数D) 算法程序中的指令条数 3. 数据的存储结构是指______。 A) 存储在外存中的数据 B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示 4.下列关于栈的描述中错误的是______。 A) 栈是先进后出的线性表 B) 栈只能顺序存储 C) 栈具有记忆作用 D) 对栈的插入与删除操作中，不需要改变栈底指针 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的线性表进行冒泡排序，最坏情况下需要比较的次数为________。 2.算法的基本特征是可行性、确定性、________ 和拥有足够的情报。 3.在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为_______。 4.某二叉树中度为2的结点有18个，则该二叉树中有 ________ 个叶子结点。 * * 回顾上次课内容→介绍本次课重点、难点→ 讲解本次课内容(ppt+板书举例)→小结→作业