信息學奧賽試題c語言,信息學奧賽c++編程題庫

本文目錄一覽：

• 1、關於C語言和信息學奧賽的一道題目，和背包問題，取數的演算法有些類似。
• 2、懸賞10分,C語言的高手嗎?第十一屆全國青少年信息學奧賽程序題第四題,有誰知道怎麼做嗎?
• 3、求第十四屆信息學奧賽聯賽普及組c語言初賽試題 第三大題第2,3題的解析
• 4、誰有2007年全國信息學奧賽的初賽試題（C語言）？
• 5、2010信息學奧賽初賽試題及答案

關於C語言和信息學奧賽的一道題目，和背包問題，取數的演算法有些類似。

物品的容量即為價值

#includestdio.h

#define max(x,y) (x)(y)?(x):(y)

int V,n;

int DP(int *v,int *w)

{

int i,j,t[10005]={0};

for(i=1;i=n;i++)

for(j=V;j=v[i];j–)

t[j]=max(t[j],t[j-v[i]]+w[i]);

return t[V];

}

int main()

{

int i,v[1005];

while(scanf(“%d%d”,n,V)==2)

{

for(i=1;i=n;i++)

scanf(“%d”,v[i]);

printf(“%d\n”,DP(v,v));

}

}

懸賞10分,C語言的高手嗎?第十一屆全國青少年信息學奧賽程序題第四題,有誰知道怎麼做嗎?

digit(n/10,m/10);

printf(“%2ld”,n%10); 容易發生錯誤.

其實前面輸出的6 2 5 4 3 7 9都是在digit(n/10,m/10); 的內層循環中輸出的。後面的9 7 3 4 5 2 6才是跳出內層循環digit(n/10,m/10); 在語句printf(“%2ld”,n%10);中輸出的，每次的內層循環digit(n/10,m/10); 都有一個語句printf(n/10,m/10);

所以結果就是這樣的了。這個問題其實不是很隱蔽

不過要是初學或不細心，哈哈，可就麻煩了！

求第十四屆信息學奧賽聯賽普及組c語言初賽試題 第三大題第2,3題的解析

2,3,1

遞歸一次，輸入參數循環左移至第一個數小於等於第二個數然後輸出

5 4 10 1 6 22 -59 -16 -11 -6

將數組中正數與負數分開排列，從數組起始開始檢測非整數數，從數組末尾檢測非負數，然後將這兩個數調換位置

最後一個遞歸沒時間分析了，下午有事要出門了

誰有2007年全國信息學奧賽的初賽試題（C語言）？

NOIP2007 初賽試題（提高組C）

© 中國計算機學會2007

1

第十三屆全國青少年信息學奧林匹克聯賽初賽試題

（ 提高組C 語言二小時完成）

● ● 全部試題答案均要求寫在答捲紙上，寫在試捲紙上一律無效●●

一、單項選擇題（共10 題，每題1.5 分，共計15 分。每題有且僅有一個正確答案）。

1. 在以下各項中，（ ）不是CPU 的組成部分。

A. 控制器B. 運算器C. 寄存器D. 主板E. 算術邏輯單元(ALU)

2．在關係資料庫中，存放在資料庫中的數據的邏輯結構以（ ）為主。

A. 二叉樹B. 多叉樹C.哈希表D. B+樹E.二維表

3．在下列各項中，只有（ ）不是計算機存儲容量的常用單位。

A. Byte B. KB C.MB D.UB E.TB

4．ASCII 碼的含義是（ ）。

A. 二—十進位轉換碼B. 美國信息交換標準代碼C. 數字的二進位編碼

D. 計算機可處理字元的唯一編碼E. 常用字元的二進位編碼

5．在C 語言中，表達式23|2^5 的值是（ ）

A. 23 B. 1 C.18 D.32 E.24

6．在C 語言中，判斷a 等於0 或b 等於0 或c 等於0 的正確的條件表達式是（ ）

A. !((a!=0)||(b!=0)||(c!=0))

B. !((a!=0)(b!=0)(c!=0))

C. !(a==0b==0)||(c!=0)

D. (a=0)(b=0)(c=0)

