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

1、信息學(xué)奧賽試題一、填空題（共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），后10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。1.微型計算機的性能主要取決于（ ）。A） 內(nèi)存 B） 主板 C） 中央處理器 D） 硬盤 E） 顯示器2.能將高級語言程序轉(zhuǎn)換為目標(biāo)程序的是( ).A）調(diào)試程序 B）解釋程序C）編輯程序 D）編譯程序E）連接程序3A=11001010B,B=00001111B,C=01011100B,則ABC=( )A）01011110 B） 00001111 C）01011100 D） 1100

2、1110 E) 110010104.計算機設(shè)備，既是輸入設(shè)備，又是輸出設(shè)備的是( )。 A)鍵盤 B)觸摸屏 C)掃描儀 D)投影儀 E)數(shù)字化儀 5.計算機病毒傳染的必要條件是( ) 。A) 在內(nèi)存中運行病毒程序 B) 對磁盤進(jìn)行讀寫操作C) 在內(nèi)存中運行含有病毒的可執(zhí)行程序 D) 復(fù)制文件 E)刪除文件6已知隊列(13，2，11，34，4l，77，5，7，18，26，15)，第一個進(jìn)入隊列的元素是13，則第五個出隊列的元素是( )。 A)5 B)41 C)77 D)13 E)18 7.在使用E-mail前，需要對Outlook進(jìn)行設(shè)置，其中ISP發(fā)送電子郵件的服務(wù)器稱為( )服務(wù)器。A)P

3、OP3 B)SMTP C)DNS D)FTP E)HTTP8.對給定的整數(shù)序列(54,73,21,35,67,78,63,24,89)進(jìn)行從小到大的排序時,采用快速排序的第一趟掃描的結(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. 編號為1到13的紙牌順時針排成一圈，有人從編號為1的牌從數(shù)字1開始順時針數(shù)下去，1，

4、2，3，,一圈又一圈,問當(dāng)數(shù)到數(shù)字n ,所在的紙牌編號為多少?A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13 E) (n-1) mod 13 10.對下圖進(jìn)行廣度優(yōu)先拓樸排序得到的頂點序列正確的是( ).A) 1,2,3,4,5,6 B) 1,3,2,4,5,6 C) 1,3,2,4,6,5D) 1,2,3,4,6,5, E) 1,3,2,4,5,611.下列屬于馮.諾依曼計算機模型的核心思想是( ).A) 采用二進(jìn)制表示數(shù)據(jù)和指令; B) 采用”存儲程序”工作方式C) 計算機硬件有五大部件(運算器、控制器、存儲器、輸入

5、和輸出設(shè)備)D) 結(jié)構(gòu)化程序設(shè)計方法 E) 計算機軟件只有系統(tǒng)軟件12CPU訪問內(nèi)存的速度比訪問下列哪個(些)存儲設(shè)備要慢( )。 A)寄存器 B)硬盤 C)軟盤 D)高速緩存 E)光盤 13下列電子郵件地址，哪個(些)是正確的( )。A)wang B).jpC)162.105.111. 22 D) E) 14數(shù)字圖像文件可以用下列哪個(些)軟件來編輯( )。 A)畫筆(Paintbrush) B)記事簿(Notepad) C)Photoshop D)WmRAR E)MidiSoft 15下列哪個(些)軟件不是操作系統(tǒng)軟件的名字( )。 A)Windo

6、ws XP B)DOS C)Linux D)OS2 E)ArchInfo 16.下面關(guān)于算法的正確的說法是( )A)算法必須有輸出 B)算法必須在計算機上用某種語言實現(xiàn)C)算法不一定有輸入 D)算法必須在有限步執(zhí)行后能結(jié)束 E)算法的每一步驟必須有確切的定義17下列邏輯運算正確的是（ ）。A) A·（A + B ）= A B) A +（A·B）= AC) A·（B + C ）= A·B + A·C D)A +（B·C）=（A + B）·（A + C） E) A+1=A18.下列關(guān)于排序說法正確的是( ).A) 插入排序、冒泡

