信息學(xué)奧賽試題及答案

信息學(xué)奧賽試題一、填空題（共20題，每題1.5分，共計(jì)30分。每題有5個(gè)備選答案，前10個(gè)題為單選題（即每題有且只有一個(gè)正確答案，選對(duì)得分），后10題為不定項(xiàng)選擇題（即每題有1至5個(gè)正確答案，只有全部選對(duì)才得分）。

1.微型計(jì)算機(jī)的性能主要取決于（）。

A）內(nèi)存B）主板C）中央處理器D）硬盤E）顯示器

2.能將高級(jí)語(yǔ)言程序轉(zhuǎn)換為目標(biāo)程序的是().

A）調(diào)試程序B）解釋程序C）編輯程序D）編譯程序E）連接程序

3．A=11001010B,B=00001111B,C=01011100B,則A∨B∧C=()

A）01011110B）00001111C）01011100D）11001110E)11001010

4.計(jì)算機(jī)設(shè)備，既是輸入設(shè)備，又是輸出設(shè)備的是()。

A)鍵盤B)觸摸屏C)掃描儀D)投影儀E)數(shù)字化儀

5.計(jì)算機(jī)病毒傳染的必要條件是()。

A)在內(nèi)存中運(yùn)行病毒程序B)對(duì)磁盤進(jìn)行讀寫操作C)在內(nèi)存中運(yùn)行含有病毒的可執(zhí)行程序D)復(fù)制文件E)刪除文件

6．已知隊(duì)列(13，2，11，34，4l，77，5，7，18，26，15)，第一個(gè)進(jìn)入隊(duì)列的元素是13，則第五個(gè)出隊(duì)列的元素是()。A)5B)41C)77D)13E)18

7.在使用E-mail前，需要對(duì)Outlook進(jìn)行設(shè)置，其中ISP發(fā)送電子郵件的服務(wù)器稱為()服務(wù)器。

A)POP3B)SMTPC)DNSD)FTPE)HTTP

8.對(duì)給定的整數(shù)序列(54,73,21,35,67,78,63,24,89)進(jìn)行從小到大的排序時(shí),采用快速排序的第一趟掃描的結(jié)果是().

A)(24,21,35,54,67,78,63,73,89)B)(24,35,21,54,67,78,63,73,89)

C)(24,21,35,54,67,63,73,78,89)D)(21,24,35,54,63,67,73,78,89)

E)(24,21,35,54,67,63,73,78,89)

9.編號(hào)為1到13的紙牌順時(shí)針排成一圈，有人從編號(hào)為1的牌從數(shù)字1開始順時(shí)針數(shù)下去，1，2，3，……,一圈又一圈,問(wèn)當(dāng)數(shù)到數(shù)字n,所在的紙牌編號(hào)為多少?

A)nmod13B)1+(n-1)mod13C)(n+1)mod13-1D)(n+1)mod13E)(n-1)mod13

10.對(duì)下圖進(jìn)行廣度優(yōu)先拓樸排序得到的頂點(diǎn)序列正確的是().

A)1,2,3,4,5,6B)1,3,2,4,5,6C)1,3,2,4,6,5D)1,2,3,4,6,5,E)1,3,2,4,5,6

11.下列屬于馮.諾依曼計(jì)算機(jī)模型的核心思想是().

A)采用二進(jìn)制表示數(shù)據(jù)和指令;B)采用”存儲(chǔ)程序”工作方式

C)計(jì)算機(jī)硬件有五大部件(運(yùn)算器、控制器、存儲(chǔ)器、輸入和輸出設(shè)備)

D)結(jié)構(gòu)化程序設(shè)計(jì)方法E)計(jì)算機(jī)軟件只有系統(tǒng)軟件

12．CPU訪問(wèn)內(nèi)存的速度比訪問(wèn)下列哪個(gè)(些)存儲(chǔ)設(shè)備要慢()。

