寧波市第31屆小學(xué)生計算機(jī)程序設(shè)計初賽試題—.選擇題（每題1.5分，共30分。每小題只有唯一個正確答案）

1.一個16位整型變量占用（）個字節(jié)A.1

B.2

C.4

D.8

2.表達(dá)式29div5mod2+trunk（3．78）的值是（）A.33

B.32

C.4

D.5

3.字母信息在計算機(jī)中最終是以數(shù)值的形式存儲的，ascii碼統(tǒng)一規(guī)定了常用符號用哪些數(shù)值來表示，例如字母‘Z'的ascii碼是十進(jìn)制的90，字母‘L’的ascii碼是十進(jìn)制（），A.108

B.90

C.76

D.75

4.下列選頂中不屬于音頻文件格式的是（）A.wav格式

B.mp3格式

C.avi格式

D.flac格式

5.如主存容量為32M字節(jié)，且按字節(jié)編址，表示該主存地址至少應(yīng)需要（）位A.16

B.20

C.2

D.32

6.如果一棵二叉樹的前序遍歷是ABDEFC.中序遍歷是DEBFAC,那么它的后序遍歷是()A.ABCDFE

B.CAFBED

C.EDFBCA

D.DEFBCA

7.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）A.abcd*+-

B.abc+*d-

C.abc*+d-

D.-+*abcd

8.計算機(jī)所能辨認(rèn)的最小信息單位是（）A.字節(jié)

B.位

C.字符串

D.（K）

9.對于下圖，至少要減掉（）條邊，使之存在一條路徑，經(jīng)過圖中每條邊一次且僅一次

A.0

B.1

C.2

D.3

10.NFC是近距離無線通訊技術(shù)，此項可以用在手機(jī)上，以下（）不屬于此技術(shù)在手機(jī)上的應(yīng)用實例A.手機(jī)登錄wifi刷微信

B.手機(jī)機(jī)場登機(jī)驗證

C.手機(jī)充當(dāng)大廈的門禁鑰匙

D.手機(jī)公交刷卡

11.己知有abcdef六個整型變量，大小關(guān)系如下：a>b,a>c,a>d,b>f,b>c,f>d,d>c,f>e,d>e,c>e根據(jù)以上大小關(guān)系，請分折六個整型變量第3大的是（）A.a

B.b

C.d

D.f

12.一片容量為16GB的SD卡能存儲大約（）張大小為2MB的碼照片。A.2000

B.4000

C.8000

D.16000

13.下列哪個不屬于物聯(lián)網(wǎng)的應(yīng)用實例()A.電腦實時顯示快遞車輛運(yùn)動軌跡

B.蘋果手機(jī)小偷刷機(jī)時警察定位并抓荻

C.遠(yuǎn)監(jiān)控工地施工

D.實況足球里的角色具備c羅、梅西的個人能力

14.互聯(lián)網(wǎng)其中一大優(yōu)勢就是可以共享資源，以下哪項活動不屬于共享資源（）A.為網(wǎng)民提供代理服務(wù)器加速流覽國外網(wǎng)站。

B.設(shè)計一個學(xué)生信息的數(shù)據(jù)庫

C.QQ傳輸文件

D.在校網(wǎng)上發(fā)布最新版編程軟件

15.15、三位水仙花數(shù)是指每個位上的數(shù)字的3次冪之和等于它木身。（例如：1^3+5^3+3^3=153）找所有三位水仙花數(shù)程序如下，它的算法屬于（）fori:lto9doforj:=0to9dofork:=0to9doif(i*i*i+j*j*j+k*k*k=i*100+j*10+k)then……A.動態(tài)規(guī)劃

B.貪心

C.枚舉

D.遞歸

16.如果一個棧始時為字．當(dāng)前棧中的元素從棧底到棧頂依次為a，b·另有元素c，d，己經(jīng)出棧，則不可能的人棧順序是（）。A.bacd

B.cdab

C.cadb

D.dabc

17.二進(jìn)制數(shù)10101轉(zhuǎn)化成十進(jìn)制表示是（）A.42

