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

【加试题】某企业举行销售业务竞赛，经过二轮预赛后进入决赛的有五位选手，他们的销售成绩分别是“11.7万元，20万元，16万元，29万元，10.7万元”，若采用冒泡排序法，则一共需要比较的次数是（   ）  

【加试题】小华在探究将两段已按从小到大排序的数据连接后用冒泡排序思想再进行从小到大排序的情况，编写VB程序功能如下：在列表框List1中显示排序前的数据(存储在数组c中)，单击“排序”按钮Command1后，在列表框List2中显示排序后的数据。程序运行界面如图所示。

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

Const n1=9       ‘第1段已排序数据长度为n1

Const n2=6       ‘第2段已排序数据长度为n2

 ‘数组c长度为n1+n2，依次存储第1，2段数据

Dim c(1 To n1+n2)As Integer

Private Sub Command1_Click()

    ‘数组c依次存储两段已按从小到大排序的数据

    ‘并在列表框List1中显示，代码略

     List2．Clear

           A位置 

     For i=n1+1 To n1+n2

         j=i

           B位置  

        Do While j>1 And Flag

              t=c(j)

             c(j)=c(j-1)

             c(j-1)=t

       C位置 

        Else

          Flag=False

        End If

        j=j-1

                ‘②

      Loop

    Next i

    For i=1 To n1+n2

    List2．Addltem c(i)

    Next i

End Sub

【加试题】以下程序段对数组a 中的8个数据a(1)到a(8)进行加工。

i = 1 : k = 0

Do While i<= 3

For j = 8 To i + 1 Step -1

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

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

k = k + 1 

End If

Next j

i = i + 1

Loop

若数组a中的数据依次为“24，29，31，24，12，10，12，25”，则加工结束后，变量k的值为（  ）

【加试题】小李基于冒泡排序算法编写了一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。

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

Const n = 10

Dim a(1 To n) As Integer

Private Sub Command1_Click()

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

  '获取排序前数据依次存储在数组a 中，并在文本框Text1 中显示。代码略

  bottom = n : i = 1

  Do While i <= bottom - 1

    For j = bottom To i + 1 Step -1

        If  Then     ‘⑴

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

        ElseIf a(j) = a(j - 1) Then ' 相邻两个数据相等，进行剔除处理

                 ‘⑵

            bottom = bottom - 1

        End If

    Next j

    i = i + 1

  Loop

Text2.Text = " "

For i = 1 To bottom

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

Next i

End Sub

⑴ ⑵ 

新华书店准备举行“买3送1”周年大酬宾活动，顾客只要每买三本书就可以免除其中一本最便宜的书的书款，上不封顶。其结算系统如图所示。图中左侧显示了顾客已挑选的书的款额，款额保存在数组s中，单击“结算”按钮后，系统会统计出所有书籍的金额数，并自动统计顾客最少所需的付款额。假设顾客买了7本书，价钱分别是10、3、2、4、4、6、9，总金额是38元，则顾客实付只需29元。

以下程序加框处有错，请改正。

Private Sub Command1_Click()

  Dim s(1 To 1000)As Single, n As Integer, x As Integer

  Dim payment As Single, cost As Single, tmp as Single

‘假设顾客共挑选了n本书，各本书金额数都已存放在数组s中

‘先对n本书按价格降序排序

For i=1 To n-1

  x=i

  For j=i+1 To n

    If  Then x=j ’

  Next j

  If x <> i Then

   tmp=s(x)

   s(x)=s(i)

   s(i)=tmp

  End If

 Next i

 ‘降序排序后，每隔两本就是一本可以减免的书

 cost=0 : payment=0

 For i=1 To n

  cost=cost+s(i)

 If  Then   ‘

   payment=payment+s(i)

  End If

 Next i

 Label1.Caption=“总金额:” & cost

 Label2.Caption=“实付:” & payment

End Sub

有一组正整数，要求仅对其中的素数进行升序排序。排序后素数在前，非素数在后排序示例如下。

排序前	86	71	5	41	81	79	37	89
排序后	5	37	41	71	79	89	86	81

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

Const n = 8

Dim a(1 To n) As Integer

Private Sub Command1_ click ( )

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

Dim flag As Boolean, sl As String, s2 As String

‘ 读取一组正整数,存储在数组a中

‘ 代码略

For i = 1 To n

  s1 = s1 + Str(a(i))

Next i

Text1. Text = s1

For i = 1 To n-1

        ‘①

    If IsPrime(a(k)) Then flag = True

    Else flag = False

    For j = i + 1 To n

      If IsPrime (a(j)) Then

        If       Then    ‘②

          k = j

          flag = True

        End If

      End If

    Next j

    If k <> i Then

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

    End If

  If Not flag Then Exit For ‘ Exit For表示退出循环

  Next i

  ‘依次输出排序后的数据

  ‘代码略

  For i=1 To n

    s2 = s2 + Str(a(i))

  Next i

  Text2. Text = s2

