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

2、不同目錄下 C)同一個磁盤的同一個目錄下5、下列設備哪一項不是計算機輸入設備( )A)鼠標 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)存容量8、Email郵件本質(zhì)上是一個( )A)文件 B)電報 C)電話 D)傳真9、2KB的內(nèi)存能存儲( )個漢字的機內(nèi)碼A)1024 B)516 C)2048 D)21810、以下對Wi

3、ndows的敘述中，正確的是( )A)從軟盤上刪除的文件和文件夾，不送到回收站B)在同一個文件夾中，可以創(chuàng)建兩個同類、同名的文件C)刪除了某個應用程序的快捷方式，將刪除該應用程序?qū)奈募﨑)不能打開兩個寫字板應用程序11、運算式(2047)10(3FF)16+(2000)8的結果是( )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.若已知一個棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( ) A)i B)n-1 C)n-i+1 D)不確定

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

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

6、b,c,f,dD)a,b,e,d,f,c二、問題求解(5+7=12分)1.已知一棵二叉樹的結點名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序為：2.平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？三、閱讀程序，寫出程序正確的運行結果(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

7、 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；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 ：

8、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：INTEGER；BEGINREADLN(X)；Y1：=0；Y2：=1；Y3：=1；WHILE Y2=X DOBEGINY1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3 END；

9、WRITELN(Y1)；END.輸入：23420輸出：四、完善程序(每空3分，共30分)1.存儲空間的回收算法。設在內(nèi)存中已經(jīng)存放了若干個作業(yè)A，B，C，D。其余的空間為可用的(如圖一中(a)。此時，可用空間可用一個二維數(shù)組dk1.100，1.2 表示，(如下表一中(a)，其中：dki，1對應第i個可用空間首址，dki，2對應第i個可用空間長度如上圖中，dk：1005030010050100 0 0100 50 300100 500 10010000 0 表一(a)表一(b)現(xiàn)某個作業(yè)釋放一個區(qū)域，其首址為d，長度為L，此時將釋放區(qū)域加入到可用空間表中。要求在加入時，若可用空間相鄰時，則必須進

10、行合并。因此出現(xiàn)下面的4種情況(如上圖一(b)所示)。(1)下靠，即回收區(qū)域和下面可用空間相鄰，例如，d=80，L=20，此時成為表二中的(a)。(2)上靠，例如，d=600，L=50，此時表成為表二中的(b)。(3)上、下靠，例如，d=150，L=150，此時表成為表二中的(c)。(4)上、下不靠，例如，d=430，L=20，此時表成為表二中的(d)。807030010050100100503001005001501003005001001005030010043020500100表二(a)(下靠)表二(b)(上靠)表二(c)(上，下靠)表二(d)(上，下不靠)程序說明：對數(shù)組dk預置2個標

11、志，即頭和尾標志，成為表二中(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 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)THENIF(D+L=DKI+1，1)THENBEGINDKI，2:=；FO

12、R J:=I+1 TO SP-1 DODKJ:=DKJ+1；SP：=SP-1； END ELSE DKI，2:=DKI，2+LELSE IF(D+L=DKI+1，1)THENBEGINDKI+1，1:=；DKI+1，2:=DKI+1，2+LEND ELSE BEGINFOR J:=SP DOWNTO I+1 DODKJ+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.求關鍵路徑 設有一個工程網(wǎng)絡如下圖表示(無環(huán)路的有向圖)： 其中，頂點表示活動，表示工程開始

13、，表示工程結束(可變，用N表示)，邊上的數(shù)字表示活動延續(xù)的時間。 如上圖中，活動開始5天后活動才能開始工作，而活動則要等、完成之后才能開始，即最早也要7天后才能工作。 在工程網(wǎng)絡中，延續(xù)時間最長的路徑稱為關鍵路徑。上圖中的關鍵路徑為：共18天完成。關鍵路徑的算法如下：1.數(shù)據(jù)結構：R1.N，1.NOF INTEGER；表示活動的延續(xù)時間，若無連線，則用-1表示； EET1.N表示活動最早可以開始的時間 ET1.N 表示活動最遲應該開始的時間 關鍵路徑通過點J，具有如下的性質(zhì)：EETJ=ETJ2.約定： 結點的排列已經(jīng)過拓撲排序，即序號前面的結點會影響序號后面結點的活動。程序清單：PROGRAM GAO7_6；VAR I，J，N，MAX，MIN，W，X，Y：INTEGER；R：ARRAY1.20，1.20OF INTEGER；EET，ET：ARRAY1.20OF INTEGER；BEGINREADLN(N)FOR I:=1 TO N DOFOR J:=1 TO N DO RI，J:=-1；READLN(X，Y，W)；輸入從活動X到活動Y的延續(xù)時間，以0為結束WHILE X0 DOBEGINRX，Y:=W；END；EET1：=0；認為工程從0天開始FOR I：=2 TO N DO BEGINMAX:=0；FOR J:=1 TO N DO IF RJ，