第四章 算法应用举例 2023-2024学年高中信息技术【人教版】选修一

第四章 算法应用举例 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．一位顾客购买了土豆X 千克、西红柿 Y 千克、辣椒 Z 千克，其中土豆 3.5元/千克、西红柿4.3元/千克、辣椒6.6元/千克。计算该顾客消费总价的算法如下： �输入三种蔬菜的重量X,Y,Z �用公式计算总价 S=3.5*X+4.3*y+6.6*z �输出总价S �结束 以上算法属于（    ）。 A．枚举算法 B．解析算法 C．排序算法 D．查找算法 2．关于迭代与递归算法，下列说法错误的是（   ） A．迭代是重复反馈的活动，其目的通常是逼近所需目标或结果 B．递归是重复调用函数自身 C．迭代程序可以转换成等价的递归程序 D．迭代和递归是同一种算法的两种不同的表述 3．有如下VB程序段： Function fun(x As Integer) As Integer If x <= 2 Then fun = x Else fun = 2 * fun(x - 1) + fun(x - 2) End If End Function 则表达式fun(5)的值为（   ） A．12 B．29 C．30 D．70 4．采用经典冒泡排序算法对数据序列“9，3，4，5，0”完成升序排序，则排序过程中数据“4”被比较的次数为（    ） A．2次 B．3次 C．4次 D．5次 5．某 VB 程序段如下： n = 6: i = 1 Do While i <= 3 k = i: j = i + 1 Do while j <= n If a(j) < a(k) Then k = j j = j +1 Loop If i <> k Then t = a(i): a(i) = a(k): a(k) = t End If i=i+1 Loop 数组元素 a(1)到 a(6)的值依次为 1，6，5，3，4，2，则该程序段运行后，数组元素 a(1)到 a(6)的值依次为（   ） A．1，2，3，5，4，6 B．6，4，5，3，2，1 C．1，2，3，4，5，6 D．6，5，4，3，2，1 6．以下程序生成10个整数,并且完成从小到大排序 Dim a(1 To 10) As Integer Randomize a(1) = Int(100 * Rnd)   '先生成第1个数 For i = 2 To 10         '然后生成2到第10个 temp = Int(100 * Rnd) Low = 1 high = i - 1   Do While Low <= high           m = (Low + high) \ 2       If temp >a(m) Then         ________①_________       Else         high = m - 1       End If    Loop    For j = i - 1 To Low Step -1   '从原来有数据的最后位置开始逐个数据后移      a(j + 1) = a(j)    Next j ________②_________ Next i 则空缺处代码为（        ） A．①Low = m + 1  ② a(Low) = temp B．① Low = m  ② a(Low) = temp C．①Low = m + 1  ② a(high) = temp D．① Low = m  ② a(high) = temp 7．二分查找又叫做折半查找，是一种应用于有序序列的高效查找算法。下列数列中适合二分查找算法的是（    ） 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 8．小刘研究冒泡排序算法后发现每一遍加工从前往后比较相邻两个数据，把较大者交换到后面，经过n-1遍加工后也能实现从小到大排序。5个学生的身高（单位：cm）依次为172，177，180，168，165，采用小刘的排序方法进行从低到高排序，第三遍加工的交换次数为（） A．3 B．2 C．1 D．0 9．一次运动会上，某组6位选手的百米成绩(单位：秒)分别是“14.1、12.3、11.2、14.8、13.9、11.0”，若使用选择排序法将该组的成绩按第一名、第二名、第三名……的顺序排序，则第一次交换数据后的顺序是（ ） A．14.8 14.1 12.3 11.2 13.9 11.0 B．11.0 12.3 11.2 14.8 13.9 14.1 C．14.8 12.3 11.2 14.1 13.9 11.0 D．11.0 14.1 12.3 11.2 14.8 13.9 10．有如下程序段： 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 11．下列VB程序段实现求双重数列0，2，1，4，1，6，2，8，3，10，5，12，8，……前n项中的奇数项和。 Dim a(1 To 100)As Integer n= Val(Text1. Text) a(1)=0:a(3)=1 s=1 Next i Text2. Text= Str(s) 方框中的代码由以下三部分组成： ①a(i)=a(i-2)+a(i-4)  ②s=s+a(i)  ③For i=5 To n Step2 代码顺序正确的选项是（    ）。 A．①②③ B．③②① C．②①③ D．③①② 12．已知t=55.8，s=64，m=-81，则下列Visual Basic表达式的值为False的是（ ） A．t < abs（m）and int（t）+8 >= s B．int（m）> s or t < abs（m） C．sqr（s）+ t < abs（m） D．t > s + m 13．有如下VB程序： n = 7 For i = 1 To n \ 2 For j = n - i + 1 To i + 1 Step -1 If a(j) Mod 10 > a(j – 1) Mod 10 Then t = a(j): a(j) = a(j – 1): a(j – 1) = t End If Next j Next i 已知a(1)到a(7)各元素初值分别是31、22、73、 54、 85、26、 37，运行上述程序后，a(1)到a(7) 各元素的值分别是 A．85、73、54、31、22、37、26 B．37、26、22、31、54、73、85 C．37、85、73、31、22、54、26 D．26、54、22、31、73、85、37 14．下面的故事与（    ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’” （   ） A．枚举 B．递归 C．二分 D．迭代 15．某对分查找算法的 VB 程序段如下: i =1 : j=10 : s="" : n=0 key = 10+int(Rnd*20) Do While i<=j n=n+1 m=(i+j)\2 s =s+ str(m) If key = a(m) Then Exit Do 'ExitDo 表示退出循环 If key < a(m) Then j=m-1 Else i=m 十 1 Loop a(1)~a(10)中的值依次是5，8，16，23，29 ,30，42，51，57，69执行程序后，以下说法正确的是（   ） A．s 的值可能是"5 8 6 7" B．i 的值一定小于6 C．j 的值一定大于2 D．n 的值一定小于4 16．某对分查找算法的VB程序段如下： Key= Val(Text1. Text) i=1: j=10 : n=0 Do While i<=j     m=(i+j)\2     n=n+1     If b(m) > Key Then         i=m+1     Else         j=m-1     End If Loop Text2. Text= str(n) 数组元素b(1)到b(10)的值依次为“25,19,17,13,10,9,8,5,3,2”。在文本框Text1中输入待查找的整数，执行该程序段后，文本框Text2中显示3，则待查找数不可能是（  ） A．19 B．9 C．4 D．2 17．有如下程序段： Private Sub Command1_Click() Dim a(1 To 7) As Integer a(1) = 1:a(2) = 4: a(3) = 7: a(4) = 3: a(5) = 5: a(6) = 6: a(7) = 1 s = "": i = 6: b = 1 Do While i > b If a(i) = a(i - 1) + a(i + 1) Then For j = i To b + 1 Step -1 a(j) = a(j - 1) Next j b = b + 1: i = i + 1 End If i = i - 1 Loop For i = b To 7 s = s + Str(a(i)) Next i Text1.Text = s End Sub 运行程序后，文本框中显示的结果为（    ） A．1 3 5 1 B．1 4 3 5 1 C．1 4 7 3 5 1 D．1 4 7 5 1 18．以下程序段执行后，整型变量a的值为（ ）。 a = 3 b = 5 b =b + a a =a + b A．3 B．5 C．11 D．13 19．编写一个VB程序实现以下功能：产生10个1~100之间的随机整数存数组a中，引入一个数组q，使得a(q(i))升序，即a(q(1) )≤a(q(2) ) ≤a(q(3) )……≤a(q(9) )≤a(q(10) )。 For i = 1 To 10        a(i) = Int(Rnd() * 100) + 1 Next i For i = 1 To 9   k = i   For j = i + 1 To 10     If     Then k = j   Next j   If i <> k Then     t = q(i): q(i) = q(k): q(k) = t   End If Next i 上述程序段2个方框处的代码分别为（   ） A．（1）q(i) = i   （2）a(q(j)) < a(q(k)) B．（1）q(i) = i   （2）a(j) < a(k) C．（1）q(i) = 1   （2）a(q(j)) < a(q(k)) D．（1）q(i) = 1   （2）a(j) < a(k) 20．有如下VB程序段： For p= 1 To 6 i=l:j=6:q=0 Do While i<= j m=(i +j)\2 q=q+1 If p= mThen f(p)=q: Exit Do   'ExitDo表示退出循环 End If If p>m Then i=m+1 Else j=m-1 Loop Next p 数组元素f(1)到f(6)初始为0，执行该程序段后，其值依次是（   ） A．2，3，1，3，2，3 B．3，2，3，1，2，3 C．2，3，1，3，3，2 D．3，2，1，3，2，3 21．在冒泡排序算法中，最好情况（即数组已经是有序的）下需要进行（   ）轮比较。 A．n B．n-1 C．n(n-1)/2 D．0 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】 2．D 【详解】本题主要考查迭代与递归算法。迭代是重复反馈的活动，其目的通常是逼近所需目标或结果；递归是重复调用函数自身；迭代程序可以转换成等价的递归程序；迭代和递归不是同一种算法的两种不同的表述，故本题选D选项。 3．B 【详解】本题考查的分析程序运行结果。运行过程如下： fun(5)    5<=2不成立    执行fun=2*fun（4）+fun（3） fun(4)    4<=2不成立    执行fun=2*fun（3）+fun（2） fun(3)    3<=2不成立    执行fun=2*fun（2）+fun（1） fun(2)    2<=2成立 fun=2 fun(1)    1<=2成立 fun=1 所以fun（5）=2*fun（4）+fun（3）             =2*（2*fun（3）+fun（2））+2*fun（2）+fun（1）             =2*（2*fun（3）+2）+2*2+1             =4fun（3）+4+5             =4（2*fun（2）+fun（1））+9             =4（2*2+1）+9             =4*5+9=29 故选项B正确。 4．D 【详解】本题主要考查冒泡排序算法。第一遍循环，与 4比较的是9，循环完数据序列为“3，4，5，0，9”；第二遍循环，与4比较的是3和5，循环完数据序列为“3，4，0，5，9”；第三遍循环，与4比较的是0，循环完数据序列为“3，0，4，5，9”；第四遍循环，与4比较的是3，循环完数据序列为“0，3，4，5，9”，故排序过程中数据“4”被比较的次数为5，故本题选D选项。 5．A 【详解】 本题考查选择排序。选择排序在一次选择中挑选需要的数交换到指定位置。题目中外循环Do While i <= 3只进行三次选择，内循环If a(j) < a(k)可知，为挑选最小的数。故三次选择，分别将最小的三个数字1，2，3交换到最前面，故本题选A。 6．A 【详解】本题考查插入排序和对分查找。插入排序核心是在数组中寻找待插入位置，本题采用对分查找寻找插入位置。题目要求升序排序，根据Do While Low <= high，以及If temp >a(m) Then可知①处代码为Low = m + 1。待插入位置为a(low)处，需先将原数据后移，通过For j = i - 1 To Low Step -1……next j循环实现，最后将待插入数据放入a（low）中，②处代码为a(Low) = temp。选项A正确。 7．C 【详解】本题主要考查二分查找算法。二分查找又叫做折半查找，是一种应用于有序序列的高效查找算法。只有数列85 74 59 53 19 18 11是有序的，故本题选C选项。 8．B 【详解】本题考查的是冒泡排序。从前往后，把较大者交换到后面，第一遍加工后：172，177，168，165，180，第二遍加工后：172，168，165，177，180，第三遍加工：172与168、165交换，故交换2次，选项B正确。 9．B 【详解】本题考查的是选择排序。选择排序是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。故则第一次交换数据后的顺序是：11.0 12.3 11.2 14.8 13.9 14.1。选项B正确。 10．A 【详解】本题考查冒泡排序。冒泡排序是相邻两项比较并进行交换，由内循环和If a(j)<a(j-2) Then可知程序实现隔位递增排序，即奇数位的数和偶数位的数分别从小到大排序，排序结果为12，11，14，13，16，15，18，17，20，19，可知 a(8)为 17，选A。 11．D 【详解】本题考查的知识点是VB函数的解读。前n项中奇数项之和，只要在循环中，把奇数项挑选出来，并相加即可。循环初值为奇数项，步长为2即③For i=5 To n Step2，a(i)的值是它之前两个奇数项之和，即①a(i)=a(i-2)+a(i-4)，前i项的奇数项之和s=s+a(i)，故选项D正确。 12．A 【详解】本题意图考核VB表达式及VB常用函数的相关知识。int（55.8）=55而不是56，所以A选项int（t）+8 >= s的值为False，t < abs（m）的值为True，False and True的值为False。B选项int（m）> s 的值为False，t < abs（m）的值为True，False or True的值True。C选项中的sqr（s）是求s的算术平方根，C、D选项的表达式的值都为真。 13．C 【详解】本题主要考查冒泡排序算法及VB程序实现。i表示排序的趟数，共排序3趟，j表示参与排序的数据范围，IF后面的表达式表示排序方式，本题按照数组a中的个位数字在排序范围内降序排序，在第1趟排序中，所有的数据都参与排序，排序后的数据是：37、31、22、73、54、85、26；在第2趟排序中，第一位和最后一位数据不参与排序，排序后的数据是：37、85、31、22、73、54、26；在第3趟排序中，前两位和后两位数据不参与排序，排序后的数据是.37、85、73、31、22、54、26，故本题选C选项。 14．B 【详解】本题主要考查递归的描述。一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，故本题选B选项。 15．B 【详解】本题主要考查对分查找算法。i=1，j=10，key = 10+int(Rnd*20)，key是随机生成[10,29]之间的整数，结合a(1)~a(10)的值，m的值应小于6（a(6)=30），s 的值不可能是"5 8 6 7"，同理i 的值一定小于6，j的值可能等于2，n的值可能等于4，故本题选B选项。 16．D 【详解】本题主要考查对分查找算法。该查找过程用二叉树表示如下，执行该程序段后，文本框Text2中显示3，即查找深度是3，而待查找数2在二叉树中的第四层，不可能，故本题选D选项。 17．A 【详解】本题考查插入排序。从后往前扫描数组，如果数组中当前元素等于前后两个元素之和，即a(i) = a(i - 1) + a(i + 1)，则a(i) = a(i – 1)，并且数组中该元素之前的所有数据都后移一个位置，程序运行后，文本框中显示的结果为：1 3 5 1，选项A正确。 18．C 【详解】 19．A 【详解】本题考查的是选择排序。选择排序算法思想找出所有元素中最小（或最大）数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小（或最大）的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。程序初始生成数组q（i）=i，题干要求a(q(i))升序，故第2个方框应为：a(q(j)) < a(q(k))。故选项A正确。 20．A 【详解】本题主要考查二分查找算法及VB程序实现。查找过程m的值用二叉树表示如下，分析程序可知，当p=m时，f(p)=q，其中p对应二叉树中的节点值（即m的值），q对应查找深度，即对应二叉树中的层，由图可知，数组元素f(1)到f(6)初始为0，执行该程序段后，其值依次是2，3，1，3，2，3，故本题选A选项。 21．B 【详解】本题考查冒泡排序。在冒泡排序算法中，如果数组已经是有序的，理论上外层循环会执行n-1轮，但实际的冒泡排序实现中，可以设置一个标志位来检测是否进行了交换，如果没有交换发生，说明数组已经是有序的，可以提前结束排序，因此实际最好情况下可能少于n-1轮比较，但题目选项中没有这一选项，因此按照传统的冒泡排序逻辑，答案是n-1。故答案为：B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$