信息學(xué)競(jìng)賽普及組初賽模擬試題

1、信息學(xué)競(jìng)賽普及組初賽模擬試題(五)  一、選擇題：（每題1.5分，共計(jì)30分。每題有5個(gè)選項(xiàng)，前10題為單選題，后10題為不定項(xiàng)選擇題，全部選對(duì)才得分）。1. 二進(jìn)制數(shù)11011011的十進(jìn)制值是（  ）A. 202     B. 219    C. 193     D. 2092. 我國(guó)研制的銀河型的超級(jí)計(jì)算機(jī)通過(guò)基準(zhǔn)程序的測(cè)試，其峰值速度是（ 

2、 ）A. 80億次B. 100億次     C. 130億次     D. 150億次3. 程序段如下：FOR I:=1 TO 5 DO     FOR J:=2 TO I DO        Writeln(*)輸出*的個(gè)數(shù)是（

3、  ）A. 5      B. 10      C. 15       D. 25      E. 304. 設(shè)待排序的記錄為（49，38，65，97，76， 13，27 , 49, 55, 4），經(jīng)過(guò)下過(guò)程將序列排序第

4、一趟：13, 27, 49, 55, 4, 49, 38, 65, 97, 76第二趟：13, 4, 49, 38, 27, 49, 55, 65, 97, 76第三趟：4, 13, 27, 38, 49, 49, 55, 65, 76, 97問(wèn)它所用的方法是：(   A. 冒泡排序

5、60;  B. 直接選擇排序   C. 直接插入排序   D. 希爾排序5. 設(shè)無(wú)向樹(shù)T有7片樹(shù)葉，其余頂點(diǎn)度均為3，則T中3度頂點(diǎn)有多少個(gè)（  ）A. 5        B. 7         C. 9    

6、60;    D. 4       E. 86. 設(shè)連通圖G的頂點(diǎn)數(shù)和邊數(shù)與一立方體相同，即有8個(gè)頂點(diǎn)和12條邊。任意一棵G的生成樹(shù)的總邊數(shù)為（  ）A7B. 8     C. 9    D. 10E. 117. 設(shè)有兩個(gè)散列函數(shù)h1(k)=k mod 13 和

7、0;h2(k)=k mod 11 +1，散列表為T(mén)012，用二次散列法解決沖突。函數(shù)h1用來(lái)計(jì)算散列地址，當(dāng)發(fā)生沖突時(shí)，h2作為計(jì)算下一個(gè)探測(cè)地址的地址增量。假定某一時(shí)刻散列表的狀態(tài)為： 0 1  2  3  4  5  6  7  8  9  10  11  12  80   

8、    44          35下一個(gè)被插入的關(guān)鍵碼為57，其插入的位置為(   。A. 4        B. 5        C. 6        D.

9、60;7        E. 8請(qǐng)根據(jù)下面是一段PASCAL程序,判斷第8、9題。for h :=1 to n-1 do beginx :=Ah+1;k :=h;while (k>=1) and (Ak>x) do beginAk+1 :=Ak;k:=k1endAk+1 :=xend8. 假設(shè)在程序開(kāi)始執(zhí)行時(shí)，數(shù)組A1n是一組隨機(jī)整數(shù)。

10、下列答案中，哪一個(gè)最好的描述了最差情況下的程序排序的時(shí)間復(fù)雜度？（  ）A. O(n log2 n)   B. O(n)      C. O(log2n)    D. O(n2)    E. O(2n)9. 假設(shè)在程序開(kāi)始執(zhí)行時(shí)，數(shù)組A1n是按關(guān)鍵字非遞減有序排列時(shí)，下列答案中，哪一個(gè)最好的描述了最好情況下的程序排序的時(shí)間復(fù)雜度

11、？（  ）A. O(n log2 n)   B. O(n)      C. O(log2n)    D. O(n2)    E. O(2n)10.對(duì)下列四個(gè)序列用快速排序方法進(jìn)行排序，以序列的第一個(gè)元素為劃分的基準(zhǔn)，在第一趟劃分過(guò)程中，元素的移動(dòng)數(shù)最多的是哪一個(gè)序列（  ）A. 70 , 

12、65 , 34 , 82 , 53 , 25 , 90B. 82 , 53 , 25 , 70 , 65 , 34 , 90C. 34 , 25 , 53 , 65 , 90 , 82 , 70D. 53 , 

13、25 , 65 , 70 , 34 , 90 , 82E. 65 , 34 , 82 , 70 , 25 , 53 , 9011.在計(jì)算機(jī)運(yùn)行時(shí)，把程序和數(shù)據(jù)一樣存放在內(nèi)存中，這是1946年由_所領(lǐng)導(dǎo)的研究小組正式提出并論證的。（  ）A. 圖靈        

14、;        B. 馮·諾依曼C. 布爾D. 赫夫曼E. 哈希12.下面關(guān)于計(jì)算機(jī)的說(shuō)法正確的是（  ）A. 微機(jī)內(nèi)存容量的基本計(jì)量單位是字節(jié)B. 二進(jìn)制數(shù)中右起第10位上的1相當(dāng)于210C. CPU每執(zhí)行一個(gè)指令，就完成一步基本運(yùn)算或判斷D. 1T=1024MB E. 32位的計(jì)算機(jī)中的“32”指的是字長(zhǎng)13.為什么說(shuō)PASCAL是“高級(jí)語(yǔ)言”，是因?yàn)樗?#160; ）

15、A. 必須在性能較高的機(jī)器上運(yùn)行B. 必須經(jīng)過(guò)良好培訓(xùn)的高水平的程序員使用C. 離機(jī)器的硬件較遠(yuǎn)D. 開(kāi)發(fā)的時(shí)間較長(zhǎng)E. 程序的性能較好14.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)？（  ）A廣義表B. 二叉樹(shù)C. 稀疏矩陣D. 串E. 隊(duì)列15.在下面關(guān)于計(jì)算機(jī)系統(tǒng)硬件的說(shuō)法中不正確的是(  A. 沒(méi)有外部設(shè)備的計(jì)算機(jī)稱(chēng)為祼機(jī)B. 當(dāng)關(guān)閉計(jì)算機(jī)電源后，RAM中的程序和數(shù)據(jù)就消失了C. 軟盤(pán)和硬盤(pán)上的數(shù)據(jù)均可由 CPU直接存取D.&

16、#160;軟盤(pán)和硬盤(pán)驅(qū)動(dòng)器既屬于輸入設(shè)備又屬于輸出設(shè)備E. CPU主要由運(yùn)算器、控制器和寄存器組成16. 下面關(guān)于算法的正確說(shuō)法是（  ）A. 算法必須有輸出B. 算法必須在計(jì)算機(jī)上用某種語(yǔ)言實(shí)現(xiàn)C. 算法不一定有輸入D. 算法必須在有限步執(zhí)行后能結(jié)束E. 算法是程序的靈魂17.以下關(guān)于結(jié)構(gòu)化程序的說(shuō)法中，正確的是（  ）A. 結(jié)構(gòu)化程序是由單入口，單出口和循環(huán)三種結(jié)構(gòu)組成B. 結(jié)構(gòu)化程序是出順序、單入中和單出口三種結(jié)構(gòu)組成C. 結(jié)構(gòu)化程序是由順序、循環(huán)和

17、GOTO語(yǔ)句結(jié)構(gòu)組成D. 結(jié)構(gòu)化程序是由順序、循環(huán)和分支三種結(jié)構(gòu)組成E. “自頂向下，逐步求精”是結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn)18.棧S最多能容納4個(gè)元素。現(xiàn)有6個(gè)元素按1，2，3，4，5，6的順序進(jìn)棧，問(wèn)下列哪一個(gè)序列是可能的出棧序列？（  ）A. 5，4，3，2，1，6B. 3, 2, 5, 4, 1, 6C. 2, 3, 5, 6, 1, 4D. 1, 4, 6, 5, 2,

