高中信息技术算法与程序设计 查找算法

1. 已知数列“15，19，21，20，84，77，36，55”，若要在数列中查找数据100，共需查找的次数是(  )

2. 已知数列“32，19，6，57，41，67，28”，若要在数列中查找数据19，共需查找的次数是(  )

3. 某查找算法的部分VB代码如下：

flag=True

Key=Val(Text1.Text)

i=1

Do While i<=8 And flag

    If a(i)=Key Then

        flag=False

    Else

        i=i+1

    End If

Loop

If Not flag Then

    Label1.Caption=“Find！”

Else

    Label1.Caption=“Fail！”

End If

数组元素a(1)到a(8)的数据依次为“11，2，0，6，8，3，5，8”，程序运行时，在文本框Text1中输入8，则在标签Label1中显示的内容是(  )

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

key = Val(Text1.Text)

i = 1: j = 10

Text2.Text = “ ”

Do While i <= j

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

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

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

    Text2.Text = Text2.Text + Str(a(m))

Loop

数组元素a(1)到a(10)的值依次为“8，17，24，30，36，40，55，58，61，66”，文本框Text1中输入的值是30，执行该程序段，文本框Text2中显示的是(  )

5. 某对分査找算法的VB程序段如下：

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

key = Int(Rnd * 100)

Do While i <= j

    m = (i + j) \ 2

    If key = a(m) Then

        s = s + “M”： Exit Do  '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(7)的值依次为“24，35，38，41，45，69，78”。若该程序段执行后，文本框Text1中显示的内容可能是(  )

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

则(1)、(2)、(3)处语句依次是(  )

7. 有以下VB程序段：

Dim a As String, b As String, p As String, s As String

a = Text1.Text

b = Text2.Text

c = Text3.Text

p = “ ”

For i = 1 To Len(a)

    If b = Mid(a, i, Len(b)) Then

        s = s + c

        p = p + Str(i)

    Else

        s = s + Mid(a, i, 1)

    End If

Next i

Label1.Caption = p

若文本框Text1中输入“Hello，Python！I use Python！”，文本框Text2中输入“Python”， 文本框Text3中输入“VB”运行该段程序后，标签Label1中显示的是(  )

8. 某对分査找算法的VB程序段如下：

i = 1: j = 9: n = 0

key = Val(Text1.Text)

Do While i<= j

    n = n + 1

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

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

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

Loop

数组元素d(1)到d(9)的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是(  )

9. 用对分查找法和顺序查找法在数字序列“1，2，3，5，8，13，21，34，55”中查找数字13，两种方法都能访问到的数字是（  ）

10. 采用如下对分查找算法对数组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

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

11. 下列程序段用于在前面部分为升序后面部分为降序的数组 a 中查找最大值，返回该数值及其位置(下标)。

i = 1: j = 10

flag = False

Do While i <= j And Not flag

    m = (i + j + 1) \ 2

    If a(m) < a(m - 1) And a(m) > a(m + 1) Then

        

    ElseIf a(m) > a(m - 1) And a(m) > a(m + 1) Then

        

    ElseIf a(m) > a(m - 1) And a(m) < a(m + 1) Then

        

    End If

Loop

List1.AddItem Str(a(m)) +Str(m)

上述程序方框处可选句为：

①i=m+1  

②j=m-1

③flag = True  

则①②③处语句依次是(  )

12. 编写一个单词查找程序，其功能是：在文本框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

13. 小明编写了一个查找替换的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

14. 小华写了一个模糊查询的VB程序，具体功能如下：程序运行时，在列表框List1中显示热门书籍名称，在文本框Text1中输入查询关键词后，单击“开始查询”按钮Command1，则在列表框List2中显示包含此关键词的书籍名称，并统计找到的书籍数；若找不到，则在列表框List2中输出“查无此书”。程序运行界面如下图所示：

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

Dim book(1 To 20) As String, st As String

Const n = 20

Private Sub Form_Load()

    '读入n个数据，存储在数组book中，并显示在列表框List1中

End Sub

