第六年全國(guó)青少年信息學(xué)奧林匹克分區(qū)普組初賽聯(lián)賽試題

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

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

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

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

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

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

7、運(yùn)行結(jié)果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個(gè)0和2n個(gè)1，排成一圈。從任一個(gè)地址開(kāi)始，每次按逆時(shí)針的方向以長(zhǎng)度為n+1的單位進(jìn)行數(shù)二進(jìn)制數(shù)。要求給出一種排法，用上面的方法產(chǎn)生出來(lái)的2個(gè)二進(jìn)制數(shù)都不相同。比方，當(dāng)n=2時(shí),即個(gè)0和個(gè)1排成以下一圈：A00101110比方，從A地址開(kāi)始，逆時(shí)針?lè)较蛉∪齻€(gè)數(shù)000，爾后再?gòu)腂地址上開(kāi)始取三個(gè)數(shù)001，接著從C開(kāi)始取三個(gè)數(shù)010，、能夠獲取000，001，010，101，011，111，110，100共8個(gè)二進(jìn)制數(shù)且都不相同。程序說(shuō)明以n=4為例，

10、即有16個(gè)0，16個(gè)1，數(shù)組a用以記錄32個(gè)0，1的排法，數(shù)組b統(tǒng)計(jì)二進(jìn)制數(shù)可否已出現(xiàn)過(guò)。程序清單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、多項(xiàng)式的乘法。比如有以下多項(xiàng)式：P(X)=2X2-X+1,Q(X)=X+1那么：P(X)Q(X)=(2X2-X+1)(X+1)=2X3+X2+1程序說(shuō)明：多項(xiàng)式的表示：系數(shù)、指數(shù)如上例中：P(X)：系數(shù)指數(shù)Q(X)系數(shù)指數(shù)2211-1110100000PXQ的結(jié)果存入C中。其輸出格式是：依次用一對(duì)括號(hào)內(nèi)的系數(shù)，指數(shù)分別來(lái)表示。如上例的輸出結(jié)果表示為：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表示其鋪法的總數(shù)的遞推公式為:7分賽區(qū)市學(xué)校姓名=密封線=【三】閱讀程序，并寫出程序的正確運(yùn)行結(jié)果10+16分，共26分（1）程序的運(yùn)行結(jié)果是:（2）程序的運(yùn)行結(jié)果是:【四】依照題意，將程序補(bǔ)充完滿(每個(gè)點(diǎn)3分，共30分)PASCAL語(yǔ)言BASIC語(yǔ)言題一70110140180220題二190240280300350第六屆全國(guó)青少年信息學(xué)計(jì)算機(jī)奧林匹克分區(qū)聯(lián)賽初賽試題普及組參照答案【一】選擇一個(gè)正確答案代碼A/B/C/D，填入每題的括號(hào)內(nèi)(每題1.5分，多項(xiàng)選擇無(wú)分，共30分題號(hào)1245678910選擇CBBBBDCDDB題號(hào)11121314151617181920選擇DCBBACDDBA【二】問(wèn)題解答第1題的第1問(wèn)2分，第2問(wèn)5分，第2題7分，兩題共14分1、答：有5種不相同形態(tài)的二叉樹(shù)能夠獲取這一遍歷結(jié)果；可畫出的這些二叉樹(shù)為:abacc/baccab/cbba2、對(duì)給出的任意一個(gè)nn0，用Fn表示其鋪法的總數(shù)的遞推公式為:F1=1F2=2Fn=Fn-2+Fn-1n3【三】閱讀程序，并寫出程序的正確運(yùn)行結(jié)果10+16分，共26分程序的運(yùn)行結(jié)果是:BBAC程序的運(yùn)行結(jié)果是:0.1250.2