18、 3E. 4，5，3，6，2，119.下列排序算法中，哪些排序是不穩(wěn)定的（  ）A快速排序B. 基數(shù)排序C. 希爾排序   D. 冒泡排序     E.選擇排序20.下列說(shuō)法正確的是（  ）A. 解釋程序是接受參數(shù)，按照某一樣板產(chǎn)生機(jī)器語(yǔ)言的計(jì)算機(jī)程序B. BASIC語(yǔ)言程序通常需解釋執(zhí)行C. 連接程序可以把經(jīng)編譯程序產(chǎn)生的目標(biāo)程序變成可執(zhí)行的機(jī)器語(yǔ)言程序D. 就執(zhí)行速度而言，編譯程序比

19、解釋程序快E. PASCAL通常是先編譯后執(zhí)行二、問(wèn)題求解題（每題5分，共計(jì)10分）1. 由四個(gè)結(jié)點(diǎn)可以構(gòu)造多少種不同的二叉樹(shù)      .2. 下圖是一個(gè)設(shè)想有11項(xiàng)活動(dòng)的活動(dòng)網(wǎng)。其中有9個(gè)事件V1，V2， V9,每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。V1表示整個(gè)工程的開(kāi)始，V9表示結(jié)束，與每個(gè)活動(dòng)相聯(lián)系的數(shù)ax(x=111)是執(zhí)行該活動(dòng)所需的時(shí)間（單位：天）。問(wèn)完成整項(xiàng)工程至少需要 天，影響工程進(jìn)度的關(guān)鍵活動(dòng)有哪些：  。 

20、60;              V2                     V7 V1            

