高考专题复习专题七-排序算法的程序实现信息技术.doc

专题七排序算法的程序实现【考纲标准】考试内容考试要求排序算法的程序实现：冒泡排序选择排序c1(20184月浙江选考)有一组正整数，要求仅对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。排序前867154181793789排序后537417179898681实现上述功能的VB程序如下，但加框处代码有误，请改正。Const n 8Dim a(1 To n) As IntegerPrivate Sub Command1_Click()Dim i As Integer, j As Integer, k As Integer, t As IntegerDim flag As Boolean读取一组正整数，存储在数组a中，代码略For i 1 To n 1 (1) If IsPrime(a(k) Then flag True Else flag False For j i 1 To n If IsPime(a(j) ThenIfThen(2) k j flag TrueEnd If End IfNext jIf k i Thent a(k): a(k) a(i): a(i) tEnd IfIf Not flag Then Exit ForExit For表示退出循环Next i依次输出排序后的数据。代码略End SubFunction IsPrime(m As Integer) As Boolean本函数判断m是否是素数：是素数返回值为True，不是素数返回值为False代码略End Function解析交换两个数的语句出现在外循环中，说明是选择排序，变量k表示每趟排序中的最值，因此k的初值是i。题目是要求仅对其中的素数进行升序排序，因此比较的对象a(k)还要求是素数。答案(1)ki(2)Not flag Or a(j) a(k)或Not IsPrime(a(k) Or a(j) a(k)或Not flag Or flag And a(j) a(k)或Not IsPrime(a(k) Or IsPrime(a(k) And a(j) a(k)2(201711月浙江选考)小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。Const n10Dim a(1 To n) As IntegerPrivate Sub Command1_Click()Dim i As Integer，j As Integer，t As IntegerDim bottom As Integer剔除重复数据后元素的个数获取排序前数据依次存储在数组a中，并在文本框Text1中显示。代码略bottomni1Do While ibottom 1For jbottom To i1 Step 1 If Then(1)ta(j)：a(j)a(j1)：a(j1)t ElseIf a(j)a(j1) Then 若相邻数据相等，进行剔除处理(2)bottombottom1 End IfNext jii1LoopText2.Text For i1 To bottomText2.TextText2.TextStr(a(i)Next iEnd Sub解析本题考核从后往前冒泡的算法思想。从后往前冒泡，前面的数据先有序，当两次比较的数据a(j1)和a(j)中相等时，a(j1)可能已经有序，因此用最后一个数据替换a(j)，同时数据的有效长度bottom少1个。答案(1)a(j)a(j)或其他等价表达式(2)a(j)a(bottom)或其他等价语句3(201610月浙江省技术选考)小吴为了研究冒泡排序过程中数据的“移动”情况，编写了一个VB程序，功能如下：在列表框List1中显示排序前数据(存储在数组a中)，在文本框Text1中输入初始位置(即下标值)，单击“排序”按钮Command1后，在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况，排序后的数据显示在列表框List2中。程序运行界面如图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。Dim a(1 To 8) As IntegerDim n As IntegerPrivate Sub Form_Load()a(1)30：a(2)47：a(3)30：a(4)72a(5)70：a(6)23：a(7)99：a(8)24n 8For i 1 To 8List1.AddItem a(i)Next iEnd SubPrivate Sub Command1_Click()Dim i As Integer, j As Integer, k As IntegerDim pos As IntegerDim s As Strings Text1.Textpos Val(Text1.Text)For i 1 To n 1For 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 last j1 flag True有交换发生 End IfNext jn n 1LoopFor i 1 To 100List2.AddItem Str(a(i)Next iLabel3.Caption “本次排序的冒泡遍数为：” & Str(n)End Sub其中，方框(1)处应改正为_；方框(2)处应改正为_。解析flag表示有无交换的标志，如果本趟中没有发生数据的交换，表示数据已经有序，flag True语句出现在交换模块中，有交换还要循环，因此循环的条件是flag True。每趟比较的结束位置是last 1，但从大到小的步长是1。答案(1)flag(2)j100 to last1Step1【例2】 有如下程序段：For i 1 To 5For j 10 To i 2 Step 1 If a(j) a(j 2) Thenta(j)：a(j)a(j2)：a(j2)t End IfNext jNext i数组元素a(1)至a(10)的值分别为“3，17，2，14，15，6，7，18，9，4”，执行该程序段后，数组元素a(8)中的值为()A3 B4 C15 D17解析从比较对象a(j)和a(j2)看，属于奇数位和偶数位分别进行升序排列，每趟有2个数据有序，因此只要进行n2趟排序。偶数位的数据有17,14,6,18,4，升序排列中第2大的数是17。答案D【变式训练1】 有一组正整数，基于冒泡排序对其中的数进行升序排序。排序后奇数在前，偶数在后。排序示例如下排序前783064394948321832 排序后394983481830326478实现上述功能的VB程序如下，但加框处代码有误，请改正。Const n 10Dim d(1 To n) As IntegerPrivate Sub Command1_Click()Dim i As Integer, j As Integer, t As Integer读取一组正整数，存储在数组 d 中，代码略i 1Do While i n 1For j n To i 1 Step 1 If d(j) Mod 2 d(j 1) Mod 2 ThenIf Then(1) t d(j): d(j) d(j 1): d(j 1) tEnd If (2)t d(j): d(j) d(j 1): d(j 1) t End If Next j i i 1Loop依次输出排序后的数据，代码略End Sub解析条件d(j) Mod 2 d(j 1) Mod 2成立，表示相邻两个数都是奇数或都是偶数，相邻两个数进行比较，并且把小的数换到前面。如果是一奇一偶，且偶数在前，要把偶数换到后面。答案(1)a(j)a(j1)(2)ElseIfa(j1) Mod 20Then 考点2从前往后冒泡排序1对称位置：在数组a(1)至a(n)中，有下列数组元素的位置是左右对称的，如a(1)与a(n)，a(2)与a(n1)，a(3)与a(n2)等，两个左右对称数组元素位置的下标之和是一个定值n1，因此可以到结论：与下标为i的数组元素左右对称的位置是ni1。2以n(n5)个元素从前往后冒泡升序排序为例，完成下列表格。趟数排序区间第1次第2次第3次第4次j终值比较次数有序区间jj1jj1jj1jj1i11，n1223344544n，ni21，n112233433n1，ni31，n2122322n2，ni41，n31211n3，n第i趟冒泡，把最大或最小的元素交换到与他左右对称的位置ni1的位置，实现从第ni1个位置到第n个位置的元素有序。数组后面的元素先有序。第i趟排序的区间是1，ni1，因此每趟排序的比较的位置(j的初值)为1。3每趟排序的算法第i趟的排序实现在区间1，ni1中，从第1个位置的数开始，依次与后面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j1)，比较完后向后移动，直到j1的位置到达最后面的位置ni1为止，此时j ni。实现区间ni1，n的数据有序。4每趟排序实现了ni1，n之间的数据有序，因此下趟排序的区间为1，ni。记录第i趟排序最后一次交换的位置j，此时表示j1，n已经有序，下趟排序的区间可以修改为1，j，当j小于ni时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。5核心代码优化前的代码优化后的代码 i 1Do While in1j1Do WhilejniIfa(j)a(j1)Thenta(j)：a(j)a(j1)：a(j1)tEnd Ifjj1Loopii1LoopflagTrue：bottomn1Do WhileflagTruej1：flagFalseDo Whilej bottomIf a(j)a(j1) Thenta(j)：a(j)a(j1)：a(j1)tpt : flag TrueEnd Ifjj1LoopbottompLoop【例3】 小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。实现上述功能的VB程序如下，请将划线处填写完整。Const n 10Dim a(n) As IntegerPrivate Sub Form_Load()产生n个随机数，并显示在文本框Text1中，代码略End SubPrivate Sub Command1_Click()Dim i As Integer, j As Integer, t As IntegerDim top As Integer, s As Stringtop 1: i 1Do While i n 1_Do While j a(j 1) Then t a(j): a(j) a(j 1): a(j 1) tElseIf a(j) a(j 1) Then _ top top 1End Ifj j 1Loopi i 1Loops For i top To ns s Str(a(i)Next iText2.Text sEnd Sub解析从语句Do While j ni来看，属于从前往后冒泡，比较的对象是a(j)和a(j1)，因此数据从后面开始有序，当两个数据是重复时，把开头的数据替换a(j)，继续排序，变量top表示不重复数据的开始位置，j的初值从top开始。 答案j topa(j) a(top)【变式训练2】 小赵对冒泡升序排列算法进行了如下改进：在一趟排序中，同时进行从最后一个元素向前的比较并交换和从第一个元素向后比较并交换，把最小的元素交接到前面，把最大的元素交换到后面，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序如下，但加框处代码有错，请改正。Dim a(8) As Integer, i As IntegerConst n 8Private Sub Command1_Click()Dim j As Integer, start As Integer, last As Integerstart 1: last nDo While start a(i 1) Thent a(i): a(i) a(i 1): a(i 1) tEnd IfNext istart start 1For i start 1 To last 1Ifa(i) a(i 1)Thent a(i): a(i) a(i 1): a(i 1) tEnd IfNext i(2)LoopFor i 1 To nList2.AddItem Str(a(i)Next iEnd SubPrivate Sub Form_Load()产生8个随机数，并显示在列表框List1中，代码略End Sub解析先用从后往前的冒泡排序，将小的数排到前面，再用从前往后冒泡排序的方法，把较大的数排序后面，直到所有数据有序。 答案(1)last To start 1 Step 1 (2)last last 1 考点3选择排序一、排序思想在数据区间i，n范围内，查找最值的位置k，并把该位置的数与第i个数进行交换，使得1，i数据有序，重复执行n1趟。该算法包括两个步骤，一是查找区间i，n中最值位置k，二是交换位置k与位置i上值。二、算法实现1理解变量i、j和k的含义变量i控制排序的趟数，n个数需要通过n1趟(轮)排序；变量j表示比较大小的元素位置，k表示每趟中最大或最小数所在位置。2比较的方向和步骤第i趟排序：在区间i，n中查找最值的位置k。每趟k的初值默认在第i个位置，因此比较的范围在i1，n，每次比较的位置j在最值k的后面。3以5个元素a(1)至a(5)选择排序升序为例。趟数排序区域k初值k所在位置的最值与j所在位置的数组元素比较比较次数有序区域第1次第2次第3次第4次j初值i11，n1k2k3k4k5241，1i22，n2k3k4k5331，2i33，n3k4k5421，3i44，n4k5511，4表示可以看出，第i趟排序的区间是i，n，因此比较位置j每次从i1开始，一直到最后，用最值k所在位置的数a(k)与a(j)，如果a(k)a(j)，将k的值更新为j的值。在比较过程中，只是发生了k值的更新，而没有进行数据交换，即每趟最多只交换了一次。每趟数据是否交换的条件取决于k值是否发生了更新。4冒泡排序与选择排序的区别排序比较对象交换情况冒泡相邻的两个数比较后，逆序即交换，每趟可能交换多次选择最值与待排序区域的数最值与第j个数交换，每趟最多交换一次5.选择排序标准代码(在数组a中，以升序为例进行选择排序)：For i1 To n1n个数共进行n1趟排序Ki 第i趟排序时，首先用k记录iFor ji1 To n k位置上的数依次与j位置上的数进行比较If a(j)a(k) Then kj若找到比k位置上更小的数，则更新k的值Next jIf ki Then 若i位置上的数不是最小数，则和k位置上的数进行互换tempa(i)：a(i)a(k)：a(k)tempEnd IfNext i【例4】 小赵对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：p1：q10Do While p qiMin p：iMax pFor i p 1 To qIf a(i) a(iMax) Then iMaxiNext it a(iMin): a(iMin) a(p): a(p) tt a(iMax): a(iMax) a(q): a(q) tpp1qq1Loop要使程序实现上述算法思想，则方框中的语句是()AIfiMax pTheniMax iMinBIfiMin pTheniMin iMaxCIfiMax pTheniMin iMaxDIfiMin pTheniMax iMin解析该算法是对选择排序算法的改进，由原来的找到最大数(或最小数)后从一个方向排序改为从最小和最大两个方向同时进行排序；每趟排序a(iMin)为找到的最小数，a(iMax) 为找到的最大数；最小数a(iMin)和a(p)交换，排到前边，然后最大数a(iMax)和a(q)交换，排到后边，实现升序排列；在每一趟循环中，如果没有方框中的语句，在a(p)恰好为最大数a(iMax)(即imaxp)时，因为最小数a(iMin)和a(p)先进行交换，交换后a(iMax)会变成最小数，a(iMax)和a(q)再进行交换会把最小数交换到a(q)而出现错误；方框中的语句应为避免这一错误的语句，A正确。分析程序时可以从待选项中获取线索。答案A【变式训练3】 从数据库中读取各考生的编号、笔试和面试成绩，在文本框Text1中输入录取人数，按笔试与面试成绩之和从高到低录取，若成绩之和相等，面试成绩高的排前面。当录取人数达到计划录取人数时，若有面试加笔试的总分与之相等的分数，也要作为录取对象。程序运行的界面如图所示：VB程序代码如下，但加框处的代码有错，请改正。Const n 266Dim ms(n) As Integer, bs(n) As Integer, bh(n) As IntegerPrivate Sub Command1_Click()Dim i As Integer, j As Integer, k As Integer, s As StringFor i 1 To n 1k iFor j i 1 To nIf ms(j) bs(j) ms(k) bs(k) Then k j Then(1) If ms(j) ms(k) Then k jEnd IfNext jIf k i Thent ms(k): ms(k) ms(i): ms(i) tt bs(k): bs(k) bs(i): bs(i) tt bh(k): bh(k) bh(i): bh(i) t End IfNext it Val(Text1.Text)i 1Do While i a(i) Then t a(j): a(j) a(i): a(i) t End If Next jNext i数组元素a(1)到a(5)的值依次为“33，24，45，16，77”，运行程序，数组元素a(1)到a(5)的值依次为()A77，45，33，16，24 B77，33，45，16，24C77，24，45，16，33 D77，45，33，24，16解析该程序段中比较和交换的对象为a(j)和a(i)，因此不属于冒泡算法，可以采用分i1和i2两种情况进行讨论。当i1时，交换77和33，当i2时，交换33和24，再交换33和45。答案A3有如下VB程序段：For i 1 To 2For j 1 To 5iIf a(j1)a(j) Then ta(j)：a(j)a(j1)：a(j1)tNext jNext i数组a(1)到a(5)中数据分别为56，23，78，11，8，执行上述VB程序段后，数组元素的值分别为()A8，11，23，56，78 B23，11，8，56，78C11，8，23，56，78 D8，11，56，23，78解析本题采用从前向后冒泡两趟的算法，a(j1)a(j)成立时交换，表示升序。答案B4有如下程序段：Dim flag(0 To 4) As Boolean, p As IntegerFor i 1 To 4flag(i) FalseNext ii 1: flag(0)TrueDo While i 4 And flag(i1)For j 5 To i 1 Step 1If a(j) a(j 1) Then ka(j)：a(j)a(j1)：a(j1)kEnd IfNext jNext i数组元素a(1)到a(6)的值依次为“71，54，58，29，31，78”，运行程序，下列说法正确的是()A数组元素a(1)到a(6)的值依次为54，29，31，58，71，78B此过程中数据共需比较次数为8次C此过程中数据共需交换次数为5次D此过程中数据“54”共被比较5次解析该程序采用从前往后冒泡两次的算法的变式，比较对象是a(j)和a(j1)，但j的初值是2。条件a(j) a(j 1)成立表示后面的比前面大交换，降序。比较次数为549次。交换次数为：第1趟，54和58，29分别和31、78交换，第2趟，31和78交换。答案D6有如下部分程序段：a(1) ”20”： a(2) ”16”： a(3) ”12”： a(4) ”o”： a(5) ”k”For i 1 To 4 For j 5 To i 1 Step 1 Ifa(j)a(j1)Thenta(j)：a(j)a(j1)：a(j1)t Next j List1.Additem a(i)Next i该程序段运行后，列表框List1中显示的内容为()A12，16，20，o，k Bo，k，20，16Co，k，20，16，12 D20，16，解析在字符比较中，先从左边第1个字符开始比较，数字小于大写字母小于小写字母，如果前面的字符相等，再继续往后比较。采用的是从后往前冒泡排序，但只显示前面4个数组元素。答案B7有如下VB程序段：s ”For i 1 To 3For j 1 To 10 i If d(j) d(j 1) Then ttd(j)：d(j)d(j1)：d(j1)tt End IfNext js s Str(d(i)Next itext1.Text s数组元素d(1)到d(10)的值分别是91、28、83、62、64、36、9、65、37、99，经过该程序段“加工”后，文本框Text1中显示的内容为()A92837