其他典型算法之线性表的应用-专项训练浙江2022届选考专用（教师版）

1、其他典型算法之线性表的应用【例1】 在一升序数组a中插入一个数x,使数组元素仍保持升序。解决该问题的VB程序段如下,在处应填入的正确语句以实现功能。i=nn为数组a中的元素个数do while i0 and a(i)xi=i-1loopa(i+1)=x答案:a(i+1)=a(i)解析:这是在一线性表中插入一元素的问题,该算法的基本方法是先找到数据插入的位置i,把原有元素a(i)、a(i+1)、a(i+2)a(n)依次移到表中的第i+1、i+2、i+3n+1个位置,以便腾出一个空位置i,再把新元素存入到该位置上。本程序的循环部分即完成了位置的查找和原数据后移的功能,因此划线处应填入的语句是a(i

2、+1)=a(i)。【例2】插入排序的基本思想是:把待排序的数据按其值的大小逐个插入到一个已经排好序的有序序列中,直到所有的数据插入完为止,得到一个新的有序序列。例如,已知待排序的一组数据是60,71,49,11,24,3,66。假设在排序过程中,前3个数据已完成升序排列,构成一个有序序列49,60,71。将待排序数据中的第4个数据(即11)插入上述有序序列,以得到一个新的含4个数据的有序序列。首先,应找到11的插入位置,再进行插入。可以将11放入数组的第一个元素r(0)中,这个元素称为监视哨,然后从71起从右到左查找,11小于71,将71右移一个位置,11小于60,又将60右移一个位置,11小

3、于49,又再将49右移一个位置,这时再将11与r(0)的值比较,11r(0),它的插入位置就是r(1)。假设11大于第一个值r(1),它的插入位置应该在r(1)和r(2)之间,由于60已经右移了,留出来的位置正好留给11,后面的数据依照同样的方法逐个插入到该有序序列中。若数据有n个,须进行n-1趟排序,才能完成。以下VB程序执行后,数组元素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)是待插入的数据。在do循环中,把小于待插入数a(0)的元素往后移动,最后留出空位存放a(0),说明这是一个降序方式的插入排序算法,所以,a(1)中存放的是最大值18。故选B课后作业1.n个人排成一个圆圈,然后把这n个人按逆时针方向分别编号为1、2、n。从编号为1的人开始按逆时针计数,当某人计数为m的倍数时,该人出圈;如此循环下去,直到圈中只有一个人留下。现用VB6制作一个模拟报数出列的程序,程序界面如下图所示:在文本框Text1中输入人数n,在文本框Text2中输入出列号m,单击按钮模拟报数Command1,在列表框List1中显示出

5、列顺序编号,程序界面如下。实现上述功能的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解析: 模拟报数是一种典型的线性表应用,程序中使用一维数组表示链表,数组元素下标即编号。算法思想是:先设数组a的每个元素值为1;然后从第1个元素开始累加,累加结果存入变量t,当累加到j号元素时如果t值为3,则置a(j)=0,即j号出列,出列人数加1,一直到出列人数为n时结束,此时的j值即为最后剩下的编号。所以划线处是把每个元素的值设为1,表示未出列,可填入语句a(i)=1。处计算本次轮到的元素下标,可填入j = j Mod n + 1,也可以是if j=n then n=1 e

7、lse j=j+1。2.利用VB程序将两组成绩数据合并为一组并按成绩从高到低排列输出。成绩相同时,第一批学生优先输出。实现上述功能的VB代码如下,但加框处代码有错,请改正:Dim xm(1 to 1000) as string存储学生姓名Dim cj(1 to 1000) as integer存储学生成绩Private Sub Form_Load()该处具体代码省略从数据库读取两批学生数据第1批学生的人数rs1,按成绩从高到低的顺序将成绩存入cj(1)、cj(2)cj(rs1)中,姓名存入xm(1)、xm(2)xm(rs1)中,第2批人数rs2,按成绩从高到低的顺序将成绩存入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以下程序开始按成绩高低逐个输出,每次输出前后两段中,尚未处理的学生中成绩最高的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循环语句中,先对n加1,再输出名次,所以n的初值应为0。变量j第二段成绩的位置,第二段成绩到rs1+rs2为止,所以处循环条件应为j=rs1+rs2。3.编写一个VB程序,将一个长度为n的有序序列a(1)、a(2)、a(n),以整数t(1tn)将该有序序列

10、划分为两段,并将序列a的前t个数与后n-t个数对调,且保持这两段(t个数和n-t个数)之间的相对位置不变(即t个数和n-t个数各自有序)。例如,长度为6的有序序列38、42、59、61、69、78,当t=2时重排结果为59、61、69、78、38、42。程序运行时产生n个整数存储在数组a中,在文本框Text1中输入t,单击“对调”按钮Command1,在列表框List2输出t个数与n-t个数对调后的数字序列。为了实现上述功能,请在划线处填入合适的代码。Const n=10Dim a(1 To 10) As IntegerPrivate Sub Form_Load()生成n个有序数,显示在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解析 很简单,根据题目意思,要将有序数组a分成两段,对换位置,首先要读入数据t,所以答案是t=Val(Text

12、1.Text)。程序为了实现数组a的1t位置和t+1n位置的互换,使用双重循环来解决这个问题,具体做法是:第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);如此重复,直到最后一轮(i=n),把a(t)a(n-1)依次后移一个位置,再把a(n)存入a(t)。所以程序第2空应该完成j-1位置到j位置的数据移动,答案是a(j)=a(j-1)。当完成t个数据的移动后,a(j)应该等于原来存放在temp中的a(i)的值,所以答案是temp。4.单循环赛制是一种较为公平合理的比

