信息學競賽普與組初賽模擬試題

./信息學競賽普與組初賽模擬試題<五>一、選擇題：〔每題1.5分,共計30分。每題有5個選項,前10題為單選題,后10題為不定項選擇題,全部選對才得分〕。1.二進制數(shù)11011011的十進制值是〔〕A.202B.219C.193D.209

2.我國研制的銀河Ⅲ型的超級計算機通過基準程序的測試,其峰值速度是〔〕A.80億次B.100億次C.130億次D.150億次3.程序段如下：FORI:=1TO5DO

FORJ:=2TOIDO

Writeln<‘*’>

輸出’*’的個數(shù)是〔〕A.5B.10C.15D.25E.30

4.設待排序的記錄為〔49,38,65,97,76,13,27,49,55,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

問它所用的方法是：<A.冒泡排序B.直接選擇排序C.直接插入排序D.希爾排序5.設無向樹T有7片樹葉,其余頂點度均為3,則T中3度頂點有多少個〔〕A.5B.7C.9D.4E.8

6.設連通圖G的頂點數(shù)和邊數(shù)與一立方體相同,即有8個頂點和12條邊。任意一棵G的生成樹的總邊數(shù)為〔〕A．7B.8C.9D.10E.11

7.設有兩個散列函數(shù)h1<k>=kmod13和h2<k>=kmod11+1,散列表為T[0…12],用二次散列法解決沖突。函數(shù)h1用來計算散列地址,當發(fā)生沖突時,h2作為計算下一個探測地址的地址增量。假定某一時刻散列表的狀態(tài)為：

0123456789101112

804435

下一個被插入的關鍵碼為57,其插入的位置為<。A.4B.5C.6D.7E.8

請根據(jù)下面是一段PASCAL程序,判斷第8、9題。forh:=1ton-1dobegin

x:=A[h+1];

k:=h;

while<k>=1>and<A[k]>x>dobegin

A[k+1]:=A[k];

k:=k–1

end

A[k+1]:=x

end

8.假設在程序開始執(zhí)行時,數(shù)組A[1…n]是一組隨機整數(shù)。下列答案中,哪一個最好的描述了最差情況下的程序排序的時間復雜度？〔〕A.O<nlog2n>B.O<n>C.O<log2n>D.O<n2>E.O<2n>

9.假設在程序開始執(zhí)行時,數(shù)組A[1…n]是按關鍵字非遞減有序排列時,下列答案中,哪一個最好的描述了最好情況下的程序排序的時間復雜度？〔〕A.O<nlog2n>B.O<n>C.O<log2n>D.O<n2>E.O<2n>

10.對下列四個序列用快速排序方法進行排序,以序列的第一個元素為劃分的基準,在第一趟劃分過程中,元素的移動數(shù)最多的是哪一個序列〔〕A.70,65,34,82,53,25,90

B.82,53,25,70,65,34,90

C.34,25,53,65,90,82,70

D.53,25,65,70,34,90,82

E.65,34,82,70,25,53,90

11.在計算機運行時,把程序和數(shù)據(jù)一樣存放在內存中,這是1946年由_______所領導的研究小組正式提出并論證的。〔〕A.圖靈

B.馮·諾依曼C.布爾D.赫夫曼E.哈希12.下面關于計算機的說法正確的是〔〕A.微機內存容量的基本計量單位是字節(jié)B.二進制數(shù)中右起第10位上的1相當于210

C.CPU每執(zhí)行一個指令,就完成一步基本運算或判斷D.1T=1024MB

E.32位的計算機中的"32"指的是字長13.為什么說PASCAL是"高級語言",是因為它〔〕A.必須在性能較高的機器上運行B.必須經過良好培訓的高水平的程序員使用C.離機器的硬件較遠D.開發(fā)的時間較長E.程序的性能較好14.以下數(shù)據(jù)結構中,哪一個是線性結構？〔〕A．廣義表B.二叉樹C.稀疏矩陣D.串E.隊列15.在下面關于計算機系統(tǒng)硬件的說法中不正確的是<A.沒有外部設備的計算機稱為祼機B.當關閉計算機電源后,RAM中的程序和數(shù)據(jù)就消失了C.軟盤和硬盤上的數(shù)據(jù)均可由CPU直接存取D.軟盤和硬盤驅動器既屬于輸入設備又屬于輸出設備E.CPU主要由運算器、控制器和寄存器組成16.下面關于算法的正確說法是〔〕A.算法必須有輸出B.算法必須在計算機上用某種語言實現(xiàn)C.算法不一定有輸入D.算法必須在有限步執(zhí)行后能結束E.算法是程序的靈魂17.以下關于結構化程序的說法中,正確的是〔〕A.結構化程序是由單入口,單出口和循環(huán)三種結構組成B.結構化程序是出順序、單入中和單出口三種結構組成C.結構化程序是由順序、循環(huán)和GOTO語句結構組成D.結構化程序是由順序、循環(huán)和分支三種結構組成E."自頂向下,逐步求精"是結構化程序設計方法的特點18.棧S最多能容納4個元素?，F(xiàn)有6個元素按1,2,3,4,5,6的順序進棧,問下列哪一個序列是可能的出棧序列？〔〕A.5,4,3,2,1,6

B.3,2,5,4,1,6

C.2,3,5,6,1,4

D.1,4,6,5,2,3

E.4,5,3,6,2,1

