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

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

2、Q(PQ) (PQ)C. PQ(PQ) (PQ)D.PQ(PQ) (PQ)4.Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名為（ ）。A.exeB.comC.dllD.以是都不是5.如果樹(shù)根算是第1層，那么一棵n層的二叉樹(shù)最多有（ ）結(jié)點(diǎn)。A.2n-1B.2nC.2n+1D.2n+16.提出“存儲(chǔ)程序”的計(jì)算機(jī)工作原理的是（ ）。A.克勞德·香農(nóng)B.戈登·摩爾C.查爾斯·巴比奇D.馮·諾依曼7.設(shè)X、Y、Z分別代表三進(jìn)制下的一位數(shù)字，若等式XYZXXYX在三進(jìn)制下成立，那么同樣在三進(jìn)制下，等式XY×ZX（ ）也成立。A.YXZB.ZXYC.XYZD.XZY

3、9.前綴表達(dá)式“3×25 12”的值是（ ）。A.23B.25C.37D.6510.主存儲(chǔ)器的存取速度比中央處理器（CPU）的工作速度慢得多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問(wèn)的存儲(chǔ)單元通常都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了（ ）。A.寄存器B.高速緩存C.閃存D.外存11.一個(gè)字長(zhǎng)為8位的整數(shù)的補(bǔ)碼是11111001,則它的原碼是（ ）。A.00000111B.01111001C.11111001D.1000011112.基于比較的排序時(shí)間復(fù)雜度的下限是（ ），其中n表示待排序的元素個(gè)數(shù)。A.O(n)B.O(

4、n log n)C.O(log n)d.O(n2)13.一個(gè)自然數(shù)在十進(jìn)制下有n位，則它在二進(jìn)制下的位數(shù)與（ ）最接近。A.5nB.n*log210C.10*log2nD.10nlog2n14.在下列HTML語(yǔ)句中，可以正確產(chǎn)生一個(gè)指向NOI官方網(wǎng)站的超鏈接的是（ ）。A.<a url=”>歡迎訪問(wèn)NOI網(wǎng)站<a>B. <a href=”>歡迎訪問(wèn)NOI網(wǎng)站<a>C. <a> <a>D. <a name=”>歡迎訪問(wèn)NOI網(wǎng)站<a>15.元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、

5、R4、R5。如果第1個(gè)出棧的是R3,那么第5個(gè)出棧的不可能是（ ）。A.R1B.R2C.R4D.R516.雙向鏈表中有兩個(gè)指針域llink的rlink，分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均非空?，F(xiàn)要求刪除結(jié)點(diǎn)P,則下面語(yǔ)句序列中錯(cuò)誤的是（ ）。A.p.rlink.llink=p.rlink; p.llink.rlink=p.llink;dispose(p);B.p.llink.rlink=p.rlink; p.rlink.llink=p.llink;dispose(p);C.p.rlink.llink=p.llink; p.rlink.llink.rlink=p

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

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

8、 yy xyx”。初始詞典只有3個(gè)條目，第一個(gè)為x，編碼為1:第二個(gè)為y，編碼為2：第三個(gè)為空格，編碼為3：于是串“xyx”的編碼為1-2-1（其中-為編碼分隔符），加上后面的一個(gè)空格就是1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的“xyx”是一個(gè)單詞，而由于該單詞沒(méi)有在詞典中，我們就可以自適應(yīng)的把這個(gè)詞條添加到詞典里，編碼為4,然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類(lèi)推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。現(xiàn)在已知初始詞典的3個(gè)條目如上述，則信息串“yyxy xx yyxy xyx xx xyx”的編碼是:  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)槭Ｏ碌?個(gè)正整數(shù)的和不可能是1。三. 閱讀程序?qū)懡Y(jié)果（共4題，每題8分，其中第4題（1）、（2）各4分，共計(jì)32分）1Varal,a2,a3,x:integer;procedure swap (var a,b:integer);Vart:integer;be

10、ginvart:integer;begint:=a;a:=b;b:=t;end;beginreadln(al,a2,a3);if al >a2 then swap(a 1,a2);if a2>a3 thenswap (a2,a3);if al>a2 thenswap(a1,a2); readlnl(x); if x<a2 then if x<al then writeln(x, ,a1, ,a2, ,a3) e1se writeln(a1, ,x, ,a2, ,a3) else if x<a3 then writeln(al, ,a2, ,x, ,a3) e

11、lse writeln(al, , a2, , a3, .x);end. 輸入:91 2 2077輸出：  2.Varn,m,i:integer;function rsum(j:integer):integer;varsum:integer;beginsum:=0;while j <> 0 do beginsum:=sum * 10 +(j mod 10);j:=j div 10;end;rsum:=sum;end;begin readln(n,m);for i:=n to m doif i=rsum(i)then write(I, );end. 輸入

