教科版 信息技术 必修 3.2 排序算法的程序实现课件（共26张ppt)

课件26张PPT。第二章　排序算法的程序实现-2--3-考点1考点2冒泡排序
冒泡排序的基本思想是把待排序的n个元素看成垂直堆放的一列数据,从最下面的一个元素起,自下而上地比较相邻的两个元素的数据,将较小的数据换到上面的一个元素中。重复这一过程,直到处理完最后两个数,称为第一遍加工。当第一遍加工完成后,最小(大)的数已经上升到第一个元素的位置。然后对余下的n-1个数重复上述过程,经过n-1遍处理以达到排序目的的一种排序方法。冒泡排序最多需要比较和交换的次数是-4-考点1考点2常用的冒泡排序程序结构:
升序方式冒泡排序的程序段
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 - 1) = t
End If
　Next j
Next i
提示在降序方式中,If语句中条件表达式为a(j)>a(j-1)。-5-考点1考点2【例1】有如下VB程序段:
s=″　″
For i = 1 To 3
For j = 6 To i + 1 Step -1
　　If a(j) > a(j-1) Then
　　　 k=a(j):a(j)=a(j-1):a(j-1)=k
　　End If
Next j
s = s + str(a(i))
Next i
Text1.Text=str(s)
数组元素从a(1)到a(6)的数据依次为“3、7、2、5、8、9”,经过该程序“加工”后,文本框Text1中显示的是(　　)
A.2　3　5 B.9　8　7 C.3　7　2 D.7　3　2-6-考点1考点2答案:B
解析:观察程序可知,内循环中每次都是对相邻的数据进行比较,把较大数交换到上面,所以该算法属于升序型冒泡排序。外循环3遍,表明排序3遍。可用列表方式模拟冒泡排序的过程。
其次,每一遍排序完之后都将对应的a(i)以字符串的形式加入到字符串变量s中,每加一次在两个数之间都会产生一个空格,最终s的结果是:9　8　7。-7-考点1考点2选择排序
选择排序算法的基本思想是在待排序的数据中选出最小(大)的数据,把它与第1个位置的数据交换,然后在其余的数据中再选出最小(大)的数据与第2个数据交换,依此类推,直到所有的数据排序完成。选择排序最多需要比较的次数是
最多需要交换的次数是n-1。
常用的选择排序程序结构:-8-考点1考点2升序方式选择排序的程序段
For i = 1 To n-1
　k=i
　For j =i+1 To n
If a(j) < a(k) Then k=j
　Next j
If　k<>i then
t = a(i): a(i) = a(k): a(k) = t
End If
Next i
提示在降序方式中,If语句中表达式为a(j)>a(k)。-9-考点1考点2【例2】 某学校举行校园歌手比赛,数组a存放歌手的得分,数组mc存放名次。名次计算规则为:分值最高为第1名,分值相同则名次相同。VB程序段的部分代码如下:
For i=1 To n-1
k=i
For j=i+1 To n
If 　①　 Then k=j?
Next j
If k<>i then t=a(k):a(k)=a(i):a(i)=t
If i=1 then
mc(1)=1　'数组元素mc(i)存放i号歌手的名次
Else
If a(i)<>a(i-1) Then 　②　 Else 　③　?
End if
Next i-10-考点1考点2答案:①a(j)>a(k)　②mc(i)=i　③mc(i)=mc(i)-1
解析:代码段采用了选择排序算法。根据题意,分值最高为第1名,并由语句mc(1)=1可知,a(1)应是最高分,说明应是对数组降序排序,故①处填a(j)>a(k)。在第i遍排序完成后,该遍中最大数已存入a(i)中,然后计算a(i)的名次。如果i=1,即最高分者为第1名,所以mc(1)=1;否则如果a(i)<>a(i-1),那么第i位歌手的名次是mc(i)=i,如果a(i)=a(i-1),表示当前歌手的得分和前一位相同,则其名次也应与前者相同,即mc(i)=mc(i)-1。-11-123456781.有以下VB程序段
For i = 1 To 2
　For j = 1 To 5-i
If d(j) > d(j +1)Then
　t = d(j):d(j) = d(j +1):d(j +1) = t
End If
　Next j
Next i
数组元素a(1)到a(5)的值依次为“48,36,78,18,15”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为 (　　)
A.36,15,18,48,78 B.36,18,15,48,78
C.15,18,36,48,78 D.15,18,48,36,78 答案解析-12-123456782.有如下程序段:
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-13-12345678End 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 答案解析-14-123456783.有如下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-15-12345678运行该段代码后,文本框Text1中显示的内容为(　　)
A.343312246121124
B.434331224612112
C.434331224612121
D.121122463123434 答案解析-16-123456784.有如下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-17-12345678数组元素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 答案解析-18-123456785.冒泡排序在某一遍加工过程中没有数据交换时,说明数据已经有序,优化程序段如下:
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-1):a(j-1)=t
flag=True
End If
Next j
i=i+1
Loop-19-12345678数组元素a(1)到a(5)的值依次为“48,36,24,97,77”,经过该程序段“加工”后,变量i的值是(　　)
A.1 B.2 C.3 D.4 答案解析-20-123456786.有如下程序段:
i=1
Do While i<=5
If i=0 or a(i-1)<=a(i) Then
i=i+1
Else
t=a(i):a(i)=a(i-1):a(i-1)=t
i=i-1
End If
Loop
数组元素a(0)到a(5)的值依次为“0,71,22,48,79,27”,经过该程序段“加工”后,数组元素a(4)的值为(　　)
A.0 B.71 C.48 D.27 答案解析-21-123456787.(2018·11浙江选考)下列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-22-12345678If (3) Then
　　y(j)=y(j)+1
Else
　　y(i)=y(i)+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) 答案解析-23-123456788.(2018·4浙江学考)有一组正整数,要求供对其中的素数进行升序排序。排序后素数在前,非素数在后。排序示例如下。
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中,代码略-24-12345678For i=1 To n-1
k=1　'①
If IsPrime(a(k)) Then flag=True Else flag=False
For j=i+1 To n
If IsPime(a(j)) Then
　　If a(j)　　　　k=j
　　　　flag=True
　　End If
End If-25-12345678Next 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-26-12345678答案: ①k=i　②Not flag Or a(j)解析: 本题利用选择排序思想,变量k记录最小素数元素的下标。第1趟找出所有素数中的最小值,交换到第1个位置。第i趟找出所有素数中的最小值,交换到第i个位置。每一趟开始前都假设第i个元素最小,然后通过内循环找出后面更小的。
变量flag用于标记每一趟的第1个元素是否为素数。如果第1个元素不是素数,内循环找到的第一个素数作为基点,k记录第一素数位置。如果素数已经出现过(flag值为True),则该素数需要和之前的素数比较大小,当前素数更小的话则更新k的值。所以这一空的答案为Not flag Or a(j)