19.下列排序算法中,哪些排序是不穩(wěn)定的〔〕A．快速排序B.基數(shù)排序C.希爾排序D.冒泡排序E.選擇排序20.下列說法正確的是〔〕A.解釋程序是接受參數(shù),按照某一樣板產生機器語言的計算機程序B.BASIC語言程序通常需解釋執(zhí)行C.連接程序可以把經編譯程序產生的目標程序變成可執(zhí)行的機器語言程序D.就執(zhí)行速度而言,編譯程序比解釋程序快E.PASCAL通常是先編譯后執(zhí)行二、問題求解題〔每題5分,共計10分〕1.由四個結點可以構造多少種不同的二叉樹.

2.下圖是一個設想有11項活動的活動網(wǎng)。其中有9個事件V1,V2,…

V9,每個事件表示在它之前的活動已經完成,在它之后的活動可以開始。V1表示整個工程的開始,V9表示結束,與每個活動相聯(lián)系的數(shù)ax<x=1…11>是執(zhí)行該活動所需的時間〔單位：天〕。問完成整項工程至少需要天,影響工程進度的關鍵活動有哪些：。V2V7

V1V5V9

V3V8

V4V6

三、程序閱讀理解題〔每題8分,共計32分〕1．programex11_8;

var

n,i,j,k,p:longint;

begin

write<'N=12'>;i:=2;j:=0;k:=1;

repeat

inc<i>;p:=j+k;j:=k;k:=p;

untili=12;

writeln<'F<',12,'>=',p>;

end.

運行結果為：

2．programexample;

var

n:byte;

a:array[1..100]oflongint;

functionf<n:byte>:longint;

vari:longint;

begin

ifa[n-1]>0theni:=a[n-1]

elsei:=f<n-1>;

ifa[n-2]>0theni:=i+a[n-2]

elsei:=i+f<n-2>;

a[n]:=i;f:=i;

end;

begin

fillchar<a,sizeof<a>,0>;

a[1]:=1;a[2]:=1;

writeln<'F<',8,'>=',f<8>>;

end.

運行結果為:

3．programexample3

begin

a[1]:=1;t:=0;

fori:=2to6do

begin

s:=0;

forj:=1toi-1do

s:=s+a[j];

a[i]:=s+1;

end;

fori:=1to6do

t:=t+a[i];

writeln<‘t=’,t>;

end.

運行結果為：

4．programexample4

vari,s,max:integer;

begin

fori:=1to10doread<a[i]>;

max:=a[1];s:=a[1];

fori:=2to10do

begin

ifs<0thens:=0;

s:=s+a[i];

ifs>maxthenmax:=s;

end;

writeln<‘max=’,max>;

end.

輸入：89

–124651115

–289

運行結果為：四、程序完善題<每題14分,共計28分>

1.n×n方陣的每行每列都是自然數(shù)1..n的一個全排列,每行〔列〕無重復數(shù)字。例：n＝5時,14325

53214

42153

31542

25431

輸入n〔>＝2〕和第一行數(shù)字〔不檢查錯誤〕輸出一個滿足要求的方陣因為只是要求每行〔列〕無重復數(shù)字,對第一行的每個數(shù)字,都四十五度斜向下寫,寫到行盡頭就從行開頭開始。這樣就不會重復。對于經過第y行,第x列的直線,斜率k=1

設：y=x+b

代入坐標,得出：b=y-x

令y=1,取首行的數(shù)：x=y-b

x從1開始,到n,如果x為0或負數(shù),則x=x+n,取出第一行的數(shù)。程序只用一維數(shù)組,存第一行的數(shù)字。programexample2;

constmaxn=10000;

var

a:array[1..maxn]ofinteger;

x,y,n:integer;

functionf<x,y:integer>:integer;

var

b:integer;

begin

<1><2>ifx<=0then<3>f:=a[x];

end;

begin

write<'Entern:'>;readln<n>;

if<n<2>or<n>maxn>thenexit;

write<'Enterfirstline:'>;

forx:=1tondoread<a[x]>;

writeln<'Output:'>;

forx:=1tondowrite<a[x]:4>;

writeln;

fory:=2tondo

begin

forx:=1tondowrite<<4>:4>;

writeln;

end;

end.

2．[程序說明]設有ｎ個人依次圍成一圈,從第１個人開始報數(shù),數(shù)到第ｍ個人出列,然后從出列的下一個人開始報數(shù),數(shù)到第ｍ個人又出列,…,如此反復到所有的人全部出列為止。設ｎ個人的編號分別為1,2,…,n,打印出出列的順序。本題用數(shù)組建立標志位等方法求解,用數(shù)組實現(xiàn)鏈式結構。數(shù)組a[i]作為"指針"變量來使用,a[i]存放下一個結點的位置。設立指針j指向當前結點,則移動結點過程為j:=a[j],當數(shù)到m時,m結點出鏈,則a[j]:=a[a[j]]。[程序]

programexample;

constn=14;m=4;

vara:array[1..n]ofinteger;

i,j,k,p:integer;

begin

fori:=1ton-1doa[i]:=i+1;

a[n]:=1;

<1>;

k:=1;

p:=0;repeat

<2>;

k:=k+1;

ifk=mthen

begin

write<a[j]:4>;

p:=p+1;

<3>;

<4>;

end

untilp=n;

end.

