第七屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題及答案(提高組PA

1、杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新第七屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時(shí)完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一 選擇一個(gè)正確答案代碼（A/B/C/D），填入每題的括號內(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)364KB的存儲(chǔ)器用十六進(jìn)制表示，它的最大的地址碼是（ ）A）10000 B）FFFF C）1FFFF D）EFFF

2、F4在樹型目錄結(jié)構(gòu)中，不允許兩個(gè)文件名相同主要指的是（ ）A）同一個(gè)磁盤的不同目錄下 B）不同磁盤的同一個(gè)目錄下C）不同磁盤的不同目錄下 D）同一個(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)品的系列號C）每秒執(zhí)行300百萬條指令 D）此種CPU允許最大內(nèi)存容量8Email郵件本質(zhì)上是一個(gè)（ ）A）文件 B）電報(bào) C）電話

3、 D）傳真92KB的內(nèi)存能存儲(chǔ)（ ）個(gè)漢字的機(jī)內(nèi)碼A）1024 B）516 C）2048 D）21810以下對Windows的敘述中，正確的是（ ）A）從軟盤上刪除的文件和文件夾，不送到回收站B）在同一個(gè)文件夾中，可以創(chuàng)建兩個(gè)同類、同名的文件C）刪除了某個(gè)應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新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）1612TCP/IP協(xié)議共有（ ）層協(xié)議A）3 B）4 C）5 D）

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

5、碼為（ ）A）011001111 B）11101000 C）11100110 D）0110010117以下哪一個(gè)不是棧的基本運(yùn)算（ ）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）2h1 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

6、,f),(f,d),(e,d) 對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ ）A）a,b,c,d,e,f B) a,c,f,e,b,d C) a,e,b,c,f,d D) a,b,e,d,f,c杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新二問題求解（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é)果

7、（4+7+8+9=28分）1 PROGRAM GAO7_1；FUNCTION ACK（M，N：INTEGER）：INTEGER；BEGINIF M=0 THEN ACK：=N+1ELSE IF N=0 THEN ACK：=ACK（M1，1）ELSE ACK：=ACK（M1，ACK（M，N1）END；BEGINWRITELN（ACK（3，4）；READLN；END.輸出：2 PROGRAM GAO7_2；VAR P，Q，S，T：INTEGER；BEGINREADLN（P）；FOR Q：=P+1 TO 2*P DOBEGINT：=0；S：=（P*Q）MOD （Q）；IF S=0 THENBEGIN

8、 T：=P+Q+（P*Q） DIV （QP）；WRITE（T：4）；END；END；END.輸入：12 輸出：3 PROGRAM GAO7_3；VAR I，J，H，M，N，K：INTEGER；B：ARRAY1.10 OF INTEGER；BEGINREADLN（N）；FOR I：=1 TO 10 DOBEGINM：=N；J：=11；杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新WHILE M>0 DOBEGIN J：=J1；BJ：=M MOD 10；M：=M DIV 10 END；FOR H：=J TO 10 DO N：=N+BH；END；WRITELN（N）；END.輸入：1234

9、 輸出：4 PROGRAM GAO7_4；VAR X，Y1，Y2，Y3：INTEGER；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）。下靠 上，下靠 上，下不靠 圖一（b）dk1.100，（a），其中：dki,1對應(yīng)第i個(gè)可用空間首址，dki,2對應(yīng)第i個(gè)可用空間長度如上圖中，

10、dk：表一（b）a） 表一（杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新現(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í)表成為表二中的（c）。d=430，L=20，此時(shí)表成為表二中的（d）。杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新表二（a）（下靠）

11、 表二（b） （上靠） 表二（c） （上、下靠） 表二（d） （上、下不靠） 程序說明：對數(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.2 OF INTEGER；BEGINREADLN（SP）；FOR I：=1 TO SP DOREADLN（DK（I，1），DKI，2）；DK0，1：=0；DK0，2：=0： ；DKSP，1：=10000；DKSP，2：=0；READLN（D，L）；I：=1；WHILE DKI，1<D DO I：

12、=I+1； ；IF （DKI，1+DKI，2=D） THENIF （D+L=DKI+1，1 THENBEGINDKI，2：= ； FOR J：=I+1 TO SP1 DODKJ：=DKJ+1；SP：=SP1；ENDELSE IF （D+L=DKI+1，1） THENBEGINDKI+1，1：= ； DKI+1，2：=DKI+1，2+L；ENDELSE BEGINFOR J：=SP DOWNTO I+1 DO DKJ+1：=DKJ； ：=D；DKI+1，2：=L；SP：=SP+1；END；FOR I：=1 TO SP DO WRITELN(DKI,1：4，DKI，2：4)；READLN； END

13、.2 關(guān)鍵路徑設(shè)有一個(gè)工程網(wǎng)絡(luò)如下圖表示（無環(huán)路的有向圖）：其中，頂點(diǎn)表示活動(dòng)，表示工程開始，表示工程結(jié)束（可變，用N表示），邊 6杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新上的數(shù)字表示活動(dòng)延續(xù)的時(shí)間。2 如上圖中，活動(dòng)開始5天后活動(dòng)才能開始，而活動(dòng)則要等、完成之后才能開始，即最早也要7天后才能工作。在工程網(wǎng)絡(luò)中，延續(xù)時(shí)間最長的路徑稱為關(guān)鍵路徑。上圖中的關(guān)鍵路徑為： 共18天完成。關(guān)鍵路徑的算法如下：1 數(shù)據(jù)結(jié)構(gòu)：R1.N，1.N OF INTEGER；表示活動(dòng)的延續(xù)時(shí)間，若無連線，則用 1表示；EET1.N 表示活動(dòng)最早可以開始的時(shí)間；ET1.N 表示活動(dòng)最遲應(yīng)該開始的時(shí)間關(guān)鍵路徑通

14、過點(diǎn)J，具有如下的性質(zhì)：EETJ=ETJ2 約定：結(jié)點(diǎn)的排列已經(jīng)過拓?fù)渑判颍葱蛱柷懊娴慕Y(jié)點(diǎn)會(huì)影響序號后面結(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 DOFOR J：=1 TO N DORI，J：=-1；READLN（X，Y，W）；輸入從活動(dòng)X到活動(dòng)Y的延續(xù)時(shí)間，以0為結(jié)束WHILE X<>0 DOBEGINRX，Y：=W； ；END；EET1

15、：=0；認(rèn)為工程從0天開始FOR I：=2 TO N DOBEGINMAX：=0；FOR J：=1 TO N DOIF RJ，I<> 1 THEN杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新IF THEN MAX：=RJ，I+EETJ； EETI：=MAX；END；FOR I：=N1 DOWNTO 1 DOBEGINMIN：=10000；FOR J：=1 TO N DOIF RI，J<> 1 THENIF ETI：=MIN；END；WRITELN（EETN）；FOR I：=1 TO N1 DOIF THENWRITE（N）；READLN； END. THEN MIN：=ETJRI，J；WRITE（I，>）；杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新NOIP2001年（第七屆）提高組（Pascal語言）參考答案一、單項(xiàng)選擇題1. A 2. D 3. B 4. D 5. C或D 6. D 7. A 8. A 9. A 10.A11. A 12. C 13. C 14. B 15. B 16. B 17. B 18. C 19. B 20. D二、問題求解（5+7分，兩題共12分）1二叉樹先序遍歷的順序?yàn)椋篈BCEG