第四课算法应用举例

第四课 算法应用举例 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．请选择与186D相等的数（    ） A．ABH B．11010110B C．B6H D．10111010B 2．一块存储容量标注为2TB的固态硬盘，大约相当于（   ）块存储容量为256GB的机械硬盘 A．2 B．4 C．8 D．12 3．二分查找实际上就是 的一种典型运用。（   ） A．动态规划法 B．分治策略 C．回溯法 D．递推法 4．二分查找实际上就是（   ）的一种典型运用。 A．动态规划法 B．分治策略 C．回溯法 D．递推法 5．有如下 VB 程序段: i = 1: j = 8: k = 4 Randomize Key = (Int(Rnd * 4) + 20) * 4 Do While i <= j m = (i + j) \ 2 If Key = a(m)  Then Exit Do ElseIf Key < a(m) Then j = m - 1: k = k / 2 Else i = m + 1: k = k * 2 End If Loop 数组元素 a(1)到 a(8)的值依次为 “80,82,84,86,88,90,92,94”，执行该程序段后， 变量 k 的值可能是（   ） A．1,4,8 B．2,4,8 C．4,16,32 D．1,4,16 6．采用冒泡排序算法对数据序列“18,13,15,2,1,20”进行排序，第一轮排序后的结果为“1,18,13,15,2,20”，则完成整个序列的排序交换的次数是（   ） A．6 B．7 C．8 D．9 7．某对分查找算法的 VB 程序段如下： key=Val(Text1.Text) i=1:j=8 Text2.Text=〝〞 Do While i<=j m=Int(i+j)/2) If key=a(m) Then Exit Do    ＇Exit Do 表示退出循环 If key<a(m) Then j=m-1 Else i=m+1 Text2.Text=Str(a(m))+Text2.Text Loop 数组元素 a(1)到 a(8)的数据依次为“12，25，36，47，68，79，87，99”，文本框 Text1中输入的值是 12，执行该程序段后，文本框 Text2 中显示的是（   ） A．68 47 25 12 B．47 25 12 C．68 36 12 D．25 47 8．某查找算法 VB 程序段如下： ans = 0: L  = 0: R = 7 key = 2 ^ (Int(Rnd * 5)) Do While L <= R     m = (L + R + 1) \ 2     If a(m) > key Then         L = m + 1         ans = ans + 1     Else         R = m - 1         ans = ans - 1 End If Loop 数组 a(0)到 a(7)的值依次为 16，16，8，8，4，2，2，1，该程序运行后，ans 的值不可能的是（ ） A．0 B．-4 C．1 D．-1 9．如下VB程序段实现对数组元素a（1）到a（10）从小到大排序。 i=1 Do While i<10 k=i：i=10 For j=10 To k + 1 Step -1 If a（j）<a（j-1） Then     t=a（j）：a（j）=a（j-1）：a（j-1）=1 ① End If Next j Loop 则代码中①处的语句可为（    ） A．i=i+1 B．i=j+1 C．i=k-1 D．i=j 10．数组a中存放了某校田径运动会中7名100米短跑运动员的成绩，数据存放情况如下表： a(1) a(2) a(3) a(4) a(5) a(6) a(7) 12.1 12.3 12.6 12.8 13.0 13.3 13.5 若用对分查找算法查找数值 13.5，则第 2 次查找到的数组元素的下标是（ ）。 A．2 B．5 C．6 D．7 11．某对分查找算法的VB程序段如下： i = 1 : j = 7 : S = "" : key = 3 Do While i<=j m =(i+j)\ 2 If key = a(m) Then S = S + "M" If key < a(m) Then j = m - 1 : S = S + "L" Else i = m + l : S = S + "R" End If Loop Text1.Text = S 数组元素a(1)到a(7)的值依次为1，2，3，3，3，5，8。该程序执行后，文本框Text1中显示的内容是（    ） A．MRLMR B．MLMR C．MLML D．LRLM 12．某对分查找算法的VB程序段如下： 若数组元素a(1)到a(8)的值依次为1，10，11，12，15，30，32，37，执行该程序段后，文本框Text1中显示的内容可能是（  ） A．1 B．3 C．4 D．7 13．有如下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 14．某对分查找算法如下： i=1:j=6:c=1 key=int（rnd*100+1） do while i <= j m=（i+j）\2 c=c+1 if key<d（m）then j=m-1 else i=m+1 1oop 数组d（1）~d（6）的值分别为“17，21，29，32，39，75”，则程序运行结束后，下列说法错误的是（    ） A．i=j+1是成立的 B．若key=21，则i=1 C．当key=32时，m=j是成立的 D．若key如果是38，那么m=4 15．已知数组a(1)到a(n)为非递减序列，使用对分查找算法在数组中查找最后一个不大于key的元素下标，若a(1)>key，则在Text2框中输出0。实现该算法的VB程序段如下： key=Val(Text1. Text) ① Do WhileL < R m=(L+R+1)\2 If a(m) < = key Then ② Else ③ End If Loop Text 2. text= ④ 以下说法正确的是（    ） A．①处可填写代码L=1:R=n B．②处可填写代码L=m+1或L=m C．③处可填写代码R=m-1或R=m D．④处可填写代码L或R 16．某对分查找算法如下 i=1:j=1000:p=0:n=1000 Key=val(textl. text) Do while i＜j m=(i+j)\2 p=p+1 If a(m)>key then j=m-1 else i=m+1 Loop Text2.text=str(n-i+1) 数组元素a（1）到a（1000）中存放的升序排列数据，下列说法正确的是（    ） A．若key的值小于a（1），则执行该段程序后，变量i的值等于0 B．若key的值大于a（1000），则执行该段程序后，变量i的值等于1001 C．若key的值等于a（1），则执行该程序后，变量p的值等于10 D．在文本框Text2中输出大于key的数据个数 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查数制转换相关内容。186D为十进制数，转换为十六进制数是BAH，转换为二进制数是1011 1010B。故本题答案是D选项。 2．C 【详解】本题考查存储容量相关内容。存储单位：1TB=1024GB；1GB=1024MB；1MB=1024KB；1KB=1024B；B是Byte（字节）的简写，一个字节就是8位（bit），在ASCII表中一个英文字母占用一个字节。2TB=2048GB，2048/256=8，故本题答案是C选项。 3．B 【详解】本题主要考查二分查找算法。二分查找实际上就是分治策略的一种典型运用，所谓分治策略，就是把规模大的问题分成若干个规模小的问题来解决，最后把各自的结果再合并，故本题选B选项。 4．B 【详解】本题主要考查二分查找算法。二分查找实际上就是分治策略的一种典型运用，所谓分治策略，就是把规模大的问题分成若干个规模小的问题来解决，最后把各自的结果再合并，故本题选B选项。 5．D 【详解】本题主要考查对分查找算法及VB程序实现。分析代码，根据对分查找思想，结合二叉树，全部k的取值有：1，2，4，8，16，32。由代码Key = (Int(Rnd * 4) + 20) *4，可知随机产生的数key为“80，84，88，92”，找到80，84，88，92时K的值分别为1，4，4，16，故本题选D选项。 6．D 【详解】本题主要考查冒泡排序算法。采用冒泡排序算法对数据序列“18,13,15,2,1,20”进行排序，第一轮排序后的结果为“1,18,13,15,2,20”，可知进行的是升序排序，每次将一个最小值放到最左边，从右边开始比较交换。第一次，1分别与2、15、13、18进行交换，得到“1,18,13,15,2,20”；第二次，2分别与15、13、18进行交换，得到“1,2,18,13,15,20”；第三次，13与18进行交换，得到“1,2,13,18,15,20”；第四次，15与18进行交换，得到“1,2,13,15,18,20”，此时已有序，排序结束，完成整个序列的排序交换的次数是4+3+1+1=9，故本题选D选项。 7．D 【详解】本题主要考查对分查找算法。key=12，i=1，j=8，第一次循环，m=Int(1+8)/2)=4，a(4)=47>key，j=m-1=3，Text2.Text=Str(a(m))+Text2.Text="47"；第二次循环，m=Int(1+3)/2)=2，a(2)=25>key，j=m-1=1，Text2.Text=Str(a(m))+Text2.Text="47 25"；第三次循环，m=Int(1+1)/2)=1，a(1)=12=key，退出循环，故执行该程序段后，文本框Text2 中显示的是25 47，故本题选D选项。 8．A 【详解】本题考查的是对分查找。Int(Rnd * 5)取值范围是0-4的整数，故key的值可能为：1、2、4、8、16。当key值为1时，ans=1；当key值为2时，ans=-1；当key值为4时，ans=1；当key值为8时，ans=-1；当key值为16时，ans=-4。故不可能为0，本题应选A。 9．D 【详解】本题考查的是VB排序。阅读程序可知，这是冒泡排序的变式，从后往前开始冒泡，每次交换完后，要记录下当前最小值得下标，如果当前比较后最小值下标为10，表示排序结束。故①处的语句可为i=j。选项D正确。 10．C 【详解】本题主要考查对分查找算法。对分查找执行过程为：1、将数组排序(从小到大)；2、每次跟中间的数mid比较，如果相等可以直接返回， 如果比mid大则继续查找大的一边，否则继续查找小的一边。按照上述提示，第1次查找时比较的数组元素下标为4，第二次为6，因此C选项正确。 【点睛】 11．A 【详解】本题主要考查对分查找算法的程序实现。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果或查找结束。题中a数组元素为1，2，3，3，3，5，8，查找键为3，则文本框Text1输出为MRLMR，因此A选项正确。 【点睛】 12．C 【详解】本题主要考查对分查找算法。Rnd是随机生成[0,1)之间的数，Int(x)是返回不大于x的最大整数，key=Int(Rnd*15+1)*2是随机生成[2,30]之间的偶数，第一次循环，m=(1+8)\2=4，a(4)=12，由数组元素值进行分类，第一种情况，当key<=10，执行完后low=2；第二种情况，当key=12时，执行完后low=4；第三种情况，当key=14时，执行完后low=5；第四种情况，当15<key，执行完后low=6，故本题选C选项。 13．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正确。 14．B 【详解】本题主要考查对分查找。此题需要画出二叉树。数组为递增的有序数列，根据算法要求有可能出现i=j+1，因此A选项正确；key=21时，发生指针跳转，因此B选项符合题意；key=32时，m=3，i=m+1，然后m=5，j=m-1，然后m=4，m=j成立，因此C选项正确；key=38时，根据算法要求，查找失败，且m=4，因此D选项正确。 【点睛】 15．D 【详解】本题主要考查对分查找算分。①处是初始化L和R，由m=(L+R+1)\2，可知，此处填写代码是L=0，R=n。②如果a(m) < = key，则key在右边，故此处填L=m。③如果a(m) > key，则key在左边，故此处填R=m-1。④循环结束完，即找到最后一个不大于key的元素下标，即L或R，故此处填L或R，故本题选D选项。 16．D 【详解】本题主要考查对分查找算法。i的初始值为1，若key的值小于a（1），则执行该段程序后，变量i的值不变，j=0，选项A说法错误；若key的值大于a（1000），则执行该段程序后，变量i的值等于1000，选项B说法错误；若key的值等于a（1），则执行该程序后，变量p的值等于9，i=j=2，选项C说法错误；位置i即为key的位置，故n-i+1为在文本框Text2中输出大于key的数据个数，故本题选D选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$