資源簡介

信息學競賽普及組初賽模擬試題(五)
一、選擇題：（每題1.5分，共計30分。每題有5個選項，前10題為單選題，后10題為不定項選擇題，全部選對才得分）。
1. 二進制數11011011的十進制值是（ ）
A. 202 B. 219 C. 193 D. 209
2. 我國研制的銀河Ⅲ型的超級計算機通過基準程序的測試，其峰值速度是（ ）
A. 80億次　　　B. 100億次 C. 130億次 D. 150億次
3. 程序段如下：
FOR I:=1 TO 5 DO
FOR J:=2 TO I DO
Writeln(‘*’)
輸出’*’的個數是（ ）
A. 5 B. 10 C. 15 D. 25 E. 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. 5 B. 7 C. 9 D. 4 E. 8
6. 設連通圖G的頂點數和邊數與一立方體相同，即有8個頂點和12條邊。任意一棵G的生成樹的總邊數為（ ）
A．7　　　B. 8 C. 9 D. 10　　　E. 11
7. 設有兩個散列函數h1(k)=k mod 13 和 h2(k)=k mod 11 +1，散列表為T[0…12]，用二次散列法解決沖突。函數h1用來計算散列地址，當發生沖突時，h2作為計算下一個探測地址的地址增量。假定某一時刻散列表的狀態為：
0 1 2 3 4 5 6 7 8 9 10 11 12
80 44 35
下一個被插入的關鍵碼為57，其插入的位置為( 。
A. 4 B. 5 C. 6 D. 7 E. 8
請根據下面是一段PASCAL程序,判斷第8、9題。
for h :=1 to n-1 do begin
x :=A[h+1];
k :=h;
while (k>=1) and (A[k]>x) do begin
A[k+1] :=A[k];
k:=k–1
end
A[k+1] :=x
end
8. 假設在程序開始執行時，數組A[1…n]是一組隨機整數。下列答案中，哪一個最好的描述了最差情況下的程序排序的時間復雜度？（ ）
A. O(n log2 n) B. O(n) C. O(log2n) D. O(n2) E. O(2n)
9. 假設在程序開始執行時，數組A[1…n]是按關鍵字非遞減有序排列時，下列答案中，哪一個最好的描述了最好情況下的程序排序的時間復雜度？（ ）
A. O(n log2 n) B. O(n) C. O(log2n) D. O(n2) E. O(2n)
10.對下列四個序列用快速排序方法進行排序，以序列的第一個元素為劃分的基準，在第一趟劃分過程中，元素的移動數最多的是哪一個序列（ ）
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.在計算機運行時，把程序和數據一樣存放在內存中，這是1946年由_______所領導的研究小組正式提出并論證的。（ ）
A. 圖靈
B. 馮·諾依曼
C. 布爾
D. 赫夫曼
E. 哈希
12.下面關于計算機的說法正確的是（ ）
A. 微機內存容量的基本計量單位是字節
B. 二進制數中右起第10位上的1相當于210
C. CPU每執行一個指令，就完成一步基本運算或判斷
D. 1T=1024MB
E. 32位的計算機中的“32”指的是字長
13.為什么說PASCAL是“高級語言”，是因為它（ ）
A. 必須在性能較高的機器上運行
B. 必須經過良好培訓的高水平的程序員使用
C. 離機器的硬件較遠
D. 開發的時間較長
E. 程序的性能較好
14.以下數據結構中，哪一個是線性結構？（ ）
A．廣義表　　　B. 二叉樹　　C. 稀疏矩陣　　D. 串　　E. 隊列
15.在下面關于計算機系統硬件的說法中不正確的是(
A. 沒有外部設備的計算機稱為祼機
B. 當關閉計算機電源后，RAM中的程序和數據就消失了
C. 軟盤和硬盤上的數據均可由 CPU直接存取
D. 軟盤和硬盤驅動器既屬于輸入設備又屬于輸出設備
E. CPU主要由運算器、控制器和寄存器組成
16. 下面關于算法的正確說法是（ ）
A. 算法必須有輸出
B. 算法必須在計算機上用某種語言實現
C. 算法不一定有輸入
D. 算法必須在有限步執行后能結束
E. 算法是程序的靈魂
17.以下關于結構化程序的說法中，正確的是（ ）
A. 結構化程序是由單入口，單出口和循環三種結構組成
B. 結構化程序是出順序、單入中和單出口三種結構組成
C. 結構化程序是由順序、循環和GOTO語句結構組成
D. 結構化程序是由順序、循環和分支三種結構組成
E. “自頂向下，逐步求精”是結構化程序設計方法的特點
18.棧S最多能容納4個元素。現有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.下列排序算法中，哪些排序是不穩定的（ ）
A．快速排序　　　B. 基數排序　　　C. 希爾排序 D. 冒泡排序 E.選擇排序
20.下列說法正確的是（ ）
A. 解釋程序是接受參數，按照某一樣板產生機器語言的計算機程序
B. BASIC語言程序通常需解釋執行
C. 連接程序可以把經編譯程序產生的目標程序變成可執行的機器語言程序
D. 就執行速度而言，編譯程序比解釋程序快
E. PASCAL通常是先編譯后執行
二、問題求解題（每題5分，共計10分）
1. 由四個結點可以構造多少種不同的二叉樹 .
2. 下圖是一個設想有11項活動的活動網。其中有9個事件V1，V2，… V9,每個事件表示在它之前的活動已經完成，在它之后的活動可以開始。V1表示整個工程的開始，V9表示結束，與每個活動相聯系的數ax(x=1…11)是執行該活動所需的時間（單位：天）。問完成整項工程至少需要　 　　天，影響工程進度的關鍵活動有哪些：　 　　　　　。




V2 V7

V1 V5 V9



V3 V8



V4 V6

三、程序閱讀理解題 （每題8分，共計32分）
1．program ex11_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;
　until i=12;
　writeln('F(',12,')=',p);
end.
運行結果為：
2．program example;
var
　n:byte;
　a:array[1..100] of longint;
function f(n:byte):longint;
　var i:longint;
　begin
　　if a[n-1]>0 then i:=a[n-1]
　　else i:=f(n-1);
　　if a[n-2]>0 then i:=i+a[n-2]
　　else i:=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．program example3
begin
a[1]:=1;t:=0;
for i:=2 to 6 do
begin
s:=0;
for j:=1 to i-1 do
s:=s+a[j];
a[i]:=s+1;
end;
for i:=1 to 6 do
t:=t+a[i];
writeln(‘t=’,t);
end.
運行結果為：　
4．program example4
var i,s,max:integer;
begin
for i:=1 to 10 do read(a[i]);
max:=a[1]; s:=a[1];
for i:=2 to 10 do
begin
if s<0 then s:=0;
s:=s+a[i];
if s>max then max:=s;
end;
writeln(‘max=’,max);
end.
輸入：8 9 –1 24 6 5 11 15 –28 9
運行結果為：
四、程序完善題 (每題14分，共計28分)
1.n×n方陣的每行每列都是自然數1..n的一個全排列，每行（列）無重復數字。
例：
n＝5時，
1 4 3 2 5
5 3 2 1 4
4 2 1 5 3
3 1 5 4 2
2 5 4 3 1
輸入 n（>＝2）和第一行數字（不檢查錯誤）
輸出 一個滿足要求的方陣
因為只是要求每行（列）無重復數字，對第一行的每個數字，都四十五度斜向下寫，寫到行盡頭就從行開頭開始。這樣就不會重復。
對于經過第y行，第x列的直線，斜率k=1
設：y=x+b
代入坐標，得出：b=y-x
令y=1，取首行的數：x=y-b
x從1開始，到n,如果x為0或負數，則x=x+n，取出第一行的數。
程序只用一維數組，存第一行的數字。
program example2;
const maxn=10000;
var
a:array[1..maxn] of integer;
x,y,n:integer;
function f(x,y:integer):integer;
var
b:integer;
begin
(1)
(2)
if x<=0 then (3)
f:=a[x];
end;
begin
write('Enter n:'); readln(n);
if (n<2) or (n>maxn) then exit;
write('Enter first line:');
for x:=1 to n do read(a[x]);
writeln('Output:');
for x:=1 to n do write(a[x]:4);
writeln;
for y:=2 to n do
begin
for x:=1 to n do write( (4) :4);
writeln;
end;
end.
2．[程序說明] 設有ｎ個人依次圍成一圈，從第１個人開始報數，數到第ｍ個人出列，然后從出列的下一個人開始報數，數到第ｍ個人又出列，…，如此反復到所有的人全部出列為止。設ｎ個人的編號分別為1，2，…，n，打印出出列的順序。
本題用數組建立標志位等方法求解,用數組實現鏈式結構。 數組a[i]作為"指針"變量來使用，a[i]存放下一個結點的位置。設立指針j指向當前結點，則移動結點過程為j:=a[j]，當數到m時，m結點出鏈，則a[j]:=a[a[j]]。
[程序]
program example;
const n=14;m=4;
var a:array[1..n] of integer;
i,j,k,p:integer;
　begin
　　for i:=1 to n-1 do a[i]:=i+1;
　　 a[n]:=1;
(1) ;
k:=1;
p:=0;
　　repeat
　 (2) ;
k:=k+1;
　　　if k=m then
begin
　　　　　write(a[j]:4);
p:=p+1;
(3) ;
(4) ;
　　　　end
　　　until p=n;
　end.
參考答案
一、選擇題：（每題1.5分，共計30分。每題有5個選項，前10題為單選題，后10題為不定項選擇題，全部選對才得分）。

題號 1 2 3 4 5 6 7 8 9 10
答案 B C B D A A E D B E
題號 11 12 13 14 15 16 17 18 19 20
答案 B ACE C DE AC ABCDE DE BE AC BCDE
二、問題求解題（每題5分，共計10分））
1、 14
2、 19 ,（2分） a1,a4,a7,a10 （3分）
三、程序閱讀理解題 （每題8分，共計32分）

1、F（12）=89
2、F（8）=21

3、　t=63
4、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;

展開更多......

收起↑