第十八全國青少年信息學(xué)奧林匹克聯(lián)賽初賽C++

1、第十八屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組c+語言試題 （競賽時間：2012年10月13日14:3016:30）選手注意：l 試題紙共有15頁，答題紙共有2頁，滿分100分。請?jiān)诖痤}紙上作答，寫在試題紙上的一律無效。l 不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分；每題有且僅有一個正確選項(xiàng)）1.目前計(jì)算機(jī)芯片（集成電路）制造的主要原料是（），它是一種可以在沙子中提煉出的物質(zhì)。a.硅 b.銅 c.鍺 d.鋁2.（）是主要用于顯示網(wǎng)頁服務(wù)器或者文件系統(tǒng)的html文件內(nèi)容，并讓用戶與這些文件交互的一種軟件。a.資源管理器

2、 b.瀏覽器 c.電子郵件 d.編譯器3.目前個人電腦的（）市場占有率最靠前的廠商包括intel、amd等公司。a.顯示器 b.cpu c.內(nèi)存 d.鼠標(biāo)4.無論是tcp/ip模型還是osi模型，都可以視為網(wǎng)絡(luò)的分層模型，每個網(wǎng)絡(luò)協(xié)議都會被歸入某一層中。如果用現(xiàn)實(shí)生活中的例子來比喻這些“層”，以下最恰當(dāng)?shù)氖? ）。a.中國公司的經(jīng)理與伊拉克公司的經(jīng)理交互商業(yè)文件b.軍隊(duì)發(fā)布命令c.國際會議中，每個人都與他國地位對等的人直接進(jìn)行會談d.體育比賽中，每一級比賽的優(yōu)勝者晉級上一級比賽5.如果不在快速排序中引入隨機(jī)化，有可能導(dǎo)致的后果是（）。a.數(shù)組訪問越界 b.陷入死循環(huán)c.排序結(jié)果錯誤 d.排序時

3、間退化為平方級6.1946年誕生于美國賓夕法尼亞大學(xué)的eniac屬于（）計(jì)算機(jī)。a.電子管 b.晶體管 c.集成電路 d.超大規(guī)模集成電路7.在程序運(yùn)行過程中，如果遞歸調(diào)用的層數(shù)過多，會因?yàn)椋ǎ┮l(fā)錯誤。a.系統(tǒng)分配的棧空間溢出 b.系統(tǒng)分配的堆空間溢出c.系統(tǒng)分配的隊(duì)列空間溢出 d.系統(tǒng)分配的鏈表空間溢出8.地址總線的位數(shù)決定了cpu可直接尋址的內(nèi)存空間大小，例如地址總線為16位，其最大的可尋址空間為64kb。如果地址總線是32位，則理論上最大可尋址的內(nèi)存空間為（）。a.128kb b.1mb c.1gb d.4gb9.以下不屬于目前3g（第三代移動通信技術(shù)）標(biāo)準(zhǔn)的是（）。a.gsm b.t

4、d-scdma c.cdma2000 d.wcdma10.仿生學(xué)的問世開辟了獨(dú)特的科學(xué)技術(shù)發(fā)展道路。人們研究生物體的結(jié)構(gòu)、功能和工作原理，并將這些原理移植于新興的工程技術(shù)之中。以下關(guān)于仿生學(xué)的敘述，錯誤的是（）。a.由研究蝙蝠，發(fā)明雷達(dá) b.由研究蜘蛛網(wǎng)，發(fā)明因特網(wǎng)c.由研究海豚，發(fā)明聲納 d.由研究電魚，發(fā)明伏特電池二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分；每題有一個或多個正確選項(xiàng)，多選或少選均不得分）1.如果對于所有規(guī)模為n的輸入，一個算法均恰好進(jìn)行（）次運(yùn)算，我們可以說該算法的時間復(fù)雜度為o(2n)。a.2n+1 b.3n c.n*2n d.22n2.從頂點(diǎn)a0出發(fā)，對有向圖