E. !((a=0)||(b=0)||(c=0))

7．地面上有標號為A、B、C 的3 根細柱，在A 柱上放有10 個直徑相同中間有孔的圓盤，從上到下依

次編號為1，2，3，……，將A 柱上的部分盤子經過B 柱移入C 柱，也可以在B 柱上暫存。如果B 柱

上的操作記錄為：「進，進，出，進，進，出，出，進，進，出，進，出，出」。那麼，在C 柱上，從下

到上的盤子的編號為（ ）。

A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6

D. 2 4 3 6 7 5 E. 2 1 4 3 7 5

8. 與十進位數17.5625 對應的8 進位數是（ ）。

A. 21.5625 B. 21.44 C. 21.73

D. 21.731 E. 前4 個答案都不對

9．歐拉圖G 是指可以構成一個閉迴路的圖，且圖G 的每一條邊恰好在這個閉迴路上出現一次（即一筆

畫成）。在以下各個描述中，不一定是歐拉圖的是（ ）。

A. 圖G 中沒有度為奇數的頂點

B. 包含歐拉環遊的圖（歐拉環遊是指通過圖中每邊恰好一次的閉路徑）

C. 包含歐拉閉跡的圖（歐拉跡是指通過圖中每邊恰好一次的路徑）

D. 存在一條迴路，通過每個頂點恰好一次

E. 本身為閉跡的圖

10. 一個無法靠自身的控制終止的循環稱為「死循環」，例如，在C 語言程序中，語句「while(1)

printf(「*」);」就是一個死循環，運行時它將無休止地列印*號。下面關於死循環的說法中，只有（ ）

是正確的。

A. 不存在一種演算法，對任何一個程序及相應的輸入數據，都可以判斷是否會出現死循環，因而，

任何編譯系統都不做死循環檢驗

B．有些編譯系統可以檢測出死循環

C. 死循環屬於語法錯誤，既然編譯系統能檢查各種語法錯誤，當然也應該能檢查出死循環

D. 死循環與多進程中出現的「死鎖」差不多，而死鎖是可以檢測的，因而，死循環也是可以檢測

的

E. 對於死循環，只能等到發生時做現場處理，沒有什麼更積極的手段

二、不定項選擇題（共10 題，每題1.5 分，共計15 分。每題正確答案的個數大於或等於1。多選

或少選均不得分）。

11. 設A=B=true，C=D=false，以下邏輯運算表達式值為真的有（ ）。

A. (¬ A∧B)∨(C∧D∨A) B. ¬ (((A∧B)∨C)∧D)

C. A∧(B∨C∨D)∨D D. (A∧(D∨C)) ∧B

12. 命題「P→Q」可讀做P蘊涵Q，其中P、Q 是兩個獨立的命題。只有當命題P成立而命題Q不成立時，

命題「P→Q」的值為false，其他情況均為true。與命題「P→Q」等價的邏輯關係式是（ ）。

A. ¬ P∨Q B. P∧Q C. ¬ (P∨Q) D. ¬ (¬ Q∧P)

13. (2070)16 + (34)8 的結果是（ ）。

A. (8332)10 B. (208C)16

C. (100000000110)2 D. (20214)8

14. 已知7 個結點的二叉樹的先根遍歷是1 2 4 5 6 3 7（數字為結點的編號，以下同），後根遍歷

是4 6 5 2 7 3 1，則該二叉樹的可能的中根遍歷是（ ）

A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7

C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3

15. 冗餘數據是指可以由其他數據導出的數據，例如，資料庫中已存放了學生的數學、語文和英語的三

科成績，如果還存放三科成績的總分，則總分就可以看作冗餘數據。冗餘數據往往會造成數據的不一致，

例如，上面4 個數據如果都是輸入的，由於操作錯誤使總分不等於三科成績之和，就會產生矛盾。下面

關於冗餘數據的說法中，正確的是（ ）。

A. 應該在資料庫中消除一切冗餘數據

B. 與用高級語言編寫的數據處理系統相比，用關係資料庫編寫的系統更容易消除冗餘數據

