其他典型算法之線(xiàn)性表的應(yīng)用-專(zhuān)項(xiàng)訓(xùn)練浙江2022屆選考專(zhuān)用（教師版）

1、其他典型算法之線(xiàn)性表的應(yīng)用【例1】 在一升序數(shù)組a中插入一個(gè)數(shù)x,使數(shù)組元素仍保持升序。解決該問(wèn)題的VB程序段如下,在處應(yīng)填入的正確語(yǔ)句以實(shí)現(xiàn)功能。i=nn為數(shù)組a中的元素個(gè)數(shù)do while i0 and a(i)xi=i-1loopa(i+1)=x答案:a(i+1)=a(i)解析:這是在一線(xiàn)性表中插入一元素的問(wèn)題,該算法的基本方法是先找到數(shù)據(jù)插入的位置i,把原有元素a(i)、a(i+1)、a(i+2)a(n)依次移到表中的第i+1、i+2、i+3n+1個(gè)位置,以便騰出一個(gè)空位置i,再把新元素存入到該位置上。本程序的循環(huán)部分即完成了位置的查找和原數(shù)據(jù)后移的功能,因此劃線(xiàn)處應(yīng)填入的語(yǔ)句是a(i

2、+1)=a(i)?！纠?】插入排序的基本思想是:把待排序的數(shù)據(jù)按其值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中,直到所有的數(shù)據(jù)插入完為止,得到一個(gè)新的有序序列。例如,已知待排序的一組數(shù)據(jù)是60,71,49,11,24,3,66。假設(shè)在排序過(guò)程中,前3個(gè)數(shù)據(jù)已完成升序排列,構(gòu)成一個(gè)有序序列49,60,71。將待排序數(shù)據(jù)中的第4個(gè)數(shù)據(jù)(即11)插入上述有序序列,以得到一個(gè)新的含4個(gè)數(shù)據(jù)的有序序列。首先,應(yīng)找到11的插入位置,再進(jìn)行插入?？梢詫?1放入數(shù)組的第一個(gè)元素r(0)中,這個(gè)元素稱(chēng)為監(jiān)視哨,然后從71起從右到左查找,11小于71,將71右移一個(gè)位置,11小于60,又將60右移一個(gè)位置,11小

3、于49,又再將49右移一個(gè)位置,這時(shí)再將11與r(0)的值比較,11r(0),它的插入位置就是r(1)。假設(shè)11大于第一個(gè)值r(1),它的插入位置應(yīng)該在r(1)和r(2)之間,由于60已經(jīng)右移了,留出來(lái)的位置正好留給11,后面的數(shù)據(jù)依照同樣的方法逐個(gè)插入到該有序序列中。若數(shù)據(jù)有n個(gè),須進(jìn)行n-1趟排序,才能完成。以下VB程序執(zhí)行后,數(shù)組元素a(1)的值是()a(1)=10:a(2)=18:a(3)=12:a(4)=6:a(5)=9for i=2 to 5a(0)=a(i)j=i-1do while a(0)a(j)a(j+1)=a(j)j=j-1loopa(j+1)=a(0)next iA.1

4、0B.18C.6D.9答案；這是一個(gè)插入排序的算法,a(0)是待插入的數(shù)據(jù)。在do循環(huán)中,把小于待插入數(shù)a(0)的元素往后移動(dòng),最后留出空位存放a(0),說(shuō)明這是一個(gè)降序方式的插入排序算法,所以,a(1)中存放的是最大值18。故選B課后作業(yè)1.n個(gè)人排成一個(gè)圓圈,然后把這n個(gè)人按逆時(shí)針?lè)较蚍謩e編號(hào)為1、2、n。從編號(hào)為1的人開(kāi)始按逆時(shí)針計(jì)數(shù),當(dāng)某人計(jì)數(shù)為m的倍數(shù)時(shí),該人出圈;如此循環(huán)下去,直到圈中只有一個(gè)人留下。現(xiàn)用VB6制作一個(gè)模擬報(bào)數(shù)出列的程序,程序界面如下圖所示:在文本框Text1中輸入人數(shù)n,在文本框Text2中輸入出列號(hào)m,單擊按鈕模擬報(bào)數(shù)Command1,在列表框List1中顯示出

5、列順序編號(hào),程序界面如下。實(shí)現(xiàn)上述功能的VB 代碼如下, 請(qǐng)?jiān)趧澗€(xiàn)處填入合適代碼。Private Sub Command1_Click()Dim n As Integer, m As IntegerDim a(1 To 100) As Integern = Val(Text1.Text)m = Val(Text2.Text)For i = 1 To nNexts = 0j = 0Do While s nt = 0Do While t m t = t + a(j)Loopa(j) = 0List1.AddItem Str(j)s = s + 1LoopText3.Text = Str(j)End

