第十二屆全國青少年信息學奧林匹克聯賽初賽試題 2006（普及組 C++語言二小時完成）●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●一、單項選擇題（共 20題，每題 1.5分，共計 30分。每題有且僅有一個正確答案 .）在下面各世界頂級的獎項中，為計算機科學與技術領域做出杰出貢獻的科學家設立的獎項是（）。A.沃爾夫獎B.諾貝爾獎C.菲爾茲獎D.圖靈獎在下列各軟件中，不屬于NOIP競賽（復賽）推薦使用的語言環境有（）。A.gcc/g++ B.TurboPascalC.RHIDE D.freepascal以下斷電之后仍能保存數據的有（）。A.寄存器 B.ROM C.RAM4．Linux是一種()。

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

B.!((a==0)&&(b==0))C.!(a==0&&b==0)D.a&&b13．某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態為空，從這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出假設車輛入站的順序為1，2，3，??，則車輛出站的順序為（）。

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

B.321546C.213546

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

。三．閱讀程序寫結果（共

4題，每題

8分，共計

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;}// 注：本例中，給定的輸入數據可以避免分母為輸入：9394輸出：_______________

0或下標越界。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個數的全部可能的排列（不一定按升序輸出）。例如，輸入 3，則應該輸出（每行輸出 5個排列）：312程序：#include<iostream.h>#include<iomanip.h>intn,a[10];//a[1],a[2],?,a[n]構成n個數的一個排列longcount=0;//變量count記錄不同排列的個數，這里用于控制換行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.由鍵盤輸入一 個奇數 P(P<100,000,000) ，其個位數字不 是 5，求一個整 數 S，使S=1111...1( 在給定的條件下，解 S必存在)。要求在屏幕上依次輸出以下結果 :（1）S的全部數字。除最后一行外，每行輸出 50位數字。（2）乘積的數字位數。

P×例1：輸入p=13，由于13*8547=111111，則應輸出（1）8547，（2）6例2：輸入p=147，則輸出結果應為（1）2）42，即等式的右端有42個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))// 如果輸入的數符合要求，結束循環;}a=0;n=0;while(a<p){ a=a*10+1;n++;// 變量a存放部分右端項， n為右端項的位數}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（對1個數給4分，無逗號扣1分）???（前?2?個對?1?個數給?1?分，后?3?個對?1?個數給?2?分）54