NOIP 2015 普及組 初賽
疑難點 學習 感悟。
本份試卷本人得分93，兩處錯誤，一錯在二、1.題，眼花了，多數了個資料3241；二錯在四、2.題(5)空，該空寫成rbound=mid-1，這個錯誤在考試中是改正不了的，這是由本人解題方法決定的。也就是說該份試卷本人的極限是98。
一、
1.
C.1000*1000位元組 是硬體商，軟體商的做法。
D.1024*1024位元組 來自教科書，也就是來源于計算機的二進制表達。
權衡之下選D
7.
示例如下（來自自個的了解）：
101.101 十進制 轉十進制1*10^2+0*10^1+1*10^0+1*10^-1+0*10^-2+1*10^-3
101.101 二進制 轉十進制1*2^2+0*2^1+1*2^0+1*2^-1+0*2^-2+1*2^-3
101.101 八進制 轉十進制1*8^2+0*8^1+1*8^0+1*8^-1+0*8^-2+1*8^-3
101.101 十六進制 轉十進制1*16^2+0*16^1+1*16^0+1*16^-1+0*16^-2+1*16^-3
以十進制為中介
0.1=1*2^-1=0.5
x*16^-1=0.5 => x=8
故答案為A
12.
n個頂點的樹，邊數為n-1
故答案為6-1=5，選B
13.
一直對D答案比較困惑，實際跨越的空間肯定不與個數成正比，不過，實際占有的空間與個數成正比，最終确定不選D，因A明顯錯誤，隻有數組才能做到随機通路。故選A
16.
(來自《算法競賽入門經典》P155)
用遞歸定義 二叉樹T 的先序周遊、中序周遊、後序周遊：
先序周遊 PreOrder(T)=T的根節點+PreOrder(T的左子樹)+PreOrder(T的右子樹)
中序周遊 InOrder(T)=InOrder(T的左子樹)+T的根節點+InOrder(T的右子樹)
後序周遊 PostOrder(T)=PostOrder(T的左子樹)+PostOrder(T的右子樹)+T的根節點
通過舉例：一個根節點與一個隻有一個節點的左子樹； 一個根節點與一個隻有一個節點的右子樹。本題很快就能做完。
17.
(來自《啊哈！算法》P184)
滿二叉樹的嚴格定義是一棵深度為h且有2^h-1個結點的二叉樹。如下圖所示：
完全二叉樹嚴格定義：若設二叉樹的高度為h，除第h層外，其他各層(1-h-1)的結點數都達到最大個數，
第h層從右向左連續缺若幹節點，則這個二叉樹就是完全二叉樹。
如下圖所示：
2^n-1=63
n=6
故為B
19.
T(n)=T(n-1)+n
推導：
T(n)=T(n-2)+n-1+n
T(n)=T(n-3)+n-2+n-1+n
T(n)=T(n-4)+n-3+n-2+n-1+n
......
T(n)=T(1)+2+......+n-3+n-2+n-1+n
T(n)=T(0)+1+2+......+n-3+n-2+n-1+n
T(n)=1+1+2+......+n-3+n-2+n-1+n
T(n)=1+(1+n)*n/2
T(n)=(n^2+n+2)/2
故T(n)=O(n^2)
故選D
二、
1.
枚舉24種組合，選出符合條件的有9種，如下：
2143
2341
2413
3142
3412
3421
4123
4312
4321
2.
猜測應該是完全二叉樹，滿二叉樹到完全二叉樹，每少兩個葉節點就多出一個葉結點。
(來自《啊哈！算法》P184)
滿二叉樹的嚴格定義是一棵深度為h且有2^h-1個結點的二叉樹。如下圖所示：
完全二叉樹嚴格定義：若設二叉樹的高度為h，除第h層外，其他各層(1-h-1)的結點數都達到最大個數，
第h層從右向左連續缺若幹節點，則這個二叉樹就是完全二叉樹。
如下圖所示：
滿二叉樹：
2^11-1=2047
葉節點個數2^10=1024
完全二叉數：
2047-2015=32，少了32個葉節點，應多出16個葉節點
故葉節點數：
1024-32+16=1008
三、
3.
統計小寫字母個數。
4.
(來自《算法競賽入門經典》P66)
函數的形參和在函數内聲明的變量都是該函數的局部變量。無法通路其他函數的局部變量。
局部變量的存儲空間是臨時配置設定的，函數執行完畢時，局部變量的空間将被釋放，其中的值無法保留到下次使用。
題中a的變化沒有影響到p1，原因如上所示，故c1值不變。
題中*a影響的是p2指向的記憶體塊，即c2裡的值，故(*a)++對應的c2值要改變。
四、
1.
a.很快識别出dayNum數組中的資料是12個月的天數。
b.将2015年1月的資料代入該程式，進行模拟，第一步寫出(3)空，第二步寫出(4)空，第三步寫出(1)空，第四步寫出(5)空，最難寫的是(2)空，寫該空時嘗試了2015年2月的資料。
2.
a.程式未完全看懂，代入資料0 3 9進行程式模拟。
b.第一步完成(1)，完全能猜出，第二步完成(5)空，采用對稱性rbound=mid-1，雖然是錯的，此空的錯誤，本人無法在考試時糾正(正确答案rbound=mid)，但不影響其它空的填寫。
c.第三步完成(4)空，第四步完成(2)空，因count需要初始化，是以(2)空還是簡單。
d.第五步完成(3)空，一開始猜反了，但在模拟資料過程中，很快糾正。