1、信息學初賽模擬試題（一）（普與組PASCAL語言二小時完成 滿分100分）一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內（每題1.5分，多選無分，共30分）1、MAN英文縮寫的含義是（）A.局域網 B.城域網    C.廣域網 D.增值網2、小張用十六進制，八進制與十進制寫了如下一個等式：6413=33式中三個數是各不相同進位制的數，試問64，13，33，分別為_。A八進制，十進制，十六進制 B十進制，十六進制，八進制C八進制，十六進制，十進制 D十進制，八進制，十六進制3、表達式(4 MOD (3)與(4 MOD 3)的值為：_。A1，1 B1，1

2、 C1，1 D1，14、試指出：下列if語句中，當x=80時, 運行的結果為_。beginy:=0;readln(x);if x<0 then y:=5else if x<10 then begin y:=10; if x<100 then y:=100; end else y:=200;write('y=',y);end.Ay=9 By=200 Cy=10 Dy=100 5、設棧S的初始狀態為空，現有5個元素組成的序列1，2，3，4，5，對該序列在S棧上依次進行如下操作(從序列中的1開始，出棧后不再進棧)：進棧，進棧，進棧，出棧，進棧，出棧，進棧，試問出棧的

3、元素序列是_。A5，4，3，2，1 B2，1 C2，3 D3，46、ASCII碼是（ ）。A國標碼 B二進制編碼 C十進制編碼 D美國標準信息交換碼7、一臺計算機的字長是4個字節，這意味著（ ）。A能處理的數值最大為4位十進制數9999B能處理的字符串最多由4個英文字母組成C在CPU中能夠同時處理32位二進制數據D在CPU中運算的最大結果為2的32次方8、假設一臺計算機的地址總線為16，那么中央處理器CPU能訪問的最大存儲器容量為( )A 2 * 16 KBB16KB C216B D16*1024*8 B9、計算機最終處理的信息形式是（ ）AASCII碼   &#

4、160; BBCD碼     C二進制     D十六進制10、與十六進制數6F等值的八進制數是（ ）A166    B139     C157     D18311、以下屬非法用戶自定義標識符的是()。Adate Bdir Clist Dtype 12、設X與Y是同一種枚舉類型變量，則下列語句中合法的是()。AX:=ORD(Y)BX:=Y CREAD(X,Y)DWRITE(T,Y)13、計算機能夠直接識別與處理的程序是_程序

5、A匯編語言 B源程序 C.機器語言 D.高級語言14、設有說明 VAR A：ARRAY'A''E'，14，BOOLEAN OF REA1； 則A'A'，3是( )。A一個實型的數組元素B一個數組，該數組具有兩個實型數組元素C一個數組，該數組具有4*2個實型數組元素D一個數組，該數組具有5*4*2個實型數組元素15、下列屬于線性時間的排序算法是： （ ）A. 快速排序B. 桶排序C. 冒泡排序 16、一棵包含n個節點的樹有幾條邊： A. nB. n-1C. 不一定 17、在Pascal語言中，表達式35 div 3 mod 4 的值是 _。ABCD

6、 18、在數據結構中，"樹"結構下層結點出現三個以上的結點，這種結構稱為_。A三層樹 B三叉樹 C多層樹 D多叉樹19、在Pascal語言中，下列程序段所計算的公式是_。程序段： 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、以下說法正確的是（ ）。A CPU與內存不交換信息 B CPU與內存直接交換信息C CPU與內存間接不交換信息 D CPU與內存部分交換信息二、閱讀下列

7、程序，寫出程序運行結果（第1題5分，第2，3，4題各6分，共23分）program exp1;const n=5;var I,j,k:integer; 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 begin rj+1:=rj;j:=j-1;end; rj+1:=k; end;for I:=1 to n do write(rI,);writelnend.鍵盤輸入: 8 4 9 3 5屏幕輸出：pro

8、gram exp2;var a,b,f:integer; function gd(m,n:integer):integer;beginif n=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.鍵盤輸入: 172 16屏幕輸出：3、Program exp3(input,output); VAR I,J,S:INTEGER; B :ARRAY0.5 OF INTEGER;BEGIN S:=1; FOR I:=1 TO 5 DO BI:=I; J:

9、=1; WHILE J>0 DO BEGIN J:=5; WHILE (J>0) AND (BJ=10+J-5) DO J:=J-1; IF J>0 THEN BEGIN S:=S+1; BJ:=BJ+1; FOR i:=J+1 TO 5 DO Bi:=BJ+i-J END; END; WRITELN('S=',S);END.4、program exp4(input,output);varm,n,g:integer;function gcd(m,n:integer):integer;beginif n=0 then gcd:=m else gcd:=gcd(n

10、,m mod n)end;beginread(m,n);g:=gcd(m,n);writeln('m=',m,'n=',n,'gcd=',g)end.輸入：48 9輸出：三、問題解答（第1題每空4分，第2題8分）1、數據結構中，下面是一個樹結構圖，這個樹的"先序遍歷"結果是_，中序遍歷結果是：_。24 8 +3 *4 10 7 -*/2、給出一個后綴算術表達式為寫出對應的中綴算術表達式：_四、完善程序（第一題每空3分，第二題每空2分，第三題每空4分，共32分 ）1、連續整數平臺問題已知一個含有多個整數的數組，其中相同的元素集中

11、在一起形成一個平臺。以下程序用于對輸入的數組求出其中最大平臺長度。例如，中元素個數為20，它們依次為2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1 1 4 4則它的最大平臺長度為9。const maxlength=100;var a:array1.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:=2 to n do if ai=t then

12、2 else begin if s>maxi then maxi:=s; t:=ai; 3 end; 4 writeln('maxi=',maxi);end.2、1000！尾0問題以下程序用于統計1000！末尾有多少個0。其中1000！=1´2´3´´1000。實際上我們只要統計1000！有多少個因子10。由于10=5´2，因而只需統計有多少個因子5與2。顯然在11000的所有數中，5的因子個數比2的因子個數少。因此，只要統計11000的所有數中共有多少個因子5就行了。var i,j,n:integer;begin n:=

13、0; for i:=1 to 200 do begin j:=i*5; while 5 =0 do begin n:=n+1; j:= 6 end; end; writeln(n:4);end.3、問題描述找數問題: 以下程序用在n個不同元素中找出第k個最小元素。程序中用分治策略來設計算法。把這n個元素放在一個數組中,然后取出第k個元素為標準m,把n個元素重新排列:小于標準m的元素放在數組前面,大于該標準的放在數組的后面。把該元素m放在兩者之間。設小于標準的元素個數為j-1,如果j=k,則A(k)即為所求元素。如果j>k,則第k個元素必在區間1,j,因此取A1,Aj為新的元素集合,然后重

14、復上述的”部分排序”的過程。如果j<k,則第k個元素必在區間j+1,n,因此取Aj,An為新的元素集合,重復過程。直至j=k為止。程序清單var j,k,n:integer; a:array1.100 of integer;procedure search(b,e:integer);var I,m,t:integer;begin if b=e then begin j:=b;exit end; I:=b;j:=e;m:= 7 ; RepeatWhile aI<m do inc(i);While m<aj do 8 ;If I<j then Begin t:=aI;aI:

15、=aj;aj:=t end;Until I>=j;If I=k then exit;If 9 then search(b,j) else search(j+1,e)End;procedure 10 var I:integer; beginfor I:=1 to n do write(aI,);writeln;writeln(a,k,=,ak);end;beginwrite(n=);readln(n);write(a1.,n,=);for k:=1 to n do read(ak);readln;write(k=);readln(k);search( 11 );pr(n);readlnen

16、d.信息學競賽初賽模擬試題（一）參考答案一、 單項選擇題（每題1分，共30分）12345678910DCBBDDCCCC111281920DBCBBBCDDB二、閱讀下列程序，寫出程序運行結果（第1題5分，第2，3，4題各6分，共23分）1、 985431、 （172，16）=43、 S=2524、 m=48n=9gcd=3三、問題解答（第1題每空4分，第2題8分）1、 ABCDE BADCE 2、(24+8)*3/4*(10-7)四、完善程序（第一題每空3分，第二題每空2分，第三題每空4分，共32分 ）(1) a1 (2)s:=s+1 (3)s:=1 (4)if s>maxi then

17、 maxi:=s; (5) j mod 5 (6) j div 5 (7) ak(8)de(j) (9)j>k (10)pr(n:integer); (11)Ln信息學初賽模擬試題(二)一、 選擇題：（選出每題正確的答案代碼，填在括號里，110題為單選題，每小題只有一個正確答案，1120題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分）1、二進制數01100100轉換成十六進制數是（ ）。A32 B64 C128 D100 E2562、操作系統是一類重要的系統軟件，下面幾個軟件中，不屬于系統軟件的是（ ）。AJava BMS-DOS CLinux DWi

18、ndows2000 EUnix3、計算機病毒的傳染是以計算機運行與（ ）為基礎的，沒有這兩個條件，病毒是不會傳染的。A編輯文稿 B讀寫磁盤 C編程序 D掃描圖畫 E打印4、因特網不屬于任何個人，也不屬于任何組織。其中在網絡知識這一塊中有一個英文簡寫ISP，它的中文意思是（ ）。A因特網連接 B因特網使用 C因特網設計 D因特網服務提供者 E信息傳輸5、Internet給我們提供了資源共享、瀏覽、檢索信息與遠程登錄等多種服務，下面幾個選項中用于遠程登錄的是（ ）。AWWW BTCP/IP CTelnet DE-mail EFTP6、IE是目前流行的瀏覽器軟件，它的工作基礎是解釋執行用（ ）語言書

19、寫的文件。AVC BHTML CBASIC DHTTP EVB7、給出3種排序：插入排序、冒泡排序、選擇排序。這3種排序的時間代價分別是（ ）。AO(n)、O(n2)、O(logn) 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、一棵完全二叉樹的結點總數為18，其葉結點數為（ ）。A7個 B8個 C9個 D10個 E11個9、在流程圖的符號中，菱形框一般作為（ ）。A起始框 B判斷框 C輸入輸出框 D處理工作框 E結速框10、在解決計算機主機與打印機之間速度不匹配時通常設置一個打印數據緩

20、沖區，主要將要輸出打印的數據依次寫入該緩沖區，而打印機從該緩沖區中取出數據打印。該緩沖區應該是一個（ ）結構。A堆棧 B數組 C線性表 D隊列 E鏈表11、多媒體技術中的“多媒體”的含義主要是指如（ ）等多種表達信息的形式。A磁盤 B音箱 C顯示器 D聲音 E圖像12、下面有關計算機知識說明，正確的是（ ）。A 在WINDOWS98操作系統下，刪除磁盤中的文件時都先存放在回收站中B FOXMAIL是用于收發電子郵件的工具C 文件夾組織是一個有層次的樹狀結構，其中最頂層的是桌面D存儲器具有記憶能力，其中的信息任何時候都不會丟失E 為了提高軟件的測試效率，應該選擇發現錯誤的可能性大的測試數據13、

21、對按關鍵字排序好的線性表進行二分查找，該線性表適合的存儲結構為（ ）。A鏈接存儲 B索引存儲 C散列存儲 D順序存儲 E循環存取14、一個棧的輸入順序為1、2、3、4、5，下列序列中可能是棧的輸出序列的是（ ）。A54312 B24135 C21543 D12534 E1234515、評價一個算法的好壞有多種指標，下列是算法評價指標的是（ ）。A 正確性 B運行時間 C占用空間 D迭代次數 E簡單性16、下面描述用多維數組表示的數據結構的語句中，正確的是（ ）。A 多維數組存放的都是同一種類型的數據B 多維數組各維的下標范圍必須一樣C 多維數組在內存中的地址是連續的D 多維數組中的下標不能是表

22、達式E 多維數組是隨機存取的數據結構17、若已知一個棧的入棧順序1，2，3，n，其輸出序列為P1，P2，P3，Pn（它是輸入序列的一個排列），則在輸出序列中可能出現的情況是（ ）。APj<Pk<Pi，其中i<j<kBPk< Pj<Pi，其中i<j<kCPj<Pi<Pk，其中i<j<kDPi<Pk< Pj，其中i<j<kE以上都不可能出現18、線性表具有如下的結構特點：（ ）A均勻性 B單一性 C簡單性 D無序性 E有序性19、下列關于數據結構的敘述中正確的是（ ）。A數據結構是帶有結構的數據元素的集

23、合B線性表的線性存儲結構優于鏈式存儲結構C隊列是限定僅在一端進行插入，在另一端進行刪除的線性表D二維數組是其數據元素為線性表的線性表E圖是一種非線性數據結構20、任意一棵樹均可惟一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹中，頂點N的左右子女分別是N在原樹里對應頂點的（ ）。A 最左子頂點/最鄰近的右兄弟B 最右子頂點/最右的兄弟C最鄰近的右兄弟/最左的兄弟D最鄰近的左兄弟/最鄰近的右兄弟F 最鄰近的右兄弟/最右的兄弟二、 問題解答：（共2題，每題5分，共10分）1、 光明中學開設數學、英語與信息學三個興趣學習小組，其中數學小組30人，英語小組15人，信息學小組18人，參加三個小組總人數為5

24、0人，其中有3人同時參加3個小組，那么同時只參加兩個小組的同學有多少人？ 2、 給出一組頂點（頂點值用A，B，C，D，E，F表示），其對應權值分別為2，3，1，7，8，4。請以A，B，C，D，E，F為葉子頂點構造一棵哈夫曼樹，并求出它的最小帶權路徑長度WPL的值。信息學命題(二)參考答案一、 選擇題：（選出每題正確的答案代碼，填在括號里，110題為單選題，每小題只有一個正確答案，1120題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分）題號12345678910答案BABDCBECBD題號111281920答案DEBCEDCEABCEACEBCDAEACDEA

25、二、問題解答：（共2題，每題5分，共10分）第1題：7第2題：61信息學初賽模擬試題(二)三、 選擇題：（選出每題正確的答案代碼，填在括號里，110題為單選題，每小題只有一個正確答案，1120題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分）1、二進制數01100100轉換成十六進制數是（ ）。A32 B64 C128 D100 E2562、操作系統是一類重要的系統軟件，下面幾個軟件中，不屬于系統軟件的是（ ）。AJava BMS-DOS CLinux DWindows2000 EUnix3、計算機病毒的傳染是以計算機運行與（ ）為基礎的，沒有這兩個條件，病毒

26、是不會傳染的。A編輯文稿 B讀寫磁盤 C編程序 D掃描圖畫 E打印4、因特網不屬于任何個人，也不屬于任何組織。其中在網絡知識這一塊中有一個英文簡寫ISP，它的中文意思是（ ）。A因特網連接 B因特網使用 C因特網設計 D因特網服務提供者 E信息傳輸5、Internet給我們提供了資源共享、瀏覽、檢索信息與遠程登錄等多種服務，下面幾個選項中用于遠程登錄的是（ ）。AWWW BTCP/IP CTelnet DE-mail EFTP6、IE是目前流行的瀏覽器軟件，它的工作基礎是解釋執行用（ ）語言書寫的文件。AVC BHTML CBASIC DHTTP EVB7、給出3種排序：插入排序、冒泡排序、選

27、擇排序。這3種排序的時間代價分別是（ ）。AO(n)、O(n2)、O(logn) 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、一棵完全二叉樹的結點總數為18，其葉結點數為（ ）。A7個 B8個 C9個 D10個 E11個9、在流程圖的符號中，菱形框一般作為（ ）。A起始框 B判斷框 C輸入輸出框 D處理工作框 E結速框10、在解決計算機主機與打印機之間速度不匹配時通常設置一個打印數據緩沖區，主要將要輸出打印的數據依次寫入該緩沖區，而打印機從該緩沖區中取出數據打印。該緩沖區應該是一個（

28、）結構。A堆棧 B數組 C線性表 D隊列 E鏈表11、多媒體技術中的“多媒體”的含義主要是指如（ ）等多種表達信息的形式。A磁盤 B音箱 C顯示器 D聲音 E圖像12、下面有關計算機知識說明，正確的是（ ）。C 在WINDOWS98操作系統下，刪除磁盤中的文件時都先存放在回收站中D FOXMAIL是用于收發電子郵件的工具C 文件夾組織是一個有層次的樹狀結構，其中最頂層的是桌面D存儲器具有記憶能力，其中的信息任何時候都不會丟失E 為了提高軟件的測試效率，應該選擇發現錯誤的可能性大的測試數據13、對按關鍵字排序好的線性表進行二分查找，該線性表適合的存儲結構為（ ）。A鏈接存儲 B索引存儲 C散列存

29、儲 D順序存儲 E循環存取14、一個棧的輸入順序為1、2、3、4、5，下列序列中可能是棧的輸出序列的是（ ）。A54312 B24135 C21543 D12534 E1234515、評價一個算法的好壞有多種指標，下列是算法評價指標的是（ ）。B 正確性 B運行時間 C占用空間 D迭代次數 E簡單性16、下面描述用多維數組表示的數據結構的語句中，正確的是（ ）。G 多維數組存放的都是同一種類型的數據H 多維數組各維的下標范圍必須一樣I 多維數組在內存中的地址是連續的J 多維數組中的下標不能是表達式K 多維數組是隨機存取的數據結構17、若已知一個棧的入棧順序1，2，3，n，其輸出序列為P1，P2

30、，P3，Pn（它是輸入序列的一個排列），則在輸出序列中可能出現的情況是（ ）。APj<Pk<Pi，其中i<j<kBPk< Pj<Pi，其中i<j<kCPj<Pi<Pk，其中i<j<kDPi<Pk< Pj，其中i<j<kE以上都不可能出現18、線性表具有如下的結構特點：（ ）A均勻性 B單一性 C簡單性 D無序性 E有序性19、下列關于數據結構的敘述中正確的是（ ）。A數據結構是帶有結構的數據元素的集合B線性表的線性存儲結構優于鏈式存儲結構C隊列是限定僅在一端進行插入，在另一端進行刪除的線性表D二維數

31、組是其數據元素為線性表的線性表E圖是一種非線性數據結構20、任意一棵樹均可惟一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹中，頂點N的左右子女分別是N在原樹里對應頂點的（ ）。C 最左子頂點/最鄰近的右兄弟D 最右子頂點/最右的兄弟C最鄰近的右兄弟/最左的兄弟D最鄰近的左兄弟/最鄰近的右兄弟L 最鄰近的右兄弟/最右的兄弟四、 問題解答：（共2題，每題5分，共10分）1、 光明中學開設數學、英語與信息學三個興趣學習小組，其中數學小組30人，英語小組15人，信息學小組18人，參加三個小組總人數為50人，其中有3人同時參加3個小組，那么同時只參加兩個小組的同學有多少人？ 2、 給出一組頂點（頂點值用

32、A，B，C，D，E，F表示），其對應權值分別為2，3，1，7，8，4。請以A，B，C，D，E，F為葉子頂點構造一棵哈夫曼樹，并求出它的最小帶權路徑長度WPL的值。五、 寫出程序的運行結果（共4題，每題8分，共32分）第1題：program test1；var n：integer；function count(n：integer)：integer；begin if n=1 then count：=0 elseif n mod 2=0 then count：=count(n div 2)+1else count：=count(n*3+1)+1；end；begin readln(n)； writel

33、n(count(n)；end.輸入：99輸出：第2題：program test2(input,output);vari,j,k,s:integer;begins:=0for i:=3 downto 1 do begin for j:=1 to 3 do begin k:=0; repeat 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); a:=0;b:=0; repeata:=a+1;b:=b+a; unt

34、il 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;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

35、;end endend.輸出：四、完善程序（共2題，每題14分，共28分）第1題（7分） 【問題描述】設有n種物品，每種物品有一個重量與一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為XK，今從n種物品中選取若干件（同一種物品可以多次選取），使其重量的與小于等于XK，而價值的與為最大。【程序清單】Program package; const maxxk=400;maxn=20; type tlist=array1maxn of byte;tmake=array0maxn,0maxxk of integer;var n,xk:integer; w,u:tlist; f:tmake

36、;procedure init; var i:byte;begin fillchar(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,xk);for i:=1 to n doend; 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 do if fi-1,j>fi,j-wi+ui then ; else ; end; end; procedure print;var get:tl

37、ist; i,j:byte;begin fillchar(get,sizeof(get),0); i:= ;j:= ; while i>0 do if fi,j=fi-1,j then dec(i) else begin dec(j,wi); end; writeln(n=,n, , xk=,xk); writeln(max worth=, ); for i:=1 to n dowriteln(no.,i, weight:,wi:2, worth:,ui:2, get,geti:2);end;begin init; make;print;end.第2題（7分）【問題描述】給定一個01串，請你找出長度介于a,b之間，重復出現次數最多的01串。輸入：a,b(0<a<=b<=12) 由0，1組合的數列，由.結尾。輸出：要求的串。提示：本程序中將01序列轉換為2進制數存取。【程序清單】program shuchuan;var i,j,s,k,a,b,max:integer; m:array18192 of integer; two,v:array120 of integer; c:char;begin for i:=1 to 13 doreadln(a,b);read(c);s:=1;k:=1;while c<>.d