A)寄存器B)硬盤C)軟盤D)高速緩存E)光盤

13．下列電子郵件地址，哪個(gè)(些)是正確的()。A)wang@B)cai@.jp

C)2D)E)

14．?dāng)?shù)字圖像文件可以用下列哪個(gè)(些)軟件來(lái)編輯()。

A)畫筆(Paintbrush)B)記事簿(Notepad)C)PhotoshopD)WmRARE)MidiSoft

15．下列哪個(gè)(些)軟件不是操作系統(tǒng)軟件的名字()。

A)WindowsXPB)DOSC)LinuxD)OS／2E)Arch／Info

16.下面關(guān)于算法的正確的說(shuō)法是()

A)算法必須有輸出B)算法必須在計(jì)算機(jī)上用某種語(yǔ)言實(shí)現(xiàn)

C)算法不一定有輸入D)算法必須在有限步執(zhí)行后能結(jié)束E)算法的每一步驟必須有確切的定義

17．下列邏輯運(yùn)算正確的是（）。

A)A·（A+B）=AB)A+（A·B）=A

C)A·（B+C）=A·B+A·CD)A+（B·C）=（A+B）·（A+C）E)A+1=A

18.下列關(guān)于排序說(shuō)法正確的是().

A)插入排序、冒泡排序是穩(wěn)定的B)選擇排序的時(shí)間復(fù)雜性為O(n2)

C)選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的

D)希爾排序、快速排序、堆排序的時(shí)間復(fù)雜性為O(nlog2n)

E)快速排序是速度最快的排序

19.對(duì)于一個(gè)大小為3的棧，若輸入隊(duì)列為123456，則下列輸出隊(duì)列有可能的是（）。

A)123456B)654321C)432165D)431256E)321654

20.設(shè)有一個(gè)含有13個(gè)元素的Hash表(0~12),Hash函數(shù)是:H(key)=key%13,其中%是求余數(shù)運(yùn)算。用二次探查法解決沖突,則對(duì)于序列(８、31、20、33、18、53、27),則下列說(shuō)法正確的是()。

A)27在1號(hào)格子中B)33在6號(hào)格子中C)31在5號(hào)格子中D)20在7號(hào)格子中E)18在4號(hào)格子中二.問(wèn)題求解（5分*2=10分）

1.某年級(jí)學(xué)生共選修6門課程，期末考試前，必須提前將這6門課程考完，每人每天只在下午至多考一門課程，設(shè)6門課程分別為c1，c2，c3，c4，c5，c6，S(ci)為學(xué)習(xí)ci的學(xué)生集合。已知S(ci)∩S(c6)≠?，i=l，2，．．．，5，S(ci)∩S(ci+1)≠?，i=1，2，3，4，S(c5)∩S(c1)≠?，問(wèn)至少安排天才能考完這6門課程。

2．設(shè)有一棵k*樹，其中只有度為0和k兩種結(jié)點(diǎn)，設(shè)n0，nk分別表示度為0和度為k的結(jié)點(diǎn)個(gè)數(shù)，試求出n0和nk之間的關(guān)系(n0=數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含nk、k和數(shù)字)。三.閱讀程序?qū)懗稣_的程序運(yùn)行結(jié)果(4*8分=32分)1programt1；

var

n，k，s：longint；

begin

readln(n);

k:=0；

s:=1；

whiles<=ndo

begin

k:=k+1;

n:=n-s;

s:=s+6*k

end;

writeln(k)

end.

輸入:1000000

輸出:

2.programt2;

varx,y1,y2,y3:integer;

begin

readln(x);

y1:=0;y2:=1;y3:=1;

whiley2<=xdo

begin

y1:=y1+1;y3:=y3+2;y2:=y2+y3;

end;

writeln(y1);

end.

輸人：x＝400

輸出：

3.program

t3；

varm，n，i，j：integer；

p，w，a，b：array[0．．19]ofinteger；

begin

