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

第四章 算法应用举例 一、选择题 1．某数组有10个元素，依次为11、22、33、45、55、66、77、88、92、98，若采用对分查找法在该数组中查找数据92，依次被访问的数据为(    ) A．55、88、92 B．55、77、88、92 C．66、88、92 D．66、88、98、92 2．a、b、c三个整数，它们满足条件：100>a>b>c>10，a*b*c=30723，a>b+c。要通过编程确定a、b、c的值，你会选择的方法是（    ）。 A．解析法 B．顺序查找算法 C．递归算法 D．穷举法 3．顺序查找算法程序如下，下列说法正确的是（      ） Dim d(1 to 10) as Integer n=10 : count = 0 For i = 1 To n count = count + 1 If ① Then Label1.Caption = “顺序查找在数组的第” &amp; i &amp; “位找到了” &amp; v Exit For End If Next i If ② Then Label1.Caption = “顺序查找没有找到” &amp; v End If A．①处的代码为key=d(i) B．②处的代码为i>n C．在最好情况下，查找结束时变量count 的值为0 D．当变量count 的值为10，说明已经找到了 4．分别采用选择排序和冒泡排序对数据序列“15 89 60 34 10 28 70”完成升序排序，则在两种排序方法过程中，数据“60”发生交换的次数分别可能为（ ） A．3   3 B．2 4 C．21   4 D．3  4 5．有如下VB程序段： For i = 1 To 8   a(i) = Int(Rnd ∗ 10)+ 1 Next i For i = 1 To 5 Step 2   k = i   For j = i + 2 To 7 Step 2     If a(j) < a(k) Or a(j)= a(k) And a(j + 1)< a(k + 1)  Then k = j   Next j   If i < > k Then     t = a(i): a(i)= a(k)：a(k)= t     t = a(i + 1): a(i + 1)= a(k + 1): a(k + 1)= t   End If Next i 运行该程序段后，数组a各元素的值可能为（  ） A．1，2，1，1，4，3，6，5 B．1，1，1，2，3，4，5，6 C．0，1，5，2，7，4，5，6 D．3，4，5，2，6，4，7，11 6．使用冒泡排序算法对序列6,10,7,4,9进行升序排序，则排序过程中总交换次数为（  ） A．5 B．6 C．7 D．8 7．冒泡排序在某一遍加工过程中没有数据交换时，说明数据已经有序，优化程序段如下： i = 1: flag = True Do While i < = 4 And flag = True flag=False For j = 6 To i + 1 Step -1 If a(j) > a(j - 1) Then t = a(j): a(j)=a(j-1): a(j-1) = t flag = True End If Next j i = i + 1 Loop 数组元素a(1)到a(6)的值依次为48，36， 24，97，77，23，经过该程序段加工后，变量i的值是（     ） A．1 B．3 C．5 D．4 8．有如下VB程序段：     i = 1: j = 10     flag = True: k = 0     Key = Val(Text1.Text)     Do While i <= j And flag = True         m = (i + j) \ 2         If a(m) = Key Then             flag = False         ElseIf a(m) > Key Then             i = m + 1             k = k - 1         Else             j = m - 1             k = k + 1         End If     Loop   数组元素a(1)～a(10)的值依次为102,91,88,84,80,72,70,65,50,46,变量k的值最终为0，则文本框Text1中输入的数字可能是（   ） A．91 B．87 C．70 D．50 9．以下VB程序段用于在升序数组a中找到第一次出现的Key的下标。 Key = Val (Text1. Text) low = 0:high = 9:flag = False Do While low <= high And Not flag     m=(1ow +high)\ 2     If Key > a(m) Then         low = m +1     ElseIf Key < a(m)Then         high = m- 1     Else         If ① Then             If ② Then high = m- 1 Else flag = True         Else             flag = True         End If     End If Loop If flag = True Then Print("元素的下标是:"+ Str(m)) Else Print("元素未找到.") End If 若数组元素a(0)~a(9)的值依次为“2，2，6，8，10，10，13，15，17，26”，在文本框Text1中输入10，运行上述程序后，程序输出“元素的下标是：4”。程序中划线处代码为（    ） A．①m>0    ②key = a(m -1) B．①m>-1    ②key = a(m -1) C．①m>0    ②key = a(m +1) D．①m>-1    ②key = a(m +1) 10．十进制数241转换成8位二进制数是（   ） A．10111111 B．11110001 C．11111001 D．10110001 11．某对分查找算法的 VB．程序段如下： t="":i=0:j=9:key=62:f=False Do While i<=j And Not f m=Fix((i+j)/2) t=t+Str(rn) If a(m)=key Then f=True Elself a(m)>key Then i=m+1 t=t+"→" Else j=m-1 t=t+"←" End If Loop 数组元素a(1)到a(10)的值依次为“99，94，90，87，78，70，63，56，45，36”，执行该程序段，t的值是（    ） A．“4→7←5→” B．“4→7←5→6→” C．“4→7←5→6” D．“4→7←5” 12．若采用冒泡排序算法对数据2， 36， 98， 15， 88， 118进行排序，排序过程如表所示。 原始数据 2 36 98 15 88 118 第一遍加工后 36 98 15 88 118 2 第二遍加工后          则第二遍加工后的结果是（  ） A．2，15，36，88，98，118 B．98，88，118，36，15，2 C．98，36，88，118，15，2 D．98，36，88，15，118，2 13．某排序算法的 VB 程序段如下： n = 8: f = 1: c = 0 For i = 1 To n \ 2 - 1 For j = 1 To n - 2 * i If f * a(j) < f * a(j + 2) Then             t = a(j): a(j) = a(j + 2): a(j + 2) = t c = c + 1 End If f = -f Next j Next i 数组元素 a(1)到 a(8)的初始值依次为:“16,31,42,38,35,29,27,15”,执行该程序段后，变量 C的值为（   ） A．6 B．7 C．8 D．9 14．在序列“7,14,18,21,23,29,31,35,38,42,46,49,52”中用二分查找法查找数字“42”，一共找了（    ）就找到了。（   ） A．2次 B．3次 C．4次 D．5次 15．下列说法正确的是（    ） A．未优化过的选择排序和冒泡排序，比较次数肯定是相同的，所以交换次数也肯定相同 B．对包含7个数据的有序数组a进行对分查找，平均查找次数为17/7次 C．VB调用数据库时，rs. fields（1）指的是调用某数据表中某条记录第1个字段的值 D．使用选择排序时，若某--遍排序时，并没有数据进行交换，说明数据已经有序 16．【加试题】所谓双向排序是在一遍加工中先从上到下把最大的元素送到最下的位置，再从下到上把最小的元素送到最上的位置。实现上述功能的vb代码如下： Dim a(1 to 100) as integer Const n=10 Private Sub form_load() ’生成n个随机数，存储在数组a中，代码略 End Sub Private Sub command1_click() Dim i as integer,j as integer For 　 ① 　 For j=i to n-i                If a (j)>a(j+1) then t=a(j):a(j)=a(j+1):a(j+1)=t End If Next j For ② If a(j)<a(j-1) then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j Next i for i=1 to n List2.additem str(a(i)) Next i End Sub 程序中①②处最合适的语句是（  ） A．① i=1 to n-1     ②j=n to i+1 step -1 B．① i=1 to n\2     ②j=n-i to i+1 step -1 C．① i=1 to n\2     ②j=n to i+1 step -1 D．① i=1 to n-1     ②j=n-i to i+1 step -1 17．有如下 VB 程序段： n = 8 For i = 1 To n d(i) = Int(Rnd * 10) + 1 Next i For i = 2 To n k = 1 For j = 1 To n - i If d(j) * k > d(j + 2) * k Then temp = d(j): d(j) = d(j + 2): d(j + 2) = temp End If k = -k Next j Next i 执行该程序段后，d 数组各元素可能是（    ） A．1,3,4,5,6,6,7,8 B．6,4,5,6,5,7,1,10 C．2,11,3,8,5,6,8,5 D．3,9,3,5,4,4,10,1 18．数组a中存储了无序的数组元素，为了使a数组中的元素存储为左右交替上升，小赵依据选择排序思想设计了如下VB程序算法，为了实现上述功能，划线处应填入的代码为（   ） L= 1:R=n Do While L<R     imin_l = L:imin_2=R     For i=L +1 To R      If a（i）< a （imin_1）Then      imin_ 2 = imin_ 1      imin_1=i ElseIf a(i) < a(imin. _2) Then imin_ 2= i End If Next i If imin _1 <> L Then t = a(imin_ 1): a(imin_ 1) = a(L): a(L) = t ________________________ If imin_ 2 <> R Then t = a(imin_ 2): a(imin_ 2) = a(R): a(R) = t L=L+1:R=R-1 Loop A．If imin_1=L Then imin_1=imin_2 B．If imin_1=L Then imin._2=imin_1 C．If imin_2=L Then imin_1=imin_2 D．If imin_2=L Then imin_2=imin_1 19．二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。二分搜索算法是利用（  ）实现的算法 A．分治法 B．动态规划 C．贪心法 D．回溯法 20．某算法表示如下： ①将 0 赋值给变量 Num，将 1 赋值给变量 i ②若 i 除以 2 余 0，则将变量 Num 的值增加 1 并输出 i ③变量 i 的值增加 1，若变量 i 小于等于 10，则转② ④结束 关于该算法的说法不正确的是 A．该算法是用自然语言来描述的 B．该算法结束后i=11 C．该算法最后输出 5 个数值 D．该算法只能用 Do While 语句实现 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题主要考查对分查找算法。令变量i=1，j=10，m=(1+10)/2=5，第一次访问的数据是55，55<92，i=m+1=6，m=(6+10)/2=8，第二次访问的数据是88，88<92，i=m+1=9，m=(9+10)/2=9，第三次访问的元素时92，故依次被访问的数据为55、88、92，故本题选A选项。 2．D 【详解】本题考查常用算法。根据题意需要对10-100以内的所有整数进行是否满足条件a*b*c=30723，a>b+c的判断，这是穷举算法的特点，选项D正确。 3．B 【分析】本题考查的知识点是顺序查找算法。①处的代码应为v=d(i)，选项A错误；在最好情况下是第一次循环即查找结束，此时变量count 的值为1，选项C错误；当变量count 的值为10，说明进入了最后一轮循环查找，选项D说法错误。②处的代码为i>n，此时i的值为11，n的值为10，说明没有查找到，故选项B说法正确。 【详解】略 4．B 【详解】本题考查排序算法。选择排序升序过程，若从左往右（大的往后排），第一遍为15，70，60，34，10，28，89，第二遍为15，28，60，34，10，70，89，第三遍为15，28，10，34，60，70，89.“60”发生交换的次数为1次，若从右往左（小的往左排），第一遍为10，89，60，34，15，28，70，第二遍为10，15，60，34，89，28，70，第三遍为10，15，28，34，89，60，70.第四遍为10，15，28，34，60，89，70，“60”发生交换的次数为2次；冒泡排序过程中，若从左往右冒泡（大的往后冒泡），则第一遍为15，60，34，10，28，70，89，第二遍为15，34，10，28，60，70，89，“60”交换的次数为4次，若从右往左冒泡（小的往前冒泡），则第一遍为10，15，89，60，34，28，70，第二遍为10，15，28，89，60，34，70，第三遍为10，15，28，34， 89，60，70，第四遍为10，15，28，34，60，89，70，“60”发生交换的次数为4次，选项B正确。 5．B 【详解】本题主要考查产生随机数和选择排序的变式。Int(Rnd * 10)+1可以产生1~10范围内的随机整数，故不可能有0或11，选项C和D错误。选择排序第i遍加工，若a(j)< a(k)，则更新k为j，挑选出奇数位置最小元素的位置；若a(j)=a(k)And a(j+1)< a(k+1)，表明奇数位置相等，则比较后续相邻偶数位置元素与a(k+1)的关系，即奇数位置元素最小值有多个，则k记录对应后续偶数位置最小数据的前一位置。归纳可得该程序功能是按奇数位置数据为主要关键字升序，偶数位置数据为次要关键字升序进行选择排序。选项A中“1，2”应该排在“1，1”的后面，选项A错误。 6．A 【详解】本题主要考查冒泡排序算法。第一遍，10分别与7、4、9进行交换，序列变为6,7,4,9,10；第二遍，7与4进行交换，序列变为6,4,7,9,10；第三遍，6与4交换，序列变为4,6,7,9,10，此时序列已有序，总交换次数为5次，故本题选A选项。 7．D 【详解】 本题考查的是冒泡排序相关知识。由外循环i < = 4 And flag = True可知，冒泡大于4趟或没有数据交换时，跳出冒泡排序。由内循环For j = 6 To i + 1 Step -1及If a(j) > a(j - 1) Then可知，这是一个从右往左，按从大到小冒泡，数组初始值：48，36， 24，97，77，23，第一趟有交换不跳出，执行一次i = i + 1，交换完后：97，48，36，24，77，23；第二趟有交换不跳出，执行一次i = i + 1，交换完后：97，77，48，36，24，23；第三趟数组已经有序了，不交换，flag=False，执行一次i= i + 1，跳出外循环，故i的值为4。选项D正确。 8．B 【详解】本题考查的是对分查找算法。10个数据对分查找的过程如图所示，其中图中数字为m的值，由程序代码可知，当执行i = m + 1及k = k - 1时，即去中间位置的右侧查找时，变量k减1，当执行ij= m - 1及k = k +1时，即去中间位置的左侧查找时，变量k加1，题干中要求变量k的值最终是0，即左右查找的次数相同，则文本框Text1中输入的数字对应位置可能是5、3、6，可能值为80、88-90、71-72，故本题应选B。 9．A 【详解】本题主要考查二分查找算法。第一空是执行if分支结构else部分，当m大于0时，执行等于key的情况，否则m=0，执行flag=True，故此处填m大于0，第二空，因为数组a是升序，此时已满足a(m)=key，此处判断前一位即a(m-1)是否与key相等，若相等则执行high=m-1，继续循环，否则已找到满足条件的下标，并赋值flag为True，故第二空填key = a(m -1)，故本题选A选项。 10．B 【详解】本题主要考查进制数的转换。十进制数241通过“除权取余、逆序排列”的方法转换为二进制数是11110001。故本题应选B。 11．B 【详解】本题考查对分查找。查找过程如表： I 0 5 5 6 7 J 9 9 6 6 6 M 4 7 5 6 退出循环 A(m) 78 56 70 63 t 4→ 4→ 7← 4→7 ←5→ 4→7 ←5→ 6→ 故选项B正确。 12．C 【详解】本题考查的是冒泡排序算法。第一遍排序后最后一个数是最小，而第一个数不是最大的数，说明这是一个从左向右冒泡的降序排序，故第二遍排序后98，36，88，118，15，2，选项C正确。 13．C 【详解】本题主要考查冒泡排序算法及VB程序实现。分析程序可知，该VB程序段对数组a中的数据进行排序，排序的规律是：奇数位置降序，偶数位置升序，C变量用于计算在排序过程中一共交换的次数，一共交换了8次，故本题选C选项。 14．A 【详解】本题考查二分查找法。二分查找法是一种将已排序的数组或列表中的元素进行查找的算法。它通过将待查找的区间不断缩小一半来快速定位目标元素。在这个序列中，首先确定整个区间的左右边界，即左边界为0，右边界为12（序列长度减1）。然后取中间位置的元素，即索引为6的元素31，与目标元素42进行比较。由于31小于42，因此目标元素一定在右半部分，于是将左边界更新为中间位置的下一个位置7，右边界不变。再次取中间位置的元素，即索引为9的元素42，由于该元素为42，因此找到了目标元素。因此，在这个序列中用二分查找法查找数字“42”，一共找了2次就找到了。选项A正确。 15．B 【详解】本题考查的是算法的基础知识。选项A选择排序和冒泡排序的比较次数是一样的，但是交换次数，不一定是相同的，选项B数组共7个数，对分查找的平均查找次数为（1+2*2+4*3）/7=17/7，选项C rs．fields（1）是某记录的第2个字段的值，选项D指的是冒泡排序，不是选择排序，所以只有选项B是正确的。 16．B 【详解】本题主要考查排序算法及VB程序实现。双向排序是对冒泡排序的改进优化，在一遍加工中既把最大的元素放在最后，还把最小的元素排在最前，因此，加工次数比普通冒泡排序节省一半，最外层循环运行到n\2时，此时元素已有序，故①中循环变量i终值为“n\2”；在第i遍排序中，首先把最大元素放在排序元素的最后，然后中，从第（n-i）个元素开始，把数组第（i+1）到（n-i）元素进行排序（此时1到i、n-i+1到n均已有序），将其中最小值放在排序元素的最前面，因此②为“j=n-i to i+1 step -1”，故本题选B选项。 17．D 【详解】本题综合考查随机数的生成和冒泡排序算法。生成的随机整数在1到10之间。排序时是奇数位和偶数位分开排序。当k=1时，是升序，当k=-1时是降序，可知奇数位是升序，偶数位是降序，故选D。 18．D 【详解】本题考查的是选择排序的变式。程序实现的 思想是：每遍加工过程，假设数组头元素是第一小，数组尾元素是第二小，然后找出第一小放在数组头，第二小放在数组尾，最后 去掉数组头和尾，重复上面步骤。每遍加工结束，如果第一小不是数组头，则要交换，如果第2小在数组头，则把第2小位置定位到imin_1，如果imin_1不是数组尾，则要交换。故选项D正确。 19．B 【详解】本题主要考查二分查找算法。动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。二分搜索算法根据搜索值会动态规划缩小搜索范围，故本题选B选项。 20．D 【详解】本题主要考查算法的描述。该算法是用自然语言来描述的，该算法结束后i=11，该算法最后输出 5 个数值（分别是2、4、6、8、10），该算法可以用 Do While 语句实现，也可以用for循环实现，故本题选D选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$