（ 提高組 C++語言 兩小時完成 ）
● ● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上壹律無效 ●●
壹、單項選擇題 （***10題，每題1.5分，***計15分。每題有且僅有壹個正確選項。）
1．在二進制下，1011001 + （ ）= 1100110。
A．1011 B ．1101 C．1010 D．1111
2．字符“A”的ASCII碼為十六進制41，則字符“Z”的ASCII碼為十六進制的（ ）。
A．66 B．5A C．50 D．視具體的計算機而定
3．右圖是壹棵二叉樹，它的先序遍歷是（ ）。
A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF
4．寄存器是（ ）的重要組成部分。
A．硬盤 B．高速緩存 C．內存 D．中央處理器（CPU）
5．廣度優先搜索時，需要用到的數據結構是（ ）。
A．鏈表 B．隊列 C．棧 D．散列表
6．在使用高級語言編寫程序時，壹般提到的“空間復雜度”中的空間是指（ ）。
A．程序運行時理論上所占的內存空間
B．程序運行時理論上所占的數組空間
C．程序運行時理論上所占的硬盤空間
D．程序源文件理論上所占的硬盤空間
7．應用快速排序的分治思想，可以實現壹個求第K大數的程序。假定不考慮極端的最壞情況，理論上可以實現的最低的算法時間復雜度為（ ）。
A．O (n2) B．O (n log n ) C．O (n) D． O (1)
8．為解決web應用中的不兼容問題，保障信息的順利流通，（ ）制定了壹系列標準，涉及HTML、XML、CSS等，並建議開發者遵循。
A．微軟 B．美國計算機協會（ACM） C．聯合國教科文組織 D．萬維網聯盟（W3C）
9．體育課的鈴聲響了，同學們都陸續的奔向操場，按老師的要求從高到低站成壹排。每個同學按順序來到操場時，都從排尾走到排頭，找到第壹個比自己高的同學，並站在他的後面。這種站隊的方法類似於（ ）算法。
A．快速排序 B．插入排序 C．冒泡排序 D．歸並排序
10．1956年（ ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉頓（Walter Brattain）
A．諾貝爾物理學獎 B．約翰?馮?諾依曼獎
C．圖靈獎 D．高德納獎 （Donald E. Knuth Prize）
二、不定項選擇題 （***10題，每題1.5分，***計15分。每題正確答案的個數不少於1。多選或少選均不得分）。
1．如果根結點的深度記為1，則壹棵恰有2011個葉子結點的二叉樹的深度可能是（ ）。
A．10 B．11 C．12 D．2011
2．在布爾邏輯中，邏輯“或”的性質有（ ）。
A．交換律：PVQ = QVP
B．結合律：PV（QVR）=（PVQ）VR
C．冪等律：PVP = P
D．有界律：PV1 = 1（1表示邏輯真）
3．壹個正整數在十六進制下有100位，則它在二進制下可能有（ ）位。
A．399 B．400 C．401 D．404
4．匯編語言（ ）。
A．是壹種與具體硬件無關的程序設計語言
B．在編寫復雜程序時，相對於高級語言而言代碼量大，且不易調試
C．可以直接訪問寄存器、內存單元、I/O端口
D．隨著高級語言的誕生，如今已被完全淘汰，不再使用
5．現有壹段文言文，要通過二進制哈夫曼編碼進行壓縮。簡單起見，假設這段文言文只由4個漢字“之”、“乎”、“者”、“也”組成，它們出現的次數分別為700、600、300、400。那麽，“也”字的編碼長度可能是（ ）。
A．1 B．2 C．3 D．4
6．生物特征識別，是利用人體本身的生物特征進行身份認證的壹種技術。目前，指紋識別、虹膜識別、人臉識別等技術已廣泛應用於政府、銀行、安全防衛等領域。以下屬於生物特征識別技術及其應用的是（ ）。
A．指靜脈驗證 B．步態驗證 C．ATM機密碼驗證 D．聲音驗證
7．對於序列“7、5、1、9、3、6、8、4”，在不改變順序的情況下，去掉（ ）會使逆序對的個數減少3。
A．7 B．5 C．3 D．6
8．計算機中的數值信息分為整數和實數（浮點數）。實數之所以能夠表示很大或者很小的數，是由於使用了（ ）。
A．階碼 B．補碼 C．反碼 D．較長的尾數
9．對右圖使用Dijkstra算法計算S點到其余各點的最短路徑長度時，到B點的距離d[B]初始時賦為8，在算法的執行過程中還會出現的值有（ ）。
A．3 B． 7 C．6 D．5
10．為計算機網絡中進行數據交換而建立的規則、標準或約定的集合稱為網絡協議。下列英文縮寫中，（ ）是網絡協議
A．HTTP B．TCP/IP C．FTP D．WWW
三．問題求解（***2題，每空5分，***計10分）
1．平面圖可以在畫在平面上，且它的邊僅在頂點上才能相交的簡單無向圖。4個頂點的平面圖至少有6條邊，如右圖所示。那麽，5個頂點的平面圖至少有 條邊。
2．定義壹種字符串操作，壹次可以將其中壹個元素移到任意位置。舉例說明，對於字符串“BCA”可以將A移到B之前，變字符串“ABC”。如果要將字符串“DACHEBGIF”變成“ABCDEFGHI”最少需要________次操作。
四．閱讀程序寫結果（***4題，每題8分，***計32分）
1．
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
int n,i,sum,x,a[SIZE];
cin>>n;
memset(a,0,sizeof(a));
for(i=1;i<=n;i++){
cin>>x;
a[x]++;
}
i=0;
sum=0;
while(sum<(n/2+1)){
i++;
sum+=a[i];
}
cout<<i<<endl;
return 0;
}
輸入：
11
4 5 6 6 4 3 3 2 3 2 1
輸出：
2．
#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
if(x<n)
f2(y,x+y);
}
void f2(int x,int y)
{
cout<<x<<' ';
f1(y,x+y);
}
int main()
{
cin>>n;
f1(0,1);
return 0;
return 0;
}
輸入：30
輸出：_______________
3．
#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
int i;
visited[x]= true;
if(len>ans)
ans=len;
for(i=1;i<=n;i++)
if( (!visited[i]) && (e[x][i]!=-1) )
dfs(i,len+e[x][i]);
visited[x]=false;
}
int main()
{
int i,j,a,b,c;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
e[i][j]=-1;
for(i=1;i<=m;i++)
{
cin>>a>>b>>c;
e[a][b]=c;
e[b][a]=c;
}
for(i=1;i<=n;i++)
visited[i]=false;
ans=0;
for(i=1;i<=n;i++)
dfs(i,0);
cout<<ans<<endl;
return 0;
}
輸入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
輸出：______________
4．
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
int ans,i;
ans=0;
for(i=1;i<=n;i++)
if( a[u][i]!=a[v][i])
ans++;
return ans;
}
int main()
{
int sum,i,j;
cin>>n;
memset(a,0,sizeof(a));
m=1;
while(1)
{
i=1;
while( (i<=n) && (a[m][i]==1) )
i++;
if(i>n)
break;
m++;
a[m][i]=1;
for(j=i+1;j<=n;j++)
a[m][j]=a[m-1][j];
}
sum=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
sum+=h(i,j);
cout<<sum<<endl;
return 0;
}
輸入：7
輸出：_________
五．完善程序 (第1題，每空2分，第2題，每空3分，***28分)
1.(大整數開方) 輸入壹個正整數n（1≤n≤10100），試用二分法計算它的平方根的整數部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//其中len表示大整數的位數；num[1]表示個位，num[2]表示十位，以此類推
hugeint times(hugeint a,hugeint b)
// 計算大整數a和b的乘積
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
① +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
② ;
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeint a,hugeint b)
//計算大整數a和b 的和
{
int i;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= ③ ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeint a,hugeint b)
//計算大整數a和b的平均數的整數部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=( ④ )*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
// 計算大整數a加2之後的結果
{
int i;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
⑤ ;
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整數a>b則返回true，否則返回false
{
int i;
if( ⑥ )
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
int i;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]- ⑦ ;
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over( ⑧ ))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}
2. （笛卡爾樹）對於壹個給定的兩兩不等的正整數序列，笛卡爾樹是這樣的壹棵二叉樹：首先，它是壹個最小堆，即除了根結點，每個節點的權值都大雨父節點的權值；其次，它的中序遍歷恰好就是給定的序列。例如，對於序列7、2、12、1、10、5、15、3，下圖就是壹棵對應的笛卡爾樹。現輸入序列的規模n（1≤n<100）和序列的n個元素，試求其對應的笛卡爾樹的深度d（根節點深度為1），以及有多少個葉子節點的深度為d。
#include<iostream>
using namespace std;
const int SIZE=100+5;
const int INFINITY=1000000;
int n,a[SIZE],maxDeep,num;
void solve(int left,int right,int deep)
{
int i,j,min;
if(deep>maxDeep){
maxDeep=deep;
num=1;
}
else if(deep==maxDeep)
① ;
min= INFINITY;
for(i=left;i<=right;i++)
if(min>a[i]){
min=a[i];
② ;
}
if(left<j)
③ ;
if(j<right)
④ ;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
maxDeep=0;
solve(1,n,1);
cout<<maxDeep<<' '<<num<<endl;
return 0;
}
NOIP2011年提高組（C++語言）參考答案與評分標準
壹、單項選擇題：（每題1.5分）
1. B 2. B 3. A 4. D 5. B
6. A 7. C 8. D 9. B 10. A
二、 不定項選擇題 （***10題，每題1.5分，***計15分。每題正確答案的個數大於或等於1。多選或少選均不得分）。
1. CD 2. ABCD 3. AB 4. BC 5. BC
6. ABD 7. CD 8. A 9. BCD 10. ABC
三、問題求解：（***2題，每空5分，***計10分）
1．9
2．4
四、閱讀程序寫結果（***4題，每題8分，***計32分）
1．3
2．1 2 5 13 34
3．150
4．57344
五、完善程序（第1題，每空2分，第2題，每空3分，***計28分）
（說明：以下各程序填空可能還有壹些等價的寫法，各省可請本省專家審定和上機驗證，不壹定上報科學委員會審查）
1．
① ans.num[i + j - 1]
② ans.num[i] = ans.num[i] mod 10
③ a.num[i] + b.num[i]
④ ans.num[i] % 2 (或 ans.num[i] & 1)
⑤ ans.len++ （或 ans.len = ans.len + 1）
⑥ a.len < b.len
⑦ '0'(或48）
⑧ times(middle, middle), target
2．
① num++ (或 num = num + 1)
② j = i
③ solve(left, j - 1, deep + 1)
④ solve(j + 1, right, deep + 1)