6、 Sub答案: a(i)=1j = j Mod n + 1 或者 if j=n then n=1 else j=j+1解析: 模擬報(bào)數(shù)是一種典型的線(xiàn)性表應(yīng)用,程序中使用一維數(shù)組表示鏈表,數(shù)組元素下標(biāo)即編號(hào)。算法思想是:先設(shè)數(shù)組a的每個(gè)元素值為1;然后從第1個(gè)元素開(kāi)始累加,累加結(jié)果存入變量t,當(dāng)累加到j(luò)號(hào)元素時(shí)如果t值為3,則置a(j)=0,即j號(hào)出列,出列人數(shù)加1,一直到出列人數(shù)為n時(shí)結(jié)束,此時(shí)的j值即為最后剩下的編號(hào)。所以劃線(xiàn)處是把每個(gè)元素的值設(shè)為1,表示未出列,可填入語(yǔ)句a(i)=1。處計(jì)算本次輪到的元素下標(biāo),可填入j = j Mod n + 1,也可以是if j=n then n=1 e

7、lse j=j+1。2.利用VB程序?qū)山M成績(jī)數(shù)據(jù)合并為一組并按成績(jī)從高到低排列輸出。成績(jī)相同時(shí),第一批學(xué)生優(yōu)先輸出。實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正:Dim xm(1 to 1000) as string存儲(chǔ)學(xué)生姓名Dim cj(1 to 1000) as integer存儲(chǔ)學(xué)生成績(jī)Private Sub Form_Load()該處具體代碼省略從數(shù)據(jù)庫(kù)讀取兩批學(xué)生數(shù)據(jù)第1批學(xué)生的人數(shù)rs1,按成績(jī)從高到低的順序?qū)⒊煽?jī)存入cj(1)、cj(2)cj(rs1)中,姓名存入xm(1)、xm(2)xm(rs1)中,第2批人數(shù)rs2,按成績(jī)從高到低的順序?qū)⒊煽?jī)存入cj(rs1+1)

