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

【加试题】小林和小王合作编写一个查询英语单词的VB程序：小林编写一个过程，单击“读取数据库”按钮Command1，从一个数据库中读取英语单词和中文含义，分别保存在a数组和b数组中。并显示在List1中；小王编写另一个过程，在文本框Text1中输入要查询的单词，单击“查询”按钮Command2，将查询单词的中文含义显示在Text2中，程序界面如图所示。

（1）分析程序，“英语单词”和“中文含义”被保存在数据表中。
（2）按此要求编写的程序如下，请在画线处填入合适的代码。
Const n=3500              ’存储单词的总数
Dim a(1 To n)As String      ’依次存储每个英语单词
Dim b(1 To n) As Strin9    ’依次存储每个英语单词的中文含义
Private Sub Command1_Click()
Dim Conn As New ADODB．Connection
Dim rs As New ADODB．Recordset
Dim strSQL As String
conn．ConnectionString=“Provider=Microsoft．ACE．OLEDB．12．0；Data source=”&App．Path&“＼dictionary1．accdb”
strSQL=”select*from list”
conn．Open
Set rs．ActiveConnection=conn
rs．Open strSQL
num=0
Do While Not rs．EOF
     num=num+1
     a(mum)=rs．Fields(“英语单词”)
       b(num)=rs．Fields(“中文含义”)
       rs．MoveNext
Loop
rs．Close
conn．Close
Set rs=Nothing
Set conn=Nothing
For i==1 To n
         List1．AddItem a(i)+“ ”+b(i)
Next i
End Sub
Private Sub Command2_Click()
Dim s As String
S=Text1．Text
If search(s)=-1 Then
        Text2．text=“找不到该单词”
Else
          Text2．Text=   ①
End If
End Sub
Function search(key As String)As Integer
Dim i，j As Integer
Dim mid1，mid2 As Integer
i=1：j=n
search=-1
Do While i<=j
       mid1=Int(j+(j—i)／3)
       mid2=Int(j-(j-i)／3)
       If key=a(mid1)Then
            search=mid1
            Exit Do
       ElseIf key<a(mid1)Then
            j=mid1-1
     ElseIf key=a(mid2)Then
            search=mid2
            Exit Do
       Elself key>a(mid2)Then
            i=mid2+1
       Else
            i=mid1+1
               ②
     End If
Loop
End Function
①    ②

【加试题】数组a中有50个互异的整数，已按升序排列。给定一个正整数key，寻找数组a中是否有一对数的和等于给定的数key，算法如下：

若存在和为key的数对，输出该数对包含的两个整数，小的在前，大的在后；

若存在多个数对满足条件，则输出最先找到的数对；

若找不到符合要求的数对，则输出“没有符合条件的数对”。

根据上述算法，小黄编写了一个VB程序，功能如下：程序加载时，自动生成50个互异的、按升序排列的随机正整数，依次存入数组a中，并显示在列表框List1中。在文本框Text1中输入key的值，单击“查找”按钮Command1，查找结果在列表框List2中输出。程序运行界面如图所示。

（1）实现上述功能的VB程序如下，请在画线处填入合适代码。
Dim a(1 To 50)As Integer

Const n As Integer=50

Private sub form_load（）

‘生成50个互异的、被升序排序的随机正整数，依次存人数组a中

‘代码略

End Sub

Private Sub Command1=_Click()

Dim M As Integer，L As Integer，R As Integer

Dim key As Integer，flag As Boolean

flag=false：key=Val(Text1．Text)

For i=1 To n-1

    L=i+1：R=n

    Do While    ①

    M=    ②

    If a(i)+a(M)<key Then

      L=M+1

    Else lf a(i)+a(M)：>key Then

      R=M-1

    Else

    List2．AddItem Str(a(i))+””+    ③

      flag=True

    End If

  Loop

If Not flag Then List2．AddItem”没有符合条件的数对!”

End Sub

① ② ③
（2）对于6个数据(12，23，35，46，57，68)的序列，若给定key的值是58，则根据上述代码查找的结果是。

编写VB程序代码，实现如下功能：在文本框Text1中输入金额(整数)后，点击“转换”

按钮Command1，则在文本框Text2中显示该金额的大写，程序运行界面如下图所示:

（1）要使窗体标题上显示的文本改为“人民币大小写”，可在其属性窗口中将属性的属性值改为“人民币大小写”。
（2）为了实现以上程序功能，使程序正常运行，请完善以下两处代码。
Private Sub Command1_Click()

Dim dx As String, dw As String

Dim s As String, c As String

Dim ch As String

Dim i As Integer

dx = "零壹贰叁肆伍陆柒捌玖拾"

dw = "亿仟佰拾萬仟佰拾元"

s = Text1.Text

If Len(s) > 9

    Text2.Text = "输入的数据超出所能转换的范围"

Else

    For i = 1 To Len(s)

       ch =

       c = c + Mid(dx, Val(ch) + 1, 1) + Mid(dw, 9 - Len(s) + i, 1)

    Next i

    Text2.Text = c + "整"

End If

End Sub
（3）由上述算法可知，若在文本框Text1中输入“20”，则文本框Text3显示的结果为。

【加试题】删数问题。输入一个数字串s，删去其中k个数字(k<数字串中数字的个数)，使剩余数字在保持相对位置不变的情况下构成一个值最小的整数。例如，s=“19990608”，k=4,处理结果为：608。

删数的算法如下：

⑴如果k>0,则从前往后检测相邻字符，否则，转⑶；

⑵①若所有相邻字符都已非降序，则将串尾k个字符删去，k值置0，转⑴；

②若相邻两数存在逆序（即前一个数>后一个数），则将前一个数删除，k值变化，然后回到⑴；

⑶去掉串首的0，输出结果。

按照上述算法思路，编写了VB程序，功能如下：在文本框Text1中输入数字串，在文本框Text2中输入删数的个数，单击“处理”按钮Command1，在文本框Text3中显示最小的整数。程序运行界面如图所示。

（1）如果输入的数字串为“20160125”，删除个数为4，则结果是。
（2）实现上述功能的VB程序如下，请在划线处填入合适代码。
delete函数说明：delete(st,x,y)为自定义函数，功能为在字符串st中删除x位置开始的y长度的子串。

Private Sub Command1_Click()

Dim s As String, k As Integer, i As Integer, j As Integer, n As Integer

s = Text1.Text

k = Val(Text2.Text)

n = Len(s)

Do While k > 0

i = 1

Do While i < n And

    i = i + 1

Loop

If i = n Then



     n = n - k

     k = 0

Else

     s = delete(s, i, 1)

     n = n - 1



End If

Loop

i = 1

Do While n > 1 And Mid(s, 1, 1) = "0"

   s = delete(s, 1, 1)

   i = i + 1

   n = n - 1

Loop

   Text3.Text = s

End Sub

Function delete(st As String, x As Integer, y As Integer) As String

delete = Mid(st, 1, x - 1) + Mid(st, x + y) 'mid函数第3个参数省略，则截取从开始位置向右到字符串结尾的所有字符

End Function

小明用VB编写了查找第二小的数的程序界面如图所示，程序随机产生50个范围在1~1000之间的随机整数，单击“查找”按钮能够在标签 Label1中显示第二小的数字。

Private Sub Command1_ Click( )

Dim n As Integer, i As Integer

Dim a(1 To 50) As Integer

Randomize

For i=1 To 5

①

List1 AddItem Str(a(i))

Next i

If a(1) < a(2) Then

firstmin=a(1)

secondmin =a(2)

Else

firstmin=a(2)

secondmin=a(1)

End if

For i=3 To 50

If a(i) < secondmin Then

If ② then

Secondmin = firstmin

firstmin = a (i)

Else

③

End If

Next i

Label1. Caption = "第二小的数是" str(secondmin)

End Sub

（1）为了在列表框List1中加入随机产生的数字，小明在程序中写了语句 “List1. AddItem Str(a(i))”，其中Addltem是List1对象的。（填字母：A .属性/B .事件/C .方法）
（2）为实现上述功能，请在划线处填入合适的代码。
① ② ③

数组d(1)~d(100)中存储某班级50位同学的语文和数学成绩，奇数位存储语文成绩，偶数位存储对应该同学的数学成绩。该数组已经按照两科总成绩升序排序。依据对分查找思想，设计一个在数组a中查找总成绩Key的程序，如果查找成功输出语文成绩在数组中的位置。实现该功能的VB程序段如下：

Key = Val(Text1.Text)

i = 1: j = 100

Do While i <= j

m = (i + j) \ 2

If (1) Then m = m - 1

