0 返回首页
1. 小明探索用链表思想实现插入排序。链表由节点连接而成，每个节点包含一个数据域和一个指针域。为了模拟这个过程，小明用a数组保存链表数据域，b数组保存链表指针域，排序的过程就是将每个数据的指针域不断链接到已有的有序链表合适位置，形成更长 的链表，直到所有的数据均链接到链表中。

例如将某节点插入到已有链表中，根据大小比较有三种情况：插入到最前面、插入到 最后、插入到中间，如图a所示，在链表中的节点 x 和节点 y之间插入节点n的过程示意：过程一（初始状态）如图1所示，链表中节点 x 的指针域指向节点y数据域，即图示①指向；过程二如图2所示，将节点n的指针域指向节点 y 数据域，即图示②指向；过程三如图 3 所示，将①指向断开，同时将节点 x 的指针域指向节点n数据域，即图示③指向；至此完成节点n的插入操作。

图a

具体程序设计方法如下：

1）将待排序的n个数保存在a(1)~a(n)，b(1)~b(n)保存对应a数组各元素的位置，形成 n个没有链接的节点；

2）将a(1)结点看成只含有一个结点的链表head，且 head=1；

3）将a(2)节点插入到链表head的适当位置，使head仍有序，此时head成为含有两个结点的有序链表；以此方法依次将a数组中的其他节点插入到链表head中，最后链表 head上包含所有结点，且结点有序。依次输出head链表的数据域即完成排序。

程序运行界面如图b所示，采用此思想进行升序排序的 VB 代码如下，请回答下列问题。

图b

(1) 若用该算法对5 个数进行降序排序，a(1)~a(5)的值分别为“52,82,12,3,66”，排序完成后，head变量的值为。
(2) 为实现上述功能，请在划线处填入合适的代码。

Private Sub Command1_Click()

Dim a(1 To 100) As Integer  'a 数组存储待排序数据（数据域）

Dim b(1 To 100) As Integer  'b 数组存储待排序数的位置（指针域） Randomize

n = Val(Text1.Text)

‘随机产生 n 个待排序的数，并将 b 数组初始化（初始值全部指向自身）

For i = 1 To n

b(i) = i

a(i) = Int(Rnd * 100) + 1

List1.AddItem Str(b(i)) + "  " + Str(a(i))

Next i head = 1

For i = 2 To n k = head

‘插入到链表最前面

If a(i) <= a(head) Then

head = i

Else

‘寻找插入位置

Do While  k = b(k)

Loop

If b(k) <> k Then

b(i) = b(k): b(k) = i Else

b(k) = i End If

End If Next i

List2.AddItem Str(head) + "  " + Str(a(head))

Do While head <> b(head)

List2.AddItem Str(b(head)) + "  " + Str(a(b(head)))

Loop

End Sub
【考点】
排序算法及程序实现;
【答案】

您现在未登录，无法查看试题答案与解析。 登录
综合题 普通
能力提升
真题演练
换一批
1. 一名商人在A地采购了n吨大米（n<=150），需要船只运送到B地。现在码头上停靠着10艘船，载重量在15到30吨之间且均不相同，同时运费单价（单位：元/吨）也存在差异。为了找出运费总数最少的方案，该商人先将10艘船的运费单价从小到大排序，若船只运费单价相同，则按船只载重量大到小排序。上述步骤完成后，将n吨大米依次装入排好序的船只中，若最后一只船装不满，则按实际装运大米的重量付运费。程序运行界面如16题图所示：单击“排序”按钮后，船只信息按照要求排序并在列表框List1中输出；在文本框Text1中输入大米总数n吨，单击“计算”按钮，将在列表框List2中列出所选船只编号，并在文本框Text2中显示运费总数。

(1) 若图中7号船的载重量由“28”改为“22”，现有60吨大米需要运送，则该商人应选择的船只编号为 （若有多个编号，用“，”隔开）
(2) 实现上述功能的VB程序如下，请在划线处填入合适的代码。

Dim yf(1 To 10) As Integer, v(1 To 10) As Integer, b(1 To 10) As Integer

