NOI精編普及組C++題目及答案

第十二屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 2006（普及組 C++語(yǔ)言二小時(shí)完成）●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無(wú)效●●一、單項(xiàng)選擇題（共 20題，每題 1.5分，共計(jì) 30分。每題有且僅有一個(gè)正確答案 .）在下面各世界頂級(jí)的獎(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)在下列各軟件中，不屬于NOIP競(jìng)賽（復(fù)賽）推薦使用的語(yǔ)言環(huán)境有（）。A.gcc/g++ B.TurboPascalC.RHIDE D.freepascal以下斷電之后仍能保存數(shù)據(jù)的有（）。A.寄存器 B.ROM C.RAM4．Linux是一種()。

D.高速緩存A.繪圖軟件B.程序設(shè)計(jì)語(yǔ)言 C.操作系統(tǒng) D.網(wǎng)絡(luò)瀏覽器5.CPU是()的簡(jiǎn)稱。A.硬盤B.中央處理器 C.高級(jí)程序語(yǔ)言 D.核心寄存器在計(jì)算機(jī)中，防火墻的作用是（）。A.防止火災(zāi)蔓延 B.防止網(wǎng)絡(luò)攻擊C.防止計(jì)算機(jī)死機(jī) D.防止使用者誤刪除數(shù)據(jù)在下列關(guān)于計(jì)算機(jī)語(yǔ)言的說法中，不正確的是（）。A.Pascal 和C都是編譯執(zhí)行的高級(jí)語(yǔ)言高級(jí)語(yǔ)言程序比匯編語(yǔ)言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C.C++是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言與匯編語(yǔ)言相比，高級(jí)語(yǔ)言程序更容易閱讀在下列關(guān)于計(jì)算機(jī)算法的說法中，不正確的是（）。一個(gè)正確的算法至少要有一個(gè)輸入算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性目前仍然存在許多涉及到國(guó)計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法在下列各種排序算法中，不是以“比較”作為主要操作的算法是（）。A.選擇排序B.冒泡排序C.插入排序D.基數(shù)排序10．在編程時(shí)（使用任一種高級(jí)語(yǔ)言，不一定是C++），如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組（例如1000*1000的double型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循環(huán)是關(guān)于列的）相比，在輸入效率上（）。A.沒有區(qū)別 B.按行讀的方式要高一些C.按列讀的方式要高一些 D.取決于數(shù)組的存儲(chǔ)方式。11．在C++中，表達(dá)式 21^2的值是（）A.441 B.42 C.23 D.2412．在C++中，判斷 a不等于0且b不等于0的正確的條件表達(dá)式是（）A.!a==0||!b==0

B.!((a==0)&&(b==0))C.!(a==0&&b==0)D.a&&b13．某個(gè)車站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車，并且只有一個(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)椋ǎ?/p>

,出”。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,214．高度為 n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（）。與十進(jìn)制數(shù)1770對(duì)應(yīng)的八進(jìn)制數(shù)是（）。16．將5個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的排序。設(shè)A=B=D=true，C=false，以下邏輯運(yùn)算表達(dá)式值為真的有（）。A.(A∧B)∨(C∧D)B.((A∨B∨D)∧C)C.A∧(B∨C∨D)D.(A∧B∧C) D18.(2010) +(32) 的結(jié)果是（）。16 8A.(8234) B.(202B) C.(20056)10 16 82設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有（）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a已知6個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是123456（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是325641，則該二叉樹的可能的中根遍歷是（）A.321465

B.321546C.213546

D.231465二．問題求解（共 2題，每題 5分，共計(jì) 10分）1．（尋找假幣） 現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第 1次的稱重方法。請(qǐng)寫出你的結(jié)果： _________________________________________________。2．（取石子游戲） 現(xiàn)有5堆石子,石子數(shù)依次為 3，5，7，19，50，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢?，不能不?。?,取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無(wú)論乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫出你的結(jié)果：_________________________________________________

。三．閱讀程序?qū)懡Y(jié)果（共

4題，每題

8分，共計(jì)

32分）1.#include<iostream.h>voidmain(){inti,u[4],a,b,x,y=10;for(i=0;i<=3;i++)cin>>u[i];a=(u[0]+u[1]+u[2]+u[3])/7;b=u[0]/((u[1]-u[2])/u[3]);x=(u[0]+a+2)-u[(u[3]+3)%4];if(x>10)y+=(b*100-u[3])/(u[u[0]%3]*5);elsey+=20+(b*100-u[3])/(u[u[0]%3]*5);cout<<x<<","<<y<<endl;}// 注：本例中，給定的輸入數(shù)據(jù)可以避免分母為輸入：9394輸出：_______________

