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

在包含100个元素的数组a中，寻找最小值的Visual Basic程序段如下：

min = a(1)              '变量min用于存储最小值

For i = 2 To 100

Next i

则方框中最合适的语句是（   ）

有如下程序段：

    For i = 1 To 2

        For j = 2 To 7 - i

            If a(j) > a(j - 1) Then

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

            End If

        Next j

Next i

数组元素a(1)到a(6)的值依次为“71，54，58，29，31，78”，经过该程序段“加工”后，下列说法正确的是（   ）

下表记录了6个数据的排序过程。分析表中数据可知，该排序采用的算法与排序方式分别为

原始数据	65	57	59	44	45	69
第1遍	44	65	57	59	45	69
第2遍	44	45	55	57	59	69
第3遍	44	45	57	65	59	69
…	…	…	…	…	…	…

 

【加试题】有如下VB程序段：

  For i=1 To 3

    For j=5 To i Step-1

       If a(j)<a(j+1)Then

           k=a(j)：a(j)=a(j+1)：a(j+1)=k

       EndIf

    Next j

    Listl．AddItem Str(a(i))

  Next i

  数组元素a（1）到a（6）的数据依次为“1，5，7，6，9，3”，经过该程序段加工后，列表框List1中显示的内容是（  ）

有如下 VB 程序段： i = 1

Do While i <= 5

If i = 1 Or a(i - 1) <= a(i) Then i = i + 1

Else

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

End If Loop

数组元素a(0)到a(8)的初始值依次为“0,4,7,3,5,1,8,6,2”。执行该程序段后，数组元素a(1)到a(8)的值分别是

编写VB程序，实现如下功能:在文本框Text1和Text2中分别输入一个整数，单击命令按钮Command1，在列表框List1中显示结果，运行效果如图1所示。结果包含两列数据，第1列为两数之间的摄氏温度值(间隔1度、升序)，第2列为对应的华氏温度值。

有如下VB程序段：

i=1: j=8: n=1

k=Val(Text1. Text)

Do While i<=j

    m=(i+j)2

    IF k<d(m) Then j=m-1 Else i=m+1

    n=n+1

Loop

数组元素d(1)到d(8)依次为3，9，14，17，25，29，32，35，在文本框 Text1输人“14”。执行程序后，下列说法不正确的是（  ）

【排序算法的应用2】双关键字排序:在Excel中可采用双关键字排序，即先按主关键字排序，如主关键字相同再按次关键字排序。小王学习了冒泡排序后，编写了一个VB程序模拟该排序过程。功能如下：在列表框List1中显示排序前数据（存储在数组a、b中），单击“排序”按钮 Command1后，按主关键字数组a升序和次关键字数组b升序排序，排序后的数据在列表框Lis2中显示。程序运行界面如图所示。

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

Const n = 10

Dim a(l To n) As Integer, b(1 To n) As Integer

Private Sub Form_Load

‘ 各产生10个随机整数存入数组a、b,并在列表框List1中显示

‘ 代码略

End sub

Private Sub Command1_Click ( )

Dim i As Integer, j As Integer

i = 1

Do While i < = n-1

      ‘①

  Do While > = i+1

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

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

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

       ‘②

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

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

    End if

    j = j-1

  Loop

  i = i+1

Loop

For 1 =1 To n

  List2. AddItem Str(a(1)) + “” + str(b(i))

Next i

End sub

① ② 

对一个n×n的矩阵以“行”为单位进行升序排序，排序结果如下表所示。

小波编写了实现上述功能的程序，程序功能如下：程序运行时，在文本框Text中输入n(1≤n≤10)，单击“产生”按钮 Command1产生n×n个随机数，随机数的范围为[0, 9]，随机存储在数组a中，并以矩阵的形式在列表框List1上显示单击“排序”按钮Command2，对矩阵以“行”为单位进行升序排序，并在表框List2中输出排序后的矩阵。程序运行界面如图所示。

凯凯学习了桶排序和冒泡排序，他发现桶排序占空间比较多而冒泡排序的效率又较低，于是他想到综合两个算法来对数据进行排序。凯凯对n个由二位数组成的数据进行排序，排序步骤如下：

1）以每个数的十位数来区分，放置到各个桶里(如图①)；

2）分别对每个桶中的数据进行冒泡排序(如图②)；

3）最后依次输出各个桶中的数据即可(如图③)。

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

Dim c(0 To 10) As Integer Dim n As Integer

