其他常用算法信息技術(shù)選考

21/211．(2019·4月浙江省選考)小明基于冒泡排序思想設(shè)計了一個改進(jìn)的排序算法。該算法先用冒泡法將數(shù)組a中奇數(shù)位置的元素、偶數(shù)位置的元素分別進(jìn)行排序，然后再進(jìn)行后續(xù)處理。算法的VB程序段如下，但加框處代碼有錯，請改正?！浯判驍?shù)據(jù)存儲在數(shù)組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(luò)－1Loopa(j＋1)＝tNexti答案(1)a(j)>a(j＋2)(2)3Ton2．(2018·11月浙江選考)某種數(shù)據(jù)加密方法描述如下(加密前后的數(shù)值都是0～255的整數(shù))：?以m個數(shù)據(jù)為一段，將n個待加密數(shù)據(jù)依次分割成若干個數(shù)據(jù)段。剩余數(shù)據(jù)(個數(shù)小于m)為一個獨(dú)立數(shù)據(jù)段。?數(shù)據(jù)段加密規(guī)則：數(shù)據(jù)個數(shù)等于m的數(shù)據(jù)段，先進(jìn)行值變換，再進(jìn)行位置變換，得到加密數(shù)據(jù)段。數(shù)據(jù)個數(shù)小于m的數(shù)據(jù)段，只進(jìn)行值變換，直接得到加密數(shù)據(jù)段。?依次合并加密數(shù)據(jù)段，即為最后的加密數(shù)據(jù)。值變換：用值變換密鑰數(shù)組x(元素個數(shù)為m，值為0～255的整數(shù))，將待加密數(shù)據(jù)段中的數(shù)據(jù)進(jìn)行值變換，方法如下：值變換后第i個元素＝(待加密數(shù)據(jù)段第i個元素＋x(i))Mod256，其中i＝1，2，…，m位置變換：用位置變換密鑰數(shù)組y(元素個數(shù)為m，值為1～m的不重復(fù)整數(shù))，將上述值變換后的m個元素進(jìn)行段內(nèi)位置變換，方法如下：加密后數(shù)據(jù)段第y(i)個元素＝值變換后第i個元素，其中i＝1，2，…，m例如，n＝5，m＝3的數(shù)據(jù)加密過程如下：(1)已知m＝3，數(shù)組x與數(shù)組y中的數(shù)據(jù)如下表所示。則待加密數(shù)據(jù)段“155，1，250”加密后的數(shù)據(jù)段為________(填數(shù)據(jù)，用逗號分隔)。x(1)x(2)x(3)102030y(1)y(2)y(3)312(2)小張根據(jù)上述加密算法，設(shè)計了一個對應(yīng)的解密程序，其VB代碼如下，請在劃線處填入合適的代碼(解密與加密使用相同的密鑰數(shù)據(jù))。PrivateSubCommand1_Click()Constn＝100Constm＝6DimiAsInteger，jAsIntegerDima(1Ton)AsInteger，b(1Ton)AsIntegerDimx(1Tom)AsInteger，y(1Tom)AsInteger′讀取值變換與位置變換的密鑰數(shù)據(jù)，分別保存在數(shù)組x與y中，代碼略。′讀取待解密數(shù)據(jù)，保存在數(shù)組a中，代碼略。′下面進(jìn)行位置變換：位置變換后數(shù)據(jù)保存到數(shù)組b中Fori＝1To____①____Forj＝1Tom____②____NextjNextiFori＝(n\m)*m＋1Tonb(i)＝a(i)Nexti′下面進(jìn)行值變換：值變換后數(shù)據(jù)仍保存到數(shù)組b中j＝1Fori＝1Tonb(i)＝____③____j＝j(luò)＋1Ifj＞mThenj＝1Nexti′輸出解密后數(shù)據(jù)，代碼略。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插入排序核心代碼也可以從后往前進(jìn)行插入排序變量i的初值是n－1，一直插入排序，使得第1個數(shù)在序?！纠?】小明對兩個班級的90名同學(xué)進(jìn)行編號，隨機(jī)產(chǎn)生不同號碼，對于其中相同的號碼，只保留一個，在號碼產(chǎn)生過程中，號碼始終是從小號到大號排列，直到找到10個同學(xué)號碼為止。1)用b數(shù)組表示該號碼是否產(chǎn)生，b(x)若為0，表示x未產(chǎn)生；2)先產(chǎn)生第1個號碼，從第2個開始，產(chǎn)生數(shù)x，先判斷b(x)的值，如果為0，再去插入到合適位置；3)如果x比前面第一個數(shù)大，則直接放入a(i)數(shù)組元素中，否則利用對分查找法找到相應(yīng)位置；4)從該數(shù)x應(yīng)該存放的位置開始的數(shù)據(jù)向后移動，并把該數(shù)x存放起來。單擊“產(chǎn)生”按鈕Command1，在列表框List1中輸出每次產(chǎn)生的號碼。請在劃線處填入合適的代碼。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＝“產(chǎn)生前”＋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(luò)＋1LoopElseIfm＝1Thenj＝1Elsej＝m－1DoWhilea(j)>xAndj>＝1j＝j(luò)－1Loopj＝j(luò)＋1EndIfseach＝j(luò)EndFunction答案①i＝2②x>a(i－1)③a(k＋1)＝x④a(m)<x【變式訓(xùn)練1】在編號為1－100的觀眾中隨機(jī)產(chǎn)生10位不同的幸運(yùn)觀眾，并將幸運(yùn)觀眾的編號升序排列。請在劃線處填入合適的代碼。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(luò)②a(j＋1)＝t約瑟夫環(huán)問題約瑟夫環(huán)是一個數(shù)學(xué)的應(yīng)用問題：已知n個人(以編號1，2，3……n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。在生活中會碰到類似很多問題，如鐘表走向、值日的輪值等。一、以24小時制式計算(0點(diǎn)－23點(diǎn))，完成如下表格t的初值經(jīng)歷時長(n)結(jié)果時間統(tǒng)一表達(dá)式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，…對于環(huán)的操作一般用Mod運(yùn)算符進(jìn)行計算，某個數(shù)Modn的范圍是[0，n－1]，其他下標(biāo)必須從0開始編號。若要實(shí)現(xiàn)從1開始編號，需把編號減去1，進(jìn)行運(yùn)算后，再加上1。對于任意字母表中第t個位置的字母加密后的表達(dá)式為(t－1＋4)Mod26＋1。如字母w在字母表中處于第23，代入以上公式，加密后為第1個位置。字符ch轉(zhuǎn)換的表達(dá)式是Chr((Asc(ch)－1＋4)Mod26＋1)。也可以用以下自定義函數(shù)來實(shí)現(xiàn)大寫字母x向后移動y個位置的功能FunctionRun(xAsString,yAsInteger)AsStringDimansAsIntegerans＝Asc(x)－65ans＝(ans＋y)Mod26Run＝Chr(ans＋65)EndFunction同理，例如對于一個m行乘以n列的矩陣，第i個位置元素所處的列數(shù)為(i－1)Modn＋1。所處行為(i－1)\n+1?！纠?】字符環(huán)上的最長公共字符串。將字符串首尾相接后可以得到一個環(huán)，如圖1和圖2分別是由字符串“ABCUVKLM”和“MADJKLUVKL”首尾相接后得到的環(huán)。在圖1和圖2所示的兩個環(huán)中，最長的公共字符串為“UVKLMA”(圖中帶背景圓圈表示)。編寫VB程序，實(shí)現(xiàn)如下功能：在文本框Text1和Text2中分別輸入一個字符串(僅由大寫字母構(gòu)成，每個字符串長度不超過100)，單擊命令按鈕Command1后，在標(biāo)簽Label3中輸出兩個字符串構(gòu)成的環(huán)的最長公共字符串長度(字符串在環(huán)中必須連續(xù))。程序運(yùn)行效果如圖所示。實(shí)現(xiàn)上述功能的VB程序如下，請回答下列問題：(1)根據(jù)題意描述，字符串“BCEFGK”和“GKBLMCKEF”的最長公共字符串長度為________。(2)請在劃線處填入合適的代碼。Functiongetmin(aAsInteger,bAsInteger)′獲取兩個整數(shù)的較小者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＝j(luò)DoWhile____②____Andcnt<minlencnt＝cnt＋1x＝xModlen1＋1y＝y(tǒng)Modlen2＋1LoopIf____③____Thenans＝cntNextjNextiLabel3.Caption＝Str(ans)EndSub答案(1)5(2)①getmin(len1,len2)②Mid(s1，x，1)＝Mid(s2，y，1)③cnt>ans【變式訓(xùn)練2】編寫VB程序，實(shí)現(xiàn)如下功能：在文本框Text1中輸入當(dāng)天對應(yīng)的星期，文本框Text2中輸入天數(shù)，單擊“推算”按鈕Command1，推算出相應(yīng)天數(shù)后的星期情況，并在標(biāo)簽Label1中輸出結(jié)果。界面如圖所示。(1)為實(shí)現(xiàn)上述功能，請在劃線處填入合適的代碼。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)若當(dāng)天是“星期五”，在文本框Text2中輸入“166”，單擊“推算”按鈕后，標(biāo)簽Label1中顯示的內(nèi)容是________。答案(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數(shù)組元素a(1)到a(6)的值依次為“19，8，96，92，85，88”，經(jīng)過該程序段“加工”后，數(shù)組元素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．小張編寫程序，實(shí)現(xiàn)把數(shù)據(jù)temp插入到升序序列中，得到一個新的升序序列，原升序序列各元素已依次存放在數(shù)組元素a(1)、a(2)、a(3)、……、a(n)中。他編寫的VB程序段如下：Iftemp>＝a(n)Thena(n＋1)＝tempElsej＝nDoWhilej>＝1Andtemp<a(j)____①____j＝j(luò)－1Loop____②____EndIf要使程序?qū)崿F(xiàn)上述功能，則方框①②中的語句分別是()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該程序段執(zhí)行后，在文本框Text1中顯示的內(nèi)容是()A．HGF B．Hgf C．FGH D．Fgh答案C二、非選擇題4．對一段字符(僅包含大小寫字母和數(shù)字)加密，加密規(guī)則為：①字母和數(shù)字都往后循環(huán)順移3位，如“a”變?yōu)椤癲”，“y”變?yōu)椤癰”；“0”變?yōu)椤?”，“7”變?yōu)椤?”，②加密后字母在前，數(shù)字在后，③字母按逆序排列，數(shù)字按順序排列，如輸入明文“a1b7Z8x3”，密文為“aCed4016”。(1)根據(jù)程序代碼分析，“加密”按鈕的名稱是__________。(2)根據(jù)加密規(guī)則，明文“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個數(shù)形成環(huán)狀，現(xiàn)要分別找出3個相鄰的數(shù)，使其相加之和最大或最小。如15個數(shù)依次為：18，14，42，61，13，19，14，13，28，52，61，58，30，則相鄰三數(shù)之和最大為62(30＋18＋14)，相鄰三數(shù)之和最小為31(4＋26＋1)。程序運(yùn)行時，先隨機(jī)生成15個[1，30]區(qū)間內(nèi)的整數(shù)，存儲在數(shù)組a(0)至a(14)中，并在文本框Text1中顯示；單擊“計算”按鈕Command1，則在標(biāo)簽Label4中顯示連續(xù)三數(shù)最大和，在標(biāo)簽Label5中顯示連續(xù)三數(shù)最小和，程序運(yùn)行界面如圖所示。實(shí)現(xiàn)上述功能的VB程序如下，請在劃線處填入合適的代碼。Constn＝14Dima(n)AsIntegerPrivateSubFormLoad()′隨機(jī)生成15個數(shù)，存儲在數(shù)組元素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．小李同學(xué)碰到了一個數(shù)學(xué)問題：400個同學(xué)按順序進(jìn)行編號后圍成一個大圈，按1至2報數(shù)(從1號位置開始)，報到2的同學(xué)出列，以此一直循環(huán)報數(shù)下去，問最后剩下的那位同學(xué)他的編號是幾號？例如以6個同學(xué)編號為例，按1至2報數(shù)(從1號位置開始)依次出列的編號次序?yàn)?－4－6－3－1－5，那么最后剩下的就是編號為5的同學(xué)。為了解決這個問題，小李用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個房間居住人數(shù)為a(i)。初始時選擇一個房間，將所有人都聚集在該房間，接著每個人都按順時針方向走到相鄰的房間，直到走到居住的房間。一個人每經(jīng)過一扇門花費(fèi)1能量，請確定初始房間，使得所有人花費(fèi)的能量和最小。例如：N＝5，a(1)＝4，a(2)＝7，a(3)＝8，a(4)＝6，a(5)＝4最佳方案：初始時所有人聚集在2號房間，花費(fèi)的能量和：7*0＋8*1＋6*2＋4*3＋4*4＝48。為了解決這個問題，小明編寫了一個VB程序。在窗體加載時，從數(shù)據(jù)庫中讀取N的值和編號為1到N的房間的居住人數(shù)，人數(shù)存儲在數(shù)組a中。點(diǎn)擊窗體上的按鈕Command1，程序枚舉每一種方案(不同的初始房間)，計算該方案的能量和，在文本框Text1中輸出最優(yōu)方案的初始房間編號，在文本框Text2中輸出最小能量和。實(shí)現(xiàn)上述功能的VB代碼如下，請在劃線處填入合適的代碼。Dima(1To100)AsInteger′依次存儲編號為1到100的房間的居住人數(shù)PrivateSubForm_Load()′本過程從數(shù)據(jù)庫中讀取N的值和每個房間居住人數(shù)，存儲在數(shù)組a中′代碼略EndSubPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,wAsInteger,kasIntegerDimtAsLong,ansAsLongk＝0：ans＝32767′ans初始化為最大的Integer數(shù)據(jù)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．?dāng)?shù)組a中存儲n個2位正整數(shù)，從倒數(shù)第2個數(shù)開始，利用對分查找的思想，找到他所在位置，并插入到位置中，實(shí)現(xiàn)整個數(shù)組有序。實(shí)現(xiàn)該功能的VB程序如下：Constn＝100Dima(n)AsIntegerPrivateSubForm_Load()′產(chǎn)生n個2位正整數(shù)，并顯示在文本框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)程序代碼中，將①處語句補(bǔ)充完整。(4)若刪除語句“Ifa(m)＝tThenright＝m:ExitDo”，則下列說法正確的是__________(單選，選填字母：A.程序進(jìn)入死循環(huán)，無法正常運(yùn)行/B.輸出排序的結(jié)果不變/C.輸出排序的結(jié)果將改變)。答案(1)D(2)left＝i＋1(3)①a(right)＝t(4)B9．某8位日期加密授權(quán)碼生成方法描述如下：①授權(quán)碼由9位字符組成，前8位為日期的密文，最后1位為驗(yàn)證碼；②日期的最后1位數(shù)字k(若k的值為0，令k＝10)，加密成26個大字英語字母表中該位置對應(yīng)的字母。③將26