第四节 查找算法的程序实现-2023-2024学年高一信息技术浙教版选修1

第四节 查找算法的程序实现 一、选择题 1．有如下 VB 程序段： Const n = 10 Dim a(1 To n) As Integer Dim mid As Integer, L As Integer, R As Integer Randomize a(1) = 10 For i = 2 To n a(i) = a(i - 1) +Int(Rnd * 2) + 1 Next i c = 0: L = 1: R = n: flag = False: Key = 11 Do While L <= R And Not flag mid = Int((L + R) / 2 + 0.5) c = c + 1 If a(mid) = Key Then flag = True ElseIf a(mid) > Key Then R = mid - 1 Else L = mid + 1         END If      Loop 执行该程序段后，变量 c 可能的值是（    ） A．1 或 2 B．2 或 3 C．3 或 4 D．4 或 2 2．某对分查找算法的VB程序段如下： i = 1: j = 7: n = 0: f = False Key = Val(Text1.Text) Do While i <= j And f = False     n = n + 1     m = Fix((i + j) / 2)     If Key = a(m) Then f = True     If Key < a(m) Then j = m - 1 Else i = m + 1 Loop 数组元素a（1）到a（7）的值依次为“2，19，29，34，43，52，66，68”。文本框Textl中输入“46”后运行该程序，运行结束后下列说法不正确的是 A．变量f的值为False B．变量m的值为5 C．变量i的值为4 D．变量n的值为3 3．编写一个基于对分查找插入数据的程序代码。实现把数据t插入降序序列后得到一个新的降序序列，原序列各元素存放在数组元素a(1)～a(n)中。实现上述功能的程序段如下： t = Val(Text1.Text) If t <= a(n) Then         a(n + 1) = t Else         L = 1: R = n         Do While L <= R             m= (L + R) \ 2             If _____①____ Then R = m - 1 Else L = m + 1         Loop         For j = n To L Step -1             _____②____         Next j         _____③____ End If 则横线①②③上的语句分别是（   ） A．①a(m) > t               ②a(j) = a(j-1)              ③a(R+1) = t B．①a(m) < t               ②a(j) = a(j-1)              ③a(L) = t C．①a(m) > t           ②a(j+1) = a(j)            ③a(R+1) = t D．①a(m) < t           ②a(j+1) = a(j)            ③a(L) = t 4．有n个连续的自然数，删除首尾两端之外的其中一个数后存储在数组元素a（1）到a（n-1）中，利用对分查找算法找出这个数的某VB程序段代码如下： Const n=10 i = 1: j = n - 1 Do While j - i >= 2     m = (i + j) \ 2     If (1) Then                     i = m     Else         (2)     End If Loop Text1.Text = Str( (3) )          上述程序中(1)(2)(3)划线处可选语句有： ① a(j) - a(m) =j-m                ② a(m) - a(i) = m - i   ③ j = m – 1                        ④ j = m ⑤ a(i) + 1                         ⑥ a(i) 则上述程序中(1)、(2) 、(3) 划线处的代码依次为（   ） A．①③⑤ B．②④⑤ C．①③⑥ D．②④⑥ 5．某对分查找算法的VB程序段如下： ’数组元素f（1）到f（8）赋初值为0，代码略 Key=2*Int（Rnd*45）+1 i=1：j=9：c=0：s=0 Do While i<j c=c+1 m=（i+j）\2 f（m）=1 If Key<a（m）Then j=m Else i=m+1 Loop For k=1 To 8 s=s+f（k） Next k 数组元素a（1）到a（8）中的值为：4，20，32，42，58，60，90，91．执行该程序段后，下列说法正确的是（    ） A．变量c的值可能为5 B．变量s的值一定为奇数 C．变量i的值可能为9 D．变量j的值可能为7 6．某对分查找算法的VB程序段如下： Key = Int(Rnd*10)*2+1 s = "" i = 1: j = 10 Do While i <= j     m = (i + j) \ 2     s = s + Str(a(m))     If a(m) > Key Then j = m - 1 Else i = m + 1 Loop Text2.Text = s 数组元素a(1)到a(10)的值依次为“2,4,5,8,9,10,13,17,19,20”。执行该程序段，则文本框Text2中显示的内容可能的是（   ） A．9  4 B．9  4  5 C．9  17  19  13 D．9  4  5  8 7．7位学生的身高(单位:cm)从高到低依次为:178,177,175,172,170,165,162｡用对分查找法找到178 的过程中,依次被访问到的数据是(  ) A．178 B．172,175,178 C．172,177,178 D．172,175,177,178 8．顺序查找算法程序如下，下列说法正确的是（      ） Dim d(1 to 10) as Integer n=10 : count = 0 For i = 1 To n count = count + 1 If ① Then Label1.Caption = “顺序查找在数组的第” &amp; i &amp; “位找到了” &amp; v Exit For End If Next i If ② Then Label1.Caption = “顺序查找没有找到” &amp; v End If A．①处的代码为key=d(i) B．②处的代码为i>n C．在最好情况下，查找结束时变量count 的值为0 D．当变量count 的值为10，说明已经找到了 9．某对分查找算法的VB程序段如下： i=1:j=8:t=0 Key=Int(Rnd()*18)+4 Do While i<=j m=Int((i+j)/2) t=t+1 If a(m)=Key Then Exit Do Else If a(m)>Key Then j=m-1 Else i=m+1 End If Loop 数组元素a(1)到a(8)的值依次为“2，3，12，15，18，19，20，22”，该程序段运行结束后，变量t达到最大值时的Key值可能是（    ） A．5 B．18 C．21 D．23 10．查找的基本算法不包括（    ） A．顺序查找 B．二分查找 C．哈希查找 D．递归 11．某对分查找算法的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 12．数组d中存放了一组数据如表所示，采用顺序查找的方式查找数据7，以下叙述正确的是（  ） d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] 12 33 15 -7 11 33 17 19 43 29 A．因为存在相同的数组元素值，所以无法采用顺序查找 B．若查找的数组元素值不存在，则查找无法进行 C．因为数据是无序的，所以无法采用顺序查找 D．查找过程中，最多只需要比较10次 13．某对分查找算法的VB程序段如下： Key = Val(Text1.Text): i = 1: j = 10 Do While i <= j    m = (i + j + 1) \ 2    t(m) = 2    If Key <= a(m) Then      j = m - 1    Else      i = m + 1    End If Loop For i = 1 To 10   s = s + t(i) Next i 数组元素t(1)至t(10)初值均为0，数组元素a(1)至a(10)的值依次为“4，7，9，11，16，19，22，24，28，29”，在文本框Text1中输入待查找数，执行该程序段后，下列选项中，s的值可能的是（   ） A．4 B．8 C．10 D．12 14．某对分查找算法的VB程序段如下： Key=Val（Text1.Text） i=1: j=Key Do While i<=j m=（i+j）\2                    '① If Key=m*m Then Exit Do     'Exit Do表示退出循环 If Key>m*m Then i=m+1 Else j=m-1 Loop If i>j Then Labell. Caption= Key&amp; "不是完全平方数" Else Labell. Caption= Key&amp; "是完全平方数" End If 运行该程序段，在文本框Text 1中输入15，运行后①处语句的执行次数是（  ） A．3 B．4 C．5 D．6 15．数组a为一组循环有序不重复的数组，如（a（1）=25，a（2）=41，a（3）=100，a（4）=5，a（5）=7，a（6）=9）。依据对分查找思想：设计个在数组a中查找数据Key并显示在列表框的程序，界面如图所示。实现该功能的VB程序段如下： 1=1:r=6 Key=Val(Text1.Text) Do While <=r m=Int((1+r)\2) If a(m)=Key Then Exit Do Elself a(m)>=a(1) Then ElseIf a(m)<a(1) Then End If Loop 上述程序中方框处可选语句为： ①If a(m)<Key And a(r)>Key Then 1=m+1 Else r=m-1 ②List1.AddItem "第"+Str(m)+ "值是"+Str(a(m)) ③If a(m)>Key And a(1)<=Key Then r=m-1 Else=m+1 则（1）、（2）、（3）处语句依次是（    ） A．③①② B．②①③ C．①③② D．②③① 二、填空题 16．下列 VB 程序实现数字字母混合序列分离后分别排序，最后又合并输出。具体算法如下： 在文本框 Text1 输入若干组混合序列，每组序列中仅包含一组字母和一个多位数字，序列之间用逗号隔开，以逗号结束。单击“排序”按钮 command1，把每组序列中的字母和数字分开，并分别排序，最后在列表框 list1 输出。排序规则如下：所有数字按从小到大升序排序，字母序列按长度升序排序，若长度相同，直接比较升序排序（按字母的 ASCII 码排序，“A”<“Z”<“a”<“z”）。 实现算法的部分程序界面如图所示，VB 程序代码如下，回答下列问题： Private Sub Command1_Click() Dim a(1 To 6) As Integer, b(1 To 6) As String,I as integer,j as integer Dim c As String, k As Integer, tmp1 As Integer, tmp2 As String s=text1.text i = 1: k = 1: tmp1 = 0: tmp2 = "" Do While i <= Len(s) c = Mid(s, i, 1) If c = "," Then a(k) = tmp1: b(k) = tmp2 tmp1 = 0: tmp2 = "" ① Else If   Then tmp2 = tmp2 + c Else tmp1=tmp1*10+val(c) End If End If i = i + 1 Loop For i = 1 To 5 For j = 1 To 6 - i If a(j) > a(j + 1) Then tmp1 = a(j): a(j) = a(j + 1): a(j + 1) = tmp1 If Len(b(j)) > Len(b(j + 1)) Or ② Then tmp2 = b(j): b(j) = b(j + 1): b(j + 1) = tmp2 End If Next j Next i For i = 1 To 6 List1.AddItem Str(a(i)) + b(i) Next i End Sub （1） 代码“list1.AddItem”中的 AddItem 是 （单选，填字母：A．属性名 B．对象名 C．方法 D．事件名 ） （2） 在程序划线处填入合适代码，使程序完整。 ①处代码为 ，②处代码为 。 （3） 加框处代码有错，请改正。 应该为 （4） 若输入的字符串为“21ckk，gho63，TCP43，23Yes，no62，phy46”，则程序运行后第3组字符是 17．某校学生会选举需要从学校数据库中随机抽取若干名学生作为监票人。该数据库文件名为school.mdb，其中数据表student存储有关学生学号（xuehao）、姓名（xingming）相关信息，括号内的内容为对应字段名。该程序编辑界面如图所示，相关对象名可参考标识图。 当主持人点击按钮“生成抽号”后，下方的标签会显示可抽取的学号姓名，一定时间后显示被抽取作为监票人的学号姓名。 'xxxss:学校学生数，kcq:可抽取 'xhxm:学号姓名，kcq:可抽取 Dim xxxss As Integer Dim xhxm(3000) As String Dim kcq(3000) As Boolean 'cq_Click:启用两个定时器 Private Sub cq_Click() cqxhxm.Enabled = True xskcqxhxm.Enabled = True End Sub Private Sub cz_Click()  '初始化数组kcq，使每个元素数据都处于可显示状态 For i =" 0" To xxxss - 1 kcq(i) = True '① Next i End Sub Private Sub xskcqxhxm_Timer() '若数组kcq第x个元素处于可抽取状态，则显示数组xhxm第x个元素 x =" Int(Rnd" * xxxss) If kcq(x) Then xhxmbq.text = kcq(x) '② End Sub Private Sub Form_Load() '从数据库中提取需要的学号姓名相关数据并初始化数组kcq Randomize xxxss = 0 Dim conn As New ADODB．Connection,rs As New ADODB．Recordset Dim str_conn as String,str_sql As String str_conn = "driver="Microsoft" access driver(*.mdb);DBQ="&amp;app.path&amp;"\school.mdb"; conn.open str_conn str_sql = "select * from students" rs.open str_sql Do While Not rs.eof xxxss =" xxxss" + 1 xhxm(xxxss) = rs.fields("xuehao")&amp;rs.fields("xingming") rs.movenext Loop For i =" 0" To xxxss - 1 kcq(i) = True Next i End Sub Private Sub cqxhxm_Timer()  '决定抽取的学号姓名作为监票人 xskcqxhxm.Enabled = False For i =" 0" To xxxss - 1 If xhxmbq.Caption =" xhxm(i)" Then kcq(i) = False Next i cqxhxm.Enabled = False End Sub 18．【加试题】给定 n(n 小于 1000) 个整数, 整数的范围在 0 到m 之间, 请使用“对分法”思想求出这 n 个整数的中位数( 所谓中位数, 是指将这 n 个数排序之后 , 排在正中间的数)。 小丫编写了一个求中位数的VB 程序，功能如下：单击“求中位数”按钮Command1，程序根据输入的n 和m，随机产生n 个在[0,m] 范围内的数。程序运行界面如下所示： 实现上述功能的VB 程序如下: Dim x(1 To 1000) As Long Private Sub Command1_Click() 　Dim n As Integer, i As Integer, rbound As Integer, mid As Integer Dim m As Integer, count As Integer n = Val(Text1.Text) m = Val(Text2.Text) List1.Clear 　Randomize For i = 1 To n 　　x(i) =Int(Rnd * (m + 1)) ' 产生[0,m] 的随机数 　　List1.AddItem x(i) Next i 　　lb = 0 　　rb = m 　Do While lb <rb 　　mid = (lb + rb) \ 2 　　　　①　 　　For i = 1 To n 　　　If　②　Then 　　　　count = count + 1 　　　End If 　　Next i 　　If count > n \ 2 Then 　　 lb = mid + 1 　　Else 　　　③　 　　End If 　Loop 　Text3. text = str(rb) End Sub 程序要实现该功能，画线处应填入的代码为： ① ② ③ 19．在我国古代《孙子算经》中曾经提出这样一个问题，原文是这样的：“今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二；问物几何？”试用枚举算法来解决这一个问题。现分析如下，所寻找之数为满足如下条件的自然数：以3除余2，以5除余3，以7除余2。程序将从自然数1开始依次寻找，逐一判断某一自然数是否满足全部条件，直至在指定范围内找到满足条件的所有自然数。程序代码如下，请补充完整。 Private Sub Command1_Click() Dim sum As Integer 'sum 用来统计符合条件的自然数个数' Dim n, max As Integer List1.Clear sum = 0 max = ____（1）____ '指定查找范围的最大自然数，Text1文本框中输入' n = 0 Do While n <= max n =" n" + 1 '从自然数1开始不断往上寻找' If ________（2）_______Then List1.AddItem Str(n) '找到后在List1中显示结果' ___________（3）_________ End If Loop List1.AddItem ("共计" + Str(sum) + "个") End Sub （1）__________________ （2）__________________ （3）__________________ 20．老王用VB编写了一个程序实现求第k（1≤k≤n）大的数。程序运行时，单击“获取成绩”按钮Command1得到n个学生成绩（百分制）保存在cj(1)~cj(n)中，并显示在List1中。在文本框Text1中输入k的值，单击“查找”按钮Command2，在标签Label1中显示第k大的数。程序运行界面如图所示。 （1）为使程序开始运行时，窗体标题自动更改为“查找第K大的数”， 则可在 （单选，填字母：A．Command1_Click()/ B．Form_Load()/C． Form1.Load()）事件处理过程中添加语句Form1.Caption=“查找第k大的数”。 （2）请在划线处填入合适代码。 （3）加框处的程序代码有错，应改为 。 Dim cj(0 To 1000)As Integer,n As Integer Private Sub Command1_Click()     ‘从数据库中读取n个学生的成绩并存储在cj数组中，代码略 End Sub Private Sub Command2_Click() Dim b(0 To 100) As Integer Dim t(0 To 100) As Integer Dim x as Integer k = Val(Text1.Text) For i = 1 To n    ①       b(x) = b(x) + 1 Next i For i = 99 to 0 step -1 If  k <= t(i+1)  Then Exit For ② Next i Label1.Caption = "第k大的数为"+ ③ End Sub 三、操作题 21．小李编写了一个成语接龙的VB程序，功能如下：在文本框Text1中输入一个成语，单击“接龙”按钮Command1，在列表框List1中显示接龙的成语。程序运行界面如下图所示。 实现上述功能的VB程序如下，但加框处代码有错，请改正。 Dim n As Integer, cy(30000) As String Private Sub Form_Load() '从数据库中读入n条成语,并存数组cy中 '代码略 End Sub Private Sub Command1_Click() Dim s As String, i As Integer, j As Integer Dim m As Integer, flag As, Boolean Dim s1 As Siring, s2 As String s=Text1.Text flag=True Do While flag                  '(1) i=1 j=n Do While<= j m= Int((i+j)/2) s2=Mid(cy(m), 1, 1) If s2=s1 Then Exit Do ElseIf s2<s1 Then i=m+1 Else j=m-1 End If Loop If    Then                 '(2) List1.AddItem s+ "— —"+cy(m) s=cy(m) Else List1.AddItem "接不下去了" flag=False End If Loop End Sub 22．查找最短26个字母字符串: 在文本框Text1中输入任意一串仅包含小写字母的字符串（长度n>=26），要求找到长度最小的一段区间，能够包含全部26个小写英文字母。小王设计了VB程序用于搜索最短字符串，单击“查找”按钮 Command1，若无解，则在标签 Label1中输出“无解！”，反之程序在标签 Labell中输出该最小区间的长度以及字符的开始位置，并在文本框Text2中输出相应的最短字符串，程序界面如图所示。 查找最短26个字母字符串的算法可描述为: 1）确定初始右边界: 从第1个字符开始，向右搜索到包含全部26个字母的子串，并因此而确定右边界，同时记录每个字母在子串中出现过的次数。 2）调整子串左边界: 若左边界有重复的字母则表明该子串可缩短，故左边界可右移1位，……直到找到一个符合条件的子串并记录，然后子串左边界再右移1位。 3）调整子串右边界: 子串右边界继续右移，在新子串符合条件后，记录并进行比较。重复2）各调整步骤，直至遍历完整个字符串，获得并输出满足条件的最小长度字符串。                实现上述功能的VB程序如下，请回答下列问题: （1）对于字符串“ qbwcadsgeqbdatcy”，包括字母 abcde的最短字符串长度为 （填数字） （2）请在划线处填入合适的代码。 Const n=200 Dim i As Integer, k As Integer, length As Integer, L As Integer Dim pos As Integer, sl As String, res As String Dim f(1 To 26) As Integer     ＇数组f记录每个小写英文字母的出现次数 Dim s(1 To n)As Integer       ＇数组s记录每个输入字符在字母表中的位置 Private Sub Command1_ Click res=" " s1=Textl. Text For i=1 To Len(s1) s(i)= Next i k=0: pos=1: length=n For i=1 To 26 f(i)=0 Next i For i=1 To Len(sl) If f(s(i))=0 Then k=k+1 f(s(i))=f(s(i))+1 Do While f(s(pos))=f(s(pos))-1 If Then k=k-1 If i-pos+1<length Then length=i-pos+1 res=Mid (sl, pos, length) L=pos End If End If pos=pos+1 Loop Next i If res<>""Then Text2 Text=res Labell. Caption="最短长度: "+Str( length)+"开始位置: "+Str(L)Else Labell. Caption="无解！" End if End Sub 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．C 3．D 4．B 5．B 6．D 7．C 8．B 9．C 10．D 11．B 12．D 13．B 14．B 15．D 16． C k = k + 1 Len(b(j)) = Len(b(j + 1)) And b(j) > b(j + 1) c< "0" or c > "9" 或 not(c >= "0" and  c< ="9")或 c >= "a" and  c< ="z" or  c >= "A" and c< ="Z" “43Yes” 17．(1)kcq(i) = True   (2)xhxmbq.Caption = xhxm(x) 18． count=0 x(i)>mid rb=mid 19．（1）Val(Text1.Text)（1分） （2）n Mod 3 =" 2" And n Mod 5 =" 3" And n Mod 7 = 2（2分） （3）sum =" sum" + 1（2分） 20． 2 ① x = cj(i) t(100)=b(100) ② t(i) = t(i+1) + b(i) ③ str(i+1) 21． s1=Mid(s,Len(s), 1) i<=j 22． 7 Asc(Mid(s1,i,1)-96或Asc(Md(s1,i,1))-Asc("a")+1 k>=26或k=26 f(s(pos))=0 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$