2019浙江选考信息技术查找算法专题

1、(一)顺序查找1顺序查找算法 顺序查找算法的处理过程假定在数组d中有n个数据，查找关键值已经存储在变量key中。其处理过程是: 从数组d的第1个元素d(1)开始，依次判断各元素的值是否与 key相等，若某个数组 元素d(i)的值等于key，则结束处理(找到了指定的数据)；若找遍了所有的n个元素, 无任何元素的值等于key，则结束处理(输出未找到信息)。 顺序查找算法流程图与程序结构(二)对分查找1. 对分查找的过程若key为查找键，数组d存放n个已按升序排序的数据。在使用对分查找时，把 查找范围i，j的中间位置上的数据d(m)与查找关键值key进行比较，结果必然是如 下三种情况之一：(1) 若

2、keyvd(m)，查找key小于中点m处的数据。由数组d中的数据的递增性， 可以确定：在(m，j)内不可能存在值为key的数据，必须在新的范围(i，m -1)中继续 查找；(2) key = d(m)，找到了需要的数据；key>d(m)，由与(1)相同的理由，必须在新的范围(m + 1，j)中继续查找。这样，除了出现情况 ，在通过一次比较后，新的查找范围将不超过上次查找范 围的一半。以规模为16的递增数组d为例，观察对分查找的过程。要查找的数据key为37。-T 9 I" EP * 6 41 J- b- .1 !. "1 目加15吋叭1使用流程图描述对分查找的算法如下

3、图所示:2对分查找算法程序的实现Private Sub Comma nd1_Click()i = 1: j = nDo While i < = jm = (i + j) 2If d(m) = Key Then'输出结果，退出查找(代码略)ElseIf Key < d(m) The nj = m 1Elsei = m + 1End IfLoopEnd Sub注意：中间位置数据d(m)的下标m的常见计算方法：m = (i + j)2、m = int(i+ j)/2)、m = fix(i + j)/2)、m = fix(i + j)/2+0.5)上面对分查找的算法用一个块if语句

4、实现，也可以用其他等价的方式：IF和一个块1F诸旬实现二卜J H悟旬实现i 1: i n: s 0i - 1: i n: s 0Do 鞘hi2 i <二 jDoi <= jii - (i * j) 2m = i + j) 2If a(n.) - i： txit DaIf-ley TIieii、一 ci： E>it lkiIf key < afu) The*1 f ke < aiki) Then J = rj - Ij in - 1If kz > a (iC Uku i 'i + 1EKeLnnpi = in + 1End IfLoop3 查找次数的估

5、算对规模为n的数组进行对分查找时，无论是否找到，至多进行log2n + 1次查找就 能得到结果，平均查找次数计算：（第1个数据需要的查找次数+第2个数据需要的查 找次数+第n个数据需要的查找次数）/n而使用顺序查找算法，在最坏的情况下（查 找键在最后一个或没找到），需要进行n次查找，最好的情况是一次查找（查找键在第 一个），平均查找次数是1、(2018.4)数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i = 1: j = 10Key = Val(Text1.T ext)Do While

6、 i <= jm = (i + j) 2If a(m) = Key The n Exit Do 'Exit Do 表示退出循环If Key Mod 2 = 1 And a(m) Mod 2 = 0 The n(1)ElseIf Key Mod 2 = 0 And a(m) Mod 2 = 1 The n(2)Else(3)End IfLoopIf i > j Then s ="没有找至U! " Else s ="位置："+ Str(m)Text2.T ext = s上述程序中方框处可选语句为： i = m + 1 j = m - 1

7、If Key < a(m) The n j = m - 1 Else i = m + 1则(1)、(2 )、(3)处语句依次是A. 、B 、 C、D 、2、 (2017.11)某对分査找算法的 VB程序段如下：i = 1: j = 7: s =""key = In t(R nd * 100)Do While i <= jm = (i + j) 2If key = a(m) The ns = s + "M": Exit Do 'Exit Do 表示退出循环ElseIf key < a(m) The nj = m - 1: s =

8、s + "L"Elsei = m + 1: s = s + "R"End IfLoopText1.T ext = s数组元素a(1)到a (9)的值依次为“ 24, 35, 38, 41, 45, 69, 78”。若该程序段执 行后，文本框Text1中显示的内容可能是A. RLB. LMRC. RLRD. LRLM3、(2017.4)某对分查找算法的VB程序段如下：key = Val(Text1.Text)i = 1: j = 10Text2.Text =""Do While i <= jm = In t(i + j) / 2

9、+ 0.5)If key = a(m) Then Exit Do'Exit Do 表示退出循环If key < a(m) The n j = m - 1 Else i = m + 1Text2.T ext = T ext2.T ext + Str(a(m)Loop数组元素a到a(10)的值依次为“8,17,24,30,36,40,55 ,58,61,66”，文本框Text1中输入的值是30,执行该程序段，文本框Text2中显示的是A. 40 24B. 40 24 36 C. 36 24D. 36 17 244、(2016.10)某对分查找算法的 VB程序段如下：i = 1: j

