资源简介

专项测试五　排序算法
一、选择题
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

展开更多......

收起↑