1、第六年全國青少年信息學(計算機)奧林匹克分區普及組初賽聯賽試題第六年全國青少年信息學(計算機)奧林匹克分區普及組初賽聯賽試題8/8第六年全國青少年信息學(計算機)奧林匹克分區普及組初賽聯賽試題第六年全國青少年信息學（計算機）奧林匹克分區普及組初賽聯賽試題普及組PASCAL語言二小時完成全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效【一】選擇一個正確答案代碼A/B/C/D，填入每題的括號內(每題1.5共30分分，多項選擇無分，1、以下無符號數中，最小的數是、A、110110012B、7510C、378D、2A162、在外面設備中，繪圖儀屬于、A、輸入設備B、輸出設備C、輔外儲藏器D、主內儲

2、藏器3、GB2312-80規定了一級漢字3755個，二級漢字3008個，其中二級漢字字庫中的漢字是以為序排列的、A、以筆劃多少B、以部首C、以ASCII碼D、以機內碼4、算法是指、A、為解決問題而編制的計算機程序B、為解決問題而采用的方法與步驟C、為解決問題而需要采用的計算機語言D、為解決問題而采用的計算方法5、RAM中的信息是、A、生產廠家起初寫入的B、計算機工作時隨機寫入的C、防范計算機病毒侵入所使用的D、特地用于計算機開機時自檢用的6、計算機主機是由CPU與組成的、A、控制器B、運算器C、輸入、輸出設備D、內儲藏器7、計算機病毒的特點是、A、流傳性、暗藏性、易讀性與隱蔽性B、破壞性、流傳

3、性、暗藏性與安全性C、流傳性、暗藏性、破壞性與隱蔽性D、流傳性、暗藏性、破壞性與易讀性8、設循環隊列中數組的下標范圍是1n，其頭尾指針分別為f和r，那么其元素個數為、A、r-fB、r-f+1C、r-fMODn+1D、r-f+nMODn9、在待排序的數據表差不多為有序時，以下排序算法中開銷時間反而多的是、A堆排序B希爾排序C冒泡排序D快速排序10、Internet的規范譯名應為、A、英特爾網B、因特網C、萬維網D、以太網11、WINDOWS9X是一種操作系統、A、單任務字符方式B、單任務圖形方式C、多任務字符方式D、多任務圖形方式12、某種計算機的內存容量是640K,那個地方的640K容量是指(

4、)個字節、A、640B、640*1000C、640*1024D、640*1024*102413、在Windows9X中，菜單項后帶有符號“”，表示該菜單項()、A、能夠進行開關選擇B、執行時有對話框C、有假設干子命令D、不能夠執行14、某數列有1000個各不相同的單元，由低至高挨次排列；現要對該數列進行二分法檢索(binarysearch)，在最壞的情況下，需檢視()個單元、A、15、數組A中，每個元素AI，J在存貯時要占3個字節，設I從1變化到8，J從1變化到10，分配內存時是從地址SA開始連續按行存貯分配的。試問：A5，8的初步地址為、A、SA+141B、SA+180C、SA+222D、S

5、A+22516、大伙理解，不相同種類的儲藏器組成了多層次結構的儲藏器系統，排列是、按存取速度從快到慢的A、快存C、快存/輔存/主存/主存/輔存B、外存D、主存/主存/輔存/輔存/外存17、線性表假設采用鏈表存貯結構，要求內存中可用存貯單元地址、A、必定連續B、部分地址必定連續C、必然不連續D、連續不連續均可18、以下表達中，正確的選項是、A線性表的線性存貯結構優于鏈表存貯結構B隊列的操作方式是先進后出C棧的操作方式是先進先出D、二維數組是指它的每個數據元素為一個線性表的線性表19、電線上停著兩種鳥A，B，能夠看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類：一類是兩端的小鳥相同；另一

6、類那么是兩端的小鳥不相同、：電線兩個極點上正好停著相同的小鳥，試問兩端為不相同小鳥的線段數目必然是A、奇數B、偶數C、可奇可偶D、數目固定20、請仔細閱讀以下程序段:PASCAL語言BASIC語言、上列程序段的正確輸出是A、-1B、-2C、-3D、-4、【二】問題解答每題7分，共14分1、，按中序遍歷二叉樹的結果為：abc問：有多少種不相同形態的二叉樹能夠獲取這一遍歷結果，并畫出這些二叉樹。2、有2n的一個長方形方格，用一個此刻用一個12的骨牌鋪滿方格，共有12的骨牌鋪滿方格。比方3種鋪法：n=3時，為23方格。試對給出的任意一個nn0，求出鋪法總數的遞推公式。【三】閱讀程序，并寫出程序正確的

7、運行結果10+16分，共1、PROGRAMNOI_002;26分VARI,J,L,N,K,S,T:INTEGER;B:ARRAY1.10OF0.9;BEGINREADLN(L,N);S:=L;K:=1;T:=L;WHILES0DOBEGINJ:=J-1;BJ:=NMODL;N:=NDIVLEND;FORI:=10-K+1TO10DOWRITE(CHR(ORD(A)+BI);END.輸入：4167輸出：2、PROGRAMNOI_004;VARI,J,J1,J2,P,Q:INTEGER;P1:BOOLEAN;B,C:ARRAY1.100OFINTEGER;BEGINREADLN(Q,P);J:=1

8、;P1:=TRUE;BJ:=Q;J1:=0;WHILE(Q0)ANDP1DOBEGINJ1:=J1+1;CJ1:=Q*10DIVP;Q:=Q*10-CJ1*P;IFQ0THENBEGINJ2:=1;WHILE(BJ2Q)AND(J2=J)DOJ2:=J2+1;IFBJ2=QTHENBEGINP1:=FALSE;WRITE(0.);FORI:=1TOJ2-1DOWRITE(CI:1);WRITE();FORI:=J2TOJ1DOWRITE(CI:1);WRITELN()ENDELSEBEGINJ:=J+1;BJ:=QENDENDEND;IFQ=0THENBEGINWRITE(0.);FORI:=

9、1TOJ1DOWRITE(CI:1);WRITELNEND;READLNEND.輸入18輸出輸入27輸出【四】完滿程序每題15分，共30分1.將2n個0和2n個1，排成一圈。從任一個地址開始，每次按逆時針的方向以長度為n+1的單位進行數二進制數。要求給出一種排法，用上面的方法產生出來的2個二進制數都不相同。比方，當n=2時,即個0和個1排成以下一圈：A00101110比方，從A地址開始，逆時針方向取三個數000，爾后再從B地址上開始取三個數001，接著從C開始取三個數010，、能夠獲取000，001，010，101，011，111，110，100共8個二進制數且都不相同。程序說明以n=4為例，

10、即有16個0，16個1，數組a用以記錄32個0，1的排法，數組b統計二進制數可否已出現過。程序清單PROGRAMNOI00;VARA:ARRAY1.36OF0.1;B:ARRAY0.31OFINTEGER;I,J,K,S,P:INTEGER;BEGINFORI:=1TO36DOAI:=0;FORI:=28TO32DOAI:=1;P:=1;A6:=1;WHILE(P=1)DOBEGINJ:=27;WHILEAJ=1DOJ:=J-1;FORI:=J+1TO27DOFORI:=0TO31DOBI:=0;FORI:=1TO32DOBEGINFORK:=ITOI+4DOS:=S*2+AK;END;S:=

11、0;FORI:=0TO31DOS:=S+BI;IFTHENP:=0END;FORI:=1TO32DOFORJ：=ITOI+4DOWRITE(AJ);WRITELNEND.2、多項式的乘法。比如有以下多項式：P(X)=2X2-X+1,Q(X)=X+1那么：P(X)Q(X)=(2X2-X+1)(X+1)=2X3+X2+1程序說明：多項式的表示：系數、指數如上例中：P(X)：系數指數Q(X)系數指數2211-1110100000PXQ的結果存入C中。其輸出格式是：依次用一對括號內的系數，指數分別來表示。如上例的輸出結果表示為：2，31，21，0程序清單PROGRAMNOI_007;VARI,J,K,

12、L,JP,JQ,JC,X,Y,X1,Y1:INTEGER;P,Q:ARRAY1.10,1.2OFINTEGER;C:ARRAY1.20,1.2OFINTEGER;BEGINJP:=0;READLN(X,Y);WHILEX0DOBEGINJP:=JP+1;PJP,1:=X;PJP,2:=Y;READLN(X,Y)END;JQ:=0;READLN(X,Y);WHILEX0DOBEGINJQ:=JQ+1;QJQ,1:=X;QJQ,2:=Y;READLN(X,Y)END;JC:=1;CJC,1:=0;CJC,2:=-1000;FORI:=1TOJPDOBEGINY:=PI,2;FORJ:=1TOJQD

13、OBEGINY1:=Y+QJ,2;K:=1;WHILEY10，用FN表示其鋪法的總數的遞推公式為:7分賽區市學校姓名=密封線=【三】閱讀程序，并寫出程序的正確運行結果10+16分，共26分（1）程序的運行結果是:（2）程序的運行結果是:【四】依照題意，將程序補充完滿(每個點3分，共30分)PASCAL語言BASIC語言題一70110140180220題二190240280300350第六屆全國青少年信息學計算機奧林匹克分區聯賽初賽試題普及組參照答案【一】選擇一個正確答案代碼A/B/C/D，填入每題的括號內(每題1.5分，多項選擇無分，共30分題號1245678910選擇CBBBBDCDDB題號11121314151617181920選擇DCBBACDDBA【二】問題解答第1題的第1問2分，第2問5分，第2題7分，兩題共14分1、答：有5種不相同形態的二叉樹能夠獲取這一遍歷結果；可畫出的這些二叉樹為:abacc/baccab/cbba2、對給出的任意一個nn0，用Fn表示其鋪法的總數的遞推公式為:F1=1F2=2Fn=Fn-2+Fn-1n3【三】閱讀程序，并寫出程序的正確運行結果10+16分，共26分程序的運行結果是:BBAC程序的運行結果是:0.1250.2