21、60;         V5                    V9               V3    

22、60;               V8                             V4     

23、;     V6 三、程序閱讀理解題 （每題8分，共計(jì)32分）1program ex11_8;varn,i,j,k,p:longint;beginwrite('N=12'); i:=2;j:=0;k:=1;repeatinc(i);p:=j+k;j:=k;k:=p;until i=12;writeln('F(',12,')=',p);end.運(yùn)行結(jié)果為：        

24、   2program example;varn:byte;a:array1.100 of longint;function f(n:byte):longint;var i:longint;beginif an-1>0 then i:=an-1else i:=f(n-1);if an-2>0 then i:=i+an-2else i:=i+f(n-2);an:=i;f:=i;end;beginfillchar(a,sizeo

25、f(a),0);a1:=1;a2:=1;writeln('F(',8,')=',f(8);end.運(yùn)行結(jié)果為:          3program example3begin  a1:=1;t:=0;for i:=2 to 6 do  begins:=0;for j:=1 to i-1 do  s:=s+aj;

26、60; ai:=s+1;   end;for i:=1 to 6 do  t:=t+ai;writeln(t=,t);end.運(yùn)行結(jié)果為：         4program example4var i,s,max:integer;begin   for i:=1 to 10 do read(ai); 

27、;  max:=a1; s:=a1;   for i:=2 to 10 dobegin if s<0 then s:=0;    s:=s+ai; if s>max then max:=s;end;writeln(max=,max);end.輸入：8 9 1 24 6 5 11 15 2

28、8 9運(yùn)行結(jié)果為：            四、程序完善題 (每題14分，共計(jì)28分)1.n×n方陣的每行每列都是自然數(shù)1.n的一個(gè)全排列，每行（列）無(wú)重復(fù)數(shù)字。例： n5時(shí)，     1 4 3 2 5      5 3 2 1 4 

29、60;    4 2 1 5 3      3 1 5 4 2      2 5 4 3 1輸入 n（>2）和第一行數(shù)字（不檢查錯(cuò)誤）輸出 一個(gè)滿(mǎn)足要求的方陣因?yàn)橹皇且竺啃校校o(wú)重復(fù)數(shù)字，對(duì)第一行的每個(gè)數(shù)字，都四十五度斜向下寫(xiě)，寫(xiě)到行盡頭就從行開(kāi)頭開(kāi)始。這樣就不會(huì)重復(fù)。對(duì)于經(jīng)過(guò)第y行，第x

30、列的直線，斜率k=1設(shè)：y=x+b代入坐標(biāo)，得出：b=y-x令y=1，取首行的數(shù)：x=y-bx從1開(kāi)始，到n,如果x為0或負(fù)數(shù)，則x=x+n，取出第一行的數(shù)。程序只用一維數(shù)組，存第一行的數(shù)字。program example2;const    maxn=10000;var     a:array1.maxn of integer;     x,y,n:integer;function f(x,y:integer):i

31、nteger;var   b:integer;begin        (1)            (2)       if x<=0 then      (3)    &

32、#160;  f:=ax;end;begin    write('Enter n:');  readln(n);    if (n<2) or (n>maxn) then exit;    write('Enter first line:');    for x:=

33、1 to n do read(ax);    writeln('Output:');    for x:=1 to n do write(ax:4);    writeln;    for y:=2 to n do      begi

34、n         for x:=1 to n do write(  (4)   :4);         writeln;      end;end.2程序說(shuō)明 設(shè)有個(gè)人依次圍成一圈，從第個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到第個(gè)人出列，然后從出列的下一個(gè)人開(kāi)始報(bào)數(shù)，

35、數(shù)到第個(gè)人又出列，如此反復(fù)到所有的人全部出列為止。設(shè)個(gè)人的編號(hào)分別為1，2，n，打印出出列的順序。本題用數(shù)組建立標(biāo)志位等方法求解,用數(shù)組實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)。 數(shù)組ai作為"指針"變量來(lái)使用，ai存放下一個(gè)結(jié)點(diǎn)的位置。設(shè)立指針j指向當(dāng)前結(jié)點(diǎn)，則移動(dòng)結(jié)點(diǎn)過(guò)程為j:=aj，當(dāng)數(shù)到m時(shí)，m結(jié)點(diǎn)出鏈，則aj:=aaj。程序program example;const n=14;m=4; var a:array1.n of integer;i,j,k,p:integer;beginfor i:=1 to&

36、#160;n-1 do ai:=i+1;    an:=1;  (1)  k:=1;p:=0; repeat      (2)  k:=k+1;if k=m then       beginwrite(aj:4);p:=p+1;  (3)    (4)

37、0;  enduntil p=n;end.參考答案一、選擇題：（每題1.5分，共計(jì)30分。每題有5個(gè)選項(xiàng)，前10題為單選題，后10題為不定項(xiàng)選擇題，全部選對(duì)才得分）。 題號(hào) 1 2 3 4 5 6 7 8 9 10    答案 B C B D A A E D B E    題號(hào)&

