noip2006提高組初賽試題C

1、1第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（提高組C+語言二小時(shí)完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案。1.在以下各項(xiàng)中。（）不是CP啲組成部分。A.控制器B.運(yùn)算器C.寄存器D. ALU E. RAM2.BIOS（基本輸入輸出系統(tǒng)）是一組固化在計(jì)算機(jī)內(nèi)（）上一個(gè)R0芯片上的程序。A.控制器B. CPU C.主板D.內(nèi)存條E.硬盤3.在下面各世界頂級的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域做出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（）A.沃爾夫獎(jiǎng)B.諾貝爾獎(jiǎng)C.菲爾茲獎(jiǎng)D.圖靈獎(jiǎng)E.南丁格爾獎(jiǎng)4.在編程時(shí)（使用

2、任一種高級語言，不一定是C+）如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組 （例如1000*1000的double型數(shù)組）按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循環(huán)是關(guān)于列的）相比，在輸入效率上（。A.沒有區(qū)別B.有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì)C.按行讀的方式要高一些D.按列讀的方式要高一些E.取決于數(shù)組的存儲方式。5.在C+中，表達(dá)式21A2的值是（）A. 441 B. 42 C.23 D.24 E.256.在C+中，判斷a不等于0且b不等于0的正確的條件表達(dá)式是（）A. !a=0 | !b=0 B. !（a=0） &（b=0） C. !（a=0&b=0）

3、D. a!=0 | b!=0 E. a & b7.某個(gè)車站呈狹長形，寬度只能容下一臺車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的出入記錄為“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”假設(shè)車輛入站的順 序?yàn)?,2,3,則車輛出站的順序?yàn)椋ā. 1,2, 3, 4, 5 B. 1,2, 4, 5, 7 C. 1,4, 3, 7, 6D. 1,4, 3, 7, 2 E. 1,4, 3, 7, 5&高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。 在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0,如果某個(gè)均衡的二

4、叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（。A. 10 B. 11 C. 12 D. 13 E. 210-19.與十進(jìn)制數(shù)1770.625對應(yīng)的八進(jìn)制數(shù)是（。A. 3352.5 B. 3350.5 C. 3352.1161D. 3350.1151 E.前4個(gè)答案都不對10.將5個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的排序。A. 6 B. 7 C. 8 D. 9 E. 10二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)大于或等于1。多 選或少選均不得分。11.設(shè)A=B=D=true, C=E=false，以下邏輯運(yùn)算表達(dá)式值為真的有（）