C. 為了提高查詢效率，在資料庫中可以適當保留一些冗餘數據，但更新時要做相容性檢驗

D. 做相容性檢驗會降低效率，可以不理睬資料庫中的冗餘數據

16.在下列各軟體中，屬於NOIP 競賽（複賽）推薦使用的語言環境有（ ）。

A. gcc B. g++

C. Turbo C D. free pascal

17. 以下斷電之後仍能保存數據的有（ ）。

A. 硬碟B. ROM C. 顯存D. RAM

18. 在下列關於計算機語言的說法中，正確的有（ ）。

A. 高級語言比彙編語言更高級，是因為它的程序的運行效率更高

B. 隨著Pascal、C等高級語言的出現，機器語言和彙編語言已經退出了歷史舞台

C. 高級語言程序比彙編語言程序更容易從一種計算機移植到另一種計算機上

D. C是一種面向過程的高級計算機語言

19. 在下列關於演算法複雜性的說法中，正確的有（ ）。

A. 演算法的時間複雜度，是指它在某台計算機上具體實現時的運行時間

B. 演算法的時間複雜度，是指對於該演算法的一種或幾種主要的運算，運算的次數與問題的規模之間的函

數關係

C. 一個問題如果是NPC類的，就意味著在解決該問題時，不存在一個具有多項式時間複雜度的演算法。

但這一點還沒有得到理論上的證實，也沒有被否定

D. 一個問題如果是NP類的，與C有相同的結論

20. 近20年來，許多計算機專家都大力推崇遞歸演算法，認為它是解決較複雜問題的強有力的工具。在下

列關於遞歸演算法的說法中，正確的是（ ）。

A. 在1977年前後形成標準的計算機高級語言「FORTRAN77」禁止在程序使用遞歸，原因之一是該方

法可能會佔用更多的內存空間

B. 和非遞歸演算法相比，解決同一個問題，遞歸演算法一般運行得更快一些

C. 對於較複雜的問題，用遞歸方式編程往往比非遞歸方式更容易一些

D. 對於已經定義好的標準數學函數sin(x)，應用程序中的語句「y=sin(sin(x));」就是一種遞

歸調用

三．問題求解（共2 題，每題5 分，共計10 分）

1．給定n 個有標號的球，標號依次為1，2，…，n。將這n 個球放入r 個相同的盒子里，不允許

有空盒，其不同放置方法的總數記為S(n,r)。例如，S(4,2)=7，這7 種不同的放置方法依次為

{(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)},

{(14),(23)}。當n=7,r=4 時，S(7,4)= _____________。

2．N 個人在操場里圍成一圈，將這N 個人按順時針方向從1 到N 編號，然後，從第一個人起，每

隔一個人讓下一個人離開操場，顯然，第一輪過後，具有偶數編號的人都離開了操場。依次做下去，直

到操場只剩下一個人，記這個人的編號為J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。則

J(400)=______________。

（提示：對N=2m+r 進行分析，其中0≤r2m ）。

四．閱讀程序寫結果（共4 題，每題8 分，共計32 分）

1．#include stdio.h

int main()

{int i,p[5],q[5],x,y=20;

for(i=0;i=4;i++)

scanf(“%d”, p[i]);

q[0]=(p[0]+p[1])+(p[2]+p[3]+p[4])/7;

q[1]=p[0]+p[1]/((p[2]+p[3])/p[4]);

q[2]=p[0]*p[1]/p[2];

q[3]=q[0]*q[1];

q[4]=q[1]+q[2]+q[3];

x=(q[0]+q[4]+2)-p[(q[3]+3)%4];

if(x10)

y+= (q[1]*100-q[3])/(p[p[4]%3]*5);

else

y+=20+(q[2]*100-q[3])/(p[p[4]%3]*5);

printf(“%d,%d\n”, x,y);

return 0;

}

/*註：本例中，給定的輸入數據可以避免分母為0 或數組元素下標越界。*/

輸入：6 6 5 5 3

輸出：_______________

2．#include stdio.h

void fun(int *a,int *b)

{int *k;

k=a; a=b; b=k;

}

main( )