End Sub

Function IsPrime (m As Integer) As Boolean

‘ 本函数判断整数m是不是素数。是素数返回值为True，不是素数返回值为False

‘ 代码略

End Function

加框①处代码应改为。

加框②处代码应改为。

有如下 VB 程序段：

For i=1 To 3

  For j=1 To 5-i

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

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

   End If

  Next j

  Text1.Text = Text1.Text + Str(a(i))

Next i

数组元素a(1)到a(5)的值依次为“3,9,6,8,4”。该程序段执行后，文本框 Text1 显示的内容是（  ）

有一组正整数，要求仅对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。

排序前	86	71	5	41	81	79	37	89
排序后	5	37	41	71	79	89	86	81

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

Const n=8

Dim a（1 To n）As Integer

Private Sub Commandl_Click（）

Dim i As Integer，j As Integer，k As Integer，t As Integer

Dim flag As Boolean

'读取一组正整数，存储在数组a中，代码略

For i= 1 To n-1

        '（1）

    If IsPrime（a（k））Then flag = True Else flag = False

    For j = i + 1 To n

      If IsPrime（a（j）） Then

        If  Then    '（2）

          k=j

          flag = True

        End If

      End If

    Next j

    If k <> i Then

      t=a（k）：a（k）= a（i）：a（i）= t

    End If

    If Not flag Then Exit For     'Exit For表示退出循环

Next i

'依次输出排序后的数据。代码略

End Sub

Function IsPrime（m As Integer）As Boolean

'本函数判断m是不是素数：是素数返回值为True，不是素数返回值为False

'代码略

End Function

⑴ ⑵ 

食堂排队买菜问题。在食堂排队买菜时，每个同学都有一个窗口买菜时间，如果某同学的等待时间超过他在窗口买菜时间的3倍，他就会不愉快，并且不参与排队，反之是愉快的。等待时间是指排在该同学之前的所有人的买菜时间之和。已知每个同学在窗口的买菜时间，请确定如何排队才能使愉快的人数最多，并输出最多的人数。例如：10个同学的买菜时间如下表所示，则最多有8个人是愉快的。

学生编号	1	2	3	4	5	6	7	8	9	10
买菜时间	3	2	5	5	6	7	1	8	1	3
最终是否参与排队	是	是	是	是	否	是	是	否	是	是

Const n = 10

Dim a（1 To n）As Integer

Private Sub Command1_Click()

Dim i As Integer，s As Integer，ans As Integer，t As Integer

'读取每个学生的买菜时间，依次存储在数组a中，代码略

For i = 1 To n-1

  k = i

  For j = n To i + 1 Step - 1

    If    Then k = j

  Next j

  If a（i）<>a（k）Then t=a（i）：a（i）= a（k）：a（k）=t

Next i

s = 0：ans = 0

For i = 1 To n

  If  Then s=s + a（i）：ans = ans + 1

Next i

Label1.Caption ="共有"+ Str（ ans）+"个人是愉快的，且参与排队买菜。"

某医院接受捐赠物资，各项物资数据包含编号、品名和收支数量。编号构成规则是：急需等级(单个大写字母，由高到低划分为A、B、C三个等级)+物资种别(单个大写字母，至多有A～Z共26种)。为提高库存管理效率，现需要整理物资库存，要求：先对同种物资数量进行合并统计；然后按各种物资库存量，更新其急需等级，并依等级由高到低分类显示。等级划分规则为：当库存量低于3天所需，设置为A级；当库存量低于7天所需，设置为B级；否则设置为C级。

按上述要求，编写一个VB程序，功能如下：在列表框List1中显示整理前的所有物资相关数据，单击“库存合并统计”按钮Command1，在列表框List2中显示整理结果，程序运行界面如图所示。

有如下程序段：

For i = 1  To 2

  For j = i + 1  To 6

    If a(i) > a(j) Then

      t = a(j): a(j) = a(i): a(i) = t

    End If

  Next j

Next i

数组元素 a(1)到 a(6)的值依次为“3，4，2，1，5，0”，经过该程序段“加工”后，数组元素 a(1)到 a(6)的值依次为（   ）。

小李基于选择排序算法编写了一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。算法的思路：第i趟排序从a(i)….a(bottom)中查找最小值并记录其下标k，同时将后面的每个元素与a(i)比较是否重复，若发现重复数据，进行剔除处理；找到最小值与a(i)交换。

实现上述功能的VB程序如下，在橫线处填入合适的代码。

Const n = 10

Dim a(1 To n) As Integer

Private Sub Command1_Click()

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