13、赛制度,比赛过程中所有参赛队伍均能相遇一次。其秩序编排可采用“逆时针轮转方法”:数字1n依次作为队伍编号,把编号按U型走向分成均等两边(若n为奇数,则在末尾增加编号0,使总数为偶数),即可得到第一轮的比赛秩序,例如,5个队伍的比赛编排情况如图a所示;第二轮,固定编号1,其余编号均按逆时针方向移动一个位置,即为该轮比赛秩序;以后各轮比赛秩序以此类推,与编号0对阵的表示本轮轮空。现用VB程序实现上述功能:在文本框Text1中输入参赛队伍数n,单击“编排”按钮Command1,在列表框List1中输出每轮比赛秩序。程序运行效果如图b所示。图a图b实现上述功能的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存储比赛编排的队伍总数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)解析 程序以数组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,依次类推。根据算法描述,以6个队伍来模拟的话,两个对阵的队伍对阵始终以数组team的1-6、2-5、3-4位置的值,下标之和是7(即c+1),所以与team(j)对阵的应该是team(c-j+1)。固定编号1,其余队伍移动的时候,先把最后一个位置的值拿出来存放到temp,把数组team的2到c-1位置的值逐个往后移动,存储到3到c的位置,由于本程序用的是c到2的循环,当j=c的时候,应该

17、是把c-1位置的值存储到c位置,j=2时,应该是把2位置的值存储到3位置,所以程序应改成team(j)=team(j-1)。4.小李同学碰到了一个数学问题:400个同学按顺序进行编号后围成一个大圈,按1至2报数(从1号位置开始),报到2的同学出列,以此一直循环报数下去,问最后剩下的那位同学他的编号是几号?例如以6个同学编号为例,按1至2报数(从1号位置开始)依次出列的编号次序为2-4-6-3-1-5,那么最后剩下的就是编号为5的同学。为了解决这个问题,小李用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的报数,报到2的就出列,直到剩下最后一位同学,定义一个a数组,元素的初值均为false,表示游戏一开始时所有学生全未出列,亦即开始时全在列。设置变量s初值为零,接着从1号开始两个两个的数,只要计数器s等于2,当前这位报到2的就出列,数组a当前元素值变为True,表示该位同学出列,计数器s重置为零,计数器f表示到当前为止已经出列的人数,以此一直循环到只剩下一位同学,f的最大值为399,a(289)=false最后剩下289号同学。5.有n个互不重复的数字,值的范围是1,n,分别保存在数组元素a(1)到a(n)中,如果数字i保存在

20、a(i),认为数字i在正确的位置上。若干个相互占用了位置的数字称为一组,一个在正确位置上的数字单独为一组,比如6个数字2,3,1,4,6,5分别保存在数组元素a(1)到a(6)中,则2、3、1为一组,4为一组,6、5为一组。该程序的功能为输出每组的情况。运行界面如下图:(1)数组元素a(1)到a(5)的值分别为2、5、3、1、4,这5个元素总共有组。(2)请在划线处填入合适的代码。Const n=10Dim a(1 To n) As Integer保存原始数据Dim b(1 To n) As Boolean数组b用来标记相应的位置有没有找过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)该循环用来查找下一组的开始位置i=i+1LoopEnd IfLoopEnd SubPrivate Sub Form_Load()Dim i A

22、s IntegerRandomizeFor i=1 To n产生n个不一样的整数,范围为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该函数的功能:判断x和数组a中前y个数有没有重复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)当程序的逻辑结构复杂,函数较多时,我们最好按照程序的运行顺序去阅读代码,在本题中,我们可以先阅读Form_Load()和Function f(),生成原始数据后,再去阅读Command1_Click(),才能理顺程序的逻辑结构。生成原始数据时,要求产生n个不一样的整数存储在数组a中,所以每生成一个随机整数a(i),需要先判断它是否和数组a前(i-1)个元素重复,只有不重复,才能存储到数组a中。如何理解“相互占用了

24、位置的数字”呢?当处理数组a的第i个元素时,若a(i)=j,表示数字j占用了位置i,则a(i)和a(j)是同一组元素,我们接下来去处理第j个元素,即令i=a(i)。就这样从一个元素“跳”到同一组的下一个元素,直到跳回该组的第一个元素,由于该组的第一个元素对应的b(i)=True,退出循环。6.平面上有N(3N100)个房间围成一圈,按顺时针方向分别编号为1、2N,相邻的两个房间之间均有一扇门,第i个房间居住人数为a(i)。初始时选择一个房间,将所有人都聚集在该房间,接着每个人都按顺时针方向走到相邻的房间,直到走到居住的房间。一个人每经过一扇门花费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程序。在窗体加载时,从数据库中读取N的值和编号为1到N的房间的居住人数,人数存储在数组a中。点击窗体上的按钮Command1,程序枚举每一种方案(不同的初始房间),计算该方案的能量和,在文本框Text1中输出最优方案的初始房间编号,在文本框Te