第十七屆2011全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題(普及組C++)

1、第十七屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 普及組 C+語(yǔ)言 二小時(shí)完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無(wú)效 一、 單項(xiàng)選擇題 （共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確選項(xiàng)。）1在二進(jìn)制下，1011001 + （ ） = 1100110。 A1011 B1101 C1010 D11112字符“0”的ASCII碼為48，則字符“9”的ASCII碼為（ ）。 A39 B57 C120 D視具體的計(jì)算機(jī)而定3一片容量為8GB的SD卡能儲(chǔ)存大約（ ）張大小為2MB的數(shù)碼照片。 A1600 B2000 C4000 D 160004摩爾定律（Moore'

2、s law)是由英特爾創(chuàng)始人之一戈登·摩爾(Gordon Moor)提出來(lái)的。根據(jù)摩爾定律，在過(guò)去幾十年一級(jí)在可預(yù)測(cè)的未來(lái)紀(jì)念，單塊集成電路的集成度大約每（ ）個(gè)月翻一番。 A1 B 6 C 18 D 365無(wú)向完全圖是圖中每對(duì)頂點(diǎn)之間都恰好有一條邊的簡(jiǎn)單圖。已知無(wú)向完全圖G有7個(gè)頂點(diǎn)，則它共有（ ）條邊。 A7 B21 C42 D49 6 寄存器是（ ）的重要組成部分。 A硬盤 B高速緩存 C內(nèi)存 D中央處理器（CPU）7如果根結(jié)點(diǎn)的深度記為1，則一棵恰有2011個(gè)葉結(jié)點(diǎn)的二叉樹(shù)的深度最少是（ ）。 A10 B11 C12 D138體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場(chǎng)，按老師的

3、要求從高到矮站成一排。每個(gè)同學(xué)按順序來(lái)到操場(chǎng)時(shí)，都從排尾走到排頭，找到第一個(gè)比自己高的同學(xué)，并站在他的后面。這種站隊(duì)的方法類似于（ ）算法。 A快速排序 B插入排序 C冒泡排序 D歸并排序9一個(gè)正整數(shù)在二進(jìn)制下有100位，則它在十六進(jìn)制下有（ ）位。 A7 B13 C25 D不能確定10 有人認(rèn)為，在個(gè)人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是（ ）。 A正確的，將文件放入回收站以為著徹底刪除、無(wú)法恢復(fù) B不正確的，只有將回收站清空后，才意味著徹底刪除、無(wú)法恢復(fù) C不正確的，即使回收站清空，文件只是被標(biāo)記為刪除，仍可能通過(guò)回復(fù)軟件找回 D不正確的，只要在硬盤上出現(xiàn)過(guò)的文件，

4、永遠(yuǎn)不可能被徹底刪除11廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。 A鏈表 B隊(duì)列 C棧 D散列表12在使用高級(jí)語(yǔ)言編寫程序時(shí)，一般提到的“空間復(fù)雜度”中的“空間”是指（ ）。 A程序運(yùn)行時(shí)理論上所占的內(nèi)存空間 B程序運(yùn)行時(shí)理論上所占的數(shù)組空間 C程序運(yùn)行時(shí)理論上所占的硬盤空間 D程序源文件理論上所占的硬盤空間13在含有n個(gè)元素的雙向鏈表中查詢是否存在關(guān)鍵字為k的元素，最快情況下運(yùn)行的時(shí)間復(fù)雜度是（ ）。 AO(1 ) BO( log n ) CO( n ) DO( n log n )14 生物特征識(shí)別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識(shí)別、虹膜識(shí)別、人臉識(shí)別等技術(shù)

5、已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。一下不屬于生物特征識(shí)別技術(shù)及其應(yīng)用的是（ ）。 A指靜脈驗(yàn)證 B步態(tài)驗(yàn)證 CATM機(jī)密碼驗(yàn)證 D聲音驗(yàn)證15現(xiàn)有一段文言文，要通過(guò)二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡(jiǎn)單起見(jiàn)，假設(shè)這段文言文只由4個(gè)漢字“之”、“呼”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、200。那么，“也”字的編碼長(zhǎng)度是（ ）。 A1 B2 C3 D416關(guān)于匯編語(yǔ)言，下列說(shuō)法錯(cuò)誤的是（ ） A是一種與具體硬件相關(guān)的程序設(shè)計(jì)語(yǔ)言 B在編寫復(fù)雜程序時(shí)，相對(duì)于高級(jí)語(yǔ)言而言代碼量較大，且不易調(diào)試 C可以直接訪問(wèn)寄存器、內(nèi)存單元、以及I/O端口 D隨著高級(jí)語(yǔ)言的誕生，如今已完全

