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

专题七排序算法的程序实现【考纲标准】考试内容考试要求排序算法的程序实现：①冒泡排序②选择排序c1．(2018·4月浙江选考)有一组正整数，要求仅对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。排序前867154181793789排序后537417179898681实现上述功能的VB程序如下，但加框处代码有误，请改正。Constn＝8Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsInteger,tAsIntegerDimflagAsBoolean′读取一组正整数，存储在数组a中，代码略Fori＝1Ton－1eq\x(k＝1)′(1)IfIsPrime(a(k))Thenflag＝TrueElseflag＝FalseForj＝i＋1TonIfIsPime(a(j))ThenIfeq\x(a（j）<a（k）)Then′(2)k＝jflag＝TrueEndIfEndIfNextjIfk<>iThent＝a(k):a(k)＝a(i):a(i)＝tEndIfIfNotflagThenExitFor′ExitFor表示退出循环Nexti′依次输出排序后的数据。代码略EndSubFunctionIsPrime(mAsInteger)AsBoolean′本函数判断m是否是素数：是素数返回值为True，不是素数返回值为False′代码略EndFunction解析交换两个数的语句出现在外循环中，说明是选择排序，变量k表示每趟排序中的最值，因此k的初值是i。题目是要求仅对其中的素数进行升序排序，因此比较的对象a(k)还要求是素数。答案(1)k＝i(2)NotflagOra(j)<a(k)或NotIsPrime(a(k))Ora(j)<a(k)或NotflagOrflagAnda(j)<a(k)或NotIsPrime(a(k))OrIsPrime(a(k))Anda(j)<a(k)2．(2017·11月浙江选考)小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。Constn＝10Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger，jAsInteger，tAsIntegerDimbottomAsInteger′剔除重复数据后元素的个数′获取排序前数据依次存储在数组a中，并在文本框Text1中显示。代码略bottom＝ni＝1DoWhilei<＝bottom－1Forj＝bottomToi＋1Step－1Ifeq\x(a（j）<a（i）)Then′(1)t＝a(j)：a(j)＝a(j－1)：a(j－1)＝tElseIfa(j)＝a(j－1)Then′若相邻数据相等，进行剔除处理eq\x(a（bottom）＝a（j）)′(2)bottom＝bottom－1EndIfNextji＝i＋1LoopText2.Text＝""Fori＝1TobottomText2.Text＝Text2.Text＋Str(a(i))NextiEndSub解析本题考核从后往前冒泡的算法思想。从后往前冒泡，前面的数据先有序，当两次比较的数据a(j－1)和a(j)中相等时，a(j－1)可能已经有序，因此用最后一个数据替换a(j)，同时数据的有效长度bottom少1个。答案(1)a(j)<a(j－1)或a(j－1)>a(j)或其他等价表达式(2)a(j)＝a(bottom)或其他等价语句3．(2016·10月浙江省技术选考)小吴为了研究冒泡排序过程中数据的“移动”情况，编写了一个VB程序，功能如下：在列表框List1中显示排序前数据(存储在数组a中)，在文本框Text1中输入初始位置(即下标值)，单击“排序”按钮Command1后，在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况，排序后的数据显示在列表框List2中。程序运行界面如图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。Dima(1To8)AsIntegerDimnAsIntegerPrivateSubForm_Load()a(1)＝30：a(2)＝47：a(3)＝30：a(4)＝72a(5)＝70：a(6)＝23：a(7)＝99：a(8)＝24n＝8Fori＝1To8List1.AddItema(i)NextiEndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsIntegerDimposAsIntegerDimsAsStrings＝Text1.Textpos＝Val(Text1.Text)Fori＝1Ton－1Forj＝nToi＋1Step－1Ifa(j)<a(j－1)Theneq\x(k＝a（j）)′(1)a(j－1)＝a(j)a(j)＝k′如果pos位置的数据参与交换，则更新pos值，记录pos变化位置Ifpos＝jThenpos＝j－1s＝s＋”→”＋Str(pos)eq\x(Else)′(2)pos＝js＝s＋”→”＋Str(pos)EndIfEndIfNextjNextiLabel1.Caption＝“位置变化情况：”＋sFori＝1TonList2.AddItemStr(a(i))NextiEndSub解析第一处改错实现的是两个变量的交换。交换变量a(j)和a(j－1)的值后，该两个元素数据位置发生变化，接下来判断这两个元素的下标是否和pos相同，如果pos和j相同，已经被交换到j－1位置，pos需要更新，否则如果pos和j－1相同，已经被交换到j位置，pos需要更新。答案(1)k＝a(j－1)(2)ElseIfpos＝j－1Then1．排序的作用是把n个数据从小到大或从大到小重新排列，使得a(1)至a(n)中的数据有序。排序的方法有很多，重点掌握冒泡排序和选择排序。2．n个数据一般需要经过n－1趟排序，变量i控制排序的趟数。第i趟的比较次数往往有n－i次。3．变量j表示比较大小的元素位置，其中数组元素a(j－1)表示第j－1个位置的数组元素，他位于a(j)的前面第一个元素，a(j＋1)位于a(j)的后面第一个元素。4．内部循环(j的循环)初值和终值决定了排序的区间和方向。如果初值大于终值，初值往往是n，表示从后往前向后排序，若j的初值小于终值，初值往往是1，表示从前往后排序。考点1从后往前冒泡排序1．以n(n＝5)个元素从后往前冒泡升序排序为例，完成下列表格。趟数排序区间第1次第2次第3次第4次j终值比较次数有序区间jj－1jj－1jj－1jj－1i＝1[1，n]5443322124[1，1]i＝2[2，n]54433233[1，2]i＝3[3，n]544342[1，3]i＝4[4，n]5451[1，4]①第i趟冒泡，把最大或最小的元素交换到第i位置，实现从第1个位置到第i个位置的元素有序。数组前面的元素先有序。②第i趟排序的区间是[i，n]，因此每趟排序的比较的位置(j的初值)为n。2．每趟排序的算法第i趟的排序实现在区间[i，n]中，从第n个位置的数开始，依次与前面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j－1)，比较完后向前移动，直到j－1的位置到达最前面的位置i为止，此时j＝i＋1。实现区间[1，i]的数据有序。3．若每趟交换的次数为0，表示所有数据均有序，可以提前结束排序算法。也可以记flag的状态为False，若发生交换，将flag的值修改为True，根据flag的值，也可以表示数据是否有序。4．每趟排序实现了[1，i]之间的数据有序，因此下趟排序的区间为[i＋1，n]。记录第i趟排序最后一次交换的位置j，此时表示[1，j－1]已经有序，下趟排序的区间可以修改为[j，n]，当j大于i＋1时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。5．核心代码【例1】小刘在研究n个数的冒泡排序算法时，发现可以从两个方面进行优化：(1)在每遍冒泡过程中，若最后一次交换的是last与last－1位置的数，则last－1位置之前的相邻数据均已有序。进行下一遍冒泡时，无序区域设置为[last，n]。(2)若在某一遍排序中没有数据交换，说明待排序数据都已经有序，冒泡排序过程可在此遍排序后终止。小刘按上述方法编写的冒泡优化VB程序，功能如下：程序运行时生成100个随机整数存入数组a，并显示在列表框List1中。单击“排序”按钮Command1后，对数组a中的数据进行排序，排序后的数据显示在列表框List2中，排序过程中实际的冒泡遍数显示在标签Label3上。程序运行界面如图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。Dima(1To100)AsIntegerPrivateSubForm_Load()′产生100个无重复的三随机整数，存入数组a并显示在列表框list1中′代码略EndSubPrivateSubCommand1_Click()DimflagAsBoolean,iAsInteger,jAsIntegerDimtAsInteger,nAsInteger,lastAsIntegern＝0:last＝1flag＝TrueDoWhileeq\x(flag＝False)′(1)flag＝FalseForeq\x(j＝100Tolast＋1)′(2)Ifa(j)>a(j－1)Thent＝a(j):a(j)＝a(j－1):a(j－1)＝tlast＝j－1flag＝True′有交换发生EndIfNextjn＝n＋1LoopFori＝1To100List2.AddItemStr(a(i))NextiLabel3.Caption＝“本次排序的冒泡遍数为：”&Str(n)EndSub其中，方框(1)处应改正为________；方框(2)处应改正为________。解析flag表示有无交换的标志，如果本趟中没有发生数据的交换，表示数据已经有序，flag＝True语句出现在交换模块中，有交换还要循环，因此循环的条件是flag＝True。每趟比较的结束位置是last＋1，但从大到小的步长是－1。答案(1)flag(2)j＝100tolast－1Step－1【例2】有如下程序段：Fori＝1To5Forj＝10Toi＋2Step－1Ifa(j)<a(j－2)Thent＝a(j)：a(j)＝a(j－2)：a(j－2)＝tEndIfNextjNexti数组元素a(1)至a(10)的值分别为“3，17，2，14，15，6，7，18，9，4”，执行该程序段后，数组元素a(8)中的值为()A．3 B．4 C．15 D．17解析从比较对象a(j)和a(j－2)看，属于奇数位和偶数位分别进行升序排列，每趟有2个数据有序，因此只要进行n\2趟排序。偶数位的数据有17,14,6,18,4，升序排列中第2大的数是17。答案D【变式训练1】有一组正整数，基于冒泡排序对其中的数进行升序排序。排序后奇数在前，偶数在后。排序示例如下排序前783064394948321832排序后394983481830326478实现上述功能的VB程序如下，但加框处代码有误，请改正。Constn＝10Dimd(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,tAsInteger′读取一组正整数，存储在数组d中，代码略i＝1DoWhilei<＝n－1Forj＝nToi＋1Step－1Ifd(j)Mod2＝d(j－1)Mod2ThenIfeq\x(d（j）>d（i）)Then′(1)t＝d(j):d(j)＝d(j－1):d(j－1)＝tEndIfeq\x(Else)′(2)t＝d(j):d(j)＝d(j－1):d(j－1)＝tEndIfNextji＝i＋1Loop′依次输出排序后的数据，代码略EndSub解析条件d(j)Mod2＝d(j－1)Mod2成立，表示相邻两个数都是奇数或都是偶数，相邻两个数进行比较，并且把小的数换到前面。如果是一奇一偶，且偶数在前，要把偶数换到后面。答案(1)a(j)<a(j－1)(2)ElseIfa(j－1)Mod2＝0Then考点2从前往后冒泡排序1．对称位置：在数组a(1)至a(n)中，有下列数组元素的位置是左右对称的，如a(1)与a(n)，a(2)与a(n－1)，a(3)与a(n－2)等，两个左右对称数组元素位置的下标之和是一个定值n＋1，因此可以到结论：与下标为i的数组元素左右对称的位置是n－i＋1。2．以n(n＝5)个元素从前往后冒泡升序排序为例，完成下列表格。趟数排序区间第1次第2次第3次第4次j终值比较次数有序区间jj＋1jj＋1jj＋1jj＋1i＝1[1，n]1223344544[n，n]i＝2[1，n－1]12233433[n－1，n]i＝3[1，n－2]122322[n－2，n]i＝4[1，n－3]1211[n－3，n]①第i趟冒泡，把最大或最小的元素交换到与他左右对称的位置n－i＋1的位置，实现从第n－i＋1个位置到第n个位置的元素有序。数组后面的元素先有序。②第i趟排序的区间是[1，n－i＋1]，因此每趟排序的比较的位置(j的初值)为1。3．每趟排序的算法第i趟的排序实现在区间[1，n－i＋1]中，从第1个位置的数开始，依次与后面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j＋1)，比较完后向后移动，直到j＋1的位置到达最后面的位置n－i＋1为止，此时j＝n－i。实现区间[n－i＋1，n]的数据有序。4．每趟排序实现了[n－i＋1，n]之间的数据有序，因此下趟排序的区间为[1，n－i]。记录第i趟排序最后一次交换的位置j，此时表示[j＋1，n]已经有序，下趟排序的区间可以修改为[1，j]，当j小于n－i时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。5．核心代码优化前的代码优化后的代码i＝1DoWhilei<＝n－1j＝1DoWhilej<＝n－iIfa(j)<a(j＋1)Thent＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝tEndIfj＝j＋1Loopi＝i＋1Loopflag＝True：bottom＝n－1DoWhileflag＝Truej＝1：flag＝FalseDoWhilej<＝bottomIfa(j)<a(j＋1)Thent＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝tp＝t:flag＝TrueEndIfj＝j＋1Loopbottom＝pLoop【例3】小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。实现上述功能的VB程序如下，请将划线处填写完整。Constn＝10Dima(n)AsIntegerPrivateSubForm_Load()′产生n个随机数，并显示在文本框Text1中，代码略EndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,tAsIntegerDimtopAsInteger,sAsStringtop＝1:i＝1DoWhilei<＝n－1____①____DoWhilej<＝n－iIfa(j)>a(j＋1)Thent＝a(j):a(j)＝a(j＋1):a(j＋1)＝tElseIfa(j)＝a(j＋1)Then____②____top＝top＋1EndIfj＝j＋1Loopi＝i＋1Loops＝""Fori＝topTons＝s＋Str(a(i))NextiText2.Text＝sEndSub解析从语句DoWhilej<＝n－i来看，属于从前往后冒泡，比较的对象是a(j)和a(j＋1)，因此数据从后面开始有序，当两个数据是重复时，把开头的数据替换a(j)，继续排序，变量top表示不重复数据的开始位置，j的初值从top开始。答案①j＝top②a(j)＝a(top)【变式训练2】小赵对冒泡升序排列算法进行了如下改进：在一趟排序中，同时进行从最后一个元素向前的比较并交换和从第一个元素向后比较并交换，把最小的元素交接到前面，把最大的元素交换到后面，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序如下，但加框处代码有错，请改正。Dima(8)AsInteger,iAsIntegerConstn＝8PrivateSubCommand1_Click()DimjAsInteger,startAsInteger,lastAsIntegerstart＝1:last＝nDoWhilestart<lastFori＝eq\x(last－1Tostart)′(1)Ifa(i)>a(i－1)Thent＝a(i):a(i)＝a(i－1):a(i－1)＝tEndIfNextistart＝start＋1Fori＝start＋1Tolast－1Ifa(i)<a(i＋1)Thent＝a(i):a(i)＝a(i＋1):a(i＋1)＝tEndIfNextieq\x(last＝n–start＋1)′(2)LoopFori＝1TonList2.AddItemStr(a(i))NextiEndSubPrivateSubForm_Load()′产生8个随机数，并显示在列表框List1中，代码略EndSub解析先用从后往前的冒泡排序，将小的数排到前面，再用从前往后冒泡排序的方法，把较大的数排序后面，直到所有数据有序。答案(1)lastTostart＋1Step－1(2)last＝last－1考点3选择排序一、排序思想在数据区间[i，n]范围内，查找最值的位置k，并把该位置的数与第i个数进行交换，使得[1，i]数据有序，重复执行n－1趟。该算法包括两个步骤，一是查找区间[i，n]中最值位置k，二是交换位置k与位置i上值。二、算法实现1．理解变量i、j和k的含义变量i控制排序的趟数，n个数需要通过n－1趟(轮)排序；变量j表示比较大小的元素位置，k表示每趟中最大或最小数所在位置。2．比较的方向和步骤第i趟排序：在区间[i，n]中查找最值的位置k。每趟k的初值默认在第i个位置，因此比较的范围在[i＋1，n]，每次比较的位置j在最值k的后面。3．以5个元素a(1)至a(5)选择排序升序为例。趟数排序区域k初值k所在位置的最值与j所在位置的数组元素比较比较次数有序区域第1次第2次第3次第4次j初值i＝1[1，n]1k→2k→3k→4k→524[1，1]i＝2[2，n]2k→3k→4k→533[1，2]i＝3[3，n]3k→4k→542[1，3]i＝4[4，n]4k→551[1，4]①表示可以看出，第i趟排序的区间是[i，n]，因此比较位置j每次从i＋1开始，一直到最后，用最值k所在位置的数a(k)与a(j)，如果a(k)<a(j)，将k的值更新为j的值。②在比较过程中，只是发生了k值的更新，而没有进行数据交换，即每趟最多只交换了一次。③每趟数据是否交换的条件取决于k值是否发生了更新。4．冒泡排序与选择排序的区别排序比较对象交换情况冒泡相邻的两个数比较后，逆序即交换，每趟可能交换多次选择最值与待排序区域的数最值与第j个数交换，每趟最多交换一次5.选择排序标准代码(在数组a中，以升序为例进行选择排序)：Fori＝1Ton－1′n个数共进行n－1趟排序K＝i′第i趟排序时，首先用k记录iForj＝i＋1Ton′k位置上的数依次与j位置上的数进行比较Ifa(j)<a(k)Thenk＝j′若找到比k位置上更小的数，则更新k的值NextjIfk<>iThen′若i位置上的数不是最小数，则和k位置上的数进行互换temp＝a(i)：a(i)＝a(k)：a(k)＝tempEndIfNexti【例4】小赵对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：p＝1：q＝10DoWhilep<qiMin＝p：iMax＝pFori＝p＋1ToqIfa(i)<a(iMin)TheniMin＝iIfa(i)>a(iMax)TheniMax＝iNextit＝a(iMin):a(iMin)＝a(p):a(p)＝teq\x()t＝a(iMax):a(iMax)＝a(q):a(q)＝tp＝p＋1q＝q－1Loop要使程序实现上述算法思想，则方框中的语句是()A．IfiMax＝pTheniMax＝iMinB．IfiMin＝pTheniMin＝iMaxC．IfiMax＝pTheniMin＝iMaxD．IfiMin＝pTheniMax＝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【变式训练3】从数据库中读取各考生的编号、笔试和面试成绩，在文本框Text1中输入录取人数，按笔试与面试成绩之和从高到低录取，若成绩之和相等，面试成绩高的排前面。当录取人数达到计划录取人数时，若有面试加笔试的总分与之相等的分数，也要作为录取对象。程序运行的界面如图所示：VB程序代码如下，但加框处的代码有错，请改正。Constn＝266Dimms(n)AsInteger,bs(n)AsInteger,bh(n)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsInteger,sAsStringFori＝1Ton－1k＝iForj＝i＋1TonIfms(j)＋bs(j)>ms(k)＋bs(k)Thenk＝jeq\x(Elsems（j）＋bs（j）<ms（k）＋bs（k）)Then′(1)Ifms(j)>ms(k)Thenk＝jEndIfNextjIfk<>iThent＝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)＝tEndIfNextit＝Val(Text1.Text)i＝1DoWhilei<＝tOreq\x(ms（i）<>ms（i＋1）)′(2)s＝”序”＋Str(i)＋”：编号”＋Str(bh(i))＋””s＝s＋Str(bs(i))＋”＋”＋Str(ms(i))＋”＝”＋Str(bs(i)＋ms(i))List1.AddItemsi＝i＋1LoopEndSubPrivateSubForm_Load()′从数据库中读取各考生的编号(bh数组)、笔试(bs数组)和面试(ms数组)成绩，分别存储在相应的数组中EndSub解析第一部分为选择排序，有两种情况要交换，即总分大于前者，或者总分相等，但笔试高的，因此为多分支选择结构。第二部分为输出，输出的条件有两个，即输出的人数比计划录取人数少；或者已经达到计划录取人数，却还存在总分与计划录取最后一人的总分相等，也要输出。答案(1)ElseIfms(j)＋bs(j)＝ms(k)＋bs(k)(2)ms(i)＋bs(i)＝ms(i－1)＋bs(i－1)一、选择题1．有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24该数组的原始顺序不可能的是()A．10，5，32，6，7，9，17，24，4B．10，5，32，6，7，9，4，17，24C．10，5，32，4，6，7，9，17，24D．4，10，5，32，17，9，24，6，7解析从第一遍排序的结果来看，把到小的数交换到第1个位置，因此属于从后往前冒泡。答案D2．有如下VB程序段：Fori＝1To2Forj＝5Toi＋1Step－1Ifa(j)>a(i)Thent＝a(j):a(j)＝a(i):a(i)＝tEndIfNextjNexti数组元素a(1)到a(5)的值依次为“33，24，45，16，77”，运行程序，数组元素a(1)到a(5)的值依次为()A．77，45，33，16，24 B．77，33，45，16，24C．77，24，45，16，33 D．77，45，33，24，16解析该程序段中比较和交换的对象为a(j)和a(i)，因此不属于冒泡算法，可以采用分i＝1和i＝2两种情况进行讨论。当i＝1时，交换77和33，当i＝2时，交换33和24，再交换33和45。答案A3．有如下VB程序段：Fori＝1To2Forj＝1To5－iIfa(j＋1)<a(j)Thent＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝tNextjNexti数组a(1)到a(5)中数据分别为56，23，78，11，8，执行上述VB程序段后，数组元素的值分别为()A．8，11，23，56，78 B．23，11，8，56，78C．11，8，23，56，78 D．8，11，56，23，78解析本题采用从前向后冒泡两趟的算法，a(j＋1)<a(j)成立时交换，表示升序。答案B4．有如下程序段：Dimflag(0To4)AsBoolean,pAsIntegerFori＝1To4flag(i)＝FalseNextii＝1:flag(0)＝TrueDoWhilei<＝4Andflag(i－1)Forj＝5Toi＋1Step－1Ifa(j)<a(j－1)Thenk＝a(j)：a(j)＝a(j－1)：a(j－1)＝kflag(i)＝TrueEndIfNextji＝i＋1Loop数组元素a(1)到a(5)值依次为“16，4，24，33，77”，程序运行后，flag数组中为True个数及i的值分别是()A．1，2 B．1，3 C．2，2 D．2，3解析本题考核的是从后往前冒泡排序，语句flag(i)＝True表示如果有交换，那么第i趟的值为True。第1趟有交换，所以flag(1)为True，第2趟没有交换，在i＝3时，条件flag(i－1)＝True不成立。flag(0)和flag(1)为True。答案D5．有如下VB程序段：Fori＝1To2Forj＝2To7－iIfa(j)>a(j－1)Thenk＝a(j)：a(j)＝a(j－1)：a(j－1)＝kEndIfNextjNexti数组元素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(j－1)，但j的初值是2。条件a(j)>a(j－1)成立表示后面的比前面大交换，降序。比较次数为5＋4＝9次。交换次数为：第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”Fori＝1To4Forj＝5Toi＋1Step－1Ifa(j)>a(j－1)Thent＝a(j)：a(j)＝a(j－1)：a(j－1)＝tNextjList1.Additema(i)Nexti该程序段运行后，列表框List1中显示的内容为()A．12，16，20，o，k B．o，k，20，16C．o，k，20，16，12 D．20，16，解析在字符比较中，先从左边第1个字符开始比较，数字小于大写字母小于小写字母，如果前面的字符相等，再继续往后比较。采用的是从后往前冒泡排序，但只显示前面4个数组元素。答案B7．有如下VB程序段：s＝””Fori＝1To3Forj＝1To10－iIfd(j)>d(j＋1)Thentt＝d(j)：d(j)＝d(j＋1)：d(j＋1)＝ttEndIfNextjs＝s＋Str(d(i))Nextitext1.Text＝s数组元素d(1)到d(10)的值分别是91、28、83、62、64、36、9、65、37、99，经过该程序段“加工”后，文本框Text1中显示的内容为()A．92837 B．999183C．28936 D．286236解析此算法属于从前往后冒泡排序算法，且只排了3趟。第1趟把91移动到后面，第2趟把83移动到后面。答案D8．有如下VB程序段：Fori＝1To6j＝7DoWhilej>iIfa(j)>a(j－1)Thena(j)＝a(j)＋a(j－1)：a(j－1)＝a(j)－a(j－1)：a(j)＝a(j)－a(j－1)EndIfj＝j－1LoopNextiFori＝3To6s＝s＋a(i)NextiLabel1.Caption＝Str(s)已知数组元素a(1)到a(7)的值依次为“8，2，3，7，10，6，5”，则执行该程序段后，标签Label1中显示的是()A．21 B．26 C．41 D．18解析这三条语句a(j)＝a(j)＋a(j－1)：a(j－1)＝a(j)－a(j－1)：a(j)＝a(j)－a(j－1)的作用是交换a(j)和a(j－1)，因此是从后往前的冒泡升序算法。把5＋6＋7＋8输出。答案B9．有如下VB程序段：Dima(5)AsInteger,b(5)AsIntegera(1)＝2:a(2)＝5:a(3)＝2:a(4)＝5:a(5)＝4b(1)＝14:b(2)＝23:b(3)＝32:b(4)＝44:b(5)＝56Fori＝1To4Forj＝5Toi＋1Step－1Ifa(i)>a(j)Thent＝a(i):a(i)＝a(j):a(j)＝tt＝b(i):b(i)＝b(j):b(j)＝tElseIfa(i)＝a(j)Andb(i)<b(j)Thent＝b(i):b(i)＝b(j):b(j)＝tEndIfNextjNexti则运行该程序后，数组b中各元素的值依次是()A．3214564423 B．1432562344C．1423324456 D．5644322314解析本题考核的知识点是冒泡排序的应用。本题中对a数组从小到大排列，同时如果a数组元素的值相等，且所对应的b数组前面的比后小，要交换b数组元素的值。数组下标i排序前排序后a(i)b(i)a(i)b(i)12142322523214323245645445445456523答案A10．实现某算法的部分VB程序段如下：i＝1DoWhilei<＝5p＝6Forj＝6Toi＋1Step－1Ifa(j)<a(j－1)Thent＝a(j):a(j)＝a(j－1):a(j－1)＝tp＝jEndIfNextji＝pn＝n＋1LoopText1.Text＝Str(n)数组元素a(1)到a(6)的数据依次为“8，3，9，16，22，2”，则程序运行后，文本框Text1中显示的内容为()A．2 B．3 C．4 D．5解析变量n表示排序的趟数，第1趟排序结果2,8,3,9，16，22，最后交换的元素为a(2)和a(1)，此时i＝2；第2趟排序结果2,3，8,9，16，22，最后交换的元素为a(3)和a(2)，此时i＝3；第3趟排序时，数据没有交换，因此i＝6，退出循环。答案B11．某VB程序段如下：i＝1DoWhilei<＝3k＝ij＝i＋1DoWhilej<＝5Ifa(j)<a(k)Thenk＝jj＝j＋1LoopIfi<>kThent＝a(i):a(i)＝a(k):a(k)＝ti＝i＋1Loop数组元素a(1)到a(5)的依次为“17，87，36，22，45”，则程序运行后，数组元素数据依次是()A．87，45，36，17，22 B．17，22，36，45，87C．17，22，36，87，45 D．87，45，17，36，22解析这是选择排序，但只排了3趟。条件a(j)<a(k)表示升序。答案C12．有如下VB程序段：Fori＝5To4Step－1k＝iForj＝6－iTo1Step－1Ifa(j)<a(k)Thenk＝jNextjIfi<>kThent＝a(i):a(i)＝a(k):a(k)＝tEndIfNexti数组元素a(1)到a(5)的值依次为“41，66，70，83，31”，经过该程序段“加工”后，数组元素a(1)到a(5)的值依次为()A．31，41，66，83，70 B．83，70，66，41，31C．83，66，70，41，31 D．31，41，66，70，83解析该算法不是选择排序，只能采用分类讨论的思想进行解题。当i＝5时，Forj＝1To1Step－1没有交换。当i＝4时，Forj＝2To1Step－1找到最小数是41。答案C13．有如下VB程序段：Fori＝1To5Forj＝i＋1To6Ifs(i)＋s(j)<s(j)＋s(i)Thent＝s(j):s(j)＝s(i):s(i)＝tEndIfNextjNextiFori＝1To6Text1.Text＝Text1.Text＋s(i)Nexti如果程序运行，一开始当数组元素s(1)到s(6)的值依次为“4”、“343”、“312”、“12”、“246”、“121”，运行该段代码后，文本框Text1中显示的内容为()A．434331224612121 B．434331224612112C．343312246121124 D．121122463123434解析这是对字符串的操作，进行字符串的连接。当i＝1、2、3时，a(i)连接起来是较大值，没有交换。答案B14．有如下VB程序段：tail＝6:i＝1:r＝2DoWhilei<rForj＝tailToi＋1Step－1Ifa(j)>a(j－1)Thent＝a(j):a(j)＝a(j－1):a(j－1)＝tEndIfNextji＝i＋1Forj＝iTotail－1Ifa(j)<a(j＋1)Thent＝a(j):a(j)＝a(j＋1):a(j＋1)＝tEndIfNextjtail＝tail－1Loop数组元素值“73、56、28、61、44、92”，运行程序，数组元素a(1)到a(6)的值依次为()A．73，61，56，92，44，28 B．92，73，56，61，44，28C．92，73，61，56，28，44 D．92，73，61，56，44，28解析这是进行首尾同时排序。答案D15．完成某排序算法的VB程序段如下：Fori＝1To7k＝0Forj＝8Toi＋1Step－1Ifa(j)<a(j－1)Thent＝a(j)：a(j)＝a(j－1)：a(j－1)＝t：k＝1NextjIfk＝0ThenExitForNexti如果用上述算法对数据序列：38，11，21，62，59，65，77，79进行排序(数据分别存储在数组元素a(1)～a(8)中)，实现数据有序时所经历的排序遍数是()A．2 B．3 C．4 D．7解析采用从后往前冒泡排序算法。变量k表示每趟交换的次数，若某趟没有进行数据交换，表示数据已经有序，可以提前退出循环。第1趟的结果是11，38，21，59，62，65，77，79，第2趟的结果是11，21，38，59，62，65，77，79，在第2趟中还有数据交换，因此共排了3趟。答案B16．有如下VB程序段：n＝8:flag＝True:k＝0First＝1:Last＝nDoWhileflagp＝False:flag＝FalseForj＝LastToFirst＋1Step－1k＝k＋1Ifa(j)<a(j－1)Thent＝a(j):a(j)＝a(j－1):a(j－1)＝tFirst＝j:flag＝TrueIfp＝FalseThenLast＝j:p＝TrueEndIfNextjIfLast<>nThenLast＝Last＋1Loop数组元素a(1)到a(8)值依次为“2，8，12，17，13，14，18，19”，程序运行后，变量k的值为()A．3 B．8 C．9 D．28解析本题主要考查排序算法的优化。flag表示是否有序的标志，First表示最后一次前面交换的位置，如果前面的有序，下次First的位置开始比较。Last表示后面第一次交换的位置，后面Last＋1至n肯定是有序的，只要跟Last＋1进行比较比较就可以了。变量k表示排序的趟数。答案A17．有如下程序段：Fori＝1To3Forj＝i＋1To7Ifa(j)<a(i)Thenk＝a(j):a(j)＝a(i):a(i)＝kc＝c＋1EndIfNextjs＝Str(a(i))＋sNextiText1.Text＝Str(c)&“：”&s数组元素a(1)至a(7)中值分别为3，9，1，5，8，6，2，该程序段运行后，文本框Text1中显示的内容是()A．5：689 B．3:986 C．3：123 D．5：321解析比较对象为a(j)和a(i)，不是相邻元素，因此不属于冒泡算法，只能采用分类讨论的思想，其中变量c表示总的交换次数。当i＝1时，Forj＝2To7。结果为1，9，3，5，8，6，2，交换1次；当i＝2时，Forj＝3To7。结果为1，2，9，5，8，6，3，交换2次；当i＝3时，Forj＝4To7。结果为1，2，3，9，8，6，5，交换2次；共交接了5次，把前面3个数进行反向连接。答案D18．有如下VB程序段：i＝1DoWhilei<＝6t＝Int(Rnd*10)＋1IftMod2＝iMod2Thena(i)＝t:i＝i＋1LoopFori＝1To2k＝1Forj＝1To6－i*2Ifa(j)*k>a(j＋2)*kThent＝a(j)：a(j)＝a(j＋2)：a(j＋2)＝tEndIfk＝－kNextjNexti执行该程序段后，数组元素a(1)到a(6)的值可能是()A．5，9，2，10，7，8 B．9，0，7，2，3，4C．9，2，5，4，3，8 D．1，8，7，6，9，4解析满足条件tMod2＝iMod2表示奇数位是奇数，偶数位是偶数。a(j)和a(j＋2)比较和交接，表示是奇数位和偶数位分别排序，其中奇数位是升序，偶数为降序。答案D二、非选择题19．有一组正整数，要求仅对其中的奇数进行升序排序。排序后在列表框List2中也仅显示奇数部分数据，结果如图所示。实现上述功能的VB代码如下，但加框处有错，请改正。Constn＝10Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimtAsInteger,iAsInteger,jAsInteger,mAsIntegerDimtmpAsInteger′读取一组正整数，存储在数组a中，并显示在列表框List1，代码略i＝1DoWhilei<＝nForj＝nToi＋1Step－1Ifa(j)Mod2＝1ThenIfeq\x(a（j）<a（j－1）)Then′(1)tmp＝a(j):a(j)＝a(j－1):a(j－1)＝tmpt＝t＋1EndIfEndIfNextjIfeq\x(a（j）Mod2＝0)Thenm＝m＋1′(2)i＝i＋1LoopFori＝1tomList2.AddItemStr(a(i))NextiList2.AddItem”一共交换了”&t&”次”EndSub解析这是典型的冒泡排序，但只要求对奇数进行排序，因此当奇数与偶数比较时，把偶数换到后面。M表示奇数的数量。答案(1)a(j)<a(j－1)Ora(j－1)Mod2＝0(2)a(i)Mod2＝120．编写一个VB程序实现数据左右交替上升排序。功能如下：随机产生n个不重复的整数存数组a，并在列表框list1中显示，单击“排序”按钮Command1，在列表框list2中显示排序后的数据。某遍程序运行后，数组a中存储的左右交替上升排序的n个正整数，如下表所示：a(1)a(2)a(3)……a(n－2)a(n－1)a(n)147……862实现该功能的VB程序如下，但加框处代码有错，请改正。Constn＝10Dima(1Ton)AsIntegerPrivateSubForm_Load()′随机产生n个不重复的整数存数组a，并在列表框List1中显示。代码略。EndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,tAsIntegerDimimin1AsInteger,imin2AsIntegerFori＝1Ton\'2imin1＝iimin2＝i＋1Ifa(imin1)>a(imin2)Thent＝imin1:imin1＝imin2:imin2＝tForj＝i＋2Ton－i＋1Ifa(j)<a(imin1)Thenimin2＝imin1:imin1＝jeq\x(Else)′(1)imin2＝jEndIfNextjIfi<>imin1Thent＝a(i):a(i)＝a(imin1):a(imin1)＝tIfimin2＝iTheneq\x(imin1＝imin2)′(2)Ifn－i＋1<>imin2Thent＝a(n－i＋1)：a(n－i＋1)＝a(imin2)：a(imin2)＝tEndIfNexti′在列表框List1中显示排序后的数组a。代码略。EndSub解析变量imin2表示次大者，当把j赋值给imin2时，需满足imin2>a(j)。位置n－i＋1是与i的对称位置。答案(1)ElseIfimin2>a(j)Then(2)imin2＝imin121．某会议室收到10场会议使用申请，会议室使用安排要求：①会议时间不冲突；②一天内安排的会议场数最多；③优先安排结束时间早的会议。小李编写了一个VB程序，在List1中显示按结束时间升序排序的10场会议，List2中显示最终会议安排方案，运行界面如图所示。已知每场会议的开始、结束时间分别保存在数组a和数组b中，比如第i场会议，开始时间保存在a(i)中，结束时间保存在b(i)中。实现上述功能的VB程序如下，但加框处代码有错，请改正。PrivateSubCommand1_Click()Dima(1To20)AsSingleDimb(1To20)AsSingleDimiAsIntegerConstkaishi＝8′会议室开门时间Constjieshu＝17′会议室关门时间′此