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

第四章算法应用举例同步练习高中信息技术人教版选修1 1．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 2．【加试题】有以下 VB 程序段 For i = 1 To 2 For j = 1 To 4-i If d(j) > d(j +1)Then t = d(j):d(j) = d(j +1):d(j +1) = t End If Next j Next i 数组元素 a(1)到 a(5)的值依次为“51，36，78，18，15”，经过该程序段“加工”后，数组元素a(1)到 a(5)的值依次为（） A．36，18，51，78，15 B．36，18，15，51，78 C．15，18，36，51，78 D．36，51，18，78，15 3．某VB程序代码如下： For i = 1 To 3     For j = 5 To i Step -1       If a(j) < a(j + 1) Then          t = a(j): a(j) = a(j + 1): a(j + 1) = t       End If     Next j   List1.AddItem Str(a(i)) Next i 数组元素 a(1)到 a(6)的数据依次为“1，5，7，6，9，3”，经过该程序段加工后，列表框 list1 中显示的内容是（  ） A．9 7 6 B．1 3 5 C．9 7 6 1 5 3 D．9 7 6 5 3 1 4．如右图所示流程图片断，该流程图中循环部分结束后，变量S的值是(    ) A．5 B．15 C．25 D．36 5．现有三个整数序列：“1，2，3，4，5”“7，1，6，8，3”“9，8，7，6，5”。用选择排序算法分别对三个序列进行升序排序，比较次数依次为x、y、z，则下列关系正确的是（　　） A．x＝y＝z B．x＞y＞z C．y＞z＞x D．z＞y＞x 6．某电子设备的电路板上有一个6位的“跳板开关”，此开关每一位都只有“打开”和“闭合”两种状态。这个“跳板开关”最多能表示的状态数为（   ） A．120 B．64 C．60 D．6 7．某对分查找算法的VB程序段如下: key=Int(Rnd*20)+3 i=1:j=6:id=1 Do While i<=j     m=(i+j)\2     If key=a(m)Then Exit Do     If key〈a(m)Then         j=m-1:id=id*2     Else         i=m+1:id=id*2+1     End If Loop Labe11. Caption=Str(id) 数组元素a（1）到a（6）的值依次为“4，7，9，14，15，21”，执行该程序段后，标签Labell中显示的内容不可能的是（   ） A．4 B．7 C．13 D．15 8．有如下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 9．某对分查找算法的VB程序段如下： i=1：j=30 m=（i+j）\2 Do While i < = j And key < > a（m）     If key >a（m） Then i = m+1 Else j = m-1     m=（i+j）\2         ① Loop 数组元素a（1）到a（30）各不相同且按升序排列，若查找键key与a（9）相等，执行该程序段，①处语句的执行次数是（    ） A．2 B．3 C．4 D．5 10．下列 VB 程序段的功能为：对数组 a 中的 n 个元素进行排序，生成左右交替上升的数据系列。如排序前 a 中元素依次为：21，33，56，11，44，60，程序运行后  a  中元素依次为：11，33，56，60，44，21。 For i=1 To ① k=i For j=i+1 To n-i+1 If a(k)>a(j) Then k=    ②      Next j If k<>i Then t=a(k):a(k)=a(i):a(i)=t   For j= ③    If a(j) < a(j+1) Then           a(j)=a(j)+a(j+1) : a(j+1)=a(j)-a(j+1):a(j)=a(j)-a(j+1) Next j Next i 上述程序段 3 个划线处的表达式分别为（    ） A．①    n-1    ②    j+1    ③    i To n-i+1 B．①    n-1    ②    j+1    ③    i To n-i C．①    n\2    ②    j    ③    i+1 To n-i D．①    n\2    ②    j    ③    i+1 To n-i+1 11．某VB程序的一个事件处理过程如下： Private  Sub  Commandl_Click（    ） Dim  a（3）As  Integer a（1）=400:a（2）=10:a（3）=30 a（0）=a（2）^2-4*a（1）*a（3） Text1.Text  =  Str（Sqr（a（0））） End  Sub 程序运行时，单击命令按钮Command1后出现的错误提示为（    ） A．下标越界 B．溢出 C．无效的过程调用或参数 D．要求对象 12．某同学使用Python编写了一个解密程序尝试找出某文件密码。调试时，程序顺利运行且没有报错，但最终无法得到正确的密码。造成这个结果的原因可能是（   ） A．程序算法存在逻辑错误 B．Python未安装相应的扩展模块 C．Python运行环境配置有问题 D．程序语句存在语法错误 13．有8阶楼梯，从第0阶开始往上走，每次可以走一步或者两步，自定义函数fg可以计算走完n阶楼梯有多少种走法，程序如下： Function fg(n As Integer)As Integer If n=1 fg=1 If n=2 fg=2 If n>=3 fg=fg(n-1)+fg(n-2) End Function 请问走完这8阶楼梯的走法有（    ） A．34种 B．35种 C．36种 D．37种 14．有如下VR程序段： tail=6:i=1:r=2 Do While i<r For j= tail To i+1 Step-1 If a (j)> a(j-1) Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j i=i+1 For j=i To tail-1    If a(j)<a(j+1) Then t=a(j):a(j)=a(j+1):a(j+1)=t End If Next j tail=tail-1 Loop 数组元素值“73、56、28、61、44、92”，运行程序，数组元素a(1)到a(6)的值依次为（    ） A．73，61，56，92，44，28 B．92，73，56，61，44，28 C．92，73，61，56，28，44 D．92，73，61，56，44，28 15．有如下VB程序段： c=0：i=1 Do While i<=6 k=i For j=i+1 To 7 If a(j)<=a(k) Then k=j Next j If a(i)<>a(k) Then t=a(i)：a(i)=a(k)：a(k)=t c=c+1 End If i=i+1 Loop 数组元素a(1)到a(7)的值依次为“9，9，8，16，45，9，78”。该程序段执行后，变量c的值是 A．0 B．3 C．4 D．6 16．数组b是一个有重复数据的递增数组，现把前面n个元素整体移动到最后形成如“7，8，9，10，1，2，3，4”的排列形式。下列程序实现如下功能：输入一个数，利用对分查找算法在数组b中查找，返回查找结果在Label2输出，若有多个相同数据，则返回最左侧数据的位置。 Dim b(1 To 20) As Integer Private Sub Command1_Click() 　Dim i As Integer, j As Integer, m As Integer 　i = 1: j = 20 　Key = Val(Text1.Text) 　Do While 　　(1)　　 　　m = (i + j + 1) \ 2 　　If b(i) < b(m) Then 　　　If　　(2)　　 Then 　　　　j = m - 1 　　　Else 　　　　i = m + 1 　　ElseIf Key = b(m) Then 　　　Exit Do 　　Else 　　　If Key > b(m) And Key <= b(j) Then 　　　　i = m + 1 　　　Else 　　　　j = m - 1 　　End If 　Loop 　If　　(3)　　 Then 　　Label2.Caption = "数组中无此数" 　Else 　　Do While m > 0 　　　If Key = b(m) Then m = m - 1 Else Exit Do 　　Loop 　　Label2.Caption = "此数在第" + Str(m + 1) + "个位置" 　End If End Sub (1)(2)(3)处可选语句为 ①i > j ②i <= j ③Key < b(m) And Key >= b(i) ④Key> b(m) And Key <=b(j) 则(1)(2)(3)处的语句依次是(　　) A．①③② B．②④① C．②③① D．①④② 17．以下VB程序段用以实现10个数组元素升序排序。 随机生成10个不重复的数据存入数组A中，代码略 要实现上述功能，方框①②中的语句分别是 A．①tmp<a(j-1) ②If j=1 Then flag=true B．①tmp<a(j-1) ②If j=1 Then flag=true C．①tmp<a(j) ②If j=0 Then flag=true D．①tmp<a(j) ②If j=0 Then flag=true 18．请选择与186D相等的数（    ） A．ABH B．11010110B C．B6H D．10111010B 19．有如下程序段： Dim a(1 To 10) As Integer Dim i As Integer, j As Integer, m As Integer Dim key As Integer i = 1: j = 10: key = Val(Text1.Text) Do While i <= j   m = (i + j) \ 2   If key < a(m) Then     j = m - 1   ElseIf key > a(m) Then     i = m + 1   Else     Do While m > 1        If a(m - 1) = key Then         m = m - 1        Else         Exit Do        End If     Loop     Exit Do   End If Loop 数组中a(1)到a(10)依次为“1，1，2，3，3，3，3，4，4，4”，若在文本框Text1中输入值3，经上述程序段执行后变量m的值为 A．7 B．6 C．5 D．4 20．某同学将对分查找程序进行了改编，程序运行时，自动产生9个[10，99]之间的不重复随机数并降序排列，在文本框Text1中显示。在文本框Text2中输入查找键key，单击“查找”按钮Command1，将查找结果显示在文本框Text3中。程序运行界面如图所示。 Key=Val（Text2. Text） i=1 j=9 flag=False Do While i <=j And flag=False     m=（i+j）\2     If      （1）     Then         j=m-1     ElseIf     （2）     Then         i=m+1     Else         If      （3）     Then             j=m-1         ElseIf      （4）      Then             i=m+1         E1se             flag=True         End If     End If Loop If flag Then Text3.Text="在第"+Str（m）+"个"Else Text3.Text="找不到" 上述程序段中方框处可选语句为： ①Key \ 10 > a（m） \ 10    ②Key Mod 10 < a（m） Mod 10 ③Key \ 10 < a（m） \ 10    ④Key Mod 10 > a（m） Mod 10 则（1）（2）（3）（4）处语句依次为（    ） A．①②③④ B．④②①③ C．①③④② D．①②④③ 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题主要考查递归算法。F(4)=F(3)+2*F(2)=F(2)+2*F(1)+2*F(2)=2+2+2*2=8，故本题选A选项。 2．A 【详解】本题主要考查排序算法及VB程序实现。分析程序可知，最后一位数组不参与排序，外层共2次循环，每一次将一个最大值放到最右边（最右端15位置不变），即第一次将78放到倒数第二位，第二次将51放到倒数第三位，故该程序段“加工”后，数组元素a(1)到 a(5)的值依次为36，18，51，78，15，故本题选A选项。 3．A 【详解】本题主要考查冒泡排序算法及VB程序实现。分析程序可知，外循环每执行一次，列表框1中输出一个值，故总共输出3个数，排除C、D选项。该程序是冒泡排序，内循环每执行一次，会将一个最大值放到最左边，故经过该程序段加工后，列表框 list1 中显示的内容是9 7 6，故本题选A选项。 4．B 【详解】 5．A 【详解】本题考查的是选择排序。根据选择排序思想可知，不管数据是否已经有序，部分有序或是无序，选择排序还是要把每个数据都比较过去，最后选择出一个最小的数据（题目为升序），若选择出的这个最小数据本身位置不在第一个位置则进行交换，然后再剩下的数据中继续找到第二个小的数同样，如果不是本身自己第二个位置的数，则交换，依次类推，其总的比较次数为n*（n﹣1）/2次，由于三组数列中均为五个元素，故x＝y＝z故选：A。 6．B 【详解】 7．C 【详解】本题主要考查对分查找算法。key=Int(Rnd*20)+3，key是随机生成[3,22]之间的整数，第一种情况，当key=3，经过程序执行，id=4；第二种情况，当key=21，经过程序执行，id=7；第三种情况，当key=22，经过程序执行，id=15。故执行该程序段后，标签Labell中显示的内容不可能的是13，故本题选C选项。 8．A 【详解】本题主要考查二分查找算法及VB程序实现。查找过程m的值用二叉树表示如下，分析程序可知，当p=m时，f(p)=q，其中p对应二叉树中的节点值（即m的值），q对应查找深度，即对应二叉树中的层，由图可知，数组元素f(1)到f(6)初始为0，执行该程序段后，其值依次是2，3，1，3，2，3，故本题选A选项。 9．B 【详解】本题考查的是对分查找。初始i=1，j=30，m=(i+j)\2=15，数组升序排序。 i=1<=j=30 key<>a(15)成立，key>a(15)不成立，执行j=m-1=14，m=(i+j)\2=7。 i=1<=j=14 key<>a(7)成立，key>a(7)成立，执行i=m+1=8，m=(i+j)\2=11。 i=8<=j=14 key<>a(11)成立，key>a(11)不成立，执行j=m-1=10，m=(i+j)\2=9。 i=8<=j=10 key<>a(9)不成立，跳出循环。故①处语句的执行次数是3次，选项B正确。 10．C 【详解】本题主要考查冒泡排序和选择排序。分析程序可知，内层第一个for循环采用选择排序，每次将一个待排序中的最小元素交换到最左边，内层第二个for循环采用冒泡排序将剩余的待排序中的一个最小元素交换到最右边，因此外层循环i只需循环到n的一半即可完成排序，故①处填n\2。②处当a(k)>a(j)时，更新k的值为j，故填j。③处是从i+1开始到n-i，即除去两端已排好序的元素，故填i+1 To n-i，故本题选C选项。 11．B 【详解】本题考查的是VB程序调试。由a（0）=a（2）^2-4*a（1）*a（3）=-47900，而数组定义的是Integer，取值范围-32768~32767，超出，故提示溢出，选项B正确。 12．A 【详解】本题考查Python程序设计。根据题意，调试时程序顺利运行且没有报错，但无法得到正确密码。这符合逻辑错误的特点。逻辑错误指程序中没有语法错误，可以通过编译、连接生成可执行程序，但程序运行的结果与预期不相符的错误。故选项A正确。 13．A 【详解】本题考查的是递归算法。走到第n阶台阶上有两种方法，分别是从n-1阶以及n-2阶上来，那么站到n-1阶台阶又可以有两种方法，分别是从n-2或者n-3上来，同理n-2阶也有两种方法上来，而站到第1阶只有一种方法，站到第2阶有两种方法，这是一个递归问题。递推式：f（n）=f（n-1）+f（n-2），即计算前两项为1和2的斐波那契数列的第8项。f（3）=f（1）+f（2）=3，f（4）=f（2）+f（3）=5，f（5）=f（3）+f（4）=8，f（6）=f（4）+f（5）=13，f（7）=f（5）+f（6）=21，f（8）=f（6）+f（7）=34。故选项A正确。 14．D 【详解】本题考查的知识点是排序算法的应用。这是进行首尾同时排序。最后数组变为降序数组。故正确答案为D选项。 15．B 【详解】本题主要考查排序算法及VB程序实现。分析程序可知，该程序实现升序排序，每次循环将i右边的数与i处的值进行比较，如果产生了最小的数，则交换a(i)与a(k)，变量c标记交换的次数，8和9交换一次，16和9交换一次，16和45交换一次，故该程序段执行后，变量c的值是3，故本题选B选项。 16．C 【详解】本题考查的是对分查找算法。(1)处是设置查找终止的条件,只要区间还有1个数就要继续找,选i<=j;(2)处判断关键字是否在左侧区间,上一行的If保证左侧区间有序,关键字大于等于i位置,小于中间值,确保在左侧区间,代码选Key < b(m) And Key >= b(i);(3)处判断是否找到,前文在区间为正时退出循环,则肯定已经找到,否则i>j说明找不到. 17．A 【详解】本题考查排序算法的实现，其本质是顺序查找算法，先找到应放入的位置，然后移动后面的数据，在正确的位置放入数据。在查找位置时，从前往后，因为是升序，如果a(i)的值小于a(j-1)，a(j-1)需要后移，a(i)赋值给了tmp，所以应为tmp<a(j-1)。移动时，如果j=1时，表明全部移动完毕，退出循环。故选A 18．D 【详解】本题考查数制转换相关内容。186D为十进制数，转换为十六进制数是BAH，转换为二进制数是1011 1010B。故本题答案是D选项。 19．D 【详解】本题考查的知识点是对分查找数据的方法步骤。对方法查找过程是先将一个数列放于一个升序数组中，然后比较中间数组元素的值与要查找的值，若中间数组元素的值比要查找的值大，则在前半个数组中查找，若中间数组的值比要查找的值小，则在后半个数组中查找。查找方法仍是比较中间数组元素的值和要查找的值。以此类推，直到查到或下限大于了上限（没查到）为止。本题程序分析如下： Dim a(1 To 10) As Integer        ’ 定义一个整型数组a，该数组元素个数为10 Dim i As Integer, j As Integer, m As Integer        ’定义整形变量i， j ，m Dim key As Integer    ’定义整型变量key i = 1: j = 10: key = Val(Text1.Text)     ’给变量i赋值为1，j赋值为10，将文本框1中的数据转为数值型后赋值给变量key，其中i为数组元素下标的下限，j为上限，key为要查找的数 Do While i <= j    ’在数组元素下标的下限小于等于数组元素下标的上限时进行循环   m = (i + j) \ 2     ’m为数组元素下标的中值   If key < a(m) Then    ’在要查找的数小于数组中值时进行如下处理     j = m – 1        ’调整数组元素的上限为中值减1   ElseIf key > a(m) Then        ’在要查找的数大于数组中值时，进行如下操作     i = m + 1        ’调整数组元素的下限为中值加1   Else            ’在要查找的数等于数组中值时进行如下处理     Do While m > 1            ’在m的值大于1时进行循环        If a(m - 1) = key Then        ’如果上一个数组元素的值仍是要查找的数时进行如下处理         m = m – 1                ’将中值调整为上一个数组元素的下标        Else                ’如果上一个数组元素的值不是要查找的数时，进行如下处理         Exit Do                ’退出内层循环        End If                ’结束条件判断     Loop                    ’结束内层do循环     Exit Do                    ’在m的值小于等于1时退出内层循环   End If                        ’结束条件判断 Loop                        ’结束外层循环 由以上分析知本题采用对方查找法进行查找数据，如果查到数据后再看前面（左边）的元素是否仍是要查找的数，如果是则调整中值m，其实质是查找最左边的数的数组元素的下标,本题让查找的数为3，最左边的3的数组元素的下标为4。故正确答案为D选项。 20．C 【详解】本题考查的是对分查找相关知识。阅读程序可知，从高位开始比较，第一次先判断十位的大小，数据是降序排列，由j=m-1可知第一空为：Key \ 10 > a（m） \ 10 ，第二空为：Key \ 10 < a（m） \ 10 ；第二次判断个位，由 j=m-1可知第三空为：Key Mod 10 > a（m） Mod 10，第四空为：Key Mod 10 < a（m） Mod 10。故选项C正确。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$