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

编写VB程序,实现如下功能：在文本框text1中输入自然数n，单击“产生n个随机数,并求和与最大数计算”按钮Command1，则在列表框List1中输出n个小于100的随机整数，并输出n个随机数的和与最大值，界面如图所示。

（1）观察运行界面，选项中没有用到的控件是 ( 选项

A . B . C . D . )。
（2）设计该窗体界面时，需要将窗体form1的属性设置为“最大随机数”。
（3）请完善下列程序代码：
Private Sub Command1_Click()
Dim a(1 To 10) As Integer
Dim s As Integer
Dim max As Integer
n = Val(Text1.Text)
i = 1
Do While i <= n
   a(i) = Int(Rnd * 100)
   List1.AddItem Str(a(i))
   s = s + a(i)
①
Loop
max = a(1)
For i = 2 To n
   If a(i) > max Then ②
Next i
List1.AddItem "和为：" + ③
List1.AddItem "最大值为：" + Str(max)
End Sub
供①②选填：
a．n=n+1      b． i=i+1       c．max=a(i)     d． a(i)=max
空格③处应填写的代码为:。

有序数列3.6,8,11.6,22,24,27,31,36.5,35，46，通过对分查找查找数31，需找（）次

A . 4 B . 3 C . 2 D . 1

编写VB程序，实现如下功能：在文本框Text1中输入一个整数，单击“查找”按钮，找出该整数的全部的连续整数固定和，并将它们显示在列表框List1中。所谓一个数n的连续整数固定和，就是指存在a₁ ， a₂ ， …，a_n ，其中a_i+1比a_i大1，使得a₁+a₂+…+a_n=n。这样a₁ ， a₂ ， …，a_n称为n的一个连续整数固定和。例如27的全部的连续整数固定和有3组，运行界面如图所示，实现上述功能的VB代码如下，但加框处代码有错，请改正。

Private Sub Command1_Click()

Dim i As Integer, j As Integer, sum As Integer

Dim n As Integer

n = Val(Text1.Text)

sum = 0

List1.Clear

For i = 1 To n ' ①

j = i - 1

Do While sum <= n ' ②

j = j + 1

sum = sum + j

Loop

If sum = n Then

List1.AddItem Str(i) & " + ... +" & Str(j) & "=" & Str(n)

End If

sum = 0

Next i

End Sub

① ②

【加试题】小明设计了一个查找数据的程序：在一组升序的数列当中，查找不小于k的最小数的位置，如果该值存在，则返回其第一次出现的位置，如果不存在则返回0。

程序界面如图所示：

（1）若在Text1中输入“8”，Text2，Text3输出的分别为。
（2）请在画线处填入合适的代码。
Dim a(1 To 10)As Integer

  Function find(L As Integer，R As Integer，key As Integer)As Integer

   If L>R Then

        find=0：Exit Functionhp

    ElseIf a(L)>=key Then

      find=L：Exit Function

Else

           ①

        If a(M)<key Thenhp

            find=find(M+1，R，key)

       ElseIf    ②     Then

            find=find(L，M-1，key)

         Else

              find=M

         End If

   End If

End Function

Private Sub Command1 Click()

  Dim k As Integer

   Dim P As Integer

   k=Val(Text1．Text)

       ③

   Text2．Text=a(P)

   Text3．Text=Str(P)

   If p=0 Then

       Text2．Text=“无”

   End If

End Sub

Private Sub Form Load()

   a(1)=3：a(2)=3：a(3)=3：a(4)=4：a(5)=7：a(6)=7

  a(7)=10：a(8)=13：a(9)=19：a(10)=21

  For i=1 To 10

      List1．AddItem Str(a(i))

   Next i

End Sub

① ② ③

【加试题】问题描述：有n个互不重复的数字，值的范围是[1,n]，分别保存在数组元素a(1)到a(n)中，如果数字i保存在a(i)，认为数字i在正确的位置上。若干个相互占用了位置的数字称为一组，一个在正确位置上的数字单独为一组，比如6个数字2,3,1,4,6,5分别保存在数组元素a(1)到a(6)中，则2、3、1为一组，4为一组，6、5为一组。该程序的功能为输出每组的情况。运行界面如下图：

