学业水平测试信息技术第四部分 专题一.docx
《学业水平测试信息技术第四部分 专题一.docx》由会员分享，可在线阅读，更多相关《学业水平测试信息技术第四部分 专题一.docx（31页珍藏版）》请在冰点文库上搜索。
学业水平测试信息技术第四部分专题一
专题一 排序算法的程序实现
【考纲标准】
考试内容
考试要求
考试属性
选考规律
排序算法的程序实现：
①冒泡排序
②选择排序
c
加试
每次选考1个选择题或1个相关非选择题
1.（2018·4浙江选考）有一组正整数，要求仅对其中的素数进行升序排序。
排序后素数在前，非素数在后。
排序示例如下。
排序前
86
71
5
41
81
79
37
89
排序后
5
37
41
71
79
89
86
81
实现上述功能的VB程序如下，但加框处代码有误，请改正。
Constn＝8
Dima（1Ton）AsInteger
PrivateSubCommand1_Click（）
DimiAsInteger,jAsInteger,kAsInteger,tAsInteger
DimflagAsBoolean
′读取一组正整数，存储在数组a中，代码略
Fori＝1Ton－1
′
（1）
IfIsPrime（a（k））Thenflag＝TrueElseflag＝False
Forj＝i＋1Ton
IfIsPime（a（j））Then
If
Then ′
（2）
k＝j
flag＝True
EndIf
EndIf
Nextj
Ifk<>iThen
t＝a（k）:
a（k）＝a（i）:
a（i）＝t
EndIf
IfNotflagThenExitFor ′ExitFor表示退出循环
Nexti
′依次输出排序后的数据。
代码略
EndSub
FunctionIsPrime（mAsInteger）AsBoolean
′本函数判断m是否是素数：
是素数返回值为True，不是素数返回值为False
′代码略
EndFunction
解析 交换两个数的语句出现在外循环中，说明是选择排序，变量k表示每趟排序中的最值，因此k的初值是i。
题目是要求仅对其中的素数进行升序排序，因此比较的对象a（k）还要求是素数。
答案
（1）k＝i
（2）NotflagOra（j）或NotflagOrflagAnda（j）或NotIsPrime（a（k））OrIsPrime（a（k））Anda（j）2.（2017·11浙江选考）小李基于冒泡排序算法编写一个VB程序，功能如下：
在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。
程序运行界面如下图所示。
实现上述功能的VB代码如下，但加框处代码有错，请改正。
Constn＝10
Dima（1Ton）AsInteger
PrivateSubCommand1_Click（）
DimiAsInteger，jAsInteger，tAsInteger
DimbottomAsInteger ′剔除重复数据后元素的个数
′获取排序前数据依次存储在数组a中，并在文本框Text1中显示。
代码略
bottom＝n
i＝1
DoWhilei<＝bottom－1
Forj＝bottomToi＋1Step－1
If
Then ′
（1）
t＝a（j）：
a（j）＝a（j－1）：
a（j－1）＝t
ElseIfa（j）＝a（j－1）Then′若相邻数据相等，进行剔除处理
′
（2）
bottom＝bottom－1
EndIf
Nextj
i＝i＋1
Loop
Text2.Text＝″ ″
Fori＝1Tobottom
Text2.Text＝Text2.Text＋Str（a（i））
Nexti
EndSub
答案
（1）a（j）a（j） 或其他等价表达式
（2）a（j）＝a（bottom） 或其他等价语句
一、冒泡排序
（一）算法基本思想
冒泡排序法第i遍排序是从第n个数（从后向前比较）或者第1个数（从前向后比较）开始，依次比较相邻的两个数，逆序时交换两个数，把第i个有序的数交换到第i个或者第n－i＋1个位置。
数据的交换是在内层循环中发生。
（二）核心代码
1.将数组a（1ton）从大到小排序，从后向前比较
Fori＝1Ton－1
Forj＝nToi＋1Step－1
Ifd（j－1）t＝d（j）:
d（j）＝d（j－1）：
d（j－1）＝t
Nextj
Nexti
2.将数组a（1ton）从大到小排序，从后向前比较
Fori＝1Ton－1
Forj＝1Ton－i
Ifd（j）t＝d（j）:
d（j）＝d（j＋1）:
d（j＋1）＝t
Nextj
NextI
（三）算法实现过程
1.理解变量i和j的含义
变量i控制排序的趟数，n个数需要通过n－1趟（轮）冒泡；变量j表示比较大小的元素a（j）位置，其中数组元素a（j－1）表示第j－1个位置的数组元素，他位于a（j）的前面第一个元素，a（j＋1）位于a（j）的后面第一个元素。
2.明确排序的方向和每趟排序的初始和结束位置
（1）若内部循环（j的循环）初值大于终值，初值往往是n，表示从后往前向冒泡，找出终值与趟数i的关系，以5个元素从后往前冒泡为例。
趟数
排序
区域
第1次
第2次
第3次
第4次
j终值
比较
次数
有序
区域
j
j－1
j
j－1
j
j－1
j
j－1
i＝1
[1，n]
5
4
4
3
3
2
2
1
2
4
[1，1]
i＝2
[2，n]
5
4
4
3
3
2
/
/
3
3
[1，2]
i＝3
[3，n]
5
4
4
3
/
/
/
/
4
2
[1，3]
i＝4
[4，n]
5
4
/
/
/
/
/
/
5
1
[1，4]
①第i趟冒泡，把最大或最小的元素交换到第i位置，实现从第1个位置到第i个位置的元素有序。
②从上表中发现，每趟排序最后1次比较的位置j（终值）是i＋1；
从后往向前冒泡的初值是n，因此内循环为Forj＝nToi＋1Step－1。
③若第i趟排序过程中，有序的区域往往是[1，i]，但该趟排序中，最后一次交换的位置是j和j－1中，当j－1>i，那么表示区域[i＋1，j－1]没有交换，也是有序的，因此该趟排序的有序区域是[1，j－1]，i的新值为j，而不是i＋1，减少了排序的趟数，达到排序的优化。
（2）若j的初值小于终值，初值往往是1，表示从前往后冒泡。
趟数
排序
区域
第1次
第2次
第3次
第4次
j终值
比较
次数
有序
区域
j
j－1
j
j－1
j
j－1
j
j－1
i＝1
[1，n]
1
2
2
3
3
4
4
5
4
4
[5，5]
i＝2
[1，n－1]
1
2
2
3
3
4
/
/
3
3
[4，5]
i＝3
[1，n－2]
1
2
2
3
/
/
/
/
2
2
[3，5]
i＝4
[1，n－3]
1
2
/
/
/
/
/
/
1
1
[2，5]
①第i趟冒泡，把最大或最小的元素交换到第n－i＋1位置，实现从第n个位置到第n－i＋1个位置的元素有序。
②从上表中发现，每趟排序最后1次比较的位置j（终值）是n－i；
从后往向前冒泡的初值是1，因此内循环为Forj＝1Ton－i。
③若第i趟排序过程中，有序的区域往往是[n－i＋1，n]，但该趟排序中，最后一次交换的位置是j和j＋1中，当j＋1（3）明确交换条件
a（j）a（j）>a（j－1）或a（j＋1）>a（j）指的是当前位置数组元素比该元素前1个位置的元素大。
二、选择排序
（一）算法基本思想
选择排序法第i遍排序是在区域[i，n]之间查找最值所在位置k，并把最值交换到第i个位置，数据的交换一般在外层循环中发生。
（二）核心代码
将数组a（1ton）从大到小排序，往往从前向后比较。
Fori＝1Ton－1
tmax＝i
Forj＝nToi＋1Step－1
Ifa（j）>a（tmax）Then
tmax＝j
Nextj
Iftmax<>iThent＝a（i）:
a（i）＝a（tmax）:
a
（tmax）＝t
Nexti
（三）算法实现过程
1.理解变量i、j和k的含义
变量i控制排序的趟数，n个数需要通过n－1趟（轮）排序；变量j表示比较大小的元素位置，j从i的下1个位置到最后。
k表示每趟中最大或最小数所在位置。
2.比较的方向和步骤
第i趟排序：
让第[i，n]（第i个到第n个之间的数）中，找出一个最大或最小的数，并交换到第i个位置。
3.以5个元素选择排序升序为例。
写出每趟排序的结果。
趟数
排序
区域
k初值
k所在位置的最值与j所在位置的数组元素比较
比较
次数
有序
区域
第1次
第2次
第3次
第4次
j初值
i＝1
[1，n]
1
k→2
k→3
k→4
k→5
2
4
[1，1]
i＝2
[2，n]
2
k→3
k→4
k→5
/
3
3
[1，2]
i＝3
[3，n]
3
k→4
k→5
/
/
4
2
[1，3]
i＝4
[4，n]
4
k→5
/
/
/
5
1
[1，4]
①从上表中“j初值”，找出初值j是i＋1,j的终值为n。
②k初值是i（即k＝i），若某趟比较中，最值发生改变，k＝j，判断最值所在位置k发生移动的语句是If k<>iThen。
③n个数组元素需排序n－1趟；共比较n*（n－1）/2次；数据最多交换n－1次。
三、解题思路
排序的算法常见在选择的第11、12题及第16题的改错中。
往往先把排序算法转换成自然语言，理解算法的思想。
首先从交换语句出现的位置来判断是选择排序还是冒泡排序，内循环交换为冒泡排序，外循环交换为选择排序。
接着再从比较的方向和步骤来理解算法。
【例1】下列关于各种算法的特点描述，正确的是（ ）
A.能用对分查找完成的查找任务，顺序查找也一定能完成
B.能用顺序查找完成的查找任务，对分查找也一定能完成
C.对同一批数据进行升序排序，冒泡排序时数据元素间比较的总次数比选择排序多
D.对同一批数据进行降序排序，冒泡排序时数据元素交换位置的总次数比选择排序少
解析 对分查找要求数列要先有序，选择查找对数列没有要求，所以A正确、B错。
对同一批n个数据，冒泡排序和选择排序都进行n－1次比较，冒泡排序相邻两数依次进行比较，逆序马上交换，交换数据在内层循环中；选择排序是每个数和较大（较小）的数比较，较大（较小）的数放到一个变量中，比较完一遍才进行交换，交换一般在外层循环中，选择排序交换的次数一般比冒泡排序少。
所以C、D错。
答案 A
【例2】有下列VB程序段：
i＝1
DoWhilei<＝2
j＝1
DoWhilej<＝5－i
Ifa（j＋1） t＝a（j）:
a（j）＝a（j＋1）:
a（j＋1）＝t
EndIf
j＝j＋1
Loop
i＝i＋1
Loop数据“36，12，88，11，7”依次存放在数组a
（1）到a（5）中，执行下列程序，数组a
（1）到a（5）数据依次为（ ）
A.7，11，12，36，88B.36，11，7，56，88
C.12，11，7，36,88D.8，11，7，36，788
解析 交换语句在内循环，说明是冒泡排序，共进行2轮（遍）排序，每次总是从第1个数组元素开始，比较到第5－i个数组元素，交换条件是后面元素比他小就交换，说明是升序。
答案 C
【例3】小刘在研究n个数的冒泡排序算法时，发现可以从两个方面进行优化：
（1）在每遍冒泡过程中，若最后一次交换的是last与last－1位置的数，则last－1位置之前的相邻数据均已有序。
进行下一遍冒泡时，无序区域设置为[last，n]。
（2）若在某一遍排序中没有数据交换，说明待排序数据都已经有序，冒泡排序过程可在此遍排序后终止。
小刘按上述方法编写的冒泡优化VB程序，功能如下：
程序运行时生成100个随机整数存入数组a，并显示在列表框List1中。
单击“排序”按钮Command1后，对数组a中的数据进行排序，排序后的数据显示在列表框List2中，排序过程中实际的冒泡遍数显示在标签Label3上。
程序运行界面如图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Dima（1To100）AsInteger
PrivateSubForm_Load（）
′产生100个无重复的三随机整数，存入数组a并显示在列表框list1中
′代码略
EndSub
PrivateSubCommand1_Click（）
DimflagAsBoolean,iAsInteger,jAsInteger
DimtAsInteger,nAsInteger,lastAsInteger
n＝0:
last＝1
flag＝True
DoWhile
′
（1）
flag＝False
For
′
（2）
Ifa（j）>a（j－1）Then
t＝a（j）:
a（j）＝a（j－1）:
a（j－1）＝t
last＝j－1
flag＝True ′有交换发生
EndIf
Nextj
n＝n＋1
Loop
Fori＝1To100
List2.AddItemStr（a（i））
Nexti
Label3.Caption＝″本次排序的冒泡遍数为：
″&Str（n）
EndSub
其中，方框
（1）处应改正为________；
方框
（2）处应改正为________。
解析 交换语句在内循环，为冒泡排序。
flag＝False表示前一遍排序过程中没有数据交换，数据已经有序，此时可以终止排序，因此继续排序的条件应为flag＝True。
内循环从n开始，说明是从后向前比较，比较的范围是[n－i＋1，n]，有序的范围是[1，i]。
按题目描述的优化方法，每遍冒泡的区域为[last，100]（比较对象为a（j）和a（j－1），当终值是last＋1时，比较对象为a（last＋1）和a（last）），Last<100，因此语句Forj＝100Tolast＋1中步长值应为－1，即：
Forj＝100Tolast＋1Step－1。
答案
（1）flag
（2）j＝100tolast－1 Step －1
【例4】（2017·4浙江选考）小赵对选择排序算法进行了如下改进：
在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。
小赵编写的VB程序段如下：
p＝1：
q＝10
DoWhilep iMin＝p：
iMax＝p
Fori＝p＋1Toq
Ifa（i）Ifa（i）>a（iMax）TheniMax＝i
Nexti
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）为找到的最小数，a（iMax）为找到的最大数；最小数a（iMin）和a（p）交换，排到前边，然后最大数a（iMax）和a（q）交换，排到后边，实现升序排列；在每一趟循环中，如果没有方框中的语句，在a（p）恰好为最大数a（iMax）（即imax＝p）时，因为最小数a（iMin）和a（p）先进行交换，交换后a（iMax）会变成最小数，a（iMax）和a（q）再进行交换会把最小数交换到a（q）而出现错误；方框中的语句应为避免这一错误的语句，A正确。
分析程序时可以从待选项中获取线索。
答案 A
考点1 冒泡排序
【训练1】下列关于冒泡排序的叙述，正确的是（ ）
A.10个数冒泡排序每一趟都要进行9次数据比较
B.冒泡排序相邻的数据一定要比较并交换
C.冒泡排序相邻的数据一定要比较，但不一定交换
D.冒泡排序只能从后向前比较
解析 冒泡排序可以从后向前比较，也可以从前向后比较，第i次比较的次数是n－i，因此每次比较的次数是不相等的，是相邻两个数的比较，如果逆序，则交换。
答案 C
【训练2】下表记录了6个数据的排序过程。
分析表中数据可知，该排序采用的算法与排序方式分别为（ ）
原始数据
65
57
59
44
45
69
第1遍
44
65
57
59
45
69
第2遍
44
45
65
57
59
69
第3遍
44
45
57
65
59
69
…
…
…
…
…
…
…
A.冒泡排序，降序B.选择排序，降序
C.冒泡排序，升序D.选择排序，升序
解析 从第1遍排序结果来看，把最小的数放在第1个位置，该数原来在第4个位置，其他数依次后移，因此是冒泡排序。
答案 C
【训练3】有如下部分程序段：
Fori＝1To4
Forj＝5Toi＋1Step－1
Ifa（j）>a（j－1）Thent＝a（j）:
a（j）＝a（j－1）:
a（j－1）＝t
Nextj
List1.Additema（i）
Nexti
a
（1）至a（5）的初值分别为″25″，″18″，″11″，″P″，″n″，该程序段运行后，列表框List1中显示的内容是（ ）
A.11 18 25 n PB.n P 25 18
C.n P 25 18 11D.25 18 11
解析 共进行4轮（遍）排序，每次总是从第5个数组元素开始比较到第i＋1个数组元素，条件a（j）>a（j－1），即比他前面的数大，交换，降序。
但输出语句只循环了4次，列表框只显示了4个值。
数字、大写字母和小写字母的ASCII值依次增大。
答案 B
【训练4】在冒泡排序时，当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。
为此小明对冒泡排序进行了优化，编写了一个VB程序，功能如下，运行程序时，在列表框List1中显示随机产生的n个整数，单击“排序”的按钮Command1，在列表框List2中显示降序排序后的结果，运行的效果如图所示。
实现上述功能的VB代码如下，但加框处代码有错，请改正。
Constn AsInteger＝10
Dima（1Ton）AsInteger
PrivateSubForm_Load（）
′产生n个随机整数并显示在列表框List1中，代码略EndSub
PrivateSubCommand1_Click（）
Dimtmp AsInteger,iAsInteger,jAsInteger,kAsInteger
Fori＝1Ton－1
k＝0
Forj＝
′
（1）
Ifa（j）>a（j－1）Then
a（j－1）＝tmp：
a（j－1）＝a（j）：
a（j）＝tmp
k＝k＋1
EndIf
Nextj
If
Theni＝n ′
（2）
Nexti
Fori＝1Ton
List2.AddItemStr（a（i））
Nexti
EndSub
EndSub
其中，方框
（1）处应改正为________________；
方框
（2）处应改正为________________。
解析 从比较语句来看，比较对象为a（j）和a（j－1），如果从前向后比较，应为2ton－i＋1。
若从后向前比较应为nToi＋1Step－1。
语句k＝k＋1出现在交换语句中，因此变量k表示交换次数，当k＝0时，表示没有交换，退出循环。
语句i＝n起到退出循环的作用。
答案
（1）nToi＋1Step－1或2ton－i＋1
（2）k＝0
考点2 选择排序
【训练5】有一数组，依次为8，4，5，7，9，2。
采用选择排序算法对其进行从大到小排序，则第二趟的排序结果是（ ）
A.987542B.985742
C.985472D.984752
答案 B
【训练6】（2015·9浙江高考模拟）采用如下选择排序算法对数组a中5个数据“23，86，98，65，2”按从小到大的顺序进行排序。
Fori＝1To4
k＝i
Forj＝i＋1To5
Ifa（j）＜a（k）Thenk＝j
Nextj
Ifk＜＞iThen
t＝a（i）：
a（i）＝a（k）：
a（k）＝t
EndIf
Nexti
整个排序过程中，数组中的数据比较次数和交换次
升级会员 