8、、cj(rs1+2)cj(rs1+rs2)中,姓名存入xm(rs1+1)、xm(rs1+2)xm(rs1+rs2)中End SubPrivate Sub Command1_Click()i=1j=rs1+1以下程序開(kāi)始按成績(jī)高低逐個(gè)輸出,每次輸出前后兩段中,尚未處理的學(xué)生中成績(jī)最高的n=1Do While i=rs1 And j=cj(j) Thenk=i:i=i+1Elsek=j:j=j+1End IfList1.AddItem(第+Str(n)+名+xm(k)+成績(jī):+Str(cj(k)LoopDo While i=rs1剩下第一段還有未輸出的,逐個(gè)輸出n=n+1List1.AddItem

9、(第+Str(n)+名+xm(i)+成績(jī):+Str(cj(i)i=i+1LoopDo While j=rs2若第二段還有未輸出的,逐個(gè)輸出n=n+1List1.AddItem(第+Str(n)+名+xm(j)+成績(jī):+Str(cj(j)j=j+1LoopEnd Sub答案: n=0j=rs1+rs2解析: 程序中,變量n表示名次,在第1個(gè)do循環(huán)語(yǔ)句中,先對(duì)n加1,再輸出名次,所以n的初值應(yīng)為0。變量j第二段成績(jī)的位置,第二段成績(jī)到rs1+rs2為止,所以處循環(huán)條件應(yīng)為j=rs1+rs2。3.編寫(xiě)一個(gè)VB程序,將一個(gè)長(zhǎng)度為n的有序序列a(1)、a(2)、a(n),以整數(shù)t(1tn)將該有序序列

10、劃分為兩段,并將序列a的前t個(gè)數(shù)與后n-t個(gè)數(shù)對(duì)調(diào),且保持這兩段(t個(gè)數(shù)和n-t個(gè)數(shù))之間的相對(duì)位置不變(即t個(gè)數(shù)和n-t個(gè)數(shù)各自有序)。例如,長(zhǎng)度為6的有序序列38、42、59、61、69、78,當(dāng)t=2時(shí)重排結(jié)果為59、61、69、78、38、42。程序運(yùn)行時(shí)產(chǎn)生n個(gè)整數(shù)存儲(chǔ)在數(shù)組a中,在文本框Text1中輸入t,單擊“對(duì)調(diào)”按鈕Command1,在列表框List2輸出t個(gè)數(shù)與n-t個(gè)數(shù)對(duì)調(diào)后的數(shù)字序列。為了實(shí)現(xiàn)上述功能,請(qǐng)?jiān)趧澗€(xiàn)處填入合適的代碼。Const n=10Dim a(1 To 10) As IntegerPrivate Sub Form_Load()生成n個(gè)有序數(shù),顯示在Lis

11、t1中,代碼略End SubPrivate Sub Command1_Click()Dim t As Integer,i As Integer,j As Integer,temp As IntegerFor i=t+1 To ntemp=a(i)For j=i To i+1-t Step-1Next ja(j)=Next iFor i=1 To nList2.AddItem Str(a(i)Next iEnd Sub答案 t=Val(Text1.Text)a(j)=a(j-1)temp解析 很簡(jiǎn)單,根據(jù)題目意思,要將有序數(shù)組a分成兩段,對(duì)換位置,首先要讀入數(shù)據(jù)t,所以答案是t=Val(Text

12、1.Text)。程序?yàn)榱藢?shí)現(xiàn)數(shù)組a的1t位置和t+1n位置的互換,使用雙重循環(huán)來(lái)解決這個(gè)問(wèn)題,具體做法是:第1輪(i=t+1),把a(bǔ)(1)a(t)依次后移一個(gè)位置,再把a(bǔ)(t+1)存入a(1);第2輪(i=t+2),把a(bǔ)(2)a(t+1)依次后移一個(gè)位置,再把a(bǔ)(t+2)存入a(2);如此重復(fù),直到最后一輪(i=n),把a(bǔ)(t)a(n-1)依次后移一個(gè)位置,再把a(bǔ)(n)存入a(t)。所以程序第2空應(yīng)該完成j-1位置到j(luò)位置的數(shù)據(jù)移動(dòng),答案是a(j)=a(j-1)。當(dāng)完成t個(gè)數(shù)據(jù)的移動(dòng)后,a(j)應(yīng)該等于原來(lái)存放在temp中的a(i)的值,所以答案是temp。4.單循環(huán)賽制是一種較為公平合理的比

13、賽制度,比賽過(guò)程中所有參賽隊(duì)伍均能相遇一次。其秩序編排可采用“逆時(shí)針輪轉(zhuǎn)方法”:數(shù)字1n依次作為隊(duì)伍編號(hào),把編號(hào)按U型走向分成均等兩邊(若n為奇數(shù),則在末尾增加編號(hào)0,使總數(shù)為偶數(shù)),即可得到第一輪的比賽秩序,例如,5個(gè)隊(duì)伍的比賽編排情況如圖a所示;第二輪,固定編號(hào)1,其余編號(hào)均按逆時(shí)針?lè)较蛞苿?dòng)一個(gè)位置,即為該輪比賽秩序;以后各輪比賽秩序以此類(lèi)推,與編號(hào)0對(duì)陣的表示本輪輪空。現(xiàn)用VB程序?qū)崿F(xiàn)上述功能:在文本框Text1中輸入?yún)①愱?duì)伍數(shù)n,單擊“編排”按鈕Command1,在列表框List1中輸出每輪比賽秩序。程序運(yùn)行效果如圖b所示。圖a圖b實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正。

14、Private Sub Command1_Click()Dim team(1 To 20) As String存儲(chǔ)各隊(duì)伍編號(hào)Dim n As Integer,c As Integer,result As StringDim i As Integer,j As Integer,temp As Stringn=Val(Text1.Text)For i=1 To nteam(i)=Str(i)Next ic=n+n Mod 2變量c存儲(chǔ)比賽編排的隊(duì)伍總數(shù)If cn Then team(c)=Str(0)For i=1 To c-1result= For j=1 To c2result=result

15、& team(j) & -&team(c-j) & ;Next jList1.AddItem 第 & Str(i) & 輪 & result固定編號(hào)1,其余隊(duì)伍逆時(shí)針移動(dòng)一個(gè)位置temp=team(c)For j=c To 2 Step -1team(j+1)=team(j)Next jteam(2)=tempNext iEnd Sub答案 team(c-j+1)team(j)=team(j-1)解析 程序以數(shù)組team來(lái)存儲(chǔ)隊(duì)伍的編號(hào),初始的時(shí)候team(i)的值就是i,用模擬法來(lái)分析算法,以6個(gè)隊(duì)伍為例,初始編號(hào)為1、2、3、4、5、6,程序始終以位置1-6、2-5、3-4的值來(lái)組成對(duì)陣表

