第十一屆全國青少年信息學(xué)計(jì)算機(jī)奧林匹克分區(qū)聯(lián)賽初賽試題

1、第十一屆全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽試題(提高組PASCAL語言 二小時(shí)完成)一、選擇一個(gè)正確答案代碼(A/B/C/D)，填入每題的括號(hào)內(nèi)(每題1.5分，多選無分，共30分)1、中央處理器CPU能訪問的最大存儲(chǔ)器容量取決于( )A)地址總線 B)數(shù)據(jù)總線 C)控制總線 D)內(nèi)存容量2、計(jì)算機(jī)軟件保護(hù)法是用來保護(hù)軟件( )的。A)編寫權(quán) B)復(fù)制權(quán) C)使用權(quán) D)著作權(quán)3、64KB的存儲(chǔ)器用十六進(jìn)制表示，它的最大的地址碼是( )A)10000 B)FFFF C)1FFFF D)EFFFF4、在樹型目錄結(jié)構(gòu)中，不允許兩個(gè)文件名相同主要指的是( )A)同一個(gè)磁盤的不同目錄下 B)

2、不同磁盤的同一個(gè)目錄下C)不同磁盤的不同目錄下 C)同一個(gè)磁盤的同一個(gè)目錄下5、下列設(shè)備哪一項(xiàng)不是計(jì)算機(jī)輸入設(shè)備( )A)鼠標(biāo) B)掃描儀 C)數(shù)字化儀 D)繪圖儀6、在計(jì)算機(jī)硬件系統(tǒng)中，cache是( )存儲(chǔ)器A)只讀 B)可編程只讀 C)可擦除可編程只讀 D)高速緩沖7、若我們說一個(gè)微機(jī)的CPU是用的PII300，此處的300確切指的是( )A)CPU的主時(shí)鐘頻率 B)CPU產(chǎn)品的系列號(hào)C)每秒執(zhí)行300百萬條指令 D)此種CPU允許最大內(nèi)存容量8、Email郵件本質(zhì)上是一個(gè)( )A)文件 B)電報(bào) C)電話 D)傳真9、2KB的內(nèi)存能存儲(chǔ)( )個(gè)漢字的機(jī)內(nèi)碼A)1024 B)516 C)

3、2048 D)21810、以下對(duì)Windows的敘述中，正確的是( )A)從軟盤上刪除的文件和文件夾，不送到回收站B)在同一個(gè)文件夾中，可以創(chuàng)建兩個(gè)同類、同名的文件C)刪除了某個(gè)應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件D)不能打開兩個(gè)寫字板應(yīng)用程序11、運(yùn)算式(2047)10(3FF)16+(2000)8的結(jié)果是( )A)(2048)10 B)(2049)10 C)(3746)8 D)(1AF7)1612、TCP/IP協(xié)議共有( )層協(xié)議A)3 B)4 C)5 D)613.若已知一個(gè)棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( )A)i B)n

4、-1 C)n-i+1 D)不確定14.計(jì)算機(jī)病毒是( )A)通過計(jì)算機(jī)傳播的危害人體健康的一種病毒B)人為制造的能夠侵入計(jì)算機(jī)系統(tǒng)并給計(jì)算機(jī)帶來故障的程序或指令集合C)一種由于計(jì)算機(jī)元器件老化而產(chǎn)生的對(duì)生態(tài)環(huán)境有害的物質(zhì)D)利用計(jì)算機(jī)的海量高速運(yùn)算能力而研制出來的用于疾病預(yù)防的新型病毒15.下面關(guān)于算法的錯(cuò)誤說法是( )A)算法必須有輸出 B)算法必須在計(jì)算機(jī)上用某種語言實(shí)現(xiàn)C)算法不一定有輸入 D)算法必須在有限步執(zhí)行后能結(jié)束16.x補(bǔ)碼=10011000，其原碼為( )A)011001111 B)11101000 C)11100110 D)0110010117.以下哪一個(gè)不是棧的基本運(yùn)算(

5、 )A)刪除棧頂元素 B)刪除棧底的元素C)判斷棧是否為空 D)將棧置為空棧18.在順序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關(guān)鍵碼比較的次數(shù)為( )A)2 B)3 C)4 D)519.一棵二叉樹的高度為h，所有結(jié)點(diǎn)的度為0，或?yàn)?，則此樹最少有( )個(gè)結(jié)點(diǎn)A)2h-1 B)2h-1 C)2h+1 D)h+120.無向圖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) 對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是( )A)a,b,e,c,d,f B)a,