Private Sub Form_Load( )

'读取若干个二位数到a(i)中，并保存个数到n

End Sub

Private Sub Command1_Click()

    Dim i As Integer, t As Integer

    For i = 1 To n

        c(a(i) \ 10) = c(a(i) \ 10) + 1

    Next i

    c(0) = 1 : c(10) =        ①       

    For i = 1 To 9

        c(i) = c(i) + c(i - 1)

    Next i

    For i = 1 To n

        t = a(i) \ 10

        c(t) = c(t) - 1

               ②       

    Next i

    For i = 1 To 9

        Call px(c(i), c(i + 1) – 1)

    Next i

    For i = 1 To n

        List2.AddItem b(i)

    Next i

End Sub

Sub px(x As Integer, y As Integer)

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

    For i =

        For j = x To y - i

            If b(j) > b(j + 1) Then

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

            End If

        Next j

    Next i

End Sub

假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序的过程中，进行第一趟排序结束时，元素40不可能在哪个元素之后（    ）

某地学考等级划分规则如下：

将考生原始成绩从高到低划分为A、B+、B、C+、C、D+、D、E共8个等级，各等级人数所占比例分别为3%、7%、16%、24%、24%、16%、7%、3%，如下表所示。

等级	A	B+	B	C+	C	D+	D	E
比例	3%	7%	16%	24%	24%	16%	7%	3%

比如参加技术学考有20000人，小明卷面分90分，排名为1800名，则他在技术学科中的所处比例是9%。A占3%，B+占7%，因此B+所处的累积比例为4%-%10,可知他所处等级为B+。

编写一个VB程序计算学生某科目成绩的等级，功能如下：从数据库中读入学生学号、姓名、班级和原始成绩，并在列表框List1中显示，单击“等级划分”按钮Command1，在列表框List2中按原始成绩从高到低显示成绩与等级。等级划分时，先按原始成绩从高到低排序（如原始成绩相同，则按“班级”号从小到大排序），再根据人数比例计算切分位置确定等级。若切分位置有相同分数学生，则归为同一个等级。例如，某等级切分位置是第100位，但第101位学生的原始成绩和第100位相同，则这两名学生的赋分等级相同。程序运行界面如图a所示。

实现上述功能的VB程序如下，请回答下列问题：

有如下VB程序段：

n = 6

For i = 1 To n - 1

    For j = n - 1 To i Step -1

        If a(j) > a(j + 1) Or a(j) = a(j + 1) And b(j) < b(j + 1) Then

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

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

        End If

    Next j

Next i

数组元素a(1)到a(6)的值依次为3，6，7，1，8，1；b(1)到b(6)的值依次为5，3，7，7，7，4。执行上述程序段后，a(2)与b(2)的值分别是（    ）

采用冒泡排序算法对某数据序列进行排序，经过第一轮排序后的结果是“2,8,3,6,7,5,9”，那么原数据序列不可能的是（   ）

学校需要统计学生的作业完成数，需要将学生的完成数按从高到低显示，下列程序模拟该信息处理过程，程序在数据库stud中找到的学生信息（编号和完成次数），并将所有学生按照完成数从高到低显示。先将所有学生的编号和完成次数从数据库stud的info表中ID和finshed两字段中取出分别保存在数组a和数组b中，第i个学生的编号保存在a(i)中，对应的作业完成次数保存在b(i)中。

数据库文件“stud. accdb”信息如图所示。

程序界面如图所示，左边列表框List1中显示所有学生信息（包括编号和完成次数），单击“排序”按钮（Command），所有编号按照作业完成次数从高到低显示在列表框List2中。

代码如下：

Dim conn As New ADODB. Connection

Dim rs As New ADODB. Recordset

Dim n As Integer

Dim a(500)As String

Dim b(500)As Integer

Private Sub Fom Load()

    Dim i As Integer

    conn. Connection String="Provider=Mi-crosoft. AC

    A.OLEDB. 12.0；DATA Source="& App. Path &"\stud. accdb"

    conn Open

    Set rs. Active Connection=conn

    rs. Open "Select*From info"

    n=0

    Do While not rs.EOF            '到记录集最后一条记录后退出循环

        n=n+1

        a(n)=rs. fields("id")

        b(n)=rs. fields("finshed")

        rs. MoveNext                 '移动到下一条记录

    Loop

    For i=1 To n

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

    Next i

    rs. Close

    conn. Close

    Set rs= Nothing

    Set conn= Nothing

End sub

