第四章算法应用举例同步练习2023—2024学年高中信息技术人教版选修1

第四章算法应用举例同步练习2023—2024学年高中信息技术人教版选修1 一、选择题 1．七进制数11表示成十进制是（   ） A．71 B．10 C．8 D．7 2．某排序算法的VB程序段如下所示： Dim i As Integer, j As Integer, t As Integer Const n=6 Dim a(1 To 6) As Integer '生成n个随机数，存储在数组a中，代码略 Private Sub Command1_ Click() For i= 2 To n t = a(i):j=i-1 Do While t < a(j) a(j+1)=a(j)   ' ① j=j-1 If j=0 Then   ExitDo Loop a(j+1)=t Next i   ' 显示排序后的数据，代码略 End Sub 经历某趟排序后，数据序列为2，5，8，1，9，7。则本趟排序前数据可能的顺序，以及本趟排序中语句①执行的次数为（    ） A．2，8，5，1，9，7  1次 B．2，5，8，1，9，7   1 次 C．8，2，5，1，9，7   2次 D．8，5，2，1，9，7   2 次 3．【加试题】有如下VB程序段：   Dim a(1 To 8) As Integer   a(1) = 12: a(2) = 44: a(3) = 65: a(4) = 26 a(5) = 48: a(6) = 91: a(7) = 98: a(8) = 13  n = 8: t = 0   For i = 1 To n - 1     k = i     For j = i + 1 To n       If a(j) < a(k) Then k = j     Next j     If k <> i Then       temp = a(i): a(i) = a(k): a(k) = temp: t = t + 1     End If   Next i   Text1.Text = Str(t) 该程序段运行后，文本框Text1中显示的内容是 A．5 B．7 C．8 D．28 4．F(n)＝F(n-1)＋2*F(n-2),F(l)＝l,F(2)＝2；当n＝4时，F的值是（   ）。 A．8 B．12 C．16 D．20 5．有一数组a(1 to 6)，其数值分别为“45、39、78、37、93、64”，想要从小到大排序，编写如下程序代码： Dim flag As boolean Dim a(1 to 6) As integer i =1: n=6: flag=True Do While i <=n-1 And flag= True     Flag=False     For j=n To i+1 Step -1         If a(j)< a(j-1) Then             k=a(j):a(j)=a(j-1):a(j-1)=k             Flag=True         End if     Next j     i=i+1 Loop 以上代码在整个排序过程中，数据总比较次数和总交换次数分别是（   ） A．9次和4次 B．9次和6次 C．12次和6次 D．15次和12次 6．如右图所示流程图片断，该流程图中循环部分结束后，变量S的值是(    ) A．5 B．15 C．25 D．36 7．某对分查找算法的VB程序段如下： Dim a(1 To 10) As Integer n = 0: a(1) = 1 For i = 2 To 10 a(i) = a(i - 1) + Int(Rnd() * 2) + 1 Next i Key = Int(Rnd() * 5) Top= 1: bottom = 10 Do While Top < = bottom m = (Top + bottom) \ 2 n = n+ 1 If Key = a(m) Then Exit Do Elself Key > a(m) Then Top = m + 1 Else bottom = m - 1 End If Loop 运行该程序段后，n的值不可能的是（    ） A．1 B．2 C．3 D．4 8．某对分查找的程序代码如下 Key = Int(Rnd * 25) * 2 n = 0: i = 1: j = 10 Do While i <= j    m = (i + j) \ 2    If Key = a(m) Then    Exit Do    If Key < a(m) Then       j = m - 1: n = n + 1    Else       i = m + 1: n = n - 1    End If Loop Text2.Text = Str(n) 其中 a(1)到 a(10)数组的值分别“2，3，6，9，10，18，38，40，47，48”， 执行该程序段后，n 的值不可能的是（   ） A．0 B．-1 C．-2 D．-3 9．以下程序生成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 10．下面是一组有序的数组d，现运用对分查找，d[m]为每次查找到的中间值，完成查找J的过程中所查找到的d[m]的值是（     ） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J K L M N A．G  K  L J B．G  C  K  J C．G  K  I  J D．G  H  K  J 11．下表记录了7个数据的冒泡排序过程，分析表中数据可以得知采用升序的方式，要经历多少次数据比较（ ） 原始数据 3 98 8 88 5 78 28 第1遍 3 5 98 8 88 78 28 第2遍 3 5 8 98 88 78 28 … … … … … … … … A．6 B．7 C．21 D．36 12．将6名选手的歌唱比赛成绩存放在数组a中，如下表所示： 若按升序排列，采用冒泡排序算法自右向左进行比较和交换，那么完成前二轮的数据处理，比较的总次数为 A．10 B．4 C．9 D．5 13．Function LEAP( Y  As Integer) As Integer If  Y  Mod 400 =" 0" Or Y Mod 4 =" 0" And Y Mod 100 <> 0 Then LEAP =" 1" Else LEAP =" 0" End Function Private Sub Text1_KeyPress(KeyAscii As Integer) Dim Y1  As Integer If  KeyAscii =" 13" Then Y1 = Val(Text1.Text)               ' 在text1中输入年份y1 Text2.Text =" Str(28" + LEAP(Y1))     ' 在text2中输出该年的二月份天数 End If End Sub 以上程序运行后，在Text1中输入 2001，在 Text2中显示的是（   ） A．28 B．29 C．30 D．31 14．下面程序段用于求两数中的较大数（结果保存到变量maxn中），不正确的是（ ） maxn=x A．maxn=xIf y>="maxn" Then maxn=y B．If x>y Then maxn="x" Else maxn=y C．maxn=xIf y>="x" Then maxn=y D．If y>="x" Then maxn=y 15．二分查找又称折半查找，是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（   ） 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 16．某 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 17．【加试题】若数组元素d(1)到d(8)的值依次为“86,75,58,46,20,18,12,5”，查找某Key值的VB程序段如下： n = 0 : i = 1 : j = 8 Key = Val(Text1.Text) Do While i <= j      m = (i + j) \ 2                    If Key = d(m) Then  Exit Do   'Exit Do表示退出循环 If Key > d(m) Then j = m - 1 : n = n - 1 Else i = m + 1 : n = n + 1     End If Loop Label1.Caption = Str(n) 当输入不同的Key值，运行该程序段后，在标签Label1中显示的不同结果共有 A．5种 B．6种 C．7种 D．8种 18．某算法流程图如图所示。当输入值为0时，该算法执行的步骤是（ ） A．①②③④ B．①②③⑤ C．①②④⑤ D．①②③④⑤ 19．有如下 VB 程序段： key =Int(Rnd()*17+2) i = 1: j = 9 Do While i <= j m = (i + j) \ 2 If a(m) <= key Then i = m + 1 Else j = m - 1 Loop Label1.Caption = str(i) 数组元素 a（1）到 a（9）的值依次为“2，4，6，8，10，12，14，16，18”，执行上述程序段后，在 Label1 中显示的内容不可能是（    ） A．1 B．2 C．5 D．10 20．方格状的地板，蜂窝，砖墙，草席等图结构上存在冗余，这种规律性的结构表现为（   ） A．空间冗余 B．结构冗余 C．视觉冗余 D．时间冗余 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查进制。七进制转换为十进制，采用位权展开法。从右往左，第一位数字乘以7的0次方，第二位数字乘以7的1次方，以此类推，然后将各个乘积相加。对于七进制数11，右边第一位1乘以7的0次方等于1，左边第一位1乘以7的1次方等于7，两者相加1+7=8，所以七进制数11表示成十进制是8。故答案为：C。 2．A 【详解】本题考查插入排序。由题中代码知，数据进行升序排序，如果当前数比前面的数小则进行交换。若经历某趟排序后，数据序列为2，5，8，1，9，7，则本趟排序前数据可能的顺序为：2，8，5，1，9，7，本趟排序中语句①执行的次数为1次，选项A正确。 3．A 【详解】本题主要考查VB程序的运行。此程序通过嵌套循环实现完成升序排序的功能，每交换一次，t的值递增1，44与13，65与26，65与44，91与65，91与98分别交换，故t的值为5，此时序列为12，13，26，44，48，65，91，98，故本题选A选项。 4．A 【详解】本题主要考查递归算法。F(4)=F(3)+2*F(2)=F(2)+2*F(1)+2*F(2)=2+2+2*2=8，故本题选A选项。 5．C 【详解】本题考查的是冒泡排序的变式。冒泡排序的基本思想是把待排序的 n 个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小（大）的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。当第一遍加工完成时，最小（大）的数据已经上升到第一个元素的位置。然后对余下的 n-1 个元素重复上述处理过程，直至最后余下两个数据的比较和交换。由外循环可知，如果没有交换，则就退出排序；由内循环可知是从右往左，按从小到大排序。第一遍排序：比较5次，交换4次，排序后数值为：37、45、39、78、64、93；第二遍排序：比较4次，交换2次，排序后数值为：37、39、45、64、78、93；第三遍排序：比较3次，无交换退出循环，共比较了：5+4+3=12次，交换了：4+2=6。故选项C正确。 6．B 【详解】 7．A 【详解】本题主要考查对分查找算法。 a(1) = 1， Int(Rnd() * 2) + 1是随机生成[1,2]之间的整数，a(i) = a(i - 1) + Int(Rnd() * 2) + 1，即后一项至少比前一项大1或2，即a(5)至少大于等于5，Key = Int(Rnd() * 5)，key是随机生成[0,4]之间的整数，第一遍循环，m = (Top + bottom) \ 2=5，显然key<a(5)，n>1，故运行该程序段后，n的值不可能的是1，故本题选A选项。 8．C 【详解】本题主要考查对分查找。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。题中a数组共10个元素，所查找数据Key = Int(Rnd * 25) * 2，由此可知，key取值范围为0-48之间的偶数，则程序执行结束后，n的值不可能为-2，因此C选项正确。 9．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正确。 10．C 【详解】 11．C 【详解】 12．C 【详解】本题主要考查冒泡排序算法。第一轮需要比较5次，最终90会被放到最右边，下一轮不参与比较，第二轮其余5个数会参与比较，比较4次，故完成前二轮的数据处理，比较的总次数为5+4=9，故本题选C选项。 13．A 【详解】 14．D 【详解】 15．D 【详解】本题主要考查二分查找算法。二分查找适合用于有序的数列，故85 78 59 53 19 18（降序序列）适合二分查找算分，故本题选D选项。 16．A 【详解】 本题考查选择排序。选择排序在一次选择中挑选需要的数交换到指定位置。题目中外循环Do While i <= 3只进行三次选择，内循环If a(j) < a(k)可知，为挑选最小的数。故三次选择，分别将最小的三个数字1，2，3交换到最前面，故本题选A。 17．D 【详解】本题主要考查二分查找算法。各种情况如下： 第一次循环 i=1，j=8 m=(1+8)\2=4 若Key>d(4) j=m-1=3 n = n – 1=-1 若Key=d(4) n=0 循环结束 d(4)=46 若Key<d(4) i=m+1=5 n = n +1=1 第二次循环 i=1，j=3 m=(1+3)\2=2 若Key>d(2) j=m-1=1 n = n – 1=-2 若Key=d(2) n=-1 循环结束 d(2)=75 若Key<d(2) i=m+1=3 n = n +1=0 i=5，j=8 m=(5+8)\2=6 若Key>d(6) j=m-1=5 n = n – 1=0 若Key=d(6) n=1 循环结束 d(6)=18 若Key<d(6) i=m+1=7 n = n +1=2 第三次循环 i=1，j=1 m=(1+1)\2=1 若Key>d(1) j=m-1=0 n = n – 1=-3 循环结束 若Key=d(1) n=-2 循环结束 d(1)=86 若Key<d(1) i=m+1=2 n = n +1=-1 循环结束 i=3，j=3 m=(3+3)\2=3 若Key>d(3) j=m-1=2 n = n – 1=-1 循环结束 若Key=d(3) n=0 循环结束 d(3)=58 若Key<d(3) i=m+1=4 n = n +1=1 循环结束 i=5，j=5 m=(5+5)\2=5 若Key>d(5) j=m-1=4 n = n – 1=-1 循环结束 若Key=d(5) n=0 循环结束 d(5)=20 若Key<d(5) i=m+1=6 n = n +1=1 循环结束 i=7，j=8 m=(7+8)\2=7 若Key>d(7) j=m-1=6 n = n – 1=1 循环结束 若Key=d(7) n=2 循环结束 d(7)=12 若Key<d(7) i=m+1=8 n = n +1=3 第四次循环 i=8，j=8 m=(8+8)\2=8 若Key>d(8) j=m-1=7 n = n – 1=2 循环结束 d(8)=5 若Key=d(8) n=3 循环结束 若Key<d(7) i=m+1=9 n = n +1=4 循环结束 综上所有情况，n的取值有：-3、-2、-1、0、1、2、3、4，故本题选D选项。 18．C 【详解】 19．A 【详解】本题主要考查二分查找算法。key =Int(Rnd()*17+2)，key是随机生成[2,18)之间的整数，i=1，j=9，m=(1+9)\2=5，a(5)=10，key<10，j=m-1=4，m=(1+4)\2=2，a(2)=4，若key=2，j=m-1=1，m=(1+1)\2=1，a(1)=2，满足a(m)<=key，i=m+1=2，即在 Label1 中显示的内容为2，不可能为1，同理其他情况，显示的内容还可能为5、10，故本题选A选项。 20．B 【详解】 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$