其他常用算法信息技术选考

21/211．(2019·4月浙江省选考)小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将数组a中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的VB程序段如下，但加框处代码有错，请改正。′待排序数据存储在数组a中(a(1)～a(n))，要求升序排列Fori＝1To(n－1)\2Forj＝1Ton－i*2Ifeq\x(a（j）>a（j＋1）)Then′(1)t＝a(j):a(j)＝a(j＋2):a(j＋2)＝tEndIfNextjNextiFori＝1Ton\2j＝2*i－1Ifa(j)>a(j＋1)Thent＝a(j):a(j)＝a(j＋1):a(j＋1)＝tNextiFori＝eq\x(1Ton)Step2′(2)t＝a(i):j＝i－1DoWhilet<a(j)a(j＋1)＝a(j):j＝j－1Loopa(j＋1)＝tNexti答案(1)a(j)>a(j＋2)(2)3Ton2．(2018·11月浙江选考)某种数据加密方法描述如下(加密前后的数值都是0～255的整数)：•以m个数据为一段，将n个待加密数据依次分割成若干个数据段。剩余数据(个数小于m)为一个独立数据段。•数据段加密规则：数据个数等于m的数据段，先进行值变换，再进行位置变换，得到加密数据段。数据个数小于m的数据段，只进行值变换，直接得到加密数据段。•依次合并加密数据段，即为最后的加密数据。值变换：用值变换密钥数组x(元素个数为m，值为0～255的整数)，将待加密数据段中的数据进行值变换，方法如下：值变换后第i个元素＝(待加密数据段第i个元素＋x(i))Mod256，其中i＝1，2，…，m位置变换：用位置变换密钥数组y(元素个数为m，值为1～m的不重复整数)，将上述值变换后的m个元素进行段内位置变换，方法如下：加密后数据段第y(i)个元素＝值变换后第i个元素，其中i＝1，2，…，m例如，n＝5，m＝3的数据加密过程如下：(1)已知m＝3，数组x与数组y中的数据如下表所示。则待加密数据段“155，1，250”加密后的数据段为________(填数据，用逗号分隔)。x(1)x(2)x(3)102030y(1)y(2)y(3)312(2)小张根据上述加密算法，设计了一个对应的解密程序，其VB代码如下，请在划线处填入合适的代码(解密与加密使用相同的密钥数据)。PrivateSubCommand1_Click()Constn＝100Constm＝6DimiAsInteger，jAsIntegerDima(1Ton)AsInteger，b(1Ton)AsIntegerDimx(1Tom)AsInteger，y(1Tom)AsInteger′读取值变换与位置变换的密钥数据，分别保存在数组x与y中，代码略。′读取待解密数据，保存在数组a中，代码略。′下面进行位置变换：位置变换后数据保存到数组b中Fori＝1To____①____Forj＝1Tom____②____NextjNextiFori＝(n\m)*m＋1Tonb(i)＝a(i)Nexti′下面进行值变换：值变换后数据仍保存到数组b中j＝1Fori＝1Tonb(i)＝____③____j＝j＋1Ifj＞mThenj＝1Nexti′输出解密后数据，代码略。EndSub答案(1)21，24，165(2)①nm或Int(n/m)②b((i－1)*m＋j)＝a((i－1)*m＋y(j))③(b(i)＋256－x(j))Mod256或(b(i)＋256－x((i－1)Modm＋1))Mod256插入排序核心代码也可以从后往前进行插入排序变量i的初值是n－1，一直插入排序，使得第1个数在序。【例1】小明对两个班级的90名同学进行编号，随机产生不同号码，对于其中相同的号码，只保留一个，在号码产生过程中，号码始终是从小号到大号排列，直到找到10个同学号码为止。1)用b数组表示该号码是否产生，b(x)若为0，表示x未产生；2)先产生第1个号码，从第2个开始，产生数x，先判断b(x)的值，如果为0，再去插入到合适位置；3)如果x比前面第一个数大，则直接放入a(i)数组元素中，否则利用对分查找法找到相应位置；4)从该数x应该存放的位置开始的数据向后移动，并把该数x存放起来。单击“产生”按钮Command1，在列表框List1中输出每次产生的号码。请在划线处填入合适的代码。Dima(10)AsInteger,b(100)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,xAsInteger,sAsStringa(1)＝Int(Rnd()*90＋1):b(a(1))＝1①____DoWhilei<＝10x＝Int(Rnd()*90＋1)Ifb(x)＝0ThenIf____②____Thena(i)＝xElsewz＝seach(i,x)Fork＝i－1TowzStep－1a(k＋1)＝a(k)Nextk____③____EndIfb(x)＝1:s＝“产生前”＋Str(i)＋“个号码是：”Forj＝1Tois＝s＋Str(a(j))NextjList1.AddItemsi＝i＋1EndIfLoopEndSubFunctionseach(pAsInteger,xAsInteger)AsIntegerDimmAsInteger,jAsIntegerm＝Int(p/2)If______④____Thenj＝m＋1DoWhilea(j)<xj＝j＋1LoopElseIfm＝1Thenj＝1Elsej＝m－1DoWhilea(j)>xAndj>＝1j＝j－1Loopj＝j＋1EndIfseach＝jEndFunction答案①i＝2②x>a(i－1)③a(k＋1)＝x④a(m)<x【变式训练1】在编号为1－100的观众中随机产生10位不同的幸运观众，并将幸运观众的编号升序排列。请在划线处填入合适的代码。n＝10:a(1)＝Int(Rnd*100＋1)i＝2DoWhilei<＝nt＝Int(Rnd*100＋1)Forj＝1Toi－1Ifa(j)＝tThenExitForNextjIf____①____ThenForj＝i－1To1Step－1Ifa(j)>tThena(j＋1)＝a(j)ElseExitForNextj____②____i＝i＋1EndIfLoop答案①i＝j②a(j＋1)＝t约瑟夫环问题约瑟夫环是一个数学的应用问题：已知n个人(以编号1，2，3……n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。在生活中会碰到类似很多问题，如钟表走向、值日的轮值等。一、以24小时制式计算(0点－23点)，完成如下表格t的初值经历时长(n)结果时间统一表达式t＝3时13小时后16时(t＋n)Mod2423小时后2时t＝15时－3小时后12时(t＋n＋24)Mod24－18小时后21时二、将字母表的字母A替换为E，B替换为F，C替换为G，…，W替换为A，X替换为B，…对于环的操作一般用Mod运算符进行计算，某个数Modn的范围是[0，n－1]，其他下标必须从0开始编号。若要实现从1开始编号，需把编号减去1，进行运算后，再加上1。对于任意字母表中第t个位置的字母加密后的表达式为(t－1＋4)Mod26＋1。如字母w在字母表中处于第23，代入以上公式，加密后为第1个位置。字符ch转换的表达式是Chr((Asc(ch)－1＋4)Mod26＋1)。也可以用以下自定义函数来实现大写字母x向后移动y个位置的功能FunctionRun(xAsString,yAsInteger)AsStringDimansAsIntegerans＝Asc(x)－65ans＝(ans＋y)Mod26Run＝Chr(ans＋65)EndFunction同理，例如对于一个m行乘以n列的矩阵，第i个位置元素所处的列数为(i－1)Modn＋1。所处行为(i－1)\n+1。【例2】字符环上的最长公共字符串。将字符串首尾相接后可以得到一个环，如图1和图2分别是由字符串“ABCUVKLM”和“MADJKLUVKL”首尾相接后得到的环。在图1和图2所示的两个环中，最长的公共字符串为“UVKLMA”(图中带背景圆圈表示)。编写VB程序，实现如下功能：在文本框Text1和Text2中分别输入一个字符串(仅由大写字母构成，每个字符串长度不超过100)，单击命令按钮Command1后，在标签Label3中输出两个字符串构成的环的最长公共字符串长度(字符串在环中必须连续)。程序运行效果如图所示。实现上述功能的VB程序如下，请回答下列问题：(1)根据题意描述，字符串“BCEFGK”和“GKBLMCKEF”的最长公共字符串长度为________。(2)请在划线处填入合适的代码。Functiongetmin(aAsInteger,bAsInteger)′获取两个整数的较小者Ifa<bThengetmin＝aElsegetmin＝bEndFunctionPrivateSubCommand1_Click()Dims1AsString,s2AsString,iAsInteger,jAsInteger,xAsInteger,yAsIntegerDimcntAsInteger,ansAsInteger,len1AsInteger,len2AsIntegers1＝Text1.Texts2＝Text2.Textlen1＝Len(s1)len2＝Len(s2)minlen＝____①____′minlen中保存s1和s2中较短字符串的长度ans＝0Fori＝1Tolen1Forj＝1Tolen2cnt＝0:x＝i:y＝jDoWhile____②____Andcnt<minlencnt＝cnt＋1x＝xModlen1＋1y＝yModlen2＋1LoopIf____③____Thenans＝cntNextjNextiLabel3.Caption＝Str(ans)EndSub答案(1)5(2)①getmin(len1,len2)②Mid(s1，x，1)＝Mid(s2，y，1)③cnt>ans【变式训练2】编写VB程序，实现如下功能：在文本框Text1中输入当天对应的星期，文本框Text2中输入天数，单击“推算”按钮Command1，推算出相应天数后的星期情况，并在标签Label1中输出结果。界面如图所示。(1)为实现上述功能，请在划线处填入合适的代码。PrivateSubCommand1_Click()DimxAsString,xqAsString,numAsIntegerDimiAsInteger,hAsIntegerx＝“日一二三四五六”xq＝Text1.Texti＝1num＝Val(Text2.Text)Fori＝1ToLen(x)Ifxq＝Mid(x,i,1)Thenh＝i:ExitForNexti_____①____Label1.Caption＝“星期”＋Mid(x,r,1)EndSub(2)若当天是“星期五”，在文本框Text2中输入“166”，单击“推算”按钮后，标签Label1中显示的内容是________。答案(1)①r＝(h＋num－1)Mod7＋1(2)星期三一、选择题1．有如下VB程序段：Fori＝4To3Step－1Ifa(i)<a(i－1)Thentmp＝a(i)Forj＝i－1To1Step－1Iftmp>a(j)ThenExitFora(j＋1)＝a(j)Nextja(j＋1)＝tmpEndIfNexti数组元素a(1)到a(6)的值依次为“19，8，96，92，85，88”，经过该程序段“加工”后，数组元素a(1)到a(6)的值依次为()A．8，19，92，96，85，88 B．8，19，85，88，92，96C．19，8，92，96，85，88 D．19，8，85，92，96，88答案C2．小张编写程序，实现把数据temp插入到升序序列中，得到一个新的升序序列，原升序序列各元素已依次存放在数组元素a(1)、a(2)、a(3)、……、a(n)中。他编写的VB程序段如下：Iftemp>＝a(n)Thena(n＋1)＝tempElsej＝nDoWhilej>＝1Andtemp<a(j)____①____j＝j－1Loop____②____EndIf要使程序实现上述功能，则方框①②中的语句分别是()A．①a(j＋1)＝a(j)②a(j＋1)＝tempB．①a(j)＝a(j－1)②a(j＋1)＝tempC．①a(j＋1)＝a(j)②a(j)＝tempD．①a(j)＝a(j－1)②a(j)＝temp答案A3．某VB程序段如下：s＝”Abc”i＝Len(s)DoWhilei>＝1ch＝Mid(s,i,1)t＝(Asc(ch)Mod32＋4)Mod26s1＝s1＋Chr(t＋65)i＝i－1LoopText1.Text＝s1该程序段执行后，在文本框Text1中显示的内容是()A．HGF B．Hgf C．FGH D．Fgh答案C二、非选择题4．对一段字符(仅包含大小写字母和数字)加密，加密规则为：①字母和数字都往后循环顺移3位，如“a”变为“d”，“y”变为“b”；“0”变为“3”，“7”变为“0”，②加密后字母在前，数字在后，③字母按逆序排列，数字按顺序排列，如输入明文“a1b7Z8x3”，密文为“aCed4016”。(1)根据程序代码分析，“加密”按钮的名称是__________。(2)根据加密规则，明文“9G78fbY5”，则密文为________。(3)请在划线处填入合适的代码：PrivateSubCom_jm_Click()DimxAsString,chAsString,c1AsStringDims1AsString,s2AsString,sAsStringDimiAsInteger,nAsInteger,yAsIntegerx＝Text1.Textn＝Len(x)Fori＝1Tonch＝Mid(x,i,1)Ifch>＝”0”Andch<＝”9”Then____①____s2＝s2&Str(y)ElseIfch>＝”a”Andch<＝”z”Theny＝(Asc(ch)－Asc(”a”)＋3)Mod26____②____s1＝c1＋s1Elsey＝(Asc(ch)－Asc(”A”)＋3)Mod26c2＝Chr(Asc(”A”)＋y)s1＝c2＋s1EndIfNexti____③____Text2.Text＝sEndSub答案(1)Com_jm(2)Beij2018(3)①y＝(Val(ch)＋3)Mod10②c1＝Chr(Asc(”a”)＋y)③s＝s1＋s25．小王编写了一个VB程序，该程序的功能是：有15个数形成环状，现要分别找出3个相邻的数，使其相加之和最大或最小。如15个数依次为：18，14，42，61，13，19，14，13，28，52，61，58，30，则相邻三数之和最大为62(30＋18＋14)，相邻三数之和最小为31(4＋26＋1)。程序运行时，先随机生成15个[1，30]区间内的整数，存储在数组a(0)至a(14)中，并在文本框Text1中显示；单击“计算”按钮Command1，则在标签Label4中显示连续三数最大和，在标签Label5中显示连续三数最小和，程序运行界面如图所示。实现上述功能的VB程序如下，请在划线处填入合适的代码。Constn＝14Dima(n)AsIntegerPrivateSubFormLoad()′随机生成15个数，存储在数组元素a(0)～a(14)中，并显示在文本框Text1中EndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsIntegerDimimaxAsInteger,iminAsIntegerDimsmaxAsInteger,sumAsInteger,sminAsIntegersmax＝0:smin＝100Fori＝0To14j＝____①____k＝____②____sum＝a(i)＋a(j)＋a(k)Ifsum>smaxThensmax＝sumimax＝iEndIfIfsum<sminThensmin＝sumimin＝iEndIfNextiLabel4.Caption＝Str(smax)Label5.Caption＝Str(smin)EndSub答案①(i＋1)Mod15②(i＋2)Mod156．小李同学碰到了一个数学问题：400个同学按顺序进行编号后围成一个大圈，按1至2报数(从1号位置开始)，报到2的同学出列，以此一直循环报数下去，问最后剩下的那位同学他的编号是几号？例如以6个同学编号为例，按1至2报数(从1号位置开始)依次出列的编号次序为2－4－6－3－1－5，那么最后剩下的就是编号为5的同学。为了解决这个问题，小李用VB编写了如下程序尝试解决，其中列表List1显示出列的顺序编号，文本框Text1中显示最后留下的编号，程序代码如下：请在划线处填入合适的代码。PrivateSubCommand1_Click()Dims,f,tAsIntegerDima(1To400)AsBooleanFori＝1To400a(i)＝FalseNextis＝0：f＝0：i＝0DoWhilef<399i＝i＋1Ifi＝401Theni＝____①____Ifa(i)＝FalseThens＝s＋1Ifs＝2Then____②____List1.AddItemStr(i)a(i)＝Truef＝____③____EndIfLoopFori＝1To400Ifa(i)＝FalseThenText1.Text＝Str(i)NextiEndSub答案①1②s＝0③f＋17．平面上有N(3≤N≤100)个房间围成一圈，按顺时针方向分别编号为1…N，相邻的两个房间之间均有一扇门，第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中输出最优方案的初始房间编号，在文本框Text2中输出最小能量和。实现上述功能的VB代码如下，请在划线处填入合适的代码。Dima(1To100)AsInteger′依次存储编号为1到100的房间的居住人数PrivateSubForm_Load()′本过程从数据库中读取N的值和每个房间居住人数，存储在数组a中′代码略EndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,wAsInteger,kasIntegerDimtAsLong,ansAsLongk＝0：ans＝32767′ans初始化为最大的Integer数据Fori＝1Tont＝0Forj＝0Ton－1w＝____①____Ifw＝0Thenw＝nt＝____②____NextjIft<ansThenk＝i：ans＝tNextiText1.Text＝Str(k)′起始房间编号Text2.Text＝Str(ans)EndSub答案①(i＋j)Modn②t＋a(w)*j8．数组a中存储n个2位正整数，从倒数第2个数开始，利用对分查找的思想，找到他所在位置，并插入到位置中，实现整个数组有序。实现该功能的VB程序如下：Constn＝100Dima(n)AsIntegerPrivateSubForm_Load()′产生n个2位正整数，并显示在文本框Text1中，代码略EndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,leftAsIntegerDimrightAsInteger,mAsInteger,tAsIntegeri＝n－1DoWhilei>＝1eq\x(left＝1)right＝nt＝a(i)DoWhileleft<＝rightm＝Int((left＋right)/2)Ifa(m)＝tThenright＝m:ExitDoIfa(m)<tThenleft＝m＋1Elseright＝m－1EndIfLoopForj＝iToright－1a(j)＝a(j＋1)Nextj____①____i＝i–1s＝””Forj＝1Tons＝s＋Str(a(j))NextjList1.AddItemsLoopEndSub(1)语句“List1.AddItems”中的AddItem是________。(单选，填字母：A.对象名/B.属性名/C.事件名/D.方法名)(2)程序代码中，加框处有错，请改正。(3)程序代码中，将①处语句补充完整。(4)若删除语句“Ifa(m)＝tThenright＝m:ExitDo”，则下列说法正确的是__________(单选，选填字母：A.程序进入死循环，无法正常运行/B.输出排序的结果不变/C.输出排序的结果将改变)。答案(1)D(2)left＝i＋1(3)①a(right)＝t(4)B9．某8位日期加密授权码生成方法描述如下：①授权码由9位字符组成，前8位为日期的密文，最后1位为验证码；②日期的最后1位数字k(若k的值为0，令k＝10)，加密成26个大字英语字母表中该位置对应的字母。③将26