其他常用算法信息技術選考

21/211．(2019·4月浙江省選考)小明基于冒泡排序思想設計了一個改進的排序算法。該算法先用冒泡法將數組a中奇數位置的元素、偶數位置的元素分別進行排序，然后再進行后續(xù)處理。算法的VB程序段如下，但加框處代碼有錯，請改正?！浯判驍祿鎯υ跀到Ma中(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)為一個獨立數據段。?數據段加密規(guī)則：數據個數等于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中，代碼略?！渥x取待解密數據，保存在數組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個數在序?！纠?】小明對兩個班級的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約瑟夫環(huán)問題約瑟夫環(huán)是一個數學的應用問題：已知n個人(以編號1，2，3……n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規(guī)律重復下去，直到圓桌周圍的人全部出列。在生活中會碰到類似很多問題，如鐘表走向、值日的輪值等。一、以24小時制式計算(0點－23點)，完成如下表格t的初值經歷時長(n)結果時間統(tǒng)一表達式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運算符進行計算，某個數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?！纠?】字符環(huán)上的最長公共字符串。將字符串首尾相接后可以得到一個環(huán)，如圖1和圖2分別是由字符串“ABCUVKLM”和“MADJKLUVKL”首尾相接后得到的環(huán)。在圖1和圖2所示的兩個環(huán)中，最長的公共字符串為“UVKLMA”(圖中帶背景圓圈表示)。編寫VB程序，實現如下功能：在文本框Text1和Text2中分別輸入一個字符串(僅由大寫字母構成，每個字符串長度不超過100)，單擊命令按鈕Command1后，在標簽Label3中輸出兩個字符串構成的環(huán)的最長公共字符串長度(字符串在環(huán)中必須連續(xù))。程序運行效果如圖所示。實現上述功能的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＝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【變式訓練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該程序段執(zhí)行后，在文本框Text1中顯示的內容是()A．HGF B．Hgf C．FGH D．Fgh答案C二、非選擇題4．對一段字符(僅包含大小寫字母和數字)加密，加密規(guī)則為：①字母和數字都往后循環(huán)順移3位，如“a”變?yōu)椤癲”，“y”變?yōu)椤癰”；“0”變?yōu)椤?”，“7”變?yōu)椤?”，②加密后字母在前，數字在后，③字母按逆序排列，數字按順序排列，如輸入明文“a1b7Z8x3”，密文為“aCed4016”。(1)根據程序代碼分析，“加密”按鈕的名稱是__________。(2)根據加密規(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個數形成環(huán)狀，現要分別找出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]區(qū)間內的整數，存儲在數組a(0)至a(14)中，并在文本框Text1中顯示；單擊“計算”按鈕Command1，則在標簽Label4中顯示連續(xù)三數最大和，在標簽Label5中顯示連續(xù)三數最小和，程序運行界面如圖所示。實現上述功能的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的同學出列，以此一直循環(huán)報數下去，問最后剩下的那位同學他的編號是幾號？例如以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中輸出最優(yōu)方案的初始房間編號，在文本框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.程序進入死循環(huán)，無法正常運行/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