Sum = (2)

If Key = Sum Then Exit Do ‘Exit Do表示退出循环

If (3) Then

i = m + 2

Else

j = m - 2

End If

Loop

If i > j Then Text2.Text = "没有找到!" Else Text2.Text = Str(m)

实现该功能,则上述程序段3个方框处的表达式分别为（）

A . (1)m Mod 2 = 1 (2)d(m) + d(m - 1) (3)Key < Sum B . (1)m Mod 2 = 1 (2)d(m) + d(m + 1) (3)Key > Sum C . (1)m Mod 2 = 0 (2)d(m) + d(m - 1) (3)Key > Sum D . (1)m Mod 2 = 0 (2)d(m) + d(m + 1) (3)Key > Sum

淳安千岛湖中有若干座岛屿，有些岛屿之间有桥相连，有些岛屿之间无桥相连，可以通过其它的岛屿相连。现在我们来建立一种关系矩阵模拟这种现象，如有9个岛屿，依次编号为1～9，相互之间有桥相连在矩阵中用1表示；无桥相连用0表示；对于自身也用0表示，即矩阵的左上角到右下角的对角线全为0。

李同学设计了一个用来求两座岛屿之间相连所需桥的数量的VB程序，点击“生成矩阵”按钮Command1，随机产生一个关系矩阵，并在列表框List1中显示。在文本框Text1和Text2中输入岛屿的编号（1～9），点击“求解”按钮Command2，在Labell中输出两座岛屿之间相连所需桥的数量。VB程序运行界面如图所示。

对无桥相连的两座岛屿p1，p2之间相连的算法思想如下：

①p1岛屿所在行开始，将与其相连的岛屿依次添加到数组b中。

②若数组b中未出现岛屿p2,则依次查找与其相连岛屿的所在行，将新出现的相连的岛屿添加到数组b中。

③在查找过程中同时记录查找步数。

数组b内全部搜索完毕，若p2还是未出现，则两座岛屿之间无法相连，反之输出桥的数量。请回答以下问题：

（1）如上图所示的矩阵，从5号岛屿到9号岛屿最少需要经过座桥。
（2）请在划线处填入合适的代码。
Const n = 9              ‘岛屿的数量

Dim a(1 To n * n) As Integer

Private Sub Command1_Click()

Dim s As String List1.Clear

For i = 1 To n

   For j = i To n

   If j = i Then

     a((i - 1) * n + j) = 0    ‘对角线为0

    Else

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

         ①          ‘矩阵对称

    End If

   Next j Next i

For i = 1 To n

    s = ""

    For j = 1 To n

        s = s + Str(a((i - 1) * n + j))

    Next j

    List1.AddItem s Next i

End Sub

Private Sub Command2_Click()

Dim b(1 To n) As Integer

Dim qiao(1 To n) As Integer     ‘记录相连岛屿之间桥的数量

Dim find(1 To n) As Boolean     ‘记录某岛屿是否被添加到数组b中

Dim p1 As Integer, p2 As Integer, cur As Integer, k As Integer, q As Integer

p1 = Val(Text1.Text)

p2 = Val(Text2.Text)

cur = p1: k = 1: q = 0

find(cur) = True

Do While find(p2) = False

   For i = 1 To n

      If a((cur - 1) * n + i) = 1 And find(i) = False Then

        b(k) = i: k = k + 1

        find(i) = True

                 ②

    End If

   Next i

   q = q + 1

   If q = k Then Exit Do Else      ③

Loop

If find(p2) = True Then

    Label1.Caption = "需要经过" + Str(qiao(p2)) + "座桥"

Else

   Label1.Caption = "无桥相连"

End If

End Sub

① ② ③

有如下VB程序段：

a(1)=2: a(2)=6: a(3)=8: a(4)=9: a(5)=12

a(6)=15: a(7)=17: a(8)=18: a(9)=22: a(10)=30

k=Val(Text1.Text)

i=1: j=10

Do While i<=j

m=(i+j)\2

If a(m)<=k Then

i=m+1

Else

j=m-1

End If

Loop

Text2.Text=Str(a(i))+"←→"+Str(a(j))

程序运行时，若在文本框Text1中输入5，则文本框Text2中显示的内容是（）

A . 2←→1 B . 6←→8 C . 2←→6 D . 6←→2

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

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

s = 0: i = 1: j = 10

Do While i <= j