16、,第2輪編號(hào)變成1、6、2、3、4、5,那么位置1-6、2-5、3-4所表示的對(duì)陣表為1-5、6-4、2-3,第3輪1、5、6、2、3、4,那么位置1-6、2-5、3-4所表示的對(duì)陣表為1-4、5-3、6-2,依次類(lèi)推。根據(jù)算法描述,以6個(gè)隊(duì)伍來(lái)模擬的話(huà),兩個(gè)對(duì)陣的隊(duì)伍對(duì)陣始終以數(shù)組team的1-6、2-5、3-4位置的值,下標(biāo)之和是7(即c+1),所以與team(j)對(duì)陣的應(yīng)該是team(c-j+1)。固定編號(hào)1,其余隊(duì)伍移動(dòng)的時(shí)候,先把最后一個(gè)位置的值拿出來(lái)存放到temp,把數(shù)組team的2到c-1位置的值逐個(gè)往后移動(dòng),存儲(chǔ)到3到c的位置,由于本程序用的是c到2的循環(huán),當(dāng)j=c的時(shí)候,應(yīng)該

17、是把c-1位置的值存儲(chǔ)到c位置,j=2時(shí),應(yīng)該是把2位置的值存儲(chǔ)到3位置,所以程序應(yīng)改成team(j)=team(j-1)。4.小李同學(xué)碰到了一個(gè)數(shù)學(xué)問(wèn)題:400個(gè)同學(xué)按順序進(jìn)行編號(hào)后圍成一個(gè)大圈,按1至2報(bào)數(shù)(從1號(hào)位置開(kāi)始),報(bào)到2的同學(xué)出列,以此一直循環(huán)報(bào)數(shù)下去,問(wèn)最后剩下的那位同學(xué)他的編號(hào)是幾號(hào)?例如以6個(gè)同學(xué)編號(hào)為例,按1至2報(bào)數(shù)(從1號(hào)位置開(kāi)始)依次出列的編號(hào)次序?yàn)?-4-6-3-1-5,那么最后剩下的就是編號(hào)為5的同學(xué)。為了解決這個(gè)問(wèn)題,小李用VB編寫(xiě)了如下程序嘗試解決,其中列表List1顯示出列的順序編號(hào),文本框Text1中顯示最后留下的編號(hào),程序代碼如下,請(qǐng)?jiān)趧澗€(xiàn)處填入合適的

18、代碼。Private Sub Command1_Click()Dim s,f,t As IntegerDim a(1 To 400) As BooleanFor i=1 To 400a(i)=FalseNext is=0:f=0:i=0Do While f399i=i+1If i=401 Then i=If a(i)=False Then s=s+1If s=2 ThenList1.AddItem Str(i)a(i)=Truef=End IfLoopFor i=1 To 400If Then Text1.Text=Str(i)Next iEnd Sub答案: 1s=0f+1Not a(i)或

19、a(i)=False解析: 400人圍成一圈從1號(hào)開(kāi)始1,2,1,2的報(bào)數(shù),報(bào)到2的就出列,直到剩下最后一位同學(xué),定義一個(gè)a數(shù)組,元素的初值均為false,表示游戲一開(kāi)始時(shí)所有學(xué)生全未出列,亦即開(kāi)始時(shí)全在列。設(shè)置變量s初值為零,接著從1號(hào)開(kāi)始兩個(gè)兩個(gè)的數(shù),只要計(jì)數(shù)器s等于2,當(dāng)前這位報(bào)到2的就出列,數(shù)組a當(dāng)前元素值變?yōu)門(mén)rue,表示該位同學(xué)出列,計(jì)數(shù)器s重置為零,計(jì)數(shù)器f表示到當(dāng)前為止已經(jīng)出列的人數(shù),以此一直循環(huán)到只剩下一位同學(xué),f的最大值為399,a(289)=false最后剩下289號(hào)同學(xué)。5.有n個(gè)互不重復(fù)的數(shù)字,值的范圍是1,n,分別保存在數(shù)組元素a(1)到a(n)中,如果數(shù)字i保存在

