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

1、杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新第七屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一 選擇一個正確答案代碼（A/B/C/D），填入每題的括號內(nèi)（每題1.5分，多選無分，共30分）1中央處理器CPU能訪問的最大存儲器容量取決于（ ）A）地址總線 B）數(shù)據(jù)總線 C）控制總線 D）內(nèi)存容量2計算機軟件保護(hù)法是用來保護(hù)軟件（ ）的。A）編寫權(quán) B）復(fù)制權(quán) C）使用權(quán) D）著作權(quán)364KB的存儲器用十六進(jìn)制表示，它的最大的地址碼是（ ）A）10000 B）FFFF C）1FFFF D）EFFF

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

3、 D）傳真92KB的內(nèi)存能存儲（ ）個漢字的機內(nèi)碼A）1024 B）516 C）2048 D）21810以下對Windows的敘述中，正確的是（ ）A）從軟盤上刪除的文件和文件夾，不送到回收站B）在同一個文件夾中，可以創(chuàng)建兩個同類、同名的文件C）刪除了某個應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新D）不能打開兩個寫字板應(yīng)用程序11運算式（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若已知一個棧的入棧順序是1，2，3，.，n，其輸出序列為P1，P2，P3，.，Pn，若P1是n，則Pi是（ ）A）i B)ni C)ni+1 D)不確定14計算機病毒是（ ）A） 通過計算機傳播的危害人體健康的一種病毒B） 人為制造的能夠侵入計算機系統(tǒng)并給計算機帶來故障的程序或指令集合C） 一種由于計算機元器件老化而產(chǎn)生的對生態(tài)環(huán)境有害的物質(zhì)D） 利用計算機的海量高速運算能力而研制出來的用于疾病預(yù)防的新型病毒E）15下面關(guān)于算法的錯誤說法是（ ）A）算法必須有輸出 B）算法必須在計算機上用某種語言實現(xiàn)C）算法不一定有輸入 D）算法必須在有限步執(zhí)行后能結(jié)束16x補碼=10011000，其原

5、碼為（ ）A）011001111 B）11101000 C）11100110 D）0110010117以下哪一個不是棧的基本運算（ ）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é)點的度為0，或為2，則此樹最少有（ ）個結(jié)點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)先遍歷，得到的頂點序列正確的是（ ）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é)點名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ 與 CGEBHFJIDA 則該二叉樹的先序遍歷的順序為：2 平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上，問用這些點為頂點，能組成多少個不同四邊形？三閱讀程序，寫出程序的正確運行結(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 存儲空間的回收算法。設(shè)在內(nèi)寸中已經(jīng)存放了若干個作業(yè)A，B，C，D。其余的空間為可用的（如圖一中（a）。下靠 上，下靠 上，下不靠 圖一（b）dk1.100，（a），其中：dki,1對應(yīng)第i個可用空間首址，dki,2對應(yīng)第i個可用空間長度如上圖中，

10、dk：表一（b）a） 表一（杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新現(xiàn)某個作業(yè)釋放一個區(qū)域，其首址為d，長度為L，此時將釋放區(qū)域加入到可用空間中。要求在加入時，若可用空間相鄰時，則必須進(jìn)行合并。因此出現(xiàn)下面的4種情況（如上圖一（b）所示）。（1） 下靠，即回收區(qū)域和下面可用空間相鄰，例如d=80，L=20，此時成為表二中的(a).（2） 上靠，例如，d=600，L=50，此時表成為表二中的（b）。（3） 上、下靠，例如，d=150，L=150，此時表成為表二中的（c）。d=430，L=20，此時表成為表二中的（d）。杭州市余杭高級中學(xué)信息學(xué)奧賽輔導(dǎo)資料 整理：管國新表二（a）（下靠）

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

14、過點J，具有如下的性質(zhì)：EETJ=ETJ2 約定：結(jié)點的排列已經(jīng)過拓?fù)渑判?，即序號前面的結(jié)點會影響序號后面結(jié)點的活動。程序清單：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）；輸入從活動X到活動Y的延續(xù)時間，以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語言）參考答案一、單項選擇題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二叉樹先序遍歷的順序為：ABCEG