第十七屆2011提高組初賽試題及答案C版

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

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

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

4、D高德納獎(jiǎng) （Donald E. Knuth Prize）二、不定項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)不少于1。多選或少選均不得分）。1如果根結(jié)點(diǎn)的深度記為1，則一棵恰有2011個(gè)葉子結(jié)點(diǎn)的二叉樹的深度可能是（ ）。 A10 B11 C12 D2011 2在布爾邏輯中，邏輯“或”的性質(zhì)有（ ）。 A交換律：PVQ = QVP B結(jié)合律：PV（QVR）=（PVQ）VR C冪等律：PVP = P D有界律：PV1 = 1（1表示邏輯真）3一個(gè)正整數(shù)在十六進(jìn)制下有100位，則它在二進(jìn)制下可能有（ ）位。 A399 B400 C401 D4044 匯編語(yǔ)言（ ）。 A是一

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

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

7、議 AHTTP BTCP/IP CFTP DWWW三問(wèn)題求解（共2題，每空5分，共計(jì)10分）1平面圖可以在畫在平面上，且它的邊僅在頂點(diǎn)上才能相交的簡(jiǎn)單無(wú)向圖。4個(gè)頂點(diǎn)的平面圖至少有6條邊，如右圖所示。那么，5個(gè)頂點(diǎn)的平面圖至少有 條邊。2定義一種字符串操作，一次可以將其中一個(gè)元素移到任意位置。舉例說(shuō)明，對(duì)于字符串“BCA”可以將A移到B之前，變字符串“ABC”。如果要將字符串“DACHEBGIF”變成“ABCDEFGHI”最少需要_次操作。四閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1#include<iostream>#include<cstring>using

8、namespace std;const int SIZE = 100;int main() int n,i,sum,x,aSIZE; cin>>n; memset(a,0,sizeof(a); for(i=1;i<=n;i+) cin>>x; ax+; i=0; sum=0; while(sum<(n/2+1) i+; sum+=ai; cout<<i<<endl; return 0;輸入：114 5 6 6 4 3 3 2 3 2 1輸出： 2#include<iostream>using namespace std;i

9、nt 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,eVV;bool visitedV;void dfs(int x

10、,int len) int i; visitedx= true; if(len>ans) ans=len; for(i=1;i<=n;i+) if( (!visitedi) && (exi!=-1) ) dfs(i,len+exi); visitedx=false;int main() int i,j,a,b,c; cin>>n>>m; for(i=1;i<=n;i+) for(j=1;j<=m;j+) eij=-1; for(i=1;i<=m;i+) cin>>a>>b>>c; eab=

11、c; eba=c; for(i=1;i<=n;i+) visitedi=false; ans=0; for(i=1;i<=n;i+) dfs(i,0); cout<<ans<<endl; return 0;輸入：4 61 2 102 3 203 4 304 1 401 3 502 4 60 輸出：_4#include<iostream>#include<cstring>#include<string>using namespace std;const int SIZE=10000;const int LENGTH=10;i

12、nt n,m,aSIZELENGTH;int h(int u,int v) int ans,i; ans=0; for(i=1;i<=n;i+) if( aui!=avi) 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) && (ami=1) ) i+; if(i>n) break; m+; ami=1; for(j=i+1;j<=n;j+) amj=am-1j; sum=0; for

13、(i=1;i<=m;i+) for(j=1;j<=m;j+) sum+=h(i,j); cout<<sum<<endl; return 0;輸入：7輸出：_5 完善程序 (第1題，每空2分，第2題，每空3分，共28分)1.(大整數(shù)開方) 輸入一個(gè)正整數(shù)n（1n10100），試用二分法計(jì)算它的平方根的整數(shù)部分。#include<iostream>#include<string>using namespace std;const int SIZE=200;struct hugeint int len,numSIZE;/其中l(wèi)en表示大整數(shù)

14、的位數(shù)；num1表示個(gè)位，num2表示十位，以此類推hugeint times(hugeint a,hugeint b)/ 計(jì)算大整數(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;i<=a.len+b.len;i+) ans.numi+1+=ans.numi/10; ; if(ans.numa.len+b.len>0) ans.len=a.len+b.len;

15、 else ans.len=a.len+b.len-1; return ans;hugeint add(hugeint a,hugeint b)/計(jì)算大整數(shù)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.numi+= ; ans.numi+1+= ans.numi/10; ans.numi%=10; if(ans.numans.len+1>0) an

16、s.len+; return ans;hugeint average(hugeint a,hugeint b)/計(jì)算大整數(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.len-; return ans;hugeint plustwo(hugeint a)/ 計(jì)算大整數(shù)a加2之后的結(jié)果 int i; hugeint ans; ans=a; ans.num1+

17、=2; i=1; while( (i<=ans.len)&&(ans.numi>=10) ) ans.numi+1+=ans.numi/10; ans.numi%=10; i+; if(ans.numans.len+1>0) ; return ans;bool over(hugeint a,hugeint b)/ 若大整數(shù)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.numi<

18、;b.numi) return false; if(a.numi>b.numi) 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.numi=starget.len-i- ; memset(left.num,0,sizeof(left.num

19、); left.len=1; left.num1=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.numi; return 0;2. （笛卡爾樹）對(duì)于一個(gè)給定的兩兩不等的正整數(shù)序列，笛卡爾樹是這樣的一棵二叉樹：首先，它是一個(gè)最小堆，即除了根結(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的權(quán)值都大雨父節(jié)點(diǎn)的權(quán)值；其次，它的中序遍歷恰好就是

20、給定的序列。例如，對(duì)于序列7、2、12、1、10、5、15、3，下圖就是一棵對(duì)應(yīng)的笛卡爾樹。現(xiàn)輸入序列的規(guī)模n（1n<100）和序列的n個(gè)元素，試求其對(duì)應(yīng)的笛卡爾樹的深度d（根節(jié)點(diǎn)深度為1），以及有多少個(gè)葉子節(jié)點(diǎn)的深度為d。#include<iostream>using namespace std;const int SIZE=100+5;const int INFINITY=1000000;int n,aSIZE,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>ai) min=ai; ; if(left<j) ; if(j<right) ; int main() int i; cin>>n; for(i=1;i<=n;i+) cin>>ai; maxDeep=0; solve(1,n,1); cout<<maxDeep<<'