资源简介

教师备用题库
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遍有数据交换。

展开更多......

收起↑