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

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

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

3、于49,又再將49右移一個位置,這時再將11與r(0)的值比較,11r(0),它的插入位置就是r(1)。假設(shè)11大于第一個值r(1),它的插入位置應(yīng)該在r(1)和r(2)之間,由于60已經(jīng)右移了,留出來的位置正好留給11,后面的數(shù)據(jù)依照同樣的方法逐個插入到該有序序列中。若數(shù)據(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答案；這是一個插入排序的算法,a(0)是待插入的數(shù)據(jù)。在do循環(huán)中,把小于待插入數(shù)a(0)的元素往后移動,最后留出空位存放a(0),說明這是一個降序方式的插入排序算法,所以,a(1)中存放的是最大值18。故選B課后作業(yè)1.n個人排成一個圓圈,然后把這n個人按逆時針方向分別編號為1、2、n。從編號為1的人開始按逆時針計數(shù),當某人計數(shù)為m的倍數(shù)時,該人出圈;如此循環(huán)下去,直到圈中只有一個人留下?，F(xiàn)用VB6制作一個模擬報數(shù)出列的程序,程序界面如下圖所示:在文本框Text1中輸入人數(shù)n,在文本框Text2中輸入出列號m,單擊按鈕模擬報數(shù)Command1,在列表框List1中顯示出

5、列順序編號,程序界面如下。實現(xiàn)上述功能的VB 代碼如下, 請在劃線處填入合適代碼。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解析: 模擬報數(shù)是一種典型的線性表應(yīng)用,程序中使用一維數(shù)組表示鏈表,數(shù)組元素下標即編號。算法思想是:先設(shè)數(shù)組a的每個元素值為1;然后從第1個元素開始累加,累加結(jié)果存入變量t,當累加到j(luò)號元素時如果t值為3,則置a(j)=0,即j號出列,出列人數(shù)加1,一直到出列人數(shù)為n時結(jié)束,此時的j值即為最后剩下的編號。所以劃線處是把每個元素的值設(shè)為1,表示未出列,可填入語句a(i)=1。處計算本次輪到的元素下標,可填入j = j Mod n + 1,也可以是if j=n then n=1 e

7、lse j=j+1。2.利用VB程序?qū)山M成績數(shù)據(jù)合并為一組并按成績從高到低排列輸出。成績相同時,第一批學(xué)生優(yōu)先輸出。實現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯,請改正:Dim xm(1 to 1000) as string存儲學(xué)生姓名Dim cj(1 to 1000) as integer存儲學(xué)生成績Private Sub Form_Load()該處具體代碼省略從數(shù)據(jù)庫讀取兩批學(xué)生數(shù)據(jù)第1批學(xué)生的人數(shù)rs1,按成績從高到低的順序?qū)⒊煽兇嫒隿j(1)、cj(2)cj(rs1)中,姓名存入xm(1)、xm(2)xm(rs1)中,第2批人數(shù)rs2,按成績從高到低的順序?qū)⒊煽兇嫒隿j(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以下程序開始按成績高低逐個輸出,每次輸出前后兩段中,尚未處理的學(xué)生中成績最高的n=1Do While i=rs1 And j=cj(j) Thenk=i:i=i+1Elsek=j:j=j+1End IfList1.AddItem(第+Str(n)+名+xm(k)+成績:+Str(cj(k)LoopDo While i=rs1剩下第一段還有未輸出的,逐個輸出n=n+1List1.AddItem

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

10、劃分為兩段,并將序列a的前t個數(shù)與后n-t個數(shù)對調(diào),且保持這兩段(t個數(shù)和n-t個數(shù))之間的相對位置不變(即t個數(shù)和n-t個數(shù)各自有序)。例如,長度為6的有序序列38、42、59、61、69、78,當t=2時重排結(jié)果為59、61、69、78、38、42。程序運行時產(chǎn)生n個整數(shù)存儲在數(shù)組a中,在文本框Text1中輸入t,單擊“對調(diào)”按鈕Command1,在列表框List2輸出t個數(shù)與n-t個數(shù)對調(diào)后的數(shù)字序列。為了實現(xiàn)上述功能,請在劃線處填入合適的代碼。Const n=10Dim a(1 To 10) As IntegerPrivate Sub Form_Load()生成n個有序數(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解析 很簡單,根據(jù)題目意思,要將有序數(shù)組a分成兩段,對換位置,首先要讀入數(shù)據(jù)t,所以答案是t=Val(Text

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

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

14、Private Sub Command1_Click()Dim team(1 To 20) As String存儲各隊伍編號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存儲比賽編排的隊伍總數(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固定編號1,其余隊伍逆時針移動一個位置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來存儲隊伍的編號,初始的時候team(i)的值就是i,用模擬法來分析算法,以6個隊伍為例,初始編號為1、2、3、4、5、6,程序始終以位置1-6、2-5、3-4的值來組成對陣表

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

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

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

20、a(i),認為數(shù)字i在正確的位置上。若干個相互占用了位置的數(shù)字稱為一組,一個在正確位置上的數(shù)字單獨為一組,比如6個數(shù)字2,3,1,4,6,5分別保存在數(shù)組元素a(1)到a(6)中,則2、3、1為一組,4為一組,6、5為一組。該程序的功能為輸出每組的情況。運行界面如下圖:(1)數(shù)組元素a(1)到a(5)的值分別為2、5、3、1、4,這5個元素總共有組。(2)請在劃線處填入合適的代碼。Const n=10Dim a(1 To n) As Integer保存原始數(shù)據(jù)Dim b(1 To n) As Boolean數(shù)組b用來標記相應(yīng)的位置有沒有找過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)用來查找下一組的開始位置i=i+1LoopEnd IfLoopEnd SubPrivate Sub Form_Load()Dim i A

22、s IntegerRandomizeFor i=1 To n產(chǎn)生n個不一樣的整數(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個數(shù)有沒有重復(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)當程序的邏輯結(jié)構(gòu)復(fù)雜,函數(shù)較多時,我們最好按照程序的運行順序去閱讀代碼,在本題中,我們可以先閱讀Form_Load()和Function f(),生成原始數(shù)據(jù)后,再去閱讀Command1_Click(),才能理順程序的邏輯結(jié)構(gòu)。生成原始數(shù)據(jù)時,要求產(chǎn)生n個不一樣的整數(shù)存儲在數(shù)組a中,所以每生成一個隨機整數(shù)a(i),需要先判斷它是否和數(shù)組a前(i-1)個元素重復(fù),只有不重復(fù),才能存儲到數(shù)組a中。如何理解“相互占用了

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