教师备用题库
1.有以下VB程序段
For i=1 To 3
For j=i To 5
If a(j) > a(j+1) Then
t=a(j): a(j)=a(j+1): a(j+1)=t
End If
Next j
List1.AdcIItem Str(a(i))
Next i
a(1)到a(6)的初始值依次为“8 6 5 7 9 3 ”,经过该程序段“加工”后,列表框List1中显示的是( )
A.8 7 6 B.8 7 9 C.6 5 3 D.5 6 7
答案 C 本题考查排序。当i=1时,j从1到5,因此数组从头到尾,把大的往后推,完成后得到6 5 7 8 3 9,因此输出a(1)=6;当i=2时,j从2到5,因此数组从第2个数开始,从头到尾,把大的往后推,完成后得到6 5 7 3 8 9,因此输出a(2)=5;当i=3时,j从3到5,因此数组从第3个数开始,从头到尾,把大的往后推,完成后得到6 5 3 7 8 9,因此输出a(3)=3。
2.下面程序是一个改进过的冒泡排序:
Dim a(1 To 5) As Integer
a(1)=5: a(2)=10: a(3)=9: a(4)=3: a(5)=7
n=5: p=0
swap=True
Do While swap=True
swap=False
For i=1 To n-1
If a(i) > a(i+1) Then
t=a(i): a(i)=a(i+1): a(i+1)=t
swap=True
End If
Next i
If swap=True Then p=p+1
Loop
Text1.Text=p
该程序段执行后,在文本框Text1中显示的内容为( )
A.1 B.2 C.3 D.4
答案 C 逻辑类型变量 swap 用于标记数组中元素是否有过交换,如果有交换,值为True,否则为 False。变量 p 统计有数据交换过的排序趟数,程序实现升序排序,从前往后,大的元素下沉。经过第一趟排序后数组 a 中的元素值依次为:5 9 3 7 10 ,数据有过交换,所以 p=1。经过第二趟排序后数组 a 中的元素值依次为:5 3 7 9 10 ,数据有交换,p=2。经过第三趟排序后数组 a 中的元素值依次为:3 5 7 9 10 ,数据有交换,p=3。第四趟时,数据无交换,swap=False,p 值不变。 所以答案选 C。
3.(2014上海6月学考,3分)在某篮球联赛中,明星队6场比赛得分依次为103,77,95,71,68,89,若采用冒泡排序算法对其进行排序,第一轮排序结果是68,103,77,95,71,89。则第三轮排序中最先进行比较的一对数为
与 。?
答案 95;89
解析 本题主要考查冒泡排序的思想方法。冒泡排序的基本思想是从最后的一个元素起,自后向前比较相邻的两个数据,如果是升序排序,则将较小的数据换到前面,较大的换到后面。从第一轮结果可以看出是从小到大排序。因此第二轮排序:89和71比较,不交换;71和95比较,交换;71和77比较,交换;71和103比较,交换。第二轮排序的结果是:68,71,103,77,95,89。第三轮排序中最先进行比较的一对数是95和89。
4.新华书店准备举行“买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 x>j 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 s(i)<3 Then ’②
payment=payment+s(i)
End If
Next i
Label1.Caption=“总金额:” & cost
Label2.Caption=“实付:” & payment
End Sub
答案 ①s(x)
②i Mod 3 <> 0
解析 ①纵观程序可知,前一段程序是降序排序过程,后一段是统计总金额和应付金额的过程。前一段程序是标准的选择排序程序,降序排序中临时下标x 更新的原则是j 位元素比它还要大时才更新,因此答案为s(x)②后一段程序中,由输出可知,程序没有统计可以减免的书的金额,而是直接统计了总金额和应付金额,而条件i Mod 3=0是表示可以减免的书,那么i Mod 3<>0表示不可以减免的书。
5.(2015浙江10月学考+选考,16,4分)n个数据的冒泡排序需要经过(n-1)遍加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面。小刘发现:当某一遍加工过程中没有数据交换时,说明数据已经有序,无需进一步加工。为此,小刘对算法进行优化,编写了一个VB程序,功能如下:运行程序时,在列表框List1中显示排序前数据,单击“排序”按钮Command1,在列表框List2中显示这些数据按升序排序后的结果,在标签Label3中显示排序过程的加工遍数。运行效果如图所示。
/
实现上述功能的VB代码如下,但加框处代码有错,请改正。
Dim a(1 To 8)As Integer
Dim n As Integer
Private Sub Form_Load( )
’n=8,排序前数据存储在数组a中,并在列表框List1中显示
’代码略
End Sub
Private Sub Command1_Click( )
Dim flag As Boolean ’flag值为True表示一遍加工中发生过交换
i=1
flag=True
Do Whilei<=n-1 Or flag=True ’(1)
flag=False
For j=n To i+1 Step-1
If a(j) k=a(j):a(j)=a(j-1):a(j-1)=k
flag=True
End If
Next j
i=i+1
Loop
Label3.Caption=“排序过程的加工遍数为”+Str(i) ’(2)
For i=1 To n
List2.AddItem Str(a(i))
Next i
End Sub
答案 (1)i<=n-1And flag=True (2)Str(i-1)
解析 本题考查冒泡排序算法的程序实现。(1)根据题干可知,循环结束的条件是:①上一遍加工过程中没有数据交换,此时flag=True;②排序已经完成n-1遍,即i=n。只要满足①②两个条件中的任意一个,循环即可结束,因此正确的Do语句的条件表达式为i<=n-1 And flag=True。逻辑“与”运算,只有当运算符两边的表达式逻辑值都为真时,计算的结果值才为真,否则计算的结果值总是假。若引用原有条件表达式i<=n-1 Or flag=True,则只有当这两个条件均不满足时,才会退出循环,这与题意不符。(2)当执行最后一遍循环时,程序会执行语句i=i+1,但此时循环退出,并没有继续排序,所以真正的排序遍数是i-1次,题中的Str(i)应改为Str(i-1)。
6.小王在研究n个数的冒泡排序算法,发现可以从两个方面进行优化:
(1)在每遍冒泡过程中,若最后一次交换的是last与last-1位置,则last位置之前的相邻数据均已有序。进行下一遍冒泡时,无序区域设置[last, n],这样可使无序区域缩小。
(2)若在某一遍排序中没有数据交换,说明待排序数据都已经有序,冒泡排序过程可在此遍排序后结束。因此可以引入一个变量flag,记录在每遍排序过程中是否发生了交换。
小王设计了如下VB程序,功能如下:按Cominandl“生成数据”后,生成一组随机的两位整数存入数组a,并输出在列表框List1中。单击Command2“排序”后,a中的数据进行降序排序,排序后的数据显示在列表框List2中,排序过程中实际的冒泡遍数显示在Label2上。程序运行界面如下所示。
/
实现上述功能的VB程序如下,回答下列问题:
(1)若按小王优化后的冒泡排序算法,数据28, 15, 10, 8, 12进行降序排序,冒泡的遍数 (填数字)。?
(2)在画线处填入合适的代码。
Dim a(1 To 20) As Integer
Private Sub Commandl_Click()
Dim i As Integer, j As Integer
List1. Clear: List2. Clear
Randomize
For i=1 To 20
① ?
For j=1 To i-1
If a(i)=a(j) Then i=i-1: Exit For
Next j
Next i
For i=1 To 20
Listl. Addltem Str(a(i))
Next i
End Sub
Private Sub Commandl2_Click()
Dim flag As Boolean, i As Integer, j As Integer
Dim temp As Integer, nuui As Integer, last As Integer
nuin=0: last=1
flag=True
Do While flag=True
② ?
For j=20 To last+1 Step-1
If a(j) > a(j-1) Then
temp=a(j): a(j)=a(j-1): a(j-1)=temp
③ ?
flag=True ??有交换发生
End If
Next j
num=num+1
Loop
For i=1 To 20
List2. Addltem Str(a(i))
Next i
Label3. Caption=〃本次排序的冒泡遍数为:〃 & Str (num)
End Sub
答案 (1)2(2)① a(i)=Int(Rnd* 90)+10 ② flag=False ③ last=j
解析 第①空,冒泡排序,降序,从前往后,小的元素下沉。第一趟排序后数据依次为 28 15 10 12 8,第二趟排序后数据依次为 28 15 12 10 8,已完成降序排序。
第②空,随机生成一组两位整数[10,99]存入数组 a 中。可以使用随机生成[a,b]之间的正整数公式:Int(Rnd*(b-a+1)+a) 。
第③空,变量 flag 记录在每遍排序过程中是否发生了交换,如果有交换,值为 True,否则为 False。每一趟排序前要初始化 flag 的值为 false。
第④空,在每遍冒泡过程中,若最后一次交换的是 last 与 last-1 位置的,last 位置之前的相邻数据均已有序。进行下一遍冒泡,无序区域设置为[last,n],使当前无序区域缩小。所以每遍冒泡过程中要记录下最后一次交换的位置 j,把 j 存储到 last 中。
第3节 排序算法及程序实现
模拟演练
1.有一段VB程序,代码如下:
For i=1 To 3
For j=8 To i+1 Step-1
If a(j) < a(i) Then
t=a(j): a(j)=a(i): a(i)=t
End If
Next j
Next i
数组元素a(1)到a(8)的值依次为“35, 18, 14, 20, 30, 15, 28, 26”,运行该程序段后,a(5)到a(8)的值依次是( )
A.30,26,28,35 B.14,15,18,20
C.26,15,18,14 D.26,28,30,35
答案 A 程序进行了三趟排序。第 i 趟排序,即从后往前逐个与 a(i)进行比较,如果比 a(i)小,数据交换。经过第一趟排序后数组 a 中的元素值依次为:14,18,15,20,30,26,28,35;第二趟排序后数组 a 中的元素值依次为:14,15,18,20,30,26,28,35;第三趟排序数据不变。 所以答案选 A。
2.有如下程序段,数组元素a(1)到a(5)的值依次为“33,24,4,16,77”,执行该程序段后,变量t的值为( )
t=0
For i=1 To 4
flag=False
For j=5 To i+1 Step-1
If a(j)>a(i) Then flag=True
t=t+1
temp=a(j):a(j)=a(i):a(i)=temp
End If
Next j
If flag=False Then Exit For
Next i
A.2 B.3 C.4 D.5
答案 B 本题考查程序阅读能力,第i趟处理时,在数组a中a(j)从后向前逐个与a(i)比较,变量t记录交换次数。i=1时,a(5)与a(1)交换,数组a变为77,24,4,16,33;i=2时,a(2)与a(5)交换,数组a变为77,33,4,16,24;i=3时,a(3)与a(5)交换,数组a变为77,24,33,16,4;i=4时,由于没有发生交换,直接退出循环。总交换次数为3次,因此正确答案是B。
3.某算法的部分程序段如下:
For i=1 To 7
k=i
For j=i+1 To 8
If a(j)>a(k) And a(j)>85 Then k=j
Next j
If k<>i Then t=a(i): a(i)=a(k): a(k)=t
Next i
数组元素a(1)到a(8)的原始数据依次为“89,70,79,85,99,80,82,74”,则第3遍“加工”后数组元素a(1)到a(8)的数据依次是( )
A.99,89,79,85,80,70,82,74
B.99,89,85,79,70,80,82,74
C.99,89,79,85,70,80,82,74
D.99,89,85,82,80,79,74,70
答案 C 本题考查冒泡排序。通过阅读程序可知,程序将数据中大于85的数字移到数组前降序排列。
4.有如下程序段:
For i=1 To 2
For j=1 To 6-i
If a(j) 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”,经过该程序段处理后,数组元素a(1)到a(6)的值依次为( )
A.29,31,54,58,71,78
B.78,71,58,54,31,29
C.54,29,31,58,71,78
D.71,58,54,78,31,29
答案 D 本题考查冒泡排序。由语句“For i=1 To 2”可知,这6个数只经过了两遍从前往后的冒泡排序,过程如下:
i
数组a初始:71,54,58,29,31,78
第1遍
71,58,54,31,78,29
第2遍
71,58,54,78,31,29
5.有如下程序段:
b(0)=0
For i=1 To 6
k=i
For j=i+1 To 7
If a(k) > a(j) Then k=j
Next j
If i <> k Then t=a(k): a(k)=a(i): a(i)=t
If a(i) <> a(i-1) Then
b(i)=i
Else
b(i)=b(i-1)
End If
Next i
若数组元素a(1)到a(7)的值依次为“6,7,6,3,9,2,3”,则经过上述程序加工后,b(5)的值是( )
A.3 B.4 C.5 D.6
答案 B 本题考查的是选择排序的改进。从代码中可以看出,该选择排序实现的是从小到大的排序效果,其中b数组的作用是用来记录排名,即如果前后两个数相等,则排名保持不变,如果前后两个数不相等,则排名更新为i。所以经过处理a(1)到a(7)的值为“2,3,3,6,6,7,9”,b(1)到b(7)的值为“1,2,2,4,4,6,7”,本题选B。
6.有如下Visual Basic程序段:
Dim a(1 To 7) As Integer, i As Integer, j As Integer
Dim k As Integer, c As Integer
a(1)=4: a(2)=9: a(3)=1: a(4)=5
a(5)=8: a(6)=6: a(7)=2
s=“”
For i=1 To 3
For j=i+1 To 7
If a(j) < a(i) Then
k=a(j): a(j)=a(i): a(i )=k
c=c+1
End If
Next j
s=Str(a(i))+s
Next i
Text1.Text=Str(c) & “:” & s
该程序段运行后,文本框Text1中显示的内容是( )
A.5:4 2 1 B.3:9 8 6 C.4:1 2 4 D.5:6 8 9
答案 A 本题主要考查冒泡排序算法。变量c的作用是记录数据交换的次数,经过计算共发生了5次数据交换,经过前三轮排序,升序序列的前3项为1、2、4。但是由于s=Str(a(i)) +s,最后的a(3)被加到最左边,中间是a(2),最右边的是a(1),因此正确答案是5:4 2 1,即选项A。
7.有如下VB程序段:
s=“26170534”:n=Len(s):y=“”
For i=1 To n
ch(i)=Mid(s, i, 1)
Next i
For i=1 To n
k=i
For j=i To n Step 2
If ch(j)< ch(k) Then k=j
Next j
If k <> i Then t=ch(k): ch(k)=ch(i): ch(i)=t
y=y & ch(i)
Next i
Label1.Caption=y
该程序段运行后,标签Label1中显示的内容是( )
A.0123 B.4567
C.01234567 D.04152637
答案 D 本题考查算法及其程序的实现。本题为选择排序的变形题,将选择排序程序的内循环步长1改成2。数组ch元素的值依次为ch(1)=“2”、ch(2)=“6”、ch(3)=“1”、ch(4)=“7”、ch(5)=“0”、ch(6)=“5”、ch(7)=“3”、ch(8)=“4”。i=1时,从ch(1)、ch(3)、ch(5)、ch(7)中找出最小元素和ch(1)交换;i=2时,从ch(2)、ch(4)、ch(6)中找出最小元素和ch(2)交换;i=3时,从ch(3)、ch(5)、ch(7)中找出最小元素和ch(3)交换,……,最终数组ch的元素的值依次为0、4、1、5、2、6、3、7。
8.有如下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 显示的内容是( )
A.3 4 6 B.6 8 9 C.3 6 4 D.3 6 6
答案 D 本题主要考查冒泡排序算法知识。5个数据,冒泡排序将大的值往后交换。进行前3轮的升序排序,然后分别输出前3轮排序的前3项。第一轮排序后结果是:3 6 8 4 9,输出第一项3。第二轮排序后结果是:3 6 4 8 9,输出第二项6。第三轮排序后结果是:3 4 6 8 9,输出第三项6。因此本题D选项正确,文本框Text1显示3 6 6。
9.有如下程序段:
For i=1 To 9
For j=10 To i+2 Step-1
If a(j) < a(j-2) Then
t=a(j): a(j)=a(j-2): a(j-2)=t
End If
Next j
Next i
数组元素a(1)到a(10)的值依次为“10,9,8,7,6,5,4,3,2,1”,执行该程序段后,数组元素a(8)中的值为( )
A.7 B.8 C.9 D.10
答案 A 本题考查冒泡排序。程序采用“隔位交换”的变形,由“If a(j) < a(j-2) Then”可知程序实现隔位递增排序,排序结果为“2,1,4,3,6,5,8,7,10,9”,答案为A。
10.小李基于选择排序算法编写了一个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
Elself a(j) = a(i) Then
a(j) = a(bottom)
If ① Then 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
② ?
End If
Loop
For i = 1 To ③ ?
Text2. Text = Text2.Text + Str(a(i))
Next i
End Sub
答案 ①k = bottom ②i = i + 1 ③bottom
解析 第①空,如果a(j) = a(i) 即发现重复数据,那么剔除重复数据a(j),就是用最后一个数据a(bottom)把a(j)替换掉。如果这时刚好找到的最小值是a(bottom),即k=bottom,那么k要改成j。
第②空,排序一遍,如果找到最小值的位置k刚好是初始化位置i,那么下一次缩小范围从i+1开始。
第③空,循环输出剔除重复数据并排序好后的数据,变量bottom已通过bottom=bottom-1语句对重复数据个数减去,所以存储的是剔除重复数据后的总数据个数。
第3节 排序算法及程序实现
真题再现
选考题组
1.(2018浙江11月选考,12,2分)下列VB程序段功能为:根据文本框Text1中各字符的大小关系,计算各字符升序排列的序号,并将序号保存在数组y中。如文本框内容为“2011”,程序运行后y(1)~y(4)各元素的值分别为“4,1,2,3”。
s=Text1.Text
n=Len(s)
For i=1 To n
y(i)=1
Next i
For i=1 To (1)
For j= (2) To n
If (3) Then
y(j)=y(j)+1
Else
y(j)=y(j)+1
End If
Next j
Next i
上述程序段3个方框处的表达式分别为( )
A.(1)n (2)1 (3)Mid(s,j,1)>=Mid(s,i,1)
B.(1)n (2)1 (3)Mid(s,j,1)>Mid(s,i,1)
C.(1)n-1 (2)i+1 (3)Mid(s,j,1)>=Mid(s,i,1)
D.(1)n-1 (2)i+1 (3)Mid(s,j,1)>Mid(s,i,1)
答案 C 本题考查字符串和数组的操作。y(i)表示第i个字符的次序,初始化为1。接下来的双循环,用i和j表示字符串中字符的位置,用i和j把所有的字符两两比较一遍,如果Mid(s,j,1)>= Mid(s,i,1),则y(j)=y(j)+1,反之,y(i)=y(i)+1。外循环i从1至n-1,内循环j从i+1至n。如i=1时,把第2至第n个字符依次与第1个字符比较;i=2时,把第3至第n个字符依次与第2个字符比较;……,以此类推。
2.(2017浙江4月学考+选考,12,2分)小赵对选择排序算法进行了如下改进:在数组的所有元素中找出最小和最大数据的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。小赵编写的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
答案 (1)a(j)a(j)或其他等价表达式) (2)a(j)=a(bottom)(或其他等价语句)
解析 (1)本程序使用冒泡排序思想,从小到大升序排序(后面元素比前面元素小要交换)。根据以下交换数据的代码可以推断,比较的是a(j)和a(j-1)的值。
(2)如果 a(j)=a(j-1),则表示a(j)和a(j-1)重复了,可以丢弃其中一个,可将数组最后一个值即a(bottom)放到a(j)的位置上替代a(j),然后bottom的值减1,相当于数组规模减少1个。
3.(2018浙江4月学考+选考,16,3分)有一组正整数,要求供对其中的素数进行升序排序。排序后素数在前,非素数在后。排序示例如下。
排序前
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
’读取一组正整数,存储在数组a 中,代码略
For i=1 To n-1
k=1 ’(1)
If IsPrime(a(k)) Then flag=True Else flag=False
For j=i+1 To n
If IsPrime(a(j)) Then
If a(j) < a(k) 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)k=i (2)a(j)解析 本题是选择排序的基础上加一个素数判断。程序的基本框架是选择排序,因此(1)处改为k=i。
(2)最后结果是从小到大排,因此(2)处填a(j) < a(k)貌似没错,但是要考虑到只排素数,素数放前面,非素数放后面,因此如果a(j)是素数,而a(k)是非素数,则一定要交换,将a(j)换到前面。第二种情况是,a(j) 和a(k)都是素数,且a(j)4.(2017浙江11月选考,16,3分)小李基于冒泡排序算法编写了一个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
Dim bottom As Integer ??剔除重复数据后元素的个数
’获取排序前数据依次存储在数组a中,并在文本框Text1中显示。代码略
bottom=n
i =1
Do While i<=bottom-1
For j=bottom To i+1 Step-1
Ifa(j) t=a(j): a(j)=a(j-1): a(j-1) =t
ElseIf a(j)=a(j-1)Then ??若相邻两个数据相等,进行剔除处理
a(bottom)=a(j) ??(2)
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
答案 (1)a(j)a(j)或其他等价表达式)
(2)a(j)=a(bottom)(或其他等价语句)
解析 (1)本程序使用冒泡排序思想,从小到大升序排序(后面元素比前面元素小要交换)。根据以下交换数据的代码可以推断,比较的是a(j)和a(j-1)的值。
(2)如果 a(j)=a(j-1),则表示a(j)和a(j-1)重复了,可以丢弃其中一个,可将数组最后一个值即a(bottom)放到a(j)的位置上替代a(j),然后bottom的值减1,相当于数组规模减少1个。
5.(2016浙江10月学考+选考,16,3分)小吴为了探究冒泡排序过程中数据的“移动”情况,编写了一个VB程序,功能如下:在列表框List1中显示排序前数据(存储在数组a中),在文本框Text1中输入初始位置(即下标值),单击“排序”按钮Command1后,在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况,排序后的数据显示在列表框List2中,程序运行界面如图所示。
/
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Dim a(1 To 8)As Integer
Dim n As Integer
Private Sub Form_Load()
’n=8,排序前的8个数据存储在数组a中,并在列表框List1中显示
’代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer,j As Integer,k As Integer
Dim pos As Integer ’变量pos存储指定数据的位置(即下标值)
Dim s As String ’变量s存储pos变化情况
s=Text1.Text
pos=Val(Text1.text)
For i=1 Ton-1
For j=n To i+1 Step-1
If a(j) k=a(j)??(1)
a(j-1)=a(j)
a(j)=k
’如果pos位置的数据参与交换,则更新pos值,记录pos变化情况
If pos=j Then
pos=j-1
s=s+“→”+Str(pos)
Else’(2)
pos=j
s=s+“→”+Str(pos)
End If
End If
Next j
Next i
Labell.Caption=“位置变化情况:”+s
For i=1 To n
List2.AddItem Str(a(i))
Next i
End Sub
答案 (1)k=a(j-1)
(2)Else If pos=j-1 Then(其中pos=j-1可用其他等价表达式)
解析 本题主要考查冒泡排序算法的程序实现。
(1)本小题考查如何实现两个数的交换。冒泡排序需要比较相邻两个数的大小,若后一个数比前一个数小,则交换两个数的位置。此处代码应该是k=a(j-1),即先将a(j-1)的值存入临时变量k,再将a(j)的值赋值给a(j-1),最后将临时变量k的值赋值给a(j)。
(2)本小题考查块if语句的运用。当两个相邻的数a(j)与a(j-1)有位置交换时,需要更新pos的值。若pos值为j时,更新pos值为j-1;若pos值为j-1时,更新pos值为j。
课件61张PPT。
第3节 排序算法及程序实现一 排序算法的基本思想二 排序算法的程序实现教材研读突破一 冒泡排序的变形突破二 选择排序的变形重难突破一、排序算法的基本思想
通常被排序的数据是一批同类型数据,存储在具有适当规模的数组变量中。通过排序可以调整数据在数组变量中的存储位置,使数组内的数据 呈现某种次序。
(1)冒泡排序教材研读 冒泡排序的基本思想是把待排序的n 个元素的数组看成是垂直堆
放的一列数据,从最下面的一个数据起,自下而上地比较相邻的两个数据,
将较小的数据换到上面。重复这一过程,直到处理完最后两个数据,称为 一遍加工。第一遍加工完成后,最小的数据已经上升到第1 个位置。然 后对余下的n-1 个数据重复上述处理过程,这是第二遍加工,第二遍加工 完成后,第二小的数据上升到了第2 个位置。然后再对余下的n-2 个元 素进行加工……。n 个数需要n-1 次加工。
以数据130,20,98,15,67,3 为例,从小到大冒泡排序的过程如下: (2)选择排序
选择排序的基本思想是在所有的记录中选出最小(大)的数据,把它
与第一个数据交换,然后在其余的记录中再选出最小(大)的数据与第二个数据交换。以此类推,直至所有数据排序完成。n 个数需要n-1 次加工(挑 选最小或最大数然后进行交换)。以数据130,20,98,15,67,3 为例,从小到大选择排序的过程如下:二、排序算法的程序实现
(1)冒泡排序的代码如下:
For i=1 To n-1 ??????n个数需要n-1次排序
For j=n To i+1 Step-1??????从后往前,两两比较,一直到第i+1个数
If a(j) temp=a(j-1):a(j-1)=a(j):a(j)=temp??????小的在后面,则交换
End If
Next j
Next i从小到大排序,If语句中条件表达式为:a(j)从大到小排序,If语句中条件表达式为:a(j)>a(j-1)。
(2)选择排序的代码如下:
For i=1 To n-1
k=i
For j=i+1 To n
If a(j)i Then
temp=a(i):a(i)=a(k):a(k)=temp
End If
Next i
说明:①虚线框内代码用于寻找数组元素a(i)到a(n)的最小值,变量k记录 当前找到的最小值的位置,即数组元素的下标,则a(k)就是当前找到的最 小的数组元素。它的思想方法是先假设数组的第i项是最小的(第i遍排序),因此k记为i,然后把从第i+1项开始的所有数组元素跟a(k)进行比较, 如果比a(k)小,则用k记录该元素的下标。这样循环结束后,变量k中存储 的就是数组中从第i项至第n项的最小元素的下标,a(k)就是第i项至第n 项中的最小元素。
②从小到大排序时,If语句中条件表达式为:a(j) 从大到小排序时,If语句中条件表达式为:a(j)>a(k)。1.按日期先后整理一堆文件的算法是:第一次,在这叠文件中从上到下找 出日期最早的文件反扣在桌面上;第二次从剩余文件中从上到下找出日 期最早的文件反扣在第一次找出的文件上;第三次,从剩余文件中从上 到下找出日期最早的文件反扣在第二次找出的文件上;……,依此类推, 最后完成整理工作。此算法属于?( A )
A.选择排序 B.对分查找 C.递归算法 D.冒泡排序解析 本题主要考查选择排序的基本思想。选择排序的基本思想 是从所有的记录中选出最大或最小的数据,把它与第一个数据交换,然 后在其余的记录中再选出最大或最小的数据与第二个数据交换。以此 类推,直至所有数据排序完成。本题中解决问题的思想方法是选择排序 的基本思想。2.(2016浙江名校新高考研究联盟第一次联考,12,2分)对下列数据序列 进行冒泡升序排序,在排序过程中效率最低的序列是?( A )
A.31,29,24,20,15,10 B.10,15,20,24,29,31
C.29,10,31,15,20,24 D.24,29,31,20,15,10解析 本题考查冒泡排序的基本原理。在比较次数一定的情况下, 冒泡排序的效率与数据发生的交换次数有关。选项A中的数据是逆序 (降序)排列,因此实现升序排序需要交换的次数最多,效率最低。3.用选择排序法对一组学生的身高数据进行升序排序,已知第一遍排序 结束后的数据序列为165,168,178,175,171,则下列选项中可能是原始数 据序列的是( B )
A.175,178,168,165,171 B.178,168,165,175,171
C.165,178,168,175,171 D.165,168,171,175,178解析 本题主要考查选择排序的基本思想。选择排序的基本思想 是从所有的元素中选出最小(升序排序)的数据,把它与第一个数据交换, 然后在其余的元素中再选出最小的数据与第二个数据交换。以此类推, 直至所有数据排序完成。因此第一遍排序后排第一位的165有5种可能 的来源,①原来就在第一位,不需要数据互换,那么原始数据就是165,168, 178,175,171;②从第二位换来,那么原始数据就是168,165,178,175,171; ③从第三位换来,那么原始数据就是178,168,165,175,171;④从第四位换 来,那么原始数据就是175,168,178,165,171;⑤从第五位换来,那么原始数
据就是171,168,178,175,165。4.有如下程序段:
For i=1 To 2
For j=5 To i+1 Step-1
If a(j) Next j
Next i数组元素a(1)到a(5)的值依次为“95,88,66,80,75”,经过该程序段“加 工”后,数组元素a(1)到a(5)的值依次为?( A )
A.66,75,95,88,80 B.66,75,80,95,88
C.95,88,66,80,75 D.95,88,80,75,66解析 此题为冒泡排序变形题,升序排序,排序两趟。答案为A。突破一 冒泡排序的变形
1.冒泡排序的标准写法(升序):
For i=1 To n-1 ??????n个数需要n-1次排序
For j=n To i+1 Step-1??????从后往前,两两比较,一直到第i+1个数
If a(j) temp=a(j-1):a(j-1)=a(j):a(j)=temp??????小的在后面,则交换
重难突破 End If
Next j
Next i
排序思想解析:n个数需要n-1遍排序;每一遍排序中,都是从最后一个
数开始,两两比较,小的换到前面,大的换到后面;第一遍把最小数推到了
第一个位置,第二遍把第二小的数推到了第二个位置,……。因此排序过 程中,是前面的数据先排好。2.冒泡排序的变形一(升序)
For i=1 To n-1
For j=n To i+1 Step-1
If a(j) temp=a(j-1):a(j-1)=a(j):a(j)=temp
End If
Next j
Next i 排序思想解析:与标准式唯一的差异就是两个比较项从a(j-1)和a(j) 变成a(j+1)和a(j),因此循环语句也从“For j=n To i+1 Step-1”变成了 “For j=n-1 To i Step-1”,本质上排序过程,与标准式是完全一样的。3.冒泡排序的变形二(升序)
For i=1 To n-1
For j=1 To n-i
If a(j+1) temp=a(j+1):a(j+1)=a(j):a(j)=temp
End If
Next j
Next i 排序思想解析:跟标准型不一样的是本代码中每一遍冒泡是从前往
后两两比较的,因此每一遍排序达到的效果是把最大值推到了最后面。第一遍排序后,最大值就到了最后位置,第二遍后,次大值就到了倒数第二个 位置……。排序过程中,是后面的数据先排好,因此每一遍排序的初值 都是1,后面的数随着一遍遍的排序慢慢排好了,因此终值是变化的,为n-i。4.冒泡排序的变形三(升序)
For i=1 To n-1
For j=i+1 To n
If a(j) temp=a(j):a(j)=a(i):a(i)=temp
End If
Next j
Next i 排序思想解析:在第i遍的排序中,把第i+1到第n个数依次与a(i)比较,如果比a(i)小,则交换。它的最大特点是:永远跟一个固定位置上的数去比 较。排序过程中,是前面的数据先排好。5.冒泡排序的错误变形
For i=1 To n-1
For j=i To n-1
If a(j+1) temp=a(j+1):a(j+1)=a(j):a(j)=temp
End If
Next j
Next i 错误原因解析:从语句“For j=i To n-1”可看出每一遍的冒泡过程
是把最大值从前往后推,因此排序过程中,是后面的数据先排好,前面的
数据是乱的,但是第i遍的冒泡过程是从第i个数开始的,因此i位置前面的
数据不能参与排序。而后面的数据已经排好的,其实是不需要参与排序 的。因此要改成“For j=1 To n-i” 6.冒泡排序的优化
当某一遍排序过程中没有数据交换,说明数据已经有序,无需进行下一 遍排序。代码如下:
Dim flag As Boolean
i=1
flag=True ??????flag值为True表示一遍加工中发生过交换
Do While i<=n-1 Or flag=true
flag=False For j=n To i+1 Step-1
If a(j) k=a(j):a(j)=a(j-1):a(j-1)=k
flag=True
End If
Next j
i=i+1
Loop 思想解析:用一个逻辑变量flag标记某一遍排序过程中是否有数据 交换,如果没有,则无需再进行下一遍排序。排序遍数是i-1遍。
另一种写法:
Dim flag As Boolean
For i=1 to n-1
flag=false
For j=n To i+1 Step-1
If a(j) k=a(j):a(j)=a(j-1):a(j-1)=k
flag=True
End If
Next j
If flag=false then exit for
Next i
注意:这种写法的排序遍数是i次,因为程序从中间跳出循环,不执行 “next i”指令,因此没有多加一次。例1 对于a数组排序的程序段如下:
For i=1 To n-1
For j=n To i+1 Step-1
If a(j) < a(j-1) Then
t=a(j): a(j)=a(j-1): a(j-l)=t
End If
Next j
Next i则下列程序段运行后,a数组的排序情况与上面程序段运行结果不同的 是?( D )解析 题干中的程序是冒泡排序,从后往前,小的元素上冒,最终实现升 序排序。A 选项是从前往后,大的元素下沉,实现升序排序。B 选项,程 序第 i 趟加工即将第 i 个数据和后面的每个数据比较一遍,使得第 i 个 数据比它后面的每个数据都小,所以也是升序。C 选项和题干一样,只 是变化了一下循环变量的表示方式。D 选项是从前往后比,大的元素下 沉,但是它除了第一趟把所有的数据比较了一遍,从第二趟开始,比较的 位置就发生了错误,前面的数据没有比较。 所以答案选 D。例2 冒泡排序在某一遍加工过程中没有数据交换时,说明数据己经有 序,优化程序段如下:
i=1: flag=True
Do While i <=4 And flag=True
flag=False
For j=5 To i+1 Step-1
If a(j) > a(j-1) Then
t=a(j): a(j)=a(j-l): a(j-l)=t flag=True
End If
Next j
i=i+1
Loop
数组元素a(l)到a(5)的值依次为“48, 36, 24,97, 77”,经过该程序段“加 工”后,变量i的值是?( D )
A.1 B.2 C.3 D.4解析 本题解题的关键在于理解变量 flag 的作用。逻辑类型变量 flag 用于标记排序过程中数据是否有过交换,如果有交换,值为 True 否则为 False。变量 i 为排序的趟数,从内循环看是降序排序,从后往前,大的元 素上冒, 因此经过两趟排序后数组 a 中的元素有序,第三趟时 i 初始值 为 3,数据没有交换,但再一次执行了 i=i+1 这一语句,所以 i=4,当 i=4 时, 由于前一趟数据没有交换,flag=False,结束循环。所以答案选 D。1.选择排序的变形:
For i=1 To n-1
k=i
For j=n To i+1 step-1
If a(j)Next j突破二 选择排序的变形
End If
Next i
在每一遍找最小值时,从前往后的比较改为从后往前的比较,其他 没有变化。If k<>i Then
temp=a(i):a(i)=a(k):a(k)=temp2.选择排序的错误变形:
For i=1 To n-1
k=i
For j=i+1 To n
If a(j)Next j
If k<>i Then
temp=a(i):a(i)=a(k):a(k)=temp End If
Next i
错误原因分析:在选择最小值的过程中把第i+1到第n个数依次与a (i)比较,“If a(j)是a(1)的值没有变过。 3.选择排序的优化
在数组的所有元素中同时找出最小和最大的元素,然后将这两个元素
分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最
大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到 所有元素的数据按升序排列。代码如下:
p=1:q=10
Do While p iMin=p:iMax=p For i=p+1 To q
If a(i) If a(i)>a(iMax) Then iMax=i
Next i
t=a(iMin):a(iMin)=a(p):a(p)=t
If iMax=p Then iMax=iMin
t=a(iMax):a(iMax)=a(q):a(q)=t
p=p+1 q=q-1
Loop
思想解析:普通的选择排序是从头到尾一个方向的,优化后的排序 是从两端往中间同时进行的,一端从小到大排,一端从大到小排,变量p和 q表示本次排序的范围(p前和q后的数据已经完成排序)。FOR语句找出 本次排序的最小数a(iMin)和最大数a(iMax),然后将a(iMin)与a(p)交换, 将 a(iMax)与a(q)交换。由于找最小数和最大数时,一开始都假定了p位 置上的数是最小值和最大值,如果本次找到的最大值在p位置,那么当a(p)和a(iMin)交换以后,最大值a(p)就被换到iMin的位置。因此当iMax=p 时,在最小值交换完毕后,再给iMax赋值iMin。例3 有如下VB程序段:
a(l)=44: a(2)=36: a(3)=58: a(4)=65: a(5)=12
b=0
c=0
For i=1 To 4
k=i
For j=i+1 To 5
If a(j) < a(k) Then k=j: b=b+1 Next j
If k <> i Then
t=a(i): a(i)=a(k): a(k)=t
c=c+1
End If
Next i
Text1.Text=Str(b)+Str(c)
该程序段执行后,文本框Text 1显示的内容是?( C ) A.53 B.44 C.43 D.34解析 本题首先要理解变量 b和变量 c的含义。变量 b 表示每趟排序 后面(j)位置上的值有几个数比 k初始位置的值要小,变量 c 表示使用选 择排序完成数据升序需要几次数据交换。
第一趟排序 k=1,初始位置的值为 44,后面有 2 个数比 44 小,找到最小 数后与 44 交换一次。
第二趟排序 k=2,初始位置的值为 36,后面没有数比 36 小,所以数据不 交换。
第三趟排序 k=3,初始位置的值为 58,后面有 1 个数比 58 小,找到并与之交换。
第四趟排序 k=4,初始位置的值为 65,后面的数比 65 小,所以交换。b=4, c=3。 所以答案选C。例4 某排序算法的VB程序段如下:
For i=1 To 4
k=i
For j=5 To i+1 Step-1
If a(j) < a(k) Then k=j
Next j
If k <> i Then
tmp=a(k): a(k)=a(i): a(i)=tmp f(i)=True
End If
Next i
当数组元素a(1)到a(5)的值依次为“8, 2,1,21, 3”,数组f的初值均为 False,执行该程序段,f数组中元素值为True的个数有?( C )
A.1个 B.2个 C.3个 D.4个解析 逻辑类型数组 f(i)用于标记第 i 趟排序时,数组 a 中的元素是否 有过交换。程序实现升序排序,其中 f(1)、f(3)、f(4)的值为 true。 所以 答案选 C。易混易淆
冒泡排序与选择排序例5 数组a共由6个元素构成:49、45、61、46、58、57,经过如下程序 处理后,m和n的值分别为?( )
m=0:n=0
For i=1 To 5
k=i
For j=i+1 To 6
If a(j) < a(k) Then k=j
m=m+1 Next j
If k <> i Then t=a(i): a(i)=a(k): a(k)=t: n=n+1
Next i
A.15,4 B.15,5 C.30,4 D.30,5解析 本题考查选择排序。通过阅读程序可知该程序是实现数组的递 增排序,m存放总的比较次数,n存放数据交换次数。答案????A例6 阅读如下程序段:
Dim flag(4) As Boolean
Dim i As Integer,j As Integer
For i=1 To 4
flag(i)=False
Next i
i=1
Do While i <=4 And flag(i)=False For j=5 To i+1 Step-1
If a(j) < a(j-1) Then
k=a(j): a(j)=a(j-1): a(j-1)=k
flag(i)=True
End If
Next j
i=i+1
Loop数组a中元素依次为“5,4,3,2,1”,该程序执行后,数组flag中值为True的 元素个数是?( C )
A.0 B.2 C.4 D.10解析 本题考查排序的应用。程序中的flag(i)是一个逻辑变量,如果第i 遍有数据交换,则flag(i)=True。分析代码可知该程序采用了冒泡排序, 升序。排序过程如表所示: 因此4次冒泡排序都有数据交换。如果是选择排序,则只有第1遍和 第2遍有数据交换。