NOIP 2009普及組初賽C/C++答案詳解
一、單項選擇題
1 D
第一臺電子計算機是在第二次世界大戰後不久製成的，那時，隨著火炮的發展，彈道計算日益複雜，原有的一些計算機已不能滿足使用要求，迫切需要有一種新的快速的計算工具。這樣，在一些科學家、工程師的努力下，在當時電子技術已顯示出具有記數、計算、傳輸、儲存控制等功能的基礎上，電子計算機就應運而生了。世界上第一臺電子計算機命名為"埃尼阿克"，是1946年美國賓夕法尼亞大學埃克特等人研製成功的。
2 B
RAM不是位置隨機，而是隨時訪問。所謂“隨機儲存”，指的是“當儲存器中的訊息被讀取或寫入時，所需要的時間與這段資訊所在的位置無關”。A錯。
高速緩衝區是CPU自帶的,CPU的一二三級快取就是快取記憶體。與快取記憶體相比,記憶體條只是下一級的低速快取。暫存器是CPU的一部分。C錯。
記憶體中的資料，斷電會立馬消失。D錯。
3 A
BIOS是英文"Basic Input Output System"的縮略詞，直譯過來後中文名稱就是"基本輸入輸出系統"。在IBM PC相容系統上，是一種業界標準的韌體介面。 BIOS是個人電腦啟動時載入的第一個軟體，它是一組固化到計算機內主機板上一個ROM晶片上的程式，它儲存著計算機最重要的基本輸入輸出的程式、開機後自檢程式和系統自啟動程式。 其主要功能是為計算機提供最底層的、最直接的硬體設定和控制。
BIOS是由主機板廠商開發的，不是由作業系統廠商（如微軟）開發的。
4 A
組合語言只有人能看的懂，CPU是看不懂的，需要用軟體將彙編轉換成機器語言，CPU才能執行程式。B錯。
位數只能說明處理的字長，所在的系統硬體指令不同，速度很難說誰快。C錯。
Intel最早發明的是微處理器，而CPU之前就由電子管、電晶體實現著呢。D錯。
5 B
ASCII（American Standard Code for Information Interchange，美國資訊交換標準程式碼）是基於拉丁字母的一套電腦編碼系統，主要用於顯示現代英語和其他西歐語言。它是現今最通用的單位元組編碼系。
6 D
WPS是類似微軟Office的國產文書處理軟體，由金山公司出品。
7 C
IPv6是Internet Protocol Version 6的縮寫，其中Internet Protocol譯為“網際網路協議”。IPv6是IETF（網際網路工程任務組，Internet Engineering Task Force）設計的用於替代現行版本IP協議（IPv4）的下一代IP協議，號稱可以為全世界的每一粒沙子編上一個網址。A錯。
域名都需要繫結在IP上，域名比IP更好記，比如 ofollow,noindex">www.baidu.com 為域名，IP都是數字。B錯。
考慮版權。D錯。
8 B
HTML全稱HyperText Markup Language，即超文字標記語言，關於HTML是不是一門程式語言，業界仍有不小的爭議。有人認為，HTML和其他標記語言（比如XML）一樣具備了語言特徵，可以被應用程式（比如瀏覽器）解釋，但不具備高階程式設計語言的特徵。另外Flash動畫一般由Adobe公司的Flash軟體開發，Flash遊戲由ActionScript語言開發。
9 C
釋在程式程式碼中不會被執行，也不會被編譯，因此註釋不會影響程式的執行速度。A錯。
只要硬體系統具備執行環境，高階語言開發的程式能夠在這些硬體系統上執行。比如C++，Java作為高階語言，已經廣泛用於手機，機頂盒，印表機。B錯。
高階語言在編寫程式時不用考慮最後程式會執行在那類作業系統上，因為很容易跨平臺移植。C對。
10 D
正確答案是74。
11 C
1758 = 1 * 8 2 + 7 * 8 + 5 = 125
0.18 = 1/8 = 0.125
所以，175.18 = 125.125
12 C
A選項：F進棧 -- E進棧 -- E出棧 -- D進棧 -- D出棧 -- C進棧 -- C出棧 -- F出棧 -- B進棧-- A進棧 -- A出棧 -- B出棧
B選項：F進棧 -- E進棧 -- D進棧 -- D出棧 -- E出棧 -- C進棧 -- C出棧 -- B進棧 -- A進棧 -- A出棧 -- B出棧 -- F出棧
C選項：F進棧 -- E進棧 -- D進棧 -- C進棧 -- C出棧 -- D出棧 -- ??，這裡E一定會比F早出棧，所以本選項錯誤。
D選項：F進棧 -- E進棧 -- D進棧 -- C進棧 -- B進棧 -- B出棧 -- C出棧 -- D出棧 -- A進棧 -- A出棧 -- E出棧 -- F出棧
13 B
中綴表示式轉換為字尾表示式的過程需要用到棧，具體過程如下：
1）如果遇到運算元，我們就直接將其輸出。
2）如果遇到操作符，則我們將其放入到棧中，遇到左括號時我們也將其放入棧中。
3）如果遇到一個右括號，則將棧元素彈出，將彈出的操作符輸出直到遇到左括號，左括號也彈出但不輸出。
4）如果遇到任何其他的操作符，如“+”， “*”，“（”等，從棧中彈出元素直到遇到發現棧中更低優先順序的元素或者棧為空為止。彈出完這些元素後，才將遇到的操作符壓入到棧中。
有一點需要注意，只有在遇到" ) "的情況下我們才彈出" ( "，其他情況我們都不會彈出" ( "。
5）如果我們讀到了輸入的末尾，則將棧中所有元素依次彈出。
對於本題的例子：
1）第一個是運算元“a”，直接輸出
入棧，左括號入棧，輸出“b”，“+”入棧，輸出“c”。如圖1所示
3）碰到右括號，將“+”彈出棧並輸出，接著將左括號彈出但不輸出，“
”不彈出仍在棧裡，如圖2所示
1-13.png
4）碰到“-”，因為棧裡“ ”的優先順序比“-”要高，所以“ ”出棧並輸出，“-”入棧，如圖3所示
5）碰到最後一個字元“d”，直接輸出，並把棧中的元素“-”彈出並輸出。如圖4所示
14 D
二叉樹的結點有兩種：葉子節點和非葉結點（也叫分支結點）。當二叉樹為完美二叉樹時，葉子結點最多。
以下圖為例，分支結點（非葉結點）有7個，葉子結點有8個。所以是n+1。
1-14.png
15 D
在最壞的情況下，待排序的序列為正序或者逆序，每次劃分只得到一個比上一次劃分少一個記錄的子序列，注意另一個為空。如果遞迴樹畫出來，它就是一棵斜樹。此時需要執行n‐1次遞迴呼叫，且第i次劃分需要經過n‐i次關鍵字的比較才能找到第i個記錄，也就是樞軸的位置，因此比較次數為
1-15.jpg
最終其時間複雜度為O(n2)。
16 B
log4000 < log4096 = 12
17 D
快速排序的具體做法：設定需要排序序列第一個數字為關鍵字P（也叫樞軸），同時設定兩個指標high和low，初始狀態時，low指向P，high指向序列中最後一個數；
首先從high所指位置起向前找第一個小於關鍵字P的數字，並與P相互交換位置；然後從low所指位置起向後搜尋，找到第一個大於P的數字，並與P相互交換位置，重複這兩部直至low=high為止，這就是一趟快速排序完成；但是到此不一定就完成了快速排序的排序工作，第一趟排序完成只是將序列中的數字分成三部分，P在中間部分，P之前的數字肯定比P小，P後面的那些數字都是比P大的，在分別對前後兩部分進行快速排序即可。
排序的穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的。
比如：對{49，38，49，20，97，76} 進行快速排序，第一輪比較是20和第一個49互換位置，導致第一個49跑到第二個49後面，所以這是不穩定的排序。
18 A
Line"/>
1-18.png
有向圖至少需要n條有向邊，無向圖至少需要n - 1條無向邊。
19 C
20 B
賽場紀律 http://www.noi.cn/newsview.html?id=68&hash=CDD941&type=6
選手可以攜帶書寫工具，如鋼筆、鉛筆等，以及手錶和適量的衣物等進入賽場。有特殊情況需要攜帶其它物品者需事先取得競賽委員會的批准。
選手不可以攜帶上述規定之外的其它物品，如紙張、書籍、食品、飲料等進入賽場。選手被嚴格禁止攜帶軟盤、光碟、U盤等儲存裝置和介質，以及手機、電子辭典、PDA等電子及通訊裝置。凡攜帶上述被嚴格禁止的裝置進入競賽場地者，在競賽開始後一經發現，無論是否使用，均以作弊論處，取消其該場競賽的資格和成績。
選手在競賽中不得與其他選手交談，不得干擾他人的競賽活動，不得損壞競賽裝置。
選手在競賽過程中如需入廁，需舉手向賽場服務人員示意並徵得允許。
二、問題求解
1 答案：70
分析：
b1, a1, a2, a3的相對位置是固定的。尤其是b1，一定是放在第一個位置。
2-1.png
這裡的問號，可以填b2,b3,b4,b5中的一個或多個，也可以為空。
（一）列舉法
列舉法過於複雜，不能使用列舉法，否則容易出錯。
（二）求組合
B任務中的b1一定做，而且肯定是第一個做的。所以b1就不用考慮了。
第一類：完成A任務，只有1種。即a1 a2 a3
第二類：完成A任務和b2，有C(4,1)=4種：
① b2 a1 a2 a3
② a1 b2 a2 a3
③ a1 a2 b2 a3
④ a1 a2 a3 b1
第三類：完成A任務和b2、b3，有C(5,2)=10種。這裡C(5, 2)表示從五個位置中挑選出2個且順序已經定好：第一個位置放b2，第二個位置放b3。其他三個位置不用選，肯定按從左到右的順序放a1，a2和a3。
第四類：完成A任務和b2、b3、b4，有C(6,3)=20種。
第五類：完成A任務和b2、b3、b4、b，有C(7,4)=35種。
加起來1+4+10+20+35=70。