（1）数组元素a(1)到a(5)的值分别为2、5、3、1、4，这5个元素总共有组。
（2）请在划线处填入合适的代码
Const n = 10
Dim a (1 To n) As Integer    ‘保存原始数据
Dim b(1 To n ) As Boolean ‘数组b用来标记相应的位置有没有找过
Private Sub Command1 _ Click ()
    Dim i As Integer , sum As Integer , total As Integer
    sum = 0: total = 1 ‘total 表不第几组
    i = 1
    List 2.Addltem “第”& Str (total) & “组”
    Do While sum < n
        Do While Not b (i)
            List 2.Addltem a (i)
            b(i) = True

            sum = sum + 1
        Loop
        If sum < n Then
            total = total + 1
            List 2.Addltem “第” & Str ( total ) &■“组”
            i = 1
            Do While b(i) ‘该循环用来查找下一组的开始位置

            Loop
        End If
    Loop
End Sub
Private Sub Form _ Load ()
Dim i As Integer
Randomize
For i = 1 To n ‘产生 n 个不一样的整数，范围为[ 1, n ]
    a(i) = Int(Rnd * n ) + 1
    Do While
        a (i) = Int(Rnd * n ) + 1
    Loop
Next i
For i = 1 To n
    List1.Addltem a (i)
    b (i) = False
Next i
End Sub
Function f(x As Integer , y As Integer ) As Boolean
‘该函数的功能：判断x和数组a中前y个数有没有重复，有重复返回值True,否则False
End Function

【加试题】用如下对分查找算法VB程序段，对数组a中7个有序数据“20,30,35,42,46,50,53”进行查找。

i=1:j=7:x=45

Do While i <= j

m = (i + j) \ 2

If a(m) = x Then Exit Do ‘Exit Do 退出 Do 循环

If a(m) > x Then

j = m - 1

Else

i = m + 1

End If

Loop

执行完上述代码后，根据最终变量值判断下列表达式，其中成立的是（）

A . i = j B . i = m + 1 C . j = m - 1 D . j = m

有如下VB程序段

Dim a(1 To 6)As Integer, I AS Integer, maxi As Integer

a(1)=12：a(2)=8：a(3)=14：a(4)=13：a(5)=12：a(6)=11

Maxi=1

For i=2 To 6

If a(i)>a(maxi)Then maxi=i

Next i

a(1)=a(1)+a(maxi)：a(maxi)=a(1)-a(maxi)：a(1)=a(1)-a(maxi)

执行该程序段后，数组元素a(1)~a(6)的值是（）

A . 14 12 8 13 12 11 B . 14 8 12 13 12 11 C . 13 8 14 12 12 11 D . 14 8 14 13 12 11

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

步骤1：如果待筛选的玻璃球个数小于或等于，则认定已经找出了这颗玻璃球（认定方法参照步骤2中描述），停止筛选，并输出筛选总次数；否则，重复执行步骤2。

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

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

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

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

重复执行步骤1。

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

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

（1）如果编号为88的小球是较轻的，按照题中给定算法，到此小球需经历的筛选次数是。
（2）实现上述功能的VB程序如下。请在划线处填入合适的代码。
Const maxn = 100

Dim a (1 To maxn) As Integer

Dim w (1 To 2) As Integer     ‘ 数组w用来存储第1份和第2份小球的质量

Private Sub Form Load ( )

‘ 此处代码用来模拟产生100个小球的质量,分别存储在数组元素a(1)~a(100)中

‘ 其中只有1个小球的质量为8,随机存储在数组a的某元素中,其余质量均为10

‘ 此处代码略

End Sub

Private Sub Command1_Click( )

Din 1eft As Integer, right As Integer     ‘ left为起始编号, right为结束编号

Dim s As Integer, C As Integer     ‘s 为每次查找的区间长度

left = 1:right = maxn

c = 1:s = right:i = 0

List2 AddItem Str(i+1) +"---->” + Str(maxn)

Do While right - left > =3

w(1) = o:w(2) = 0:k =1

i = left

  s =       ①

Do While i < = (s \3)*2 + left -1

‘Do语句用于将待筛选的数据进行区域划分

    w(k) = w(k)+a(i)

    If i = (s\3)*k+ left -1 Then k = k+1

    i = i+1

Loop

If w(1) = w(2) Then

    left = left + (s\3)*2

ElseIf w(1) < w(2) Then

            ②

Else

    right = left+(s\3)

    left =s\3+ left

End If

        ③

List2. AddItem Str (left) & ”---->” & str(right)

Loop

List2. AddItem "经过”+s tr(c) +" 次后找到”

End sub

① ② ③

