2、 算法题重视考查算法原理和设计思维
学习算法与程序设计不仅要会套用经典算法的程序框架来解决实际问题,更要在深入理解算法原理的基础上,逐渐形成基于既有算法改造之上的算法设计能力。加试部分的算法与程序设计题,充分体现了这种价值取向。
如2015年10月的第16题,要求考生在理解传统冒泡排序算法基础上,根据试题提示分析原算法中存在的冗余处理,并按照改进后的算法要求改正程序中的错误。核心部分的程序段如下:
本题考查的主要特点为:
理解冒泡排序算法的原理
冒泡排序的基本原理是每次在一个未处理区间内扫描,发现逆序对数据后即进行互换,逐渐缩小扫描区间直到区间长度为2。该算法的改进原理就是当剩余区间内数据没有发现逆序对时,即可停止排序。如果考生对原冒泡排序算法的原理理解不够深刻,就无法设计出相应的循环条件并完成改错。
理解冒泡排序程序外循环循环变量的作用原理
教材中冒泡排序算法用For i=1 to n-1语句来控制外循环,循环变量i的主要作用有两个,一是冒泡排序加工的遍数,二是为每遍的加工设定左边界。如果考生未能对这些原理有深刻的理解,就无法理解外循环变量i的作用,也就不能正确分析出Do While循环语句中的条件进而正确写出改正后的结果(将标记(1)处的“or”改为“and”、将标记(2)处的“i”改为“i-1”)。
再如2016年4月第11、12题,2017年4月第11题,2017年4月第12题。这些试题首先需要运用已学经典算法的原理去理解新的程序,更要基于新的问题去创造性地设计算法解决问题。以2017年4月的第12题为例,试题要求考生运用已学的选择排序算法思想,完善改进后的在两端同时进行选择的排序程序。该题的主要内容如下:
该题的考查特点有:
运用内化的选择排序思想理解新的选择排序算法
本题可以说是考查选择排序算法,但又不局限于考查教材中的选择排序算法,而是需要运用内化的选择排序中的“选择”思想,去帮助理解改进后的新排序算法。
根据新问题特点去创造性地设计算法
改进后的选择排序算法带来了新的问题,即两端同时进行选择时所带来的数据交换的相互影响。为了解决这个新问题,需要考生能根据问题特点去完善算法(设计思维)。新问题只有在左端点是最大值时产生,顺藤摸瓜进行分析,当最小值被交换到左端点时,最大值被交换到iMin所指位置,所以正确选项为A。