B.21

C.13

D.25

18.18、己知邏輯表達(dá)式值為false的是（）a＝trueb＝falsec＝falsed＝trueA.aandbxorcandd

B.aOrbandcord

C.axorborcandd

D.aorbxordandc

19.計算機(jī)前端總線的英文名字是FrontSideBus，用FSB表示．指的是將CPU接到（）的總線。A.內(nèi)存

B.北橋芯片

C.南橋芯片

D.I/O設(shè)備

20.第45屆全球超級汁算機(jī)500強(qiáng)排行榜．于2015年7月公布，冠軍是（）A.中國“天河二號”

B.美國橡樹嶺國家驗率的“泰坦”

C.日本理化學(xué)研究所的"KComputer"

D.美國勞倫斯一利弗莫爾國家實驗的“紅杉”

二.問題求解（每理5分，共10分）

1.豆豆是個對數(shù)學(xué)非常敏感的孩子，剛學(xué)了加法，他就發(fā)現(xiàn)3的所有倍數(shù)個位數(shù)字都是有規(guī)律的，例如:3,6,9,12,15,18,21,24,27,30,33,36,39,42....存?zhèn)€循環(huán)(3,6,9,2,5,8,1,4,7,0)。等到學(xué)了乘法后，他思考這個問題：3^2016(2016個3相乘)運(yùn)算結(jié)果的個位上的數(shù)字是（）。

答案：

2.豆豆課余愛好之一就是玩各種自創(chuàng)的數(shù)字游戲，其中一種很受同學(xué)的好評，大家經(jīng)常開展比賽。這個游戲如下：5行5列的數(shù)字方陣中選取5個數(shù)，求這5個數(shù)任意2個既不是同一行，也不能同一列?？纯凑l能最先算出這5個數(shù)最大和是（）。豆豆總是能勝出?？慈说牧?。15061412200311180313060914091413120716192214080714

答案：

三.閱讀程序，求程序運(yùn)行輸出結(jié)果（每題8分，共32分）

1.var

a,b,c,d:longint;

begin

read(a,b,c);

a:=a+b*c;

b:=a-c;

c:=a+b;

d:=b*c-a;

a:=d*(a-b);

writeln('a=',a);

end.

【輸入】：111輸出：

2.var

i,j:longint;

a,b:array[0..20]oflongint;

out：array[0..200]ofboolean;

begin

fori:=1to12

do

read(a[i]);

fori:=1to15

do

read(b[i]);

fori:=1to12do

forj:=1to15do

ifa[i]=b[j]thenout[a[i]]:=true;

fori:=1to90do

ifnotout[i]and(imod8=0)then

write(i,'');

end.

【輸入】：

217232829373848495879114

2172328293845485658677275101122輸出：

3.var

j:longint;

use:array[0..10]ofboolean;

a：array[0..10]oflongint;

proceduredfs(i:longint);

varj:longint;

begin

ifi>2thenbegin

forj:=1to2do

write(a[j],'');

writeln;

exit

end;

forj:=a[i-1]+1to3do

Ifnotuse[j]thenbegin

use[j]:=true;

a[i]:=j；

dfs(i+1)；

use[j]:=false;

end;

end;

begin

dfs(1);

end.輸出：

4.var

n,i,j,t,sum:longint;

a:array[0..50]oflongint;

f:array[0..50]ofboolean;

begin

readln(n);

for

i:=1

tondo

read(a[i]);

fillchar(f,sizeof(f),true);

fori:=1

tondo

iff[i]then

begin

inc(sum);

t:=a[i]；

forj:=itondo

iff[j]and(t=a[j])then

begin

f[j]:=false;

t:=t-1;

ift=0then

break;

end;

end;

writeln(sum);

end.

【輸入】：

8

9191173261

輸出：

四.完善程序（前兩空每空2分，其余八空每空3分，共28分）

1.買書

書店有個買2送1的活動：買3本書只要付較貴的2本就可以了。舉個例子：