read(n)；m：=0；

fori：=0ton-1do

beginread(p[i])；b[i]：=1；end；

fori：=0ton-1do

begin

if(i>0)then

a[m]：=p[i]-p[i-1]

else

a[m]：=p[i]；

m：=m+1：

while((m>1)and(a[rn-1]=0))do

beginm；=m-1；b[m]：=l；end；

if(m>0)then

w[i]：=b[m-1]

else

w[i]：=b[0]；

a[m-1]：=a[m-1]-1；

forj：=0tom-1dob[j]；=b[j]+1；

while((m>1)and(a[m-1]=0))do

begin

m：=m-1；b[m]：=1；

end;

end;

fori：=0ton-1do

begin

write(w[i])；write('');

end；

writeln('')；

end．

輸入：4

4666

輸出：

4.programt4；

const

u：array[1．．4]ofinteger=(0，5，3，1)；

v：array[1．．4]0finteger=(0，7，6，5)；

vara，b，c，d，e，f，x，y，z：integer；

begin

read(a，b，c，d，e，f)；

z：=f+e+d+(c+3)div4；y：=5*d+u[cmod4]；

if(b>y)then

begin

z：=z+(b-y+8)div9；

x：=((b-y+8)div9*9-(b-y))*4+11*e+V[cmod4]；

end

else

x：=(y-b)*4+11*e+v[cmod4]；

if(a>x)then

z：=z+(a-x+35)div36；

writeln(z)；

end．

輸入:479205647

輸出:四.完善程序題(2分+3*4分+2分+4*3分=28分)

1．問(wèn)題描述：工廠在每天的生產(chǎn)中，需要一定數(shù)量的零件，同時(shí)也可以知道每天生產(chǎn)

一個(gè)零件的生產(chǎn)單價(jià)。在N天的生產(chǎn)中，當(dāng)天生產(chǎn)的零件可以滿足當(dāng)天的需要，若當(dāng)天用不完，

可以放到下一天去使用，但要收取每個(gè)零件的保管費(fèi)，不同的天收取的費(fèi)用也不相同。

問(wèn)題求解：求得一個(gè)N天的生產(chǎn)計(jì)劃(即N天中每天應(yīng)生產(chǎn)零件個(gè)數(shù))，使總的費(fèi)用最少。

輸入：N(天數(shù)

N<=29)

每天的需求量

(N個(gè)整數(shù))

每天生產(chǎn)零件的單價(jià)(N個(gè)整數(shù))

每天保管零件的單價(jià)(N個(gè)整數(shù))

輸出：每天的生產(chǎn)零件個(gè)數(shù)(N個(gè)整數(shù))

例如：當(dāng)N=3時(shí)，其需要與費(fèi)用如下：

┌────┬────┬────┬────┐

│

│第一天│第二天│第三天│

├────┼────┼────┼────┤

│需要量│

25

│

15

│

30

│

├────┼────┼────┼────┤

│生產(chǎn)單價(jià)│

20

│

30

│

32

│

├────┼────┼────┼────┤

│保管單價(jià)│

5

│

10

│

0

│

└────┴────┴────┴────┘

生產(chǎn)計(jì)劃的安排可以有許多方案，如下面的三種：

┌────┬────┬────┬───────────┐

│第一天│第二天│第三天│

總的費(fèi)用

│

├────┼────┼────┼───────────┤

│

25

│

15

│

30

│25*20+15*30+30*32=1910│

├────┼────┼────┼───────────┤

│

40

│

0

│

30

│40*20+15*5+30*32=1835│

├────┼────┼────┼───────────┤

│

70

│

0

│

0

│70*20+45*5+30*10=1925│

└────┴────┴────┴───────────┘

程序說(shuō)明：

bln]：存放每天的需求量

cln]：每天生產(chǎn)零件的單價(jià)

d[n]：每天保管零件的單價(jià)

e[n]：生產(chǎn)計(jì)劃

