专项测试五 排序算法
一、选择题
1.采用冒泡排序算法对数组a中的6个数据“8，20，5，17，30，9”进行排序，部分程序代码如下：
For i＝1 To 2
For j＝6 To i＋1 Step －1
If a(j)>a(j－1) Then
t＝a(j): a(j)＝a(j－1): a(j－1)＝t
End If
Next j
Next i
运行该程序，数据交换的次数为( )
A.1 B.2
C.3 D.4
解析 本题主要考查的是冒泡排序的数据交换次数。根据语句“If a(j)>a(j－1)Then”可知，排序方式为从大到小排序(降序)，排序是通过从后往前相邻数据比较和交换进行，排序过程如下：
原始数据
8
20
5
17
30
9
说明
第1趟
30
8
20
5
17
9
30分别与17、5、20、8交换位置，因此，共交换4次
第2趟
30
20
8
17
5
9
17与5交换位置，20与8交换位置，因此，共交换2次
因此，答案为B。
答案 B
2.采用冒泡排序对数组d中元素进行排序，第一趟排序后的结果为“10，25，15，30，50，38，60，55”，则d数组中元素的初始顺序不可能是( )
A.25，15，30，50，38，60，55，10
B.25，15，30，50，38，60，10，55
C.25，15，10，50，38，60，30，55
D.25，15，30，50，10，38，60，55
解析 观察第一趟的排序可知，数据是按升序排序的，数据比较和交换是从后往前进行的，本题可从选项模拟排序，D选项进行第一趟排序后的数据顺序为“10，25，15，30，50，38，55，60”，因此，答案为D。
答案 D
3.对数组元素b(1)～b(8)进行降序排序，其排序算法的VB部分程序如下：
For x ＝ 1 To 7
w ＝ x
For y ＝ x ＋ 1 To 8
Next y
If w < > x Then
Temp ＝ b(x): b(i) ＝ b(w): b(w) ＝ temp
End If
Next x
方框中应填入的语句为( )
A.If b(w) > b(y) Then w ＝ y
B.If b(w) < b(y) Then w ＝ y
C.If b(w) > b(y) Then w ＝ x
D.If b(w) < b(y) Then w ＝ x
解析 本题主要考查的是选择排序算法的程序实现。排序方式为降序，用变量w记录当前最大的元素所在的位置，当在后面找到更多的数时，则更新w的值，因此加框处的代码为If b(w) < b(y) Then w ＝ y，答案为B。
答案 B
4.有如下程序段：
For i ＝ 1 To 4
For j ＝ i ＋ 1 To 5
If a(j) > a(i) Then t ＝ a(j): a(j) ＝ a(i): a(i) ＝ t
Next j
Next i
数组元素a(1)～a(5)的值依次为“15，4，12，7，9”，整个排序过程中，数组中数据比较次数和交换次数分别是( )
A.比较11次，交换3次
B.比较11次，交换4次
C.比较10次，交换3次
D.比较10次，交换4次
解析 本题主要考查的是选择排序算法。这是非优化的选择排序，每遍排序时将i位置的元素顺序与它后面的元素比较，若比它大，则交换它们的位置。排序过程如下表所示：
原始数据
15
4
12
7
9
比较次数和交换次数
第一趟结束时
15
4
12
7
9
比较4次，无交换
第二趟
15
12
4
7
9
比较3次，交换1次
第三趟
15
12
9
4
7
比较2次，交换2次
第四趟
15
12
9
7
4
比较1次，交换1次
因此，共比较次数为4＋3＋2＋1＝10次，共交换次数为1＋2＋1＝4次，答案为D。
答案 D
5.如下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中显示的内容是( )
A.8，12，16，21 B. 42，65，71，89
C.21，16，12，8 D.89，71，65，42
解析 本题考查的是冒泡排序算法的程序实现。该程序的功能是对数据使用冒泡排序降序排序4趟，并将每趟得到的最小值存放在字符串st中，需注意的是语句st ＝ Str(d(j)) ＋ st，即将当前得到的最小数拼接在字符串st的前面。因此，四趟排序结束后，变量st的值为“21，16，12，8”，答案为C。
答案 C
6.有如下VB程序段：
Private Sub Command1_Click()
Dim a(1 To 100) As String, x As String, st As String
Dim i As Integer, j As Integer, n As Integer
x ＝ Text1.Text
n ＝ Len(Text1.Text)
For i ＝ 1 To n
a(i) ＝ Mid(x, i, 1)
Next i
For i ＝ 1 To n － 1
For j ＝ n To i ＋ 1 Step －1
If a(j) > a(j － 1) Then
st ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ st
End If
Next j
Next i
st ＝ “ ”
For i ＝ 1 To n
st ＝ st ＋ a(i)
Next i
Label1.Caption ＝ st
End Sub
程序运行时，在文本框Text1中输入“Text”(不包含双引号)，单击按钮Command1，则在标签Label1上显示的内容为( )
A.Tetx B.Txte
C.xtTe D.xteT
解析 本题主要考查的是冒泡排序算法。本题的功能是将文本框中输入的字符串进行降序排序，字符比较大小实质是比较字符的ASCII码，小写字母的ASCII值大于大写字母，因此排序结果为xteT，答案为D。
答案 D
二、非选择题
7.下面是一个采用拉锯式排序法对数组元素按升序进行排序的程序，所谓“拉锯式排序法”是这一遍把最小的元素从下往上移动到最上面的位置，下一遍则是从上往下把最大的元素移动到最下面的位置。 程序运行效果如下图所示。
Private Sub Command1_Click()
Dim a(10) As Integer, i As Integer
Randomize ′产生不同的随机数
For i ＝ 1 To 10
a(i) ＝ Int(Rnd * 100) ＋ 1
Text1.Text ＝ Text1.Text & Str(a(i))
Next i
Call Shaker_sort(a()) ′调用Shaker_sort
For i ＝ 1 To 10
Text2.Text ＝ Text2.Text & Str(a(i))
Next i
End Sub
Private Sub Shaker_sort(k() As Integer)
Dim i As Integer，c As Integer，d As Integer
Dim t As Integer
c ＝ 1
d ＝ 10
Do While c<＝d
For i＝______①______ ′从下往上把最小的元素移到最上面的位置
If k(i－1)>k(i) Then
t ＝ k(i － 1)：k(i－ 1) ＝ k(i)：k(i) ＝ t
End If
Next i
For i ＝ c＋1 To d－c ′从上到下把最大的元素移到最下面的位置
If ______②______ Then
t ＝ k(i＋1)：k(i＋1) ＝ k(i)：k(i) ＝ t
End If
Next i
c ＝ c ＋ 1
______③______
Loop
End Sub
解析 此题考查排序算法的分析和拓展。①代码表示把当前最小的元素从下往上移到最上面的位置，因此代码为d to c＋1 Step －1；②处所在循环的功能是从上到下把最大的元素移到最下面的位置，即当前位置的元素比后面元素大时，交换他们的位置，因此②处代码为k(i)>k(i＋1)；每一趟排序将排定头尾两个数的位置，因此，③处代码为 d＝d－1。
答案 ①d to c＋1 Step －1 ②k(i)>k(i＋1)
③d＝d－1
8.小李基于冒泡排序算法编写了一个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
程序中加框①处应改正为_________________________________________；
加框②处应改正为_______________________________________________。
解析 本题考查的是冒泡排序算法的变式。从数据交换的语句可知，加框①处的表达式为a(j)与a(j－1)的比较，因为排序方式为升序，因此加框①处的代码修改为a(j)
答案 ①a(j) a(j)
②a(j)＝a(bottom)或t＝a(j)：a(j)＝a(bottom)：
a(bottom)＝t
9.编写一个VB程序，实现功能为在n个数中寻找第m大的数。程序运行时，自动生成n个三位数随机整数，并显示在列表框List1中，单击“排序”按钮Command1，将数据进行排序，并将排好序的数据显示在列表框List2中，在文本框Text1中输入m，单击“计算”按钮Command2，在文本框Text2中显示第m大的数。程序运行效果如下图所示：
为实现上述功能的VB程序如下，在程序划线处填入合适的代码。
Dim d(1 To 20) As Integer
Const n ＝ 20
Private Sub Form_Load()
Dim i As Integer, j As Integer, t As Single
List1.Clear
Randomize
For i ＝ 1 To n
________①________
List1.AddItem Str(d(i))
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t1 As Integer
For i ＝ 1 To n － 1
For j ＝________②________
If d(j) < d(j － 1) Then
t1 ＝ d(j): d(j) ＝ d(j － 1): d(j － 1) ＝ t1
End If
Next j
Next i
For i ＝ 1 To n
List2.AddItem Str(d(i))
Next i
End Sub
Private Sub Command2_Click()
Dim m As Integer
m ＝ Val(Text1.Text)
Text2.Text ＝ “第” ＋ Str(m) ＋ “ 大的数为：”
＋ ________③________
End Sub
解析 本题采用冒泡排序算法。①处主要考查的是随机函数，要求生成三位数整数(即[100，999]范围内的整数)，根据代码“List1.AddItem Str(d(i))”可知，随机数存储在数组d中，第i个随机数存储在数组元素d(i)中，因此，①处代码为d(i)＝Int((Rnd * 900＋100))；②处所在的事件处理过程是冒泡排序，从交换语句可知，相邻数据的比较是从后往前进行的，因此②处代码为n To i ＋ 1 Step －1；③处代码考查的是学生的思维能力，由于排序后的数据是升序，因此第m大的数为d(n－m＋1)，而不是d(n－m)，因此③处代码为Str(d(n － m ＋ 1))。
答案 ①d(i) ＝ Int((Rnd * 900 ＋ 100))
②n To i ＋ 1 Step －1 ③Str(d(n － m ＋ 1))
10.小王编写了一个数据排序且将重复数删除的VB程序。算法的基本思想：先随机生成20个[1，50]区间内的整数，然后按照数据从低到高进行排序，最后删除重复数(相同的数据只保留一个)。
程序运行时，单击“生成随机数”按钮Command1，则生成20个[1，50]区间内的整数，存储在数组a中，并显示在文本框Text1中；单击“排序并去重”按钮Command2，则将数组a中数据进行从低到高排序，并将排序结果显示在文本框Text2中，将去重后结果显示在文本框Text3中，在标签Label4中显示共删除的重复数个数，程序运行界面如下图所示。
实现上述功能的VB程序如下，请回答下列问题：
(1)若20个随机数分别为：7，18，5，7，7，12，7，1，10，14，17，7，9，7，10，16，5，18，8，18，则去掉的重复数共________个。
(2)请在划线处填入合适的代码。
Dim a(1 To 20) As Integer
Const n ＝ 20
Private Sub Command1_Click()
Dim i As Integer, s1 As String
Randomize
s1 ＝ “ ”
For i ＝ 1 To n
a(i) ＝ Int(Rnd * 50 ＋ 1)
s1 ＝ s1 ＋ Str(a(i))
Next i
Text1.Text ＝ s1
End Sub
Private Sub Command2_Click()
Dim i As Integer, j As Integer, p As Integer, tt As Integer
Dim ans As Integer, s2 As String, s3 As String
For i ＝ 1 To n － 1
p ＝ i
For j ＝ n To i ＋ 1 Step －1
If a(j) < a(p) Then p ＝ j
Next j
If a(i) < > a(p) Then
tt ＝ a(i)
a(i) ＝ a(p)
a(p) ＝ tt
End If
Next i
s2 ＝ “ ”：s3 ＝ “ ”
ans ＝ 0
For i ＝ 1 To n
s2 ＝ s2 ＋ Str(a(i))
Next i
Text2.Text ＝ s2
__________①__________
s3 ＝ Str(a(1))
For i ＝ 2 To n
If a(i) < > q Then
__________②__________
q ＝ a(i)
Else
__________③__________
End If
Next i
Text3.Text ＝ s3
Label4.Caption ＝ Str(ans)
End Sub
解析 (1)重复的数有5、7、10、18，去掉1个5，5个7，1个10，2个18，因此共删除的重复数有9个。(2)本题的算法思想是：首先将数据进行升序排序，然后将相邻的重复数删除。因此，先将第一个数赋给变量q，然后从2个数开始与q进行比较，如果不相等，说明当前的数与它前面的数不重复，则将它存放在字符串s3中，并把当前数赋给q，继续往下比较；如果相等，说明当前的数与它前面的数重复，则不放入字符串s3，进行重复数的计数，根据语句“Label4.Caption ＝ Str(ans)”可知，重复数的个数记录在变量ans中，然后继续往下比较。因此①处应填入的语句为q＝a(1)，②处应填入的语句为s3＝s3＋Str(a(i))，③处应填入的语句为ans＝ans＋1。
答案 (1)9 (2)①q ＝ a(1)
②s3 ＝ s3 ＋ Str(a(i)) ③ans ＝ ans ＋ 1
专项测试五 排序算法
一、选择题
1.采用冒泡排序算法对数组a中的6个数据“8，20，5，17，30，9”进行排序，部分程序代码如下：
For i＝1 To 2
For j＝6 To i＋1 Step －1
If a(j)>a(j－1) Then
t＝a(j): a(j)＝a(j－1): a(j－1)＝t
End If
Next j
Next i
运行该程序，数据交换的次数为( )
A.1 B.2
C.3 D.4
2.采用冒泡排序对数组d中元素进行排序，第一趟排序后的结果为“10，25，15，30，50，38，60，55”，则d数组中元素的初始顺序不可能是( )
A.25，15，30，50，38，60，55，10
B.25，15，30，50，38，60，10，55
C.25，15，10，50，38，60，30，55
D.25，15，30，50，10，38，60，55
3.对数组元素b(1)～b(8)进行降序排序，其排序算法的VB部分程序如下：
For x ＝ 1 To 7
w ＝ x
For y ＝ x ＋ 1 To 8
Next y
If w < > x Then
Temp ＝ b(x): b(i) ＝ b(w): b(w) ＝ temp
End If
Next x
方框中应填入的语句为( )
A.If b(w) > b(y) Then w ＝ y
B.If b(w) < b(y) Then w ＝ y
C.If b(w) > b(y) Then w ＝ x
D.If b(w) < b(y) Then w ＝ x
4.有如下程序段：
For i ＝ 1 To 4
For j ＝ i ＋ 1 To 5
If a(j) > a(i) Then t ＝ a(j): a(j) ＝ a(i): a(i) ＝ t
Next j
Next i
数组元素a(1)～a(5)的值依次为“15，4，12，7，9”，整个排序过程中，数组中数据比较次数和交换次数分别是( )
A.比较11次，交换3次
B.比较11次，交换4次
C.比较10次，交换3次
D.比较10次，交换4次
5.如下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中显示的内容是( )
A.8，12，16，21 B. 42，65，71，89
C.21，16，12，8 D.89，71，65，42
6.有如下VB程序段：
Private Sub Command1_Click()
Dim a(1 To 100) As String, x As String, st As String
Dim i As Integer, j As Integer, n As Integer
x ＝ Text1.Text
n ＝ Len(Text1.Text)
For i ＝ 1 To n
a(i) ＝ Mid(x, i, 1)
Next i
For i ＝ 1 To n － 1
For j ＝ n To i ＋ 1 Step －1
If a(j) > a(j － 1) Then
st ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ st
End If
Next j
Next i
st ＝ “ ”
For i ＝ 1 To n
st ＝ st ＋ a(i)
Next i
Label1.Caption ＝ st
End Sub
程序运行时，在文本框Text1中输入“Text”(不包含双引号)，单击按钮Command1，则在标签Label1上显示的内容为( )
A.Tetx B.Txte
C.xtTe D.xteT
二、非选择题
7.下面是一个采用拉锯式排序法对数组元素按升序进行排序的程序，所谓“拉锯式排序法”是这一遍把最小的元素从下往上移动到最上面的位置，下一遍则是从上往下把最大的元素移动到最下面的位置。 程序运行效果如下图所示。
Private Sub Command1_Click()
Dim a(10) As Integer, i As Integer
Randomize ′产生不同的随机数
For i ＝ 1 To 10
a(i) ＝ Int(Rnd * 100) ＋ 1
Text1.Text ＝ Text1.Text & Str(a(i))
Next i
Call Shaker_sort(a()) ′调用Shaker_sort
For i ＝ 1 To 10
Text2.Text ＝ Text2.Text & Str(a(i))
Next i
End Sub
Private Sub Shaker_sort(k() As Integer)
Dim i As Integer，c As Integer，d As Integer
Dim t As Integer
c ＝ 1
d ＝ 10
Do While c<＝d
For i＝______①______ ′从下往上把最小的元素移到最上面的位置
If k(i－1)>k(i) Then
t ＝ k(i － 1)：k(i－ 1) ＝ k(i)：k(i) ＝ t
End If
Next i
For i ＝ c＋1 To d－c ′从上到下把最大的元素移到最下面的位置
If ______②______ Then
t ＝ k(i＋1)：k(i＋1) ＝ k(i)：k(i) ＝ t
End If
Next i
c ＝ c ＋ 1
______③______
Loop
End Sub
8.小李基于冒泡排序算法编写了一个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
程序中加框①处应改正为_________________________________________；
加框②处应改正为_______________________________________________。
9.编写一个VB程序，实现功能为在n个数中寻找第m大的数。程序运行时，自动生成n个三位数随机整数，并显示在列表框List1中，单击“排序”按钮Command1，将数据进行排序，并将排好序的数据显示在列表框List2中，在文本框Text1中输入m，单击“计算”按钮Command2，在文本框Text2中显示第m大的数。程序运行效果如下图所示：
为实现上述功能的VB程序如下，在程序划线处填入合适的代码。
Dim d(1 To 20) As Integer
Const n ＝ 20
Private Sub Form_Load()
Dim i As Integer, j As Integer, t As Single
List1.Clear
Randomize
For i ＝ 1 To n
________①________
List1.AddItem Str(d(i))
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t1 As Integer
For i ＝ 1 To n － 1
For j ＝________②________
If d(j) < d(j － 1) Then
t1 ＝ d(j): d(j) ＝ d(j － 1): d(j － 1) ＝ t1
End If
Next j
Next i
For i ＝ 1 To n
List2.AddItem Str(d(i))
Next i
End Sub
Private Sub Command2_Click()
Dim m As Integer
m ＝ Val(Text1.Text)
Text2.Text ＝ “第” ＋ Str(m) ＋ “ 大的数为：”
＋ ________③________
End Sub
10.小王编写了一个数据排序且将重复数删除的VB程序。算法的基本思想：先随机生成20个[1，50]区间内的整数，然后按照数据从低到高进行排序，最后删除重复数(相同的数据只保留一个)。
程序运行时，单击“生成随机数”按钮Command1，则生成20个[1，50]区间内的整数，存储在数组a中，并显示在文本框Text1中；单击“排序并去重”按钮Command2，则将数组a中数据进行从低到高排序，并将排序结果显示在文本框Text2中，将去重后结果显示在文本框Text3中，在标签Label4中显示共删除的重复数个数，程序运行界面如下图所示。
实现上述功能的VB程序如下，请回答下列问题：
(1)若20个随机数分别为：7，18，5，7，7，12，7，1，10，14，17，7，9，7，10，16，5，18，8，18，则去掉的重复数共________个。
(2)请在划线处填入合适的代码。
Dim a(1 To 20) As Integer
Const n ＝ 20
Private Sub Command1_Click()
Dim i As Integer, s1 As String
Randomize
s1 ＝ “ ”
For i ＝ 1 To n
a(i) ＝ Int(Rnd * 50 ＋ 1)
s1 ＝ s1 ＋ Str(a(i))
Next i
Text1.Text ＝ s1
End Sub
Private Sub Command2_Click()
Dim i As Integer, j As Integer, p As Integer, tt As Integer
Dim ans As Integer, s2 As String, s3 As String
For i ＝ 1 To n － 1
p ＝ i
For j ＝ n To i ＋ 1 Step －1
If a(j) < a(p) Then p ＝ j
Next j
If a(i) < > a(p) Then
tt ＝ a(i)
a(i) ＝ a(p)
a(p) ＝ tt
End If
Next i
s2 ＝ “ ”：s3 ＝ “ ”
ans ＝ 0
For i ＝ 1 To n
s2 ＝ s2 ＋ Str(a(i))
Next i
Text2.Text ＝ s2
__________①__________
s3 ＝ Str(a(1))
For i ＝ 2 To n
If a(i) < > q Then
__________②__________
q ＝ a(i)
Else
__________③__________
End If
Next i
Text3.Text ＝ s3
Label4.Caption ＝ Str(ans)
End Sub
