2023-2024学年高中信息技术浙教版选修一 第二章 算法实例

第二章 算法实例 一、选择题 1．面额为1元、2元和5元的纸币共有10张，求总额恰好为32元取法方案的算法是：设1元取a张、2元取b张、5元取c张，a、b、c都取0到10之间的整数，将a、b、c取值的所有可能组合逐一代入表达式a+2b+5c=32，判断是否成立，若成立，则输出这一方案。此算法属于（    ）。 A．解析算法 B．枚举算法 C．递归算法 D．排序算法 2．使用枚举算法解决问题的最大优势是（  ） A．枚举算法设计直接、简单 B．枚举算法时间复杂度低 C．枚举算法空间复杂度低 D．枚举算法可以解决所有问题 3．二分查找又称折半查找，是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（   ） A．11  99  5  17  2  39 B．30  52  43  71  78  81 C．67  62  68  6   15   15 D．85  78  59  53  19  18 4．判断某自然数m是不是素数（只能被1或本身整除的大于1的自然数称为素数）的算法基本思想是：把m作为被除数，将2到m-1中的自然数作为除数，逐一进行相除，如果都除不尽，m就是素数，否则m就不是素数。这种判定素数的算法属于（    ）。 A．穷举算法 B．解析算法 C．递归算法 D．排序算法 5．在以下数组a中，采用对分查找思想查找数据"all"，则以下说法正确的是(    )。 a(1) a(2) a(3) a(4) a(5) a(6) a(7) all bro car due eve fre geo A．只需查找1次就能找到数据"all" B．第2次查找的范围是a(1)——a(4) C．查找过程中依次被访问到的数据是"due"、"bro"、"all" D．该数组中存放的都是字符型数据，无法使用对分查找 6．有数据序列为“2，6，8，3，5，9，7”，经过一轮冒泡排序后的结果是“2，3，6，8，5，7，9”，那么还需要（   ）轮冒泡排序后，数据才能完全有序。 A．2 B．3 C．4 D．5 7．采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（   ） A．O(log2n) B．O(n2) C．O(nlog2n) D．O(n) 8．下列问题中不适合使用枚举算法解决的是（   ） A．求全部两位数奇数。 B．求1000以内同时能被3和5整除的所有自然数的和 C．裴波那切函数 D．输入两个数，求最大公约数 9．下午两点（艳阳高照），王明带着一根3米长的竹竿和一个卷尺来到中心广场，今天他想测量一下广场上那个标志物的高度。当然，王明所带的卷尺不可能直接测量标志物的高度，但肯定足够丈量标志物的影子。现王明已经测得竹竿和标志物的影子长度，他想选择一个算法，编程计算标志物的高度。下列算法中，王明的最佳选择是_______。 A．枚举算法 B．递归算法 C．解析算法 D．查找算法 10．下列能用枚举算法求解的是（   ） A．将二进制数转换为十进制数 B．计算两个两位数的乘积 C．从100个U盘中找出存储容量最大的一个 D．求一个班同学的平均身高 11．二分查找又叫做折半查找，是一种应用于有序序列的高效查找算法。下列数列中适合二分查找算法的是（    ） A．11 99 44 55 3 99 45 B．43 71 78 8 55 12 46 C．85 74 59 53 19 18 11 D．10 15 25 20 65 75 55 12．有如下Visual Basic 程序段： s = 0 For i =　　1　　To 5 s =" s" + 3 Next i 该程序段运行后，变量s的值是（    ）。 A．10 B．15 C．20 D．25 13．有如下VB程序段 m=a(1) For i=2  to  100 If  a(i) > m  then  m=a(i) Next i 该程序段执行后，变量m中存储的是(    ) A．累加值 B．计数值 C．a(1)至a(100)中的最大值 D．最小值 14．某同学编写了以下Visual Basic 程序段，运行这段程序段，循环体的循环次数为：（   ） Dim x，y As Integer x=2 y=20 Do While  x<y x =x^2 Loop A．4 B．3 C．2 D．0 15．由于计算机运算速度快，我们可以一一列举x、y和z的所有可能值的算法叫（   ） A．枚举法 B．二分法 C．递归法 D．迭代法 16．已知在一直角三角形中，直角边a,b为整数，斜边C为不大于50的整数，输入直边a，输出所有满足条件的直角三角形三边a,b,c。解题思路为在斜边C的范围内，检验直角边b是否满足条件。这种算法是（     ） A．解析算法 B．枚举算法 C．查找算法 D．排序算法 17．我们在用计算机解决问题时，常采用递归法。已知：f(3)=3，当n>3时，f(n)=f(n-1)*n，编程求f(5)的值。下列结果正确的是（    ） A．120 B．60 C．3 D．23 18．整数序列“2，3，6，11，19，23，41，47，51”用对分查找法和顺序查找法在查找23时两种方法都能访问到的是 A．3 B．6 C．19 D．47 19．有如下程序段： For i=1 To 9   For j=10 To i+2 Step -1     If a(j)<a(j-2) Then       t=a(j): a(j)=a(j-2): a(j-2)=t     End If   Next j Next i 数组元素 a(1)到 a(10)的值依次为20，19，18，17，16，15，14，13，12，11，执行该程序段后，数组元素 a(8)的值为（   ） A．17 B．18 C．19 D．20 20．将序列 [1,4.2,5.3] 从小到大排序，使用选择排序法，从第一轮到最后一轮正确的顺序号。（   ） ① [1,2,3,4,5]  ② [1,2,3,5,4]  ③ [1,2,4,5,3]  ④ [1,4,2,5,3] A．④②③① B．④③②① C．③④②① D．③②④① 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查常用算法。根据题意需要对0到10之间的所有整数进行是否满足条件a+2b+5c=32的判断，这是枚举算法的特点，选项B正确。 2．A 【详解】本题考查枚举算法。枚举算法的最大优势是其设计直接、简单。枚举算法是一种朴素的穷举方法，通过遍历所有可能的解空间，逐一检查每个可能的解，从中找到满足条件的解。这使得枚举算法的设计相对直接简单，容易理解和实现。然而，并非所有问题都适合使用枚举算法，因为在某些情况下，其时间复杂度可能较高，但在设计直接简单的优势方面，枚举算法仍然具有一定优势。故答案为：A。 3．D 【详解】本题主要考查二分查找算法。二分查找适合用于有序的数列，故85 78 59 53 19 18（降序序列）适合二分查找算分，故本题选D选项。 4．A 【详解】本题考查常用算法。枚举算法（穷举法）的特点是：1.确定问题的求解范围，在枚举范围内不遗漏、不重复地枚举；2.确定满足要求的判断条件，并根据此判断条件对每一个枚举对象进行满足要求的判断；3.枚举算法的缺点是效率低，优化的方法通常是缩小枚举范围，题中算法的思想符合穷举算法特点2，选项A正确。 5．C 【详解】本题考查的是对分查找。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找;在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。第一次查找的位置是int(1+7)/2)=4，a(4)=due，故选项A说法错误，第二次查找的范围是a(1)——a(3)，查找的位置是int((1+3)/2)=2，a(4)=bro，第三次查找的位置是int((1+2)/2)=1，a(1)=all。查找过程中依次被访问到的数据是due、bro、all，选项C正确。 【点睛】 6．A 【详解】本题主要考查冒泡排序算法。冒泡排序是一种简单的排序算法，它也是一种稳定排序算法。其实现原理是重复扫描待排序序列，并比较每一对相邻的元素，当该对元素顺序不正确时进行交换。一直重复这个过程，直到没有任何两个相邻元素可以交换，就表明完成了排序。数据序列为“2，6，8，3，5，9，7”经过第一轮排序后为“2，3，6，8，5，7，9”，经过第二轮排序后为“2，3，5，6，8，7，9”，经过第三轮排序后为“2，3，5，6，7，8，9”，此后序列有排序结束，因此A选项正确。 【点睛】 7．A 【详解】本题考查二分查找。二分查找法在长度为n的有序线性表中查找元素时，每次比较都将查找区间缩小一半，因此平均查找长度为O(log2n)。故答案为：A。 8．C 【详解】本题考查枚举算法相关内容。枚举算法通过列举问题所有可能的解，并逐一检查每个解是否满足问题的条件。解析算法是通过数学公式或逻辑推理来直接计算或推导问题的解。ABD选项可以使用枚举算法解决，C选项应使用解析算法解决。故本题答案是C选项。 9．C 【详解】 10．C 【详解】本题考查枚举算法相关内容。枚举算法：现实中有一类问题可以采用搜索的方法，在搜索结果的过程中，把各种可能考虑的情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果。A选项是数制转换；B选项是乘法运算；D选项是求平均值；C选项是从100个中找出最大值，属于枚举算法。故本题答案是C选项。 11．C 【详解】本题主要考查二分查找算法。二分查找又叫做折半查找，是一种应用于有序序列的高效查找算法。只有数列85 74 59 53 19 18 11是有序的，故本题选C选项。 12．B 【详解】 13．C 【详解】 14．B 【详解】 15．A 【详解】本题考查枚举法。枚举法是对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案的方法。一一列举x、y和z的所有可能值的算法叫枚举法。故选：A。 16．B 【详解】本题主要考查算法描述。输出所有满足条件的直角三角形三边a，b，c，可知这种算法是枚举算法，故本题选B选项。 17．B 【详解】本题考查的是递归算法。根据题意，得f（5）=f（4）*5，要算出f（5）的值需要知道f（4）的值，而f（4）=f（3）*4，f（3）的值已知，将f（3）=3代入算出f（4）=12，继续代人算出f（5）=60。故选项B正确。 18．C 【详解】本题主要考查对分查找算法。使用对分查找访问到的数分别为：19、41、23。使用顺序查找法访问的数分别是：2、3、6、11、19、23，故本题选C选项。 19．A 【详解】本题考查冒泡排序。冒泡排序是相邻两项比较并进行交换，由内循环和If a(j)<a(j-2) Then可知程序实现隔位递增排序，即奇数位的数和偶数位的数分别从小到大排序，排序结果为12，11，14，13，16，15，18，17，20，19，可知 a(8)为 17，选A。 20．B 【详解】本题主要考查选择排序算法。选择排序算法：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。将序列 [1,4,2,5,3] 从小到大排序，使用选择排序法，则排序过程是：④ [1,4,2,5,3]→③ [1,2,4,5,3]→② [1,2,3,5,4]→① [1,2,3,4,5]，故本题选B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$