參考答案一、選擇題：〔每題1.5分,共計30分。每題有5個選項,前10題為單選題,后10題為不定項選擇題,全部選對才得分〕。題號12345678910答案BCBDAAEDBE題號11121314151617181920答案BACECDEACABCDEDEBEACBCDE二、問題求解題〔每題5分,共計10分〕〕1、142、19,〔2分〕a1,a4,a7,a10〔3分〕三、程序閱讀理解題〔每題8分,共計32分〕

1、F〔12〕=89

2、F〔8〕=21

3、t=634、max=77四、程序完善題<每題14分,共計28分>

1、

①

b:=y-x;

②

x:=1-b;

③

x:=x+n;

④

f<x,y>2、

①

j:=n;

②

j:=a[j];

③

a[j]:=a[a[j]];

④

k:=1;grundfos發(fā)表于>2004-10-1810:16:57[全文][評論][引用][推薦][檔案][推給好友]2004-10-18信息學競賽普與組初賽模擬試題<四>

信息學競賽普與組初賽模擬試題<四>一、選擇題：〔選出每題正確的答案代碼,填在括號里,1—10題為單選題,每小題只有一個正確答案,11—20題為不定項選擇題,每小題有一個或一個以上的正確答案,共20題,每題1.5,共30分〕1、二進制數(shù)01100100轉換成十六進制數(shù)是〔〕。A．32B．64C．128D．100E．256

2、操作系統(tǒng)是一類重要的系統(tǒng)軟件,下面幾個軟件中,不屬于系統(tǒng)軟件的是〔〕。A．JavaB．MS-DOSC．LinuxD．Windows2000E．Unix

3、計算機病毒的傳染是以計算機運行和〔〕為基礎的,沒有這兩個條件,病毒是不會傳染的。A．編輯文稿B．讀寫磁盤C．編程序D．掃描圖畫E．打印4、因特網(wǎng)不屬于任何個人,也不屬于任何組織。其中在網(wǎng)絡知識這一塊中有一個英文簡寫ISP,它的中文意思是〔〕。A．因特網(wǎng)連接B．因特網(wǎng)使用C．因特網(wǎng)設計D．因特網(wǎng)服務提供者E．信息傳輸5、Internet給我們提供了資源共享、瀏覽、檢索信息和遠程登錄等多種服務,下面幾個選項中用于遠程登錄的是〔〕。A．WWWB．TCP/IPC．TelnetD．E-mailE．FTP

6、IE是目前流行的瀏覽器軟件,它的工作基礎是解釋執(zhí)行用〔〕語言書寫的文件。A．VCB．HTMLC．BASICD．E．VB

7、給出3種排序：插入排序、冒泡排序、選擇排序。這3種排序的時間代價分別是〔〕。A．O<n>、O<n2>、O<logn>B．O<logn>、O<n>、O<n2>C．O<n2>、O<n>、O<logn>

D．O<n2>、O<n>、O<n>E．O<n2>、O<n2>、O<n2>

8、一棵完全二叉樹的結點總數(shù)為18,其葉結點數(shù)為〔〕。A．7個B．8個C．9個D．10個E．11個9、在流程圖的符號中,菱形框一般作為〔〕。A．起始框B．判斷框C．輸入輸出框D．處理工作框E．結速框10、在解決計算機主機與打印機之間速度不匹配時通常設置一個打印數(shù)據(jù)緩沖區(qū),主要將要輸出打印的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應該是一個〔〕結構。A．堆棧B．數(shù)組C．線性表D．隊列E．鏈表11、多媒體技術中的"多媒體"的含義主要是指如〔〕等多種表達信息的形式。A．磁盤B．音箱C．顯示器D．聲音E．圖像12、下面有關計算機知識說明,正確的是〔〕。A．在WINDOWS98操作系統(tǒng)下,刪除磁盤中的文件時都先存放在回收站中B．FOXMAIL是用于收發(fā)電子的工具C．文件夾組織是一個有層次的樹狀結構,其中最頂層的是桌面D．存儲器具有記憶能力,其中的信息任何時候都不會丟失E．為了提高軟件的測試效率,應該選擇發(fā)現(xiàn)錯誤的可能性大的測試數(shù)據(jù)13、對按關鍵字排序好的線性表進行二分查找,該線性表適合的存儲結構為〔〕。A．存儲B．索引存儲C．散列存儲D．順序存儲E．循環(huán)存取14、一個棧的輸入順序為1、2、3、4、5,下列序列中可能是棧的輸出序列的是〔〕。A．54312B．24135C．21543D．12534E．12345

15、評價一個算法的好壞有多種指標,下列是算法評價指標的是〔〕。A．正確性B．運行時間C．占用空間D．迭代次數(shù)E．簡單性16、下面描述用多維數(shù)組表示的數(shù)據(jù)結構的語句中,正確的是〔〕。A．多維數(shù)組存放的都是同一種類型的數(shù)據(jù)B．多維數(shù)組各維的下標X圍必須一樣C．多維數(shù)組在內存中的地址是連續(xù)的D．多維數(shù)組中的下標不能是表達式E．多維數(shù)組是隨機存取的數(shù)據(jù)結構17、若已知一個棧的入棧順序1,2,3,…,n,其輸出序列為P1,P2,P3,…,Pn〔它是輸入序列的一個排列〕,則在輸出序列中可能出現(xiàn)的情況是〔〕。A．Pj<Pk<Pi,其中i<j<k

B．Pk<Pj<Pi,其中i<j<k

C．Pj<Pi<Pk,其中i<j<k

D．Pi<Pk<Pj,其中i<j<k