{int a=3,b=6,*x=a,*y=b;

fun(x,y);

printf(“No.1: %d,%d “,a,b);

fun(a,b);

printf(“No.2: %d,%d\n”,a,b);

}

輸出:____________________

3．#include “math.h”

#include “stdio.h”

main()

{int a1[51]={0};

int i,j,t,t2,n=50;

for (i=2;i=sqrt(n);i++)

if(a1[i]==0)

{t2=n/i;

for(j=2;j=t2;j++) a1[i*j]=1;

}

t=0;

for (i=2;i=n;i++)

if(a1[i]==0)

{printf(“%4d”,i); t++;

if(t%10==0) printf(“\n”);

}

printf(“\n”);

}

輸出： ________________________________________

________________________________________

4. #include “stdio.h”

char ch[]={‘q’,’A’,’S’,’O’,’R’,’T’,’E’,’X’,’A’,’M’,’P’,’L’,’E’};

int n=12;

void shift(int k, int n)

{char v;

int j;

v=ch[k]; j=k+k;

while (j=n)

{if((jn) (ch[j]ch[j+1])) j++;

if (vch[j])

{ ch[j/2]=ch[j]; j*=2; }

else

return;

ch[j/2]=v;

}

}

void hpsrt(void)

{int k;

char tmp;

for (k=n/2; k0; k–) shift(k,n); /* 建堆*/

printf(“No.1: “);

for(k=1; k=n; k++) putchar(ch[k]);

putchar(‘\n’);

for (k=n; k0; k–)

{ tmp=ch[1]; ch[1]=ch[k]; ch[k]=tmp;

shift(1,k-1);

}

}

main()

{int k;

hpsrt();

printf(“No.2: “);

for(k=1; k=n; k++) putchar(ch[k]);

putchar(‘\n’);

}

輸出：__________________________________________

___________________________________________

五．完善程序(前5 空，每空2 分，後6 空，每空3 分，共28 分)

1．（格雷碼，Gray Code）

格雷碼是對十進位數的一種二進位編碼。編碼順序與相應的十進位數的大小不一致。其特點是：對於

兩個相鄰的十進位數，對應的兩個格雷碼只有一個二進位位不同。另外，最大數與最小數之間也僅有一個

二進位位不同，以4 位二進位數為例，編碼如下：

十進位數格雷碼十進位數格雷碼

0 0000 8 1100

1 0001 9 1101

2 0011 10 1111

3 0010 11 1110

4 0110 12 1010

5 0111 13 1011

6 0101 14 1001

7 0100 15 1000

如果把每個二進位的位看作一個開關，則將一個數變為相鄰的另一個數，只須改動一個開關。因此，

格雷碼廣泛用於信號處理、數-模轉換等領域。

下面程序的任務是：由鍵盤輸入二進位數的位數n (n16)，再輸入一個十進位數m(0≤m2n)，然

後輸出對應於m 的格雷碼（共n 位，用數組gr[]存放）。

為了將程序補充完整，你必須認真分析上表的規律，特別是對格雷碼固定的某一位，從哪個十進位數

起，由0 變為1，或由1 變為0。

#include stdio.h

main()

{int bound=1,m,n,i,j,b,p,gr[15];

printf(“input n,m\n”);

scanf(“%d%d”,n,m);

for(i=1;i=n;i++) bound= ① ;

if(m0||m=bound)

{printf(“Data error!\n”);

② ;

}

b=1;

for(i=1;i=n;i++)

{p=0; b=b*2;

for( ③ ;j=m;j++)

if( ④ )

p=1-p;

gr[i]=p;

}

for(i=n; ⑤ )

printf(“%1d”,gr[i]); /* 在”%1d” 中出現的是數字1，不是字母l */

printf(“\n”);

}

2．（連續郵資問題）某國發行了n 種不同面值的郵票，並規定每封信最多允許貼m 張郵票，在這

些約束下，為了能貼出{1，2，3,…，maxvalue}連續整數集合的所有郵資，並使maxvalue 的值最

大，應該如何設計各郵票的面值？例如，當n=5、m=4 時，面值設計為{1，3，11，15，32}，可使

