查找算法及程序实现 知识点题库

【加试题】编写VB程序，实现如下功能：单击“生成密文”按钮Command2，在文本框Text3中产生与每个小写字母对应的密文（每个明文字母对应1个不重复的密文字母）。在文本框Text1中输入单词字符串，单击“加密”按钮Command1后，进行逐个字符加密，加密方法：在“明文”中找到相应字符，再得到明文对应位置的密文,并在文本框Text2中显示对应密文（运行效果如图17所示）。实现上述功能的VB代码如下：

 

Dim m2 As String

Private Sub Command1Click()

Dim flag(1 To 26) As Boolean

Dim num As Integer,t As Integer

Randomize

num = 1

Text3.Text = " "

For i = 1 To 26

    flag(i) = False

Next i

Do While num <= 26

    x = Int(Rnd * 26) + 97

          ①      

    If  flag(t) = False Then

    m2 = m2 + Chr(x)

    num = num + 1

      ②       

    End If

Loop

Text3.Text = m2

End Sub

Private Sub Command2Click()

Dim s As String， m As String， result As String

Dim k As String， c As Integer

s = Text1.Text

m = "abcdefghijklmnopqrstuvwxyz"

For i = 1 To Len(s)

    k = Mid(s, i, 1)

    If  k >= "A" And k <= "Z"  Then

    k = Chr(Asc(k) + 32)

    End If

    c = 1: continue = True

    Do While       ③       

    If k = Mid(m, c, 1) Then

    continue = False

    End If

    c = c + 1

    Loop

   ④     

Next i

Text2.Text = result

End Sub

程序①处的代码是

程序②处的代码是

程序③处的代码是

程序④处的代码是

小明编写了一个VB程序，功能如下：在文本框Text1中输入一段英文，并在文本框Text2中输入英文段落中的某个单词（或字符串），单击“最大间距”按钮（Command1）后，在文本框Text3中显示该单词在文中某两次出现的最大间距，若只出现一次或不出现则显示值为0。程序运行界面如下图所示：

实现上述功能的VB程序如下：

Private Sub Command1_Click()  

Dim a(1 To 1000) As String   '数组a存储文中出现该指定单词(或字符串)的各个位置

Dim s As String, c As String ,ch As String

Dim n As Integer, max As Integer, i As Integer

s = Text1.Text 

c = Text2.Text

n = 0: Max = 0

For i = 1 To Len(s) - Len(c) + 1

    ch =     ①   

    If ch = c Then

        n = n + 1

        a(n) = i

        If n >= 2 Then

If a(n) - a(n - 1) - Len(c) > Max Then Max = a(n) - a(n - 1) - Len(c)

        End If

    End If

Next i

Text3.Text =     ②  

End Sub

以上程序段运行时，为了实现上述功能，划线处①和②应填入的代码分别为： 

① ②

【加试题】对于数组（形如a数组：4，5，6，1，2，3或b数组：1，2，3，4，5，6）称元素1为此二数组的拐点，为寻找此类递增或循环递增数组的拐点，可以用顺序查找和对分查找的方法，通常相比之下对分查找算法较优，以下为使用对分法查找拐点的算法。

做法是比较中点与当前查找范围第1个数大小关系，用对分法使查找范围逼近拐点；当余下数组只有两个元素时，可根据此二元素大小关系得到拐点的位置。

依据上述描述设计了VB程序，界面如图所示。请回答下列问题：

【加试题】对分查找程序如下，数组a的值依次为3，8，9，21，37，56，68，72，89，96，对数组中的每个元素进行对分查找，则查找成功的平均查找次数是（  ）

   i = 1: j = 10

Do While i <= j

       m = (i + j) \ 2

       If a(m) = Key Then text1.Text = "查找成功": Exit Do

       If Key < a(m) Then j = m - 1

       If Key > a(m) Then i = m + 1

Loop

有100个大小形状一样的玻璃球，其中有1个玻璃球的重量轻于其他99个玻璃球，如何用一台无砝码的天平，以最快的速度找出这个轻玻璃球？运用“三分筛选”法来模拟“寻找”这个轻玻璃球的算法如下：

步骤1：如果待筛选的玻璃球个数<3，则认定已经找出了这个玻璃球(认定方法参照步骤2中描述)，停止筛选，并输出经过的筛选总次数;否则，重复执行步骤2。