程序：

programexp5;

var

i,j,n,yu,jO,j1,s

:integer;

b,c,d,e

:array[O..30]ofinteger;

begin

readln(n);

fori:=1tondoreadln(b[i],c[i],d[i]);

fori:=1tondoe[i]:=0;

____(1)____:=10000;

c[n+2]:=0;

b[n+1]:=0;

j=1;

while(jO<=n)do

begin

yu:=c[jO];

j1:=jO;

s:=b[jO];

while____(2)____

do

begin

____(3)____

j1:=j1+1;s:=s+b[j1];

end;

____(4)____

j0:=j1+1:

end;

fori:=1tondowrite(e[I]:4);

readln;

end.

2.問(wèn)題描述]

將一個(gè)含有運(yùn)算符為：(、)、+、-、*、/、^(乘冪運(yùn)算)、~(求負(fù)運(yùn)算)的中綴表達(dá)式，

如：((1+2)*5)^2-(3+5)/2轉(zhuǎn)化為后綴表達(dá)式，如：12+5*2^35+2/-．

[解題思路]將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，首先規(guī)定運(yùn)算符的優(yōu)先數(shù)如下：

┌───┬───┬───┬─────┬──────┬───┬───┐

│運(yùn)算符│

(│

)│

+，－│

*

，/

│

~

│

~

│

├───┼───┼───┼─────┼──────┼───┼───┤

│優(yōu)先數(shù)│

0│

1│

2

│

3

│

4

│

5

│

└───┴───┴───┴─────┴──────┴───┴───┘

1．若輸入是運(yùn)算量，則將該運(yùn)算量輸出；

2．若是左括號(hào)“(”，則將該符號(hào)的優(yōu)先數(shù)壓入設(shè)置的運(yùn)算符堆棧e[p]中去；

3．輸入運(yùn)算符優(yōu)先數(shù)是2，3，4，5時(shí)，如果?？?，則將運(yùn)算符的優(yōu)先數(shù)進(jìn)棧。如果棧不空，

則將它與棧頂元素進(jìn)行比較，倘若優(yōu)先數(shù)大于棧頂元素的優(yōu)先數(shù)，則進(jìn)棧；小于頂元的，則

頂元退棧并輸出該運(yùn)算符，然后再繼續(xù)比較，直到大于頂元或?？諘r(shí)進(jìn)棧；

4．若是右括號(hào)“)”，同時(shí)棧頂元又為左括號(hào)“(”，則棧頂元退棧，并抹去右括號(hào)“)”．

否則轉(zhuǎn)3處理；

5．輸入完而棧非空，則將棧內(nèi)內(nèi)容逐一退棧并輸出。所有輸出的結(jié)果就為后綴表達(dá)式。

過(guò)程中用到的相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：

typearraydata=array[1..100]ofstring[20];

constfh:array[1..8]ofstring[1]

=('(',')','+','-','*','/','~','^');

b:array[1..8]ofbyte=(0,1,2,2,3,3,4,5);

vard:arraydata;{存儲(chǔ)運(yùn)算量及運(yùn)算符號(hào)}

i,j,m,k:byte;

[過(guò)程程序]

procedurehzbds(vard:arraydata;varm:byte);

var:array[1..100]ofbyte;

i,p,k,bi:byte;

bl:boolean;

begin

p:=O;k:=1;bj:=0;

whilek<=mdo

begin

if

d[k]=’(‘then

begin

p:=p+1;e[p]:=1

end

elsebegin

fori:=2to8do

if___(1)___then

begin

b1:=true;

repeat

if___(2)___then

begin

p:=p+1;e[p]:=i;bj:=1;b1:=false

end

elseif____(3)___then

ife[p]<>1then

begin

p:=p+1;e[p]:=i;bj:=1;b1:=false

end

elseifd[k]<>')'then

begin

p:=p+1;e[p]:=i;bj:=1;b1:=false

end

el