maxvalue 達到最大值70（或者說，用這些面值的1 至4 張郵票可以表示不超過70 的所有郵資，但無

法表示郵資71。而用其他面值的1 至4 張郵票如果可以表示不超過k 的所有郵資，必有k≤70）。

下面是用遞歸回溯求解連續郵資問題的程序。數組x[1:n]表示n 種不同的郵票面值，並約定各元

素按下標是嚴格遞增的。數組bestx [1:n]存放使maxvalue 達到最大值的郵票面值（最優解），

數組y[maxl]用於記錄當前已選定的郵票面值x[1:i]能貼出的各種郵資所需的最少郵票張數。請將程

序補充完整。

#include stdio.h

#define NN 20

#define maxint 30000

#define maxl 500 /*郵資的最大值*/

int n,m,bestx[NN],x[NN],y[maxl],maxvalue=0;

void result()

{輸出結果：最大值：maxvalue 及最優解： bestx[1:n]（略）

}

void backtrace(int i,int r)

{ int j,k,z[maxl];

for(j=0;j= ① ;j++)

if(y[j]m)

for(k=1;k=m-y[j];k++)

if(y[j]+k=y[ ② ])

y[ ③ ]=y[j]+k;

while(y[r]maxint) r++;

if(in)

{if(r-1maxvalue)

{maxvalue= ④ ;

for(j=1;j=n;j++)

bestx[j]=x[j];

}

return;

}

for(k=0;kmaxl;k++)

z[k]=y[k];

for(j= ⑤ ;j=r;j++)

{x[i]=j;

⑥ ;

for(k=0;kmaxl;k++)

y[k]=z[k];

}

}

void main()

{int j;

printf(“input n,m:\n”);

scanf(「%d%d」,n,m);

for(j=1;jmaxl;j++)

y[j]=maxint;

y[0]=0; x[0]=0; x[1]=1;

backtrace(2,1);

result();

}

答案:

一、單項選擇題：（每題1.5分）

1. D 2. E 3. D 4. B 5. A

6. B 7. D 8. B 9. D 10. A

二、 不定項選擇題 （共10題，每題1.5分，共計15分。每題正確答案的個數大於或等於1。多選或少選均不得分）。

11. ABC 12. AD 13. ABD 14. ABD 15. BC

16. ABD 17. AB 18. CD 19. BC 20. AC

三、問題求解：（共2題，每題5分，共計10分）

1．350

2．289

四、閱讀程序寫結果（共4題，每題8分，共計32分）

1 129,43

2 No.1:3,6 No.2:3,6

3 2 3 5 7 11 13 17 19 23 29

31 37 41 43 47

4 No.1: XTORSEAAMPLE

No.2: AAEELMOPRSTX

五．完善程序 (前5空，每空2分，後6空，每空3分，共28分)

（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）

1 ① bound*2

② return

③ j=0

④ (j % b-(b / 2))=0

⑤ = 1

2 ① x[i-2]*(m-1)

② j+x[i-1]*k

③ j+x[i-1]*k （同2）

④ r-1

⑤ x[i-1]+1

⑥ backtrace(i+1,r)

2010信息學奧賽初賽試題及答案

NOIP2010（Pascal提高組）

一、單項選擇題

1.與16進位數 A1.2等值的10進位數是 （ ）A.101.2 B.111.4 C.161.125 D.177.25

2.一個位元組（byte）由（ ）個二進位組成。 A.8 B.16 C.32 D.以上都有可能

3.以下邏輯表達式的值恆為真的是（ ）。

A.P∨（┓P∧Q）∨(┓P∧┓Q) B.Q∨（┓P∧Q）∨（P∧┓Q）

C.P∨Q∨（P∧┓Q）∨（┓P∧Q） D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)

4.Linux下可執行文件的默認擴展名是( )。 A. exe B. com C. dll D.以上都不是

5.如果在某個進位下等式7*7=41成立，那麼在該進位下等式12*12=（ ）也成立。

A. 100 B. 144 C. 164 D. 196

6.提出「存儲程序」的計算機工作原理的是（ ）。