步骤2：按编号依次将玻璃球均分成3份，如果有多余的放入第3份中;比较第1、2份的玻璃球重量：

①如果第1份等于第2份的重量，则选取第3份的玻璃球作为下一次筛选的对象;

②如果第1份小于第2份的重量，则选取第1份的玻璃球作为下一次筛选的对象;

③如果第1份大于第2份的重量，则选取第2份的玻璃球作为下一次筛选的对象;

重复执行步骤1。

例如：第1次筛选的小球编号区间是1~100，均分成三份的待称重小球编号分别是1~33、34~66、67~100；第2次则选取以上3份中的一份进行再筛选、再均分……直至找到。

解决上述问题的VB程序功能如下：运行程序，在列表框List1中显示100组数据，分别代表每个编号及对应的小球重量(其中有且只有一个小球的重量与其他小球不同)，单击“筛选”按钮Command1，在列表框List2中显示每次筛选的编号区间和完成筛选的总次数。程序运行界面如图。

【加试题】有如下VB程序段：数组元素a(1)到a(6)的值分别为“Beijing”、“Guangdong”、“Jiangsu”、“Jiangxi”、“Shanghai”、“Zhejiang”，已按字典序排序。当key的值为“Zhejiang”时，单击命令按钮Command1，文本框Text1中显示的内容为（  ）

Private Sub Command1_Click()

Dim i As Integer, j As Integer, m As Integer

Dim s As String

i = 1: j = 6

Key = Text1.Text：s = ""

Do While i <= j

m = Int((i + j) / 2 + 0.5)

s = s + " " + a(m)

If Key > a(m) Then

i = m + 1

Else

j = m - 1

End If

Loop

Text1.Text = s

End Sub

杨氏矩阵数组的特征是每行从左到右是递增的，每列从上到下是递增的，如下图所示为一个4×4的杨氏矩阵。

1	5	7	9
4	6	10	15
8	11	12	19
14	16	18	21

已知数据逐行存储在数组a中，在杨氏矩阵数组中查找某数字是否存在的VB程序段如下：

cz = False : i = 1 : j = n

Do While j >= 1 And i <= n

   

    If key < a(s) Then

          ⑵ 

    ElseIf key > a(s) Then

          ⑶ 

    Else

      cz = True:Exit Do

    End If

Loop

方框中的代码由以下三部分组成：

①j = j - 1

②s = (i - 1) * n + j

③i = i + 1

代码顺序正确的选项是（  ）

下列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

数组元素a(1)～a(100)用以存储某班级50位学生的信息技术和通用技术成绩，奇数位置存储信息技术成绩，偶数位置存储对应学生的通用技术成绩。该数组已经按照两科总成绩升序排序。依据对分查找思想，设计一个在数组a中查找总成绩为key的程序，统计输出两科总成绩大于等于key的人数。部分运行界面如图所示：

实现该功能的VB程序如下：

Private Sub Command1_Click()

Dim a(1 To 100) As Integer

Dim sum As Intcger

Const t= 50

‘将50个学生的信息技术和通用技术成绩依次存储在数组a(1)~a(100)，代码略

Key = Val(Text2.Text)

i= 1

j= 100

m=(i+j)\2

Do While   ①   And m>1

    If m Mod 2=1 Then m= m- 1

    sum = a(m)+ a(m- 1)

    If  ②  Then

        j=m-2

    Else

       

    End If

    m=(i+j)\2

Loop

Label2.Caption "大于等于"& Key & "分的人数为: "+ Str(t-j\2)

End Sub

某数组有10个元素，依次为5、12、16、23、27、3、35、41、49、50，下列选项中正确的是（  ）

1.某对分查找算法的VB程序段如下：

i=1: j=8: t=0

Key=Int (rnd( )*20)+10

Do While i<m=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，11，14，15，18，19，25，32”，该程序段运行结束后，变量t的最大值可能是（  ）

有如下VB程序段：

数组元素f(1)到(9)赋初值为0，代码略

a(1)= 1

For i=2 To 9

  a(i)=a(i-1)+ Int(Rnd* 2)+1

Next i

Key= Val(Text1. Text)

i=1: j=9

