排序算法的程序实现（教师版）
1.有如下程序段:
For i = 1 To 2
For j = 5 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(5)的值依次为“33,24,45,16,77”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为( )
A.77,45,33,16,24 B.77,33,45,16,24
C.77,24,45,16,33 D.77,45,33,24,16
答案 A
解析 这是一个选择排序,其排序思想是:在i遍排序中,从最后一个元素开始到第i+1个元素依次和第i号元素比较,如果有比i号元素大的立刻交换,并且记录元素下标,一遍全部比较结束后再交换进行下一轮。
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
答案 A
解析 如果找到的最小值的元素序号iMin=q,最大值的元素序号iMax=p,那么在执行完语句t = a(iMin): a(iMin) = a(p): a(p) = t后,实际上最大值同时也被交换到了a(q)中。这种情况下,如果直接执行后续的语句t = a(iMax): a(iMax) = a(q): a(q) = t,则又将最大值交换到a(p)中,并把最小值也换回到原来的a(q)中。为避免交换好的数据换回来,可以把iMax的值赋为q或iMin,如此t = a(iMax): a(iMax) = a(q): a(q) = t语句就变成了自己和自己交换,不会把交换好的数据换回来。
3.有如下VB程序段:
Dim s(1 To 6) As String
s(1)=″4″:s(2)=″343″:s(3)=″312″:s(4)=″12″:s(5)=″246:s(6)=″121″
c=″ ″
For i=1 To 5
For j=i+1 To 6
If s(i)+s(j)
t=s(j):s(j)=s(i):s(i)=t
End If
Next j
c=c+s(i)
Next i
Text1.text=c
运行该段代码后,文本框Text1中显示的内容为( )
A.343312246121124
B.434331224612112
C.434331224612121
D.121122463123434
答案C
该程序段采用选择排序法对字符类型的数据进行排序。字符串大小的比较方法是:先比较第1个字符,若不同,ASCII大的一方字符串值较大,之后不用再比较;若相同,则比较第2个。例如:″4″>″345″,″4366″<″451″。根据代码s(i)+s(j)4.有如下VB程序段:
For i = 5 To 4 Step -1
k = i
For j = 6 - i To 1 Step-1
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(5)的值依次为“41,66,70,83,31”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为 ( )
A.31,41,66,83,70 B.83,70,66,41,31
C.83,66,70,41,31 D.31,41,66,70,83
答案C
第一遍循环,i=5,k=5,内循环为j=1 to 1只执行1次,比较a(1)5.有如下程序段:
bottom=6: i=1: r=Val(Text1.Text)
Do While iFor j=bottom 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
i=i+1
For j=i To bottom -1
If a(j)t=a(j):a(j)=a(j+1):a(j+1)=t
End If
Next j
bottom=bottom-1
Loop
数组元素a(1)到a(6)的值依次为“73、56、28、61、44、92”,若在文本框Text1中输入“2”,则经过该程序段“加工”后,数组元素a(1)到a(6)的值依次为( )
A.73,61,56,92,44,28
B.92,73,56,61,44,28
C.92,73,61,56,28,44
D.92,73,61,56,44,28
答案B
本题是双向冒泡排序算法,内循环前半部分从后往前,将大的元素往上冒;后半部分从前往后,将小的元素往下沉。因为r值为2,所以仅排序一次,排序后数组a各元素值为92、73、56、61、44、28。
6.n个数据的冒泡升序排序需要经过n-1遍的加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面,在第i遍加工过程中需要进行n-i对数据的比较。在某些情况下,第i遍加工过程中,在上面部分较小数据已经有序情况下,不需要再进行n-i对数据的比较。如对“17,18,19,24,23,20”这6个数据排序中,第1遍排序结束后数据为“17,18,19,20,24,23”,第2遍排序时不再需要对20及其前面共4个数据进行比较。以下程序实现了冒泡升序排序的优化,在划线处填入合适的代码。
Dim n As Integer
Dim a(1 To 100) As Integer
'n=10,排序前生成的数据存储在数组a中,并在列表框List1中显示,代码略
Private Sub Command1_Click()
Dim i As Integer,j As Integer,start As Integer,t As Integer
i=2
Do While i<=n
start=n
For j=n To i Step-1
If ① Then
t=a(j):a(j)=a(j-1):a(j-1)=t
②
End If
Next j
i=start+1
Loop
For i=1 To n
List2.AddItem= ③
Next i
End Sub
答案 ①a(j)解析 程序要实现升序排序,所以只有当后面的数据小于前面的数据时才需要数据交换,而从后面交换的语句中可以看出是a(j)与a(j-1)交换,所以第①空填a(j)7.用VB小程序统计文章中字母出现的频率,程序功能如下:在文本框text1中输入文章,单击按钮command1,在列表框list1中按各字母出现的次数降序显示,程序运行界面如下图所示。
实现上述功能的VB程序如下。请在划线处填入合适代码。
Private Sub Command1_Click()
Dim s As String,t1 As Integer,t2 As String
Dim i As Integer,j As Integer,c As String
Dim a(1 To 26) As Integer '数组a存放字母出现次数
Dim b(1 To 26) As String '数组b存放26个小写字母
For i=1 To 26
a(i)=0
b(i)= ①
Next i
s=Text1.Text
For i=1 To Len(s)
c=Mid(s,i,1)
If c>=″A″ And c<=″Z″ Then
c=Chr(Asc(c)+32)
End If
If c>=″a″ And c<=″z″ Then
②
a(j)=a(j)+1
End If
Next i
For i=1 To 25
For j=1 To ③
If a(j) t1=a(j):a(j)=a(j+1):a(j+1)=t1
t2=b(j):b(j)=b(j+1):b(j+1)=t2
End If
Next j
Next i
For i=1 To 26
List1.AddItem b(i) &″:″ & a(i)
Next i
End Sub
答案 ①Chr(Asc(″a″)+i-1) ②j=Asc(c)-Asc(″a″)+1 ③26-i
解析 ①该语句所在循环功能对数组a、b进行初始化,把数组a中的每个元素赋值为0,把数组b中的每个元素依次赋值为“a”、“b”、“c”、……、“z”,所以①处填Chr(Asc(″a″)+i-1)。
②该处的功能是:如果取出字符c为字母,则该字母个数加1,字母个数存入数组a对应的元素中,即a(1)存放字母“a”的个数,a(2)存放字母“b”的个数……,②处要找出字母对应的元素下标j,所以j=Asc(c)-Asc(″a″)+1。
③该处二重循环的功能是对保存在数组a中各字母出现的次数进行降序排列,数组b也作相应调整,排列使用冒泡法,每次是从数组第1个元素开始进行两两比较,通过一轮循环把最小值移到最后(移到第27-i号元素中),所以③处语句为26-i。排序算法的程序实现（学生版）
1.有如下程序段:
For i = 1 To 2
For j = 5 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(5)的值依次为“33,24,45,16,77”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为( )
A.77,45,33,16,24 B.77,33,45,16,24
C.77,24,45,16,33 D.77,45,33,24,16
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
3.有如下VB程序段:
Dim s(1 To 6) As String
s(1)=″4″:s(2)=″343″:s(3)=″312″:s(4)=″12″:s(5)=″246:s(6)=″121″
c=″ ″
For i=1 To 5
For j=i+1 To 6
If s(i)+s(j) t=s(j):s(j)=s(i):s(i)=t
End If
Next j
c=c+s(i)
Next i
Text1.text=c
运行该段代码后,文本框Text1中显示的内容为( )
A.343312246121124
B.434331224612112
C.434331224612121
D.121122463123434
4.有如下VB程序段:
For i = 5 To 4 Step -1
k = i
For j = 6 - i To 1 Step-1
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(5)的值依次为“41,66,70,83,31”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为 ( )
A.31,41,66,83,70 B.83,70,66,41,31
C.83,66,70,41,31 D.31,41,66,70,83
5.有如下程序段:
bottom=6: i=1: r=Val(Text1.Text)
Do While iFor j=bottom 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
i=i+1
For j=i To bottom -1
If a(j)t=a(j):a(j)=a(j+1):a(j+1)=t
End If
Next j
bottom=bottom-1
Loop
数组元素a(1)到a(6)的值依次为“73、56、28、61、44、92”,若在文本框Text1中输入“2”,则经过该程序段“加工”后,数组元素a(1)到a(6)的值依次为( )
A.73,61,56,92,44,28
B.92,73,56,61,44,28
C.92,73,61,56,28,44
D.92,73,61,56,44,28
6.n个数据的冒泡升序排序需要经过n-1遍的加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面,在第i遍加工过程中需要进行n-i对数据的比较。在某些情况下,第i遍加工过程中,在上面部分较小数据已经有序情况下,不需要再进行n-i对数据的比较。如对“17,18,19,24,23,20”这6个数据排序中,第1遍排序结束后数据为“17,18,19,20,24,23”,第2遍排序时不再需要对20及其前面共4个数据进行比较。以下程序实现了冒泡升序排序的优化,在划线处填入合适的代码。
Dim n As Integer
Dim a(1 To 100) As Integer
'n=10,排序前生成的数据存储在数组a中,并在列表框List1中显示,代码略
Private Sub Command1_Click()
Dim i As Integer,j As Integer,start As Integer,t As Integer
i=2
Do While i<=n
start=n
For j=n To i Step-1
If ① Then
t=a(j):a(j)=a(j-1):a(j-1)=t
②
End If
Next j
i=start+1
Loop
For i=1 To n
List2.AddItem= ③
Next i
End Sub
7.用VB小程序统计文章中字母出现的频率,程序功能如下:在文本框text1中输入文章,单击按钮command1,在列表框list1中按各字母出现的次数降序显示,程序运行界面如下图所示。
实现上述功能的VB程序如下。请在划线处填入合适代码。
Private Sub Command1_Click()
Dim s As String,t1 As Integer,t2 As String
Dim i As Integer,j As Integer,c As String
Dim a(1 To 26) As Integer '数组a存放字母出现次数
Dim b(1 To 26) As String '数组b存放26个小写字母
For i=1 To 26
a(i)=0
b(i)= ①
Next i
s=Text1.Text
For i=1 To Len(s)
c=Mid(s,i,1)
If c>=″A″ And c<=″Z″ Then
c=Chr(Asc(c)+32)
End If
If c>=″a″ And c<=″z″ Then
②
a(j)=a(j)+1
End If
Next i
For i=1 To 25
For j=1 To ③
If a(j) t1=a(j):a(j)=a(j+1):a(j+1)=t1
t2=b(j):b(j)=b(j+1):b(j+1)=t2
End If
Next j
Next i
For i=1 To 26
List1.AddItem b(i) &″:″ & a(i)
Next i
End Sub