E．以上都不可能出現(xiàn)18、線性表具有如下的結構特點：〔〕A．均勻性B．單一性C．簡單性D．無序性E．有序性19、下列關于數(shù)據(jù)結構的敘述中正確的是〔〕。A．數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合B．線性表的線性存儲結構優(yōu)于鏈式存儲結構C．隊列是限定僅在一端進行插入,在另一端進行刪除的線性表D．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表E．圖是一種非線性數(shù)據(jù)結構20、任意一棵樹均可惟一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹中,頂點N的左右子女分別是N在原樹里對應頂點的〔〕。A．最左子頂點/最鄰近的右兄弟B．最右子頂點/最右的兄弟C．最鄰近的右兄弟/最左的兄弟D．最鄰近的左兄弟/最鄰近的右兄弟F．最鄰近的右兄弟/最右的兄弟二、問題解答：〔共2題,每題5分,共10分〕1、光明中學開設數(shù)學、英語和信息學三個興趣學習小組,其中數(shù)學小組30人,英語小組15人,信息學小組18人,參加三個小組總人數(shù)為50人,其中有3人同時參加3個小組,那么同時只參加兩個小組的同學有多少人？

2、給出一組頂點〔頂點值用A,B,C,D,E,F表示〕,其對應權值分別為2,3,1,7,8,4。請以A,B,C,D,E,F為葉子頂點構造一棵哈夫曼樹,并求出它的最小帶權路徑長度WPL的值。三、寫出程序的運行結果〔共4題,每題8分,共32分〕第1題：programtest1；varn：integer；functioncount<n：integer>：integer；begin

ifn=1thencount：=0

else

ifnmod2=0thencount：=count<ndiv2>+1

elsecount：=count<n*3+1>+1；end；begin

readln<n>；writeln<count<n>>；end.

輸入：99

輸出：第2題：programtest2<input,output>;

var

i,j,k,s:integer;

begin

s:=0

fori:=3downto1do

begin

forj:=1to3do

begin

k:=0;

repeat

k:=k+1;s:=s+k;

untilk=j;

end;

s:=s-<k+1>;

end;

write<‘s=’,s>;

end.

輸出：第3題：programtest3;

vara,b,n:longint;

begin

readln<n>;

a:=0;b:=0;

repeat

a:=a+1;b:=b+a;

untilb>=n;

writeln<a>;

end.

輸入：415377

輸出：programtest4;

varm,n,i,p,k：integer;

r:array[1…200]ofinteger;

b:Boolean;

begin

m:=6;n:=2;

forI:=1tom-1dor[i]:=i+1;

r[m]:=1;i:=0;p:=1;b:=true;

whilebdo

begin

i:=i+1;k:=p;p:=r[p];

ifk=pthen

beginwriteln<p>;b:=falseend

elseifi=n+1then

begin

write<p,‘

’>;i:=0;p:=r[p];r[k]:=p;

end

end

end.

輸出：四、完善程序〔共2題,每題14分,共28分〕第1題〔7分〕[問題描述]設有n種物品,每種物品有一個重量與一個價值。但每種物品的數(shù)量是無限的,同時有一個背包,最大載重量為XK,今從n種物品中選取若干件〔同一種物品可以多次選取〕,使其重量的和小于等于XK,而價值的和為最大。[程序清單]Programpackage;

constmaxxk=400;maxn=20;

typetlist=array[1…maxn]ofbyte;

tmake=array[0…maxn,0…maxxk]ofinteger;

varn,xk:integer;

w,u:tlist;

f:tmake;

procedureinit;

vari:byte;

begin

fillchar<w,sizeof<w>,0>;

fillchar<u,sizeof<u>,0>;

readln<n,xk>;

fori:=1tondo

①

;

end;

proceduremake;

vari,j:byte;

begin

fori:=1tondo

begin

forj:=1tow[i]-1do

f[i,j]:=f[i-1,j];

forj:=w[i]toxkdo

iff[i-1,j]>f[i,j-w[i]]+u[i]then

②

;

else

③

;

end;

end;

procedureprint;

varget:tlist;

i,j:byte;

begin

fillchar<get,sizeof<get>,0>;

i:=

④

;j:=

⑤

;

whilei>0do

iff[i,j]=f[i-1,j]thendec<i>

elsebegin

dec<j,w[i]>;

⑥

;

end;

writeln<‘n=’,n,

‘,’,

‘xk=’,xk>;

writeln<‘maxworth=’,

⑦

;

fori:=1tondo

writeln<‘no.’,i‘,weight:’,w[i]:2,

‘worth:’,u[i]:2,

‘get’,get[i]:2>;

end;

begin

init;

make;

print;

end.

第2題〔7分〕[問題描述]給定一個01串,請你找出長度介于a,b之間,重復出現(xiàn)次數(shù)最多的01串。輸入：a,b<0<a<=b<=12>

由0,1組合的數(shù)列,由‘.’結尾。輸出：要求的串。提示：本程序中將01序列轉換為2進制數(shù)存取。[程序清單]programshuchuan;

vari,j,s,k,a,b,max:integer;

m:array[1…8192]ofinteger;

two,v:array[1…20]ofinteger;

c:char;

begin

fori:=1to13do

①

;

readln<a,b>;

read<c>;

s:=1;k:=1;

whilec<>‘.’dobegin

s:=sshl1+ord<c>-48;

if

②

then

s:=<<s-two[b+1]>modtwo[b]>+two[b];

