信息技术选考对分查找

16/16DACCCBDAB某对分査找算法的VB程序段如下:PriateSubComand_Clck()Dimd(1to1)AsInege,iAsIntger,jAsInege,mAsIntgerDimKeyAsIntger,sAsStingKey=IntRnd*50+1)s="":i=1:j=10DoWhiei<jm=(i+j)\2IfKey=d()ThenExitDo IfKey<d()Thenj=m:s=s+"L"Elsei=m+1:s=s+"R"EndIfLoopLabl.Capion=sEndSub若数组元素d(1)到d(10)的值依次为“3，8，9，15，26，28，32，37，45，49”，执行该程序段后，标签Label1上显示的字符串s出现字母“L”和“R”个数相同的情况有A．1种 B．2种 C．3种 D．4种7如图a所示，已有若干学生从1开始编号，在文本框Text1中输入新增的学生姓名，填补到空缺的学号(2、3、6、11)位置。填补规则：从最小号开始依次填补。单击“新增”按钮后在列表框List1中完整显示所有学生信息，如图b所示。实现上述功能的VB代码如下，但加框处有错，请改正。DimnAsInteger′学生人数Dima(1To100)AsInteger′存储学生的学号Dimb(1To100)AsString′存储学生的姓名PrivateSubForm_Load()′从数据库中读取学生学号、学生姓名和总人数，分别存储在数组a、数组b和变量n中，代码略。EndSubPrivateSubCommand1_Click()DimLAsInteger,RAsIntegerDimmAsInteger,keyasStringkey＝Text1.TextL＝1:R＝nDoWhileL<＝Rm＝(L＋R)\'2Ifeq\x(a（m）<key)Then′(1)L＝m＋1ElseR＝m－1EndIfLoopFori＝eq\x(nTomStep－1)′(2)a(i＋1)＝a(i)b(i＋1)＝b(i)Nextin＝n＋1a(i＋1)＝Lb(i＋1)＝Key′插入后的结果显示在列表框List2，代码略。EndSub8．查找最接近的数。编写一个查找最接近数的VB程序：程序运行时，在文本框Text1中输入产生随机数的个数(1到100之间)，单击命令按钮“产生随机数并升序排列”后，在列表框List1中显示已经按升序排列后的随机整数。然后在文本框Text2中输入要查找的整数，单击命令按钮“查找”后，在标签Label3中显示随机整数序列中与待查找数最接近的整数(当最接近的数有2个时，输出较大的一个)。程序运行效果如图所示。实现上述功能的VB代码如下，请在划线处填入合适代码。DimnAsInteger′存储随机数的个数Dimf(1To100)AsBoolean′f(i)为true时表示随机整数i已经产生过Dima(1To100)AsInteger′依次存放升序排序后的n个随机数PrivateSubCommand1_Click()′命令按钮”产生随机数并升序排列”的单击事件DimiAsIntegerRandomizeFori＝1To100f(i)＝FalseNextin＝Val(Text1.Text)Fori＝1Tont＝Int(Rnd*100＋1)DoWhilef(t)＝Truet＝Int(Rnd*100＋1)Loop____①____Nextij＝0Fori＝1To100′实现排序并输出Iff(i)＝TrueThenj＝j＋1a(j)＝____②____List1.AddItemStr(i)EndIfNextiEndSubPrivateSubCommand2_Click()′命令按钮”查找”的单击事件DimkeyAsIntegerkey＝Val(Text2.Text)Ifkey<＝a(1)ThenLabel3.Caption＝Str(a(1)):ExitSubIfkey>＝a(n)ThenLabel3.Caption＝Str(a(n)):ExitSubL＝1:R＝nDoWhileL<＝R′找到与key较为接近的两个数a(R)和a(L)9．数组a中存储的是一组正整数，特征是：①以三个数为一组的话，每组中任意一个数都比前面一组中的任意一个数要大；②每组中三个数依次递减；③数组中数的总个数为3的倍数。依据对分查找思想，设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下，但加框处代码有错，请改正。PrivateSubCommand1_Click()Constn＝15Dima(1Ton)AsInteger,searchAsInteger,keyAsIntegerDimiAsInteger,jAsInteger,mAsInteger′读取一组正整数，按上述规则存入数组a中，代码略。key＝Val(Text1.Text)i＝1:j＝n:search＝0DoWhilei<＝jm＝(i＋j)\2IfmMod3<>0Thenm＝m－2′(1)把m调整到三个一组的最后一个数的位置Ifkey＝a(m)Thensearch＝m:ExitDoElseIfkey<a(m)Thenj＝m－3ElseIfkey<＝a(m－2)Then′(2)i＝m＋1ElseIfkey＝a(m－2)Thensearch＝m－2:ExitDoElseIfkey＝a(m－1)Thensearch＝m－1:ExitDoElsesearch＝0:ExitDoEndIfLoopIfsearch<>0ThenText2.Text＝Str(search)ElseText2.Text＝”找不到”EndIfEndSub10．“轮转后有序数组(RotatedSortedArray)”是将有序数组取其中某一个数为分割点，将其之前的所有数都轮转到数组的末尾所得。比如{7，11，13，17，2，3，5}就是一个轮转后的有序数组，原有序数组中的子串{2，3，5}被轮转到了数组的末尾处。对于一个轮转后有序数组arr也可以进行二分查找，算法思路如下(以升序为例)：每次根据查找的左侧位置L和右侧位置R求出中间位置M后，M左边[L，M]和右边[M＋1，R]，这两部分中至少一个是有序的(可根据中间位置数据和边界数据的大小关系判断)。arr[M]和待查找数据Key比较①arr[M]＝Key，返回M的值②若M位置的右侧有序，当待查找数据在右侧，则下次在右侧查找，否则在M左侧查找③若M位置的左侧有序，当待查找数据在左侧，则下次在左侧查找，否则在M右侧查找(1)对于轮转后有序数组{7，11，13，17，2，3，5}使用以上函数search()查找key值3，所需要的查找次数为__________。(2)以下VB函数Search()实现了对轮转后有序数组arr进行二分查找的过程，如果查询成功，返回m值，查询失败则返回－1。请补充程序中①②③划线处的代码：FunctionSearch(keyAsInteger,LAsInteger,RAsInteger)AsInteger______①____DoWhileL<＝RAndSearch＝－1M＝(L＋R)\'2Ifarr(M)＝keyThenSearch＝MElseIf____②____ThenIfarr(L)<＝keyAndkey<arr(M)ThenR＝M－1ElseL＝M＋1EndIfElseIf____③____ThenL＝M＋1ElseR＝M－1EndIfEndIfEndIfLoopEndFunction11.(2018·11月浙江选考)数组a中存储的是左右交替上升的n个正整数，如下表所示：a(1)a(2)a(3)……a(n－2)a(n－1)a(n)32538……553112依据对分查找思想，设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下，但加框处代码有错，请改正。桶排序优化。桶排序的思想是根据数组中各元素的值，依次放入相应编号的桶中，最后按顺序输出桶中数据，即可完成排序。例如：数据10、15、8、9、3，桶中的顺序如下表：但是，当数据范围很大时，需要的桶则非常多，会造成很大的资源浪费。为了解决该问题，小张对桶排序进行了优化，算法思想如下：①先依据数组中元素的个位进行桶排序；②再依据数组中元素的十位进行桶排序；直到排序完成。例如：有数组a中各元素分别为53，3，542，748，17，214，154，63，616，第一趟按个位排序过程如下：①个位填入相应桶编号中，并统计每个桶中数据个数。②计算索引。计算方法是从前往后，依次计算当前桶中元素个数与前一项之和。③按索引从桶中倒序取出数据，每取一个索引减1。重新排列后为542，53，3，63，214，154，616，17，748。接下来对重新排序后的数据以十位、百位依次进行桶排序即可完成排序(每一趟排序后数据重新排列)。（1）第二趟以十位排序后的结果中，前4个数为_____。（数字间用逗号间隔）（2）现在有n个0～5000的数据，其VB代码如下，请在划线处填入合适的代码。Constn＝10Dima(1Ton)AsIntegerDimtmp(1Ton)AsInteger'临时数组，用来保存桶排序后的结果Dimcount(0To9)AsIntegerDimiAsInteger,jAsIntegerDimsAsInteger,kAsIntegerPrivateSubForm_Load()'待排序数据保存在a数组中，代码略EndSubPrivateSubCommand1_Click()s＝1Fori＝1To________Forj＝0To9'初始化数组count(j)＝0NextjForj＝1Ton'统计各桶中数据个数k＝(a(j)\s)Mod10count(k)＝count(k)＋1NextjForj＝1To9'计算索引count(j)＝__________NextjForj＝nTo1Step－1'根据索引，从桶中取出数