信息學(xué)競賽初賽模擬試題16套

1、信息學(xué)初賽模擬試題（五）（初中組PASCA語言，兩小吋完成）'選擇題：（每題1.5分，共計30分。每題有5個選項，前10題為單選題，后10題為 不定項選擇題，全部選對才得分）。1.二進(jìn)制數(shù)11011011的十進(jìn)制值是（）A. 202 B. 219 C. 193 D. 2092.我國研制的銀河III型的超級計算機(jī)通過基準(zhǔn)程序的測試，其峰值速度是（）A. 80億次 B. 100億次 C. 130億次 0. 150 億次3.程序段如下：FOR 1:二 1 TO 5 DOFOR J:=2 TO 1 DO Writei n()輸出'*'的個數(shù)是（）A. 5B. 10C. 15D.

2、25E. 304.設(shè)待排序的記錄為（49, 38,65,97,76,13,27,49,55, 4）,經(jīng)過下過程將序列排序第趟：13,27, 49, 55, 4,49,3&65,97,76第二趟：13,4, 49, 3& 27,49,55,65,97,76第三趟：4,13, 27, 3& 49,49,55,65,76,97問它所用的方法是：（）A. 冒泡排序 B.直接選擇排序C.直接插入排序D.希爾排序5.設(shè)無向樹T有7片樹葉，其余頂點度均為3,則T中3度頂點有多少個（）A. 5B. 7C. 9D. 4E. 86.設(shè)連通圖G的頂點數(shù)和邊數(shù)與一立方體相同，即有8個頂點和12

3、條邊。任意一棵G的 生成樹的總邊數(shù)為（）A. 7 B. 8 C. 9 D. 10 E. 117.設(shè)有兩個散列函數(shù)hl 解決沖突。探測地址的地址增量（k） =k mod 13和h2 （k） =k mod 11 +1,散列表為T0，用 二次散列法 函數(shù)hl用來計算散列地址，當(dāng)發(fā)生沖突時，h2作為計算下一個 假 定某一時刻散列表的狀態(tài)為：6 7 8 9101112804435下一個被插入的關(guān)鍵碼為57,其插入的位置為（）A. 4B. 5C. 6D. 7E. 8請根據(jù)下面是一段PASCALS序,判斷第8、9題。for h :二1 to nT do beg inx :=Ah+l;k :=h;while

4、(k>=l) and (Ak>x) do begi nAk+1:二 Ak;k:=k - 1 endAk+1: =xend8. 假設(shè)在程序開始執(zhí)行時，數(shù)組 A1n是一組隨機(jī)整數(shù)。下列答案中，哪一個最好的描述了最差情況下的程序排序的吋間復(fù)雜度？()A. 0(n Iog2 n) B. 0(n)C. 0(log2n) D. 0(n2) E. 0(2n)9. 假設(shè)在程序開始執(zhí)行時，數(shù)組 Al ? n是按關(guān)鍵字非遞減有序排列時，下列答案中，哪一個最好的描述了最好情況下的程序排序的時間復(fù)雜度？()2A. 0(n log2 n) B. 0(n)C. 0(log2 n) D. 0(n) E. 0(2

5、 n)10. 對下列四個序列用快速排序方法進(jìn)行排序，以序列的第一個元素為劃分的基準(zhǔn)，在第一趟劃分過程中，元素的移動數(shù)最多的是哪一個序列()A.70 ,65 ,34 ,82 ,53 ,25 ,90B.82 ,53 ,25 ,70 ,65 ,34 ,90C.34 ,25 ,53 ,65 ,90 ,82 ,70D.53 ,25 ,65 ,70 ,34 ,90 ,82E.65 ,34 ,82 ,70 ,25 ,53 ,9011.在計算機(jī)運行時，把程序和數(shù)據(jù)一樣存放在內(nèi)存中，這是1946年由 所領(lǐng)導(dǎo)的研究小組正式提岀并論證的。()A.圖靈B.馮？諾依曼C.布爾D.赫夫曼E.哈希12.下面關(guān)于計算機(jī)的說法

6、正確的是()A.微機(jī)內(nèi)存谷量的基本計量單位是子節(jié)B.二進(jìn)制數(shù)中右起第10位上的1相當(dāng)于210C.CPU每執(zhí)仃個扌曰令，就兀成步基本運算或判斷D.1T 二 1024MBE.32位的計算機(jī)中的“32”指的是字長13.為什么說PASCAI是“高級語言”,是因為它()A.必須在性能較咼的機(jī)器上運行B.必須經(jīng)過良好培訓(xùn)的高水平的程序員使用C.離機(jī)器的硬件較遠(yuǎn)D.開發(fā)的時間較長E.程序的性能較好14?以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)？()A.廣義表B.二叉樹C.稀疏矩陣D.串E.隊列15. 在下而關(guān)于計算機(jī)系統(tǒng)硬件的說法中不正確的是()A. 沒有外部設(shè)備的計算機(jī)稱為裸機(jī)B. 當(dāng)關(guān)閉計算機(jī)電源后，RAM中的