inc<m[s]>;

ifk<bthen

fori:=atok-1do

③

;

inc<k>;

read<c>;

end;

fori:=two[b]totwo[b+1]do

ifm[i]>0then

forj:=atob-1do

m[<imodtwo[j]>+two[j]]:=

④

;

max:=0;

fori:=two[a]totwo[b+1]do

ifm[i]>maxthen

⑤

;

fori:=two[a]totwo[b+1]do

ifm[i]=maxthenbegin

j:=0;k:=I;

repeat

inc<j>;v[j]:=kmod2;

⑥

;

until

⑦

;

whilej>0dobeginwrite<v[j]>;dec<j>end;

writeln;

end;

end.

信息學命題<四>參考答案一、選擇題：〔選出每題正確的答案代碼,填在括號里,1—10題為單選題,每小題只有一個正確答案,11—20題為不定項選擇題,每小題有一個或一個以上的正確答案,共20題,每題1.5,共30分〕題號12345678910答案BABDCBECBD題號11121314151617181920答案DEBCEDCEABCEACEBCDAEACDEA二、問題解答：〔共2題,每題5分,共10分〕第1題：7

第2題：61

三、寫出程序的運行結果：〔共4題,每題8分,共32分〕第1題：25第2題：s=18第3題：911第4題：421365四、完善程序〔共2題,每題14分,共28分〕第1題：

①read<w[i],u[i]>

②f[i,j]:=f[i-1,j]

③f[i,j]:=f[i,j-w[i]]+u[i]

④i:=n

⑤j:=xk

⑥inc<get[i]>

⑦f[n,xk]

第2題：

①two[i]:=1shli；②s>=two[b+1]<或k>b>

③inc〔m[<smodtwo[i]>+two[i]]〕④m[<imodtwo[j]>+two[j]]+m[i]

⑤max:=m[i]

⑥k:=kdiv2

⑦k=1信息學競賽普與組初賽模擬試題<三>一、選擇一個正確答案代碼〔A/B/C/D〕,填入每題的括號內〔每題1.5分,多選無分,共30分〕1、MAN英文縮寫的含義是〔〕A.局域網(wǎng)B.城域網(wǎng)C.廣域網(wǎng)D.增值網(wǎng)2、小X用十六進制,八進制和十進制寫了如下一個等式：64－13=33

式中三個數(shù)是各不相同進位制的數(shù),試問64,13,33,分別為________。A．八進制,十進制,十六進制B．十進制,十六進制,八進制C．八進制,十六進制,十進制D．十進制,八進制,十六進制3、表達式<4MOD<－3>>與<－4MOD3>的值為：_______。A．－1,－1B．1,－1C．－1,1D．1,1

4、試指出：下列if語句中,當x=80時,運行的結果為______。begin

y:=0;

readln<x>;

ifx<0theny:=5

else

ifx<10thenbegin

y:=10;

ifx<100theny:=100;

end

elsey:=200;

write<'y=',y>;

end.

A．y=9B．y=200C．y=10D．y=100

5、設棧S的初始狀態(tài)為空,現(xiàn)有5個元素組成的序列{1,2,3,4,5},對該序列在S棧上依次進行如下操作<從序列中的1開始,出棧后不再進棧>：進棧,進棧,進棧,出棧,進棧,出棧,進棧,試問出棧的元素序列是________。A．{5,4,3,2,1}B．{2,1}C．{2,3}D．{3,4}

6、ASCII碼是〔〕。A．國標碼B．二進制編碼C．十進制編碼D．美國標準信息交換碼7、一臺計算機的字長是4個字節(jié),這意味著〔〕。A．能處理的數(shù)值最大為4位十進制數(shù)9999

B．能處理的字符串最多由4個英文字母組成C．在CPU中能夠同時處理32位二進制數(shù)據(jù)D．在CPU中運算的最大結果為2的32次方8、假設一臺計算機的地址總線為16,那么中央處理器CPU能訪問的最大存儲器容量為<A．2*16KBB．16KBC．216BD．16*1024*8B

9、計算機最終處理的信息形式是〔〕A．ASCII碼B．BCD碼C．二進制D．十六進制10、與十六進制數(shù)6F等值的八進制數(shù)是〔〕A．166B．139C．157D．183

11、以下屬非法用戶自定義標識符的是<>。A．dateB．dirC．listD．type

12、設X和Y是同一種枚舉類型變量,則下列語句中合法的是<>。A．X:=ORD<Y>B．X:=YC．READ<X,Y>D．WRITE<T,Y>

13、計算機能夠直接識別和處理的程序是_______程序A．匯編語言B．源程序C.機器語言D.高級語言14、設有說明VARA：ARRAY['A'．．'E',1．．4,BOOLEAN]OFREA1；則A['A',3]是<。A．一個實型的數(shù)組元素B．一個數(shù)組,該數(shù)組具有兩個實型數(shù)組元素C．一個數(shù)組,該數(shù)組具有4*2個實型數(shù)組元素D．一個數(shù)組,該數(shù)組具有5*4*2個實型數(shù)組元素15、下列屬于線性時間的排序算法是：〔〕A.快速排序B.桶排序C.冒泡排序

16、一棵包含n個節(jié)點的樹有幾條邊：

A.nB.n-1C.不一定

17、在Pascal語言中,表達式35div3mod4的值是________。A．０B．２C．３D．６