Private Sub Command1_Click()

    Dim i As Integer, j As Integer, len1 As Integer, len2 As Integer，k As Integer

    st = Text1.Text

    List2.Clear

    len1 = Len(st)

    k = 0

    For i = 1 To n

        len2 = Len(book(i))

              '①

        Do While j <= len2 - len1 + 1

            If  Then    '②

                List2.AddItem book(i)

                k = k + 1

            End If

            j = j + 1

        Loop

    Next i

    If k> 0 Then

        List2.AddItem “共找到”+Str(k) + “条信息”

    Else

        List2.AddItem “查无此书”

    End If

End Sub

程序中加框①处应改正为；

加框②处应改正为。

15. 大家期盼的校运会要来了，同学们踊跃报名，共有20人报了100米，30人报了200米。小明编写了一个VB程序，用于查询同时报名参加100米和200米比赛的学生，并统计学生数。具体功能如下：程序运行时，在列表框List1中显示报100米的学生学号和姓名，在列表框List2中显示报200米的学生学号和姓名，单击“排序”按钮Command1后，将List2中数据按“姓名”升序排序，并将排序后的数据重新显示在列表框List2中；单击“查询并统计”按钮Command2后，在列表框List3中显示同时报名参加100米和200米比赛的学生信息，并在该列表框的最后显示同时报名这两项比赛的学生数。程序运行界面如下图所示：

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

Dim xm1(1 To 20) As String, xh1(1 To 20) As String′数组xm1、xh1分别存储选报课程1的学生的姓名和学号

Dim xm2(1 To 30) As String, xh2(1 To 30) As String′数组xm2、xh2分别存储选报课程2的学生的姓名和学号

Const n = 20, m = 30

Private Sub Form_Load()

    '获取选报数据，并显示在列表框List1和List2中

    '代码略

End Sub

Private Sub Command1_Click()

    Dim i As Integer, j As Integer, tt As String

    List2.Clear

    For i = 1 To m - 1

        For j =Step -1

            If xm2(j) < xm2(j - 1) Then

                tt = xm2(j): xm2(j) = xm2(j - 1): xm2(j - 1) = tt

                tt = xh2(j): xh2(j) = xh2(j - 1): xh2(j - 1) = tt

            End If

        Next j

    Next i

    For i = 1 To m

        List2.AddItem xh2(i) + “  ” + xm2(i)

    Next i

End Sub

Private Sub Command2_Click()

    Dim i As Integer, j As Integer, w As Integer, tt As String, k As Integer

    For i = 1 To n

        p = 1

        

        Do While p <= q

            w = (p + q) \ 2

            If xm1(i) = xm2(w) Then

                List3.AddItem xh1(i) + “ ” + xm1(i)

                k = k + 1

            End If

            If Then

                q = w - 1

            Else

                p = w + 1

            End If

        Loop

    Next i

    List3.AddItem “共有” + Str(k) + “ 位同学”

End Sub

16. 对分查找算法可用于求解方程的近似值。现要求方程x³-4x²+x+5=0的一个近似值，可设f(x)= x³-4x²+x+5，若有区间[a，b]，使f(a)与f(b)异号，则该区间内必存在该方程的一个解。小明为此编写了VB程序，功能如下：程序运行时，在文本框Text1、Text2中输入区间值a、b，要求a<b，单击“计算”按钮Command1，若该区间有解，则计算出该区间内的一个近似值(精确到0.00001)，否则提示“请重新输入区间”，计算后的相关结果显示在列表框List1中。程序运行效果如下图所示。

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

Function f(x As Double) As Double

    Dim y As Double

    

    f = y

End Function

Private Sub Command1_Click()

    Dim a As Double, b As Double, m As Double, x As Double

    a = Val(Text1.Text)

    b = Val(Text2.Text)

    If f(a) * f(b) < 0 And a < b Then

        Do While a <= b

            

            If Abs(f(m)) < 0.00001 Then Exit Do

            If  Then

                b = m

            Else

                a = m

            End If

        Loop

        x = Format(m, “0.00000”) ′Format函数用于定义输出的小数位数

        List1.AddItem “[” & Text1.Text & “，” & Text2.Text & “]” & “解为：” & x

    Else

        List1.AddItem “[“ & a & ”，“ & b & ”]” & “请重新输入区间”

    End If

End Sub