NOIP2011提高組初賽試題及答案C+版

1、第十七屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 C+語言 兩小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確選項。）1在二進(jìn)制下， + （ ）= 。 A1011 B 1101 C1010 D11112 字符“A”的ASCII碼為十六進(jìn)制41，則字符“Z”的ASCII碼為十六進(jìn)制的（ ）。 A66 B5A C50 D視具體的計算機而定3右圖是一棵二叉樹，它的先序遍歷是（ ）。AABDEFC BDBEFAC CDFEBCA DABCDEF 4寄存器是（ ）的重要組成部分。 A硬盤 B高速緩存 C內(nèi)

2、存 D中央處理器（CPU）5 廣度優(yōu)先搜索時，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。 A鏈表 B隊列 C棧 D散列表 6在使用高級語言編寫程序時，一般提到的“空間復(fù)雜度”中的空間是指（ ）。A程序運行時理論上所占的內(nèi)存空間B程序運行時理論上所占的數(shù)組空間C程序運行時理論上所占的硬盤空間D程序源文件理論上所占的硬盤空間7應(yīng)用快速排序的分治思想，可以實現(xiàn)一個求第K大數(shù)的程序。假定不考慮極端的最壞情況，理論上可以實現(xiàn)的最低的算法時間復(fù)雜度為（ ）。AO (n2) BO (n log n ) CO (n) D O (1) 8為解決web應(yīng)用中的不兼容問題，保障信息的順利流通，（ ）制定了一系列標(biāo)準(zhǔn)，涉及HTML

3、、XML、CSS等，并建議開發(fā)者遵循。 A微軟 B美國計算機協(xié)會（ACM） C聯(lián)合國教科文組織 D萬維網(wǎng)聯(lián)盟（W3C）9體育課的鈴聲響了，同學(xué)們都陸續(xù)的奔向操場，按老師的要求從高到低站成一排。每個同學(xué)按順序來到操場時，都從排尾走到排頭，找到第一個比自己高的同學(xué)，并站在他的后面。這種站隊的方法類似于（ ）算法。 A快速排序 B插入排序 C冒泡排序 D歸并排序101956年（ ）授予肖克利（William Shockley）、巴?。↗ohn Bardeen）和布拉頓（Walter Brattain） A諾貝爾物理學(xué)獎 B約翰馮諾依曼獎 C圖靈獎 D高德納獎 （Donald E. Knuth Pri

4、ze）二、不定項選擇題 （共10題，每題1.5分，共計15分。每題正確答案的個數(shù)不少于1。多選或少選均不得分）。1如果根結(jié)點的深度記為1，則一棵恰有2011個葉子結(jié)點的二叉樹的深度可能是（ ）。 A10 B11 C12 D2011 2在布爾邏輯中，邏輯“或”的性質(zhì)有（ ）。 A交換律：PVQ = QVP B結(jié)合律：PV（QVR）=（PVQ）VR C冪等律：PVP = P D有界律：PV1 = 1（1表示邏輯真）3一個正整數(shù)在十六進(jìn)制下有100位，則它在二進(jìn)制下可能有（ ）位。 A399 B400 C401 D4044 匯編語言（ ）。 A是一種與具體硬件無關(guān)的程序設(shè)計語言 B在編寫復(fù)雜程序時，

5、相對于高級語言而言代碼量大，且不易調(diào)試 C可以直接訪問寄存器、內(nèi)存單元、I/O端口 D隨著高級語言的誕生，如今已被完全淘汰，不再使用5現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由4個漢字“之”、“乎”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、400。那么，“也”字的編碼長度可能是（ ）。A1 B2 C3 D4 6 生物特征識別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜識別、人臉識別等技術(shù)已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。以下屬于生物特征識別技術(shù)及其應(yīng)用的是（ ）。 A指靜脈驗證 B步態(tài)驗證 CATM機密碼

6、驗證 D聲音驗證 7對于序列“7、5、1、9、3、6、8、4”，在不改變順序的情況下，去掉（ ）會使逆序?qū)Φ膫€數(shù)減少3。 A7 B5 C3 D68計算機中的數(shù)值信息分為整數(shù)和實數(shù)（浮點數(shù)）。實數(shù)之所以能夠表示很大或者很小的數(shù)，是由于使用了（ ）。A階碼 B補碼 C反碼 D較長的尾數(shù)9對右圖使用Dijkstra算法計算S點到其余各點的最短路徑長度時，到B點的距離dB初始時賦為8，在算法的執(zhí)行過程中還會出現(xiàn)的值有（ ）。A3 B 7 C6 D510為計算機網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定的集合稱為網(wǎng)絡(luò)協(xié)議。下列英文縮寫中，（ ）是網(wǎng)絡(luò)協(xié)議 AHTTP BTCP/IP CFTP DWWW三

7、問題求解（共2題，每空5分，共計10分）1平面圖可以在畫在平面上，且它的邊僅在頂點上才能相交的簡單無向圖。4個頂點的平面圖至少有6條邊，如右圖所示。那么，5個頂點的平面圖至少有 條邊。2定義一種字符串操作，一次可以將其中一個元素移到任意位置。舉例說明，對于字符串“BCA”可以將A移到B之前，變字符串“ABC”。如果要將字符串“DACHEBGIF”變成“ABCDEFGHI”最少需要_次操作。四閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1#include#includeusing namespace std;const int SIZE = 100;int main() int n,i,sum

