相关试卷

每个方块用一个代表其周围墙的数字之和（0≤p≤15）表示：1 表示西墙，2 表示北墙，4 表示东墙，8 表示南墙。城堡的内墙被计算两次，方块（1，1）的南墙同时也是方块（2，1）的北墙。城堡至少有两个房间。例如，图a的每个方块对应数字如图b所示。

图a

图b

程序运行界面如图c所示，现已知城堡地形对应的数字矩阵，要求出城堡一共有多少房间，最大 的房间有多大。小金利用深度优先搜索算法解决当 前问题，具体算法如下：

图c

在城堡中按行搜索，找到第一个未被搜索过方块， 以它为起点，分别按左、上、右、下的顺序向其四个方向试探，若发现一个方向上的方块是未被搜索过且可以通往的（无墙），则以这个方块为新起点，再重复上述试探。若当前方块四个方向上均无路可走，则返回上一个方块进行其他方向上的搜索，直至返回开始当前搜索的第一个方块且这个方块四个方向上也无路可走是，则本轮搜索结束。

例如，共有N=5个景点，每个景点连接的下一个景点分别是 2，4，2，3，1。

则他可以从2号景点出发，最多可以游玩2号、3号、4号三个景点。程序代码如下：

Private Sub Command1_Click()

    Dim a(1 To 100) As Integer, d(1 To 100) As Integer    '数组 a 存放下一景点号

    Dim jd As String, m As String, c As Integer, i As Integer

    Dim s As Integer, p As Integer, k As Integer, ans As Integer

    jd=Text1.Text+","

    s=0 : c=0

    For i=1 To Len(jd)

        m=Mid(jd,i,1)

        If m<>"," Then

                   ①       

        Else

            c=c+1 : a(c)=s: s=0

        End If

    Next i

    For k=1 To 100 d(k)=0

    Next k

    ans=0: k=0

    For i=1 To c    '枚举起点

        If d(i)=0 Then p=i

            Do While p<=c

                If d(p)=0 Then

                    k=k+1 :d(p)=k

                Else

                           ②       

                    If y>ans Then ans=y k=0

                    Exit Do

                End If

                     '改错

            Loop

        End If

    Next i

    Text2.Text=Str(ans)

End Sub

图 a

Key = Int(Rnd * 25) * 2

n = 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: n = n + 1

    Else

        i = m + 1: n = n - 1

    End If

Loop

Text2.Text = Str(n)

其中 a(1)到 a(10)数组的值分别“2，3，6，9，10，18，38，40，47，48”， 执行该程序段后，n 的值不可能的是（   ）

Dim a(1 To 6) As String i = 6

Text1.Text = ""

Do While i > 1

    k = i

    For j = 1 To i - 1

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

    Next j

    tmp = a(k): a(k) = a(i): a(i) = tmp

    Text1.Text = a(i)

    i = i - 1

Loop

其中数据元素 a(1)到a(6)的值依次为“12”、“34”、“8”、“9”、“77”、“23”，执行该程序段后，文本框Text1中显示的内容为（   ）

For i = 1 To 5

    a(i) = Int(Rnd * 90) + 10

Next i

For j = 5 To 2 Step -1

    If a(j) Mod 2 = 1 And a(j) < a(j - 1) Then

        t = a(j): a(j) = a(j - 1): a(j - 1) = t

    Else

        a(j) = a(j) / 2

    End If

Next j

执行该程序段后，a(1)到a(5)各元素不可能的是（   ）

s = Text1.Text

s1 = ""

For i = 1 To Len(s) \ 2

    m = Mid(s, i, 1)

    n = Mid(s, n - i + 1, 1)

    If m > n Then

        s1 = s1 + m + n

    Else

       s1 = s1 + n + m

Next i

Text2.Text = s1

在Text1中输入“8523691”，则执行该程序后，Text2中输出的是（   ）

但是，当数据范围很大时，需要的桶则非常多，会造成很大的资源浪费。为了解决该问题，小张对桶排序进行了优化，算法思想如下：

① 先依据数组中元素的个位进行桶排序；

② 再依据数组中元素的十位进行桶排序；

......

直到排序完成。

例如：有数组 a 中各元素分别为 53，3，542，748，17，214，154，63，616，第一趟按个位排序过程如下：

① 个位填入相应桶编号中，并统计每个桶中数据个数。

② 计算索引。计算方法是从前往后，依次计算当前桶中元素个数与前一项之和。

③按索引从桶中倒序取出数据，每取一个索引减 1。重新排列后为542，53，3，63，214，154，616，17，748。

接下来对重新排序后的数据以十位、百位依次进行桶排序即可完成排序(每一趟排序后数据重新排列)。

实现上述功能的VB代码如下。

Const n ＝ 100

Dim a(1 To n+1) As Integer   ‘产生n个随机数，存储在数组a中，并已按升序排序，代码略

Private Sub Command1_Click( )

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

    key ＝Val(Text1.Text)

    i=1: j=n

    Do While i <= j

        m=(i+j)\2

        If               Then    ‘改错

            j=m-1

        Else

            i=m+1

        End If

    Loop

    If a(i)=key Then        ‘找重复数的结束位置

        For k=i+1 To n

                If a(k) <> key Then

            Exit For   ‘退出For循环

            End If

        Next k

        List2.AddItem “a(” + Str(i) + “) -a(” +_______+ “)”    ‘填空

    Else

        List2.AddItem “未找到”

    End If

End Sub