Dim k As Integer, bottom As Integer

'获取排序前数据，依次存储在数组 a 中，并在文本框 Text1 中显示。代码略

bottom = n: i = 1

Do While i <= bottom - 1

k = i: j = bottom

Do While j > i

If a(j) < a(k) Then

k = j

ElseIf a(j) = a(i) Then         '若发现重复数据，进行剔除处理

a(j) = a(bottom)

IfThen k = j

bottom = bottom - 1

End If

j = j - 1

Loop

If k <> i Then

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

Else

EndIF

Loop

For i = 1 To

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

Next i

End Sub

有如下 VB 程序段：

n = 8

L = 1: R = n

For i = 1 To n - 1

  If i Mod 2 = 1 Then

    pos = L: L = L + 1

  Else

    pos = R: R = R - 1

  End If

  k = pos

  For j = L To R

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

  Next j

  If pos <> k Then

    t = a(pos): a(pos) = a(k): a(k) = t

  End If

Next i

已知a数组的各元素值分别为12,18,23,25,9,47,29,36，则运行程序段后，a数组各元素的值变为 (    )

某排序算法的VB程序段如下：

For i=1 To 2

  For j=2 To7-i

    If a（j-1）>a（j）Then

      t=a（j）：a（j）=a（j-1）：a（j-1）=t

    End If

  Next j

Next i

若数组元素a（1）到a（6）的值依次为“8，2，9，3，5，1”，则经过该程序段“加工”后，数组元素a（1）到a（6）的值依次为（  ）

（聪明的猪）某屠宰厂每天决定宰杀若干头猪（1<=n<=100），把每天待宰杀的猪按顺序编号后排成一排，每次将排在单号位置的猪杀掉；然后把剩下的猪按上一次相对的位置排好，重新编号，再次将排在单号位置的猪杀掉；以后每次重复前面的过程，直到仅剩下一头猪时停止宰杀，将这头幸运的猪放回；有一头猪聪明的猪，每天都能躲避被屠宰。利用VB编写一个程序，根据每天杀猪的数量，求出当天这头聪明的猪的原始编号。VB程序界面设计如下：

控件属性设置如下：

对象	属性	属性值	说明
Form1	Caption	幸运的猪	窗体的标题
Label1	Caption	当天要杀猪的数量	标签显示 文字
Label2	Caption	幸运猪的原始编号	标签显示的文字
Text1	Text	空白	文本框的文本
Text2	Text	空白	文本框的文本
Image1	Picture	Pig.gif	显示的图片
Command1	Caption	计算	按钮显示的文字

数组a中存储着某市2010年到 2019 年的GDP数值，编写VB程序，实现找出相邻两年GDP变化最大（即相邻两年GDP差值最大）的年份区间。若有多个符合要求的年份区间，只输出距今最近的年份区间。部分代码如下所示

Dim i As Integer,  imax As Integer

     ①       

For i = 3 To 10

    If Abs(a(i) - a(i - 1)) >=   ②     Then imax = i

Next i

Text1.Text = "GDP变化最大的年份区间是" + Str(imax + 2008) + "-" + Str(imax + 2009)

划线处①、②应填入的代码为（   ）

某教室在上午8点到12点的时间段可以安排活动。为了安排尽可能多场次的活动，按以下方法安排：先安排结束时间早的活动；若有多个活动的结束时间相同，则优先安排占用时间少的活动。要求编写一个VB程序，实现上述功能。在文本框Text1中输入一批数据（数据都用逗号分隔并以逗号结尾），奇数位置数据表示某活动的起始时间，偶数位置数据表示该活动的结束时间，单击“确定”按钮Command1后，在列表框List1中显示各活动的起始和结束时间，在列表框List2中显示选择安排的活动。运行界面如图所示。

 

某数据序列为“18,7,15,33,42,29,63,81”，采用选择排序算法将数据从小到大排序，那么排序过程中需要交换元素的次数是（   ）

实现某排序算法的部分VB程序如下：

For i=1 To 6

    k=i

    For j=i+1 To 7

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

    Next j

    If i<>k then

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

    End If

Next i

在排序过程中，经过某一遍排序“加工”后，数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”，则下一遍排序“加工”后数组元素a(1)到a(7)的数据依次是(    )

某省举办大型活动，面向省内城市招募有志愿服务工作经历的志愿者，每个志愿者的报名数据包含城市序号、姓名（字母缩写）和参加志愿服务的次数。现需整理报名数据，要求是：先按城市序号从小到大排列；然后，同一城市的志愿者按参加志愿服务的次数从多到少排列。

按上述要求，编写一个VB程序，功能如下：在列表框List 1中显示整理前的数据，单击“整理”按钮Command 1，整理结果显示在列表框List 2中，程序运行界面如图所示。