18、在數(shù)據(jù)結構中,"樹"結構下層結點出現(xiàn)三個以上的結點,這種結構稱為________。A．三層樹B．三叉樹C．多層樹D．多叉樹19、在Pascal語言中,下列程序段所計算的公式是________。程序段：S：=0；T：=1；ForI：=1to10do

Begin

T：=T*I；S：=S+T；end;

A.S=1+2+3+4+……+10

B.S=1*2*3*4*……*10

C.S=1！+2！+3！+4！+……+10！D.S=1+2*3+3*4+4*5+……+10*11

20、以下說法正確的是〔〕。

A．CPU與內存不交換信息B．CPU與內存直接交換信息C．CPU與內存間接不交換信息D．CPU與內存部分交換信息二、閱讀下列程序,寫出程序運行結果〔第1題5分,第2,3,4題各6分,共23分〕programexp1;

constn=5;

varI,j,k:integer;

r:array[0..10]ofinteger;

begin

forI:=1tondo

read<r[I]>;

forI:=2tondo

begin

k:=r[I];j:=I-1;

while<k>r[j]>and<j>0>do

beginr[j+1]:=r[j];j:=j-1;end;

r[j+1]:=k;

end;

forI:=1tondo

write<r[I],’’>;

writeln

end.

鍵盤輸入:84935

屏幕輸出：programexp2;

vara,b,f:integer;

functiongd<m,n:integer>:integer;

begin

ifn=0thengd:=m

elsegd:=gd<n,mmodn>;

end;

begin

readln<a,b>;

write<‘<‘,a,’,’,b,’>=’>;

f:=gd<a,b>;

writeln<f>

end.

鍵盤輸入:17216

屏幕輸出：3、Programexp3<input,output>;

VARI,J,S:INTEGER;

B:ARRAY[0..5]OFINTEGER;

BEGIN

S:=1;

FORI:=1TO5DOB[I]:=I;

J:=1;

WHILEJ>0DO

BEGIN

J:=5;

WHILE<J>0>AND<B[J]=10+J-5>DOJ:=J-1;

IFJ>0THEN

BEGIN

S:=S+1;B[J]:=B[J]+1;

FORi:=J+1TO5DOB[i]:=B[J]+i-J

END;

END;

WRITELN<'S=',S>;

END.

4、programexp4<input,output>;

varm,n,g:integer;

functiongcd<m,n:integer>:integer;

begin

ifn=0thengcd:=m

elsegcd:=gcd<n,mmodn>

end;

begin

read<m,n>;

g:=gcd<m,n>;

writeln<'m=',m,'n=',n,'gcd=',g>

end.

輸入：489

輸出：三、問題解答〔第1題每空4分,第2題8分〕1、數(shù)據(jù)結構中,下面是一個樹結構圖,這個樹的"先序遍歷"結果是________,中序遍歷結果是：________________。248+3*4107-*/

2、給出一個后綴算術表達式為寫出對應的中綴算術表達式：___________________________________________

四、完善程序〔第一題每空3分,第二題每空2分,第三題每空4分,共32分〕1、連續(xù)整數(shù)平臺問題已知一個含有多個整數(shù)的數(shù)組,其中相同的元素集中在一起形成一個平臺。以下程序用于對輸入的數(shù)組求出其中最大平臺長度。例如,中元素個數(shù)為20,它們依次為22223333311111111144

則它的最大平臺長度為9。constmaxlength=100;

var

a:array[1..maxlength]ofinteger;

i,maxi,n,s,t:integer;

begin

write<'n='>;readln<n>;

fori:=1tondoread<a[i]>;

readln;

maxi:=0;

t:=[1]s:=1;

fori:=2tondo

ifa[i]=tthen[2]else

begin

ifs>maxithenmaxi:=s;

t:=a[i];

[3]end;

[4]writeln<'maxi=',maxi>;

end.

2、1000！尾0問題以下程序用于統(tǒng)計1000！末尾有多少個0。其中1000！=1´2´3´…´1000。實際上我們只要統(tǒng)計1000！有多少個因子10。由于10=5´2,因而只需統(tǒng)計有多少個因子5和2。顯然在1～1000的所有數(shù)中,5的因子個數(shù)比2的因子個數(shù)少。因此,只要統(tǒng)計1～1000的所有數(shù)中共有多少個因子5就行了。vari,j,n:integer;

begin

n:=0;

fori:=1to200do

beginj:=i*5;

while[5]=0do

begin

n:=n+1;

j:=[6]end;

end;

writeln<n:4>;

end.

3、[問題描述]找數(shù)問題:以下程序用在n個不同元素中找出第k個最小元素。程序中用分治策略來設計算法。把這n個元素放在一個數(shù)組中,然后取出第k個元素為標準m,把n個元素重新排列:小于標準m的元素放在數(shù)組前面,大于該標準的放在數(shù)組的后面。把該元素m放在兩者之間。設小于標準的元素個數(shù)為j-1,如果j=k,則A<k>即為所求元素。如果j>k,則第k個元素必在區(qū)間[1,j],因此取A[1],…,A[j]為新的元素集合,然后重復上述的"部分排序"的過程。如果j<k,則第k個元素必在區(qū)間[j+1,n],因此取A[j],…,A[n]為新的元素集合,重復過程。直至j=k為止。[程序清單]

varj,k,n:integer;

a:array[1..100]ofinteger;

proceduresearch<b,e:integer>;

varI,m,t:integer;

begin

ifb=ethenbeginj:=b;exitend;

