noip2006提高組初賽試題C

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

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

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

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

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個結(jié)點的二叉樹的先根遍歷是1 2 3 4 5 6(數(shù)字為結(jié)點的編號，以下同)后根遍歷是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競賽(復賽)推薦使用的語言環(huán)境有(。A. gcc/g+ B. Turbo PascalC. Turbo C D. free pascal17.以下斷電之后將不能保存數(shù)據(jù)的有()。A.硬盤B. ROM C.顯存D. RAM18.在下列關(guān)于計算機語言的說法中，

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

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

9、(3)對同一子集中任何2個不相識的人，在該子集中恰好只有1個人認識這兩個人。則滿足上述條件 的子集最多能有個？2將邊長為n的正三角形每邊n等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形, 我們稱為小3三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是最 下面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位于同一行或下一行的小三角形，并且每個小三角形不能經(jīng)過兩次或兩次以上（圖中是n=5時一條通路的例 子）設(shè)n=10,則該正三角形的不同的通路的總數(shù)為_。四閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計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或下標越界。輸入：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個數(shù)中取k(1=k=n)個數(shù)的全 部可能的排列(不一定按升序輸出。例如，當n=3,k=2時，應(yīng)該輸出(每行輸出5個排列)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。遺傳算法的核心是通過兩個個體的交叉操作，產(chǎn)生兩 個 新的個體。下面的程序給出了最簡單的一種交叉算法。具體過程如下：(1) 選定中間一段作為互換段，該段的起止下標為t1，t2，隨機生成t1，t2后，互換兩段。(2) 互換后，在每個新的排列中可能有重復數(shù)字，因而不能作為新個體的編碼，一般再做兩步處理：(2.1)將兩個互換段中，共同的數(shù)字標記為0，表示已處理完。

15、(2.2)將兩個互換段中其余數(shù)字標記為1，按順序?qū)⒒Q段外重復的數(shù)字進行替換。例如：n=12,兩 個個體分別是：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。上述每一行中，兩個星號間的部分為互換段。假定數(shù)組的下標從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)的項標記為0， 星號內(nèi)數(shù)字2,9,10,11對應(yīng)的項標記為1， 并且按順序?qū)?應(yīng)關(guān) 系為:102

16、，119。于是，將a19=10替換為a19=2，將a22=2替換為a22=10， 類似再做 第2組替換。這樣處理后，就得到了兩個新個體：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)輸出兩個新個體的編碼。 程序：#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+語言）參考答案與評分標準一、單項選擇題： （每題1.5分）E 2. C 3. D 4. E 5. C 6. E 7. C 8. B 9. A 10. B二、不定項選擇題： （每題1.5分）11. ABC 12. AB 13. C 14. BC 15. ABCD16. AD 17. CD 18.AB 19. BD 20.（滿分，空白0分）三、問題求解： （每題5分）401 2.