38、#160;11 12 13 14 15 16 17 18 19 20    答案 B ACE C DE AC ABCDE DE BE AC BCDE  二、問(wèn)題求解題（每題5分，共計(jì)10分）   1、      14   

39、0;      2、  19   ,（2分）     a1,a4,a7,a10  （3分）三、程序閱讀理解題 （每題8分，共計(jì)32分） 1、F（12）=89 2、F（8）=21    3、t=63    4、max=77       

40、60;四、程序完善題 (每題14分，共計(jì)28分) 1、       b:=y-x;                         x:=1-b;         

41、60;              x:=x+n                        f(x,y)         

42、60;          2、       j:=n                         j:=aj;     

43、60;            aj:=aaj;           k:=1;                   grundfos 發(fā)表于 >2004-10-18 10:1

44、6:57 全文 評(píng)論 引用 推薦 檔案 推給好友  2004-10-18信息學(xué)競(jìng)賽普及組初賽模擬試題(四)信息學(xué)競(jìng)賽普及組初賽模擬試題(四)    一、 選擇題：（選出每題正確的答案代碼，填在括號(hào)里，110題為單選題，每小題只有一個(gè)正確答案，1120題為不定項(xiàng)選擇題，每小題有一個(gè)或一個(gè)以上的正確答案，共20題，每題1.5，共30分）1、二進(jìn)制數(shù)01100100轉(zhuǎn)換成十六進(jìn)制數(shù)是（     ）。A32     B64  

45、;   C128     D100     E2562、操作系統(tǒng)是一類(lèi)重要的系統(tǒng)軟件，下面幾個(gè)軟件中，不屬于系統(tǒng)軟件的是（     ）。AJava     BMS-DOS     CLinux     DWindows2000   

46、0; EUnix3、計(jì)算機(jī)病毒的傳染是以計(jì)算機(jī)運(yùn)行和（     ）為基礎(chǔ)的，沒(méi)有這兩個(gè)條件，病毒是不會(huì)傳染的。A編輯文稿     B讀寫(xiě)磁盤(pán)     C編程序     D掃描圖畫(huà)     E打印4、因特網(wǎng)不屬于任何個(gè)人，也不屬于任何組織。其中在網(wǎng)絡(luò)知識(shí)這一塊中有一個(gè)英文簡(jiǎn)寫(xiě)ISP，它的中文意思是（   

47、60; ）。A因特網(wǎng)連接  B因特網(wǎng)使用  C因特網(wǎng)設(shè)計(jì)  D因特網(wǎng)服務(wù)提供者  E信息傳輸5、Internet給我們提供了資源共享、瀏覽、檢索信息和遠(yuǎn)程登錄等多種服務(wù)，下面幾個(gè)選項(xiàng)中用于遠(yuǎn)程登錄的是（     ）。AWWW   BTCP/IP   CTelnet   DE-mail   EFTP6、IE是目前流行的瀏覽器軟件，它的工作基

48、礎(chǔ)是解釋執(zhí)行用（     ）語(yǔ)言書(shū)寫(xiě)的文件。AVC     BHTML     CBASIC     DHTTP     EVB7、給出3種排序：插入排序、冒泡排序、選擇排序。這3種排序的時(shí)間代價(jià)分別是（     ）。AO(n)、O(n2)、O(logn)   

49、0;BO(logn) 、O(n)、O(n2)    CO(n2)、O(n)、O(logn)DO(n2)、O(n)、O(n)       EO(n2)、O(n2)、O(n2)8、一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為18，其葉結(jié)點(diǎn)數(shù)為（     ）。A7個(gè)   B8個(gè)   C9個(gè)   D10個(gè)   E11個(gè)9、在流程圖的符

50、號(hào)中，菱形框一般作為（     ）。A起始框     B判斷框   C輸入輸出框   D處理工作框   E結(jié)速框10、在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主要將要輸出打印的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)（     ）結(jié)構(gòu)。A堆棧   B數(shù)組 &

51、#160; C線性表   D隊(duì)列   E鏈表11、多媒體技術(shù)中的“多媒體”的含義主要是指如（     ）等多種表達(dá)信息的形式。A磁盤(pán)    B音箱   C顯示器    D聲音    E圖像12、下面有關(guān)計(jì)算機(jī)知識(shí)說(shuō)明，正確的是（     ）。A 在WINDOWS98操作

