资源简介

第3节　选择排序及程序实现
考试内容
考试要求
选择排序算法思想
c
选择排序程序实现
c
一、选择排序算法思想
每趟排序是在所有的数据中找出最大(或最小)的数据，与第一个数据交换位置，然后再在剩下的数据中找出最大(或最小)的数据，与第二个数据交换位置，以此类推，直到所有元素成为一个有序序列为止。
n个数据排序共需进行n－1趟(遍)排序。
二、选择排序算法框架
设定：对数组d中的n个数据进行升序排序。
(1)从前往后进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　假定i位置上的数为最小数
　For j ＝ i ＋ 1 To n　′i后面的位置
　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
交换d(i)与d(k)
　End If
Next i
注：若要按降序排列，将程序中的语句“If d(k)>d(j)”改为“If d(k)(2)从后往前进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　假定i位置上的数为最小数
　For j ＝ n To i ＋ 1　Step －1　 ′i后面的位置
　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
　交换d(i)与d(k)
　End If
Next i
注：若要按降序排列，将程序中的语句“If d(k)>d(j)”改为“If d(k)三、选择排序程序实现
设定：对数组d中的n个数据进行升序排序。
(1)从前往后进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　k ＝ i　　　　　　′假定i位置上的数为最小数
　For j ＝ i ＋ 1 To n　　　 ′i后面的位置
　 If d(k) > d(j) Then k ＝ j　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i
(2)从后往前进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　k ＝ i　′假定i位置上的数为最小数
　For j ＝ n To i ＋ 1 Step －1　′i后面的位置
If d(k) > d(j) Then k ＝ j　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i