I:=b;j:=e;m:=[7];

Repeat

Whilea[I]<mdoinc<i>;

Whilem<a[j]do[8];

IfI<jthen

Begint:=a[I];a[I]:=a[j];a[j]:=tend;

UntilI>=j;

IfI=kthenexit;

If[9]thensearch<b,j>elsesearch<j+1,e>

End;

procedure[10]varI:integer;

begin

forI:=1tondowrite<a[I],’’>;

writeln;

writeln<‘a[‘,k,’]=’,a[k]>;

end;

begin

write<‘n=’>;readln<n>;

write<‘a[1..’,n,’]=’>;

fork:=1tondoread<a[k]>;

readln;

write<‘k=’>;readln<k>;

search<[11];

pr<n>;

readln

end.

參考答案一、單項選擇題〔每題1分,共30分〕

12345678910

DCBBDDCCCC

11121314151617181920

DBCBBBCDDB二、閱讀下列程序,寫出程序運行結果〔第1題5分,第2,3,4題各6分,共23分〕1、98543

1、〔172,16〕=4

3、S=252

4、m=48n=9gcd=3

三、問題解答〔第1題每空4分,第2題8分〕1、ABCDEBADCE

2、<24+8>*3/4*<10-7>

四、完善程序〔第一題每空3分,第二題每空2分,第三題每空4分,共32分〕<1>a[1]<2>s:=s+1<3>s:=1<4>ifs>maxithenmaxi:=s;

<5>jmod5<6>jdiv5

<7>a[k]<8>de<j><9>j>k<10>pr<n:integer>;<11>Ln

信息學競賽普與組初賽模擬試題<二>〔pascal語言〕限時2小時完成,滿分100分一、選擇題：〔共20小題,1-15小題為單選題,每題1分；16-20小題為多選題,每題2分。共25分〕1.對存儲器按字節(jié)進行編址,若某存儲器芯片共有10根地址線的引腳,則該存儲器芯片的存儲容量為<。<A>512B<B>1KB<C>2KB<D>4KB<E>8KB

2.在待排序的數(shù)據(jù)表已經為有序時,下列排序算法中花費時間反而多的是<。<A>堆排序<B>希爾排序<C>冒泡排序<D>快速排序<E>二分排序3.某數(shù)列有1000個各不相同的單元,由低至高按序排列,現(xiàn)要對該數(shù)列進行二分法檢索,在最壞的情況下,需要檢索<單元。<A>1000<B>10<C>100<D>500<E>300

4.已知數(shù)組a中,每個元素a[i,j]在存儲時要占3個字節(jié),設i從1變化到8,j從1變化到10,分配內存實是從地址sa開始連續(xù)按行存儲分配的。試問：a[5,8]的起始地址為<。<A>sa+141<B>sa+180<C>sa+222<D>sa+225<E>sa+155

5.在pascal語言過程調用時,數(shù)值形參得到的是實際參數(shù)的<。<A>數(shù)值<B>地址<C>值<D>變量<E>以上都不是6.一個24*24點陣的漢字字形信息所占的字節(jié)數(shù)為<。<A>2<B>8<C>24<D>32<E>72

7.在微機系統(tǒng)中,最基本的輸入輸出模塊BIOS存放在<中。<A>RAM<B>ROM<C>硬盤<D>寄存器<E>控制器8.十進制算術表達式:3*512+5*64+2*8+1的運算中,用二進制表示為<。<A>1011010001<B><C><D><E>111000

9.設棧S的初始狀態(tài)為空,現(xiàn)對序列{1,2,3,4,5}在棧S上,依次進行如下操作<從元素1開始,出棧后不再進棧>:進棧,出棧,進棧,進棧,出棧,出棧。試問出棧的元素序列是<。<A>{1,2,3}B>{1,3,2}C>{3,2,1}D>{2,3,1}<E>以上都不對10.E-mail本質上是一個<<A>文件<B>電報<C><D><E>電訊11.一棵二叉樹的高度為h,所有結點的度為0,或為2,則此樹最少有<個結點<A>2h-1<B>2h-1<C>2h+1<D>h+1<E>h*h+1

12.無向圖G=<V,E>,其中V={a,b,c,d,e,f}

E={<a,b>,<a,e>,<a,c>,<b,e>,<c,f>,<f,d>,<e,d>}對該圖進行深度優(yōu)先遍歷,得到的頂點序列正確的是<<A>a,b,e,c,d,f<B>a,c,f,e,b,d<C>a,e,b,c,f,d<D>a,b,e,d,f,c<E>以上都不對13.pascal編譯程序是<〔A〕.把pascal源程序轉換成可運行的EXE文件的程序〔B〕.把pascal源程序轉換成等價的目標碼的程序〔C〕.生成和修改一個pascal語言源程序的等程序〔D〕.把pascal的目標碼程序轉換成可運行的EXE文件的程序〔E〕.生成一個等價的匯編程序14.將三封信投到4個郵筒,最多的投法有〔〕〔A〕．種〔B〕．種〔C〕．種〔D〕．34種E.

15.電子信函<電子>的特點之一是〔〕?！睞〕.比郵政信函,電報,,都更快〔B〕.在通信雙方的計算機之間建立其直接的通信線路后即可快速傳遞數(shù)字信息〔C〕.采用存儲-轉發(fā)方式在網(wǎng)絡上逐步傳遞信息,不象那樣直接、與時,但費用低廉〔D〕.在通信雙方的計算機都開機工作的情況下即可快速傳遞數(shù)字信息