7、程序和數(shù)據(jù)就消失了C. 軟盤和硬盤上的數(shù)據(jù)均可由CPU直接存取D. 軟盤和硬盤驅(qū)動器既屬于輸入設(shè)備又屬于輸出設(shè)備E. CPU主要由運算器、控制器和寄存器組成16. 下面關(guān)于算法的正確說法是（）A. 算法必須有輸出B. 算法必須在計算機(jī)上用某種語言實現(xiàn)C. 算法不一定有輸入D. 算法必須在有限步執(zhí)行后能結(jié)束E. 算法是程序的靈魂17. 以下關(guān)于結(jié)構(gòu)化程序的說法中，正確的是（）A. 結(jié)構(gòu)化程序是由單入口，單出口和循環(huán)三種結(jié)構(gòu)組成B. 結(jié)構(gòu)化程序是出順序、單入屮和單出口三種結(jié)構(gòu)組成C. 結(jié)構(gòu)化程序是由順序、循環(huán)和 GOTO語句結(jié)構(gòu)組成D. 結(jié)構(gòu)化程序是由順序、循環(huán)和分支三種結(jié)構(gòu)組成E. “自頂向下，

8、逐步求精”是結(jié)構(gòu)化程序設(shè)計方法的特點18. 棧S最多能容納4個元素?，F(xiàn)有6個元素按1, 2, 3, 4, 5, 6的順序進(jìn)棧，問下列哪 一個序列是可能的出棧序列？（）A.5,4,3,2,1,6B.3,2,5,4,1,6C.2,3,5,6,1,4D.1,4,6,5,2,E.4,5,3,6,2, 119. 下列排序算法中，哪些排序是不穩(wěn)定的（）A.快速排序B.基數(shù)排序C.希爾排序D.冒泡排序E.選擇排序20. 下列說法正確的是（）A. 解釋程序是接受參數(shù)，按照某一樣板產(chǎn)生機(jī)器語言的計算機(jī)程序B. BASIC語言程序通常需解釋執(zhí)行C. 連接程序可以把經(jīng)編譯程序產(chǎn)生的目標(biāo)程序變成可執(zhí)行的機(jī)器語言程序D

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

10、int;begi nwrite( 5 N 二 12');i:=2;j:=O;k:=l;repeatinc(i);p:二 j+k;j: 二 k;k:二 p;until i 二 12;writeln( ，F(xiàn)(', 12,', p);end.運行結(jié)果為：2. program example; varn:byte;a:array1. . 100 of longint;fun cti on f (n:byte):l ongint; var i:l ongint;beginif an-l>0 the n i:=a n-Ielse i :=f (n T);if a n2>

11、0 then i:=i+a n2else i:=i+f( n-2);an :=i;f:=i;begi nfill char (a, sizeof(a) , 0 )al ：=l;a2 ：=1;writeinF (', 8,') 二' , f );end.運行結(jié)果為：3. program example3begi na1:=1;t:=0;for i:=2 to 6 dobegins:=0;for j:=1 to iT dos:=s+aj;ai:二 s+1;end;for i:=1 to 6 dot :=t+ai;write in ( 't 二',t );en

12、d.運行結(jié)果為：4. program example4var i,s,max:i nteger;begi nfor i:=1 to 10 do read (ai) max:=al; s:=al;for i:=2 to 10 dobeginif s<0 then s:二 0;s:二 s+ai;if s>max the n max:=s;end;writeln ( "max 二，,max);end.輸入：8 9- 1 24 6 5 11 15 - 28 9 運行結(jié)果為：四、程序完善題(每題14分，共計28分)I. nXn方陣的每行每列都是自然數(shù)l ? .n的一個全排列，每行(

13、列)無重復(fù)數(shù)字。例:n = 5 時，1 43 2553 21442 15331 54225 431輸入n 0 = 2)和笫一行數(shù)字(不檢查錯誤)輸出一個滿足要求的方陣因為只是要求每行(列)無重復(fù)數(shù)字，對第一行的每個數(shù)字，都四十五度斜向下寫，寫到 盡頭就從行開頭開始。這樣就不會重復(fù)。對于經(jīng)過第y行，第x列的直線，斜率21設(shè)：y 二 x+b代入坐標(biāo)，得出：b二y-x令y二1,取首行的數(shù)：x=y-bx從1開始，到n,如果x為0或負(fù)數(shù)，則x二x+n,取出第一行的數(shù)。 程序只用一維數(shù)組，存笫一行的數(shù)字。program examp1e2;con stmax n=10000;vara:array1 maxn

14、 of in teger;x, y, n: in teger;function f (x,y:integer ) :integer;varb:i nteger;begi nif x<=0 then(3)f：=ax;end;begi nwriteEnter n:; readln(n); if (n<2) or (n>maxn) then exit; write(，Enter first line/ );for x: = I to n do read (ax); write inO utput:');for x: = I to n dowrite(a x:4);write in;for y:=2to n dobeginfor x:=l write In;to n do write (end.2. 程序說明設(shè)有n個人依次圍成一圈，從第1個人開始報數(shù)，數(shù)到第m個人出列，然后從 出列的下一個人開始報數(shù)，數(shù)到第 m個人又出列，如此反復(fù)到所有的人全部出列為止。設(shè)n個人的編號分別為1, 2,，n,打卬出111列的順序。本題用數(shù)組建立標(biāo)志位等方法求解，用數(shù)組實現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)。數(shù)組ai作為指針變量來使用，ai存放下一個結(jié)點的位置。設(shè)立指針j指向當(dāng)前結(jié)點，則移動結(jié)點過程為 j : =aj, 當(dāng)數(shù)到m