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