10324649,如果這樣組合(10,3,2),(4,6,4)and(9),就能在第一個括號中省下2元，第二括號中省下4元，但第三個括號不能省了，因為不足3本書。

售貨員是個熱心腸也愛動腦筋的人，他想為每位顧客盡可能多的省錢，請你幫助她吧。

注意：不一定非要組合三本書一堆，但一堆的數(shù)量必須是1到3

輸入的第一行一個整數(shù)N，表示書的數(shù)量。接下來的N行，每行包含一個整數(shù)Ci，表示每本書的價格。輸出一個數(shù)。表示最終要為這些書付出的最小價格。

解題思路：貪心的策略，按照書費(fèi)的降序排序，挑盡可能貴的2本放在一起來省去書費(fèi)，反復(fù)操作，直到書少于3本樣例中10324649就可以這樣分組：

（1096）、（443）、（2），很顯然省去了6+3+2=9，這是最省錢的分組方案，根據(jù)這個思路，請完善以下程序

var

n,i:longint;

a:array[0..100001]oflongint;

s:int64;

proceduresort(l,r:longint);//sort過程實現(xiàn)a數(shù)組值的降序排序

vari,j,x,y:longint;

begin

i:=l;j:=r;x:=a[(l+r)div2];

repeat

while

_________doinc(i);

whilex>a[j]dodec(j);

ifnot(i>j)then

begin

y:=a[i];_________;a[j]:=y;

inc(i);j:=j-1;

end;

until_________;

ifl<j

thensort(l,j);

ifi<rthensort(i,r);

end;

begin

readln(n);

fori:=1tondo

read(a[i]);

sort(1,n);

fori:=1tondo

if_________then

s:=_________;

writeln(s);

end.

2.拼木棍

有一些同樣長的木棍，氫這些木棍隨意砍成幾段。現(xiàn)在，他想把小木棍拼接成原來的的樣子，但是忘記了自己開始時有多少根木棍和它們的的長度。

給出每段小木棍的長度，編程找出原始木棍的最小可能長度。

輸入第一行為一個單獨(dú)的整數(shù)N表示砍過以后的小木棍的總數(shù)。笫二行為N個用空格隔開的正整數(shù)，表示N根小木棍的長度，輸出僅一行，表示要求的原始木棍的最小可能長度。

樣例輸入：

9

521521521

樣例輸出：

6

解題思路：

枚舉原始木棍長度，然后驗證小木棍是否能拼湊出該枚舉長度的整數(shù)倍，但要充分利用題目的隱含的信息進(jìn)行優(yōu)化，不然會超時

優(yōu)化1：原始木棍長度>=最大的小木棍長度，原始木棍長度<=小木棍長度之和

優(yōu)化2：小木棍的長度之和一定是原始的木棍長度的倍數(shù)

優(yōu)化3：小木棍應(yīng)該由大到小去拼湊枚舉出來的原始木棍長度

優(yōu)化4：當(dāng)每次嘗試接入小木棍后，大木棍未達(dá)到要求長度時，嘗試接入的下一根小木棍要和剛剛接入小木棍和長度不相等

優(yōu)化5：當(dāng)一個小木棍接入后，剛好達(dá)到原始木棍長度，在以后的嘗試中沒有必要用更小的小木棍代替這個剛接入的小木棍

根據(jù)以上解題思路完善如下程序

var

n,i,L,max,sum,j:longint;

a:array[0..100]oflongint;

visit:array[0..100]ofboolean;

proceduredfs(k,now:longint);

var

i,last:longint;

begin

if(k>n)and(now=0)then

begin

writeln(L);

halt;//退出整個秤序

end;

ifk>nthenexit;

last:=0;

fori:=1tondo

if(not(visit[i]))and(now+a[i]<=L)and(_________)

then

begin

visit[i]:=true;

if(_________)

then

begin

dfs(k+1,0);

visit[i]:=false;

exit;//這里的退出體現(xiàn)了優(yōu)化5

end;

_________

;

visit[i]:=false；

last:=a[i];

ifnow=0thenexit;

end;

end;

begin

readln(n);

i:=n;

wh