20、a(i),認(rèn)為數(shù)字i在正確的位置上。若干個(gè)相互占用了位置的數(shù)字稱(chēng)為一組,一個(gè)在正確位置上的數(shù)字單獨(dú)為一組,比如6個(gè)數(shù)字2,3,1,4,6,5分別保存在數(shù)組元素a(1)到a(6)中,則2、3、1為一組,4為一組,6、5為一組。該程序的功能為輸出每組的情況。運(yùn)行界面如下圖:(1)數(shù)組元素a(1)到a(5)的值分別為2、5、3、1、4,這5個(gè)元素總共有組。(2)請(qǐng)?jiān)趧澗€(xiàn)處填入合適的代碼。Const n=10Dim a(1 To n) As Integer保存原始數(shù)據(jù)Dim b(1 To n) As Boolean數(shù)組b用來(lái)標(biāo)記相應(yīng)的位置有沒(méi)有找過(guò)Private Sub Command1_Click(

21、)Dim i As Integer,sum As Integer,total As Integersum=0:total=1total表示第幾組i=1List2.Addltem 第+Str(total)+組Do While sumnDo While Not b(i)List2.Addltem a(i)b(i)=Truesum=sum+1LoopIf sumn ThenList2.Addltem 第+Str(total)+組i=1Do While b(i)該循環(huán)用來(lái)查找下一組的開(kāi)始位置i=i+1LoopEnd IfLoopEnd SubPrivate Sub Form_Load()Dim i A

22、s IntegerRandomizeFor i=1 To n產(chǎn)生n個(gè)不一樣的整數(shù),范圍為1,na(i)=Int(Rnd n)+1Do While a(i)=Int(Rnd n)+1LoopNext iFor i=1 To nListl.Addltem a(i)b(i)=FalseNext iEnd SubFunction f(x As Integer,y As Integer) As Boolean該函數(shù)的功能:判斷x和數(shù)組a中前y個(gè)數(shù)有沒(méi)有重復(fù)Dim j As Integerf=FalseFor j=1 To yIf a(j)=x Then f=True:Exit ForNext iEnd

23、Function答案 (1)2(2)i=a(i)total=total+1f(a(i),i-1)或f(a(i),i-1)=True解析 (1)第1組:2,5,4,1;第2組:3。(2)當(dāng)程序的邏輯結(jié)構(gòu)復(fù)雜,函數(shù)較多時(shí),我們最好按照程序的運(yùn)行順序去閱讀代碼,在本題中,我們可以先閱讀Form_Load()和Function f(),生成原始數(shù)據(jù)后,再去閱讀Command1_Click(),才能理順程序的邏輯結(jié)構(gòu)。生成原始數(shù)據(jù)時(shí),要求產(chǎn)生n個(gè)不一樣的整數(shù)存儲(chǔ)在數(shù)組a中,所以每生成一個(gè)隨機(jī)整數(shù)a(i),需要先判斷它是否和數(shù)組a前(i-1)個(gè)元素重復(fù),只有不重復(fù),才能存儲(chǔ)到數(shù)組a中。如何理解“相互占用了

24、位置的數(shù)字”呢?當(dāng)處理數(shù)組a的第i個(gè)元素時(shí),若a(i)=j,表示數(shù)字j占用了位置i,則a(i)和a(j)是同一組元素,我們接下來(lái)去處理第j個(gè)元素,即令i=a(i)。就這樣從一個(gè)元素“跳”到同一組的下一個(gè)元素,直到跳回該組的第一個(gè)元素,由于該組的第一個(gè)元素對(duì)應(yīng)的b(i)=True,退出循環(huán)。6.平面上有N(3N100)個(gè)房間圍成一圈,按順時(shí)針?lè)较蚍謩e編號(hào)為1、2N,相鄰的兩個(gè)房間之間均有一扇門(mén),第i個(gè)房間居住人數(shù)為a(i)。初始時(shí)選擇一個(gè)房間,將所有人都聚集在該房間,接著每個(gè)人都按順時(shí)針?lè)较蜃叩较噜彽姆块g,直到走到居住的房間。一個(gè)人每經(jīng)過(guò)一扇門(mén)花費(fèi)1能量,請(qǐng)確定初始房間,使得所有人花費(fèi)的能量和最小。例如:N=5,a(1)=4,a(2)=7,a(3)=8,a(4)=6,a(5)=4最佳方案:初始時(shí)所有人聚集在2號(hào)房間,花費(fèi)的能量和:7 0+8 1+6 2+4 3+4 4=48。為了解決這個(gè)問(wèn)題,小明編寫(xiě)了一個(gè)VB程序。在窗體加載時(shí),從數(shù)據(jù)庫(kù)中讀取N的值和編號(hào)為1到N的房間的居住人數(shù),人數(shù)存儲(chǔ)在數(shù)組a中。點(diǎn)擊窗體上的按鈕Command1,程序枚舉每一種方案(不同的初始房間),計(jì)算該方案的能量和,在文本框Text1中輸出最優(yōu)方案的初始房間編號(hào),在文本框Te