0或下標(biāo)越界。2.#include<iostream.h>voidmain(){inti,j,m[]={2,3,5,7,13};longt;for(i=0;i<=4;i++){t=1;for(j=1;j<m[i];j++)t*=2;cout<<(t*2-1)*t<<"";}cout<<endl;}輸出:____________________3.#include"iostream.h"#defineN7intfun(chars[],chara,intn){intj;j=n;while(a<s[j]&&j>0)j--;returnj;}voidmain(){chars[N+1];intk;for(k=1;k<=N;k++)s[k]='A'+2*k+1;cout<<fun(s,'M',N)<<endl;}輸出：_____________4.#include<iostream.h>#include<iomanip.h>voiddigit(longn,longm){if(m>0)cout<<setw(2)<<n%10;if(m>1)digit(n/10,m/10);cout<<setw(2)<<n%10;}voidmain(){longx,x2;cout<<"Inputanumber:"<<endl;cin>>x;x2=1;while(x2<x)x2*=10;x2/=10;digit(x,x2);cout<<endl;}輸入：9734526輸出：______________________________四．完善程序(前4空，每空 2.5分，后6空，每空3分，共28分)1．（全排列）下面程序的功能是利用遞歸方法生成從 1到n(n<10)的n個(gè)數(shù)的全部可能的排列（不一定按升序輸出）。例如，輸入 3，則應(yīng)該輸出（每行輸出 5個(gè)排列）：312程序：#include<iostream.h>#include<iomanip.h>intn,a[10];//a[1],a[2],?,a[n]構(gòu)成n個(gè)數(shù)的一個(gè)排列l(wèi)ongcount=0;//變量count記錄不同排列的個(gè)數(shù)，這里用于控制換行voidperm(intk){intj,p,t;if( ①){count++;for(p=1;p<=n;p++)cout<<setw(1)<<a[p];cout<<"";if( ②)cout<<endl;return;}for(j=k;j<=n;j++){t=a[k];a[k]=a[j];a[j]=t;;t=a[k]; ④;}}voidmain(){inti;cout<<"Entryn:"<<endl;cin>>n;for(i=1;i<=n;i++)a[i]=i;⑤;}2.由鍵盤輸入一 個(gè)奇數(shù) P(P<100,000,000) ，其個(gè)位數(shù)字不 是 5，求一個(gè)整 數(shù) S，使S=1111...1( 在給定的條件下，解 S必存在)。要求在屏幕上依次輸出以下結(jié)果 :（1）S的全部數(shù)字。除最后一行外，每行輸出 50位數(shù)字。（2）乘積的數(shù)字位數(shù)。

P×例1：輸入p=13，由于13*8547=111111，則應(yīng)輸出（1）8547，（2）6例2：輸入p=147，則輸出結(jié)果應(yīng)為（1）2）42，即等式的右端有42個(gè)1。程序：#include<iostream.h>#include<iomanip.h>voidmain(){longp,a,b,c,t,n;while(1){cout<<" 輸入p,最后一位為 1或3或7或9:"<<endl;cin>>p;if((p%2!=0)&&(p%5!=0))// 如果輸入的數(shù)符合要求，結(jié)束循環(huán);}a=0;n=0;while(a<p){ a=a*10+1;n++;// 變量a存放部分右端項(xiàng)， n為右端項(xiàng)的位數(shù)}t=0;do{b=a/p;cout<<setw(1)<<b;t++;if( ⑦)cout<<endl;c=⑧;a=⑨;n++;}while(c>0);cout<<endl<<"n="<< ⑩<<endl;}參考答案一． 選擇題DBBCBBCADDCDCBCBBACB二． 問題解答4次（1分）第一步：分成 3組：27，27，26，將前兩組放在天平上（ 4分）有獲勝策略(1?分)，第?1?次在第?5?堆中取?32?顆石子(4?分)，。三．閱讀程序10，10（對(duì)1個(gè)數(shù)給4分，無(wú)逗號(hào)扣1分）???（前?2?個(gè)對(duì)?1?個(gè)數(shù)給?1?分，后?3?個(gè)對(duì)?1?個(gè)數(shù)給?2?分）54