一组“非降序”的数据分别存储在数组元素a(1)~a(n)中，用对分查找算法在数组a中查找key值所在的位置，如果有重复的元素，则显示最小的位置。部分VB程序如下：

key = Val (Text1. Text)

i = 1: j = n

Do While i < = j

m = (i+j) \2

If a(m) > key Then

j = m - 1

ElseIf a(m) < key Then

i = m + 1

Else

if Then

j = m-1

Else

Label2. Caption = str(key) +“的起始位置是”+ str(m)

Exit Do

End If

End if

Loop

If i > j Then

Label2. Caption = “找不到” + str(key)

End If

要使程序实现上述算法思想，则方框中的正确语句是（）

A . a(m-1) = key B . a(m) = key C . m-1 > 0 And a(m-1) = key D . m-1 > 0 And a(m) = key

有序（非降序）数组A有n个元素，用对分查找算法在数组A中查找key值所在的位置，如果有重复的元素，则显示最早出现该key值的位置。相应的VB程序段如下：

key = Val(Text1.Text)

i = 1: j = n

Do While i <= j

m = (i + j) \ 2

If a(m) > key Then

j = m - 1

ElseIf a(m) < key Then

i = m + 1

Else

If Then

j = m - 1

Else

Label2.Caption = Str(key) + "的起始位置是" + Str(m)

Exit Do

End If

Loop

If i > j Then

Label2.Caption = "找不到" + Str(key)

End If

要使程序实现上述算法思想，则方框中的语句是（）

A . a(m - 1) = key B . a(m) = key C . m - 1 >= 0 And a(m - 1) = key D . m - 1 >= 0 And a(m) = key

有如下VB程序段：

Dim a(1 To 10)As Integer

Private Sub Form_Load()

a(1)=2: a(2)=3: a(3)=3: a(4)=3: a(5)=3

a(6)=6: a(7)=7: a(8)=7: a(9)=8: a(10)=9

End Sub

Private Sub Command1_Click()

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

Dim m As Integer, p As Integer

key=Val(Text1.Text)

i=1: j=10

Do While i<=j

m=(i+j)\2

If a(m)= key Then

p=m

j=m-1

ElseIf key<a(m)Then

j=m-1

Else

i=m+1

End If

Loop

Text2.Text=Str(p)

End Sub

程序运行时，在文本框 Text1中输入3，单击按钮，文本框Text2中显示的内容是（）

A . 2 B . 3 C . 4 D . 5

（加试题）编写一个成绩查询程序，输入要查找的分数，输出该分数的名次及同分人数，其算法是：用数组a存放不同的分值，数组m存储相同分数的人数，数组mc存储不同分数的名次。例如，数据库中有一组成绩（已按降序排列）：98，95，95，92，90，90，87，按该算法，各数组值如下表所示：

i	1	2	3	4	5
a	98	95	92	90	87
m	1	2	1	2	1
mc	1	2	4	5	7

程序界面如下图所示，在文本框Text1中输入查询成绩，点击“查找”按钮，若找到，则输出该分数的名次和同分数的人数，若找不到，则输出“查无此分”。

程序代码如下，请在划线处填入合适的代码。

Dim n As Integer

Dim a(1 To 1000) As Integer ‘存放不同的分数值

Dim m(0 To 1000) As Integer ‘存放相同分数的人数

Dim mc (0 To 1000) As Integer ‘存放此分数的名次

Private Sub Form_Load()

Dim conn As New ADODB. Connection

Dim rs As New ADODB. Recordset

Dim tmp As Integer

Dim s As Integer

tmp = -1: n = 0

conn. Connectionstring = “provider=Microsoft. ACE．OLEDB. 12. 0; data source=”& App. Path & “\mydb. accdb”

conn. Open

Set rs. ActiveConnection = conn

rs.Open "Select * from score"

mc(0) = 1: m(0) = 0

Do While Not rs. EOF

s = rs. Fields (“成绩”)

If s = tmp Then ‘当前读入分数与上一个分数相同

m(n) = ①

Else

n = n + 1

a(n) = s

m(n) = 1

mc(n) = ②

End If

③

rs. MoveNext

Loop

End Sub

Private Sub Command1_Click0

Dim key As Integer, i As Integer, j As Integer, mid As Integer

key = Val (Text1.Text)

i = 1: j = n

mid = (i + j) \ 2

Do While i <= j And ④

mid = (i + j) \ 2

If a(mid) < key Then

j = mid – 1

Else

i = mid + 1

End If

Loop

If a(mid) = key Then

