信息學(xué)競賽普及組初賽模擬試題

信息學(xué)競賽普及組初賽模擬試題（五）一、選擇題：（每題1.5分，共計30分。每題有5個選項，前10題為單選題，后10題為不定項選擇題，全部選對才得分）。1.二進(jìn)制數(shù)11011011的十進(jìn)制值是（）202B.219C.193D.209我國研制的銀河III型的超級計算機(jī)通過基準(zhǔn)程序的測試，其峰值速度是（）80億次B.100億次C.130億次D.150億次程序段如下：FORI:=1TO5DOFORJ:=2TOIDOWriteln（‘*'）輸出'*'的個數(shù)是（）A.5B.10C.15D.25E.30設(shè)待排序的記錄為（49，38，65，97，76，13，27,49,55,4），經(jīng)過下過程將序列排序第一趟：13,27,49,55,4,49,38,65,97,76第二趟：13,4,49,38,27,49,55,65,97,76第三趟：4,13,27,38,49,49,55,65,76,97問它所用的方法是：（□A.冒泡排序B.直接選擇排序C.直接插入排序D.希爾排序設(shè)無向樹T有7片樹葉，其余頂點度均為3,則T中3度頂點有多少個（）A.5B.7C.9D.4E.8設(shè)連通圖G的頂點數(shù)和邊數(shù)與一立方體相同，即有8個頂點和12條邊。任意一棵G的生成樹的總邊數(shù)為（）A．7 B.8C.9D.10E.11設(shè)有兩個散列函數(shù)h1（k）=kmod13和h2（k）=kmod11+1，散列表為T[0?12]，用二次散列法解決沖突。函數(shù)hl用來計算散列地址，當(dāng)發(fā)生沖突時，h2作為計算下一個探測地址的地址增量。假定某一時刻散列表的狀態(tài)為：0123456789101112804435804435下一個被插入的關(guān)鍵碼為57，其插入的位置為(。A.4 B.5 C.6D.7E.8請根據(jù)下面是一段PASCAL程序,判斷第8、9題。forh:=1ton-1dobeginx:=A[h+1];k:=h;while(k>=1)and(A[k]>x)dobeginA[k+1]:=A[k];k:=k-1endA[k+1]:=xend8?假設(shè)在程序開始執(zhí)行時，數(shù)組A[l?n]是一組隨機(jī)整數(shù)。下列答案中，哪一個最好的描述了最差情況下的程序排序的時間復(fù)雜度？()A.O(nlog2n)B.0(n)C.O(log2n)D.0(n2)E.0(2n)9?假設(shè)在程序開始執(zhí)行時，數(shù)組A[1?n]是按關(guān)鍵字非遞減有序排列時，下列答案中，哪一個最好的描述了最好情況下的程序排序的時間復(fù)雜度？()A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)E.O(2n)對下列四個序列用快速排序方法進(jìn)行排序，以序列的第一個元素為劃分的基準(zhǔn)，在第一趟劃分過程中，元素的移動數(shù)最多的是哪一個序列()70,65,34,82,53,25,9082,53,25,70,65,34,9034,25,53,65,90,82,7053,25,65,70,34,90,8265,34,82,70,25,53,90在計算機(jī)運行時，把程序和數(shù)據(jù)一樣存放在內(nèi)存中，這是1946年由 所領(lǐng)導(dǎo)的研究小組正式提出并論證的。()圖靈馮?諾依曼C.布爾D.赫夫曼E.哈希下面關(guān)于計算機(jī)的說法正確的是（）微機(jī)內(nèi)存容量的基本計量單位是字節(jié)B.二進(jìn)制數(shù)中右起第10位上的1相當(dāng)于210CPU每執(zhí)行一個指令，就完成一步基本運算或判斷D.1T=1024MBE.32位的計算機(jī)中的“32”指的是字長為什么說PASCAL是“高級語言”，是因為它（）必須在性能較高的機(jī)器上運行必須經(jīng)過良好培訓(xùn)的高水平的程序員使用離機(jī)器的硬件較遠(yuǎn)開發(fā)的時間較長程序的性能較好以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)？（）E.隊列廣義表 B.二叉樹C.稀疏矩陣 D.E.隊列在下面關(guān)于計算機(jī)系統(tǒng)硬件的說法中不正確的是（口沒有外部設(shè)備的計算機(jī)稱為祼機(jī)當(dāng)關(guān)閉計算機(jī)電源后，RAM中的程序和數(shù)據(jù)就消失了軟盤和硬盤上的數(shù)據(jù)均可由CPU直接存取軟盤和硬盤驅(qū)動器既屬于輸入設(shè)備又屬于輸出設(shè)備CPU主要由運算器、控制器和寄存器組成下面關(guān)于算法的正確說法是（）算法必須有輸出算法必須在計算機(jī)上用某種語言實現(xiàn)算法不一定有輸入算法必須在有限步執(zhí)行后能結(jié)束算法是程序的靈魂以下關(guān)于結(jié)構(gòu)化程序的說法中，正確的是（）A.結(jié)構(gòu)化程序是由單入口，單出口和循環(huán)三種結(jié)構(gòu)組成結(jié)構(gòu)化程序是出順序、單入中和單出口三種結(jié)構(gòu)組成結(jié)構(gòu)化程序是由順序、循環(huán)和GOTO語句結(jié)構(gòu)組成結(jié)構(gòu)化程序是由順序、循環(huán)和分支三種結(jié)構(gòu)組成“自頂向下，逐步求精”是結(jié)構(gòu)化程序設(shè)計方法的特點18.棧S最多能容納4個元素?，F(xiàn)有6個元素按1，2，3，4，5，6的順序進(jìn)棧，問下列哪一個序列是可能的出棧序列？（）A.5，4，3，2，1，63,2,5,4,1,62,3,5,6,1,41,4,6,5,2,3E.4，5，3，6，2，1下列排序算法中，哪些排序是不穩(wěn)定的（）A.快速排序 B.基數(shù)排序 C.希爾排序D.冒泡排序E.選擇排序下列說法正確的是（）解釋程序是接受參數(shù)，按照某一樣板產(chǎn)生機(jī)器語言的計算機(jī)程序BASIC語言程序通常需解釋執(zhí)行連接程序可以把經(jīng)編譯程序產(chǎn)生的目標(biāo)程序變成可執(zhí)行的機(jī)器語言程序就執(zhí)行速度而言，編譯程序比解釋程序快PASCAL通常是先編譯后執(zhí)行二、問題求解題（每題5分，共計10分）由四個結(jié)點可以構(gòu)造多少種不同的二叉樹.下圖是一個設(shè)想有11項活動的活動網(wǎng)。其中有9個事件VI,V2,…V9,每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。V1表示整個工程的開始，V9表示結(jié)束，與每個活動相聯(lián)系的數(shù)ax（x=l?ll）是執(zhí)行該活動所需的時間（單位：天）。問完成整項工程至少需要天,影響工程進(jìn)度的關(guān)鍵活動有哪些： 。V2V7V1V5V9V3V8V6V4V6三、程序閱讀理解題（每題8分，共計32分）1．programex11_8;varn,i,j,k,p:longint;beginwrite('N=12');i:=2;j:=0;k:=1;repeatinc(i);p:=j+k;j:=k;k:=p;untili=12;writeln('F(',12,')=',p);end.運行結(jié)果為：2．programexample;varn:byte;a:array[1..100]oflongint;functionf(n:byte):longint;vari:longint;beginifa[n-1]>0theni:=a[n-1]elsei:=f(n-1);ifa[n-2]>0theni:=i+a[n-2]elsei:=i+f(n-2);a[n]:=i;f:=i;end;beginfillchar(a,sizeof(a),0);a[1]:=1;a[2]:=1;writeln('F(',8,')=',f(8));end.運行結(jié)果為:3．programexample3begina[1]:=1;t:=0;fori:=2to6dobegins:=0;forj:=1toi-1dos:=s+a[j];a[i]:=s+1;end;fori:=1to6dot:=t+a[i];writeln(‘t=',t);end.運行結(jié)果為：4．programexample4vari,s,max:integer;beginfori:=1to10doread(a[i]);max:=a[1];s:=a[1];fori:=2to10dobeginifs<0thens:=0;s:=s+a[i];ifs>maxthenmax:=s;end;writeln（‘max=',max）;end.輸入：89-124651115-289運行結(jié)果為：四、程序完善題（每題14分，共計28分）nXn方陣的每行每列都是自然數(shù)l..n的一個全排列，每行（列）無重復(fù)數(shù)字。例：n=5時，1432553214421533154225431輸入n（＞=2）和第一行數(shù)字（不檢查錯誤）輸出一個滿足要求的方陣因為只是要求每行（列）無重復(fù)數(shù)字，對第一行的每個數(shù)字，都四十五度斜向下寫，寫到行盡頭就從行開頭開始。這樣就不會重復(fù)。對于經(jīng)過第y行，第x列的直線，斜率k=1設(shè)：y=x+b代入坐標(biāo)，得出：b=y-x令y=1，取首行的數(shù)：x=y-bx從1開始，到n,如果x為0或負(fù)數(shù)，則x=x+n，取出第一行的數(shù)。程序只用一維數(shù)組，存第一行的數(shù)字。programexample2;constmaxn=10000;vara:array[1..maxn]ofinteger;x,y,n:integer;functionf（x,y:integer）:integer;varb:integer;begin(1)(2)ifx<=0then(3)f:=a[x];end;beginwrite('Entern:');readln(n);if(n<2)or(n>maxn)thenexit;write('Enterfirstline:');forx:=1tondoread(a[x]);writeln('Output:');forx:=1tondowrite(a[x]:4);writeln;fory:=2tondobeginforx:=1tondowrite((4):4);writeln;end;end.[程序說明]設(shè)有n個人依次圍成一圈，從第1個人開始報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人開始報數(shù)，數(shù)到第m個人又出列，…，如此反復(fù)到所有的人全部出列為止。設(shè)n個人的編號分別為1,2，?，n，打印出出列的順序。本題用數(shù)組建立標(biāo)志位等方法求解，用數(shù)組實現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)。數(shù)組a[i]作為"指針"變量來使用，a[i]存放下一個結(jié)點的位置。設(shè)立指針j指向當(dāng)前結(jié)點，則移動結(jié)點過程為j:=a[j]，當(dāng)數(shù)到m時，m結(jié)點出鏈，則a[j]:=a[a[j]]。[程序]programexample;constn=14;m=4;vara:array[1..n]ofinteger;i,j,k,p:integer;beginfori:=1ton-1doa[i]:=i+1;a[n]:=1;;k:=1;p:=0;repeat;k:=k+1;ifk=mthenbeginwrite(a[j]:4);p:=p+1;;;enduntilp=n;end.參考答案一、選擇題：(每題1.5分，共計30分。每題有5個選項，前10題為單選題后10題為不定項選擇題，全部選對才得分)。題號12345678910答案BCBDAAEDBE題號11121314151617181920答案BACECDEACABCDEDEBEACBCDE二、問題求解題（每題5分，共計10分））1、142、19,（2分）a1,a4,a7,a10（3分）三、程序閱讀理解題（每題8分，共計32分）1、F（12）=892、F（8）=213、t=634、max=77四、程序完善題（每題14分，共計28分）1、b:=y-x;x:=1-b;x:=x+n;f(x,y)j:=n;j:=a[j];a[j]:=a[a[j]];k:=1;grundfos發(fā)表于＞2004-10-1810:16:5^Z1［全文］［評論］［引用］［推薦］［檔案］［推給好友］2004-10-18信息學(xué)競賽普及組初賽模擬試題（四）信息學(xué)競賽普及組初賽模擬試題（四）一、選擇題：（選出每題正確的答案代碼，填在括號里，1—10題為單選題，每小題只有一個正確答案，11—20題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分）1、二進(jìn)制數(shù)01100100轉(zhuǎn)換成十六進(jìn)制數(shù)是（）。A．32B．64C．128D．100E．2562、 操作系統(tǒng)是一類重要的系統(tǒng)軟件，下面幾個軟件中，不屬于系統(tǒng)軟件的是（）。A．JavaB．MS-DOSC．LinuxD．Windows2000E．Unix3、 計算機(jī)病毒的傳染是以計算機(jī)運行和（）為基礎(chǔ)的，沒有這兩個條件，病毒是不會傳染的。編輯文稿B.讀寫磁盤C.編程序D.掃描圖畫E.打印4、因特網(wǎng)不屬于任何個人，也不屬于任何組織。其中在網(wǎng)絡(luò)知識這一塊中有一個英文簡寫ISP，它的中文意思是()。因特網(wǎng)連接B.因特網(wǎng)使用C.因特網(wǎng)設(shè)計D.因特網(wǎng)服務(wù)提供者E.信息傳輸5、 Internet給我們提供了資源共享、瀏覽、檢索信息和遠(yuǎn)程登錄等多種服務(wù)，下面幾個選項中用于遠(yuǎn)程登錄的是()。WWWB.TCP/IPC.TelnetD.E-mailE.FTP6、IE是目前流行的瀏覽器軟件，它的工作基礎(chǔ)是解釋執(zhí)行用()語言書寫的文件。A.VCB.HTMLC.BASICD.HTTPE.VB7、 給出3種排序：插入排序、冒泡排序、選擇排序。這3種排序的時間代價分別是()。A.O(n)、O(n2)、O(logn)B.O(logn)、O(n)、O(n2)C.O(n2)、O(n)、O(logn)D.O(n2)、O(n)、O(n)E.O(n2)、O(n2)、O(n2)8、一棵完全二叉樹的結(jié)點總數(shù)為18，其葉結(jié)點數(shù)為( )。A.7個B.8個C.9個D.10個E.11個9、 在流程圖的符號中，菱形框一般作為()。起始框B.判斷框C.輸入輸出框D.處理工作框E.結(jié)速框10、 在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主要將要輸出打印的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個()結(jié)構(gòu)。A.堆棧B.數(shù)組C.線性表D.隊列E.鏈表11、多媒體技術(shù)中的“多媒體”的含義主要是指如( )等多種表達(dá)信息的形式。A.磁盤B.音箱C.顯示器D.聲音E.圖像12、 下面有關(guān)計算機(jī)知識說明，正確的是()。A.在WINDOWS98操作系統(tǒng)下，刪除磁盤中的文件時都先存放在回收站中B．FOXMAIL是用于收發(fā)電子郵件的工具C．文件夾組織是一個有層次的樹狀結(jié)構(gòu)，其中最頂層的是桌面D.存儲器具有記憶能力，其中的信息任何時候都不會丟失E．為了提高軟件的測試效率，應(yīng)該選擇發(fā)現(xiàn)錯誤的可能性大的測試數(shù)據(jù)13、 對按關(guān)鍵字排序好的線性表進(jìn)行二分查找，該線性表適合的存儲結(jié)構(gòu)為（）。A.鏈接存儲 B.索引存儲 C.散列存儲 D.順序存儲 E.循環(huán)存取14、 一個棧的輸入順序為1、2、3、4、5，下列序列中可能是棧的輸出序列的是（）。A．54312B．24135C．21543D．12534E．1234515、 評價一個算法的好壞有多種指標(biāo)，下列是算法評價指標(biāo)的是（）。A.正確性B.運行時間 C.占用空間D.迭代次數(shù)E.簡單性16、 下面描述用多維數(shù)組表示的數(shù)據(jù)結(jié)構(gòu)的語句中，正確的是（）。多維數(shù)組存放的都是同一種類型的數(shù)據(jù)多維數(shù)組各維的下標(biāo)范圍必須一樣多維數(shù)組在內(nèi)存中的地址是連續(xù)的多維數(shù)組中的下標(biāo)不能是表達(dá)式多維數(shù)組是隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)17、 若已知一個棧的入棧順序1,2,3,…，n其輸出序列為Pl,P2,P3,…,Pn（它是輸入序列的一個排列），則在輸出序列中可能出現(xiàn)的情況是（）。PjvPkvPi，其中ivjvkPk<Pj<Pi，其中ivjvkPjvPivPk，其中ivjvkPivPkvPj,其中ivjvk以上都不可能出現(xiàn)18、線性表具有如下的結(jié)構(gòu)特點：（ ）A.均勻性B.單一性C.簡單性D.無序性E.有序性19、 下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是（）。A.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列是限定僅在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表圖是一種非線性數(shù)據(jù)結(jié)構(gòu)20、任意一棵樹均可惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹中，頂點N的左右子女分別是N在原樹里對應(yīng)頂點的（）。最左子頂點/最鄰近的右兄弟最右子頂點/最右的兄弟最鄰近的右兄弟/最左的兄弟最鄰近的左兄弟/最鄰近的右兄弟最鄰近的右兄弟/最右的兄弟二、 問題解答：（共2題，每題5分，共10分）1、 光明中學(xué)開設(shè)數(shù)學(xué)、英語和信息學(xué)三個興趣學(xué)習(xí)小組，其中數(shù)學(xué)小組30人，英語小組15人，信息學(xué)小組18人，參加三個小組總?cè)藬?shù)為50人，其中有3人同時參加3個小組，那么同時只參加兩個小組的同學(xué)有多少人？2、 給出一組頂點（頂點值用A,B,C,D,E,F表示），其對應(yīng)權(quán)值分別為2,3、 1,7,8,4。請以A,B,C,D,E,F為葉子頂點構(gòu)造一棵哈夫曼樹，并求出它的最小帶權(quán)路徑長度WPL的值。三、 寫出程序的運行結(jié)果（共4題,每題8分,共32分）第1題：programtest1；varn：integer；functioncount（n：integer）：integer；beginifn=1thencount：=0elseifnmod2=0thencount：=count(ndiv2)+1elsecount：=count(n*3+1)+1；end；beginreadln(n)；writeln(count(n))；end.輸入：99輸出：第2題：programtest2(input,output);vari,j,k,s:integer;begins:=0fori:=3downto1dobeginforj:=1to3dobegink:=0;repeatk:=k+1;s:=s+k;untilk=j;end;s:=s-(k+1);end;write(‘s=',s);end.輸出：第3題：programtest3;vara,b,n:longint;beginreadln(n);a:=0;b:=0;repeata:=a+1;b:=b+a;untilb>=n;writeln(a);end.輸入：415377輸出：programtest4;varm,n,i,p,k：integer;r:array[1?200]ofinteger;b:Boolean;beginm:=6;n:=2;forI:=1tom-1dor[i]:=i+1;r[m]:=1;i:=0;p:=1;b:=true;whilebdobegini:=i+1;k:=p;p:=r[p];ifk=pthenbeginwriteln(p);b:=falseendelseifi=n+1thenbeginwrite(p,‘');i:=0;p:=r[p];r[k]:=p;endend輸出：四、完善程序(共2題，每題14分，共28分)第1題(7分)【問題描述】設(shè)有n種物品，每種物品有一個重量及一個價值。但每種物品的數(shù)量是無限的，同時有一個背包，最大載重量為XK,今從n種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于XK,而價值的和為最大。【程序清單】Programpackage;constmaxxk=400;maxn=20;typetlist=array[1?maxn]ofbyte;tmake=array[0?maxn,0?maxxk]ofinteger;varn,xk:integer;w,u:tlist;f:tmake;procedureinit;vari:byte;beginfillchar(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,xk);fori:=1tondo①;end;proceduremake;vari,j:byte;beginfori:=1tondobeginforj:=1tow[i]-1dof[i,j]:=f[i-1,j];forj:=w[i]toxkdoiff[i-1,j]>f[i,j-w[i]]+u[i]then②;else③;end;end;procedureprint;varget:tlist;i,j:byte;beginfillchar(get,sizeof(get),0);i:=④;j:=⑤;whilei>0doiff[i,j]=f[i-1,j]thendec(i)elsebegindec(j,w[i]);⑥;end;writeln(‘n=',n,‘,',‘xk=',xk);writeln(‘maxworth=', ⑦口fori:=1tondowriteln(‘no.',i‘,weight:',w[i]:2,‘worth:',u[i]:2,‘get',get[i]:2);end;begininit;make;print;第2題(7分)【問題描述】給定一個01串，請你找出長度介于a,b之間，重復(fù)出現(xiàn)次數(shù)最多的01串。輸入：a,b(0vav=bv=12)由0，1組合的數(shù)列，由‘.'結(jié)尾。輸出：要求的串。提示：本程序中將01序列轉(zhuǎn)換為2進(jìn)制數(shù)存取。【程序清單】programshuchuan;vari,j,s,k,a,b,max:integer;m:array[1?8192]ofinteger;two,v:array[1?20]ofinteger;c:char;beginfori:=1to13do①;readln(a,b);read(c);s:=1;k:=1;whilec<>‘.'dobegins:=sshl1+ord(c)-48;if②thens:=((s-two[b+1])modtwo[b])+two[b];inc(m[s]);ifk<bthenfori:=atok-1do③;inc(k);read(c);end;fori:=two[b]totwo[b+1]doifm[i]>0thenforj:=atob-1dom[(imodtwo[j])+two[j]]:=④;max:=0;fori:=two[a]totwo[b+1]doifm[i]>maxthen ⑤;fori:=two[a]totwo[b+1]doifm[i]=maxthenbeginj:=0;k:=I;repeatinc(j);v[j]:=kmod2;⑥;until⑦;whilej>0dobeginwrite(v[j]);dec(j)end;writeln;end;end.信息學(xué)命題(四)參考答案一、選擇題：(選出每題正確的答案代碼，填在括號里，1—10題為單選題，每小題只有一個正確答案，11—20題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分)題號12345678910答案BABDCBECBD題號11121314151617181920答案DEBCEDCEABCEACEBCDAEACDEA二、問題解答：(共2題，每題5分，共10分)第1題：第2題：61三、寫出程序的運行結(jié)果：(共4題，每題8分，共32分)第1題：25第2題：s=18第3題：911第4題：421365四、完善程序(共2題，每題14分，共28分)第1題：read(w[i],u[i])f[i,j]:=f[i-l,j]f[i,j]:=f[i,j-w[i]]+u[i]i:=nj:=xkinc(get[i])f[n,xk]第2題：two[i]:=1shli；s>=two[b+1](或k>b)inc(m[(smodtwo[i])+two[i]])m[(imodtwo[j])+two[j]]+m[i]max:=m[i]k:=kdiv2k=1信息學(xué)競賽普及組初賽模擬試題（三）一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內(nèi)（每題1.5分，多選無分，共30分）1、MAN英文縮寫的含義是（）A.局域網(wǎng)B.城域網(wǎng)C.廣域網(wǎng)D.增值網(wǎng)2、 小張用十六進(jìn)制，八進(jìn)制和十進(jìn)制寫了如下一個等式：64－13=33TOC\o"1-5"\h\z式中三個數(shù)是各不相同進(jìn)位制的數(shù)，試問64，13，33，分別為 。八進(jìn)制，十進(jìn)制，十六進(jìn)制B.十進(jìn)制，十六進(jìn)制，八進(jìn)制C.八進(jìn)制，十六進(jìn)制，十進(jìn)制D.十進(jìn)制，八進(jìn)制，十六進(jìn)制3、表達(dá)式（4MOD（－3））與（－4MOD3）的值為： 。A.－1，－1 B.1，－1C.－1，1 D.1，14、試指出：下列if語句中，當(dāng)x=80時,運行的結(jié)果為 。beginy:=0;readln（x）;ifx<0theny:=5elseifx<10thenbeginy:=10;ifx<100theny:=100;endelsey:=200;write（'y=',y）;end.A.y=9 B.y=200 C.y=10 D.y=1005、 設(shè)棧S的初始狀態(tài)為空，現(xiàn)有5個元素組成的序列｛1，2,3,4,5｝，對該序列在S棧上依次進(jìn)行如下操作（從序列中的1開始，出棧后不再進(jìn)棧）：進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，出棧，進(jìn)棧，試問出棧的元素序列是A．{5，4，3，2，1}B．{2，1}C．{2，3}D．{3，4}6、ASCII碼是()。A.國標(biāo)碼B.二進(jìn)制編碼C.十進(jìn)制編碼D.美國標(biāo)準(zhǔn)信息交換碼7、一臺計算機(jī)的字長是4個字節(jié)，這意味著()。A.能處理的數(shù)值最大為4位十進(jìn)制數(shù)9999B.能處理的字符串最多由4個英文字母組成在CPU中能夠同時處理32位二進(jìn)制數(shù)據(jù)在CPU中運算的最大結(jié)果為2的32次方8、 假設(shè)一臺計算機(jī)的地址總線為16,那么中央處理器CPU能訪問的最大存儲器容量為(口A.2*16KBB.16KBC.216BD.16*1024*8B9、 計算機(jī)最終處理的信息形式是()A.ASCII碼B.BCD碼C.二進(jìn)制D.十六進(jìn)制10、 與十六進(jìn)制數(shù)6F等值的八進(jìn)制數(shù)是()A.166B.139C.157D.18311、 以下屬非法用戶自定義標(biāo)識符的是()。A.date B.dirC.listD.type12、 設(shè)X和Y是同一種枚舉類型變量，則下列語句中合法的是()。A.X:=ORD(Y) B.X:=YC.READ(X,Y)D.WRITE(T,Y)13、計算機(jī)能夠直接識別和處理的程序是 程序A.匯編語言B.源程序 C.機(jī)器語言D.高級語言14、 設(shè)有說明VARA：ARRAY['A'..'E'，1..4，BOOLEAN]OFREA1；則A['A',3]是(匚I。一個實型的數(shù)組元素一個數(shù)組，該數(shù)組具有兩個實型數(shù)組元素一個數(shù)組，該數(shù)組具有4*2個實型數(shù)組元素一個數(shù)組，該數(shù)組具有5*4*2個實型數(shù)組元素15、下列屬于線性時間的排序算法是：（）A.快速排序 B.桶排序C.冒泡排序16、一棵包含n個節(jié)點的樹有幾條邊：A.n B.n-1C.不一定TOC\o"1-5"\h\z17、 在Pascal語言中，表達(dá)式35div3mod4的值是 。A.O B.2 C.3 D.618、 在數(shù)據(jù)結(jié)構(gòu)中，"樹"結(jié)構(gòu)下層結(jié)點出現(xiàn)三個以上的結(jié)點，這種結(jié)構(gòu)稱為A.三層樹B.三叉樹C.多層樹D.多叉樹19、在Pascal語言中，下列程序段所計算的公式是 。程序段：S：=0；T：=1；ForI：=1to10doBeginT：=T*I；S：=S+T；end;S=1+2+3+4+??+10S=1*2*3*4*??*10S=1！+2！+3！+4！+??+10！S=1+2*3+3*4+4*5+??+10*1120、 以下說法正確的是（）。A.CPU與內(nèi)存不交換信息B.CPU與內(nèi)存直接交換信息C.CPU與內(nèi)存間接不交換信息D.CPU與內(nèi)存部分交換信息二、閱讀下列程序，寫出程序運行結(jié)果（第1題5分，第2，3，4題各6分，共23分）programexp1;constn=5;varI,j,k:integer;r:array[0..10]ofinteger;beginforI:=1tondoread(r[I]);forI:=2tondobegink:=r[I];j:=I-1;while(k>r[j])and(j>0)dobeginr[j+1]:=r[j];j:=j-1;end;r[j+1]:=k;end;forI:=1tondowrite(r[I],'');writelnend.鍵盤輸入:84935屏幕輸出：programexp2;vara,b,f:integer;functiongd(m,n:integer):integer;beginifn=0thengd:=melsegd:=gd(n,mmodn);end;beginreadln(a,b);write(‘(‘,a,',',b,')=');f:=gd(a,b);writeln(f)end.鍵盤輸入:17216屏幕輸出：3、Programexp3(input,output);VARI,J,S:INTEGER;B:ARRAY[0..5]OFINTEGER;BEGINS:=1;FORI:=1TO5DOB[I]:=I;J:=1;WHILEJ>0DOBEGINJ:=5;WHILE(J>0)AND(B[J]=10+J-5)DOJ:=J-1;IFJ>0THENBEGINS:=S+1;B[J]:=B[J]+1;FORi:=J+1TO5DOB[i]:=B[J]+i-JEND;END;WRITELN('S=',S);END.4、programexp4(input,output);varm,n,g:integer;functiongcd(m,n:integer):integer;beginifn=0thengcd:=melsegcd:=gcd(n,mmodn)end;beginread(m,n);g:=gcd(m,n);writeln('m=',m,'n=',n,'gcd=',g)end.輸入：489輸出：三、問題解答（第1題每空4分，第2題8分）1、數(shù)據(jù)結(jié)構(gòu)中，下面是一個樹結(jié)構(gòu)圖，這個樹的"先序遍歷"結(jié)果是 中序遍歷結(jié)果是： 。248+3*4107-*/@2、給出一個后綴算術(shù)表達(dá)式為寫出對應(yīng)的中綴算術(shù)表達(dá)式： 四、完善程序（第一題每空3分，第二題每空2分，第三題每空4分，共32分）1、連續(xù)整數(shù)平臺問題已知一個含有多個整數(shù)的數(shù)組，其中相同的元素集中在一起形成一個平臺。以下程序用于對輸入的數(shù)組求出其中最大平臺長度。例如，中元素個數(shù)為20，它們依次為22223333311111111144則它的最大平臺長度為9。constmaxlength=100;vara:array[1..maxlength]ofinteger;i,maxi,n,s,t:integer;beginwrite('n=');readln(n);fori:=1tondoread(a[i]);readln;maxi:=0;t:=[1]s:=1;fori:=2tondoifa[i]=tthen[2]elsebeginifs>maxithenmaxi:=s;t:=a[i];[3]end;[4]writeln('maxi=',maxi);end.2、1000！尾0問題以下程序用于統(tǒng)計1000！末尾有多少個0。其中1000！=1´2´3´…´1000。實際上我們只要統(tǒng)計1000!有多少個因子10。由于10=5´2，因而只需統(tǒng)計有多少個因子5和2。顯然在1?1000的所有數(shù)中，5的因子個數(shù)比2的因子個數(shù)少。因此，只要統(tǒng)計1?1000的所有數(shù)中共有多少個因子5就行了。vari,j,n:integer;beginn:=0;fori:=1to200dobeginj:=i*5;while[5]=0dobeginn:=n+1;j:=[6]end;end;writeln(n:4);end.3、[問題描述]找數(shù)問題：以下程序用在n個不同元素中找出第k個最小元素。程序中用分治策略來設(shè)計算法。把這n個元素放在一個數(shù)組中，然后取出第k個元素為標(biāo)準(zhǔn)m,把n個元素重新排列:小于標(biāo)準(zhǔn)m的元素放在數(shù)組前面，大于該標(biāo)準(zhǔn)的放在數(shù)組的后面。把該元素m放在兩者之間。設(shè)小于標(biāo)準(zhǔn)的元素個數(shù)為j-1,如果j=k,則A(k)即為所求元素。如果j>k,則第k個元素必在區(qū)間[l,j]，因此取A[l],…，A[j]為新的元素集合，然后重復(fù)上述的”部分排序”的過程。如果jvk,則第k個元素必在區(qū)間[j+1,n],因此取A[j],?,A[n]為新的元素集合，重復(fù)過程。直至j=k為止。[程序清單]varj,k,n:integer;a:array[1..100]ofinteger;proceduresearch(b,e:integer);varI,m,t:integer;beginifb=ethenbeginj:=b;exitend;I:=b;j:=e;m:=[7];RepeatWhilea[I]<mdoinc(i);Whilem<a[j]do[8];IfI<jthenBegint:=a[I];a[I]:=a[j];a[j]:=tend;UntilI>=j;IfI=kthenexit;If[9]thensearch(b,j)elsesearch(j+1,e)End;procedure[10]varI:integer;beginforI:=1tondowrite(a[I],'');writeln;writeln(‘a(chǎn)[‘,k,']=',a[k]);end;beginwrite(‘n=');readln(n);write(‘a(chǎn)[1..',n,']=');fork:=1tondoread(a[k]);readln;write(‘k=');readln(k);search([11]口pr(n);readlnend.參考答案、單項選擇題（每題1分，共30分）12345678910DCBBDDCCCC11121314151617181920DBCBBBCDDB二、閱讀下列程序，寫出程序運行結(jié)果(第1題5分，第2，3，4題各6分，共23分）1、985431、（172，16）=43、S=2524、m=48n=9gcd=3三、問題解答(第1題每空4分，第2題8分)1、ABCDE BADCE2、(24+8)*3/4*(10-7)四、完善程序(第一題每空3分，第二題每空2分，第三題每空4分，共32分)(1)a[1](2)s:=s+1(3)s:=1(4)ifs>maxithenmaxi:=s;(5)jmod5(6)jdiv5(7)a[k](8)de(j)(9)j>k(10)pr(n:integer);(11)Ln信息學(xué)競賽普及組初賽模擬試題(二)(pascal語言)限時2小時完成，滿分100分一、選擇題：(共20小題，1-15小題為單選題，每題1分；16-20小題為多選題，每題2分。共25分)1.對存儲器按字節(jié)進(jìn)行編址，若某存儲器芯片共有10根地址線的引腳，則該存儲器芯片的存儲容量為(口。512B(B)1KB(C)2KB(D)4KB(E)8KB2?在待排序的數(shù)據(jù)表已經(jīng)為有序時，下列排序算法中花費時間反而多的是(口。(A)堆排序 (B)希爾排序 (C)冒泡排序 (D)快速排序(E)二分排序某數(shù)列有1000個各不相同的單元，由低至高按序排列，現(xiàn)要對該數(shù)列進(jìn)行二分法檢索，在最壞的情況下，需要檢索(□單元。(A)1000 (B)10 (C)100 (D)500(E)300已知數(shù)組a中，每個元素a[i,j]在存儲時要占3個字節(jié)，設(shè)i從1變化到8，j從1變化到10,分配內(nèi)存實是從地址sa開始連續(xù)按行存儲分配的。試問：a[5,8]的起始地址為(口。(A)sa+141 (B)sa+180 (C)sa+222 (D)sa+225(E)sa+1555?在pascal語言過程調(diào)用時，數(shù)值形參得到的是實際參數(shù)的(口。(A)數(shù)值(B)地址(C)值 (D)變量 (E)以上都不是—個24*24點陣的漢字字形信息所占的字節(jié)數(shù)為(口。(A)2 (B)8 (C)24 (D)32(E)72在微機(jī)系統(tǒng)中，最基本的輸入輸出模塊BIOS存放在(□中。(A)RAM(B)ROM(C)硬盤(D)寄存器(E)控制器十進(jìn)制算術(shù)表達(dá)式:3*512+5*64+2*8+1的運算中，用二進(jìn)制表示為(口。(A)1011010001(B)10110100011(C)11101010001(D)11110100011(E)111000設(shè)棧S的初始狀態(tài)為空，現(xiàn)對序列｛123,4,5｝在棧S上，依次進(jìn)行如下操作(從元素1開始,出棧后不再進(jìn)棧):進(jìn)棧,出棧,進(jìn)棧,進(jìn)棧,出棧,出棧。試問出棧的元素序列是(口。(A){1,2,3}B){1,3,2}C){3,2,1}D){2,3,1}(E)以上都不對E-mail郵件本質(zhì)上是一個(匚I(A)文件(B)電報(C)電話(D)傳真(E)電訊一棵二叉樹的高度為h,所有結(jié)點的度為0,或為2,則此樹最少有(□個結(jié)點(A)2h-1 (B)2h-1 (C)2h+1 (D)h+1(E)h*h+112?無向圖G=(V,E),其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}對該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點序列正確的是(□(A)a,b,e,c,d,f(B)a,c,f,e,b,d(C)a,e,b,c,f,d(D)a,b,e,d,f,c(E)以上都不對pascal編譯程序是(匚I.把pascal源程序轉(zhuǎn)換成可運行的EXE文件的程序.把pascal源程序轉(zhuǎn)換成等價的目標(biāo)碼的程序.生成和修改一個pascal語言源程序的等程序.把pascal的目標(biāo)碼程序轉(zhuǎn)換成可運行的EXE文件的程序.生成一個等價的匯編程序?qū)⑷庑磐兜?個郵筒,最多的投法有( )．種 (B)．種 (C)．種 (D)．34種E.電子信函(電子郵件)的特點之一是( )。.比郵政信函,電報,電話,傳真都更快.在通信雙方的計算機(jī)之間建立其直接的通信線路后即可快速傳遞數(shù)字信息.采用存儲-轉(zhuǎn)發(fā)方式在網(wǎng)絡(luò)上逐步傳遞信息,不象電話那樣直接、及時,但費用低廉.在通信雙方的計算機(jī)都開機(jī)工作的情況下即可快速傳遞數(shù)字信息以下屬于多媒體硬件的是( )(A).主機(jī)(B).光驅(qū)(C).聲卡 (D).音箱 (E).超級解霸17.正確的二維數(shù)組類型說明是( )(A)typear2=array[1..5,5..1]ofinteger;typear2=array[1..5]ofarray[5.1]ofinteger;typear2=array[1..5,1..5]ofinteger;typear2=array[1..5]ofarray[1..5]ofintegertypear2=array[1..5,1..5]of0..1下列屬于信息處理的是()(A)信息加工 (B)信息分類(C)信息技術(shù)(D)信息采集(E)信息存儲在windows中,最小化一個應(yīng)用程序窗口后，該程序?qū)? )。(A)被終止執(zhí)行(B)被暫停執(zhí)行(C)被轉(zhuǎn)入后臺(D)繼續(xù)執(zhí)行(E)以上答案都不對下面的常量說明中，正確的是()(A)CONST(B)、CONST(C)、CONST(D)、CONST(E)CONSTt=trueb,C=45M=100，15N=1OR2a='A'二、問題求解：(第1小題5分，第2-3小題各4分,共13分)[問題1]:在所有三位數(shù)中，各位數(shù)字從高位到低位順次減小的數(shù)共有 個。[問題2]："銀條"一位銀礦勘探員無力預(yù)付3月份的房租。他有一根長31英寸的純銀條，因此他和女房東達(dá)成如下協(xié)議。他說，他將把銀條切成小段。3月份的第一天，他給女房東1英寸長的一段，然后每天給她增加1英寸，以此作為抵押?？碧絾T預(yù)期到3月份的最后一天，他能全數(shù)付清租金，而屆時女房東將把銀條小段全部還給他。3月份有31天，一種辦法是把銀條切成31段，每段長1英寸?？墒沁@處花很多功夫。勘探員希望既履行協(xié)議，又能使銀條的分段數(shù)目盡量減少。例如，他可以第一天給女房東1英寸的一段，第二天再給1英寸的一段，第三開他取回這兩段1英寸的而給她3英寸的一段。假設(shè)銀條的各段是按照這種方式來回倒換的話，勘探員至少需要把他的銀條切成 段？[問題3]:"換不開的鈔票"錢柜里有1.15美分，一位顧客提出：把1美元的鈔票換成硬幣，但出納小姐說換不開，后來這位顧客提出：把50美分的鈔票換成硬幣，但出納小姐又說換不開，而實際上，出納小姐也無法把25美分、10美分、5美分的鈔票換成硬幣請問錢柜里到底有哪些硬幣？他們分別有多少枚？答： 。三、寫出程序的運行結(jié)果：（每小題6分，共30分）1.programtext1;constn=6;m=3;vari,j,k:integer;beginfori:=-ntondobegink:=n-abs(i);write('':39-k);forj:=-ktokdoifabs(j)>k-mthenwrite(n-(i+n)div2)elsewrite('');writeln;end;end.輸出的結(jié)果為：PROGAMtext2；VARa:ARRAY[1..10]OFChark:Integer；ch:Char；BEGINFORk:=1TO10DOa[k]:=Chr(Ord('A')+k)；FORk:=1TO10DOBEGINch:=a[k]；a[k]:=a[11-k]；a[11-k]:=ch；END；FORk:=1TO10DOWrite(a[k])；WritelnEND.輸出的結(jié)果為：programtext3(input,output);Varm,n,p:integer;x:real;proceduremm(varm:integer;x:real);varn:integer;beginm:=m+1;n:=m+1;x:=n*3;p:=n;end;beginm:=8;n:=5;p:=3;x:=1.0;mm(n,x);writeln(m:5,n:5,p:5,x:6:1);end.輸出的結(jié)果為：programtext4;constn=5;typeary=array[0..n-1,0..n-1]ofinteger;vara:ary;i,j,k:integer;beginfori:=0ton-1doforj:=0ton-1doa[i,j]:=0;k:=1;fori:=1tondoforj:=n-1downtoidobegina[j,j-i]:=k;k:=k+1;end;fori:=0ton-1dobeginforj:=0ton-1dowrite(a[I,j]:4);writeln;end;end.輸出的結(jié)果為：programtext5(input,output);varch:char;i,n,sum:integer;beginsum:=0;read(ch);casechof'A':fori:=4to6dobeginread(n):sum:=sum＋nend;'B'：beginread(n);fori:=1tondo

beginread(n);sum:=sum＋nend;end;'C':repeatread(n);sum:=sum＋nuntilsum>10;'D':beginread(n);whilen<=3dobeginsum:=sum＋n;read(n)endendend;writeln(sum:4)end.當(dāng)程序運行(1)輸入A4(2)輸入B(1)輸入A4(2)輸入B4(3)輸入C4(4)輸入D4111123456723456723456723456788889時9時9時9時其輸出為其輸出為其輸出為其輸出為四、完善程序(第1題每空2分第2、3題每空3分，共32分)第1題孿生素數(shù)是指兩個相差為2的素數(shù)，例如：3和5，5和7，11和13等下面程序可輸出15對孿生素數(shù)，其中函數(shù)q判斷整數(shù)a是否為素數(shù)。programp(output);vark,n:integerfuncti