NOIP2010第十六屆初賽試題及答案分析

1、第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組 Pascal 語言 兩小時(shí)完成? 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ?一. 單項(xiàng)選擇題共 20 題，每題 1.5 分，共計(jì) 30 分。每題有且僅有一個(gè)正確 答 案。1.2E 03 表示 。C.8 D.2000A. 2.03 B.52. 一個(gè)字節(jié) byte 由 個(gè)二進(jìn)制位組成。A. 8 B.16 C.32 D. 以上都有可 能3. 以下邏輯表達(dá)式的值恒為真的是A. PV PA Q V Q C. P V QV P AQ V PA Q Q。B. QV PA Q V P AQ D.PV QV P A Q V A4. Linux 下

2、可執(zhí)行文件的默認(rèn)擴(kuò)展名為 A.exeB C.dllD.以是都不是A. 如果樹根算是第1層，那么一棵n層的二叉釁多有結(jié)點(diǎn)26.提出“存儲(chǔ)程序 的計(jì)算機(jī)工作原理的是 。A.克勞德？香農(nóng)B.戈登？摩爾C.查爾斯？巴比奇D.馮？諾依曼7.設(shè)X、丫、Z 分別代表三進(jìn)制下的一位數(shù)字， 假設(shè)等式 XY+ ZX= XYX 在三進(jìn)制下成 立，那么同 樣在三進(jìn)制下，等式 XYX ZX=也成立。A.YXZB.ZXYC.XYZD.XZY9. 前綴表達(dá)式“ + 3X 2+ 5 12 的值是 。A.23B.25C.37D.6510. 主存儲(chǔ)器的存取速度比中央處理器 CPU 的工作速度慢得多，從而使得后者 的效率受到影響。

3、而根據(jù)局部性原理， CPU 所訪問的存儲(chǔ)單元通常都趨于聚集在 一 個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率， 在 CPU 中引入了。A.存放器B.高速緩存C.閃存D.外存11. 一個(gè)字長為 8 位的整數(shù)的補(bǔ)碼是A.00000111B.0111100111111001, 那么它的原碼是 。C. 11111001D.10000111，其中 n 表示待排序的元素個(gè)數(shù) 2C.Olog nd.On A.5nB.n*log 210C.10*log 2nD.10 log 2n12. 基于比擬的排序時(shí)間復(fù)雜度的下限是 A.OnB.On log n13. 一個(gè)自然數(shù)在十進(jìn)制下有 n 位，那么它在二進(jìn)

4、制下的位數(shù)與 最接近14. 在以下HTMIS句中，可以正確產(chǎn)生一個(gè)指向NOI官方網(wǎng)站的超鏈接的是A. va url= :/ noi 歡送>訪問 NOI 網(wǎng)站</ a>B. <a href= :/ noi 歡送訪問 NOI 網(wǎng)站 </a>C. <a> :/ noi < a>D. <a name= :/ noi 歡送訪問 NOI 網(wǎng)站</ a>15. 元素 R1、R2 R3 R4 R5 入棧的順序?yàn)?R1、R2 R3 R4 R5 如果第 1個(gè) 出棧的是R3,那么第5個(gè)出棧的不可能是。A.R1B.R2C.R4D.R516.

5、 雙向鏈表中有兩個(gè)指針域 llink 的 rlink ，分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均非空。現(xiàn)要求刪除結(jié)點(diǎn)P,那么下面語句序列中錯(cuò)誤的選項(xiàng)是 。A. pdrli nkdlli nk=pdrli nk;pil li nkdrli nk=pAli nk;dispose p;B. pdlli nkdrli nk=pdrli nk;pirli nkdl li nk=pA .l li nk;disposep;C. pUli nkTli nk=pTli nk;pirli nkdl li nkdrli nk=pdrli nk;dispose p;D. pdlli nkd

6、rli nk=pdrli nk;pA.Ili nkdrli nkdlli nk=pdlli nk;dispose p;17. 一棵二叉樹的前序遍歷序列是 ABCDEFG 后序遍歷序列是 CBFEGDA 那么根結(jié)點(diǎn) 的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是 。A.2B.3C.4D.518. 關(guān)于拓?fù)渑判?，下面說法正確的選項(xiàng)是 。A. 所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判?。B. 對(duì)同一個(gè)圖而言，拓?fù)渑判虻慕Y(jié)果是唯一的。C. 拓?fù)渑判蛑腥攵葹?0的結(jié)點(diǎn)總會(huì)排在入度大于 0 的結(jié)點(diǎn)的前面。D. 拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度為 0 的點(diǎn)。19. 完全二叉樹的順序存儲(chǔ)方案，是指將完全二叉樹的結(jié)點(diǎn)從上至下 從左至

