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

1、第十六屆全國青少年信息學奧林匹克聯賽初賽試題普及組 Pascal 語言 兩小時完成? 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ?一. 單項選擇題共 20 題，每題 1.5 分，共計 30 分。每題有且僅有一個正確 答 案。1.2E 03 表示 。C.8 D.2000A. 2.03 B.52. 一個字節(jié) byte 由 個二進制位組成。A. 8 B.16 C.32 D. 以上都有可 能3. 以下邏輯表達式的值恒為真的是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í)行文件的默認擴展名為 A.exeB C.dllD.以是都不是A. 如果樹根算是第1層，那么一棵n層的二叉釁多有結點26.提出“存儲程序 的計算機工作原理的是 。A.克勞德？香農B.戈登？摩爾C.查爾斯？巴比奇D.馮？諾依曼7.設X、丫、Z 分別代表三進制下的一位數字， 假設等式 XY+ ZX= XYX 在三進制下成 立，那么同 樣在三進制下，等式 XYX ZX=也成立。A.YXZB.ZXYC.XYZD.XZY9. 前綴表達式“ + 3X 2+ 5 12 的值是 。A.23B.25C.37D.6510. 主存儲器的存取速度比中央處理器 CPU 的工作速度慢得多，從而使得后者 的效率受到影響。

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

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

5、 雙向鏈表中有兩個指針域 llink 的 rlink ，分別指向該結點的前驅及后繼。設p指向鏈表中的一個結點，它的左右結點均非空?，F要求刪除結點P,那么下面語句序列中錯誤的選項是 。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 那么根結點 的左子樹的結點個數可能是 。A.2B.3C.4D.518. 關于拓撲排序，下面說法正確的選項是 。A. 所有連通的有向圖都可以實現拓撲排序。B. 對同一個圖而言，拓撲排序的結果是唯一的。C. 拓撲排序中入度為 0的結點總會排在入度大于 0 的結點的前面。D. 拓撲排序結果序列中的第一個結點一定是入度為 0 的點。19. 完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上至下 從左至

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

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

9、元素組成的有序序列。例如，當元素 1、2、3入隊，元素 1出隊后，此刻的隊列快照是“ 2 3 。當元素 2、3 也出隊后，隊 列快照是“，即為空?，F有 3個正整數元素依次入隊、出隊。它們的和 為 8, 那么共有種可能的不同的隊列快照不同的隊列的相同快照只計一次。例如，“ 5 1 、“ 4 2 2 、“都是可能的隊列快照；而“ 7不 是可能的隊列快照，因為剩下的 2 個正整數的和不可能是 1°三.閱讀程序寫結果共 4題，每題 8分，其中第 4 題1、 2各 4 分, 共計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,佔.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.(哥德巴赫猜測 )哥德巴赫猜測是指，任一大于 2 的偶數都可寫成兩個質數之 和，迄 今為止，這仍然是一個著名的世界難題，被譽為數學王冠上的明珠。試編 寫程序，驗 證任一大于 2 且不超過 n 的偶數都能寫成兩個質數之和。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.假設輸入n為2021,那么輸出 時表示驗證成功，即大于2且不超過2021的偶數都滿足哥德巴赫猜測。2.過河問題在一個月黑風高的夜晚，有一群人在河的右岸，想通過唯一的一 根獨木 橋走到河的左岸。在這伸手不見五指

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

17、過橋到河的左岸，總時間為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 語言)參考答案與評分標準一 ,單項選擇題 (共 20 題 ,