7、排序是穩(wěn)定的 B) 選擇排序的時間復(fù)雜性為O(n2)C) 選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的D) 希爾排序、快速排序、堆排序的時間復(fù)雜性為O(nlog2n)E) 快速排序是速度最快的排序19.對于一個大小為3的棧，若輸入隊列為123456，則下列輸出隊列有可能的是（ ）。A) 123456 B)654321 C)432165 D)431256 E)32165420. 設(shè)有一個含有13個元素的Hash表(012),Hash函數(shù)是:H(key)=key % 13,其中% 是求余數(shù)運算。用二次探查法解決沖突,則對于序列(、31、20、33、18、53、27),則下列說法正確的是( ) 。

8、A)27在1號格子中 B) 33在6號格子中 C) 31在5號格子中 D) 20在7號格子中E) 18在4號格子中二.問題求解（5分*2=10分）1.某年級學(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)Ø ，問至少安排天才能考完這6門課程。2設(shè)有一棵k*樹，其中只有度為0和k兩種結(jié)點，設(shè)n0，nk分別表示度為0和度為k的結(jié)點個數(shù)

9、，試求出n0和nk之間的關(guān)系(n0=數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含nk、k和數(shù)字)。三.閱讀程序?qū)懗稣_的程序運行結(jié)果(4 *8分=32分)1 program t1；var  n，k，s：longint；begin readln(n);  k:=0；  s:=1；  while s <= n do  begin    k:=k+1;    n:=n-s;    s:=s+6*

10、k  end;  writeln (k)end.輸入:1000000 輸出:2. program t2;var x,y1,y2,y3:integer; begin  readln(x);  y1:=0;y2:=1;y3:=1;  while y2<=x do    begin      y1:=y1+1;y3:=y3+2;y2:=y2+y3;    e

11、nd;  writeln(y1);end.輸人：x400輸出：3. program  t3； var m，n，i，j：integer； p，w，a，b：array019 of integer； begin read(n)； m：= 0； for i：= 0 to n-1 do begin read (pi)； bi ：=1； end； for i ：= 0 to n-1 do begin if (i>0) then am：= pi-pi-1 else am：= pi； m：= m+1： while (m>1) and (arn-1=0) do

12、 begin m ；= m-1； bm ：= l； end； if (m>0) then wi：=bm-1 else wi：=b0； am-1 ：= am-1-1； for j ：= 0 to m-1 do bj ；= bj+1； while (m>1) and (am-1=0) do begin m ：= m-1； bm ：=1； end;end;for i ：= 0 to n-1 do begin write(wi)； write(' '); end；writeln(' ')；end 輸入：44 6 6 6輸出：4. program t4； co

13、nst u：array14 of integer = (0，5，3，1)； v：array14 0f integer = (0，7，6，5)； var a，b，c，d，e，f，x，y，z： integer； begin read (a，b，c，d，e，f)； z ：= f + e + d + (c+3) div 4； y ：= 5 * d + u c mod 4 ； if (b>y) thenbeginz ：= z+ (b-y+8) div 9；x ：= (b-y+8) div 9 * 9- (b-y) * 4+11*e+Vc mod 4；endelsex ：= (y-b) *4+11*

14、e+vc mod 4；if (a>x) thenz ：= z + (a-x+35) div 36； writeln(z)； end輸入: 4 7 9 20 56 47輸出: 四.完善程序題(2分+3*4分+2分+4*3分=28分)1問題描述：工廠在每天的生產(chǎn)中，需要一定數(shù)量的零件，同時也可以知道每天生產(chǎn)一個零件的生產(chǎn)單價。在N天的生產(chǎn)中，當(dāng)天生產(chǎn)的零件可以滿足當(dāng)天的需要，若當(dāng)天用不完，可以放到下一天去使用，但要收取每個零件的保管費，不同的天收取的費用也不相同。    問題求解：求得一個N天的生產(chǎn)計劃(即N天中每天應(yīng)生產(chǎn)零件個數(shù))，使總的費用最少。&

15、#160;   輸入：N(天數(shù)    N<=29)       每天的需求量    (N個整數(shù))    每天生產(chǎn)零件的單價(N個整數(shù))    每天保管零件的單價(N個整數(shù))    輸出：每天的生產(chǎn)零件個數(shù)(N個整數(shù))  例如：當(dāng)N=3時，其需要與費用如下：  &#