Private Sub Command1_Click()

    Dim n As Integer, i As Integer, j As Integer, t As Integer

    List1.AddItem "船只编号" + " " + "载重量" + " " + "运费单价" List2.AddItem "船只编号"

    For i = 1 To 10     '对船只进行编号

        b(i) = i

    Next i

    '随机生成10艘船的运费单价，数值在100到200之间，代码略

    For i = 1 To 10    '随机生成10艘船载重量，载重量均不相同

        v(i) = 15 + Int(Rnd() * 16)

        For j = 1 To i - 1

            If v(i) = v(j) Then : Exit For

        Next j

    Next i

    For i = 1 To 9

        For j = 10 To i + 1 Step -1

            If Then

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

            End If

        Next j

    Next i

    '在list1中输出10艘船的编号、载重量、运费单价，代码略

End Sub

Private Sub Command2_Click()

    Dim n As Integer, k As Integer

    Dim sum As Long

    n = Val(Text1.Text): sum = 0 k = 1

    Do While n > 0

        If n >= v(b(k)) Then

           

        Else

            sum = sum + n * yf(b(k))

        End If

        List2.AddItem Str(b(k)) n = n - v(b(k))

        k = k + 1

    Loop

    Text2.Text = Str(sum)

End Sub
综合题 困难
2. 编写“区间覆盖”程序，实现如下功能：输入数轴上的若干个封闭区间范围（均为正整数且左 坐标 < 右坐标），单击“统计”按钮，计算覆盖所有区间所需的数据点的个数。

例如：依次输入以下区间：[2 5]，[4 7]，[1 4]，[5 9]，[4 5]，[2 4]，数轴如下：

 坐标点“4”覆盖了[2 5]，[4 7]，[1 4]，[4 5]，[2 4]共5个区间，坐标点“9”覆盖了[5 9]区间，所以覆盖这6个区间所需的坐标点数为2个。

程序运行界面如图所示。实现上述功能的VB代码如下：

Dim n As Integer

Dim a(1 To 100) As Integer

Private Sub Input_Click()

'输入n个正整数区间，依次存放到数组

'a(1)到 a(2*n)中，并在List1中显示

'代码略

End Sub

Private Sub Count_Click()

  Dim right As Integer, t As Integer, k As Integer

  Dim tmp As Integer, i As Integer, ans As Integer

   

      tmp = a(k): a(k) = a(t): a(t) = tmp

      tmp = a(k + 1): a(k + 1) = a(t + 1): a(t + 1) = tmp

    End If

  Next i

   ‘改错

  ans = 1: t = 3

  Do While t < 2 * n

    If    ①    Then

      If a(t + 1) < right Then right = a(t + 1)

    Else

      ans = ans + 1

      right = a(t + 1)

    End If

          ②   

  Loop

  Text3.Text = Str(ans)

End Sub

请回答下列问题：

(1) 根据程序可知，“统计”按钮的对象名为 。
(2) 根据虚线框中算法可知，如示例所示输入的数据[4 7]和[4 5]，在排序后，这两组数据在数组 中的前后位置顺序是否发生改变？ 。（填：是/否）
(3) 程序中加框处代码有误，请改正。
(4) 请在划线①②处填入合适的代码。

① ②
综合题 普通
3. 小明基于冒泡排序算法编写了一个VB程序，功能如下：单击“生成”按钮command1，生成n个【10，99】的随机整数赋值给a数组，并在列表框list1中显示。单击“排序”按钮command2，对这组数据进行错位排序(即从前往后依次是最小的，最大的，第二小的，第二大的……依次类推)。在列表框list2中依次输出数据排序的结果，程序运行界面如图所示：

实现上述功能的VB程序如下：

Const n=10

Dim a(1 To 10)As Integer

Private Sub Command1  Click()

For i=1 To n

               ‘①

    List1．Addltem Str(a(i))

    Next i

End Sub

 Private Sub Command2  Click()

    tmp=1

    For i=1 To n-1

    For j=n To i+1 Step-1

    If  ＞0 Then    ①

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

    End If

    Next j

    ②

    Next i

    For i=1 To 10

    List2．Addltem Str(a(i))

    Next i

 End Sub

(1) 程序测试运行后生成如下文件：(A ．paixu．frmB .paixu．vbp C ．paixu·vbw D ．pai×u．exe)，其中属于windows系统可执行文件是：(单选，填字母：)
(2) 划线①处应填： 
(3) 加框①、②处代码有错，请改正。

① ② 
综合题 困难