A. 克勞德•香農 B.戈登•摩爾 C.查爾斯•巴比奇 D.馮•諾依曼

7.前綴表達式「+ 3 * 2 + 5 12 」 的值是（ ）。A. 23 B. 25 C. 37 D. 65

8.主存儲器的存取速度比中央處理器(CPU)的工作速度慢的多，從而使得後者的效率受到影響。而根據局部性原理，CPU所訪問的存儲單元通常都趨於一個較小的連續區域中。於是，為了提高系統整體的執行效率，在CPU中引入了( )。A.寄存器 B.高速緩存 C.快閃記憶體 D.外存

9.完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上到下、從左到右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置上，則第k號結點的父結點如果存在的話，應當存放在數組中的（ ）號位置。 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2

10.以下競賽活動中歷史最悠久的是（ ）。A. NOIP B.NOI C. IOI D. APIO

二、不定項選擇題

1.元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個出棧的是R3，那麼第5個出棧的可能是( )。A.R1 B.R2 C.R4 D.R5

2. Pascal語言，C語言和C++語言都屬於( )。A.高級語言 B.自然語言 C.解釋性語言 D.編譯性語言

3. 原地排序是指在排序過程中(除了存儲待排序元素以外的)輔助空間的大小與數據規模無關的排序演算法。以下屬於原地排序的有( )。A.冒泡排序 B.插入排序 C.基數排序 D.選擇排序

4. 在整數的補碼錶示法中，以下說法正確的是（ ）。

A．只有負整數的編碼最高位為1 B．在編碼的位數確定後，所能表示的最小整數和最大整數的絕對值相同

C．整數0隻有一個唯一的編碼 D．兩個用補碼錶示的數相加時，若在最高位產生進位，則表示運算溢出

5. 一顆二叉樹的前序遍歷序列是ABCDEFG，後序遍歷序列是CBFEGDA，則根結點的左子樹的結點個數可能是（ ）。 A．0 B. 2 C. 4 D. 6

6. 在下列HTML語句中，可以正確產生一個指向NOI官方網站的超鏈接的是（ ）。

A．a url=」h t t p : / / w w w . n o i . c n」歡迎訪問NOI網站/a

B．a href=」h t t p : / / w w w . n o i . c n」歡迎訪問NOI網站/a

C．ah t t p : / / w w w . n o i . c n/a

D．a name」h t t p : / / w w w . n o i . c n」歡迎訪問NOI網站/a

7. 關於拓撲排序，下列說法正確的是( )。

A．所有連通的有向圖都可以實現拓撲排序

B．對同一個圖而言，拓撲排序的結構是唯一的

C．拓撲排序中入度為0的結點總會排在入度大於0的結點的前面

D．拓撲排序結果序列中的第一個結點一定是入度大於0的點

8. 一個平面的法線是指與該平面垂直的直線。過點(1,1,1)、（0,3,0）、(2,0,0)的平面的法線是（ ）。

A．過點（1，1，1）、（2，3，3）的直線 B．過點（1，1，1）、（3，2，1）的直線

C．過點（0，3，0）、（-3，1，1）的直線 D．過點（2，0，0）、（5，2，1）的直線

9.雙向鏈表中有兩個指針域llink和rlink，分別指向該結點的前驅及後繼。設p指向鏈表中的一個結點，他的左右結點均為非空。現要求刪除結點p，則下列語句序列中正確的是( )。

A．p-rlink-llink=p-rlink;

p-llink-rlink=p-llink; delete p;

B．p-llink-rlink=p-rlink;

p-rlink-llink = p-llink; delete p;

C．p-rlink-llink = p-llink;

p-rlink-llink -rlink = p-rlink; delete p;

D．p-llink-rlink = p-rlink;

p-llink-rlink-link = p-llink; delete p;

10. 今年(2010年)發生的事件有（ ）。

A．惠普實驗室研究員Vinay Deolalikar 自稱證明了P≠NP

B．英特爾公司收購計算機安全軟體公司邁克菲(McAfee)

C．蘋果公司發布iPhone 4手機 D．微軟公司發布Windows 7 操作系統

三、問題求解