5、（ ）進(jìn)行廣度優(yōu)先搜索（bfs）時，一種可能的遍歷順序是a0,a1,a2,a3,a4。3.如果一個棧初始時為空，且當(dāng)前棧中的元素從棧底到棧頂依次為a,b,c（如右圖所示），另有元素d已經(jīng)出棧，則可能的入棧順序有（）。a.a,b,c,d b.b,a,c,dc.a,c,b,d d.d,a,b,c4.在計(jì)算機(jī)顯示器所使用的rgb顏色模型中，（）屬于三原色之一。a.黃色 b.藍(lán)色 c.紫色 d.綠色5.一棵二叉樹一共有19個節(jié)點(diǎn)，其葉子節(jié)點(diǎn)可能有（）個。a.1 b.9 c.10 d.116已知帶權(quán)有向圖g上的所有權(quán)值均為正整數(shù)，記頂點(diǎn)u到頂點(diǎn)v的最短路徑的權(quán)值為 。若 是圖g上的頂點(diǎn)，且它們之間兩兩都

6、存路徑可達(dá)，則以下說法正確的有（ ）。a 到的最短路徑可能包含一個環(huán)b c d如果是 到 的一條最短路徑，那么是 到的一條最短路徑 7邏輯異或（）是一種二元運(yùn)算，其真值表如下所示。abfalsefalsefalsefalsetruetruetruefalsetruetruetrueflase以下關(guān)于邏輯異或的性質(zhì)，正確的有（ ）。a交換律： b結(jié)合律：c關(guān)于邏輯與的分配律：d關(guān)于邏輯或的分配律：8十進(jìn)制下的無限循環(huán)小數(shù)（不包括循環(huán)節(jié)內(nèi)的數(shù)字均為0成均為9的平凡情況），在二進(jìn)制下有可能是（ ）。a無限循環(huán)小數(shù)(不包括循環(huán)節(jié)內(nèi)的數(shù)字均為0或均為9的平凡情）b無限不循環(huán)小數(shù)c有限小數(shù)d整數(shù)9（ ）是

7、目前互聯(lián)網(wǎng)上常用的e-mail服務(wù)協(xié)議。ahttp bftp cpop3 dsmtp10以下關(guān)于計(jì)算復(fù)雜度的說法中，正確的有（ ）。a如果一個問題不存在多項(xiàng)式時間的算法，那它一定是np類問題b如果一個問題不存在多項(xiàng)式時間的算法，那它一定不是p類問題c如果一個問題不存在多項(xiàng)式空間的算法，那它一定是np類問題d如果一個問題不存在多項(xiàng)式空間的算法，那它一定不是p類問題三、問題求解（共2題，每題5分，共計(jì)10分）1.本題中，我們約定布爾表達(dá)式只能包含p,q,r三個布爾變量，以及“與”（）、“或”（）、“非”（?）三種布爾運(yùn)算。如果無論p,q,r如何取值，兩個布爾表達(dá)式的值總是相同，則稱它們等價。例如，

8、(pq)r和p(qr)等價，p?p和q?q也等價；而pq和pq不等價。那么，兩兩不等價的布爾表達(dá)式最多有_個。2.對于一棵二叉樹，獨(dú)立集是指兩兩互不相鄰的節(jié)點(diǎn)構(gòu)成的集合。例如，圖1有5個不同的獨(dú)立集（1個雙點(diǎn)集合、3個單點(diǎn)集合、1個空集），圖2有14個不同的獨(dú)立集。那么，圖3有_個不同的獨(dú)立集。四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，其中第3題的2個小題各4分，共計(jì)32分）1. #includeusing namespace std;int n,i,temp,sum,a100;int main()cinn;for(i=1;iai;for(i=1;iai+1)temp=ai;ai=ai+1;ai+

9、1=temp;for(i=n;i=2;i-)if(aiai-1)temp=ai;ai=ai-1;ai-1=temp;sum=0;for(i=2;i=n-1;i+)sum+=ai;coutsum/(n-2)endl;return 0;輸入：840 70 50 70 20 40 10 30輸出：_2. #includeusing namespace std;int n,i,ans;int gcd(int a,int b)if(a%b=0)return b;elsereturn gcd(b,a%b);int main()cinn;ans=0;for(i=1;i=n;i+)if(gcd(n,i)=i)

10、ans+;coutansendl;輸入：120輸出：_3. #includeusing namespace std;const int size=20;int datasize;int n,i,h,ans;void merge()datah-1=datah-1+datah;h-;ans+;int main()cinn;h=1;datah=1;ans=0;for(i=2;i1&datah=datah-1)merge();coutansendl;（1）輸入：8輸出：_（4分）（2）輸入：2012輸出：_（4分）4. #include#includeusing namespace std;int l

11、efts20,rights20,father20;string s1,s2,s3;int n,ans;void calc(int x,int dep)ans=ans+dep*(s1x-a+1);if(leftsx=0)calc(leftsx,dep+1);if(rightsx=0)calc(rightsx,dep+1);void check(int x)if(leftsx=0)check(leftsx);s3=s3+s1x;if(rightsx=0)check(rightsx);void dfs(int x,int th)if(th=n)s3=;check(0);if(s3=s2)ans=0;

12、calc(0,1);coutans=0)dfs(fatherint main()cins1;cins2;n=s1.size()memset(lefts,memset(rightsmemset(fatherdfs(0,1);輸入：abcdefbcaedf輸出：_五、完善程序（第1題第2空3分，其余每空2.5分，共計(jì)28分）1.（排列數(shù)）輸入兩個正整數(shù)n,m(1n20,1mn)，在1n中任取m個數(shù)，按字典序從小到大輸出所有這樣的排列。例如輸入：3 2輸出：1 21 32 12 33 13 2#include#includeusing namespace std;const int size=25;

13、bool usedsize;int datasize;int n,m,i,j,k;bool flag;int main()cinnm;memset(used,false,sizeof(used);for(i=1;i=m;i+)datai=i;usedi=true;flag=true;while(flag)for(i=1;i=m-1;i+)coutdatai;coutdatam=1;i-) ;for(j=datai+1;j=n;j+)if(!usedj)usedj=true;datai= ;flag=true;break;if(flag)for(k=i+1;k=m;k+)for(j=1;j2是一

14、個固定的正整數(shù)，表示殼的厚度。小z還希望，每次操作，無論是壓入、彈出還是翻轉(zhuǎn)，都僅用與c無關(guān)的常數(shù)時間完成。聰明的你能幫助她編程實(shí)現(xiàn)“新殼?！眴?程序期望的實(shí)現(xiàn)效果如以下兩表所示。其中，輸入的第一行是正整數(shù)c，之后每行輸入都是一條指令。另外，如遇彈出操作時棧為空，或翻轉(zhuǎn)操作時棧中元素不足c個，應(yīng)當(dāng)輸出相應(yīng)的錯誤信息。指令涵義1空格e在棧頂壓入元素e2彈出（并輸出）棧頂元素3翻轉(zhuǎn)棧頂?shù)那癱個元素0退出表1：指令的涵義輸入輸出棧中的元素（左為棧底，右為棧頂）說明3輸入正整數(shù)c1 11壓入元素11 21 2壓入元素21 31 2 3壓入元素31 41 2 3 4壓入元素431 4 3 2翻轉(zhuǎn)棧頂?shù)那?/p>

15、c個元素1 51 4 3 2 5壓入元素531 4 5 2 3翻轉(zhuǎn)棧頂?shù)那癱個元素231 4 5 2彈出棧頂元素3221 4 5彈出棧頂元素 2251 4彈出棧頂元素 53錯誤信息1 4由于棧中元素不足c個，無法翻轉(zhuǎn)，故操作失敗，輸出錯誤信息241彈出棧頂元素421空彈出棧頂元素12錯誤信息空由于棧中元素不足c個，無法翻轉(zhuǎn)，故操作失敗，輸出錯誤信息0空退出表2：輸入輸出樣例#includeusing namespace std;const intnsize=100000,csize=1000;int n,c,r,tail,head,snsize,qcsize;/數(shù)組s模擬一個棧，n為棧的元素個

16、數(shù)/數(shù)組q模擬一個循環(huán)隊(duì)列，tail為隊(duì)尾的下標(biāo)，head為隊(duì)頭的下bool direction,empty;int previous(int k)if(direction)return(k+c-2)%c)+1;elsereturn(k%c)+1;int next(int k)if(direction) ;elsereturn(k+c-2)%c)+1;void push()int element;cinelement;if(next(head)=tail)n+; ;tail=next(tail);if(empty)empty=false;elsehead=next(head);=element;void pop()if(empty)couterror:the stack is empty!return;cout0)tail=previous(tail); =sn;n-;void reverse()int