6、被淘汰，不再使用17 （ ）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。當(dāng)搜索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇。： A回溯法 B枚舉法 C動(dòng)態(tài)規(guī)劃 D貪心181956年（ ）手語(yǔ)肖克利、巴丁和布拉頓，以表彰他們對(duì)半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。 A諾貝爾物理學(xué)獎(jiǎng) B約翰·馮·諾依曼獎(jiǎng) C圖靈獎(jiǎng) D高德納獎(jiǎng)19 對(duì)一個(gè)有向圖而言，如果每個(gè)節(jié)點(diǎn)都存在到達(dá)其他任何節(jié)點(diǎn)的路徑，那么就稱它是強(qiáng)連通的。例如，有圖就是一個(gè)強(qiáng)連通圖。事實(shí)上，在刪掉邊（ ）后，它依然是強(qiáng)連通的。 A a Bb Cc Dd20從ENIAC到當(dāng)前最先進(jìn)的計(jì)算機(jī)，馮·

7、諾依曼體系結(jié)構(gòu)始終占有重要地位。馮諾依曼提醒結(jié)構(gòu)的核心內(nèi)容是（ ）。 A采用開(kāi)關(guān)電路 B采用半導(dǎo)體器件 C采用存儲(chǔ)程序和程序控制原理 D采用鍵盤輸入二問(wèn)題求解（共2題，每空5分，共計(jì)10分）1每份考卷都有一個(gè)8位二進(jìn)制序列號(hào)。當(dāng)且僅當(dāng)一個(gè)序列號(hào)含有偶數(shù)個(gè)1時(shí)，它才是有效的。例如，0000000、01010011都是有效的序列號(hào)，而11111110不是。那么，有效的序列號(hào)共有 個(gè)。2定義字符串的基本操作為：刪除一個(gè)字符插入一個(gè)字符和將一個(gè)字符修改成另外一個(gè)字符這三種操作。將字符串變成字符串的最少操作步數(shù)，稱為字符串到字符串的編輯距離。字符串“ABCDEFG”到字符串“BADECG”的編輯距離為

8、。三閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1#include<iostream>using namespace std;int main() int i,n,m,ans; cin>>n>>m; i=n; ans=0; while(i<=m) ans+=i; i+; cout<<ans<<endl; return 0;輸入：10 20輸出：_2#include<iostream>#include<string>using namespace std;int main() string map= &q

9、uot;2223334445556667778889999" string tel; int i; cin>>tel; for(i=0;i<tel.length();i+) if(teli>='0') && (teli<='9') ) cout<<teli; else if( (teli>='A') && (teli<='Z') cout<<mapteli-'A' cout<<endl; retu

10、rn 0;輸入：CCF-NOIP-2011 輸出：_3#include<iostream>#include<cstring>using 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; retur

11、n 0;輸入：114 5 6 6 4 3 3 2 3 2 1輸出： 4#include<iostream>using namespace std;int solve(int n,int m) int i,sum; if(m=1) return 1; sum=0; for(i=1;i<n;i+) sum+= solve(i,m-1); return sum;int main() int n,m; cin>>n>>m; cout<<solve(n,m)<<endl; return 0;輸入：7 4輸出：_四完善程序 (前11空，每空

12、2分，后2空，每空3分，共28分)1（子矩陣）給輸入一個(gè)n1*m1的矩陣a，和n2*m2的矩陣b，問(wèn)a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出“There isno answer”。#include<iostream>using namespace std;const int SIZE = 50;int n1,m1,n2,m2,aSIZESIZE,bSIZESIZE;int main() int i,j,k1,k2; bool good ,haveAns; cin>>n1>>m1; for(i=1;i<=n1;i+)

13、for(j=1;j<=m1;j+) cin>>aij; cin>>n2>>m2; for(i=1;i<=n2;i+) for(j=1;j<=m2;j+) ; haveAns=false; for(i=1;i<=n1-n2+1;i+) for(j=1;j<= ;j+) ; for(k1=1;k1<=n2;k1+) for(k2=1;k2<= ;k2+) if(ai+k1-1j+k2-1!=bk1k2) good=false; if(good) cout<<i<<' '<&l

14、t;j<<endl; ; if(!haveAns) cout<<"There is no answer"<<endl; return 0;2. (大整數(shù)開(kāi)方) 輸入一個(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ù)的位數(shù)；num1表示個(gè)位，num2表示十位，以此類推hug

15、eint 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; else ans.len=a.len+b.len-1;

16、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) ans.len+; return ans;hugeint av

17、erage(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+=2; i=1; while( (i<=ans.le

18、n)&&(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<b.numi) return false; if(a.n

19、umi>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); left.len=1; left.num1=1; right=tar