16、160;                    第一天 第二天 第三天               需要量    25      15      30      

17、;           生產(chǎn)單價   20      30      32                 保管單價    5      10     

18、;  0          生產(chǎn)計劃的安排可以有許多方案，如下面的三種：              第一天 第二天 第三天   總的費用                  

19、60;         25      15      30   25*20+15*30+30*32=1910                 40       0      30 

20、;  40*20+15*5+30*32=1835                  70       0       0   70*20+45*5+30*10=1925        程序說明：  bln：存放每天的需求量

21、0; cln：每天生產(chǎn)零件的單價  dn：每天保管零件的單價  en：生產(chǎn)計劃程序：program exp5;vari,j,n,yu,jO,j1,s  :integer;b, c, d, e        : arrayO.30 of integer;begin  readln(n);  for i:=1 to n do readln(bi ,ci ,di);  for i:=1 to

22、n do ei:=0;_(1)_:=10000;    cn+2:=0;    bn+1:=0;    j=1;while (jO<=n) do   begin     yu:=cjO;    j1:=jO;    s:=bjO;     while _(2)_  do&#

23、160;     begin         _(3)_    j1:=j1+1;s:=s+bj1;      end;     _(4)_  j0:=j1+1:  end;for i:=1 to n do write(eI:4);readln;end.2. 問題描述將一個含有運算符為：(

24、、)、+、-、*、/、(乘冪運算)、(求負(fù)運算)的中綴表達(dá)式，如：(1+2)*5)2-(3+5)/2轉(zhuǎn)化為后綴表達(dá)式，如：12+5*235+2/-解題思路將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，首先規(guī)定運算符的優(yōu)先數(shù)如下：運算符    (     )     +，     *  ，/            優(yōu)先數(shù) &#

25、160;  0     1     2         3          4     5  1若輸入是運算量，則將該運算量輸出；2若是左括號“(”，則將該符號的優(yōu)先數(shù)壓入設(shè)置的運算符堆棧ep中去；3輸入運算符優(yōu)先數(shù)是2，3，4，5時，如果?？眨瑒t將運算符的優(yōu)先數(shù)進(jìn)棧。如果棧不

26、空，則將它與棧頂元素進(jìn)行比較，倘若優(yōu)先數(shù)大于棧頂元素的優(yōu)先數(shù)，則進(jìn)棧；小于頂元的，則頂元退棧并輸出該運算符，然后再繼續(xù)比較，直到大于頂元或?？諘r進(jìn)棧；4若是右括號“)”，同時棧頂元又為左括號“(”，則棧頂元退棧，并抹去右括號“)”否則轉(zhuǎn)3處理；5輸入完而棧非空，則將棧內(nèi)內(nèi)容逐一退棧并輸出。所有輸出的結(jié)果就為后綴表達(dá)式。過程中用到的相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：type arraydata = array1.100 of string20;const fh:array1.8 of string1        =('(&

27、#39;,')','+','-','*','/','','');      b:array1.8 of byte =(0,1,2,2,3,3,4,5);var d: arraydata; 存儲運算量及運算符號    i,j,m,k: byte;過程程序procedure hzbds(var d: arraydata; var m: byte );  var: arr

28、ay 1. 100 of byte;     i,p,k ,bi:byte;     bl: boolean;  begin    p:=O;k:=1;bj:=0;    while k<=m do    begin      if  dk=( then   &#

29、160;  begin        p:=p+1;ep:=1      end      else begin           for i:=2 to 8 do         

30、60; if _(1)_ then           begin             b1:= true;             repeat         &

31、#160;     if _(2)_ then               begin                 p:= p+1 ;ep:=i;bj:= 1 ;b1:= false      &

32、#160;        end               else if _(3)_ then                 if ep < >1 then    

33、0;            begin                   p:=p+1;ep:=i;bj:=1;b1:=false               

34、;  end                 else if dk < >')' then                   begin       

35、              p:=p+1;ep:=i;bj:=1;b1:=false                   end             

36、60;     else begin                      _(4)_;bj:= 1 ;b1:= false;                 

37、60;      end                 else begin                        write(fhep ,' ') ;p:=p-1                 &