第三单元算法的程序实现复习

第三单元 算法的程序实现 一、知识内容 （一）枚举算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。 枚举算法的基本思想是根据问题的本身性质，一一列举出该问题所有可能的情况，并根据题目的条件逐个作出判断，从中挑选出符合条件的解答。 枚举算法属于搜索策略，适用于那些解变量确定的连续值域的问题。设置枚举算法要列举出所有可能的情况，不能遗漏，也不能重复。 （二）解析算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。 解析算法的基本思想是用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过数学表达式的计算来实现问题的求解。 （三）排序算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。 1．冒泡排序 冒泡排序的基本思想是在待排序的数据中，先找到最小（大）的数据将它放到最前面，再从第二个数据开始，找到第二小（大）的数据将它放到第二个位置，以此类推，直到只剩下最后一个数据为止。 2．选择排序 选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。 （四）查找算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。 1．顺序查找 顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置；反之，查找不成功。 2．对分查找 对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，使查找成功，或直到子表不存在，查找不成功。 对分查找的条件是被查找的数据必须是有序的。 （五）递归算法 考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。 函数或过程调用它本身，称为递归。递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题 ，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的解。即采用“大事化小、小事化了”的基本思想。 采用递归算法的条件：（1）每一步骤解决问题的方法要一致；（2）有边界条件。 二、例题分析 1．有5位运动员100米成绩依次为13.8，12.5，13.0，13.2，13.4， 原始数据 13.8 12.5 13.0 13.2 13.4 第一趟 12.5 13.8 13.0 13.2 13.4 第二趟 第三趟 12.5 13.0 13.2 13.8 13.4 第四趟 12.5 13.0 13.2 13.4 13.8 若采用选择排序算法对其进行从小到大排序，则第二趟的排序结果是 (A) 12.5 13.8 13.2 13.4 13.0 (B) 12.5 13.4 13.2 13.8 13.0 (C) 12.5 13.0 13.8 13.2 13.4 (D) 12.5 13.2 13.8 13.4 13.0 参考答案：C 所考知识点：选择排序 选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。此题中要从小到 ... ...