选择性必修一 第五章 数据结构的应用-普通高中春招考试备考教材 信息技术（第六版）

16. 有一棵二叉树，先序遍历序列为 ABDGCEF，中序遍历序列为 DGBAECF，请画出该二 叉树，并写出后序遍历序列。 17. 建立一棵二叉树的示意图，使其中序遍历的结果为 a*b+c/d。 18. 把一个算术表达式表示成一棵二叉树：运算符作为根节点，运算符的前后两个运算 对象分别作为根的左、右两棵子树。请你写出图中二叉树所表示的算术表达式。 第五章　数据结构的应用 一、迭代与递归 1.迭代 迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程 的重复称为一次迭代，而每一次迭代得到的结果会作为下一次迭代的初始值。 【例】s=1+2+3+…+100 在 Python 中的程序段为： s=0 for i in range（101）： 　 s=s+1 86 选择性必修一　数据与数据结构　 print（s） 在这个程序段中，s 就是一个迭代变量，整个过程就是一个迭代过程。 用迭代法解决问题的步骤： ①确定迭代变量。 ②建立迭代关系式。 ③过程控制（不能无休止重复执行，必须有迭代结束条件）。 2.递归 若一个对象直接或间接调用它自己，则称这个对象是递归的，其过程称为递归过程。 【例】求 n！。 def fib（n）： 　　if n==1： 　　　　return 1 　　else： 　　　　return n*fib（n-1） 　　s=0 　　for i in range（101）： 　　　　s=s+i 　　print（s） 二、排序 1.排序的分类 看相同键值在排序过程中的相对位置是否发生变化，排序可分为稳定排序和非稳定 排序。 看是否一次进入内存排序，排序可分为内部排序和外部排序。内部排序：冒泡法排序、 插入排序、选择排序、交换排序、归并排序和基数排序。外部排序主要是针对大量数据。 2.常用的排序方法 常用的排序方法有冒泡排序法和快速排序法。 （1）冒泡排序法 冒泡排序法的思想如下： ①假设待排序元素有 n 个，从第一个元素开始，依次交换相邻的两个逆序元素，直到最 后一个元素为止，当第一趟排序结束，就会将最大（小）的元素移动到序列的末尾。 ②然后按照以上方法进行第二趟排序，次大（小）的元素将会被移动到序列的倒数第二 个位置。 ③依次类推，经过 n-1 趟排序后，整个元素序列就成了一个有序（升序或降序）的序列。 每趟排序过程中，值小（大）的元素向前移动，值大（小）的元素向后移动，就像气泡一样 87 向上升，因此将这种排序方法称为冒泡排序。 （2）快速排序法 快速排序采用分治法的策略：将原问题划分成规模更小但与原问题相似的小问题，然后 用递归法解决这些小问题，最后将它们组合形成原问题的解。 其基本思想如下： ①从待排序元素序列中选取一个元素（通常是第一个元素）作为基准元素，其关键字设 为 key，然后将其余关键字小于 key 的元素移至 key 前面，而将关键字大于 key 的元素移至 key 后面，实现将待排序元素序列分为两个子表，最后将关键字 key 的元素插入其分界线的位置 上，这个过程称为一趟快速排序。 ②通过这一趟划分后，以关键字 key 的元素为界，待排序列被分为两个子表，且前面子表 中所有元素的关键字均不大于 key，而后面子表中所有元素的关键字均大于 key。 ③继续对分割后的子表按上述原则进行划分，直到所有子表的表长不超过 1 为止，此时 的元素序列就成了一个有序序列。 三、查找 　 ● 顺序查找：适合在一个有限数据集合中查找数据，无论这个数据集合的元素是否有 序，只需要将待查找的数据与该数据集合中的每一个元素逐一比较即可。 　 ● 二分查找：也叫折半查找，实现这一查找的前提是待查数据集合的元素必须是依照特 定顺序排列的。 四、算法与数据结构的关系与区别 1.算法与数据结构的关系 算法+数据结构=程序，算法与数据结构密切相关，数据结构是算法实现的基础，数据结 构直接影响算法的设计和运行效率，算法操作对象是数据，它必须依赖于具体的数据结构来 实现。 2.算法与数据结构的区别 数据结构关注的是数据的逻辑结构和存储结构，也就是数据表示，而算法关注的是如何 在数据结构的基础上解决实际问题，是对数据运算的描述，也就是数据处理，即设计解决方 法和处理数据。算法是编程思想，而数据结构则是这些思想的逻辑基础。 随堂练习 一、单项选择题 1. 小明和小华玩猜数字的游戏，所猜数字不超过 800，小明首先猜 400，小华说大了，小明 又猜 200，小华再次说大了，小明猜 100，小华说小了，小明猜 150……以此类推，直到猜到正 88 选择性必修一　数据与数据结构　 确的数字。上述内容的算法思想是（　　）。 A. 穷举算法 B. 递归算法 C. 二分查找法 D. 顺序查找法 2.（　　）是重复反馈过程的活动，其目的通常是逼近所需目标或结果，（　　）是直接或 间接地调用函数自身。 A. 枚举　递归 B. 递归　迭代 C. 迭代　递归 D. 递归　枚举 3. 如图所示的程序，用 Python 生成斐波那契数列，采 用的是（　　）算法。 A. 迭代 B. 递归 C. 累加 D. 循环 4. 下列关于迭代法的相关说法，不正确的是（　　）。 A. 在使用迭代法解决的问题中，一定存在一个迭代变量 B. 建立迭代关系式通常可以使用顺推或者倒推的方法来完成 C. 迭代过程不能无休止地重复执行下去 D. 对于迭代次数无法预先确定的情况下，就不能使用循环结构来解决问题 5. 在 Python 语言中，使用递归法求 n！（n 的阶乘），其结束条件是（　　）。 A.n>1 B.n<1 C.n=1 D.n==1 6. 下列关于查找的说法，正确的是（　　）。 A. 顺序查找要求各元素必须有序排列 B. 顺序查找比二分法查找效率高 C. 在任何情况下，顺序查找比二分查找的查找次数要多 D. 进行二分查找时，被查找的数据可以是升序排列的，也可以是降序排列的 7. 有这样一个元素序列：2、4、5、9、12、16、20、35、48、57。要在这个序列中查找元素 20， 采用二分法查找，需要查找的次数是（　　）。 A.1 B.2 C.3 D.4 8. 对有序数组（5、13、19、21、37、56、64、75、88、92、100）进行二分查找，成功查找元素 19 的查找长度（比较次数）是（　　）次。 A.1 B.2 C.3 D.4 9. 用冒泡排序对 4、5、6、3、2、1 进行从小到大排序，第三趟排序后的状态为（　　）。 A.4 5 3 2 1 6 B.4 3 2 1 5 6 C.3 2 1 4 5 6 D.2 1 3 4 5 6 10. 假定对元素序列（7、3、5、9、1、12、8、15）进行快速排序（升序排序），则进行第一次划 分后，得到的左区间中元素的个数为（　　）个。 A.2 B.3 C.4 D.5 89 11. 若递归模型为 f（1）=1，f（n）=f（n-1）+n （n>1），则递归出口（递归终结条件）是（　　）。 A.f（1） B.f（n） C.f（1）=1 D.f（n）=n 二、判断题 12. 链表排序一定比数组快。 （　　） 13. 利用快速排序法对 n 个元素排序，要经过 n-1 趟排序。 （　　） 14. 当数据量较大时，二分查找会比顺序查找快很多。 （　　） 15. 快速排序是一种递归算法。 （　　） 三、填空题 16. 重复执行一系列运算步骤，从前面的量依次求出后面的量的过程称为　　　　。 17. 二分查找算法利用的算法思想是　　　　。 18.　　　　是平均排序次数最少的排序算法之一，也是目前平均速度最快的排序，特 别适合数据量较多的排序。 四、应用题 19. 有一组数据元素序列（7、15、23、5、18、39、45、31、10、2），现将其按从小到大的顺序 排序。 （1）用冒泡法排序，写出每一趟排序的结果。 （2）用快速排序法排序，写出每一次交换后的结果。 90 第五章 数据结构的应用 五、随堂练习 （一）选择题 1-5CCBDD 6-10 DDBCC 11 C （二）判断题 12-15✖✖✔✔ （三）填空题 16.迭代 17.递归 18.s快速排序 （四）简答题 19. （1）第一趟排序：7 15 5 18 23 39 31 10 2 45 第二趟排序：7 5 15 18 23 31 10 2 39 45 第三趟排序：5 7 15 18 23 10 2 31 39 45 第四趟排序：5 7 15 18 10 2 23 31 39 45 第五趟排序：5 7 15 10 2 18 23 31 39 45 第六趟排序：5 7 10 2 15 18 23 31 39 45 第七趟排序：5 7 2 10 15 18 23 31 39 45 第八趟排序：5 2 7 10 15 18 23 31 39 45 第九趟排序：2 5 7 10 15 18 23 31 39 45 （2） ｛2 5｝7｛23 18 39 45 31 10 15｝ 2｛5｝7｛15 18 10｝23｛31 45 39｝ 2 5 7 ｛10｝15｛18｝23 31 ｛45 39｝ 2 5 7 10 15 18 23 31 39 45 学科网（北京）股份有限公司 $$