1．LZW編碼是一種自適應詞典編碼。在編碼的過程中，開始時只有一部基礎構造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，並用於後繼信息的編碼。

舉例說明，考慮一個待編碼的信息串：「xyx yy yy xyx」。初始詞典只有3個條目，第一個為x,編碼為1；第二個為y，編碼為2；第三個為空格，編碼為3；於是串「xyx」的編碼為1-2-1（其中-為編碼分隔符），加上後面的一個空格就是1-2-1-3。但由於有了一個空格，我們就知道前面的「xyx」是一個單詞，而由於該單詞沒有在詞典中，我們就可以自適應的把這個詞條添加到詞典里，編碼為4，然後按照新的詞典對後繼信息進行編碼，以此類推。於是，最後得到編碼：1-2-1-3-2-2-3-5-3-4。

我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接受方，接收方也只要根據基礎詞典就可以完成對該序列的完全恢復。解碼過程是編碼過程的逆操作。現在已知初始詞典的3個條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼後的信息串是」____________」。

2.無向圖G有7個頂點，若不存在由奇數條邊構成的簡單迴路，則它至多有__________條邊。

3.記T為一隊列，初始時為空，現有n個總和不超過32的正整數依次入列。如果無論這些數具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列T中的數之和恰好為9，那麼n的最小值是___________。

四、閱讀程序寫結果

1.

const

size = 10;

var

i, j, cnt, n, m : integer;

data : array[1..size] of integer;

begin

readln(n, m);

for i := 1 to n do

read(data[i]);

for i := 1 to n do

begin

cnt := 0;

for j := 1 to n do

if (data[i] data[j]) or ((data[j] = data[i]) and (j i))

then inc(cnt);

if cnt = m

then writeln(data[i]);

end;

end.

輸入

5 2

96 -8 0 16 87

輸出：__________

2.

const

size = 100;

var

na, nb, i, j, k : integer;

a, b : array[1..size] of integer;

begin

readln(na);

for i := 1 to na do

read(a[i]);

readln(nb);

for i := 1 to nb do

read(b[i]);

i := 1;

j := 1;

while (i = na) and (j = nb) do

begin

if a[i] = b[j] then

begin

write(a[i],’ ‘);

inc(i);

end

else begin

write(b[j], ‘ ‘);

inc(j);

end;

end;

if i = na then

for k := i to na do

write(a[k], ‘ ‘);

if j = nb then

for k := j to nb do

write(b[k], ‘ ‘);

end.

輸入

5

1 3 5 7 9

4

2 6 10 14

輸出：__________

3.

const

num = 5;

var

n: integer;

function r(n : integer) : integer;

var

i : integer;

begin

if n = num then

begin

r := n;

exit;

end;

for i :=1 to num do

if r(n-i) 0 then

begin

r:=i;

exit;

end;

r:=-1;

end;

begin

readln(n);

writeln(r(n));

end.

輸入 16

輸出：__________

4.

const

size=100;

var

n,m,x,y,i :integer;

r: array[1.. size] of integer;

map : array[1..size, 1..size] of boolean;

found : boolean;

function successful : boolean;

var

i : integer;

begin

for i :=1 to n do

if not map[r[i]][r[i mod n + 1]]

then begin

successful := false;

exit;

end;

successful :=true;

end;

procedure swap(var a, b : integer);

var

t : integer;

begin

t := a;

a := b;

b := t;

end;

procedure perm(left, right : integer);

var

i : integer;

begin

if found

then exit;

if left right

then begin

if successful

then begin

for i := 1 to n do

writeln(r[i], ‘ ‘);

found := true;

end;

exit;

end;

for i:= left to right do

begin

swap(r[left], r[i]);

perm(left + 1, right);

swap(r[left], r[i]);

end;

end;

begin

readln(n, m);

fillchar(map, sizeof(map), false);

for i := 1 to m do

begin

readln(x, y);

map[x][y] := true;

map[y][x] := true;

end;

for i := 1 to n do

r[i] := i;

found := false;

perm(1, n);

if not found

then writeln(‘No soloution’);

end.

輸入:

9 12

1 2

2 3

3 4

4 5

5 6

6 1

