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

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

i=1:j=6:flag=False key=Val(Text1.Text)

Do While i<=j And flag = False

m=(i+j)\2

If key=a(m) Then flag=True

If key<a(m) Then j=m-1 Else i=m+1 Loop

数组元素a(1)到a(6)的值依次为“7，9，15，27，34，51”。文本框Text1中输入“27”后运行该程序，运行结束后，下列说法不正确的是（）

A . 变量flag的值为True B . 变量i的值为5 C . 变量 j 的值为4 D . 变量 m 的值为4

编写一个成绩查找程序，只要输入成绩，即可输出其排名、同分数的人数以及比此分高的人数。具体算法思路如下：

⑴预处理。用数组a存放不同的分值，数组b存放相同分数的人数，数组s存放高于此分数的人数，数组下标表示名次。依次从数据库读取每个学生的成绩(数据库中每个学生的成绩已降序存储，即从高到低排列)，当读入数与前一个数相同时，该名次的人数加1，当读入数与前一个数不同时，名次加1，即数组下标加1，存储当前分数，求高于本分数的人数并存储。

举例：如果数据库中有一组成绩(降序)：95，95，93，93，92，91，90，按上述算法处理，三个数组的最终结果如图所示。

数组/下标	1	2	3	4	5
a	95	93	92	91	90
b	2	2	1	1	1
s	0	2	4	5	6

⑵对需要查找的成绩二分查找。读入需要查找的成绩x，在数组a中二分查找成绩，若找到，输出名次、相同分数的人数和高于本分数的人数;若找不到，输出“查无此分”。

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

Dim rank As Integer

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

Dim b(1 to 1000) As Integer ‘存放相同分数的人数

Dim s(1 to 1000) As Integer ‘存放高于此分数的人数

rank=0

Private Sub Form_Load()

Dim conn As New ADODB.Connection

Dim rs As New ADODB.Recordset

Dim tmp As Integer, n As Integer

tmp=-1: n=0

conn.ConnectionString=“provider=Microsoft.ACE.OLEDB.12.0;data source=“App.Path+”Score.accdb”

conn.open

Set rs.ActiveConnection=conn

rs.open “Select * from score”

n=0

Do While Not rs.EOF

n=n+1

mark=rs.fields(“成绩”)

If mark=tmp Then ‘当前读入分数与上一个分数相同，则对应名次的人数增加1

b(rank)=b(rank)+1

Else ‘当前读入分数与上一个分数不同时

rank= ‘名次增加1

a(rank)= ‘存储当前分数到数组a中

s(rank)= ‘求高于本分数的人数并存储至数组s

b(rank)=1 ‘将自身统计入同分人数

End If

‘更新上一个分数

rs.Movenext

Loop

End Sub

Private Sub Command1_Click()

Dim x As Integer, low As Integer, high As Integer, mid As Integer

x=Val(Text1.Text)

low=1: high=rank

mid=(low+high)\ 2

Do While low <=high and

mid=(low+high)\ 2

If a(mid) < x Then

high=mid-1

Else

low=mid+1

End If

Loop

If a(mid)=x Then

Label1.Caption=“名次:“+mid+”同分人数:“+b(mid)+”高于此分人数:”+s(mid)

Else

Label1.Caption=“查无此分”

End If

End Sub

多数高次方程不存在求根公式，求精确根非常困难，因此寻找方程的近似根就显得特别重要。由于数轴上的点是有序的，所以我们可以用对分查找法找出高次方程在某一区间的实根，即：不断地将区间对分，使得区间中点的值不断逼近方程的根，当区间小于精度的时候我们就停止对分，并用此时区间的中点值作为方程的根。

现有三次方程y=5x^3-55x^2+170x-130，其函数图象如图所示：

观察该函数图象发现函数有一实根在区域(1.2)之间，因此我们取两者的中点m=(1+2)/2代入方程进行检测发现f(1.5)=18.125。因为f(1.5)>0，因此区间应该往左移动，得下一个区间(1,1.5)然后继续进行检测。如果区间差值≤误差率，则认为该中点是方程的根。根据上述方法描述设计一个VB求解程序的根，要求单击求解按钮Command1，在文本框Text1中显示方程的根，部分程序如下。

（1）代码“PrivateSubCommand1_Click()”中的Command1_Click()是(单选，填字母：A.对象名/B.事件名/C.事件处理过程)
（2）将划线处的代码补充完整。
PrivateSubCommand1_Click()

DimiAsDouble,jAsDouble,mAsDoubleDimrAsDouble,yAsDouble

i=1:j=2:y=1:r=j-iDoWhiley<>0Andr>0.00001

m=(i+j)/2

y=

Ify>0Then

j=m

ElseIfy<0Then

i=m

EndIf

Loop

Text1.Text=m