8、,x,aSIZE; cinn; memset(a,0,sizeof(a); for(i=1;ix; ax+; i=0; sum=0; while(sum(n/2+1) i+; sum+=ai; coutiendl; return 0;輸入：114 5 6 6 4 3 3 2 3 2 1輸出： 2#includeusing namespace std;int n;void f2(int x,int y);void f1(int x,int y) if(xn) f2(y,x+y);void f2(int x,int y) coutxn; f1(0,1); return 0; return 0;輸入

9、：30 輸出：_3#includeusing namespace std;const int V=100;int n,m,ans,eVV;bool visitedV;void dfs(int x,int len) int i; visitedx= true; if(lenans) ans=len; for(i=1;inm; for(i=1;i=n;i+) for(j=1;j=m;j+) eij=-1; for(i=1;iabc; eab=c; eba=c; for(i=1;i=n;i+) visitedi=false; ans=0; for(i=1;i=n;i+) dfs(i,0); cout

10、ansendl; return 0;輸入：4 61 2 102 3 203 4 304 1 401 3 502 4 60 輸出：_4#include#include#includeusing namespace std;const int SIZE=10000;const int LENGTH=10;int n,m,aSIZELENGTH;int h(int u,int v) int ans,i; ans=0; for(i=1;in; memset(a,0,sizeof(a); m=1; while(1) i=1; while( (in) break; m+; ami=1; for(j=i+1

11、;j=n;j+) amj=am-1j; sum=0; for(i=1;i=m;i+) for(j=1;j=m;j+) sum+=h(i,j); coutsumendl; return 0;輸入：7輸出：_5 完善程序 (第1題，每空2分，第2題，每空3分，共28分)1.(大整數(shù)開方) 輸入一個正整數(shù)n（1n10100），試用二分法計算它的平方根的整數(shù)部分。#include#includeusing namespace std;const int SIZE=200;struct hugeint int len,numSIZE;/其中l(wèi)en表示大整數(shù)的位數(shù)；num1表示個位，num2表示十位，以此

12、類推hugeint times(hugeint a,hugeint b)/ 計算大整數(shù)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.numi*b.numj; for(i=1;i0) ans.len=a.len+b.len; else ans.len=a.len+b.len-1; return ans;hugeint add(hugeint a,hugeint b)/計算大整數(shù)a和b 的和 int i; hugeint ans;

13、memset(ans.num,0,sizeof(ans.num); if(a.lenb.len) ans.len=a.len; else ans.len=b.len; for(i=1;i0) ans.len+; return ans;hugeint average(hugeint a,hugeint b)/計算大整數(shù)a和b的平均數(shù)的整數(shù)部分 int i; hugeint ans; ans=add(a,b); for(i=ans.len;i=2;i-) ans.numi-1+=( )*10; ans.numi/=2; ans.num1/=2; if(ans.numans.len=0) ans.l

14、en-; return ans;hugeint plustwo(hugeint a)/ 計算大整數(shù)a加2之后的結(jié)果 int i; hugeint ans; ans=a; ans.num1+=2; i=1; while( (i=10) ) ans.numi+1+=ans.numi/10; ans.numi%=10; i+; if(ans.numans.len+10) ; return ans;bool over(hugeint a,hugeint b)/ 若大整數(shù)ab則返回true，否則返回false int i; if( ) return false; if( a.lenb.len ) ret

15、urn true; for(i=a.len;i=1;i-) if(a.numib.numi) return true; return false;int main() string s; int i; hugeint target,left,middle,right; cins; memset(target.num,0,sizeof(target.num); target.len=s.length(); for(i=1;i=1;i-) coutleft.numi; return 0;2. （笛卡爾樹）對于一個給定的兩兩不等的正整數(shù)序列，笛卡爾樹是這樣的一棵二叉樹：首先，它是一個最小堆，即除了根

16、結(jié)點，每個節(jié)點的權(quán)值都大雨父節(jié)點的權(quán)值；其次，它的中序遍歷恰好就是給定的序列。例如，對于序列7、2、12、1、10、5、15、3，下圖就是一棵對應(yīng)的笛卡爾樹?，F(xiàn)輸入序列的規(guī)模n（1n100）和序列的n個元素，試求其對應(yīng)的笛卡爾樹的深度d（根節(jié)點深度為1），以及有多少個葉子節(jié)點的深度為d。#includeusing namespace std;const int SIZE=100+5;const int INFINITY=;int n,aSIZE,maxDeep,num;void solve(int left,int right,int deep)int i,j,min; if(deepmaxD

17、eep) maxDeep=deep; num=1; else if(deep=maxDeep) ; min= INFINITY; for(i=left;iai) min=ai; ; if(leftj) ; if(jn; for(i=1;iai; maxDeep=0; solve(1,n,1); coutmaxDeep numendl; return 0;NOIP2011年提高組（C+語言）參考答案與評分標(biāo)準(zhǔn)一、單項選擇題：（每題1.5分） 1. B 2. B 3. A 4. D 5. B6. A 7. C 8. D 9. B 10. A二、 不定項選擇題 （共10題，每題1.5分，共計15分。每題正確答案的個數(shù)大于或等于1。多選或少選均不得分）。1. CD 2. ABCD3. AB 4. BC 5. BC 6. ABD 7. CD 8. A 9. BCD 10. ABC 三、問題求解：（共2題，每空5分，共計10分）19 24四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分） 13 21 2 5 13 34 3150 457344五、完善程序（第1題，每空2分，第2題，每空3分，共計28分）（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機