Private Sub Command1_Click()

    Dim i As Integer, j As Integer, t1 As Integer, t2 As String, k As Integer

    For i=1 To n-1             'n表示学生总数

        k=i           'k保存第i大的数，一开始假定是a(i)

        For j=i+1 To n

            If b(k)<b(j) Then k=j            '比较完成数

                ①      

            If    ②      Then

                t1=b(i): b(i)=b(k): b(k)=t1           '交换完成次数

                t2=a(i): a(i)=a(k): a(k)=t2           '交换编号

            End If

        Next j

    Next i

    For i=1 To n          '在列表框List2中输出排序结果

        Listt2. Addltem a(i)+" "+Str(b(i))

    Next i

End sub

编写一个VB程序，功能如下：随机产生100个0到99之间的整数，在列表框list1中显示，单击“统计”按钮Command1，统计落入各范围的整数个数，在列表框List2中按从高到低的顺序显示各范围的整数个数。程序运行界面如图所示。

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

Const n = 100

Dim a(1 To n)As Integer

Private Sub Form_Load( )

    ‘随机产生100个0到99之间的整数存数组a中，并在列表框list1中显示。

End Sub

Private Sub Command1_Click( )

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

    Dim b(0 To 9)As Integer, c(0 To 9)As Integer

    For i = 1 To n

           ①

    Next i

    For i = 0 To 9

        b(i) = i

    Next i

    i = 0

    Do While i <= 8

        For j = i + 1 To 9

            If  Then   ②

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

                t = c(i): c(i) = c(j): c(j) = t

            End If

        Next j

        i = i + 1

    Loop

    List2.AddItem “范围元素个数”

    For i = 0 To 9

        List2.AddItem Str(b(i) * 10) + "~" + Str(b(i) * 10 + 9) + ": " + Str(c(i)) + "个"

    Next i

End Sub

有如下 VB 程序段:

i = 6: flag = True

Do While i >= 4 And flag = True

    flag = False

    k = i

    For j = 1 To i - 1

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

    Next j

    If k <> i Then

        t = a(i): a(i) = a(k): a(k) = t

        flag = True

    End If

    i = i - 1

Loop

数组元素a(1)到a(6)的值依次为：“19,6,34,40,13,53”，执行该程序段后，数组元素a(1)到a(6)的值依次为(    )

小杜对某班技术成绩情况进行分析，先排序再分析，排序后女生在前，男生在后(该班级男女生都有，其中0表示女，1表示男) ，且男女生均按成绩降序排序，最后比对男生女生平均分情况。数组a中存储了n位学生的性别和成绩数据，其中奇数位置存储性别信息，偶数位置存储成绩信息。

编写VB程序实现上述功能，运行程序在列表框List1中显示排序前学生数据。单击“统计”按钮，在列表框List2中显示排序后的结果，并且在Label1中显示男生女生平均分比对结果。程序运行界面如15题图所示。

对n个互不相同的整数(整数的最大值不超过m)进行排序，排序要求如下：①奇数在前，偶数在后；②奇数升序排序；③偶数降序排序。小刘用VB编写了实现上述功能的程序。程序运行时，自动产生n个不同的随机数存储在数组a中，并在列表框List1中显示。单击按钮Command1后，按要求在列表框List2中输出排序后的结果。

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

Const n=15

Const m=100      '整数的最大值

Dim a(1 To n) As Integer

Private Sub Form_ Load()

    '本过程产生n个不重复的随机数存储在数组a中，并在列表框List1中显示

End Sub

Private Sub Command1_Click()

    Dim i As Integer

    Dim flag(1 To m) As Boolean      'flag(i)= True代表数组a中存在值为i的元素

    For i=1 To m

        flag(i)= False

    Next i

    For i=1 To n

             '

    Next i

    For i=1 To m-1 Step 2

        If flag(i) Then List2. AddItem Str(i)

    Next i

    For     '

        If flag(i) Then List2. AddItem Str(i)

    Next i

End Sub

如下VB程序段：

st = “ ”

For i = 1 To 4

    For j = 1 To 10 - i

        If d(j) < d(j + 1) Then

            temp = d(j): d(j) = d(j + 1): d(j + 1) = temp

        End If

    Next j

    st = Str(d(j)) + st

Next i

Text1.Text = st

数组元素d(1)～d(10)中的数据依次为“21，8，12，16，26，71，65，89，42，36”，程序执行后，在文本框Text1中显示的内容是(  )