資源簡介

NOIP 2010試題與解題報告
NOIP 2010初賽試題
（ 普及組 C++語言 ）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確選項。）
1．2E+03表示（ ）。
A. 2.03 B. 5 C. 8 D. 2000
2．一個字節（byte）由（ ）個二進制位組成。
A. 8 B. 16 C. 32 D. 以上都有可能
3．以下邏輯表達式的值恒為真的是（ ）。
A. P∨( P∧Q)∨( P∧ Q) B. Q∨( P∧Q)∨(P∧ Q)
C. P∨Q∨(P∧ Q)∨( P∧Q) D. P∨ Q∨(P∧ Q)∨( P∧ Q)
4．Linux下可執行文件的默認擴展名為（ ）。
A. exe B. com C. dll D. 以上都不是
5．如果樹根算第1層，那么一棵n層的二叉樹最多有（ ）個結點。
A. 2n-1 B. 2n C. 2n+1 D. 2n+1
6．提出“存儲程序”的計算機工作原理的是（ ）。
A. 克勞德·香農 B. 戈登·摩爾 C. 查爾斯·巴比奇 D. 馮·諾依曼
7．設X、Y、Z分別代表三進制下的一位數字，若等式XY + ZX = XYX在三進制下成立，那么同樣在三進制下，等式XY * ZX = （ ）也成立。
A. YXZ B. ZXY C. XYZ D. XZY
8．Pascal語言、C語言和C++語言都屬于（ ）。
A. 面向對象語言 B. 腳本語言 C. 解釋性語言 D. 編譯性語言
9．前綴表達式“+ 3 * 2 + 5 12”的值是（ ）。
A. 23 B. 25 C. 37 D. 65
10．主存儲器的存取速度比中央處理器（CPU）的工作速度慢得多，從而使得后者的效率受到影響。而根據局部性原理，CPU所訪問的存儲單元通常都趨于聚集在一個較小的連續區域中。于是，為了提高系統整體的執行效率，在CPU中引入了（ ）。
A. 寄存器 B. 高速緩存 C. 閃存 D. 外存
11．一個字長為8位的整數的補碼是11111001，則它的原碼是（ ）。
A. 00000111 B. 01111001 C. 11111001 D. 10000111
12．基于比較的排序時間復雜度的下限是（ ），其中n表示待排序的元素個數。
A. Θ(n) B. Θ(n log n) C. Θ(log n) D. Θ(n2)
13．一個自然數在十進制下有n位，則它在二進制下的位數與（ ）最接近。
A. 5n B. n*log210 C. 10*log2n D. 10nlog2n
14．在下列HTML語句中，可以正確產生一個指向NOI官方網站的超鏈接的是（ ）。
A. 歡迎訪問NOI網站
B. 歡迎訪問NOI網站
C. http://www.
D. 歡迎訪問NOI網站
15．元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個出棧的是R3，那么第5個出棧的不可能是（ ）。
A. R1 B. R2 C. R4 D. R5
16．雙向鏈表中有兩個指針域llink和rlink，分別指向該結點的前驅及后繼。設p指向鏈表中的一個結點，它的左右結點均非空?，F要求刪除結點p，則下面語句序列中錯誤的是（ ）。
A. p->rlink->llink = p->rlink;
p->llink->rlink = p->llink; delete p;
B. p->llink->rlink = p->rlink;
p->rlink->llink = p->llink; delete p;
C. p->rlink->llink = p->llink;
p->rlink->llink->rlink = p->rlink; delete p;
D. p->llink->rlink = p->rlink;
p->llink->rlink->llink = p->llink; delete p;
17．一棵二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結點的左子樹的結點個數可能是（ ）。
A. 2 B. 3 C. 4 D. 5
18．關于拓撲排序，下面說法正確的是（ ）。
A. 所有連通的有向圖都可以實現拓撲排序
B. 對同一個圖而言，拓撲排序的結果是唯一的
C. 拓撲排序中入度為0的結點總會排在入度大于0的結點的前面
D. 拓撲排序結果序列中的第一個結點一定是入度為0的點
19．完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上至下、從左至右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置，則第k號結點的父結點如果存在的話，應當存放在數組的（ ）號位置。
A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2下取整
20．全國青少年信息學奧林匹克系列活動的主辦單位是（ ）。
A. 教育部 B. 科技部 C. 共青團中央 D. 中國計算機學會
二、問題求解（共2題，每題5分，共計10分）
1．LZW編碼是一種自適應詞典編碼。在編碼的過程中，開始時只有一部基礎構造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。
舉例說明，考慮一個待編碼的信息串："xyx yy 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。
現在已知初始詞典的3個條目如上述，則信息串"yyxy xx yyxy xyx xx xyx"的編碼是_________。
2．隊列快照是指在某一時刻隊列中的元素組成的有序序列。例如，當元素1、2、3入隊，元素1出隊后，此刻的隊列快照是"2 3"。當元素2、3也出隊后，隊列快照是""，即為空。現有3個正整數元素依次入隊、出隊。已知它們的和為8，則共有_________種可能的不同的隊列快照（不同隊列的相同快照只計一次）。例如，"5 1"、"4 2 2"、""都是可能的隊列快照；而"7"不是可能的隊列快照，因為剩下的2個正整數的和不可能是1。
三、閱讀程序寫結果（共4題，每題8分，其中第4題（1）、（2）各4分，共計32分）
1．
#include
using namespace std;
void swap(int & a, int & b)
{
int t;
t = a;
a = b;
b = t;
}
int main()
{
int a1, a2, a3, x;
cin>>a1>>a2>>a3;
if (a1 > a2)
swap(a1, a2);
if (a2 > a3)
swap(a2, a3);
if (a1 > a2)
swap(a1, a2);
cin>>x;
if (x < a2)
if (x < a1)
cout<else
cout<else
if (x < a3)
cout<else
cout<return 0;
}
輸入：
91 2 20
77
輸出：_________
2．
#include
using namespace std;
int rSum(int j)
{
int sum = 0;
while (j != 0) {
sum = sum * 10 + (j % 10);
j = j / 10;
}
return sum;
}
int main()
{
int n, m, i;
cin>>n>>m;
for (i = n; i < m; i++)
if (i == rSum(i))
cout<return 0;
}
輸入：90 120
輸出：_________
3．
#include
#include
using namespace std;
int main()
{
string s;
char m1, m2;
int i;
getline(cin, s);
m1 = ' ';
m2 = ' ';
for (i = 0; i < s.length(); i++)
if (s[i] > m1) {
m2 = m1;
m1 = s[i];
}
else if (s[i] > m2)
m2 = s[i];
cout<return 0;
}
輸入：Expo 2010 Shanghai China
輸出：_________
提示：
字符 空格 '0' 'A' 'a'
ASCII碼 32 48 65 97
4．
#include
using namespace std;
const int NUM = 5;
int r(int n)
{
int i;
if (n <= NUM)
return n;
for (i = 1; i <= NUM; i++)
if (r(n - i) < 0)
return i;
return -1;
}
int main()
{
int n;
cin>>n;
cout<return 0;
}
（1）
輸入：7
輸出：_________（4分）
（2）
輸入：16
輸出：_________（4分）
四、完善程序（前4空，每空2.5分，后6空，每空3分，共計28分）
1．（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶數都可寫成兩個質數之和。迄今為止，這仍然是一個著名的世界難題，被譽為數學王冠上的明珠。試編寫程序，驗證任一大于2且不超過n的偶數都能寫成兩個質數之和。
#include
using namespace std;
int main()
{
const int SIZE = 1000;
int n, r, p[SIZE], i, j, k, ans;
bool tmp;
cin>>n;
r = 1;
p[1] = 2;
for (i = 3; i <= n; i++) {
① ;
for (j = 1; j <= r; j++)
if (i % ② == 0) {
tmp = false;
break;
}
if (tmp) {
r++;
③ ;
}
}
ans = 0;
for (i = 2; i <= n / 2; i++) {
tmp = false;
for (j = 1; j <= r; j++)
for (k = j; k <= r; k++)
if (i + i == ④ ) {
tmp = true;
break;
}
if (tmp)
ans++;
}
cout<return 0;
}
若輸入n為2010，則輸出 ⑤ 時表示驗證成功，即大于2且不超過2010的偶數都滿足哥德巴赫猜想。
2．（過河問題）在一個月黑風高的夜晚，有一群人在河的右岸，想通過唯一的一根獨木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時必須借助燈光來照明，很不幸的是，他們只有一盞燈。另外，獨木橋上最多承受兩個人同時經過，否則將會坍塌。每個人單獨過橋都需要一定的時間，不同的人需要的時間可能不同。兩個人一起過橋時，由于只有一盞燈，所以需要的時間是較慢的那個人單獨過橋時所花的時間。現輸入n（2≤n<100）和這n個人單獨過橋時需要的時間，請計算總共最少需要多少時間，他們才能全部到達河的左岸。
例如，有3個人甲、乙、丙，他們單獨過橋的時間分別為1、2、4，則總共最少需要的時間為7。具體方法是：甲、乙一起過橋到河的左岸，甲單獨回到河的右岸將燈帶回，然后甲、丙再一起過橋到河的左岸，總時間為2+1+4=7。
#include
using namespace std;
const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
int n, hour[SIZE];
bool pos[SIZE];
int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
int go(bool stage)
{
int i, j, num, tmp, ans;
if (stage == RIGHT_TO_LEFT) {
num = 0;
ans = 0;
for (i = 1; i <= n; i++)
if (pos[i] == RIGHT) {
num++;
if (hour[i] > ans)
ans = hour[i];
}
if ( ① )
return ans;
ans = INFINITY;
for (i = 1; i <= n - 1; i++)
if (pos[i] == RIGHT)
for (j = i + 1; j <= n; j++)
if (pos[j] == RIGHT) {
pos[i] = LEFT;
pos[j] = LEFT;
tmp = max(hour[i], hour[j]) + ② ;
if (tmp < ans)
ans = tmp;
pos[i] = RIGHT;
pos[j] = RIGHT;
}
return ans;
}
if (stage == LEFT_TO_RIGHT) {
ans = INFINITY;
for (i = 1; i <= n; i++)
if ( ③ ) {
pos[i] = RIGHT;
tmp = ④ ;
if (tmp < ans)
ans = tmp;
⑤ ;
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for (i = 1; i <=n; i++) {
cin>>hour[i];
pos[i] = RIGHT;
}
cout<return 0;
}CCF NOIP2010普及組（C++語言）參考答案與評分標準
一、單項選擇題（共20題，每題1.5分，共計30分）
1 2 3 4 5 6 7 8 9 10
D A A D A D B D C B
11 12 13 14 15 16 17 18 19 20
D B B B B A A D C D
二、問題求解（共2題，每題5分，共計10分）
1．2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或22123113431213536）
2．49
三、閱讀程序寫結果（共4題，每題8分，其中第4題（1）、（2）各4分，共計32分）1．2 20 77 91
2．99 101 111
3．120 112
4．（1）1
（2）4
四、完善程序（前4空，每空2.5分，后6空，每空3分，共計28分）
（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）
1．① tmp = true
② p[j]
③ p[r] = i
④ p[j] + p[k]（或p[k] + p[j]）
⑤ 1004
2．① num <= 2（或num < 3 或num == 2）
② go(LEFT_TO_RIGHT)
③ pos[i] == LEFT（或LEFT == pos[i]）
④ hour[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) + hour[i]）
⑤ pos[i] = LEFT
本小題中，LEFT可用true代替，LEFT_TO_RIGHT可用true代替，RIGHT_TO_LEFT可用false代替。

展開更多......

收起↑