12、:90 120輸出:  3.VarS:string;i:integer;m1,m2:char;begin readln(s);n1:= ;m2:= ;for i:=1 to length(s) doif si > m1 then beginm2:=m1;m1:=si;endelse if si > m2 then m2:=si;writeln(ord(m1), , ord(m2);end. 輸入:Expo 2010 Shanchai China輸出: 提示:字符空格0AaASCII碼32486597 4constNUM=5;Varn:integer;f

13、unction r(n:integer:intecer;Var i:integer;begin if n< = NUM then begin r:=n; exit; end; for i:=1 to NUM d0 if r(n-i) < 0 then begin r:=i; exit; end; begin readln(n);writeln(r(n);end. (1)輸入: 7輸出: (4分) (2)輸入: 16輸出: （4分） 四. 完善程序（前4空，每空2.5分，后6空，每空3分，共28分）1.（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫(xiě)成兩個(gè)質(zhì)數(shù)之和，

14、迄今為止，這仍然是一個(gè)著名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。試編寫(xiě)程序，驗(yàn)證任一大于2且不超過(guò)n的偶數(shù)都能寫(xiě)成兩個(gè)質(zhì)數(shù)之和。const size=1000;var n,r,i,j,k,ans:integer; p:array 1.size of integer; tmp:boolean;begin readln(n); r:=1; p1:=2; for i:=3 to n do begin ; for j:=1 to r do if I mod =0 then begin tmp:=false; break; end; if tmp then begin inc(r); ; end; end

15、; ans:=0; for i:=2 to (n div 2) do begin tmp:=false; for j:=1 to r do if i+i= then begin tmp:=true; break; end; if tmp then inc(ans); end; writeln(ans);end.若輸入n為2020，則輸出 時(shí)表示驗(yàn)證成功，即大于2且不超過(guò)2010的偶數(shù)都滿(mǎn)足哥德巴赫猜想。2.（過(guò)河問(wèn)題）在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過(guò)唯一的一根獨(dú)木橋走到河的左岸。在這伸手不見(jiàn)五指的黑夜里，過(guò)橋時(shí)必須借助燈光來(lái)照明，不幸的是，他們只有一盞燈。另外，獨(dú)木橋上最多承受

16、兩個(gè)人同時(shí)經(jīng)過(guò)，否則將會(huì)坍塌。每個(gè)人單獨(dú)過(guò)橋都需要一定的時(shí)間，不同的人需要的時(shí)間可能不同。兩個(gè)人一起過(guò)橋時(shí)，由于只有一盞燈，所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過(guò)橋時(shí)所花的時(shí)間?，F(xiàn)輸入n(2<=n<100)和這n個(gè)人單獨(dú)過(guò)橋時(shí)需要的時(shí)間，請(qǐng)計(jì)算總共最少需要多少時(shí)間，他們才能全部到達(dá)河的左岸。例如，有3個(gè)人甲、乙、丙，他們單獨(dú)過(guò)橋的時(shí)間分別為1、2、4，則總共最少需要的時(shí)間為7。具體方法是：甲、乙一起過(guò)橋到河的左岸，甲單獨(dú)回到河的右岸將燈帶回，然后甲、丙再一起過(guò)橋到河的左岸，總時(shí)間為2+1+47。const size=100; infinity=10000; left=true; rig

17、ht=false; left_to_right=true; right_to_left=false;var n,i:integer; time:array 1.size of integer; pos:array 1.size of boolean;function max(a,b:integer):integer;begin if a>b thenmax:=a elsemax:=b;end;function go(stage:boolean):integer;var I,j,num,tmp,ans:integer;begin if (stage=right_to_lefft) then

18、begin num:=0; ans:=0; for i:=1 to n do if posi=right then begin inc(num); if timei>ans then ans:=timei; end; if then begin go:=ans; exit; end; ans:=infinity; for i:=1 to n-1 do if posi=right then for j:=i+1 to n do if posj=right then begin posi:=left; posj:=left; tmp:=max(timei,timej)+ ; if tmp&l

19、t;ans then ans:=tmp; posi:=right; posj:=right; end; go:=ans; else if (stage=left_to_right) then begin ans:=infinity; for i:=1 to n do if then begin posi:=right; tmp:= ; if tmp<ans then ans:=tmp; ; end; go:=ans;endelse go:=0; end;begin readln(n); for i:=1 to n dobegin read(timei); posi:=right;end; writeln(go(right_to_left);end.      NOIP2010普及組(Pa