5、。A. (AAB)V(CAD)VE B.(AAB)VC)ADAE)C. AA(BVCVDVE) D. (AA(BVC)ADAE212. (2010)16+ (32)8的結(jié)果是(。A. (8234)ioB. (202A)16C. (0110)2D. (2042)1613.設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e依次入棧，以下出棧序列不可能出現(xiàn)的有()。A. a, b, c, e, d B. b, c, a, e, dC. a, e, c, b, d D. d, c, e, b, a14.已知6個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是1 2 3 4 5 6(數(shù)字為結(jié)點(diǎn)的編號，以下同)后根遍歷是3 2

6、 564 1，則該二叉樹的可能的中根遍歷是()A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 3 1 5 4 6 D. 2 3 1 4 6 515.在下列各數(shù)據(jù)庫系統(tǒng)軟件中，以關(guān)系型數(shù)據(jù)庫為主體結(jié)構(gòu)的是(。A. ACCESS B. SQL ServerC. Oracle D. Foxpro16.在下列各軟件中，屬于NOIF競賽(復(fù)賽)推薦使用的語言環(huán)境有(。A. gcc/g+ B. Turbo PascalC. Turbo C D. free pascal17.以下斷電之后將不能保存數(shù)據(jù)的有()。A.硬盤B. ROM C.顯存D. RAM18.在下列關(guān)于計(jì)算機(jī)語言的說法中，

7、正確的有()。A.Pascal和C都是編譯執(zhí)行的高級語言B.高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C.C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D.高級語言比匯編語言更高級，是因?yàn)樗某绦虻倪\(yùn)行效率更高19.在下列關(guān)于計(jì)算機(jī)算法的說法中，正確的有()。A.一個(gè)正確的算法至少要有一個(gè)輸入B.算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步C.判斷一個(gè)算法的好壞，主要依據(jù)它在某臺計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間D.目前仍然存在許多涉及到國計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法20.在下列關(guān)于青少年信息學(xué)競賽的說法中，你贊成的是()(本題不回答為0分，答

8、題一律滿分)。A.舉行信息學(xué)競賽的目的，是為了帶動(dòng)廣大青少年學(xué)科學(xué)、愛科學(xué)，為造就一大批優(yōu)秀的計(jì)算機(jī)科學(xué)與 技術(shù)人才奠定良好的基礎(chǔ)B.如果競賽優(yōu)勝者不能直接保送上大學(xué)，我今后就不再參與這項(xiàng)活動(dòng)了C.準(zhǔn)備競賽無非要靠題海戰(zhàn)術(shù)，為了取得好成績，就得拼時(shí)間、拼體力D.為了取得好成績，不光要看智力因素，還要看非智力因素。優(yōu)秀選手應(yīng)該有堅(jiān)韌不拔的意志，有嚴(yán) 謹(jǐn)求實(shí)的作風(fēng)，既要努力奮進(jìn)，又要?jiǎng)俨或湐〔火H三問題求解(共2題，每題5分，共計(jì)10分)1將2006個(gè)人分成若干不相交的子集，每個(gè)子集至少有3個(gè)人，并且：(1)在每個(gè)子集中，沒有人認(rèn)識該子集的所有人。(2)同一子集的任何3個(gè)人中，至少有2個(gè)人互不認(rèn)識。

9、(3)對同一子集中任何2個(gè)不相識的人，在該子集中恰好只有1個(gè)人認(rèn)識這兩個(gè)人。則滿足上述條件 的子集最多能有個(gè)？2將邊長為n的正三角形每邊n等分，過每個(gè)分點(diǎn)分別做另外兩邊的平行線，得到若干個(gè)正三角形, 我們稱為小3三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最 下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上（圖中是n=5時(shí)一條通路的例 子）設(shè)n=10,則該正三角形的不同的通路的總數(shù)為_。四閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)1. #in elude

10、 void mai n()int i,u4,v4,x,y=10;for(i=0;iui;v0=(u0+u1+u2+u3)/7;v1=u0/(u1-u2)/u3);v2=u0*u1/u2*u3; v3=v0*v1;x=(v0+v1+2)-u(v3+3)%4;if(x10)y+= (v2*100-v3)/(uu0%3*5);elsey+=20+(v2*100-v3)/(uv0%3*5);cout x,ye ndl; /本例中，給定的輸入數(shù)據(jù)可以避免分母為0或下標(biāo)越界。輸入：9 3 9 4輸出：_2. # in clude void mai n()int i,j,m=2,3,5,7,13;long

11、t;for (i=0;i=4;i+)t=1;for(j=1;jmi;j+) t*=2;cout (t*2-1)*t;cout e ndl;輸出:_3. #in clude iostream.h4#defi ne N 7int fun 1(char s,char a,i nt n)int j;j=n;while(a0) j-;return j;int fun 2(char s,char a,i nt n)int j；j=1；while(asj & j=n) j+;return j;void mai n()char sN+1;int k,p; for(k=1;k=N;k+) sk=A+2*

12、k+1; p=fun1(s,M,N);cout p+fu n2(s,M,N)e ndl;輸出：_4.#in clude #i nclude void digit(l ong n,long m)if(m0)cout setw(2)1)digit (n/10,m/10);cout setw(2) n%10;void mai n()long x,x2;cout I nput a nu mber: x;x2=1;while(x2x) x2*=10;x2/=10; digit(x,x2); cout e ndl;輸入：9734526輸出：_五.完善程序(前5空，每空2分，后6空，每空3分，共28分)1.

13、(選排列)下面程序的功能是利用遞歸方法生成從1到n(n10)的n個(gè)數(shù)中取k(1=k=n)個(gè)數(shù)的全 部可能的排列(不一定按升序輸出。例如，當(dāng)n=3,k=2時(shí)，應(yīng)該輸出(每行輸出5個(gè)排列)12 13 21 23 32531程序：#in clude #i nclude int n ,k,a10;long coun t=0;void perm2(i nt j)int i,p,t;if()for(i=k;i=n;i+)count+;t=ak; ak=ai; ai=t;for()coutsetw(1)ap;cout ; t=ak;ak=ai;ai=t; if(count%5=0) cout endl;re

14、turn;for(i=j;i=n;i+)t=aj;aj=ai;ai=t;3;t=aj;void main()int i;cout nEntry n,k (k=n)nnk;for(i=1;i=n;i+) ai=i;cout 4-2-1-5-3。遺傳算法的核心是通過兩個(gè)個(gè)體的交叉操作，產(chǎn)生兩 個(gè) 新的個(gè)體。下面的程序給出了最簡單的一種交叉算法。具體過程如下：(1) 選定中間一段作為互換段，該段的起止下標(biāo)為t1，t2，隨機(jī)生成t1，t2后，互換兩段。(2) 互換后，在每個(gè)新的排列中可能有重復(fù)數(shù)字，因而不能作為新個(gè)體的編碼，一般再做兩步處理：(2.1)將兩個(gè)互換段中，共同的數(shù)字標(biāo)記為0，表示已處理完。

15、(2.2)將兩個(gè)互換段中其余數(shù)字標(biāo)記為1，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。例如：n=12,兩 個(gè)個(gè)體分別是：6a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9t1=5，t2=8。上述每一行中，兩個(gè)星號間的部分為互換段。假定數(shù)組的下標(biāo)從1開始，互換后有：a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9然后， 將數(shù)字6,7對應(yīng)的項(xiàng)標(biāo)記為0， 星號內(nèi)數(shù)字2,9,10,11對應(yīng)的項(xiàng)標(biāo)記為1， 并且按順序?qū)?應(yīng)關(guān) 系為:102

16、，119。于是，將a19=10替換為a19=2，將a22=2替換為a22=10， 類似再做 第2組替換。這樣處理后，就得到了兩個(gè)新個(gè)體：a1: 1 3 5 4 6 7 10 11 2 12 8 9a2: 3 10 1 12 2 6 7 9 8 5 4 11(3)輸出兩個(gè)新個(gè)體的編碼。 程序：#include #include #define N 20int a1N,a2N,kz1N,kz2N,n;int rand1(int k)int t=0;while(tk) t=(int)(double)rand()/RAND_MAX*k); return t;void read1(int a,int m

17、)讀入數(shù)組元素a1至am，a0=0，略。void wrt1(int a,int m)輸出數(shù)組元素a1至am，略。 void cross(int a1, int a2,int t1, int t2, int n) int i,j,t,kj;for(i=t1; i=t2; i+) t=a1i; ； for(i=1;i=n;i+) if(it2) kz1i=kz2i=-1;else;for(i=t1;i=t2;i+) for(j=t1;j=t2;j+) if(a1i=a2j); break;for(i=t1; i=t2; i+) if(kz1i=1) for(j=t1;j=t2;j+) if(kz2

18、j=1) kj=j; break; for(j=1;j=n;j+) if()a1j=a2kj;break;for(j=1;j=n;j+) if() a2j=a1i; break;kz1i=kz2kj=0;void main()int k,t1,t2;cout 5):n;cout input array 1 (n numbers):endl; read1(a1,n); cout input array 2 (nnumbers):t2)k=t1; t1=t2; t2=k;wrt1(a1,n); wrt1(a2,n);8提高組（C+語言）參考答案與評分標(biāo)準(zhǔn)一、單項(xiàng)選擇題： （每題1.5分）E 2. C 3. D 4. E 5. C 6. E 7. C 8. B 9. A 10. B二、不定項(xiàng)選擇題： （每題1.5分）11. ABC 12. AB 13. C 14. BC 15. ABCD16. AD 17. CD 18.AB 19. BD 20.（滿分，空白0分）三、問題求解： （每題5分）401 2.