52、系統(tǒng)下，刪除磁盤(pán)中的文件時(shí)都先存放在回收站中B FOXMAIL是用于收發(fā)電子郵件的工具C 文件夾組織是一個(gè)有層次的樹(shù)狀結(jié)構(gòu)，其中最頂層的是桌面D存儲(chǔ)器具有記憶能力，其中的信息任何時(shí)候都不會(huì)丟失E 為了提高軟件的測(cè)試效率，應(yīng)該選擇發(fā)現(xiàn)錯(cuò)誤的可能性大的測(cè)試數(shù)據(jù)13、對(duì)按關(guān)鍵字排序好的線性表進(jìn)行二分查找，該線性表適合的存儲(chǔ)結(jié)構(gòu)為（     ）。A鏈接存儲(chǔ)     B索引存儲(chǔ)     C散列存儲(chǔ)  

53、60;  D順序存儲(chǔ)     E循環(huán)存取14、一個(gè)棧的輸入順序?yàn)?、2、3、4、5，下列序列中可能是棧的輸出序列的是（     ）。A54312     B24135     C21543     D12534      E1234515、評(píng)價(jià)一個(gè)算法的好壞有多種指標(biāo)，

54、下列是算法評(píng)價(jià)指標(biāo)的是（     ）。A 正確性     B運(yùn)行時(shí)間     C占用空間     D迭代次數(shù)     E簡(jiǎn)單性16、下面描述用多維數(shù)組表示的數(shù)據(jù)結(jié)構(gòu)的語(yǔ)句中，正確的是（    ）。A 多維數(shù)組存放的都是同一種類(lèi)型的數(shù)據(jù)B 多維數(shù)組各維的下標(biāo)范圍必須一樣C 

55、;多維數(shù)組在內(nèi)存中的地址是連續(xù)的D 多維數(shù)組中的下標(biāo)不能是表達(dá)式E 多維數(shù)組是隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)17、若已知一個(gè)棧的入棧順序1，2，3，n，其輸出序列為P1，P2，P3，Pn（它是輸入序列的一個(gè)排列），則在輸出序列中可能出現(xiàn)的情況是（     ）。APj<Pk<Pi，其中i<j<kBPk< Pj<Pi，其中i<j<kCPj<Pi<Pk，其中i<j<kDPi<Pk< Pj，其中i<j<kE以上都不可能出現(xiàn)18、線

56、性表具有如下的結(jié)構(gòu)特點(diǎn)：（     ）A均勻性     B單一性     C簡(jiǎn)單性     D無(wú)序性     E有序性19、下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是（    ）。A數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合B線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C隊(duì)列是限定僅在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表D二維數(shù)組是

57、其數(shù)據(jù)元素為線性表的線性表E圖是一種非線性數(shù)據(jù)結(jié)構(gòu)20、任意一棵樹(shù)均可惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)中，頂點(diǎn)N的左右子女分別是N在原樹(shù)里對(duì)應(yīng)頂點(diǎn)的（     ）。A 最左子頂點(diǎn)/最鄰近的右兄弟B 最右子頂點(diǎn)/最右的兄弟C最鄰近的右兄弟/最左的兄弟D最鄰近的左兄弟/最鄰近的右兄弟F 最鄰近的右兄弟/最右的兄弟二、 問(wèn)題解答：（共2題，每題5分，共10分）1、 光明中學(xué)開(kāi)設(shè)數(shù)學(xué)、英語(yǔ)和信息學(xué)三個(gè)興趣學(xué)習(xí)小組，其中數(shù)學(xué)小組30人，英語(yǔ)小組15人，信息學(xué)小組18人，參加三個(gè)小組總?cè)藬?shù)為

58、50人，其中有3人同時(shí)參加3個(gè)小組，那么同時(shí)只參加兩個(gè)小組的同學(xué)有多少人？ 2、 給出一組頂點(diǎn)（頂點(diǎn)值用A，B，C，D，E，F(xiàn)表示），其對(duì)應(yīng)權(quán)值分別為2，3，1，7，8，4。請(qǐng)以A，B，C，D，E，F(xiàn)為葉子頂點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，并求出它的最小帶權(quán)路徑長(zhǎng)度WPL的值。三、 寫(xiě)出程序的運(yùn)行結(jié)果（共4題，每題8分，共32分）第1題：program test1；var n：integer；function count(n：integer)：integer；begin  if n=1 then 