16.以下屬于多媒體硬件的是〔〕〔A〕．主機〔B〕.光驅〔C〕.聲卡〔D〕.音箱〔E〕.超級解霸17.正確的二維數(shù)組類型說明是<>

<A>typear2=array[1..5,5..1]ofinteger;

<B>typear2=array[1..5]ofarray[5.1]ofinteger;

<C>typear2=array[1..5,1..5]ofinteger;

<D>typear2=array[1..5]ofarray[1..5]ofinteger

<E>typear2=array[1..5,1..5]of0..1

18.下列屬于信息處理的是〔〕〔A〕信息加工〔B〕信息分類〔C〕信息技術〔D〕信息采集〔E〕信息存儲19.在windows中,最小化一個應用程序窗口后,該程序將〔〕。<A>被終止執(zhí)行<B>被暫停執(zhí)行<C>被轉入后臺<D>繼續(xù)執(zhí)行〔E〕以上答案都不對20.下面的常量說明中,正確的是〔〕〔A〕CONST〔B〕、CONST〔C〕、CONST〔D〕、CONST〔E〕CONST

t=trueb,C=45M=100,15N=1OR2a=

’A’二、問題求解：〔第1小題5分,第2-3小題各4分,共13分〕[問題1]:在所有三位數(shù)中,各位數(shù)字從高位到低位順次減小的數(shù)共有個。[問題2]："銀條"

一位銀礦勘探員無力預付3月份的房租。他有一根長31英寸的純銀條,因此他和女房東達成如下協(xié)議。他說,他將把銀條切成小段。3月份的第一天,他給女房東1英寸長的一段,然后每天給她增加1英寸,以此作為抵押?？碧絾T預期到3月份的最后一天,他能全數(shù)付清租金,而屆時女房東將把銀條小段全部還給他。3月份有31天,一種辦法是把銀條切成31段,每段長1英寸。可是這處花很多功夫?？碧絾T希望既履行協(xié)議,又能使銀條的分段數(shù)目盡量減少。例如,他可以第一天給女房東1英寸的一段,第二天再給1英寸的一段,第三開他取回這兩段1英寸的而給她3英寸的一段。假設銀條的各段是按照這種方式來回倒換的話,勘探員至少需要把他的銀條切成______段？[問題3]:"換不開的鈔票"

錢柜里有1.15美分,一位顧客提出：把1美元的鈔票換成硬幣,但出納小姐說換不開,后來這位顧客提出：把50美分的鈔票換成硬幣,但出納小姐又說換不開,而實際上,出納小姐也無法把25美分、10美分、5美分的鈔票換成硬幣。請問錢柜里到底有哪些硬幣？他們分別有多少枚？答：_________________。三、寫出程序的運行結果：〔每小題6分,共30分〕1.programtext1;

constn=6;m=3;

vari,j,k:integer;

begin

fori:=-ntondo

begin

k:=n-abs<i>;

write<'':39-k>;

forj:=-ktokdo

ifabs<j>>k-m

thenwrite<n-<i+n>div2>

elsewrite<''>;

writeln;

end;

end.輸出的結果為：2.PROGAMtext2；VARa:ARRAY[1..10]OFChar；k:Integer；ch:Char；BEGIN

FORk:=1TO10DOa[k]:=Chr<Ord<'A'>+k>；FORk:=1TO10DO

BEGIN

ch:=a[k]；a[k]:=a[11-k]；a[11-k]:=ch；END；FORk:=1TO10DOWrite<a[k]>；Writeln

END.

輸出的結果為：

3.programtext3<input,output>;

Varm,n,p:integer;

x:real;

proceduremm<varm:integer;x:real>;

varn:integer;

begin

m:=m+1;

n:=m+1;

x:=n*3;

p:=n;

end;

begin

m:=8;n:=5;p:=3;x:=1.0;mm<n,x>;

writeln<m:5,n:5,p:5,x:6:1>;

end.

輸出的結果為：4.programtext4;

constn=5;

typeary=array[0..n-1,0..n-1]ofinteger;

vara:ary;i,j,k:integer;

begin

fori:=0ton-1do

forj:=0ton-1doa[i,j]:=0;

k:=1;

fori:=1tondo

forj:=n-1downtoido

begin

a[j,j-i]:=k;

k:=k+1;

end;

fori:=0ton-1do

beginforj:=0ton-1do

write<a[I,j]:4>;

writeln;

end;

end.

輸出的結果為：5.programtext5<input,output>;

varch:char;

i,n,sum:integer;

beginsum:=0;

read<ch>;

casechof'A':fori:=4to6dobegin

read<n>:

sum:=sum＋n

end;

'B'：beginread<n>;

fori:=1tondobeginread<n>;sum:=sum＋nend;

end;

'C':repeatread<n>;sum:=sum＋n

untilsum>10;

'D':beginread<n>;

whilen<=3dobeginsum:=sum＋n;read<n>endendend;writeln<sum:4>

end.

當程序運行<1>輸入A4123456789時,其輸出為_____________。<2>輸入B4123456789時,其輸出為_____________。<3>輸入C4123456789時,其輸出為_____________。<4>輸入D4123456789時,其輸出為_____________。四、完善程序〔第1題每空2分第2、3題每空3分,共32分〕第1題孿生素數(shù)是指兩個相差為2的素數(shù),例如：3和5,5和7,1