第十六屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

CCFCCFNOIP2010初賽普及組C++PAGE4第十六屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（普及組C++語(yǔ)言兩小時(shí)完成）●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確選項(xiàng)。）1．2E+03表示（）。A.2.03B.5C.8D.20002．一個(gè)字節(jié)（byte）由（）個(gè)二進(jìn)制位組成。A.8B.16C.32D.3．以下邏輯表達(dá)式的值恒為真的是（）。A.P∨(?P∧Q)∨(?P∧?Q)B.Q∨(?P∧Q)∨(P∧?Q)C.P∨Q∨(P∧?Q)∨(?P∧Q)D.P∨?Q∨(P∧?Q)∨(?P∧?Q)4．Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名為（）。A.exeB.comC.dllD.以上都不是5．如果樹根算第1層，那么一棵n層的二叉樹最多有（）個(gè)結(jié)點(diǎn)。A.2n-1B.2nC.2n+1D.2n+16．提出“存儲(chǔ)程序”的計(jì)算機(jī)工作原理的是（）。A.克勞德·香農(nóng)B.戈登·摩爾C.查爾斯·巴比奇D.馮·諾依曼7．設(shè)X、Y、Z分別代表三進(jìn)制下的一位數(shù)字，若等式XY+ZX=XYX在三進(jìn)制下成立，那么同樣在三進(jìn)制下，等式XY*ZX=（）也成立。A.YXZB.ZXYC.XYZD.XZY8．Pascal語(yǔ)言、C語(yǔ)言和C++語(yǔ)言都屬于（）。A.面向?qū)ο笳Z(yǔ)言B.腳本語(yǔ)言C.解釋性語(yǔ)言D.編譯性語(yǔ)言9．前綴表達(dá)式“+3*2+512”的值是（A.23B.25C.37D.6510．主存儲(chǔ)器的存取速度比中央處理器（CPU）的工作速度慢得多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問的存儲(chǔ)單元通常都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了（）。A.寄存器B.高速緩存C.閃存D.外存11．一個(gè)字長(zhǎng)為8位的整數(shù)的補(bǔ)碼是11111001，則它的原碼是（）。A.00000111B.01111001C.11111001D.12．基于比較的排序時(shí)間復(fù)雜度的下限是（），其中n表示待排序的元素個(gè)數(shù)。A.Θ(n)B.Θ(nlogn)C.Θ(logn)D.Θ(n2)13．一個(gè)自然數(shù)在十進(jìn)制下有n位，則它在二進(jìn)制下的位數(shù)與（）最接近。A.5nB.n*log210C.10*log2nD.10nlog214．在下列HTML語(yǔ)句中，可以正確產(chǎn)生一個(gè)指向NOI官方網(wǎng)站的超鏈接的是（）。A.<aurl="">歡迎訪問NOI網(wǎng)站</a>B.<ahref="">歡迎訪問NOI網(wǎng)站</a>C.<a></a>D.<aname="">歡迎訪問NOI網(wǎng)站</a>15．元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第1個(gè)出棧的是R3，那么第5個(gè)出棧的不可能是（）。A.R1B.R2C.R4D.R16．雙向鏈表中有兩個(gè)指針域llink和rlink，分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均非空?，F(xiàn)要求刪除結(jié)點(diǎn)p，則下面語(yǔ)句序列中錯(cuò)誤的是（）。A.p->rlink->llink=p->rlink;p->llink->rlink=p->llink;deletep;B.p->llink->rlink=p->rlink;p->rlink->llink=p->llink;deletep;C.p->rlink->llink=p->llink;p->rlink->llink->rlink=p->rlink;deletep;D.p->llink->rlink=p->rlink;p->llink->rlink->llink=p->llink;deletep;17．一棵二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是（）。輸入：9122077輸出：_________2．#include<iostream>usingnamespacestd;intrSum(intj){intsum=0;while(j!=0){sum=sum*10+(j%10);j=j/10;}returnsum;}intmain(){intn,m,i;cin>>n>>m;for(i=n;i<m;i++)if(i==rSum(i))cout<<i<<'';return0;}輸入：90120輸出：_________3．#include<iostream>#include<string>usingnamespacestd;intmain(){strings;charm1,m2;inti;getline(cin,s);m1='';m2='';for(i=0;i<s.length();i++)if(s[i]>m1){m2=m1;m1=s[i];}elseif(s[i]>m2)m2=s[i];cout<<int(m1)<<''<<int(m2)<<endl;return0;}輸入：Expo2010ShanghaiChina輸出：_________提示：字符空格'0''A''a'ASCII碼324865974．#include<iostream>usingnamespacestd;constintNUM=5;intr(intn){inti;if(n<=NUM)returnn;for(i=1;i<=NUM;i++)if(r(n-i)<0)returni;return-1;}intmain(){intn;cin>>n;cout<<r(n)<<endl;return0;}（1）輸入：7輸出：_________（4分）（2）輸入：16輸出：_________（4分）四、完善程序（前4空，每空2.5分，后6空，每空3分，共計(jì)28分）1．（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)之和。迄今為止，這仍然是一個(gè)著名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。試編寫程序，驗(yàn)證任一大于2且不超過n的偶數(shù)都能寫成兩個(gè)質(zhì)數(shù)之和。#include<iostream>usingnamespacestd;intmain(){constintSIZE=1000;intn,r,p[SIZE],i,j,k,ans;booltmp;cin>>n;r=1;p[1]=2;for(i=3;i<=n;i++){①;for(j=1;j<=r;j++)if(i%②==0){tmp=false;break;}if(tmp){r++;③;}}ans=0;for(i=2;i<=n/2;i++){tmp=false;for(j=1;j<=r;j++)for(k=j;k<=r;k++)if(i+i==④){tmp=true;break;}if(tmp)ans++;}cout<<ans<<endl;return0;}若輸入n為2010，則輸出⑤時(shí)表示驗(yàn)證成功，即大于2且不超過2010的偶數(shù)都滿足哥德巴赫猜想。2．（過河問題）在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過唯一的一根獨(dú)木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時(shí)必須借助燈光來照明，很不幸的是，他們只有一盞燈。另外，獨(dú)木橋上最多承受兩個(gè)人同時(shí)經(jīng)過，否則將會(huì)坍塌。每個(gè)人單獨(dú)過橋都需要一定的時(shí)間，不同的人需要的時(shí)間可能不同。兩個(gè)人一起過橋時(shí)，由于只有一盞燈，所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過橋時(shí)所花的時(shí)間?，F(xiàn)輸入n（2≤n<100）和這n個(gè)人單獨(dú)過橋時(shí)需要的時(shí)間，請(qǐng)計(jì)算總共最少需要多少時(shí)間，他們才能全部到達(dá)河的左岸。例如，有3個(gè)人甲、乙、丙，他們單獨(dú)過橋的時(shí)間分別為1、2、4，則總共最少需要的時(shí)間為7。具體方法是：甲、乙一起過橋到河的左岸，甲單獨(dú)回到河的右岸將燈帶回，然后甲、丙再一起過橋到河的左岸，總時(shí)間為2+1+4=7。#include<iostream>usingnamespacestd;constintSIZE=100;constintINFINITY=10000;constboolLEFT=true;constboolRIGHT=false;constboolLEFT_TO_RIGHT=true;constboolRIGHT_TO_LEFT=false;intn,hour[SIZE];boolpos[SIZE];intmax(inta,intb){if(a>b)returna;elsereturnb;}intgo(boolstage){inti,j,num,tmp,ans;if(stage==RIGHT_TO_LEFT){num=0;ans=0;for(i=1;i<=n;i++)if(pos[i]==RIGHT){num++;if(hour[i]>ans)ans=hour[i];}if(①)returnans;ans=INFINITY;for(i=1;i<=n-1;i++)if(pos[i]==RIGHT)for(j=i+1;j<=n;j++)if(pos[j]==RIGHT){pos[i]=LEFT;pos[j]=LEFT;tmp=max(hour[i],hour[j])+②;if(tmp<ans)