59、count：=0  elseif n mod 2=0 then count：=count(n div 2)+1else count：=count(n*3+1)+1；end；begin  readln(n)；  writeln(count(n)；end.輸入：99輸出：第2題：program test2(input,output);vari,j,k,s:integer;begins:=0for i:=3 downto 

60、1 do  begin    for j:=1 to 3 do       begin         k:=0;         repeat        

61、   k:=k+1;s:=s+k;         until k=j;       end;     s:=s-(k+1);  end;write(s=,s);end.輸出：第3題：program test3;var a,b,n:longint;begin  readln(n);

62、0; a:=0;b:=0;  repeata:=a+1;b:=b+a;  until b>=n;  writeln(a);end.輸入：415377輸出：program test4;var m,n,i,p,k：integer;r:array1200 of integer;b:Boolean;beginm:=6;n:=2;for I:=1 to m-1 do ri:=i+1;rm:=1;i:=0;p:=1;b:=true;

63、while b dobegin  i:=i+1;k:=p;p:=rp;if k=p thenbegin writeln(p);b:=false end  else if i=n+1 thenbegin  write(p,  );i:=0;p:=rp;rk:=p;end  endend.輸出：四、完善程序（共2題，每題14分，共28分）第1題（7分）    【問(wèn)題描述】

64、設(shè)有n種物品，每種物品有一個(gè)重量及一個(gè)價(jià)值。但每種物品的數(shù)量是無(wú)限的，同時(shí)有一個(gè)背包，最大載重量為XK，今從n種物品中選取若干件（同一種物品可以多次選?。蛊渲亓康暮托∮诘扔赬K，而價(jià)值的和為最大?！境绦蚯鍐巍縋rogram package;  const maxxk=400;maxn=20;  type tlist=array1maxn of byte;tmake=array0maxn,0maxxk of integer;var n,xk:integer; &#

65、160;  w,u:tlist;    f:tmake;procedure init;  var i:byte;begin  fillchar(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,xk);for i:=1 to n do             &#

66、160;      end;  procedure make;  var i,j:byte;  beginfor i:=1 to n dobegin  for j:=1 to wi-1 do    fi,j:=fi-1,j;  for j:=wi to xk 

67、do  if fi-1,j>fi,j-wi+ui then                                         &#

68、160; else                         end;  end;  procedure print;var get:tlist;   i,j:byte;begin  fillchar(get,sizeof(

69、get),0);    i:=                   j:=                       while 

70、;i>0 do       if fi,j=fi-1,j then dec(i)         else begin             dec(j,wi);       

71、60;                                end;     writeln(n=,n, , xk=,xk);     writeln

72、(max worth=,                      for i:=1 to n dowriteln(no.,i, weight:,wi:2, worth:,ui:2, get,geti:2);end;begin  init;  make;pri

73、nt;end.第2題（7分）【問(wèn)題描述】給定一個(gè)01串，請(qǐng)你找出長(zhǎng)度介于a,b之間，重復(fù)出現(xiàn)次數(shù)最多的01串。輸入：a,b(0<a<=b<=12)      由0，1組合的數(shù)列，由.結(jié)尾。輸出：要求的串。提示：本程序中將01序列轉(zhuǎn)換為2進(jìn)制數(shù)存取。【程序清單】program shuchuan;var i,j,s,k,a,b,max:integer;  m:array18192 of integer;  two,v:array120

74、0;of integer;  c:char;begin  for i:=1 to 13 do                readln(a,b);read(c);s:=1;k:=1;while c<>.do begin  s:=s shl 1+ord(c)-48; 

75、 if                then    s:=(s-twob+1) mod twob)+twob;  inc(ms);  if k<b then   for i:=a to k-1 do   

76、;               inc(k); read(c);end;for i:=twob to twob+1 do  if mi>0 then    for j:=a to b-1 do      m(i&#

77、160;mod twoj)+twoj:=             max:=0;for i:=twoa to twob+1 do  if mi>max then                  

78、;  for i:=twoa to twob+1 do  if mi=max then begin    j:=0;k:=I;    repeat    inc(j);vj:=k mod 2;             &

79、#160;     until               while j>0 do begin write(vj);dec(j) end;  writeln;end;end.信息學(xué)命題(四)參考答案一、 選擇題：（選出每題正確的答案代碼，填在括號(hào)里，110題為單選題，每小題只有一個(gè)正確答案，1120題為不定項(xiàng)選

80、擇題，每小題有一個(gè)或一個(gè)以上的正確答案，共20題，每題1.5，共30分） 題號(hào) 1 2 3 4 5 6 7 8 9 10    答案 B A B D C B E C B D    題號(hào) 11 12 13 14 15 16 17 1

81、8 19 20    答案 DE BCE D CE ABCE ACE BCD AE ACDE A  二、問(wèn)題解答：（共2題，每題5分，共10分）第1題：7第2題：61三、寫(xiě)出程序的運(yùn)行結(jié)果：（共4題，每題8分，共32分） 第1題：25 第2題：s=18    第3題：     911 第4題：4&#

82、160; 2  1  3  6  5  四、完善程序（共2題，每題14分，共28分）第1題：          read(wi,ui)fi,j:=fi-1,jfi,j:=fi,j-wi+uii:=nj:=xkinc(geti)fn,xk第2題：            &

83、#160;   twoi:=1 shl i；s>=twob+1(或k>b)inc（m(s mod twoi)+twoi）m(i mod twoj)+twoj+mimax:=mik:=k div 2k=1 信息學(xué)競(jìng)賽普及組初賽模擬試題(三)  一、選擇一個(gè)正確答案代碼（A/B/C/D），填入每題的括號(hào)內(nèi)（每題1.5分，多選無(wú)分，共30分）1、MAN英文縮寫(xiě)的含義是（ ）A.局域網(wǎng)  B.城域網(wǎng)  

84、  C.廣域網(wǎng)  D.增值網(wǎng)2、小張用十六進(jìn)制，八進(jìn)制和十進(jìn)制寫(xiě)了如下一個(gè)等式：6413=33式中三個(gè)數(shù)是各不相同進(jìn)位制的數(shù)，試問(wèn)64，13，33，分別為_(kāi)。A八進(jìn)制，十進(jìn)制，十六進(jìn)制     B十進(jìn)制，十六進(jìn)制，八進(jìn)制C八進(jìn)制，十六進(jìn)制，十進(jìn)制     D十進(jìn)制，八進(jìn)制，十六進(jìn)制3、表達(dá)式(4 MOD (3)與(4 MOD 3)的值為：_。A1，1     

85、0;B1，1      C1，1        D1，14、試指出：下列if語(yǔ)句中，當(dāng)x=80時(shí), 運(yùn)行的結(jié)果為_(kāi)。beginy:=0;readln(x);if x<0  then y:=5else    if x<10  then begin      &

86、#160;     y:=10;            if x<100  then y:=100;            end    else y:=200;write('y=',y);end.

87、Ay=9          By=200        Cy=10       Dy=100       5、設(shè)棧S的初始狀態(tài)為空，現(xiàn)有5個(gè)元素組成的序列1，2，3，4，5，對(duì)該序列在S棧上依次進(jìn)行如下操作(從序列中的1開(kāi)始，出棧后不再進(jìn)棧)：進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，出棧，

88、進(jìn)棧，試問(wèn)出棧的元素序列是_。A5，4，3，2，1    B2，1    C2，3     D3，4 6、ASCII碼是（     ）。A國(guó)標(biāo)碼    B二進(jìn)制編碼  C十進(jìn)制編碼  D美國(guó)標(biāo)準(zhǔn)信息交換碼7、一臺(tái)計(jì)算機(jī)的字長(zhǎng)是4個(gè)字節(jié)，這意味著（     ）。A能處理的數(shù)值最大為

89、4位十進(jìn)制數(shù)9999B能處理的字符串最多由4個(gè)英文字母組成C在CPU中能夠同時(shí)處理32位二進(jìn)制數(shù)據(jù)D在CPU中運(yùn)算的最大結(jié)果為2的32次方8、假設(shè)一臺(tái)計(jì)算機(jī)的地址總線為16，那么中央處理器CPU能訪問(wèn)的最大存儲(chǔ)器容量為(    A 2 * 16 KBB16KB C216B D16*1024*8 B9、計(jì)算機(jī)最終處理的信息形式是（   ）AASCII碼     BBCD碼   &

90、#160; C二進(jìn)制     D十六進(jìn)制10、與十六進(jìn)制數(shù)6F等值的八進(jìn)制數(shù)是（    ）A166    B139     C157     D18311、以下屬非法用戶(hù)自定義標(biāo)識(shí)符的是()。Adate Bdir Clist Dtype 12、設(shè)X和Y是同一種枚舉類(lèi)型變量，則下列語(yǔ)句中合法的是()。AX:=ORD(Y)

91、BX:=Y CREAD(X,Y)DWRITE(T,Y)13、計(jì)算機(jī)能夠直接識(shí)別和處理的程序是_程序A匯編語(yǔ)言  B源程序  C.機(jī)器語(yǔ)言  D.高級(jí)語(yǔ)言14、設(shè)有說(shuō)明    VAR A：ARRAY'A''E'，14，BOOLEAN OF REA1；    則A'A'，3是(    。A一個(gè)實(shí)型的數(shù)組元素B一個(gè)數(shù)組，該數(shù)組具有兩個(gè)實(shí)

92、型數(shù)組元素C一個(gè)數(shù)組，該數(shù)組具有4*2個(gè)實(shí)型數(shù)組元素D一個(gè)數(shù)組，該數(shù)組具有5*4*2個(gè)實(shí)型數(shù)組元素15、下列屬于線性時(shí)間的排序算法是： （    ）A. 快速排序B. 桶排序C. 冒泡排序     16、一棵包含n個(gè)節(jié)點(diǎn)的樹(shù)有幾條邊： A. nB. n-1C. 不一定    17、在Pascal語(yǔ)言中，表達(dá)式35 div 3 mod 4 

93、的值是 _。ABCD 18、在數(shù)據(jù)結(jié)構(gòu)中，"樹(shù)"結(jié)構(gòu)下層結(jié)點(diǎn)出現(xiàn)三個(gè)以上的結(jié)點(diǎn)，這種結(jié)構(gòu)稱(chēng)為_(kāi)。A三層樹(shù)  B三叉樹(shù) C多層樹(shù)  D多叉樹(shù)19、在Pascal語(yǔ)言中，下列程序段所計(jì)算的公式是_。程序段： S：=0 ；T：=1；For I：=1 to 10 doBeginT：=T*I；S：=S+T；end;A.S=1+2+3+4+10B.S=1*2*3*4*10C.S=1！+2！+3！+4！+10！D.S=1+2*3+3*4+4*5+10*1120

94、、以下說(shuō)法正確的是（     ）。 A CPU與內(nèi)存不交換信息       B  CPU與內(nèi)存直接交換信息C CPU與內(nèi)存間接不交換信息   D  CPU與內(nèi)存部分交換信息二、閱讀下列程序，寫(xiě)出程序運(yùn)行結(jié)果（第1題5分，第2，3，4題各6分，共23分）program exp1;const n=5;var I,j,k:integer; &#

95、160;  r:array0.10 of integer;beginfor I:=1 to n do  read(rI);for I:=2 to n dobegin    k:=rI;j:=I-1;    while (k>rj) and (j>0) do      

96、begin rj+1:=rj;j:=j-1;end;    rj+1:=k;  end;for I:=1 to n do  write(rI,);writelnend.鍵盤(pán)輸入: 8 4 9 3 5屏幕輸出：program exp2;var a,b,f:integer;  function gd(m,n:integer):integer;beginif n=

97、0 then gd:=m      else gd:=gd(n,m mod n);end;begin  readln(a,b);  write(,a,b,)=);  f:=gd(a,b);  writeln(f)end.鍵盤(pán)輸入: 172 16屏幕輸出：3、Program exp3(input,output); VAR I,J,S:INTEGER; 

98、;   B :ARRAY0.5 OF INTEGER;BEGIN     S:=1;     FOR I:=1 TO 5 DO   BI:=I;     J:=1;     WHILE J>0 DO    

99、; BEGIN          J:=5;          WHILE (J>0) AND (BJ=10+J-5) DO J:=J-1;          IF J>0 THEN  &

100、#160;          BEGIN                  S:=S+1;  BJ:=BJ+1;               

101、0;  FOR i:=J+1 TO 5 DO  Bi:=BJ+i-J             END;     END;     WRITELN('S=',S);END.4、program exp4(input,output);var m,n,g:int

102、eger;function gcd(m,n:integer):integer;begin if n=0 then gcd:=m  else gcd:=gcd(n,m mod n)end;begin read(m,n); g:=gcd(m,n); writeln('m=',m,'n=',n,'gcd=',g)end.輸入：48  9輸出： 三、問(wèn)題解答（第1題每空4分，第2題8分）1、數(shù)據(jù)結(jié)

103、構(gòu)中，下面是一個(gè)樹(shù)結(jié)構(gòu)圖，這個(gè)樹(shù)的"先序遍歷"結(jié)果是_，中序遍歷結(jié)果是：_。24  8  +3  *4  10  7  -*/2、給出一個(gè)后綴算術(shù)表達(dá)式為 寫(xiě)出對(duì)應(yīng)的中綴算術(shù)表達(dá)式：_四、完善程序（第一題每空3分，第二題每空2分，第三題每空4分，共32分 ）1、連續(xù)整數(shù)平臺(tái)問(wèn)題已知一個(gè)含有多個(gè)整數(shù)的數(shù)組，其中相同的元素集中在一起形成一個(gè)平臺(tái)。以下程序用于對(duì)輸入的數(shù)組求出其中最大平臺(tái)長(zhǎng)度。例如，中元素個(gè)數(shù)為20，它們依次為2 &

104、#160;2  2  2  3  3  3  3  3  1  1  1  1  1  1  1  1  1  4  4則它的最大平臺(tái)長(zhǎng)度為9。const maxlength=100;var  a:array1

105、.maxlength of integer;  i,maxi,n,s,t:integer;begin  write('n=');readln(n);  for i:=1 to n do read(ai);  readln;  maxi:=0;  t:=   1    s:=1;  for i:

106、=2 to n do    if ai=t then   2        else        begin          if s>maxi then maxi:=s;

107、0;         t:=ai;            3          end;    4    writeln('maxi=',maxi);end. 2、1000！尾0問(wèn)題以下程序用于統(tǒng)計(jì)1000！末尾有多少個(gè)0。其中1000！=1&acute;2&acute;3&acute;&acute;1000。實(shí)際上我們只要統(tǒng)計(jì)1000！有多少個(gè)因子10。由于10=5&acute;2，因而只需統(tǒng)計(jì)有多少個(gè)因子5和2。顯然在11000的所有數(shù)中，5的因子個(gè)數(shù)比2