6、c,f,e,b,d C)a,e,b,c,f,d D)a,b,e,d,f,c二、問題求解(5+7=12分)1.已知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序?yàn)椋?.平面上有三條平行直線，每條直線上分別有7，5，6個(gè)點(diǎn)，且不同直線上三個(gè)點(diǎn)都不在同一條直線上。問用這些點(diǎn)為頂點(diǎn)，能組成多少個(gè)不同四邊形？三、閱讀程序，寫出程序正確的運(yùn)行結(jié)果(4+7+8+9=28分)1.PROGRAM GAO7_1：FUNCTION ACK(M，N：INTEGER)：INTEGER；作者： 218.94.125.* 2005-9-1

7、4 20:01 回復(fù)此發(fā)言-2 獨(dú)家透密:今年全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽試題BEGINIF M=0 THEN ACK：=N+1ELSE IF N=0 THEN ACK:=ACK(M-1，1)ELSE ACK:=ACK(M-1，ACK(M，N-1)END；BEGIN WRITELN(ACK(3，4)； READLN； END.輸出2.PROGRAM GAO7_2；VAR P，Q，S，T：INTEGER； BEGIN READLN(P)； FOR Q：=P+1 TO 2*P DOBEGINT:=0；S:=(P*Q)MOD(Q-P)；IF S=0 THEN BEGIN T:=P+

8、Q+(P*Q)DIV(Q-P)；WRITE(T：4)；END；END；END.輸入12 輸出3.PROGRAM GAO7_3；VAR I，J，H，M，N，K：INTEGER；B ：ARRAY1.10OF INTEGER；BEGINREADLN(N)；FOR I:=1 TO 10 DOBEGINM：=N；J：=11；WHILE M0 DOBEGIN J:=J-1；BJ：=M MOD 10；M:=M DIV 10 END；FOR H:=J TO 10 DO N:=N+BH；END；WRITELN(N)；END.輸入1234 輸出：4.PROGRAM GAO7_4；VAR X，Y1，Y2，Y3：IN

9、TEGER；BEGINREADLN(X)；Y1：=0；Y2：=1；Y3：=1；WHILE Y2=X DOBEGINY1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3END；WRITELN(Y1)；END.輸入：23420 輸出：四、完善程序(每空3分，共30分)1.存儲(chǔ)空間的回收算法。設(shè)在內(nèi)存中已經(jīng)存放了若干個(gè)作業(yè)A，B，C，D。其余的空間為可用的(如圖一中(a)。此時(shí)，可用空間可用一個(gè)二維數(shù)組dk1.100，1.2 表示，(如下表一中(a)，其中：dki，1對(duì)應(yīng)第i個(gè)可用空間首址，dki，2對(duì)應(yīng)第i個(gè)可用空間長度如上圖中，dk：100 50300 10050 1000 0100 5030

10、0 100500 10010000 0表一(a) 表一(b)現(xiàn)某個(gè)作業(yè)釋放一個(gè)區(qū)域，其首址為d，長度為L，此時(shí)將釋放區(qū)域加入到可用空間表中。要求在加入時(shí)，若可用空間相鄰時(shí)，則必須進(jìn)行合并。因此出現(xiàn)下面的4種情況(如上圖一(b)所示)。(1)下靠，即回收區(qū)域和下面可用空間相鄰，例如，d=80，L=20，此時(shí)成為表二中的(a)。(2)上靠，例如，d=600，L=50，此時(shí)表成為表二中的(b)。(3)上、下靠，例如，d=150，L=150，此時(shí)表成為表二中的。(4)上、下不靠，例如，d=430，L=20，此時(shí)表成為表二中的(d)。80 70300 10050 100100 50300 100500

11、150100 300500 100100 50300 100430 20500 100表二(a)(下靠) 表二(b)(上靠) 表二(上，下靠) 表二(d)(上，下不靠)程序說明：對(duì)數(shù)組dk預(yù)置2個(gè)標(biāo)志，即頭和尾標(biāo)志，成為表二中(b)，這樣可使算法簡單，sp為dk表末地址。程序清單：PROGRAM GAO7_5；VAR I，J，SP，D，L：INTEGER；DK ：ARRAY0.100，1.2OF INTEGER；BEGINREADLN(SP)；FOR I:=1 TO SP DOREADLN(DKI，1，DKI，2)；DK0，1:=0；DK0，2:=0； ；DKSP，1:=10000；DKSP，

12、2:=0；READLN(D，L)；I:=1；WHILE DKI，1D DO I:=I+1； ；IF(DKI，1+DKI，2=D)THENIF(D+L=DKI+1，1)THENBEGINDKI，2:= ；FOR J:=I+1 TO SP-1 DODKJ:=DKJ+1；SP：=SP-1；ENDELSE DKI，2:=DKI，2+LELSE IF(D+L=DKI+1，1)THENBEGINDKI+1，1:= ；DKI+1，2:=DKI+1，2+L作者： 218.94.125.* 2005-9-14 20:01 回復(fù)此發(fā)言-3 獨(dú)家透密:今年全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽試題ENDEL

13、SE BEGINFOR J:=SP DOWNTO I+1 DO DKJ+1:=DKJ； :=D； DKI+1，2:=L；SP:=SP+1；END；FOR I:=1 TO SP-1 DO WRITELN(DKI，1:4，DKI，2:4)；READLN； END.2.求關(guān)鍵路徑設(shè)有一個(gè)工程網(wǎng)絡(luò)如下圖表示(無環(huán)路的有向圖)：其中，頂點(diǎn)表示活動(dòng)，表示工程開始，表示工程結(jié)束(可變，用N表示)，邊上的數(shù)字表示活動(dòng)延續(xù)的時(shí)間。如上圖中，活動(dòng)開始5天后活動(dòng)才能開始工作，而活動(dòng)則要等、完成之后才能開始，即最早也要7天后才能工作。在工程網(wǎng)絡(luò)中，延續(xù)時(shí)間最長的路徑稱為關(guān)鍵路徑。上圖中的關(guān)鍵路徑為：共18天完成。關(guān)鍵

14、路徑的算法如下：1.數(shù)據(jù)結(jié)構(gòu)：R1.N，1.NOF INTEGER； 表示活動(dòng)的延續(xù)時(shí)間，若無連線，則用-1表示； EET1.N 表示活動(dòng)最早可以開始的時(shí)間ET1.N 表示活動(dòng)最遲應(yīng)該開始的時(shí)間關(guān)鍵路徑通過點(diǎn)J，具有如下的性質(zhì)：EETJ=ETJ2.約定：結(jié)點(diǎn)的排列已經(jīng)過拓?fù)渑判颍葱蛱?hào)前面的結(jié)點(diǎn)會(huì)影響序號(hào)后面結(jié)點(diǎn)的活動(dòng)。 程序清單：PROGRAM GAO7_6；VAR I，J，N，MAX，MIN，W，X，Y：INTEGER；R：ARRAY1.20，1.20 OF INTEGER；EET，ET：ARRAY1.20 OF INTEGER；BEGINREADLN(N)FOR I:=1 TO N DO

15、FOR J:=1 TO N DORI，J:=-1；READLN(X，Y，W)；輸入從活動(dòng)X到活動(dòng)Y的延續(xù)時(shí)間，以0為結(jié)束WHILE X0 DOBEGINRX，Y:=W； END；EET1：=0；認(rèn)為工程從0天開始FOR I：=2 TO N DOBEGINMAX:=0；FOR J:=1 TO N DOIF RJ，I-1 THENIF THEN MAX:=RJ，I+EETJ；EETI:=MAX；END；FOR I：=N-1 DOWNTO 1 DOBEGINMIN：=10000；FOR J：=1 TO N DOIF RI，J-1 THENIF THEN MIN：=ETJ - RI，J； ETI：=M

16、IN； END； WRITELN(EETN)；FOR I：=1 TO N -1 DOIF THEN WRITE(I，)；WRITE(N)；READLNEND.第十一屆全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽試題(提高組參考答案)一、選擇一個(gè)正確答案代碼(A/B/C/D)，填入每題的括號(hào)內(nèi)(每題1.5分，多選無分，共30分) 題號(hào) 1 2 3 4 5 6 7 8 9 10選擇 A D B D C D A A A A題號(hào) 11 12 13 14 15 16 17 18 19 20選擇 A C C B B B B C B D二、問題解答(5+7分，兩題共12分)1.答：該二叉樹先序遍歷的順序?yàn)椋篈BCEGDFHIJ2.答：用這些點(diǎn)為頂點(diǎn)，能組成2250個(gè)不