10、= 9 : n=0key = Val(Text1.Text)Do While i <= jN=n+1m = fix(i + j) / 2)If key = d(m) Then Exit DoIf key < dm) The n j = m - 1 Else i = m + 1Loop数组元素d(1)到d(9)的值依次为“ 7,12,18,25,39,58,61,72,86 ”，若该程序段运行结束 后，n的值为2,则key的值是A.39 B. 18 或 61C.18 或 72 D. 12 或 615、(2016.4 )已知一无序数组a (下标1到n )，通过引入数组b (下标1到n)

11、，使得a(b(1) < a(b(2) < a(b(3)< a(b(n)(示如图所示)，对这些有序数据可进行对分查找。 第一次查找时，中点位置m与中点值分别是A. m的值是Fix(1+ n)/2),中点值是B. m的值是Fix(1+ n)/2),中点值是C. m 的值是 Fix(b(1)+b(n)/2),a(m)a(b(m)>=C>引入散烟b麻ihi) aitXi)12234434451務例 则中点值是a(m)D. m 的值是 Fix(b(1)+b(n)/2),中点值是 a(b(m) 6、( 2015.10)已知单调函数f(x)在0，1区间存在一个X。，使f(x。)

12、0。现用对分查找法搜索X。的值，开始搜索区间为0，1，若经过10次对分查找后还需继续搜索，则 第11次搜索区间的长度为A.1/2B. 1/10C. 1/10替换结杲；D. 1/2107、(2017.4)小王编写了一个实现文字查找替换功能的VB程序，运行界面如图所示。文本框Text1显示原文内容，Text2中输入查找内容，Text3中输入替换内容，单击“全 部替换”按钮Command1后，Text4显示查找替换的结果，Text5中显示替换的次数， Text6显示“查找内容”在原文中的起始位置。Text 1匚X原文内容:&重 用布 1 徒一 得，口 is 曹交冃为 硃府已 sra -, 星

13、"息 Is目要Text2晉换为：01咋童捞內答； 8 *Text4Text5替换廣聲： >原交中的起始位畫:冃为 殊府已 建B1 -, 悬，息 IE1目姜i 用布 1 S 广甲 1实现上述功能的VB程序如下，但加框处代码有错，请改正Private Sub Comma nd1_Click()Dim s As Strin g, resule As String, pos As Stri ngDim count As Integer , i As Integeri = 1: count = 0resule = "": pos =""Do Whi

14、le i <= Len(T ext1.Text)s = Mid(Text1.T ext, i, Len(T ext2.T ext)If s = Text2.Text The nresult = result + T ext3.Textcount = count + 1pos = pos + Str(co unt) i = i + Len(T ext2.Text) Elseresult = result + Text2.Texti = i + 1End IfLoopText4.T ext = resultText5.T ext = Str(cou nt)Text6.T ext = posE

15、nd Sub1、按钮command1的鼠标事件处理过程如下：Private Sub Comma nd1_Click()Dim st(1 To 6) As Stringst(1) = "she":st (2) = "her":st(3) = "your"st="me":t(5) = "you":st(6) = "i"Key = text1.T extt = Falsei = 0Do While i < 6 And t = Falsei = i + 1If st(i) =

16、Key The n t = TrueLoopIf t = flase The n i = 0text2.T ext = Str(i)End Sub程序运行时，在文本框中输入“ you”后单击按钮command1后，在文本框text2中 显示的内容是()A.0B.1C.5D.72、 某8位男生的肺活量数据放在数组a( 1 )到a( 8 )中，其数据依次为“ 3104,3700,3058,3222,3621,3329,4233,4540 ”。使用顺序查找算法查找数据 3339， 则共需查找次数为()A.0B.1C.8D.93、有以下两组数据： 54,31,43,12,8,73,56,34,89,6

17、0,23,67 87,83,75,70,63,59,55,37,33,21,17,7下列有关查找方法描述不正确的是()A.可以直接使用对分查找B.可以直接使用对分查找C.可以直接使用顺序查找D.可以直接使用顺序查找4、 某8位男生的肺活量数据放在数组a( 1 )到a( 8 )中，其数据依次为“ 3205,3408,3471,3498,3621,3829,4233,4540 ”。使用对分查找，设定查找键 key，若 第一个被访问到的数据是3498，小于key值，则第二个被访问到的数据是()A.3408B.3829C.4233D.45405、某对分查找算法的vb程序段如下：i = 1: j = 9

18、: n = 0Key = Val(Text1.T ext)Do While i <= jn = n + 1m = Fix(i + j) / 2)If Key = d(m) Then Exit DoIf Key < d(m) The n j = m - 1 Else i = m + 1Loop数组元素d(1)到d(9)的值依次为“ 7,12,18,25,39,58,61,72,86 ”。若该程序段运行 结束后，n的值为2，则key的值是()A.39B.18 或 61C.18 或 72D.12 或 616、数组元素d到d(10)的值依次为“ 60,51,49,45,40,31,20,1

19、0,5”，用对分查找找到49的过程中，依次被访问到的数据是()A. 49B.40 49C.40 45 49D.40 51 497、下列有关查找的说法，正确的是()A进行顺序查找时，被查找的数据必须是有序的B. 在任何情况下，顺序查找比对分查找的查找次数要多C进行对分查找时，被查找的数据可以是有序的，也可以无序的D对规模为n的有序数据进行对分查找，最多查找的次数是log 2n+18、某查找算法的部分VB程序代码如下：Key=Val(Text1.Text)i = 1: j = 9: k = 0Do While i <= jk = k + 1m = in t(i + j)/2+0.5)If k

20、ey = a(m) The n Exit DoIf key < a(m) The n j = m - 1 Else i = m + 1LoopText2.Text=str(k)数组元素a(1)到a(9)的数据依次为“ 10，15，36, 49，55，62，88，92， 99”，该程序运行过程中，文本框Text2中显示的值为2，文本框Text1中输入值可 能是()A.88B.62C.92D.159、某对分查找算法的VB程序段如下：i=1: j=6: n=0: f=Falsekey=val(Text1.Text)Do while i<=j and f=Falsen=n+1m=(i+j)

21、2If key=d(m) the n f=TrueIf key<d(m) the n j=m-1 Else i=m+1Loop数组元素d(1)到d(6)的值依次为“ 13，18，25，30，35，59”。文本框Text1中输 入33后运行该程序，运行结束后下列说法不正确.的是()A.变量f的值为FalseB.变量i的值为5C. 变量m的值为4D.变量n的值为210、有如下程序段：i = 1: j = 6: s = "": key = T ext1.TextDo While i <= jm = In t(i + j) /2 + 0.5)s = s + "

