第十二屆全國青少年信息學奧林匹克聯賽初賽試題及答案（普及組、C語言）普及組??C語言??二小時完成)
一、單項選擇題(共20題，每題1.5分，共計30分。
每題有且僅有一個正確答案)1．在下面各世界頂級的獎項中，為計算機科學與技術領域做出杰出貢獻的科學家設立的獎項是()。
A．沃爾夫獎????B．諾貝爾獎????C．菲爾茲獎????D．圖靈獎
2．在下面各軟件中，不屬于NOIP競賽(復賽)推薦使用的語言環境是()。
A．gcc/g++????B．Turbo
Pascal????C．RHIDE????D．free
pascal
3．以下斷電之后仍能保存數據的有()。
A．寄存器????B．ROM????C．RAM????D．高速緩存
4．Linux是一種()。
A．繪圖軟件????B．程序設計語言????C．操作系統????D．網絡瀏覽器
5．CPU是()的簡稱。
A．硬盤????B．中央處理器????C．高級程序語言????D．核心寄存器
6．在計算機中，防火墻的作用是()。
A．防止火災蔓延????B．防止網絡攻擊????C．防止計算機死機????D．防止使用者誤刪除數據
7．在下列關于計算機語言的說法中，不正確的是()。
A．Pascal和C都是編譯執行的高級語言
B．高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上
C．C++是歷史上的第一個支持面向對象的計算機語言
D．與匯編語言相比，高級語言程序更容易閱讀
8．在下列關于計算機算法的說法中，不正確的是()。
A．一個正確的算法至少要有一個輸入
B．算法的改進，在很大程度上推進了計算機科學與技術的進步
C．判斷一個算法的好壞的主要標準是算法的時間復雜性與空間復雜性
D．目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法
9．在下列各種排序算法中，不是以“比較”作為主要操作的算法是()。
A．選擇排序????B．冒泡排序????C．插入排序????D．基數排序
10．在編程時(使用任一種高級語言，不一定是C)，如果需要從磁盤文件中輸入一個很大的二維數組(例如1000*1000的double型數組)，按行讀(即外層循環是關于行的)與按列讀(即外層循環是關于列的)相比，在輸入效率上()。
A．沒有區別????????????????B．按行讀的方式要高一些
C．按列讀的方式要高一些????D．取決于數組的存儲方式
11．在C語言中，表達式21^2的值是()。
A．441????B．42????C．23????D．24
12．在C語言中，判斷a不等于0且b不等于0的正確的條件表達式是()。
A．！a==0
||
!b==0????B．!(a==0)&&(b==0)C．!(a==0&&b==0)D．a&&b
13．某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態為空，從這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出，出”。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為()。
A．1，2，3，4，5????B．1，2，4，5，7????C．1，4，3，7，6????D．1，4，3，7，2
14．高度為n的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹。在這里，樹高等于結點的最大深度，根結點的深度為0，如果某個均衡的二叉樹共有2381個結點，則該樹的樹高為()。
A．10????B．11????C．12????D．13
15．與十進制數1770對應的八進制數是()。
A．3350????B．3351????C．3352????D．3540
16．將5個數的序列排序，不論原先的順序如何，最少都可以通過()次比較。完成從小到大的排序。
A．6????B．7????C．8????D．9
17．設A=B=D=ture，C=false，以下邏輯運算表達式值為真的有()。
A．(﹁A∧B)∨(C∧D)B．﹁((A∨B∨D)∧C)C．﹁A∧(B∨C∨D)D．(A∧B∧C)∨﹁D
18．(2010)16+(32)8的結果是()。
A．(8234)10????B．(202B)16????C．(20056)8????D．(100000000110)2
19．設棧S的初始狀態為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現的有()。
A．a,b,c,e,d????B．b,c,a,e,d????C．a,e,c,b,d????D．d,c,e,b,a
20．已知6個結點的二叉樹的先根+遍歷是1
6(數字為結點的編號，以下同)，后根遍歷是3
1，則該二叉樹的可能的中根遍歷是()。
A．3
5????B．3
6????C．2
6????D．2
二、問題求解(共2題，每題5分，共計10分)
1．(尋找假幣)現有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第1次的稱重方法。請寫出你的結果：________________________________________________________________。
2．(取石子游戲)現有5堆石子，石子數依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任取(每次只能取自一堆，不能不取)，取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略(即無論乙怎樣取，甲只要不失誤，都能獲勝)？如果有，甲第一步應該在哪一堆里取多少？請寫出你的結果：____________________________________________________________________。
三、閱讀程序寫結果(共4題，每題8分，共計32分)
1.#include
int
main()
{
int
i,u[4],a,b,x,y=10;
for(i=0;i<=3;i++)
scanf(“%d“,&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);
else
y+=20+(b*100-u[3])/(u[u[0]%3]*5);
printf(“%d,%d＼n“,x,y);
return
0;
}
/*注：本例中，給定的輸入數據可以避免分母為0或下標越界。*/
輸入：9??3??9??4
輸出：________________
2.#include
main()
{
int
i,j,m[]={2,3,5,7,13};
long
t;
for(i=0;i<=4;i++)
{
t=1;
for(j=1;j t*=2; printf(“%ld??“,(t*2-1)*t); } printf(“＼n“); } 輸出：________________ 3.#include “stdio.h“ #define N int fun(char s[],char a,int n) { int j; j=n; while(a && j>0) j--; return j; } int main() { char s[N+1]; int k,p; for(k=1;k<=N;k++) s[k]=＇A＇+2*k+1; printf(“%d＼n“,fun(s,＇M＇,N)); } 輸出：________________ 4.#include void digit(long n,long m) { if(m>0) printf(“%2ld“,n%10); if(m>1) digit(n/10,m/10); printf(“%2ld“,n%10); } main() { long x,x2; printf(“Input a number:＼n“); scanf(“%ld“,&x); x2=1; while(x2 x2*=10; x2/=10; digit(x,x2); printf(“＼n“); } 輸入：9734526 輸出：________________ 四、完善程序(前4空，每空2.5分，后6空，每空3分，共28分) 1．(全排列)下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個數的全部可能的排列(不一定按升序輸出)。例如，輸入3，則應該輸出(每行輸出5個排列)： 123??132??213??231??321 312 程序： #include int n,a[10];/*a[1],a[2],…,a[n]構成n個數的一個排列*/ long count=0;/*變量count記錄不同排列的個數，這里用于控制換行*/ void perm(int k) { int j,p,t; if(______①______) { count++; for(p=1;p<=n;p++) printf(“%1d“,a[p]);/* “%1d“?中是數字1，不是字母l */ printf(“ “); if(______②______) printf(“＼n“); return; } for(j=k;j<=n;j++) { t=a[k]; a[k]=a[j];a[j]=t; ______③______; t=a[k]; ______④______; } } main() { int i; printf(“Entry n:＼n“); scanf(“%d“,&n); for(i=1;i<=n;i++) a[i]=i; ______⑤______; } 2.由鍵盤輸入一個奇數P(P<100,000,000)，其個位數字不是5，求一個整數S，使P×S=1111...1(在給定的條件下，解s必存在)。要求在屏幕上依次輸出以下結果： (1) S的全部數字。除最后一行外，每行輸出50位數字。(2)乘積的數字位數。 例1：輸入P=13，由于13*8547=111111，則應輸出(1) 8547，(2) 例2：輸入P=147，則輸出結果應為(1) 7558578987******613(2) 42，即等式的右端有42個1。 程序： #include main() { long p,a,b,c,t,n; int bl; while(1) { printf(“輸入p,最后一位為1或3或7或9：＼n“); scanf(“%ld“,&p); if((p%2!=0)&&(p%5!=0))/*?如果輸入的數符合要求，結束循環?*/ ______⑥______; } a=0; n=0; while(a { a=a*10+1; n++;/*?變量a存放部分右端項，n為右端項的位數?*/ } t=0; do { b=a/p; printf(“%1ld“,b); t++; if(______⑦______) printf(“＼n“); c=______⑧______;a=______⑨______;n++; }while(c>0); printf(“＼nn=%ld＼n“,______⑩______); } 一、選擇一個正確答案代碼（A/B/C/D/E）,填入每題的括號內(每題1.5分,多選無分,?共30?分) 題號 ３ 選擇 D B B C B B C A D D 題號 選擇 C D C B C B B A C B 二、問題求解(共2題，每題5分，共計10分) 1.4次(1分)第一步：分成3組：27，27，26，將前2組放到天平上（4分）。 2.有獲勝策略(1分)第1次在第5堆中取32顆石子(4分)。 三、閱讀程序寫結果(共4題，每題8分，共計32分) 1.10，10（對1個數給4分，無逗號扣1分） 2.6??28??496??8128??33550336 (前2個對1個數給1分，后3個對1個數給2分) 3.5 4.6 6（數字之間無空格扣2分） 四、完善程序(前4空，每空2.5分，后6空，每空3分，共28分) 1.①?k==n??②?count%5==0??③?perm(k+1)④?a[k]=a[j]; a[j]=t??⑤?perm(1) 2.⑥?break????⑦?t%50==0????⑧?a-p*b????⑨?c*10+1????⑩?n-1
點擊咨詢