高考專題復習專題七-排序算法的程序實現(xiàn)信息技術

專題七排序算法的程序實現(xiàn)【考綱標準】考試內容考試要求排序算法的程序實現(xiàn)：①冒泡排序②選擇排序c1．(2018·4月浙江選考)有一組正整數(shù)，要求僅對其中的素數(shù)進行升序排序。排序后素數(shù)在前，非素數(shù)在后。排序示例如下。排序前867154181793789排序后537417179898681實現(xiàn)上述功能的VB程序如下，但加框處代碼有誤，請改正。Constn＝8Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsInteger,tAsIntegerDimflagAsBoolean′讀取一組正整數(shù)，存儲在數(shù)組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表示退出循環(huán)Nexti′依次輸出排序后的數(shù)據(jù)。代碼略EndSubFunctionIsPrime(mAsInteger)AsBoolean′本函數(shù)判斷m是否是素數(shù)：是素數(shù)返回值為True，不是素數(shù)返回值為False′代碼略EndFunction解析交換兩個數(shù)的語句出現(xiàn)在外循環(huán)中，說明是選擇排序，變量k表示每趟排序中的最值，因此k的初值是i。題目是要求僅對其中的素數(shù)進行升序排序，因此比較的對象a(k)還要求是素數(shù)。答案(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中顯示排序前的數(shù)據(jù)，單擊“排序”按鈕Command1，在文本框Text2中顯示剔除重復數(shù)據(jù)后的升序排序結果。程序運行界面如下圖所示。實現(xiàn)上述功能的VB代碼如下，但加框處代碼有錯，請改正。Constn＝10Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger，jAsInteger，tAsIntegerDimbottomAsInteger′剔除重復數(shù)據(jù)后元素的個數(shù)′獲取排序前數(shù)據(jù)依次存儲在數(shù)組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′若相鄰數(shù)據(jù)相等，進行剔除處理eq\x(a（bottom）＝a（j）)′(2)bottom＝bottom－1EndIfNextji＝i＋1LoopText2.Text＝""Fori＝1TobottomText2.Text＝Text2.Text＋Str(a(i))NextiEndSub解析本題考核從后往前冒泡的算法思想。從后往前冒泡，前面的數(shù)據(jù)先有序，當兩次比較的數(shù)據(jù)a(j－1)和a(j)中相等時，a(j－1)可能已經有序，因此用最后一個數(shù)據(jù)替換a(j)，同時數(shù)據(jù)的有效長度bottom少1個。答案(1)a(j)<a(j－1)或a(j－1)>a(j)或其他等價表達式(2)a(j)＝a(bottom)或其他等價語句3．(2016·10月浙江省技術選考)小吳為了研究冒泡排序過程中數(shù)據(jù)的“移動”情況，編寫了一個VB程序，功能如下：在列表框List1中顯示排序前數(shù)據(jù)(存儲在數(shù)組a中)，在文本框Text1中輸入初始位置(即下標值)，單擊“排序”按鈕Command1后，在標簽Label1中顯示指定初始位置的數(shù)據(jù)在排序過程中的位置變化情況，排序后的數(shù)據(jù)顯示在列表框List2中。程序運行界面如圖所示。實現(xiàn)上述功能的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位置的數(shù)據(jù)參與交換，則更新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解析第一處改錯實現(xiàn)的是兩個變量的交換。交換變量a(j)和a(j－1)的值后，該兩個元素數(shù)據(jù)位置發(fā)生變化，接下來判斷這兩個元素的下標是否和pos相同，如果pos和j相同，已經被交換到j－1位置，pos需要更新，否則如果pos和j－1相同，已經被交換到j位置，pos需要更新。答案(1)k＝a(j－1)(2)ElseIfpos＝j－1Then1．排序的作用是把n個數(shù)據(jù)從小到大或從大到小重新排列，使得a(1)至a(n)中的數(shù)據(jù)有序。排序的方法有很多，重點掌握冒泡排序和選擇排序。2．n個數(shù)據(jù)一般需要經過n－1趟排序，變量i控制排序的趟數(shù)。第i趟的比較次數(shù)往往有n－i次。3．變量j表示比較大小的元素位置，其中數(shù)組元素a(j－1)表示第j－1個位置的數(shù)組元素，他位于a(j)的前面第一個元素，a(j＋1)位于a(j)的后面第一個元素。4．內部循環(huán)(j的循環(huán))初值和終值決定了排序的區(qū)間和方向。如果初值大于終值，初值往往是n，表示從后往前向后排序，若j的初值小于終值，初值往往是1，表示從前往后排序。考點1從后往前冒泡排序1．以n(n＝5)個元素從后往前冒泡升序排序為例，完成下列表格。趟數(shù)排序區(qū)間第1次第2次第3次第4次j終值比較次數(shù)有序區(qū)間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位置，實現(xiàn)從第1個位置到第i個位置的元素有序。數(shù)組前面的元素先有序。②第i趟排序的區(qū)間是[i，n]，因此每趟排序的比較的位置(j的初值)為n。2．每趟排序的算法第i趟的排序實現(xiàn)在區(qū)間[i，n]中，從第n個位置的數(shù)開始，依次與前面相鄰的數(shù)比較，如果逆序即交換，比較和交換的對象為a(j)和a(j－1)，比較完后向前移動，直到j－1的位置到達最前面的位置i為止，此時j＝i＋1。實現(xiàn)區(qū)間[1，i]的數(shù)據(jù)有序。3．若每趟交換的次數(shù)為0，表示所有數(shù)據(jù)均有序，可以提前結束排序算法。也可以記flag的狀態(tài)為False，若發(fā)生交換，將flag的值修改為True，根據(jù)flag的值，也可以表示數(shù)據(jù)是否有序。4．每趟排序實現(xiàn)了[1，i]之間的數(shù)據(jù)有序，因此下趟排序的區(qū)間為[i＋1，n]。記錄第i趟排序最后一次交換的位置j，此時表示[1，j－1]已經有序，下趟排序的區(qū)間可以修改為[j，n]，當j大于i＋1時，就縮小下趟排序的區(qū)間，減少排序的次數(shù)，達到優(yōu)化排序的效果。5．核心代碼【例1】小劉在研究n個數(shù)的冒泡排序算法時，發(fā)現(xiàn)可以從兩個方面進行優(yōu)化：(1)在每遍冒泡過程中，若最后一次交換的是last與last－1位置的數(shù)，則last－1位置之前的相鄰數(shù)據(jù)均已有序。進行下一遍冒泡時，無序區(qū)域設置為[last，n]。(2)若在某一遍排序中沒有數(shù)據(jù)交換，說明待排序數(shù)據(jù)都已經有序，冒泡排序過程可在此遍排序后終止。小劉按上述方法編寫的冒泡優(yōu)化VB程序，功能如下：程序運行時生成100個隨機整數(shù)存入數(shù)組a，并顯示在列表框List1中。單擊“排序”按鈕Command1后，對數(shù)組a中的數(shù)據(jù)進行排序，排序后的數(shù)據(jù)顯示在列表框List2中，排序過程中實際的冒泡遍數(shù)顯示在標簽Label3上。程序運行界面如圖所示。實現(xiàn)上述功能的VB程序如下，但加框處代碼有錯，請改正。Dima(1To100)AsIntegerPrivateSubForm_Load()′產生100個無重復的三隨機整數(shù)，存入數(shù)組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′有交換發(fā)生EndIfNextjn＝n＋1LoopFori＝1To100List2.AddItemStr(a(i))NextiLabel3.Caption＝“本次排序的冒泡遍數(shù)為：”&Str(n)EndSub其中，方框(1)處應改正為________；方框(2)處應改正為________。解析flag表示有無交換的標志，如果本趟中沒有發(fā)生數(shù)據(jù)的交換，表示數(shù)據(jù)已經有序，flag＝True語句出現(xiàn)在交換模塊中，有交換還要循環(huán)，因此循環(huán)的條件是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數(shù)組元素a(1)至a(10)的值分別為“3，17，2，14，15，6，7，18，9，4”，執(zhí)行該程序段后，數(shù)組元素a(8)中的值為()A．3 B．4 C．15 D．17解析從比較對象a(j)和a(j－2)看，屬于奇數(shù)位和偶數(shù)位分別進行升序排列，每趟有2個數(shù)據(jù)有序，因此只要進行n\2趟排序。偶數(shù)位的數(shù)據(jù)有17,14,6,18,4，升序排列中第2大的數(shù)是17。答案D【變式訓練1】有一組正整數(shù)，基于冒泡排序對其中的數(shù)進行升序排序。排序后奇數(shù)在前，偶數(shù)在后。排序示例如下排序前783064394948321832排序后394983481830326478實現(xiàn)上述功能的VB程序如下，但加框處代碼有誤，請改正。Constn＝10Dimd(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,tAsInteger′讀取一組正整數(shù)，存儲在數(shù)組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′依次輸出排序后的數(shù)據(jù)，代碼略EndSub解析條件d(j)Mod2＝d(j－1)Mod2成立，表示相鄰兩個數(shù)都是奇數(shù)或都是偶數(shù)，相鄰兩個數(shù)進行比較，并且把小的數(shù)換到前面。如果是一奇一偶，且偶數(shù)在前，要把偶數(shù)換到后面。答案(1)a(j)<a(j－1)(2)ElseIfa(j－1)Mod2＝0Then考點2從前往后冒泡排序1．對稱位置：在數(shù)組a(1)至a(n)中，有下列數(shù)組元素的位置是左右對稱的，如a(1)與a(n)，a(2)與a(n－1)，a(3)與a(n－2)等，兩個左右對稱數(shù)組元素位置的下標之和是一個定值n＋1，因此可以到結論：與下標為i的數(shù)組元素左右對稱的位置是n－i＋1。2．以n(n＝5)個元素從前往后冒泡升序排序為例，完成下列表格。趟數(shù)排序區(qū)間第1次第2次第3次第4次j終值比較次數(shù)有序區(qū)間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的位置，實現(xiàn)從第n－i＋1個位置到第n個位置的元素有序。數(shù)組后面的元素先有序。②第i趟排序的區(qū)間是[1，n－i＋1]，因此每趟排序的比較的位置(j的初值)為1。3．每趟排序的算法第i趟的排序實現(xiàn)在區(qū)間[1，n－i＋1]中，從第1個位置的數(shù)開始，依次與后面相鄰的數(shù)比較，如果逆序即交換，比較和交換的對象為a(j)和a(j＋1)，比較完后向后移動，直到j＋1的位置到達最后面的位置n－i＋1為止，此時j＝n－i。實現(xiàn)區(qū)間[n－i＋1，n]的數(shù)據(jù)有序。4．每趟排序實現(xiàn)了[n－i＋1，n]之間的數(shù)據(jù)有序，因此下趟排序的區(qū)間為[1，n－i]。記錄第i趟排序最后一次交換的位置j，此時表示[j＋1，n]已經有序，下趟排序的區(qū)間可以修改為[1，j]，當j小于n－i時，就縮小下趟排序的區(qū)間，減少排序的次數(shù)，達到優(yōu)化排序的效果。5．核心代碼優(yōu)化前的代碼優(yōu)化后的代碼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中顯示排序前的數(shù)據(jù)，單擊“排序”按鈕Command1，在文本框Text2中顯示剔除重復數(shù)據(jù)后的升序排序結果。程序運行界面如下圖所示。實現(xiàn)上述功能的VB程序如下，請將劃線處填寫完整。Constn＝10Dima(n)AsIntegerPrivateSubForm_Load()′產生n個隨機數(shù)，并顯示在文本框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)，因此數(shù)據(jù)從后面開始有序，當兩個數(shù)據(jù)是重復時，把開頭的數(shù)據(jù)替換a(j)，繼續(xù)排序，變量top表示不重復數(shù)據(jù)的開始位置，j的初值從top開始。答案①j＝top②a(j)＝a(top)【變式訓練2】小趙對冒泡升序排列算法進行了如下改進：在一趟排序中，同時進行從最后一個元素向前的比較并交換和從第一個元素向后比較并交換，把最小的元素交接到前面，把最大的元素交換到后面，以此類推，直到所有元素的數(shù)據(jù)按升序排列。小趙編寫的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個隨機數(shù)，并顯示在列表框List1中，代碼略EndSub解析先用從后往前的冒泡排序，將小的數(shù)排到前面，再用從前往后冒泡排序的方法，把較大的數(shù)排序后面，直到所有數(shù)據(jù)有序。答案(1)lastTostart＋1Step－1(2)last＝last－1考點3選擇排序一、排序思想在數(shù)據(jù)區(qū)間[i，n]范圍內，查找最值的位置k，并把該位置的數(shù)與第i個數(shù)進行交換，使得[1，i]數(shù)據(jù)有序，重復執(zhí)行n－1趟。該算法包括兩個步驟，一是查找區(qū)間[i，n]中最值位置k，二是交換位置k與位置i上值。二、算法實現(xiàn)1．理解變量i、j和k的含義變量i控制排序的趟數(shù)，n個數(shù)需要通過n－1趟(輪)排序；變量j表示比較大小的元素位置，k表示每趟中最大或最小數(shù)所在位置。2．比較的方向和步驟第i趟排序：在區(qū)間[i，n]中查找最值的位置k。每趟k的初值默認在第i個位置，因此比較的范圍在[i＋1，n]，每次比較的位置j在最值k的后面。3．以5個元素a(1)至a(5)選擇排序升序為例。趟數(shù)排序區(qū)域k初值k所在位置的最值與j所在位置的數(shù)組元素比較比較次數(shù)有序區(qū)域第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趟排序的區(qū)間是[i，n]，因此比較位置j每次從i＋1開始，一直到最后，用最值k所在位置的數(shù)a(k)與a(j)，如果a(k)<a(j)，將k的值更新為j的值。②在比較過程中，只是發(fā)生了k值的更新，而沒有進行數(shù)據(jù)交換，即每趟最多只交換了一次。③每趟數(shù)據(jù)是否交換的條件取決于k值是否發(fā)生了更新。4．冒泡排序與選擇排序的區(qū)別排序比較對象交換情況冒泡相鄰的兩個數(shù)比較后，逆序即交換，每趟可能交換多次選擇最值與待排序區(qū)域的數(shù)最值與第j個數(shù)交換，每趟最多交換一次5.選擇排序標準代碼(在數(shù)組a中，以升序為例進行選擇排序)：Fori＝1Ton－1′n個數(shù)共進行n－1趟排序K＝i′第i趟排序時，首先用k記錄iForj＝i＋1Ton′k位置上的數(shù)依次與j位置上的數(shù)進行比較Ifa(j)<a(k)Thenk＝j′若找到比k位置上更小的數(shù)，則更新k的值NextjIfk<>iThen′若i位置上的數(shù)不是最小數(shù)，則和k位置上的數(shù)進行互換temp＝a(i)：a(i)＝a(k)：a(k)＝tempEndIfNexti【例4】小趙對選擇排序算法進行了如下改進：在數(shù)組的所有元素中找出最小和最大數(shù)據(jù)的元素，然后將這兩個元素分別與第一個和最后一個元素交換數(shù)據(jù)，在余下的元素中找出最小和最大數(shù)據(jù)的元素，分別與第二個和倒數(shù)第二個元素交換數(shù)據(jù)，以此類推，直到所有元素的數(shù)據(jù)按升序排列。小趙編寫的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要使程序實現(xiàn)上述算法思想，則方框中的語句是()A．IfiMax＝pTheniMax＝iMinB．IfiMin＝pTheniMin＝iMaxC．IfiMax＝pTheniMin＝iMaxD．IfiMin＝pTheniMax＝iMin解析該算法是對選擇排序算法的改進，由原來的找到最大數(shù)(或最小數(shù))后從一個方向排序改為從最小和最大兩個方向同時進行排序；每趟排序a(iMin)為找到的最小數(shù)，a(iMax)為找到的最大數(shù)；最小數(shù)a(iMin)和a(p)交換，排到前邊，然后最大數(shù)a(iMax)和a(q)交換，排到后邊，實現(xiàn)升序排列；在每一趟循環(huán)中，如果沒有方框中的語句，在a(p)恰好為最大數(shù)a(iMax)(即imax＝p)時，因為最小數(shù)a(iMin)和a(p)先進行交換，交換后a(iMax)會變成最小數(shù)，a(iMax)和a(q)再進行交換會把最小數(shù)交換到a(q)而出現(xiàn)錯誤；方框中的語句應為避免這一錯誤的語句，A正確。分析程序時可以從待選項中獲取線索。答案A【變式訓練3】從數(shù)據(jù)庫中讀取各考生的編號、筆試和面試成績，在文本框Text1中輸入錄取人數(shù)，按筆試與面試成績之和從高到低錄取，若成績之和相等，面試成績高的排前面。當錄取人數(shù)達到計劃錄取人數(shù)時，若有面試加筆試的總分與之相等的分數(shù)，也要作為錄取對象。程序運行的界面如圖所示：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()′從數(shù)據(jù)庫中讀取各考生的編號(bh數(shù)組)、筆試(bs數(shù)組)和面試(ms數(shù)組)成績，分別存儲在相應的數(shù)組中EndSub解析第一部分為選擇排序，有兩種情況要交換，即總分大于前者，或者總分相等，但筆試高的，因此為多分支選擇結構。第二部分為輸出，輸出的條件有兩個，即輸出的人數(shù)比計劃錄取人數(shù)少；或者已經達到計劃錄取人數(shù)，卻還存在總分與計劃錄取最后一人的總分相等，也要輸出。答案(1)ElseIfms(j)＋bs(j)＝ms(k)＋bs(k)(2)ms(i)＋bs(i)＝ms(i－1)＋bs(i－1)一、選擇題1．有一個數(shù)組，采用冒泡排序，第一遍排序后的結果為：4，10，5，32，6，7，9，17，24該數(shù)組的原始順序不可能的是()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解析從第一遍排序的結果來看，把到小的數(shù)交換到第1個位置，因此屬于從后往前冒泡。答案D2．有如下VB程序段：Fori＝1To2Forj＝5Toi＋1Step－1Ifa(j)>a(i)Thent＝a(j):a(j)＝a(i):a(i)＝tEndIfNextjNexti數(shù)組元素a(1)到a(5)的值依次為“33，24，45，16，77”，運行程序，數(shù)組元素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數(shù)組a(1)到a(5)中數(shù)據(jù)分別為56，23，78，11，8，執(zhí)行上述VB程序段后，數(shù)組元素的值分別為()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數(shù)組元素a(1)到a(5)值依次為“16，4，24，33，77”，程序運行后，flag數(shù)組中為True個數(shù)及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數(shù)組元素a(1)到a(6)的值依次為“71，54，58，29，31，78”，運行程序，下列說法正確的是()A．數(shù)組元素a(1)到a(6)的值依次為54，29，31，58，71，78B．此過程中數(shù)據(jù)共需比較次數(shù)為8次C．此過程中數(shù)據(jù)共需交換次數(shù)為5次D此過程中數(shù)據(jù)“54”共被比較5次解析該程序采用從前往后冒泡兩次的算法的變式，比較對象是a(j)和a(j－1)，但j的初值是2。條件a(j)>a(j－1)成立表示后面的比前面大交換，降序。比較次數(shù)為5＋4＝9次。交換次數(shù)為：第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個字符開始比較，數(shù)字小于大寫字母小于小寫字母，如果前面的字符相等，再繼續(xù)往后比較。采用的是從后往前冒泡排序，但只顯示前面4個數(shù)組元素。答案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數(shù)組元素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)已知數(shù)組元素a(1)到a(7)的值依次為“8，2，3，7，10，6，5”，則執(zhí)行該程序段后，標簽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則運行該程序后，數(shù)組b中各元素的值依次是()A．3214564423 B．1432562344C．1423324456 D．5644322314解析本題考核的知識點是冒泡排序的應用。本題中對a數(shù)組從小到大排列，同時如果a數(shù)組元素的值相等，且所對應的b數(shù)組前面的比后小，要交換b數(shù)組元素的值。數(shù)組下標i排序前排序后a(i)b(i)a(i)b(i)12142322523214323245645445445456523答案A10．實現(xiàn)某算法的部分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)數(shù)組元素a(1)到a(6)的數(shù)據(jù)依次為“8，3，9，16，22，2”，則程序運行后，文本框Text1中顯示的內容為()A．2 B．3 C．4 D．5解析變量n表示排序的趟數(shù)，第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趟排序時，數(shù)據(jù)沒有交換，因此i＝6，退出循環(huán)。答案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數(shù)組元素a(1)到a(5)的依次為“17，87，36，22，45”，則程序運行后，數(shù)組元素數(shù)據(jù)依次是()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數(shù)組元素a(1)到a(5)的值依次為“41，66，70，83，31”，經過該程序段“加工”后，數(shù)組元素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時，F(xiàn)orj＝1To1Step－1沒有交換。當i＝4時，F(xiàn)orj＝2To1Step－1找到最小數(shù)是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如果程序運行，一開始當數(shù)組元素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數(shù)組元素值“73、56、28、61、44、92”，運行程序，數(shù)組元素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如果用上述算法對數(shù)據(jù)序列：38，11，21，62，59，65，77，79進行排序(數(shù)據(jù)分別存儲在數(shù)組元素a(1)～a(8)中)，實現(xiàn)數(shù)據(jù)有序時所經歷的排序遍數(shù)是()A．2 B．3 C．4 D．7解析采用從后往前冒泡排序算法。變量k表示每趟交換的次數(shù)，若某趟沒有進行數(shù)據(jù)交換，表示數(shù)據(jù)已經有序，可以提前退出循環(huán)。第1趟的結果是11，38，21，59，62，65，77，79，第2趟的結果是11，21，38，59，62，65，77，79，在第2趟中還有數(shù)據(jù)交換，因此共排了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數(shù)組元素a(1)到a(8)值依次為“2，8，12，17，13，14，18，19”，程序運行后，變量k的值為()A．3 B．8 C．9 D．28解析本題主要考查排序算法的優(yōu)化。flag表示是否有序的標志，F(xiàn)irst表示最后一次前面交換的位置，如果前面的有序，下次First的位置開始比較。Last表示后面第一次交換的位置，后面Last＋1至n肯定是有序的，只要跟Last＋1進行比較比較就可以了。變量k表示排序的趟數(shù)。答案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數(shù)組元素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表示總的交換次數(shù)。當i＝1時，F(xiàn)orj＝2To7。結果為1，9，3，5，8，6，2，交換1次；當i＝2時，F(xiàn)orj＝3To7。結果為1，2，9，5，8，6，3，交換2次；當i＝3時，F(xiàn)orj＝4To7。結果為1，2，3，9，8，6，5，交換2次；共交接了5次，把前面3個數(shù)進行反向連接。答案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執(zhí)行該程序段后，數(shù)組元素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表示奇數(shù)位是奇數(shù)，偶數(shù)位是偶數(shù)。a(j)和a(j＋2)比較和交接，表示是奇數(shù)位和偶數(shù)位分別排序，其中奇數(shù)位是升序，偶數(shù)為降序。答案D二、非選擇題19．有一組正整數(shù)，要求僅對其中的奇數(shù)進行升序排序。排序后在列表框List2中也僅顯示奇數(shù)部分數(shù)據(jù)，結果如圖所示。實現(xiàn)上述功能的VB代碼如下，但加框處有錯，請改正。Constn＝10Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimtAsInteger,iAsInteger,jAsInteger,mAsIntegerDimtmpAsInteger′讀取一組正整數(shù)，存儲在數(shù)組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解析這是典型的冒泡排序，但只要求對奇數(shù)進行排序，因此當奇數(shù)與偶數(shù)比較時，把偶數(shù)換到后面。M表示奇數(shù)的數(shù)量。答案(1)a(j)<a(j－1)Ora(j－1)Mod2＝0(2)a(i)Mod2＝120．編寫一個VB程序實現(xiàn)數(shù)據(jù)左右交替上升排序。功能如下：隨機產生n個不重復的整數(shù)存數(shù)組a，并在列表框list1中顯示，單擊“排序”按鈕Command1，在列表框list2中顯示排序后的數(shù)據(jù)。某遍程序運行后，數(shù)組a中存儲的左右交替上升排序的n個正整數(shù)，如下表所示：a(1)a(2)a(3)……a(n－2)a(n－1)a(n)147……862實現(xiàn)該功能的VB程序如下，但加框處代碼有錯，請改正。Constn＝10Dima(1Ton)AsIntegerPrivateSubForm_Load()′隨機產生n個不重復的整數(shù)存數(shù)組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中顯示排序后的數(shù)組a。代碼略。EndSub解析變量imin2表示次大者，當把j賦值給imin2時，需滿足imin2>a(j)。位置n－i＋1是與i的對稱位置。答案(1)ElseIfimin2>a(j)Then(2)imin2＝imin121．某會議室收到10場會議使用申請，會議室使用安排要求：①會議時間不沖突；②一天內安排的會議場數(shù)最多；③優(yōu)先安排結束時間早的會議。小李編寫了一個VB程序，在List1中顯示按結束時間升序排序的10場會議，List2中顯示最終會議安排方案，運行界面如圖所示。已知每場會議的開始、結束時間分別保存在數(shù)組a和數(shù)組b中，比如第i場會議，開始時間保存在a(i)中，結束時間保存在b(i)中。實現(xiàn)上述功能的VB程序如下，但加框處代碼有錯，請改正。PrivateSubCommand1_Click()Dima(1To20)AsSingleDimb(1To20)AsSingleDimiAsIntegerConstkaishi＝8′會議室開門時間Constjieshu＝17′會議室關門時間′此