Do While i<=j

  m=(i+j+1)\ 2

  f(m)= 1

  If a(m) > Key Then

    j=m-1

  Else

    i=m+1

  End If

Loop

在文本框Text1中输入待查找数，执行该程序段后，下列选项中，f(1)到f(9)各元素值不可能的是（    ）

已知数组元素a（1）到a（9）的值依次为“19，28，37，46，55，64，73，82，91”，若在Text1中输入29，并执行如下程序段后，Text2中显示的内容是（  ）

Key=Val（Text1.Text）\10

Text2.Text=""

i=1：j=9：f=False

Do While i<=j And Not f

    m=（i+j）\2

    If a（m）Mod 10=Key Then

        search=m：f=True

    ElseIf a（m）Mod 10>Key Then

        i=m+1

    Else

        j=m-1

    End If

Text2.Text=Text2.Text+Str（m）

Loop

某查找算法的VB 程序段如下：

Dim a(1 To 10) As Integer

Randomize

n = 0

i = 1: j = 10

Key = Int(Rnd * 25) * 2 + 1

Do While i <= j

    m = Int((i + j) / 2)

    If Key = a(m) Then Exit Do

    If Key > a(m) Then

        i = m + 1: n = n * 2 + 1

    Else

        j = m - 1: n = n * 2 - 1

    End If

Loop

数组元素a(1)到a(10)的值依次为“5,8,11,18,23,29,33,42,45,51”。执行该程序段后，n的值不可能的是（    ）

有多人在不同楼层要乘坐同一部电梯，所有人都是去往更高楼层，电梯初始位置为第一批用户出发的楼层位置。电梯在运行时，上升一层需耗时3秒，在某一层停留时(含电梯初始位置和电梯结束位置)，不论有多少人进出都算8秒。小马同学利用上述算法编写了一个VB程序，在列表框list1中显示所有人的出发与到达楼层，按照出发楼层升序(出发楼层相同按到达楼层升序)排序，在列表框list2 中输出排序后结果，最后在文本框Text1中输出电梯本次运行的总时间。程序运行界面如图所示，回答下列问题：

某对分查找算法的VB程序段如下：

Key= Val(Text1.Text)

i=1： j=10： n=0

Do While i<=j

    m=(i+j)\2

    n=n+1

    If a(m) ： > Key Then

        j=m-1

    Else

        i=m+ 1

    End If

Loop

Text2.Text=str(n)

数组元素a(1)到a(10)的值依次为“2，3，5，8，9，10，13，17，19，25”。在文本框Text1中输入待查找的整数，执行该程序段，则文本框Text2中显示3，待查找数不可能是（    ）

某算法有如下程序段

Key = Int(Rnd * 5) * 2 + 10

i = 1: j = 8: n = 0

Do While i <= j

    m = (i + j + 1) \ 2

    If a(m) >= Key Then i = m + 1 Else j = m - 1

    n = n + 1

Loop

数组元素a(1)~a(8)的值为“22，21，18，17，16，15，14，10”。若该程序段执行后，下列说法错误的是(        )

有如下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的值可能是(        )

“轮转后有序数组(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右侧查找

小明编写了一个查找替换的VB程序，其功能为：在一串由汉字、空格和标点符号组成的文本中，把文本中的某个字符串用另一个字符串替换。

程序界面如下图所示，程序运行时，在文本框Text1中输入一段文本，在文本框Text2中输入查找的字符串，在文本框Text3中输入替换为的字符串，单击“查找替换”按钮Command1，则在文本框Text4中输出替换后的文本，在标签Label6中显示替换的次数。

实现上述功能的VB程序如下，请在程序划线处填入合适的代码。

Private Sub Command1_Click()

    Dim st1 As String, st2 As String

    Dim i As Integer, n As Integer, count As Integer

    Dim st3 As String, ch As String, result As String

    result = “ ”

    st1 = Text1.Text

    st2 = Text2.Text

    st3 = Text3.Text

    len1 = Len(Text2.Text)

   

    result = “ ”

    i = 1

    Do While i <= n

       

        If ch = st2 Then

            result = result + st3

            count = count + 1

            i = i + len1

        Else

            

            i = i + 1

        End If

    Loop

    Text4.Text = result

    Label6.Caption = Str(count)

End Sub