第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題及答案（普及組、C語言）普及組??C語言??二小時(shí)完成)

一、單項(xiàng)選擇題(共20題，每題1.5分，共計(jì)30分。

1．在下面各世界頂級(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)

2．在下面各軟件中，不屬于NOIP競(jìng)賽(復(fù)賽)推薦使用的語言環(huán)境是()。

A．gcc/g++????B．Turbo

Pascal????C．RHIDE????D．free

pascal

3．以下斷電之后仍能保存數(shù)據(jù)的有()。

A．寄存器????B．ROM????C．RAM????D．高速緩存

4．Linux是一種()。

A．繪圖軟件????B．程序設(shè)計(jì)語言????C．操作系統(tǒng)????D．網(wǎng)絡(luò)瀏覽器

5．CPU是()的簡(jiǎn)稱。

A．硬盤????B．中央處理器????C．高級(jí)程序語言????D．核心寄存器

6．在計(jì)算機(jī)中，防火墻的作用是()。

A．防止火災(zāi)蔓延????B．防止網(wǎng)絡(luò)攻擊????C．防止計(jì)算機(jī)死機(jī)????D．防止使用者誤刪除數(shù)據(jù)

7．在下列關(guān)于計(jì)算機(jī)語言的說法中，不正確的是()。

A．Pascal和C都是編譯執(zhí)行的高級(jí)語言

B．高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上

C．C++是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言

D．與匯編語言相比，高級(jí)語言程序更容易閱讀

8．在下列關(guān)于計(jì)算機(jī)算法的說法中，不正確的是()。

A．一個(gè)正確的算法至少要有一個(gè)輸入

B．算法的改進(jìn)，在很大程度上推進(jìn)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步

C．判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性

D．目前仍然存在許多涉及到國計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法

9．在下列各種排序算法中，不是以“比較”作為主要操作的算法是()。

A．選擇排序????B．冒泡排序????C．插入排序????D．基數(shù)排序

10．在編程時(shí)(使用任一種高級(jí)語言，不一定是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．24

12．在C語言中，判斷a不等于0且b不等于0的正確的條件表達(dá)式是()。

A．！a==0

||

!b==0????B．!(a==0)&&(b==0)C．!(a==0&&b==0)D．a(chǎn)&&b

13．某個(gè)車站呈狹長形，寬度只能容下一臺(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)?)。

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的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為()。

A．10????B．11????C．12????D．13

15．與十進(jìn)制數(shù)1770對(duì)應(yīng)的八進(jìn)制數(shù)是()。

A．3350????B．3351????C．3352????D．3540

16．將5個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過()次比較。完成從小到大的排序。

A．6????B．7????C．8????D．9

17．設(shè)A=B=D=ture，C=false，以下邏輯運(yùn)算表達(dá)式值為真的有()。

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的結(jié)果是()。

A．(8234)10????B．(202B)16????C．(20056)8????D．(100000000110)2

19．設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有()。

A．a(chǎn),b,c,e,d????B．b,c,a,e,d????C．a(chǎn),e,c,b,d????D．d,c,e,b,a

20．已知6個(gè)結(jié)點(diǎn)的二叉樹的先根+遍歷是1

6(數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，后根遍歷是3

1，則該二叉樹的可能的中根遍歷是()。

A．3

5????B．3

6????C．2

6????D．2

二、問題求解(共2題，每題5分，共計(jì)10分)

1．(尋找假幣)現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第1次的稱重方法。請(qǐng)寫出你的結(jié)果：________________________________________________________________。

2．(取石子游戲)現(xiàn)有5堆石子，石子數(shù)依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任取(每次只能取自一堆，不能不取)，取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略(即無論乙怎樣取，甲只要不失誤，都能獲勝)？如果有，甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫出你的結(jié)果：____________________________________________________________________。

三、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)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;

}

/*注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或下標(biāo)越界。*/

輸入：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個(gè)數(shù)的全部可能的排列(不一定按升序輸出)。例如，輸入3，則應(yīng)該輸出(每行輸出5個(gè)排列)：

123??132??213??231??321

312

程序：

#include

int

n,a[10];/*a[1],a[2],…,a[n]構(gòu)成n個(gè)數(shù)的一個(gè)排列*/

long

count=0;/*變量count記錄不同排列的個(gè)數(shù)，這里用于控制換行*/

void

perm(int

k)

{

int

j,p,t;

if(______①______)

{

count++;

for(p=1;p<=n;p++)

printf(“%1d“,a[p]);/*

“%1d“?中是數(shù)字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.由鍵盤輸入一個(gè)奇數(shù)P(P<100,000,000)，其個(gè)位數(shù)字不是5，求一個(gè)整數(shù)S，使P×S=1111...1(在給定的條件下，解s必存在)。要求在屏幕上依次輸出以下結(jié)果：

(1)

S的全部數(shù)字。除最后一行外，每行輸出50位數(shù)字。(2)乘積的數(shù)字位數(shù)。

例1：輸入P=13，由于13*8547=111111，則應(yīng)輸出(1)

8547，(2)

例2：輸入P=147，則輸出結(jié)果應(yīng)為(1)

7558578987******613(2)

42，即等式的右端有42個(gè)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))/*?如果輸入的數(shù)符合要求，結(jié)束循環(huán)?*/

______⑥______;

}

a=0;

n=0;

while(a

{

a=a*10+1;

n++;/*?變量a存放部分右端項(xiàng)，n為右端項(xiàng)的位數(shù)?*/

}

t=0;

do

{

b=a/p;

printf(“%1ld“,b);

t++;

if(______⑦_(dá)_____)

printf(“＼n“);

c=______⑧______;a=______⑨______;n++;

}while(c>0);

printf(“＼nn=%ld＼n“,______⑩______);

}

一、選擇一個(gè)正確答案代碼（A/B/C/D/E）,填入每題的括號(hào)內(nèi)(每題1.5分,多選無分,?共30?分)

題號(hào)

３

選擇

D

B

B

C

B

B

C

A

D

D

題號(hào)

選擇

C

D

C

B

C

B

B

A

C

B

二、問題求解(共2題，每題5分，共計(jì)10分)

1.4次(1分)第一步：分成3組：27，27，26，將前2組放到天平上（4分）。

2.有獲勝策略(1分)第1次在第5堆中取32顆石子(4分)。

三、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)

1.10，10（對(duì)1個(gè)數(shù)給4分，無逗號(hào)扣1分）

2.6??28??496??8128??33550336

(前2個(gè)對(duì)1個(gè)數(shù)給1分，后3個(gè)對(duì)1個(gè)數(shù)給2分)

3.5

4.6

6（數(shù)字之間無空格扣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