1 7

2 7

3 8

4 8

5 9

6 9

輸出：__________

五、完善程序

1.(過河問題) 在一個月黑風高的夜晚,有一群人在河的右岸,想通過唯一的一根獨木橋走到河的左岸.在伸手不見五指的黑夜裡,過橋時必須借照燈光來照明,不幸的是,他們只有一盞燈.另外,獨木橋上最多能承受兩個人同時經過,否則將會坍塌.每個人單獨過獨木橋都需要一定的時間,不同的人要的時間可能不同.兩個人一起過獨木橋時,由於只有一盞燈,所以需要的時間是較慢的那個人單獨過橋所花費的時間.現在輸入N(2=N1000)和這N個人單獨過橋需要的時間,請計算總共最少需要多少時間,他們才能全部到達河左岸.

例如,有3個人甲、乙、丙,他們單獨過橋的時間分別為1 2 4,則總共最少需要的時間為7.具體方法是:甲 乙一起過橋到河的左岸,甲單獨回到河的右岸將燈帶回,然後甲,丙在一起過橋到河的左岸,總時間為2+1+4=7.

const

SIZE = 100;

INFINITY = 10000;

LEFT = true;

RIGHT = false;

LEFT_TO_RIGHT = true;

RIGHT_TO_LEFT = false;

var

n, i : integer;

time : array[1..Size] of integer;

pos :array[1..Size] of Boolean;

function max(a, b :integer) : integer;

begin

if a b then

max := a

else

max := b;

end;

function go(stage : boolean) : integer;

var

i, j, num, tmp, ans : integer;

begin

if (stage = RIGHT_TO_LEFT)

then begin

num := 0;

ans :=0;

for i := 1 to n do

if pos[i] = Rignt then

begin

inc(num);

if time[i] ans then

ans := time[i];

end;

if __________ then

begin

go := ans;

exit;

end;

ans := INFINITY;

for i := 1 to n – 1 do

if pos[i] = RIGHT then

for j := i+1 to n do

if pos[j] = RIGHT then

begin

pos[i] := LEFT;

pos[j] := LEFT;

tmp := max(time[i], time[j]) + _______;

if tmp ans then

ans := tmp;

pos[i] := RIGHT;

pos[j] := RIGHT;

end;

go := ans;

end

else if (stage = LEFT_TO_RIGHT)

then begin

ans := INFINITY;

for i := 1 to n do

if _______ then

begin

pos[i] := RIGHT;

tmp := ________;

if tmp ans then

ans := tmp;

_________;

end;

go := ans;

end

else go := 0;

end;

begin

readln(n);

for i := 1 to n do

begin

read(time[i]);

pos[i] := RIGHT;

end;

writeln(go(RIGHT_TO_LEFT));

end.

一、單項選擇題（共10題，每題1.5分，共計15分）

1 2 3 4 5 6 7 8 9 10

C A A D B D C B C B

二、不定項選擇題（共10題，每題1.5分，共計15分，多選或少選均不得分）

1 2 3 4 5 6 7 8 9 10

ACD AD ABD AC B B D D BCD ABC

三、問題求解（共3題，每題5分，共計15分）

1．yyxy xx yyxy xyx xx xyx 2．12 3．18

四、閱讀程序寫結果（共4題，每題7分，共計28分）

1．16 2．1 2 3 5 6 7 9 10 14 3．4 4．1 6 9 5 4 8 3 2 7

五、完善程序（第1空2分，其餘10空，每空2.5分，共計27分）

（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）

1．① num = 2（或num 3 或num = 2）

② go(LEFT_TO_RIGHT)

③ pos[i] = LEFT（或LEFT = pos[i]）

④ time[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) + time[i]）

⑤ pos[i] := LEFT

本小題中，LEFT可用true代替，LEFT_TO_RIGHT可用true代替，RIGHT_TO_LEFT可用false代替。

2．① opt[k]

② home[r] := k

③ j := i + i（或j := 2 * i 或j := i * 2）

④ swap(i, j)（或swap(j, i)）

⑤ value[i] + heap[1]（或heap[1] + value[i]）

⑥ i – m