m = (i + j) \ 2

If Key = a(m) Then Exit Do

If Key < a(m) Then

j = m - 1: s = s * 2

Else

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

End If

Loop

数组元素a(1)到a(10)的值依次为“3,13,15,20,28,35,45,52,63,97”，执行该程序段后，s的值不可能为（）

A . 1 B . 5 C . 9 D . 14

下列有关查找算法的说法，正确的是（）

A . 进行对分查找时，被查找的数据必须已按升序排列 B . 进行对分查找时，如果查找的数据不存在，则无需输出结果 C . 在新华字典中查找某个汉字，最适合使用顺序查找 D . 对规模为n的数据进行顺序查找，平均查找次数是

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

Key=Val（Text1.Text）

i=1：j=6

n=0：f=False

flag=False

Do While i<=j And Not f

n=n+1

m=Int（（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（6）的值依次为“3，9，12，17，28，39”，在文本框Text1中输入17后运行该程序，则以上程序段运行结束后，下列说法不正确的是（）

A . 变量i的值为4 B . 变量j的值为4 C . 变量m的值为4 D . 变量n的值为4

找数对。已知一数组a中有9个元素，在文本框Text1中输入一个正整数key，单击“找数对”Command1按钮，则在数组a中搜索是否有一对数的和等于key，若有，在标签Label2中输出最先找到的两个数，若无则输出“没有找出数对”。运行界面如图所示：

（1）根据程序，若文本框Text1中输入内容为17，则标签Label2中输出的内容是。
（2）请划线处填入合适的代码。
Const n = 9

Dim a(1 To n) As Integer,i As Integer, j As Integer

Private Sub Form_Load()

Dim s As String, k As Integer

a(1) = 9: a(2) = 13: a(3) = 11: a(4) = 3: a(5) = 20

a(6) = 6: a(7) = 18: a(8) = 15: a(9) = 8

For i = n To 2 Step -1

  k = i

   For j =

    If a(j) < a(k) Then t = a(j): a(j) = a(k): a(k) = t

   Next j

          '③改错

Next i

Label1.Caption = s End Sub

Private Sub Command1_Click()

Dim L As Integer, R As Integer, m As Integer, key As Integer

key = Val(Text1.Text)

For i = 1 To n - 1

   L = 1: R = n

   Do While L <= R

      m = (L + R) \ 2

    If a(i) + a(m) = key Then

      Label2.Caption = Str(a(i)) & Str(a(m))

        Exit For

      ElseIf Then

        L = m + 1

      Else

        R = m - 1

      End If

  Loop

Next i

If L > R Then Label2.Caption = "没有找到数对"

End Sub
（3）请改正加框处语句的错误。

编写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)

数组a 中存储的是左右交替上升的n个正整数，如下表所示：

a(1)	a(2)	a(3)	……	a(n-2)	a(n-1)	a(n)
3	25	38	……	55	31	12

依据对分查找思想，设计一个在数组a中查找数据key 的程序，实现该功能的VB程序如下，但加框处代码有错，请改正。

Private Sub Command1_Click()

Const n = 6

Dim a(1 To n) As Integer, flag As Boolean

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

‘读取一组正整数，按上述规则存入数组a中，代码略

key = Val(Text1.Text)

i = 1

j = (n + 1) \ 2

flag = False

Do While And Not flag ‘⑴

m = (i + j) \ 2

If key = a(m) Then

flag = True

ElseIf key < a(m) Then

j = m - 1

Else

i = m + 1

End If

Loop

If Not flag And j > 0 Then

m = ‘⑵

If key = a(m) Then flag = True

End If

If flag Then

Text2.Text = Str(m)

Else

Text2.Text = "找不到"

End If

End Sub

⑴⑵

用VB编程求两个字符串的最长连续公共子串，程序功能如下：在文本框Text1和Text2中分别输入任意两个字符串s1和s2，单击命令按钮 Command1，在标签 Label3和Label4中分别输出这两个字符串的最长连续公共子串和子串的长度其算法思想：分别从字符串s1和s2的左边第一个字符开始检查，若发现这两个字符串中有一个字符相同，则以这个字符为基准向右边扩大搜索范围，先检查其后面的第一个字符是否相同，若还是相同则继续搜索，直到找到不同的字符为止。然后按照该方法依次继续往后搜索，直到查找结束。程序界面如图所示，请回答下列问题：

