資源簡介

CCF NOIP2010提高組（C++語言）參考答案與評分標(biāo)準(zhǔn)
一、單項選擇題（共10題，每題1.5分，共計15分）
1 2 3 4 5 6 7 8 9 10
C A A D B D C B C B
二、不定項選擇題（共10題，每題1.5分，共計15分，多選或少選均不得分）
1 2 3 4 5 6 7 8 9 10
ACD AD ABD AC B B D D BCD ABC
三、問題求解（共3題，每題5分，共計15分）
1．yyxy xx yyxy xyx xx xyx
2．12
3．18
四、閱讀程序?qū)懡Y(jié)果（共4題，每題7分，共計28分）
1．16
2．1 2 3 5 6 7 9 10 14
3．4
4．1 6 9 5 4 8 3 2 7
五、完善程序（第1空2分，其余10空，每空2.5分，共計27分）
（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學(xué)委員會審查）
1．① 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代替。
2．① opt[k]
② home[r] = k
③ j = i + i（或j = 2 * i 或j = i * 2）
④ swap(i, j)（或swap(j, i)）
⑤ value[i] + heap[1]（或heap[1] + value[i]）
⑥ i - mNOIP 2010 初賽試題
（ 提高組 C++語言 兩小時完成 ）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、單項選擇題（共10題，每題1.5分，共計15分。每題有且僅有一個正確選項。）
1．與16進制數(shù)A1.2等值的10進制數(shù)是（ ）。
A. 101.2 B. 111.4 C. 161.125 D. 177.25
2．一個字節(jié)（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下可執(zhí)行文件的默認擴展名為（ ）。
A. exe B. com C. dll D. 以上都不是
5．如果在某個進制下等式7*7=41成立，那么在該進制下等式12*12=（ ）也成立。
A. 100 B. 144 C. 164 D. 196
6．提出“存儲程序”的計算機工作原理的是（ ）。
A. 克勞德·香農(nóng) B. 戈登·摩爾 C. 查爾斯·巴比奇 D. 馮·諾依曼
7．前綴表達式“+ 3 * 2 + 5 12”的值是（ ）。
A. 23 B. 25 C. 37 D. 65
8．主存儲器的存取速度比中央處理器（CPU）的工作速度慢得多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問的存儲單元通常都趨于聚集在一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了（ ）。
A. 寄存器 B. 高速緩存 C. 閃存 D. 外存
9．完全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點從上至下、從左至右依次存放到一個順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點存放在數(shù)組的1號位置，則第k號結(jié)點的父結(jié)點如果存在的話，應(yīng)當(dāng)存放在數(shù)組的（ ）號位置。
A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2下取整
10．以下競賽活動中歷史最悠久的是（ ）。
A. 全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）
B. 全國青少年信息學(xué)奧林匹克競賽（NOI）
C. 國際信息學(xué)奧林匹克競賽（IOI）
D. 亞太地區(qū)信息學(xué)奧林匹克競賽（APIO）
二、不定項選擇題（共10題，每題1.5分，共計15分。每題有一個或多個正確選項。多選或少選均不得分。）
1．元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個出棧的是R3，那么第5個出棧的可能是（ ）。
A. R1 B. R2 C. R4 D. R5
2．Pascal語言、C語言和C++語言都屬于（ ）。
A. 高級語言 B. 自然語言 C. 解釋性語言 D. 編譯性語言
3．原地排序是指在排序過程中（除了存儲待排序元素以外的）輔助空間的大小與數(shù)據(jù)規(guī)模無關(guān)的排序算法。以下屬于原地排序的有（ ）。
A. 冒泡排序 B. 插入排序 C. 基數(shù)排序 D. 選擇排序
4．在整數(shù)的補碼表示法中，以下說法正確的是（ ）。
A. 只有負整數(shù)的編碼最高位為1
B. 在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對值相同
C. 整數(shù)0只有唯一的一個編碼
D. 兩個用補碼表示的數(shù)相加時，如果在最高位產(chǎn)生進位，則表示運算溢出
5．一棵二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結(jié)點的左子樹的結(jié)點個數(shù)可能是（ ）。
A. 0 B. 2 C. 4 D. 6
6．在下列HTML語句中，可以正確產(chǎn)生一個指向NOI官方網(wǎng)站的超鏈接的是（ ）。
A. 歡迎訪問NOI網(wǎng)站
B. 歡迎訪問NOI網(wǎng)站
C. http://www.
D. 歡迎訪問NOI網(wǎng)站
7．關(guān)于拓撲排序，下面說法正確的是（ ）。
A. 所有連通的有向圖都可以實現(xiàn)拓撲排序
B. 對同一個圖而言，拓撲排序的結(jié)果是唯一的
C. 拓撲排序中入度為0的結(jié)點總會排在入度大于0的結(jié)點的前面
D. 拓撲排序結(jié)果序列中的第一個結(jié)點一定是入度為0的點
8．一個平面的法線是指與該平面垂直的直線。過點(1,1,1)、(0,3,0)、(2,0,0)的平面的法線是（ ）。
A. 過點(1,1,1)、(2,3,3)的直線
B. 過點(1,1,1)、(3,2,1)的直線
C. 過點(0,3,0)、(-3,1,1)的直線
D. 過點(2,0,0)、(5,2,1)的直線
9．雙向鏈表中有兩個指針域llink和rlink，分別指向該結(jié)點的前驅(qū)及后繼。設(shè)p指向鏈表中的一個結(jié)點，它的左右結(jié)點均非空。現(xiàn)要求刪除結(jié)點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;
10．今年（2010年）發(fā)生的事件有（ ）。
A. 惠普實驗室研究員Vinay Deolalikar自稱證明了P≠NP
B. 英特爾公司收購計算機安全軟件公司邁克菲（McAfee）
C. 蘋果公司發(fā)布iPhone 4手機
D. 微軟公司發(fā)布Windows 7操作系統(tǒng)
三、問題求解（共3題，每題5分，共計15分）
1．LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。
舉例說明，考慮一個待編碼的信息串："xyx yy yy xyx"。初始詞典只有3個條目，第一個為x，編碼為1；第二個為y，編碼為2；第三個為空格，編碼為3；于是串"xyx"的編碼為1-2-1（其中-為編碼分隔符），加上后面的一個空格就是1-2-1-3。但由于有了一個空格，我們就知道前面的"xyx"是一個單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個詞條添加到詞典里，編碼為4，然后按照新的詞典對后繼信息進行編碼，以此類推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。
我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接收方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對該序列的完全恢復(fù)。解碼過程是編碼過程的逆操作。現(xiàn)在已知初始詞典的3個條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是"_________"。
2．無向圖G有7個頂點，若不存在由奇數(shù)條邊構(gòu)成的簡單回路，則它至多有_________條邊。
3．記T為一隊列，初始時為空，現(xiàn)有n個總和不超過32的正整數(shù)依次入隊。如果無論這些數(shù)具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列T中的數(shù)之和恰好為9，那么n的最小值是_________。
四、閱讀程序?qū)懡Y(jié)果（共4題，每題7分，共計28分）
1．
#include
using namespace std;
int main() {
const int SIZE = 10;
int data[SIZE], i, j, cnt, n, m;
cin>>n>>m;
for(i = 1; i <= n; i++)
cin>>data[i];
for(i = 1; i <= n; i++) {
cnt = 0;
for(j = 1; j <= n; j++)
if ((data[i] < data[j]) || (data[j] == data[i] && j < i))
cnt++;
if(cnt == m)
cout<}
return 0;
}
輸入
5 2
96 -8 0 16 87
輸出：_________
2．
#include
using namespace std;
int main()
{
const int SIZE = 100;
int na, nb, a[SIZE], b[SIZE], i, j, k;
cin>>na;
for (i = 1; i <= na; i++)
cin>>a[i];
cin>>nb;
for (i = 1; i <= nb; i++)
cin>>b[i];
i = 1;
j = 1;
while ((i <= na) && (j <= nb)) {
if (a[i] <= b[j]) {
cout<i++;
}
else {
cout<j++;
}
}
if (i <= na)
for (k = i; k <= na; k++)
cout<if (j <= nb)
for (k = j; k <= nb; k++)
cout<return 0;
}
輸入：
5
1 3 5 7 9
4
2 6 10 14
輸出：_________
3．
#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;
}
輸入：16
輸出：_________
4．
#include
using namespace std;
const int SIZE = 100;
int n, m, r[SIZE];
bool map[SIZE][SIZE], found;
bool successful()
{
int i;
for (i = 1; i <= n; i++)
if (! map[r[i]][r[i % n + 1]])
return false;
return true;
}
void swap(int *a, int *b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
void perm(int left, int right)
{
int i;
if (found)
return;
if (left > right) {
if (successful()) {
for (i = 1; i <= n; i++)
cout<found = true;
}
return;
}
for(i = left; i <= right; i++) {
swap(r + left, r + i);
perm(left + 1, right);
swap(r + left, r + i);
}
}
int main()
{
int x, y, i;
cin>>n>>m;
memset(map, false, sizeof(map));
for (i = 1; i <= m; i++) {
cin>>x>>y;
map[x][y] = true;
map[y][x] = true;
}
for (i = 1; i <= n; i++)
r[i] = i;
found = false;
perm(1, n);
if (! found)
cout<<"No solution!"<return 0;
}
輸入：
9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
輸出：_________
五、完善程序（第1空2分，其余10空，每空2.5分，共計27分）
1．（過河問題）在一個月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過唯一的一根獨木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時必須借助燈光來照明，很不幸的是，他們只有一盞燈。另外，獨木橋上最多承受兩個人同時經(jīng)過，否則將會坍塌。每個人單獨過橋都需要一定的時間，不同的人需要的時間可能不同。兩個人一起過橋時，由于只有一盞燈，所以需要的時間是較慢的那個人單獨過橋時所花的時間。現(xiàn)輸入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;
}
2．（烽火傳遞）烽火臺又稱烽燧，是重要的軍事防御設(shè)施，一般建在險要處或交通要道上。一旦有敵情發(fā)生，白天燃燒柴草，通過濃煙表達信息；夜晚燃燒干柴，以火光傳遞軍情。在某兩座城市之間有n個烽火臺，每個烽火臺發(fā)出信號都有一定的代價。為了使情報準(zhǔn)確地傳遞，在連續(xù)m個烽火臺中至少要有一個發(fā)出信號。現(xiàn)輸入n、m和每個烽火臺發(fā)出信號的代價，請計算總共最少花費多少代價，才能使敵軍來襲之時，情報能在這兩座城市之間準(zhǔn)確傳遞。
例如，有5個烽火臺，它們發(fā)出信號的代價依次為1、2、5、6、2，且m為3，則總共最少花費的代價為4，即由第2個和第5個烽火臺發(fā)出信號。
#include
using namespace std;
const int SIZE = 100;
int n, m, r, value[SIZE], heap[SIZE],
pos[SIZE], home[SIZE], opt[SIZE];
//heap[i]表示用順序數(shù)組存儲的堆heap中第i個元素的值
//pos[i]表示opt[i]在堆heap中的位置，即heap[pos[i]]=opt[i]
//home[i]表示heap[i]在序列opt中的位置，即opt[home[i]]=heap[i]
void swap(int i, int j)
//交換堆中的第i個和第j個元素
{
int tmp;
pos[home[i]] = j;
pos[home[j]] = i;
tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
tmp = home[i];
home[i] = home[j];
home[j] = tmp;
}
void add(int k)
//在堆中插入opt[k]
{
int i;
r++;
heap[r] = ① ;
pos[k] = r;
② ;
i = r;
while ((i > 1) && (heap[i] < heap[i / 2])) {
swap(i, i / 2);
i /= 2;
}
}
void remove(int k)
//在堆中刪除opt[k]
{
int i, j;
i = pos[k];
swap(i, r);
r--;
if (i == r + 1)
return;
while ((i > 1) && (heap[i] < heap[i / 2])) {
swap(i, i / 2);
i /= 2;
}
while (i + i <= r) {
if ((i + i + 1 <= r) && (heap[i + i + 1] < heap[i + i]))
j = i + i + 1;
else
③ ;
if (heap[i] > heap[j]) {
④ ;
i = j;
}
else
break;
}
}
int main()
{
int i;
cin>>n>>m;
for (i = 1; i <= n; i++)
cin>>value[i];
r = 0;
for (i = 1; i <= m; i++) {
opt[i] = value[i];
add(i);
}
for (i = m + 1; i <= n; i++) {
opt[i] = ⑤ ;
remove( ⑥ );
add(i);
}
cout<return 0;
}

展開更多......

收起↑