EndSub

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

i = 1: j = 8: s =“”

key =“sheep”

Do While i < =j

m =(i+j)\2

If key = a(m) Then

s = s + “M”

Exit Do

ElseIf key < a(m) Then

j = m-1:s = s+“L”

Else

i=m+1 : s = s +“R”

End if

Loop

Text1. Text = s

数组元素a(1)到a(8)的值依次为“tiger, snake, sheep, rabbit, pig, muse, monkey, dog”，该程序段执行后，文本框Text1中显示的内容是（）

A . LR B . RLM C . LRM D . LRL

对于无序数组a（下标1到n），通过引入数组b（下标1到n），使得a(b(1))≤a(b(2))≤a(b(3)≤…≤a(b(n))。

小王编写了一个VB程序，功能如下：在列表List1框中显示i、a(i)、b(i)、a(b(i))在文本框Text1中输入要查找的数据，单击“查找”按钮Command1后，在标签Label3中显示该数据在a数组中的位置。程序运行界面如图所示。

实现上述功能的VB程序如下，但加框处代码有错，请改正。

Dim a(1 To 8)As Integer, b(1 To 8)As Integer

Dim n As Integer

Private Sub Form_ Load ( )

‘ n = 8, 对分查找前的8个数据存储在a数组中,每个数据的位次存储在b数组中

‘ 在列表框List1中显示数组下标、a数组、b数组、a(b(i))数组

‘ 代码略

End Sub

Private Sub Command1_ Click ( )

Dim i As Integer, 3 As Integer, k As Integer

Dim m As Integer, key As Integer

key = Val (Text1. Text)

i = 1: j = n

Do While i < = j

m = (i+j) \2

k = ‘①

If key = k Then

Exit Do

Eelseif key > k Then

i = m+1

Else

j = m-1

End if

Loop

If i > j Then

Label13. Caption = “该数据不存在”

Else

Label13. Caption = ‘②

End If

End sub

① ②

图书管理系统对图书管理是按图书的序号从小到大进行管理的，若要查找一本已知序号的书，则能快速地查找的算法是（）。

A . 穷举算法 B . 解析算法 C . 对分查找 D . 冒泡排序

编写VB程序，实现如下功能：在文本框Text1中输整数x，单击“查找删除”按钮Command1，在数组a（从小到大排列并显示在标签Label1中）中查找该数。若找到，则从数组a中删除该数（该数后的数组元素都往前移一位），并在标签Label2中显示删除后的结果（运行效果如图所示）；否则在标签Label2中显示“该数没有找到”。

请在划线处填入合适代码。

Dim a(1 To 10) As Integer

Private Sub Form_Load()

'产生10个升序的随机数并显示在Label1，代码略

End Sub

Private Sub Command1_Click()

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

Dim x As Integer, f As Boolean, s As String

x=Val(Text1.Text)

i=1: j=10: f=False

Do While ①

m=(i+j)\2

If a(m)=x Then

f=True

ElseIf ② Then

i=m+1

Else

j=m-1

End If

Loop

If f=True Then

For k=m To 9

③

Next k

For k=1 To 9 '逐个显示删除后的数组元素

s=s+Str(a(k))+ ""

Next k

Else

s="该数没有找到"

End If

Label2.Caption=s

End Sub

① ② ③

某算法程序段如下：

Dim a(1 To 10) As Integer

Dim i As Integer, j As Integer

Dim key As Integer

i = 1: j = 10: n = 0

Randomize

key = Int(Rnd * 10) * 2 + 1

Do While i <= j

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

If key = a(m) Then

Exit Do

ElseIf key > a(m) Then

j = m - 1: n = n - 1

Else

i = m + 1: n = n + 1

End If

Loop

Text1. Text = Str (n)

已知数组元素a(1)至a(10)的值依次为20，19，17，16，14，11，8，5，2，0若执行该程序后，文本框Text1中显示的内容不可能是（）

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

用二分法求解 x³- x² + x - 1 = 0，完善下面程序。

def f(x):

#定义方程

return x**3-x**2+x-1

a=float(input("请输入解区间的左边界:"))

b=float(input("请输入解区间的右边界:"))

while abs(b-a)>1e-6:

x0=(a+b)/2

if:

b=x0

if:

a=x0

if:

break

print("解为:",x0)

input("运行完毕,请按回车键退出...")

有如下 VB 程序段:

For i = 1 To 6

a(i) = Int(Rnd * 20) + 1: b(i) = i

Next i

For i = 1 To 5

For j = i+1 To 6

If a(b(i))>a(b(j)) Then

t = b(j): b(j) = b(i): b(i) = t

End If

Next j

Next i

i = 1 : j = 6: s="" : Key = Val(Text1.Text)

Do While i <= j

m = (i + j) \ 2

If Key = a(b(m)) Then Exit Do

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

s = s + Str(m)

Loop

Text2.Text = s

在文本框Text1中输入10，运行以上程序段后，文本框Text2中显示的内容为 3 5 4，则 a 数组中 a(1)到 a(6)各元素的值可能的是（）

A . 11，6，4，13，18，15 B . 4，5，8，19，10，17 C . 2，11，7，6，3，18 D . 9，2，11，21，5，16

数组元素a(1)-a(2*n)中存储的一批正整数，以两个数为一组，每组中两个数均比前面一组的两个数要大。现用对分查找的思想，设计一个在数组a中查找数据key的程序，如果找到key，在标签Label1上显示“yes”，否则显示“no”。

Key=Val(Text1.Text)

i=1:j=n*2:flag=False

Do While i+1＜=j And Not flag

m=(i+j)\2

If Then m=m-1

If a(m)=Key or a(m+1)=Key Then

Flag=True

Elseif a(m)＞key Then

Else

End if

Loop

If a(i)=Key Or a(j)=Key Then flag=True

If flag Then Label1.Caption=“yes” Else Label1.Caption=“no”

划线处的代码正确的是（）

A . ①m Mod 2=1 ②j=m-1 ③i=m+2 B . ①m Mod 2=0 ②j=m-1 ③i=m+2 C . ①m Mod 2=1 ②j=m-2 ③i=m+2 D . ①m Mod 2=0 ②j=m-2 ③i=m+2

下面VB程序段功能为：将一组升序排列的数据“1，3，3，5，5，7，10，11，12，15”依次存储到数组元素a(1)到a(10)中，在文本框Text1中输人k的值，找出大于k的数据的起始位置并显示在标签Label1中。

n=10：k =Val(Text1.Text)

i=0：j= ①

Do While i<j

m =(i+j+1)\2

If k<a(m) Then j=m-1 Else i= ②

Loop

L= ③

Label1.Caption =">"+Str(k)+"的数据位置为："+Str(L)

上述程序段横线①②③处的语句依次为( )

A . ①n-1 ②m ③i B . ①n ②m ③i+1 C . ①n ②m+1 ③i D . ①n-1 ②m+1 ③i+1

有如下VB程序段：

key = Val(Text1.Text): cnt=10

For i = 1 To cnt - 1

n = key - a(i)

L = i + 1: R = cnt

Do While L <= R

m = (L + R) \ 2

If a(m) = n Then Exit Do

If a(m) > n Then R = m - 1 Else L = m + 1

Loop

If L <= R Then Text2.Text = Str(key - a(m)) + "," + Str(a(m))

Next i

在数组a(1)～a(10)中存储的数据依次为“1，4，9，16，25，36，49，64，81，100”，在Text1中输入一个不大于200的数，执行该程序后，Text2中显示的内容可能是（）

A . 1，99 B . 36，64 C . 81，25 D . 100，100

某班级学生为毕业晚会的一个节目设计一个仿“V”字的造型，先筛选出班级里所有男生，然后将参演的n 名男生按照身高，摆出中间低两边高（先右后左）的造型，如图所示。

原1-7号男生身高	171 172 180 174 176 179 178
筛选排序后序列	171 172 174 176 178 179 180
“造型设计”后序列	180 178 174 171 172 176 179

王林同学用VB编写模拟“节目造型”程序，功能如下：从数据库中导出所有学生编号、性别和身高数据；单击“筛选排序”按钮Command1，选出“男生”且按身高升序排列显示在文本框Text1中；单击“设计造型”按钮Command2，根据身高仿“V”字的造型进行有序排列，并将结果显示在文本框Text2 中。程序运行界面如图所示。举例说明如下：

Const n = 7

Dim h2(1 To n) As Integer

Dim height1(1 To n) As Integer, height 2 (1 To n) As Integer

Dim i As Integer, j As Integer, temp As Integer

Dim sex(1 To n) As Boolean ' 男生sex=true

Private Sub Form_Load()

'n名学生的身高和性别由数据库导出，分别存储在数组height1和sex中，代码略！

End Sub

Private Sub Command1_Click()

For i = 1 To n - 1

For j = n To i + 1 Step -1

IfThen

temp = height1(j): height1(j) = height1(j - 1): height1(j - 1) = temp

End If

Next j

Next i

For i = 1 To n

Text1.Text = Text1.Text + " " + Str(height1(i))

Next i

End Sub

Private Sub Command2_Click()

Dim left, right As Integer, i As Integer, mid As Integer

mid = Int((1 + n) / 2)

left = 0: right = 0

For i = 2 To n Step 2

right = right + 1

height2(mid + right) = height1(i)

left = left + 1

Next i

For i = 1 To n

Text2.Text = Text2.Text +“ “ + Str(height2(i))

Next i

End Sub

为实现以上功能，请在画线处填写正确代码。

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

i=1: j=6: n=0: f= False

key=Val(Text1. Text)

Do While i < = j And f = False

n=n+1

m=(i+j)\2

If key=d(m) Then f = True

If key < d(m) Then j = m-1 Else i=m+1

Loop

数组元素d(1)到d(6)的值依次为“13，18，25，30，35，59”。文本框Text1中输入33后运行该程序，运行结束后下列说法不正确的是（）

A . 变量f的值为False B . 变量i的值为5 C . 变量m的值为4 D . 变量n的值为2

跳蚤市场：为了筹集善款，学校组织了跳蚤市场活动。有n个学生打算卖出某种物品，其中第i个人希望以不低于a(i)的价格卖出：另有m个学生打算买入这种物品，其中第i个人希望以不高于b(i)的价格买入。如果物品的价格不低于卖方的最低价格且不高于买方的最高价格，则交易成功，否则交易失败。

另外为了公平，学校决定统一定价，使得最终价格能够让最多对学生成功进行交易。若有多个价格满足条件，则取满足条件的最高价。请你帮助校方完善VB程序，编程计算这批物品的最终定价。

例如，有6个学生打算卖出物品，他们的预期价格如图1所示。

卖方编号	1	2	3	4	5	6
预期价格	30	32	31	33	29	35

图1

另一有6个学生打算买入物品，他们的预期价格如图2所示。

买方编号	1	2	3	4	5	6
预期价格	34	31	29	32	33	31

图2

若分别以31元或32元的价格成交，都有3对学生交易成功，故最终定价为32元。

程序运行时，从外部数据库中输入买卖双方价格并显示到列表框List1和List2中，单击命令按钮Command1进行计算，并将最终的计算结果输出到标签Label3中，程序运行界面如图3所示。

（1）若图2中的买家1退出了交易，不再卖出物品，则最终定价为元。
（2） VB代码实现如下，请在划线处填入合适的代码。
Dim n As Integer， m As Integer

Dim a(1 To 20) As Integer， b(1 To 20) As Integer

Private Sub Form_ Load()

    '读取卖家人数n以及最低卖出价格，存入数组元素a(1)到a(n)中；

    '读取买家人数m以及最高买入价格，存入数组元素b(1)到b(m)中；

    '代码略

End Sub

Private Sub Command1_Click()

   Dim i As Integer， L As Integer， R As Integer

   Dim ml As Integer， m2 As Integer， sI As Integer， s2 As Integer

   Dim price1 As Integer， price2 As Integer

   Dim tot1 As Integer， tot2 As Integer

   Dim mini As Integer， maxi As Integer

    mini = a(1)： maxi =            ' mini 和maxi分别为可交易的最低价和最高价

    For i=2 To n

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

    Next i

    For i=2 To m

        If maxi < b(i) Then maxi = b(i)

    Next i

    L=mini：R=maxi

    Do While L<R

        s1 =0：s2= 0

       m1=(L+R+1)\2

        For i=1 To n

            If a(i)<=m1 Then s1=s1+1

       Next i

       For i=1 To m

            If b(i)>=m1 Then s2=s2+1

        Next i

        If s1>s2 Then Else L=m1

   Loop

    price1=L： tot1 = s1      'price1和tot1分别为价格和交易人数

   L=mini：R=maxi

    Do While L<R

        s1 =0：s2=0

        m2=(L+R)\2

        For i =1 To n

            If a(i) <= m2 Then s1=s1 + 1

        Next i

        For i=1 To m

            If b(i) >= m2 Then s2=s2+1

        Next i

       If s1<s2 Then L=m2+1 Else R=m2

    Loop

   price2 = L： tot2 = s2    ' price2和tot2分别为价格和交易人数

   If Then

        Label3.Caption ="最终定价为" + Str(price1) + "元"

    End If

End Sub

有下列 Python 程序段：

fruit=["pear","apple","orange"]

n=len(fruit)

ans=1

i=0

while i<=n-1:

if len(fruit[i])%2==0:

ans=ans*2

else:

ans=ans*2+1

i=i+1

print(ans)

执行该程序段后，输出的结果是（）

A . 10 B . 12 C . 15 D . 20

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

ElseIf Key Mod 2＝0 And a(m) Mod 2＝1 Then

Else

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

则方框处语句依次是(　　)

A . ①、②、③ B . ①、③、② C . ②、①、③ D . ③、②、①

采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”。

i = 1: j = 7: x = 55

Do While i <= j

m = (i + j) \ 2

If a(m) = x Then Exit Do

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

Loop

上述程序段运行后，下列表达式正确的是( )

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

有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 ⑴ Then

i= m

Else

⑵

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 . ②④⑥

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

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