7、右依次 存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中，假定根結(jié)點(diǎn)存放在數(shù)組的 1 號(hào)位置，那么第 K 號(hào)結(jié)點(diǎn) 的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組的 號(hào)位置。A.2k取整B.2k+1C.k/2 下取整D.(k+1)/2 下20. 主辦單位是全國青少年信息學(xué)奧林匹克系列活動(dòng)的D.中國計(jì)算機(jī)學(xué)會(huì)A.教育部B.科技部C.共青團(tuán)中央問題求解共 2題，每空 5分，共 10分1. LZW 編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時(shí)只有一部基 礎(chǔ)構(gòu) 造元素的編碼詞典，如果在編碼的過程中遇到一個(gè)新的詞條， 那么該詞條及一 個(gè)新的 編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個(gè)待編碼的信息串：“ xyx y

8、y yy xyx 。初始詞典只有3個(gè)條目，第一個(gè)為x,編碼為1:第二個(gè)為y,編碼為2:第三個(gè)為空格，編碼 為3: 于是串“ xyx的編碼為1-2-1 其中-為編碼分隔符，加上后面的一個(gè)空格就是1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的“xyx是一個(gè)單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個(gè)詞條添加到詞典里， 編碼為 4,然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類推。于是，最后得到 編 碼：1-2-1-3-2-2-3-5-3-4°yyxy xx yyxy xyx xx xyx 的現(xiàn)在初始詞典的 3個(gè)條目如上述，那么信息串編碼是：2.隊(duì)列快照是指在某一時(shí)刻隊(duì)列中的

