2023-2024学年浙教版高一下学期第五章第四节 查找算法的程序实现

2023-2024学年浙教版高一下学期第五章第四节 查找算法的程序实现 一、选择题 1．有如下 VB 程序段：（   ） s = "AAABBBCCCCDDEFF" i = 1: j = Len(s): Key = "H": v = "" Do While i <= j   m = (i + j) \ 2   c = Mid(s, m, 1)   If c = Key Then Exit Do   If c > Key Then      j = m - 1: v = v &amp; c    ElseIf c < Key Then        i = m + 1: v = v &amp; c    End If Loop     执行完以上程序后，v的值为 A．CDFF B．CDF C．CDEF D．DEF 2．有如下程序段： m = 1:n = 12 key = Val(Text1. Text) mid =(m+ n+1)\2 Do While a(mid)<> key And m <= n If a(mid)> key Then n = mid-1 left = left +1 Else m = mid +1 End If mid =(m +n)\2 sum = sum +1 Loop 数组a(1)至a(12)中的数据分别为2，3，8，16，19，27，29，32，49，64，72，99，在文本框Text1中输入19，运行该程序段，则变量sum和left的值分别为（    ） A．1  1 B．1  2 C．2  1 D．2  2 3．某对分查找算法的 VB 程序段如下： Key = Val(Text1.Text): s = "" i = 1: j = 10 Do While i <= j     m = (i + j) \ 2     If a(m) <= Key Then         i = m + 1         s = s + "R"     Else         j = m - 1         s = s + "L"     End If Loop Text2.Text = s 数组元素 a(1)到 a(10)的值依次为“1，4，6，10，16，16，16，18，21，33”。在文本框 Text1中输入 16 后，该程序段的输出结果与输入下列值的输出结果相同的是（      ） A．10 B．12 C．17 D．18 4．把学生成绩由高到低排序后，按姓名在前、成绩在后的顺序依次存储在数组a中。例如(“蒙多”，“94”，“C罗”，“688”，“卢本伟”，“85”......设计一个VB程序，利用对分查找思想实现在数组a中查找成绩为Key的学生姓名。程序段如下： i=l:j=n            'n代表学生数量 Key=Val(Text1.Text) Do While i<=j m= If Val(a(m))>Key Then i=m\2+1 Else j=m\2-1 Loop Listl.Clear j=j+1 Do While j<=n If Val(a(2*j))=Key Then Listl.AddItem a(2*j-1)+""+a(2*j) Else Exit Do j=j+1 Loop 上述程序中方框处可能的语句是（       ） A．(i+j)\2*2 B．（(i+j)\2)*2 C．(i+j)\2 D．((i+j)\2)/2 5．某对分查找算法的VB程序段如下： key = Val(Text1．Text) s = "" i = 1: j = 10 Do While i <= j   m = (i + j) \ 2   s = s + Str(m)   If a(m) = key Then Exit Do   If a(m) > key Then j = m - 1 Else i = m + 1 Loop Label1．Caption = s 数组元素a(1)到a(10)依次存放10个升序的整数。在文本框Text1中输入一个任意整数执行该程序段，标签Label上中显示的内容可能的是（  ） A．5 2 3 1 B．5 3 2 4 C．5 8 6 7 D．5 8 9 7 6．某查找算法的部分VB程序代码如下： i=1:j=8:k=0 key=95 Do While i<=j k=k+1 m=Int((i+j)/2) If key=a(m) Then Exit Do If key<a(m) Then j=m-1 Else i=m+1 Loop 数组元素a(1)到a(8)的数据依次为“12，28，49，56，57，88，95，100”，该程序运行过程中，当变量k的值为2时，对应查找的a（m）值是（    ） A．28 B．56 C．88 D．95 7．数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下： i = 1: j = 10 Key = Val(Text1.Text) Do While i <= j m = (i + j) \ 2 If a(m) = Key Then Exit Do 'Exit Do 表示退出循环 If Key Mod 2 = 1 And a(m) Mod 2 = 0 Then （1） ElseIf Key Mod 2 = 0 And a(m) Mod 2 = 1 Then （2） Else （3） End If Loop If i > j Then s = "没有找到！" Else s = "位置：" + Str(m) Text2.Text = s 上述程序中划线处处可选语句为： ①i = m + 1 ②j = m - 1 ③If Key < a(m) Then j = m - 1 Else i = m + 1 则（1）、（2）、（3）处语句依次是（    ） A．①、②、③ B．①、③、② C．②、①、③ D．③、②、① 8．某对分查找算法的VB程序段如下： ’随机产生包含8个整型元素的降序序列，依次存入数组a，代码略 i=1：j=8：c=0 Key=Val（Text1.Text） Do While i <= j      m=（i+j+1）\2      c=c+1      If a（m）>Key Then i =m+ 1 Else j=m-1 Loop Text2.Text=Str（c） 在文本框Text1中输入待查找的数，执行该程序段后，下列说法错误的是（  ） A．i的值为j+1 B．c的值为3或4 C．i的值可能为9 D．j的值不可能为0 9．使用跳跃表来维护一组有序的整型数据组成的集合，数据组织如下图所示： 假如要查找元素11，共需遍历的次数为（   ） A．2 B．3 C．4 D．5 10．【加试题】某对分查找算法的 VB 程序段如下： Key = val(text1.text)   N=0 i = 1: j = 7 flag = False Do While i <= j And flag = False n = n + 1 m = Fix((i + j) / 2) If a(m) = Key Then flag = True If Key < a(m) Then i = m + 1 Else j = m – 1    Loop If flag = True Then Text2.Text = "在第" &amp; Str(m) &amp; "个，" Else Text2.Text = "未找到，" End If 数组元素 a(1)到 a(7)的值依次为“89，72，68，45，23，19，17”。文本框 Text1 中输入 17，执 行该程序段后，下列变量的值不．正．确．的是（    ） A．n=2 B．m=7 C．i=7 D．j=6 11．数组a中6个有序数据为“11，22，33，44，55，66”，用下面的程序代码查找数据“23”，则程序执行完毕后，下列各变量值正确的是（    ） Dim a(1To6)As Integer Dim i As Integer,j As Integer,Key As Integer,m As Integer a(1)=11:a(2)=22:a(3)=33:a(4)=44:a(5)=55:a(6)=66 i=1:j=6:p=0:Key=23 Do While i<=j p=p+1 m=(i+j)\2 If j Mod 2=0 Then m=m+1 If a(m)=Key Then Exit Do If Key<a(m)Then j=m-1 Else i=m+1 Loop A．i=5 B．j=4 C．m=3 D．p=2 12．编写 VB  程序，实现把数据 key  插入升序序列中，得到一个新的升序序列，原升序序列各元素已依次存放在数组元素 a(1)、a(2)、a(3)、……、a(10)中，VB  程序段如下： i = 1: j = 10 Do While  i <= j m = (i + j) \ 2 If key <= a(m) Then       ’① Else ’② End If Loop For k = 10 To i Step -1 ’③ Next k a(i) = key 要使程序实现上述功能，则方框①②③中的语句分别是（              ） A．j = m - 1    i = m + 1    a(k + 1) = a(k) B．j = m - 1     i = m + 1     a(k) = a(k - 1) C．i = m + 1    j = m - 1    a(k + 1) = a(k) D．i = m + 1     j = m - 1     a(k) = a(k - 1) 13．数组a中存放了一批数据如下表，现采用对分查找方式在这批数据中查找“zhu”，以下说法正确的是（  ） a(1) a(2) a(3) a(4) a(5) a(6) a(7) hou ji long ma niu she tu A．无法进行对分查找，因为这批数据还没排好序 B．依次被比较的数据是“ma”，“ji”，“hou” C．无法进行查找操作，因为这批数据中没有“zhu” D．依次被比较的数据是“ma”，“she”，“tu” 14．【加试题】对分查找的VB程序段如下： key=78 i=1 j=8 k=1 Do While i<=j m= fix((i+j)/2) if d(m)=key Then Label1.Caption=k Exit do End if If d(m)<key Then i=m+1 else j=m-1 End If k=k+1 Loop 数组元素a(1)到a(8)的值依次为“22，34，41，53，66，71，78，91”。若该程序执行后得到的结果是 A．1 B．2 C．3 D．4 15．已知字符串数组a(1)到a(6)的原始数据为"118"，"69"，"78"，"25"，"98"，"2"，利用以下VB程序对其进行排序： pos=3:s= Str(pos):i=1 flag=True Do While i<6 And flag=True flag=False For j=1 To 6-i If a(j)<a(j+1)Then t=a(j):a(j)=a(j+1):a(j+1)=t flag= True If pos=j Then pos=j+1 s=s+"→"+Str(pos) Else lf  pos =j+1 then pos=j s=s+"→"+Str(pos) End if End if Next j Loop 程序运行之后，变量s的值为（    ） A．3 B．3→2→1 C．3→2→3 D．3→2→1→2 二、填空题 16．在我国古代《孙子算经》中曾经提出这样一个问题，原文是这样的：“今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二；问物几何？”试用枚举算法来解决这一个问题。现分析如下，所寻找之数为满足如下条件的自然数：以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）__________________ 17．下列 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组字符是 18．一个程序功能如下：单击开始按钮，每隔1秒产生一个[1,100]的随机数，赋给变量n，对产生的随机数进行判断，如果是偶数就显示在列表框1中，如果是奇数显示在列表框2中。当随机数达到20个时，停止。Timer控件的Enabled属性设置为False，即程序刚运行时不起作用。 程序代码如下： Dim m As Integer  'm 为模块级变量，用于记录随机数个数 Private Sub Command1_Click() Randomize Timer1.Enabled = True End Sub Private Sub Timer1_Timer() Dim n As Integer ① If ② Then List1.AddItem n Else List2.AddItem n   End If m =" m" + 1           If m =" 20" Then ③ End Sub 在程序①、②、③划线处，填入适当的语句或表达式，把程序补充完整: 程序中①划线处应填入___________________。 程序中②划线处应填入___________________。 程序中③划线处应填入___________________。 19．老王用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 20．杭州市民卡是由杭州市人民政府授权发放给市民用于办理个人相关事务和享受公共服务的集成电路卡（IC卡），具有信息储存、身份识别、电子支付等功能。每位市民卡的卡号是唯一的，卡内会记录每位市民的姓名、住址、金额等信息。 假设共有1000个市民，市民的相关信息都存储在“information.accdb”的data表中，查询程序界面如图所示。工作人员在文本框Text1中输入卡号，单击“开始查询”按钮，如果找到，就在Label1中显示卡内市民姓名和卡内余额；否则显示“查无此人”。请按要求将下列程序补充完整。 Private Sub command1_click() Dim conn As New ADODB．Connection, rs As New ADODB．Recordset Dim strSQL As String Dim a,b as string ‘分别定义姓名、余额 Dim n as integer conn.ConnectionString = "Provider="Microsoft.ACE.OLEDB．12.0;Data" Source=" + App.Path + "\information.accdb"     '打开到数据库的链接 conn.Open strSQL ="select xh,xm from data where '卡号=&amp;(Text1.Text) &amp; '" '设置查询的SQL语句 Set rs.ActiveConnection = conn    '设置rs的ActiveConnection属性，指定与其关联的数据库链接 rs.Open strSQL   '打开记录集，将从表information中读取的结果保存到记录集rs中 Label1.Caption = "" n=0 Do while not rs.EOF ① a=rs.Fields("姓名") b=rs.Fields("余额") rs.movenext loop rs.Close conn.close set rs=nothing set conn=nothing ② if n="0" then Label1.caption="查无此人" End Sub （1）程序中①划线处应填入___________________。 （2）程序中②划线处应填入___________________。 三、操作题 21．数组 a 中随机产生 n 个1到10之间的随机数，并已按升序排列，依据对分查找思想，设计一个在数组 a 中查找数据 key 的起始、结束位置的程序，运行界面如下图所示。 实现上述功能的 VB 代码如下。 Const n ＝ 100 Dim a(1 To n+1) As Integer   '产生 n 个随机数，存储在数组 a 中，并已按升序排序，代码略 Private Sub Command1_Click( ) Dim key As Integer, i As Integer, j As Integer Dim m As Integer, k As Integer key ＝ Val(Text1.Text) i=1: j=n   Do While i <= j m=(i+j)\2 If   Then  ' 改 错 j=m-1 Else i=m+1 End If Loop If  a(i)=key Then        '找重复数的结束位置 For k=i+1 To n If  a(k) <> key Then Exit For   ' 退出For循环 End If Next k List2.AddItem “a(” + Str(i) + “) -- a(” + + “)”    ' 填 空 Else List2.AddItem “未找到”   End If End Sub （1）代码“List1.AddItem”中的 AddItem 是 (单选，填字母：A．对象名/B．属性名/C．事件名/D．方法名)。 （2）程序代码中，加框处语句有错，请改正。 （3）请将划线处代码补充完整。 （4）若查找的 key 值为 3，则程序结束时，变量 k 的值为 22．数组a中存储n个2位正整数，从倒数第2个数开始，利用对分查找的思想，找到它的所在位置，并插入正确位置中，实现整个数组有序。实现该功能的VB程序如下: Const n = 100 Dim a(n) As Integer Private Sub Form_Load() ′产生n个2位正整数，并显示在文本框Text1中，代码略 End Sub Private Sub Command1_Click() Dim i As Integer，j As Integer，left As Integer Dim right As Integer，m As Integer，t As Integer i = n-1 Do While i > = 1 right = n t = a(i) Do While left < = right m = Int((left + right)/2) If a(m) = t Then right = m:Exit Do If a(m) < t Then left = m + 1 Else right = m-1 End If Loop Forj = i To right-1 a(j) = a(j + 1) Next j i = i-1 s = “” For j = 1 Ton s = s + Str(a(j)) Next j List1.AddItem s Loop End Sub (1)语句“Listl.AddItem s”中的AddItem是 (单选，填字母:A．对象名/B．属性名/C．事件名/D．方法名)。 (2)程序代码中，加框处有错，请改正。 (3)程序代码中，将①处语句补充完整。 (4)若删除语句“Ifa(m) = tThenright = m:ExitDo”，则下列说法正确的是 (单选，选填字母:A．程序进入死循环，无法正常运行/B．输出排序的结果不变/C．输出排序的结果将改变)。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 2．C 3．C 4．B 5．C 6．C 7．C 8．D 9．C 10．A 11．C 12．A 13．D 14．C 15．D 16．（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分） 17． 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” 18．（1） n =" Int(Rnd" * 100) + 1 （2）n Mod 2 =" 0" （多） （3）  Timer1.Enabled = False 19． 2 ① x = cj(i) t(100)=b(100) ② t(i) = t(i+1) + b(i) ③ str(i+1) 20．（1）n=n+1 （2）Label1.caption="a+" "卡内余额为"+b+"元" 21． key< a(m) Str(k-1) D 17 22． D left = i + 1； a(right) = t B 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$