一、选择排序算法思想
理解选择排序的基本思想，学会将待排数据按照选择算法思想进行手工模拟排序。
【典例1】 使用选择排序对下表中9个数据进行排序，排序过程如下所示：
初始数据
100
50
80
70
60
35
90
85
25
第1遍
100
50
80
70
60
35
90
85
25
第2遍
100
90
80
70
60
35
50
85
25
第3遍
则第三遍的排序结果为(　　)
A.100，90，85，80，70，60，35，50，25
B.100，90，85，70，60，35，50，80，25
C.100，90，85，80，70，60，50，35，25
D.100，90，85，60，70，35，50，80，25
解析　本题主要考查选择排序算法的基本思想。观察第1、2遍的排序结果可知，该选择排序为降序排序，第3遍排序时，数据85与80进行交换，因此第三遍排序后的结果为“100，90，85，70，60，35，50，80，25”，答案为B。
答案　B
【变式训练】 采用选择排序算法对数组d中的8个数据“20，8，6，4，15，3，19，50”进行排序，部分程序如下：
For i＝1 To 5
k ＝ i
For j＝i＋1 To 8
If d(j)If i< >k Then
tt＝d(k)：d(k)＝d(i)：d(i)＝tt
End If
　Next j
Next i
该程序段执行后，数组元素d(1)～d(8)依次为(　　)
A.3，4，6，8，15，19，20，50
B.3，4，6，8，15，50，20，19
C.3，4，6，8，15，20，19，50
D.3，4，6，8，15，20，50，19
解析　本题主要考查的是选择排序。根据语句“If d(j)初始数据
20
8
6
4
15
3
19
50
第1遍
3
8
6
4
15
20
19
50
第2遍
3
4
6
8
15
20
19
50
第3遍
3
4
6
8
15
20
19
50
第4遍
3
4
6
8
15
20
19
50
第5遍
3
4
6
8
15
20
19
50
因此答案为C。
答案　C
【方法总结】 选择排序时，首先用变量记录最大或最小元素的位置，然后与相应位置上的元素进行交换；通过If语句中表达式确定排序的升降性。
二、选择排序算法实例应用
【典例2】 有如下VB程序段：
For n ＝ 1 To 4
　p ＝ n
　For m ＝ n ＋ 1 To 5
If a(m) < a(p) Then p ＝ m
　Next m
　If p > n Then
temp ＝ a(n)
a(n) ＝ a(p)
a(p) ＝ temp
　End If
Next n
设数组元素a(1)～a(5)的值分别为“1000，1200，1018，1208，1019”，经过该程序段“加工”后，数组元素a(1)＋a(3)的值为(　　)
A.2018 B.2019
C.2200 D.2208
解析　本题主要考查的是选择排序算法。排序方式为升序，排序后数组元素a(1)～a(5)的值分别为“1000，1018，1019，1200，1208”，因此a(1)＋a(3)＝1000＋1019＝2019。
答案　 B
【变式训练】 小赵对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：
p ＝ 1: q ＝ 10
Do While p < q
　iMin ＝ p: iMax ＝ p
　For i ＝ p ＋ 1 To q
If a(i) < a(iMin) Then iMin ＝ i
If a(i) > a(iMax) Then iMax ＝ i
　Next i
　t ＝ a(iMin): a(iMin) ＝ a(p): a(p) ＝ t
　____①____
　t ＝ a(iMax): a(iMax) ＝ a(q): a(q) ＝ t
　p ＝ p ＋ 1
　q ＝ q － 1
Loop
要使程序实现上述算法思想，则程序中划线处的语句是(　　)
A.If iMax ＝ p Then iMax ＝ iMin
B.If iMin ＝ p Then iMin ＝ iMax
C.If iMax ＝ p Then iMin ＝ iMax
D.If iMin ＝ p Then iMax ＝ iMin
解析　本题考查的是选择排序算法的变式。选择排序的原本思想是找出一个最大(或最小)的元素将它与第一个元素进行互换，本题的选择排序算法思想是：首先找出当前数据中的一个最小元素和一个最大元素，然后将最小元素与队首元素交换，将最大元素与队尾元素进行互换。当最大元素在p位置时，由于它与最小元素进行互换后，原来的存放位置发生了变化，即由p的位置更改为iMin的位置了，因此要将它的新位置记录在iMax中，然后再与q位置上的元素进行互换。因此，答案为A。
答案　A
【方法总结】 在掌握选择排序常规算法的基础上，还要对选择排序的各种变式进行研究，做到举一反三，触类旁通。
1.对数组元素a(1)～a(8)进行从小到大排序，其选择排序算法的VB程序段如下：
For m＝1 To 7
　 p＝m
　 For n＝m＋1 To 8
　 ________
　 Next n
　 IF p< >m then t＝a(p)：a(p)＝a(m)：a(m)＝t
Next m
划线处的语句是(　　)
A.If a(n)B.If a(n)C.If a(n)>a(p) Then p＝n
D.If a(n)>a(p) Then p＝m
解析　本题主要考查的是选择排序的程序实现。要降序排序，因此划线处的语句为If a(n)答案　B
2.实现某排序算法的部分VB程序如下：
For i ＝ 1 To 7
　 k ＝ i
　 For j ＝ i ＋ 1 To 8
　 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(8)的数据依次为“1，2，15，8，16，7，6，5”。则下一遍排序“加工”后数组元素a(1)到a(7)的数据依次是(　　)
A.1，2，5，6，7，8，15，16
B.1，2，5，15，16，7，6，8
C.1，2，5，8，16，6，7，15
D.1，2，5，8，16，7，6，15
解析　本题主要考查的是选择排序(升序)的实现过程。根据程序代码或给出的数据序列可知，是升序排序，前2个数已经有序，因此下一遍的排序是剩下的6个元素中选出一个最小数与第三个位置上的元素进行交换，即15与5交换。
第i遍
1
2
15
8
16
7
6
5
第i＋1遍
1
2
5
8
16
7
6
15
具体排序如表。
答案　D
3.十佳歌手评选。某校举行学生歌唱比赛，得分最高的前十名选手为校园十佳歌手。下面的Visual Basic程序用于解决这一问题，数组a中存储了参赛学生的编号，数组b中存储了参赛学生的得分，原始信息显示在列表框List1中，单击“计算”按钮后，“得分”最高的10名学生的信息显示在列表框List2中，程序运行界面如图所示。
程序代码如下：
Const n ＝ 80
Dim a(1 To n) As String, b(1 To n) As Single
Private Sub Command1_Click()
　 Dim i As Integer, j As Integer, m As Integer
　 Dim s As String, t As Single
For i ＝ 1 To n － 1
m ＝ i
For j ＝ i ＋ 1 To n
　 If ____①____ Then m ＝ j
Next j
If____②____ Then
　s ＝ a(i): a(i) ＝ a(m): a(m) ＝ s
　t ＝ b(i): b(i) ＝ b(m): b(m) ＝ t
End If
Next i
For i ＝ 1 To 10
List2.AddItem a(i) ＋ “　 ” ＋ Str(b(i))
　 Next i
End Sub
Private Sub Form_Load()
′此过程用于对数组a和数组b进行赋值，并显示在List1中，代码略
End Sub
(1)程序中加框部分的算法是________________(选填：选择排序/冒泡排序)。
(2)在程序①和②划线处，填入适当的语句或表达式，把程序补充完整。
解析　本题主要考查的是选择排序算法。十佳歌手的评选是按照选手的得分降序排序，取前十名得到的，数组b存储的是选手的得分，因此①处的语句为b(m)m。
答案　(1)选择排序 (2)①b(m) < b(j)　②i < > m
基础巩固
1.有如下程序段：
For i ＝ 1 To 2
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)的值依次为“3，11，19，17，7”，经过该程序段“加工”后，数组元素a(1)到a(5)的值依次为(　　)
A.3，7，11，17，19 B.19，17，11，7，3
C.19，17，3，11，7 D.19，17，3，7，11
解析　本题主要考查的是选择排序算法。这是普通的选择排序，每遍排序时将i位置的元素顺序与它后面的元素比较，若比它大，则交换它们的位置。本程序是求二遍降序排序后数据的顺序。
答案　C
2.有如下VB程序段：
For n ＝ 1 To 4
　p ＝ n
　For m ＝ n ＋ 1 To 5
If a(m) < a(p) Then p ＝ m
　Next m
　 If p > n Then
temp ＝ a(n)
a(n) ＝ a(p)
a(p) ＝ temp
　End If
Next n
设数组元素a(1)～a(5)的值分别为“1000，1200，1018，1208，1019”，经过该程序段“加工”后，数组元素a(1)＋a(3)的值为(　　)
A.2018 B.2019
C.2200 D.2208
解析　本题主要考查的是选择排序算法。排序方式为升序，排序后数组元素a(1)～a(5)的值分别为“1000，1018，1019，1200，1208”，因此a(1)＋a(3)＝1000＋1019＝2019。
答案　 B
3.某排序算法的VB程序段如下：
　n ＝ 10
　For i ＝ n To 8 Step －1
p ＝ i
For j ＝ i － 1 To 1 Step －1
　 If a(p) > a(j) Then p ＝ j
Next j
If p < i Then
　 tt ＝ a(p): a(p) ＝ a(i): a(i) ＝ tt
End If
　Next i
　For i ＝ 1 To n
s ＝ s ＋ Str(a(i))
　Next i
　Text1.Text ＝ s
End Sub
数组元素a(1)到a(10)的值依次为“92，1，84，52，69，50，29，68，87，19”，执行该程序段，文本框Text1中显示的是(　　)
A.92 87 84 69 68 52 50 29 19 1
B.92 87 84 52 69 50 68 29 19 1
C.92 87 84 69 52 50 68 29 19 1
D.92 87 84 52 50 69 68 29 19 1
解析　本题是选择排序算法的一种变式。本题的选择排序进行的方式为：从后往前进行排序，即从后往前找到一个最小数，然后让其与最后一个数进行交换位置，再从后往前找到第二小的数，让其与倒数第二个数交换位置，共进行3趟排序，求三趟排序后数列的情况。
答案　B
4.某程序运行界面如图所示。程序运行时，单击“生成随机数”按钮，将随机生成n个[100，500]区间内的偶数，并在列表框List1中显示；在文本框Text1中输入整数k，单击“排序”按钮，将第k趟(遍)升序排序后的数据显示在列表框List2中。
在程序中的划线处，填入适当的语句或表达式，把程序补充完整.
Const n ＝ 12
Dim d(1 To n) As Integer
Private Sub Command1_Click()
　 Dim i As Integer
　 Randomize
　 For i ＝ 1 To n
　 d(i) ＝ Int(Rnd *____①____) * 2 ＋ 100
　 List1.AddItem Str(d(i))
　 Next i
End Sub
Private Sub Command2_Click()
　Dim k As Integer, i As Integer, j As Integer, t As Integer, p As Integer
　 k ＝ Val(Text1.Text)
　 For i ＝____②____
　 p ＝ i
　 For j ＝ i ＋ 1 To n
　　　 If ____③____ Then p ＝ j
　 Next j
　 If p < > i Then
　　　 t ＝ d(p): d(p) ＝ d(i): d(i) ＝ t
　 End If
　 Next i
　 For i ＝ 1 To n
　 List2.AddItem Str(d(i))
　 Next i
End Sub
解析　①代码表示生成随机数，随机整数的范围为[100，500]，括号内的范围为[0，200]，因此，①处代码为201；变量i表示排序的趟数，题目要求进行k趟排序，因此②处代码为1 To k；排序方式为升序，因此③处代码为d(p) > d(j)。
答案　①201　②1 To k　③d(p) > d(j)
能力提升
5.有一组正整数，要求对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。
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
　′读取一组正整数，存储在数组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
程序中加框(1)处应改正为_________________________________________；
加框(2)处应改正为________________________________________________。
解析　本题主要考查的是选择排序算法。本题对传统的选择排序进行变式，题意是对两类数据进行选择性排序。每趟排序进行时(升序)，首先将i位置上的元素当作是最小数，因此(1)处语句应改为k＝i，然后到它后面去找更小数，并将该数位置记录在变量k中。变量flag表示每趟进行时i位置上的数是否为素数，如果当前i位置的数不是素数，则找到它后面的第一个素数作为基数，并用k记录此素数的位置；如果素数已经出现过(flag＝True)，则该素数需要和它之前的素数比较大小，若当前素数更小，则更新k的值。
答案　(1)k＝i　(2)Not flag Or a(j) 6.小炫报名参加“智力大冲浪”节目。比赛规则如下：
比赛开始时参赛者将预先得到M元奖金。
比赛时间分为N个时段(N≤100)，有N个小游戏，每个时段可完成1个游戏，第i个小游戏必须在规定期限t(i)时段前完成(1≤t(i)≤N)，否则要从奖金M元中扣去奖金w(i)，w(i)为自然数，不同的游戏扣去的奖金是不一样的。每个游戏必须从整时段开始。注意：比赛绝对不会让参赛者赔钱！
例如：当N＝5，M＝100时
游戏编号
1
2
3
4
5
完成期限t(i)
1
4
2
3
2
扣除奖金数w(i)
5
4
10
8
7
在这种情况下，小炫依次完成编号为5、3、4、2、1的小游戏，获得了最高奖金95元。
他的算法思想：让扣款高的游戏尽量准时完成。扣除的奖金越少，则最后赢取的奖金越多。
(1)按扣款数值从大到小排序，在样例中，排序后游戏编号依次为3、4、5、1、2；
(2)对于游戏i，在时间段1到t(i)完成，效果都是一样的，所以尽量放置的时间段t(i)完成，若该时段已经被占用，则依次考查时间段t(i)－1, t(i)－2，……，1。在样例中，
①考虑游戏3，放置在时间段2完成(注：t(3)＝2)；
②考虑游戏4，放置在时间段3完成(注：t(4)＝3)；
③考虑游戏5，时间段2已被游戏3占用，放置在时间段1完成(注：t(5)－1＝1)；
④考虑游戏1，时间段1已被游戏5占用，不能按时完成，记录扣款；
⑤考虑游戏2，放置在时间段4完成(注：t(2)＝4)
小炫按如上算法编写了一个VB程序，计算“智力大冲浪”游戏中玩家最多可赢取的奖金，将结果输出到文本框Text1中。
VB程序代码如下所示，请在划线处填入合适代码。
Dim n As Integer, m As Integer
Dim t(1 To 100) As Integer　′变量t(i) 表示第i个游戏的完成期限
Dim w(1 To 100) As Integer　 ′变量w(i) 表示第i个游戏未完成要扣除的奖金
Dim f(1 To 100) As Boolean　 ′变量f(i)表示第i个时段是否已经被占用
Private Sub Form_Load()
　′初始化游戏设置信息，时段数量n、初始奖金数m 、数组t、数组w
　′代码略
End Sub
Sub swap(x As Integer, y As Integer) ′自定义过程，用Call语句来调用该过程
　Dim z As Integer
　z ＝ x: x ＝ y: y ＝ z
End Sub
Sub sort()　′自定义过程，可以用Call语句来调用该过程
　Dim x As Integer, i As Integer, j As Integer
　For i ＝ 1 To n － 1
For j ＝ i ＋ 1 To n
　 If w(i) < w(j) Then
Call swap( w(i), w(j) )　′调用自定义过程
　　 ____①____
　 End If
Next j
　Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, k As Integer, p As Integer
　Call sort　′调用自定义过程
　tot ＝ 0
　For i ＝ 1 To n
f(i) ＝ True
　Next i
　For i ＝ 1 To n ′对每个游戏从该游戏的规定期限开始往左找可用时间段
　′找到可用时间段则完成该游戏，否则放弃该游戏
p ＝ －1
k ＝ t(i)
Do While k > 0 And p ＝ －1
　If f(k) ＝ True Then
p ＝ k
f(k) ＝ False
　 Else
　 ____②____
　 End If
Loop
If p ＝ －1 Then tot ＝ tot ＋ w(i)
　Next i
　____③____
　Text1.Text＝Str(ans)
End Sub
解析　本题主要考查的是选择排序的朴素(非优化的)算法及程序综合应用能力。自定义过程sort()的功能是将数据按游戏扣除奖金数的降序排序，因此在满足条件时，除了交换扣除奖金数的数据外(t(i)与t(j))，还需交换游戏完成期限的数据，即交换t(i)与t(j)的值，因此①处应填入的语句为Call swap(t(i)，t(j))，也可以写作Call swap(t(j)，t(i))；②处表示f(k) ＝ False时的情况，即第k个时段已被用掉，按照游戏规则，将往左寻找一个空的时段，因此②处语句为k＝k－1；变量tot表示扣除的总奖金数，m表示游戏开始前的总的奖金数，因此游戏结束时所获得的奖金数ans为m－tot，故③处应填入的语句为ans＝m－tot。
答案　①call swap(t(i)，t(j))或Call swap(t(j)，t(i))
②k＝k－1　③ans＝m－tot
课件19张PPT。第3节　选择排序及程序实现一、选择排序算法思想每趟排序是在所有的数据中找出最大(或最小)的数据，与第一个数据交换位置，然后再在剩下的数据中找出最大(或最小)的数据，与第二个数据交换位置，以此类推，直到所有元素成为一个有序序列为止。
n个数据排序共需进行n－1趟(遍)排序。二、选择排序算法框架设定：对数组d中的n个数据进行升序排序。
(1)从前往后进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　假定i位置上的数为最小数
　For j ＝ i ＋ 1 To n　′i后面的位置
　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
交换d(i)与d(k)
　End If
Next i注：若要按降序排列，将程序中的语句“If d(k)>d(j)”改为“If d(k)(2)从后往前进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　假定i位置上的数为最小数
　For j ＝ n To i ＋ 1　Step －1　 ′i后面的位置
　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换　交换d(i)与d(k)
　End If
Next i
注：若要按降序排列，将程序中的语句“If d(k)>d(j)”改为“If d(k)(1)从前往后进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　k ＝ i　　　　　　′假定i位置上的数为最小数
　For j ＝ i ＋ 1 To n　　　 ′i后面的位置
　 If d(k) > d(j) Then k ＝ j　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i(2)从后往前进行比较
For i ＝ 1 To n － 1　′n个排序共进行n－1趟排序
　k ＝ i　′假定i位置上的数为最小数
　For j ＝ n To i ＋ 1 Step －1　′i后面的位置
If d(k) > d(j) Then k ＝ j　′若找到更小的数，则将用k记录此数的位置
　Next j
　If k < > i Then　′若i位置上的数不是最小数，则和k位置上的数进行互换
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i一、选择排序算法思想理解选择排序的基本思想，学会将待排数据按照选择算法思想进行手工模拟排序。【典例1】 使用选择排序对下表中9个数据进行排序，排序过程如下所示：则第三遍的排序结果为(　　)
A.100，90，85，80，70，60，35，50，25
B.100，90，85，70，60，35，50，80，25
C.100，90，85，80，70，60，50，35，25
D.100，90，85，60，70，35，50，80，25解析　本题主要考查选择排序算法的基本思想。观察第1、2遍的排序结果可知，该选择排序为降序排序，第3遍排序时，数据85与80进行交换，因此第三遍排序后的结果为“100，90，85，70，60，35，50，80，25”，答案为B。
答案　B【变式训练】 采用选择排序算法对数组d中的8个数据“20，8，6，4，15，3，19，50”进行排序，部分程序如下：For i＝1 To 5
k ＝ i
For j＝i＋1 To 8
If d(j) If i< >k Then
tt＝d(k)：d(k)＝d(i)：d(i)＝tt
End If
　Next j
Next i该程序段执行后，数组元素d(1)～d(8)依次为(　　)
A.3，4，6，8，15，19，20，50
B.3，4，6，8，15，50，20，19
C.3，4，6，8，15，20，19，50
D.3，4，6，8，15，20，50，19解析　本题主要考查的是选择排序。根据语句“If d(j)【典例2】 有如下VB程序段：For n ＝ 1 To 4
　p ＝ n
　For m ＝ n ＋ 1 To 5
If a(m) < a(p) Then p ＝ m
　Next m
　If p > n Then
temp ＝ a(n)
a(n) ＝ a(p)
a(p) ＝ temp
　End If
Next n设数组元素a(1)～a(5)的值分别为“1000，1200，1018，1208，1019”，经过该程序段“加工”后，数组元素a(1)＋a(3)的值为(　　)
A.2018 B.2019
C.2200 D.2208
解析　本题主要考查的是选择排序算法。排序方式为升序，排序后数组元素a(1)～a(5)的值分别为“1000，1018，1019，1200，1208”，因此a(1)＋a(3)＝1000＋1019＝2019。
答案　 B【变式训练】 小赵对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：p ＝ 1: q ＝ 10
Do While p < q
　iMin ＝ p: iMax ＝ p
　For i ＝ p ＋ 1 To q
If a(i) < a(iMin) Then iMin ＝ i
If a(i) > a(iMax) Then iMax ＝ i　Next i
　t ＝ a(iMin): a(iMin) ＝ a(p): a(p) ＝ t
　____①____
　t ＝ a(iMax): a(iMax) ＝ a(q): a(q) ＝ t
　p ＝ p ＋ 1
　q ＝ q － 1
Loop要使程序实现上述算法思想，则程序中划线处的语句是(　　)
A.If iMax ＝ p Then iMax ＝ iMin
B.If iMin ＝ p Then iMin ＝ iMax
C.If iMax ＝ p Then iMin ＝ iMax
D.If iMin ＝ p Then iMax ＝ iMin解析　本题考查的是选择排序算法的变式。选择排序的原本思想是找出一个最大(或最小)的元素将它与第一个元素进行互换，本题的选择排序算法思想是：首先找出当前数据中的一个最小元素和一个最大元素，然后将最小元素与队首元素交换，将最大元素与队尾元素进行互换。当最大元素在p位置时，由于它与最小元素进行互换后，原来的存放位置发生了变化，即由p的位置更改为iMin的位置了，因此要将它的新位置记录在iMax中，然后再与q位置上的元素进行互换。因此，答案为A。答案　A【方法总结】 在掌握选择排序常规算法的基础上，还要对选择排序的各种变式进行研究，做到举一反三，触类旁通。

展开更多......

收起↑