22、 " + a(m)If a(m) > Key The ni = m + 1Elsej = m - 1End IfLoopTextl.T ext = s数组元素 a (1)到 a (6)的值依次为"Beijing"、"Guangdong"、"Jiangsu"、"Jiangxi"、 "Shanghai"、"Zhejiang"，已按字典序排序。当key的值为"Zhejiang"时，单击命令按钮 Command1，文本框Text1中显示的内容为()

23、A. JiangxiZhejiang ZhejiangB. JiangsuShanghaiJiangxiC. Jia ngxiZhejia ngShan ghaiD. Jia ngsuShan ghaiZhejia ng11、某对分查找算法的VB程序段如下：key = Val(Text1.Text)i = 1: j = 10Text2.Text =""Do While i <= jm = In t(i + j) / 2 + 0.5)If key = a(m) Then Exit Do 'Exit Do 表示退出循环If key < a(m) The n

24、j = m - 1 Else i = m + 1Text2.T ext = T ext2.T ext + Str(a(m)Loop数组元素 a(1)到 a(10)的值依次为“ 8,17,24,30,36,40,55,58,61,66”，文本框 Text1 中输入的值是30,执行该程序段，文本框Text2中显示的是()A. 40 24B. 40 24 36C. 40 24 36 30D. 36 17 2412、 下列程序执行后文本框Text1显示的内容是()s = "ERROR:Divisor must not be zero!" flag = False : m = 0Fo

25、r i = 1 T o Len(s)ch = Mid(s, i, 1)If ch >= "a" A nd ch <= "z" The nIf Not flag The nm = m + 1: flag = TrueEnd IfElseflag = False End IfNext iText1.T ext=Str(m)C. 6 D. 19A. 4 B. 5 13、编写一个技术成绩查询的 VB程序。程序功能如下：在文本框Text1中输入分数key（0-50的整数），单击“查询”按钮Command1，查询出信息成绩大于等于 key的 所有记录，并

26、以“信息”为主要关键字、“通用”为次要关键字均进行降序排序，结果输出在列表框List2中。运行界面如下图所示实现上述功能的 VB程序如下，请回答下列冋题：(1)观察上图，排序后第 5位的学生姓名是 (2)请在划线处填入合适的代码Dim xm(1 T o 600)Dim xx(1 To 600)Dim ty(1 T o 600)Dim n As In tegerAs String'存储学生姓名As In teger'存储信息成绩As In teger'存储通用成绩'存储记录总数Private Sub Form_Load()List1中显示,代码'本过程从数

27、据库中读取学生数据，存储在相应的变量中，并在 略End subPrivate Sub Comma nd1_Click()Dim key As Integer, mid As IntegerDim i As Integer, L As Integer, R As Integer, k As IntegerDim tmp1 As Stri ng, tmp2 As In teger'以“信息”为主要关键字、“通用”为次要关键字排序For i = 1 T o n - 1k = iFor j = i + 1 T o nIf xx(k) < xx(j) orThenk = jEnd IfNe

28、xt jIf k <> i The ntmp1 = xm(k) : xm(k) = xm(i) : xm(i) = tmp1 tmp2 = xx(k): xx(k) = xx(i): xx(i) = tmp2tmp2 = ty(k): ty(k) = ty(i): ty(i) = tmp2End IfNext i '查询记录key = Val(Text1 . Text) L = 1: R = nDo While L <= Rmid = (L + R) 2IfThe nL = mid + 1ElseR = mid - 1End IfLoopList2 . Clear&#

29、39;vbTab相当于是键盘上制表符 TAB按键的功能List2 . Additem "姓名"& vbTab & "信息"& vbTab & "通用"For i = 1 to List2 . Additem xm(i) & vbTab & xx(i) & vbT ab & ty(i)Next iEnd sub14、 要求从某一个字符串中删除指定的字符(假设所含的英文字母均为小写字母)，并 将处理后的字符串重新输出。程序界面如图所示，在文本框text_1中输入原始字符串，

30、在文本框text_2中输入需要删除的字符，单击“删除此字符”按钮(command1 )后, 在文本框text_3中输出处理后的结果，相应的 vb程序如下：Private Sub Comma nd3_Click()Dim p As Stri ng, k As Stri ngDim i As Integer , result As Stringresult =""p = text_1.Textk = text_2.TextFor i = 1 T o Len(p)If Mid(p, i, 1) <> k The nresult = result + End IfNex

31、t iEnd Sub(1) 解决此问题的算法是 (选填：顺序查找 或对分查找)(2) 在程序处，填入适当的语句或表达式，把程序补充完整。在程序出填入：在程序出填入：15、小王设计了学校食堂学生IC卡查询系统，输入学生的卡号，可以查出该卡号对应的余额。所有学生的IC卡号和相应的余额已分别保存在数组stu (按从小到大排序)和数组money中，第i个学生的卡号保存在stu( i)中，对应的卡号余额保存在 money(i)中。程序界面如图所示，左边列表框 List1中显示的是部分学生的卡号和余额， 在文本框Text1中输入学生的IC卡号，单击“查询余额”按钮(Command1 )后，如 果找到此卡号

32、，则在标签Lab3中显示“此卡号余额为”和卡号对应的余额值，如果未 找到则显示“找不到此卡号”，请重新输入。环崔余额志（单位：元12211463 -7122121211122131.63.g12214209.612215393.012216246212217&7<IEZ18385.512219328a12220277312Z211918122223S711眇於3朋4Jtk清输扎H卡卡是:j查询余颤解决此问题的部分程序段如下:Const n = 1500Dim stu(1 T o n) As LongDim money(1 T o n) As SinglePrivate Sub F

33、orm_Load()此过程用于对数组stu和数组money进行初始赋值，代码略End SubPrivate Sub Comma nd1_Click()Dim x As Lon g, i As Long, j As Long, m As Long, find As Boolea n x = Val(Text1.Text)j = nfind = FalseDo While i <= j And Not findIf x = stu(m) The n ElseIf x < stu(m) The n j = m - 1Elsei = m + 1End IfLoopIf find ThenL

34、ab3.Caption ="此卡号余额为"+ Str（money（m） + "元"ElseLab3.Caption ="找不到此卡号，请重新输入"End IfEnd Sub（1） 解决此问题的算法是 （选题：对分查找或顺序查找）（2）在程序划线出填入适当的语句或表达式，将程序补充完整： 16、对于无序数组a (下标1到n),通过引入数 组b (下标 1 到n)使得a(b(1) Wa(b(2) < a(b(3)< a(b(n)。小王编写了一个VB程 序,功能如下：在列表框Listl中显 示i、a(i)、 b(i)、a(b(i

35、),在文本框Textl输入要查找的数 据，单击“查找”按钮Command1后，在标签 Label3中显示该数据在a数组中的位置。程 序运行界面如图所示实现上述功能的VB程序如下，但加框处代码有错，请改正。Dim a(1 to 8) As In teger,b(1 to 8) As In tegerDim n As In tegerPrivate Sub Form_Load()'n=8,对分查找前的8个数据存储在a数组中，每个数据的位次存储在b数组中 '在列表框List1中显示数组下标、a数组、b数组、a(b(i)数组'代码略End SubPrivate Sub Comm

36、a nd1_Click()Dim i As In teger, j As In teger, k As In teger Dim m As In teger, key As In tegerkey = Val(Text1.Text) i = 1:j = nDo While i <= jm = (i + j) 2 k =a(m) If key = k Then Exit Do ElseIf key > k Then i = m + 1 Elsej = m - 1 End IfLoopIf i > j Then Label3.Caption="该数据不存在"E

37、lseLabel3.Capti on =s|tr(m)End IfEnd Sub【巩固训练-变式题】1、对数组a中6个有序数据“ 11, 22, 33，44，55, 66 ”用下面的程序代码查找数据“23” 程序执行完毕后，下列各变量值正确的是()Dim a(1 To 6) As In tegerDim i As Integerj As Integer, Key As Integer,m As Integera(1) = 11: a(2) = 22: a(3) = 33: a=44: a(5) = 55: a(6) = 66i = 1: j = 6: p = 0: Key = 23Do Whi

38、le i <= j p = p+ 1m = (i + j) 2If j Mod 2 = 0 The n m = m + 1If a(m) = Key Then Exit DoIf Key < a(m) The n j = m - 1 Else i = m + 1LoopA. i=5B. j=4C. m=3D. p=22、有以下VB程序段()a(1) = 6: a(2) = 8: a(3) = 7: a=3a(5) = 1: a(6) = 2: a(7) = 5: a(8) = 4i = 1: j = 8key = a(1)Do While i<jDo While i <

39、 j And a(j) >= keyj = j - 1Loopa(i) = a(j)Do While i < j And a(i) <= keyi = i + 1Loopa(j)=a(i)Loopa(i) = keyFor i = 1 To 8Label1.C aptio n = Label1.C apti on + " " + Str(a(i) Next i执行该程序段，标签Label1上显示的内容是A. 1 2 3 4 5 6 7 8B. 8 7 6 5 4 3 2 1C. 4 5 2 3 1 6 7 8D. 45 1 3 2 6 7 83、某对分查找

40、算法的VB程序段如下：i = 1j = 7s =""Do While i <= jm = (i + j) 2If a(m) = Key The n s = "E" Exit DoElself a(m) > Key Thenj = m Ts = "L"Elsei = m + 1s = "R"End IfLoop数组元素a到a(7)的值依次为“ 25,42,53,66,77,83,98 ”，若key=60，运行上述程序 段后，下列条件表达式成立的是()A. s = "E"B. s = &

41、quot;R" C. s = "L"D. s = "LRR"4、某对分查找算法的vb程序段如下：i = 1: j = 7 : s=""key = in t(R nd*100)Do While i <= jm = (i + j) 2If key = a(m) The ns=s+"M" : Exit Do 'Exit Do 表示退出循环Elself key < a(m) The nj = m - 1: s=s + "L"Elsei = m + 1: s=s + &quo

42、t;R"End IfLoopText1.T ext = s数组元素a(1)到a的值依次为“ 24, 35，38, 41，45，69，78”。若该程序段执行 后，文本框Text1中显示的内容可能是()A.RL LMR C.RLR LRLM5、已知数组元素a(1)到a(9)的值为19,28,37,46,55,64,73,82,91,若在Text1中输入 29，然后执行下面程序段：Key = Val(Text1.Text) 10Text2.Text =""i = 1: j = 9: f = FalseDo While i <= j And Not fm = (i

43、+ j) 2If a(m) Mod 10 = Key The nsearch = m: f = TrueElseIf a(m) Mod 10 > Key The ni = m + 1Elsej = m -1End IfText2.T ext = T ext2.T ext + Str(m)Loop执行完该程序段后，Text2中显示的内容是()A. 52 B.55 37 28 C. 55 73 82 D.5 786、数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据 对分查找思想：设计一个在数组 a中查找数据Key的程序。实现该功能的VB程序段 如下：i = 1: j

44、= 10Key = Val(Text1.T ext)Do While i <= jm = (i + j) 2If a(m) = Key The n Exit Do 'Exit Do 表示退出循环If Key Mod 2 = 1 And a(m) Mod 2 = 0 The nElseIf Key Mod 2 = 0 And a(m) Mod 2 = 1 The nElseEnd IfLoopIf i > j Then s ="没有找至U! " Else s ="位置："+ Str(m)Text2.T ext = s上述程序中方框处可选

45、语句为： i = m + 1 j = m - 1 If Key < a(m) The n j = m - 1 Else i = m + 1 则(1)、(2 )、(3)处语句依次是A.、B.、 C.、D.、7、有一种查找算法，VB程序设计如下：cs = 0: i = 14: t = i:dx = 0Do While t <= 100cs = cs + 1If a(t) = find The nExit DoElseIf a(t) > find The nt = t -1If dx = t Then Exit DoElsedx = t: i = i -1If t + i >

46、 100 Thent = t + 1Elset = t + iEnd IfEnd IfLoop已知数组a有序递增，有100个元素a (1 )到a (100),变量find的数值是从外部输 入，则程序运行后，变量cs的值最大可以是A. 7 B. 13C. 14D. 50 8小明设计了如下一个查找数据的程序：在一组升序的数列当中，查找不小于 k的最 小数的位置，如果该值存在，则返回其第一次出现的位置，如果不存在则返回 0。程 序界面如下：(1) 若在Text1中输入“ 8”，Text2、Text3输出的分别为Asd Frril于：匸争诫-姫:TtftSt(2)请在划线处填入适合代码。Dim a(1

47、 T o 10) As In tegerFunction find(L As Integer , R As Integer, key In teger)As In tegerIf L > R The nfind = 0: Exit FunctionElseIf a(L) >= key The nfind = L: Exit FunctionElseIf a(m) < key The n find = fin d(M + 1, R, key)ElseIf The nfind = fin d(L, M - 1, key) Else find = MEnd If End IfEnd

48、 Fun cti onPrivate Sub Comma nd1_Click()Dim k As In tegerDim p As In tegerk = Val(Text1.Text)Text2.T ext = a(p)Text3.T ext = Str(p)If p = 0 The nText2.T ext ="无"End IfEnd SubPrivate Sub Form_Load()a(1) = 3 : a(2) = 3 : a(3) = 3 : a(4) = 4 : a(5) = 7 : a(6) = 7a(7) = 10 : a(8) = 13 : a(9) =

49、 19 : a(10) = 21For i = 1 To 10List1.AddItem Str(a(i)Next iEnd Sub9、对于数组(形如a数组：4、5、6、1、2、3或b数组：1、2、3、4、5、6)，我们 称元素1为此二数组的拐点。为寻找此类递增或循环递增数组的拐点，可以用顺 序查找和对分查找的方法，通常相比之下对分查找算法较优，以下为使用对分法 查找拐点的算法。做法是比较中点与当前查找范围第1个数大小关系，用对分法使查找范围逼近拐 点；当余下数组只有二个元素时，可根据此二元素大小关系得到拐点的位置。依据上述描述设计了 VB程序，界面如图所示。请回答下列问题：a寻找数担捋点回匚

50、丐：St®； “li、u 苗irr、垢、坨、拐点兀素対b下标沖13计算120、1 M、4 4 升 &、T、目(1) 对于循环递增数组“ 9、10、11、12、13、14、15、16、17、18、19、20、1、2、3、4、5、6、7、8”，代码中加框处执行的次数为 次。(2) 请在划线处填入合适的代码。Dim a(1 T o 20) As In tegerPrivate Sub Comma nd1_Click()Dim Low As Integer, High As IntegerLow = 1High = 20Do While High > LowIf Then

51、9;当只余下两个元素时If ThenLabel1.Caption ="拐点元素为"+ Str(a(1) + ",下标为"+ Str(1) ElseLabel1.Caption ="拐点元素为"+ Str(a(High) + ",下标为"+ Str(High)End IfExit DoEnd Ifm = (Low + High) 2If a(m) >= a(Low) ThenLow = mElseEnd IfLoopEnd SubPrivate Sub Form_Load()'生成循环递增的数组a，代码

52、略End Sub10、一个整数数组，里面有正有负，要求找到并输出其中连加和最大的子数组，输出 其开始位置和结束位置。如果两个子数组的和相同，则取前一个子数组。如 2、-6、0、3、-1、2、5、-4、4、-3,连加和最大的子数组为3、-1、2、5。算法：如果前几项之和为正，继续往后累加，否则从该项开始重新计算和。小李编写了一个实现该功能的 VB程序，运行界面如图所示。单击“随机生成”按钮 Command1后，随机产生10个-10,10随机整数，并在列表框Listl中显示。单击“找子数组”按钮Command2后，找出连加和最大的子数组，将最大和在标签Labell 中输出，将子数组在标签Label

53、2中输出，子数 组的起始位置和结束位置在标签Label3中输出。髓机生成1找子數组1I sssss连加宜最大的和为1=3连加值杲大的子数组为：鮎?、1、日、7、6手埶组M第嘲第环 实现上述功能的 VB程序如下，但加框处代码有误，请改正。Dim a(1 To 10) As In tegerPrivate Sub Comma nd1_Click()'生成10个随机数，并显示在列表框List1中。代码略。End SubPrivate Sub Comma nd2_Click()Dim maxsum As Integer , lastsum As Integer , ks As Integer,

54、 js As Integer , k As IntegerDim s As Strin g, i As In tegerks = 1: js = 1: k = 1: maxsum = a(1): lastsum = a(1)For i = 2 To 10If lastsum > 0 The nastsum = maxsum + a(i) ' (1)Elselastsum = a(i)ks = i' (2)End IfIf lastsum > maxsum Thenmaxsum = lastsumks = kjs = iEnd IfNext iLabel1.Capti

55、on ="连加值最大的和为"+ Str(maxsum)For i = ks To jss = s + Str(a(i)If i <> js Then s = s + "、"Next i11、“轮转后有序数组(Rotated Sorted Array ) ”是将有序数组取其中某一个数为分割点，将其之前的所有数都轮转到数组的末尾所得。比如 7, 11, 13, 17, 2, 3, 5 就 是一个轮转 后的有序数组，原有序数组中的子串 2，3，5 被轮转到了数组的末 尾处。对于一个轮转后有序数组arr也可以进行二分查找，算法思路如下(以升序为 例)

56、：每次根据查找的左侧位置L和右侧位置R求出中间位置M后，M左边L, M和右边M+1, R这两部分中至少一个是有序的(可根据中间位置数据和边界数据的大小关系判断)。arrM和待查找数据Key比较(1) . arrM=Key，返回 M 的值(2) .若M位置的右侧有序，当待查找数据在右侧，则下次在右侧查找，否则在M左 侧查找(3) .若M位置的左侧有序，当待查找数据在左侧，则下次在左侧查找，否则在M右 侧查找(1) 对于轮转后有序数组 7, 11,13,17, 2, 3, 5 使用以上函数search()查 找key值3,所需要的查找次数为_。(2) 以下VB函数Search()实现了对轮转后有序数组arr进行二分查找的过程， 如果查询成 功，返回m值，查询失败则返回-1。请补充程序中划线处的代 码：Fun cti on Search(key As In teger, L As In teger, R As In teger) As In teger填写合适的代码Do While L <= R And Search =-1 M =(L + R) 2If arr(M) = key The n Search = M Else填写合适的代码The填写合适的代码IfThe nIf arr(L)<= key And key < arr(M)n R = M - 1E