9、元素組成的有序序列。例如，當(dāng)元素 1、2、3入隊(duì)，元素 1出隊(duì)后，此刻的隊(duì)列快照是“ 2 3 。當(dāng)元素 2、3 也出隊(duì)后，隊(duì) 列快照是“，即為空?，F(xiàn)有 3個(gè)正整數(shù)元素依次入隊(duì)、出隊(duì)。它們的和 為 8, 那么共有種可能的不同的隊(duì)列快照不同的隊(duì)列的相同快照只計(jì)一次。例如，“ 5 1 、“ 4 2 2 、“都是可能的隊(duì)列快照；而“ 7不 是可能的隊(duì)列快照，因?yàn)槭Ｏ碌?2 個(gè)正整數(shù)的和不可能是 1°三.閱讀程序?qū)懡Y(jié)果共 4題，每題 8分，其中第 4 題1、 2各 4 分, 共計(jì)32分Var al,a2,a3,x:i nteger; procedure swap (var a,b:intege

10、r);Var t:i nteger;beginvart:i nteger;begint:=a;a:=b;b:= t;end;beginread ln( al,a2,a3);if al >a2 the n swap(a 1,a2);if a2>a3 then swap (a2,a3);if al>a2 the n swap(a1,a2);readl nl(x);if x<a2 the nif x<al the nwritel n(x,a1, ' ,a2,'e1se，a3)writel n (a1.>；elseif x<a3 the n，a

11、2,'，a3)writel n(al.',a2,',x,'，a3)elsewritel n(al.a2,佔(zhàn).xend.輸入：91 2 2077輸出：2.Varn, m,i:i n teger;fun cti on rsum(j:i n teger):i n teger; varsum:i n teger;beg insum:=0;while j <> 0 dobeg in sum:=sum * 10 +(j mod 10); j:=j div 10; end;rsum:=sum;end;beg inreadl n( n, m);for i:=n to

12、 m doif i=rsum(i)the n write(l, ');end.輸入:90 120輸出：3.VarS:stri ng;i:i nteger; m1,m2:char;beg inreadl n(s);n1:=m2:='for i:=1 to len gth(s) do if si > ml the n beg inm2:=m1; m1:=si;endelse if si > m2 the nm2:=si;write In (ord(m1), ord(m2);end.輸入:Expo 2021 Sha nchai Chi na輸出:提示:字符空格 O'

13、; AaASCII 碼324865974con stNUM=5;Varn:i nteger;function r(n:integer:intecer;Vari:i n teger;beg inif n< = NUM the nbeg inr:=n;exit;end;for i:=1 to NUM d0if r(n-i) < 0 thenbegi nr:=i;exit;end;begi nreadl n(n);write In (r( n);end.(1)輸入：7輸出： (4 分)輸入:16輸出：(4 分)四?完善程序 (前 4 空，每空 2.5 分，后 6 空，每空 3 分，共 2

14、8 分)1.(哥德巴赫猜測(cè) )哥德巴赫猜測(cè)是指，任一大于 2 的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)之 和，迄 今為止，這仍然是一個(gè)著名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。試編 寫程序，驗(yàn) 證任一大于 2 且不超過 n 的偶數(shù)都能寫成兩個(gè)質(zhì)數(shù)之和。constsize=1000;varn ,r,i,j,k,a ns:i nteger;p:array 1.size of in teger;tmp:boolea n;beg inreadl n(n);r:=1;P1：=2；for i:=3 to n dobegi n；for j:=1 to r doif I mod=0 thenbegi ntmp:=false;br

15、eak;end;if tmp the nbeg inin c(r);；end;end;an s:=0;for i:=2 to (n div 2) dobeg intmp:=false;for j:=1 to r doif i+i= the nbegi ntmp:=true;break;end;if tmp the nin c(a n s);end;write ln (a n s);end.假設(shè)輸入n為2021,那么輸出 時(shí)表示驗(yàn)證成功，即大于2且不超過2021的偶數(shù)都滿足哥德巴赫猜測(cè)。2.過河問題在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過唯一的一 根獨(dú)木 橋走到河的左岸。在這伸手不見五指

16、的黑夜里，過橋時(shí)必須借助燈光來照明，不幸的 是，他們只有一盞燈。另外，獨(dú)木橋上最多承受兩個(gè)人同時(shí)經(jīng)過，否 那么將會(huì)坍塌。每 個(gè)人單獨(dú)過橋都需要一定的時(shí)間，不同的人需要的時(shí)間可能不同。 兩個(gè)人一起過橋 時(shí)，由于只有一盞燈，所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過橋 時(shí)所花的時(shí)間?，F(xiàn)輸 入 n(2<=n<100) 和這 n 個(gè)人單獨(dú)過橋時(shí)需要的時(shí)間，請(qǐng)計(jì)算 總共最少需要多少時(shí)間， 他們才能全部到達(dá)河的左岸。例如，有 3 個(gè)人甲、乙、丙，他們單獨(dú)過橋的時(shí)間分別為 1、2、 4, 那么總共 最少 需要的時(shí)間為 7。具體方法是：甲、乙一起過橋到河的左岸，甲單獨(dú)回到河的右岸將燈帶回，然后甲、丙再一起

17、過橋到河的左岸，總時(shí)間為2+1+4 = 7。constsize=100;infin ity=10000;left=true;right=false;left_to_right=true;right_to_left=false;varn ,i:i nteger;time:array 1.size of integer; pos:array 1.size of boolean; functionmax(a,b:integer):integer; beginif a>b thenmax:=aelsemax:=b;end;function go(stage:boolean):integer; v

18、arI,j,num,tmp,ans:integer; beginif (stage=right_to_lefft) thenbeginnum:=0;ans:=0;for i:=1 to n doif posi=right thenbegininc(num);if timei>ans then ans:=timei;end;if thenbegi ngo:=a ns;exit;end;ans:=infin ity;for i:=1 to n-1 doif posi=right the nfor j:=i+1 to n doif posj=right the nbegi nposi:=lef

19、t;posj:=left;tmp:=max(timei,timej)+if tmpva ns the n an s:=tmp;posi:=right;posj:=right;end;go:=a ns;elseif (stage=left_to_right) the nbegi n ans:=infin ity;for i:=1 to n dothe nif begi nposi:=right;tmp:=if tmpva ns the nan s:=tmp;end; go:=a ns; end else go:=0;end;beg inreadl n(n);for i:=1 to n dobegi nread(timei); posi:=right;end; writeln(go(right_to_left); end.NOIP2021 普及組 (Pascal 語言)參考答案與評(píng)分標(biāo)準(zhǔn)一 ,單項(xiàng)選擇題 (共 20 題 ,