NOIP2001提高組初賽試題答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第七屆分區(qū)聯(lián)賽提高組初賽(提高組PASCAL語(yǔ)言二小時(shí)完成)一、選擇一個(gè)正確答案代碼(A/B/C/D)，填入每題的括號(hào)內(nèi)(每題1.5分，多選無(wú)分，共30分)1、中央處理器CPU能訪問(wèn)的最大存儲(chǔ)器容量取決于( )A)地址總線 B)數(shù)據(jù)總線 C)控制總線 D)內(nèi)存容量2、計(jì)算機(jī)軟件保護(hù)法是用來(lái)保護(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、在樹(shù)型目錄結(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、若我們說(shuō)一個(gè)微機(jī)的CPU是用的PII300，此處的300確切指的是( )A)CPU的主時(shí)鐘頻率 B)CPU產(chǎn)品的系列號(hào)C)每秒執(zhí)行300百萬(wàn)條指令 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)2048

3、D)21810、以下對(duì)Windows的敘述中，正確的是( )A)從軟盤上刪除的文件和文件夾，不送到回收站B)在同一個(gè)文件夾中，可以創(chuàng)建兩個(gè)同類、同名的文件C)刪除了某個(gè)應(yīng)用程序的快捷方式，將刪除該應(yīng)用程序?qū)?yīng)的文件D)不能打開(kāi)兩個(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)6 13.若已知一個(gè)棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( ) A)i B)n-1

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

5、序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關(guān)鍵碼比較的次數(shù)為( )A)2 B)3 C)4 D)519.一棵二叉樹(shù)的高度為h，所有結(jié)點(diǎn)的度為0，或?yàn)?，則此樹(shù)最少有( )個(gè)結(jié)點(diǎn)A)2h-1 B)2h-1 C)2h+1 D)h+120.無(wú)向圖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,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,b,e,d,f,c二、問(wèn)題求解(5

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

7、CK(M-1，ACK(M，N-1)END； BEGIN WRITELN(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-P)；IF S=0 THEN BEGIN T:=P+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；BEGINREA

8、DLN(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：INTEGER；BEGINREADLN(X)；Y1：=0；Y2：=1；Y3：=1；WHILE Y2=X DOBEGINY1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3 END；WRITELN(Y1)；END.輸入：23420輸出：四

9、、完善程序(每空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è)可用空間長(zhǎng)度如上圖中，dk：1005030010050100 0 0100 50 300100 500 10010000 0 表一(a)表一(b)現(xiàn)某個(gè)作業(yè)釋放一個(gè)區(qū)域，其首址為d，長(zhǎng)度為L(zhǎng)，此時(shí)將釋放區(qū)域加入到可用空間表中。要求在加入時(shí)，若可用空間相鄰時(shí)，則必須進(jìn)行合并。因此出現(xiàn)下面的4種情況(如上圖一(b)所示)。(

10、1)下靠，即回收區(qū)域和下面可用空間相鄰，例如，d=80，L=20，此時(shí)成為表二中的(a)。(2)上靠，例如，d=600，L=50，此時(shí)表成為表二中的(b)。(3)上、下靠，例如，d=150，L=150，此時(shí)表成為表二中的(c)。(4)上、下不靠，例如，d=430，L=20，此時(shí)表成為表二中的(d)。807030010050100100503001005001501003005001001005030010043020500100表二(a)(下靠)表二(b)(上靠)表二(c)(上，下靠)表二(d)(上，下不靠)程序說(shuō)明：對(duì)數(shù)組dk預(yù)置2個(gè)標(biāo)志，即頭和尾標(biāo)志，成為表二中(b)，這樣可使算法簡(jiǎn)單，s

11、p為dk表末地址。程序清單：var i,j,sp,d,l:integer; dk:array0.100,1.2of integer;begin readln(sp); for i:=1 to sp do readln(dki,1,dki,2); dk0,1:=0;dk0,2:=0; _; dksp,1:=10000;dksp,2:=0; readln(d,l); i:=1; while dki,1d do i:=i+1; _; if (dki,1+dki,2=d) then if (d+l=dki+1,1) then begin dki,2:=_; for j:=i+1 to sp-1 do

12、dkj:=dkj+1; sp:=sp-1; end else dki,2:=dki,2+l /l 不是1 else if (d+l=dki+1,1) then begin dki+1,1:=_; dki+1,2:=dki+1,2+l end else begin for 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ò)如下圖表示(無(wú)環(huán)路的有向圖)： 其中，頂點(diǎn)表示活

13、動(dòng)，表示工程開(kāi)始，表示工程結(jié)束(可變，用N表示)，邊上的數(shù)字表示活動(dòng)延續(xù)的時(shí)間。 如上圖中，活動(dòng)開(kāi)始5天后活動(dòng)才能開(kāi)始工作，而活動(dòng)則要等、完成之后才能開(kāi)始，即最早也要7天后才能工作。 在工程網(wǎng)絡(luò)中，延續(xù)時(shí)間最長(zhǎng)的路徑稱為關(guān)鍵路徑。上圖中的關(guān)鍵路徑為：共18天完成。關(guān)鍵路徑的算法如下：1.數(shù)據(jù)結(jié)構(gòu)： R1.N，1.NOF INTEGER；表示活動(dòng)的延續(xù)時(shí)間，若無(wú)連線，則用-1表示； EET1.N表示活動(dòng)最早可以開(kāi)始的時(shí)間 ET1.N 表示活動(dòng)最遲應(yīng)該開(kāi)始的時(shí)間 關(guān)鍵路徑通過(guò)點(diǎn)J，具有如下的性質(zhì)：EETJ=ETJ2.約定： 結(jié)點(diǎn)的排列已經(jīng)過(guò)拓?fù)渑判?，即序?hào)前面的結(jié)點(diǎn)會(huì)影響序號(hào)后面結(jié)點(diǎn)的活動(dòng)。程序清

14、單：var i,j,n,max,min,w,x,y:integer; r:array1.20,1.20of integer; eet,et:array1.20of integer;begin readln(n); for i:=1 to n do for j:=1 to n do ri,j:=-1; readln(x,y,w); while x0 do begin rx,y:=w; _; end; eet1:=0; for i:=2 to n do begin max:=0; for j:=1 to n do if rj,i-1 then if _ then max:=rj,i+eetj; e

15、eti:=max; end; _ for i:=n-1 downto 1 do begin min:=1000; for j:=1 to n do if ri,j-1 then if _ then min:=etj-ri,j; eti:=min; end; writeln(eetn); for i:=1 to n-1 do if _ then write(i,); writeln(n); readln;end.第七屆全國(guó)青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽試題 (普及組參考答案)一、選擇一個(gè)正確答案代碼(A/B/C/D)，填入每題的括號(hào)內(nèi)(每題1.5分，多選無(wú)分，共30分)題號(hào)12345678910選擇CDBDBCDCAA題號(hào)11121314151617181920選擇ACBAABCDCC二、問(wèn)題解答(5+7分，兩題共12分)1.答：在a,b,c,d,e,f六件物品中，按條件能選出的物品是：a,b,c,f2.答：用這些點(diǎn)為頂點(diǎn)，能組成75