NOIP 2010普及組初賽C/C++答案詳解
一、單項選擇題
1 D
2E + 03 = 2 * 10 3 = 2000
2E - 03 = 2 * 1 / (2 * 10 3 ) = 2 * 0.001 = 0.002
2 A
常識題
3 A
對於A選項，假設P為真，則結果必為真；假設P為假，則!p為真 ==> (!P & Q)和(!P & !Q)中必有一個為真 ==> P | (!P & Q) | (!P & !Q)為真。
對於B選項，當P和Q同時為假時，Q | (!P & Q) | (P & !Q)為假。
對於C選項，當P和Q同時為假時，整個表示式為假。
對於D選項，當P為真Q為假時，整個表示式為假。
4 D
exe是Windows下的可執行檔案。exe是executable（可執行的）的縮寫
COM是Component Object Model （元件物件模型）的縮寫。COM是微軟公司為了計算機工業的軟體生產更加符合人類的行為方式開發的一種新的軟體開發技術。在COM構架下，人們可以開發出各種各樣的功能專一的元件，然後將它們按照需要組合起來，構成複雜的應用系統。
注意，這裡的com不是域名（比如 ofollow,noindex">www.google.com ）中的com。若是有學生誤以為是域名中的com而將B選項排除，只能說是碰巧排除對了。
DLL是Dynamic Link Library的縮寫，意為動態連結庫。在Windows中，許多應用程式並不是一個完整的可執行檔案，它們被分割成一些相對獨立的動態連結庫，即DLL檔案，放置於系統中。當我們執行某一個程式時，相應的DLL檔案就會被呼叫。一個應用程式可有多個DLL檔案，一個DLL檔案也可能被幾個應用程式所共用。
所以A, B, C選項都是Windows系統的檔案，並且dll檔案不能被獨立執行。
那麼Linux下的可執行檔案字尾名是什麼呢？答案是Linux/Unix/Mac系統下的程式的字尾名不重要，Linux/Unix/Mac系統下的檔案功能不是以後綴名來劃分的。這是Linux/Unix/Mac與Windows的一大重要差別。
5 A
1層最多有2 1 - 1 = 1個結點。
2層最多有2 2 - 1 = 3個結點。
3層最多有2 3 - 1 = 7個結點。
6 D
識記題。
美籍匈牙利數學家馮·諾依曼於1946年提出儲存程式原理，把程式本身當作資料來對待，程式和該程式處理的資料用同樣的方式儲存。 馮·諾依曼體系結構馮·諾依曼理論的要點是：計算機的數制採用二進位制；計算機應該按照程式順序執行。人們把馮·諾依曼的這個理論稱為馮·諾依曼體系結構。
7 B
最低位，Y + X = X，則Y必為0
最高位，X + Z = XY，則Z = 2, X = 1
XY * ZX = 10 * 21 = 210 = ZXY
8 D
PASCAL與C面向過程，C++面向物件。
指令碼語言又被稱為擴建的語言，或者動態語言，是一種程式語言，用來控制軟體應用程式，指令碼通常以文字（如ASCII)儲存，只在被呼叫時進行解釋或編譯。指令碼語言有Shell, JavaScript, Perl, Python, PHP, Ruby等。
解釋型語言相對於編譯型語言存在的，原始碼不是直接翻譯成機器語言，而是先翻譯成中間程式碼，再由直譯器對中間程式碼進行解釋執行。比如Python/JavaScript / Perl /Shell等都是解釋型語言。
9 C
字首表示式的計算機求值：
從右至左掃描表示式，遇到數字時，將數字壓入堆疊，遇到運算子時，彈出棧頂的兩個數，用運算子對它們做相應的計算（棧頂元素 op 次頂元素），並將結果入棧；重複上述過程直到表示式最左端，最後運算得出的值即為表示式的結果。
本題中，先將12和5先後入棧；碰到+，將5和12依次彈出，計算5 + 12 = 17，將17入棧；將2入棧；碰到*，將2和17依次彈出棧，計算2 * 17 = 34，將34入棧；將3入棧；碰到+，將3和34依次彈出棧，計算3 + 34 = 37。
10 B
CPU快取記憶體（Cache Memory）是位於CPU與記憶體之間的臨時儲存器，它的容量比記憶體小的多但是交換速度卻比記憶體要快得多。快取記憶體的出現主要是為了解決CPU運算速度與記憶體讀寫速度不匹配的矛盾，因為CPU運算速度要比記憶體讀寫速度快很多，這樣會使CPU花費很長時間等待資料到來或把資料寫入記憶體。在快取中的資料是記憶體中的一小部分，但這一小部分是短時間內CPU即將訪問的，當CPU呼叫大量資料時，就可先快取中呼叫，從而加快讀取速度。
11 D
正數的原碼、反碼、補碼都一樣。
負數的補碼為原碼取反加1，原碼為補碼減1取反（注意最高位的1是符號位，不用取反）。
12 B
對於n個待排序元素，在未比較時，可能的正確結果有n!種。
在經過一次比較後，其中兩個元素的順序被確定，所以可能的正確結果剩餘n!/2種（確定之前兩個元素的前後位置的情況是相同，確定之後相當於少了一半的可能性）。
次類推，直到經過m次比較，剩餘可能性n!/(2^m)種。
直到n!/(2^m)<=1時，結果只剩餘一種。
由n!/(2^m) <= 1
得m >= log 2 (n!)
= log 2 (n * (n - 1) * (n - 2) * ... * 2 * 1)
= log 2 n + log 2 (n - 1) + log 2 (n - 2) + ... + log 2 2 + log 2 1
>= log 2 n + log 2 (n - 1) + log 2 (n - 2) + ... + log 2 (n/2)
>= log 2 (n/2) + log 2 (n/2) + log 2 (n/2) + ... + log 2 (n/2)
>= n/2*log 2 (n/2)
所以基於比較的排序的時間複雜度下界是O(nlog 2 n)
13 B
這題可以舉個特例n = 3。三位數的最小值為100，最大值為999。
100 = 1100100，這是七位二進位制。
999 < 1024 = 210 = 10000000000(B), 1024是十一位二進位制，則999是十位二進位制。
再看四個答案，5n = 15, n log(10) = 8.x, 10 log(n) > 10, 10nlog(n) > 1000。所以選B。
14 B
href是Hypertext Reference的縮寫。意思是指定超連結目標的URL。
15 B
R1在R2的下方，所以R2不可能是最後一個出棧的。
16 A
1-16.png
A選項中，p->rlink->llink = p->rlink;表示RightNode的左指標指向了RightNode本身，錯誤。
17 A
畫出圖即可知道答案。
1-17.png
18 D
拓補排序的思路：
在有向圖中選一個沒有前驅的頂點並且輸出；
從圖中刪除該頂點和所有以它為尾的弧（白話就是：刪除所有和它有關的邊）
重複上述兩步，直至所有頂點輸出，或者當前圖中不存在無前驅的頂點為止，後者代表我們的有向圖是有環的，因此，也可以通過拓撲排序來判斷一個圖是否有環。
有環圖不能進行拓補排序，A錯；拓補排序可能有好幾個結果，B錯；只要求第一個結點一定是入度為0的結點，C錯。
19 C
舉個特例。比如k = 3時，3號結點的父結點是1號結點（也就是根結點）。
1 = ⌊k/2⌋ = ⌊3/2⌋ 。
20 D
NOIP又叫CCF NOIP，CCF即為NOIP的主辦單位。CCF, China Computer Federation，中國計算機學會。
二、問題求解
1 答案：2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6
分析：
x為1，y為2，空格為3；第一次碰到yyxy後加入到詞典裡，編號為4；第一次碰到xx後加入到詞典裡，編號為5；第一次碰到xyx後加入到詞典裡，編號為6。