Label2. Caption = “名次: ”+ Str(mc (mid)) + “同分人数: ”+ Str(m(mid))

Else

Label2. Caption =“查无此分”

End If

End Sub

① ② ③ ④

已知一无序数组A中的元素为“90，15，40，72，65，32，81，6”通过引入数组a元素按升序排列时的下标，b数组元素为“8，2，6，3，5，4，7，1”，使得a(b(1))<=a(b(2))<=a(b(3))…<=a(b(n))，从对数组a中的数据进行对分查找。部分程序如下：

i=1: j=8: c=0

Key=Val(Text1.Text)

Do While i<= j

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

t=b(m)

c=c+1

If a(t)=Key Then p=t: Exit Do

If a(t)< Key Then

i=m+1

Else

j=m-1

End If

Loop

当文本框Text1输的值为32时，程序运行结束后变量c的值是（）

A . 1 B . 2 C . 3 D . 4

编写一个基于对分查找插入数据的程序代码。实现把数据temp插入降序序列后得到一个新的降序序列，原序列各元素存放在数组元素a(1)-a(n)中。实现上述功能的程序段如下：

temp = Val(Text1.Text)

If temp <= a(n) Then

a(n + 1)= temp

Else

left= 1: right= n

Do While left <= right

mid = (left + right) \2

If ① Then right= mid- 1 Else left= mid+ 1

Loop

For j= n To left Step-1

②

Next j

③

End If

则横线①②③上的语句分别是（）

A . ①a(mid)>temp ②a(j)=a(j-1) ③a(right+1)=temp B . ①a(mid)<temp ②a(j)=a(j-1) ③a(left)=temp C . ①a(mid)>temp ②a(j+1)=a(j) ③a(right+1)=temp D . ①a(mid)<temp ②a(j+1)=a(j) ③a(left)=temp

某对分查找算法的VB 程序段如下: key=Val(Text1.text)

s = 0: i = 1: j = 11

Do While i <= j

m = (i + j) \ 2

If Key > a(m) Then

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

Else

j = m - 1: s = 2 * s

End If

Loop

Text2.Text = Str(s)

数组a(1)到a(11)的值依次为“2,13,24,31,35,44,47,50,61,88,101”，在文本框Text1中输入下列选项值，所得输出结果与其他三项不相同的是（）

A . 25 B . 34 C . 35 D . 65

数组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

For j = i To right-1

a(j) = a(j + 1)

Next j

________________

i = i-1

s = “”

For j = 1 To n

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）若删除语句“If a(m) = t Then right = m: ExitDo”，则下列说法正确的是(单选，选填字母：A .程序进入死循环，无法正常运行/B .输出排序的结果不变/C .输出排序的结果将改变)。

某vb程序段如下：

L=1: R=10: n=10: key=78

Do While L<=R

m=Fix((L+R)/2)

If Then

R=m-1

Else

L=m+1

End If

Loop

For i=1 To R

List1.Additem Str(a(i))

Next i

数组元素a(1)到a(10)的值依次为86,78,78,77,73,69,60,54,54,51，若执行该程序段后，列表框List1中输出的数据个数为3，则方框处的代码为（）

A . Key>a(m) B . Key>=a(m) C . Key<a(m) D . Key<=a(m)

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

key = Val(Text1．Text)

s="" ：i=1；j= 10

Do While i<=j

m=(i+j)\2

If a(m)= key Then Exit Do 'Exit Do表示退出循环

If key < a(m) Then

j=m-1：s=s+"L"

Else

i=m+1 ：s=s+ "R"

End If

Loop

按非降序排序的整型数组a(1)到a( 10)的值依次为“11，23，31，39，44，52，60，x，69，89”。在文本框Text1中输入66，执行该程序段后s值为“RRL”，则x的可能值的个数为( )

A . 3 B . 4 C . 5 D . 6

在数组元素a(1)到a(8)中查找键值为key的数，其顺序查找的VB程序段如下，请在划线处填写正确的语句。

for i=1 to 8

if 　then

Text1.text=str(i)

exit for

end if

next i

if then

text1.text=″在数组中没有找到″+str(key)

end if

小明和小华玩猜数字的游戏，所猜数字不超过800，小明首先猜400，小华说大了，小明又猜200，当小华再次说大了，小明猜100，当小华说小了，小明猜150，以此类推，直到猜到正确的数字。上述方法中蕴含的算法思想是（）

A . 穷举算法 B . 递归算法 C . 二分查找法 D . 顺序查找法

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

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