（1）根据代码，若输入的s1为“Teacher”，s2为“teacher”，则最长连续公共子串为。
（2）实现上述功能的VB程序如下，请在划线处填入合适代码。
Dim s1 As String, s2 As string, maxstr As string

Dim len1 As Integer, len2 As Integer, maxlen As Integer

Function Min (a As Integer, b As Integer) As Integer

    If a >=b Then min = b else min = a

End Function

Function Search (m As Integer, n As Integer) As Integer

    Dim c As Integer

    c = 1

    Do While c<= Min (len1 -m, len2 - n)

        If Mid (s1, m+ c, 1) = Mid(s2,n+c,1) Then



        Else

            Exit Do 'Exit Do的作用是退出Do循环

        End if

  Loop

   Search = c -1

End function

Private Sub Command1_Click()

    s1 = Text1. Text

    s2 = Text2. Text

    len1 = Len (s1)

    len2 = Len (s2)

    maxlen = 0: maxstr = ""

    Dim i As Integer, j As Integer, k As Integer

   For i=1 To len1

        For j=1 To len2

            If Mid(s1, i, 1) = Mid(s2,j,1) Then

                k =  'k用于记录连续公共子串的长度

                If (k> maxlen) Then

                    maxlen = k

                    maxstr =

                End if

            End If

        Next j

    Next i

    Labe13. Caption= "最长连续公共子串为:"& maxstr

    Labe14. Cantion = "该子串长度是:"& str (maxlen)

End sub

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

i=1：j=7

f=False

key=Val（Text1. Text）

Do While i<=j And Not f

m=（i+j）\2

If a（m）=key Then f=True

If a（m）>key Then i=m-1 Else i=m+1

Loop

List1. AddItem Str（i）+Str（j）+Str（m）

数组元素a（1）到a（7）的值依次为"23，42，58，66，77，83，98"，运行上述程序段后，列表框List1中

显示的结果为"5 4 5"，则文本框Text1中输入值的范围是（）

A . [66，77] B . [66，77） C . （66，77] D . （66，77）

某学校图书管理系统中有10万条图书资料记录(已经索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为(　　)

A . 100万毫秒 B . 50万毫秒 C . 10毫秒 D . 170毫秒

编写一个单词查找程序，其功能是：在文本框Text1中输入要查找的单词，单击“查找”按钮Command1后，在标签Label4中输出查找结果。程序运行效果如下图所示。

算法说明：

1)英语单词存放在数组words中。

2)如果在数组words中找到要查找的单词，则在标签Label4中显示“查找成功！”，并显示单词在数组words中出现的次数，如果未找到则显示“无此单词，请重输！”。

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

Dim n As Integer

Dim words(1 To 100) As String

Private Sub Command1_Click()

Dim key As String, i As Integer, times As Integer

key = Text1.Text

times = 0

For i = 1 To n

If key=words(i) Then

Next i

If times > 0 Then

Label4.Caption=“查找成功！共找到”+ +“个”

Else

Label4.Caption = “无此单词，请重输！”

End If

End Sub

Private Sub Text1_KeyPress(KeyAscii As Integer)

Dim word As String

word = Text1.Text

If KeyAscii = 13 Then

n = n + 1

List1.AddItem Str(n) + “：” + word

Text1.Text = “ ”

End If

End Sub

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

i=1: j = 5: k=0: s =""

key = Int (Rnd * 100)

Do While i<=j

k=k+1

m=(i+j)\2

s = s+Str(a(i))

If key = a(m) Then

Exit Do ‘ExitDo表示退出循环

Elself key < a(m) Then

j =m-1

Else

i=m+1

End If

Loop

Text1. Text = s

数组元素a(1)到a(5)的值依次为“6，18，25；37 ，49”。若该程序段执行后，k的值为3，则key的值不可能为( )

A . 4 B . 18 C . 47 D . 55

采用如下对分查找算法对数组a(1)到a(8)中8个有序数据“1，5，8，13，16，27，31，39”进行查找，其程序如下：

i =1 : j=8 : x=27 : mark = False

Do While i <= j And Not mark

m=(i+j+1)\2

If a(m) = x Then mark = True

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

Text1. Text = Text1. Text+Str(m)

Loop

执行该程序段，文本框Text1中显示的是（）

A . 46 B . 476 C . 163127 D . 576

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

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