資源簡介

信息學競賽普及組初賽模擬試題(四)
一、 選擇題：（選出每題正確的答案代碼，填在括號里，1—10題為單選題，每小題只有一個正確答案，11—20題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分）
1、二進制數01100100轉換成十六進制數是（ ）。
A．32 B．64 C．128 D．100 E．256
2、操作系統是一類重要的系統軟件，下面幾個軟件中，不屬于系統軟件的是（ ）。
A．Java B．MS-DOS C．Linux D．Windows2000 E．Unix
3、計算機病毒的傳染是以計算機運行和（ ）為基礎的，沒有這兩個條件，病毒是不會傳染的。
A．編輯文稿 B．讀寫磁盤 C．編程序 D．掃描圖畫 E．打印
4、因特網不屬于任何個人，也不屬于任何組織。其中在網絡知識這一塊中有一個英文簡寫ISP，它的中文意思是（ ）。
A．因特網連接 B．因特網使用 C．因特網設計 D．因特網服務提供者 E．信息傳輸
5、Internet給我們提供了資源共享、瀏覽、檢索信息和遠程登錄等多種服務，下面幾個選項中用于遠程登錄的是（ ）。
A．WWW B．TCP/IP C．Telnet D．E-mail E．FTP
6、IE是目前流行的瀏覽器軟件，它的工作基礎是解釋執行用（ ）語言書寫的文件。
A．VC B．HTML C．BASIC D．HTTP 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、一棵完全二叉樹的結點總數為18，其葉結點數為（ ）。
A．7個 B．8個 C．9個 D．10個 E．11個
9、在流程圖的符號中，菱形框一般作為（ ）。
A．起始框 B．判斷框 C．輸入輸出框 D．處理工作框 E．結速框
10、在解決計算機主機與打印機之間速度不匹配時通常設置一個打印數據緩沖區，主要將要輸出打印的數據依次寫入該緩沖區，而打印機從該緩沖區中取出數據打印。該緩沖區應該是一個（ ）結構。
A．堆棧 B．數組 C．線性表 D．隊列 E．鏈表
11、多媒體技術中的“多媒體”的含義主要是指如（ ）等多種表達信息的形式。
A．磁盤 B．音箱 C．顯示器 D．聲音 E．圖像
12、下面有關計算機知識說明，正確的是（ ）。
A． 在WINDOWS98操作系統下，刪除磁盤中的文件時都先存放在回收站中
B． FOXMAIL是用于收發電子郵件的工具
C． 文件夾組織是一個有層次的樹狀結構，其中最頂層的是桌面
D．存儲器具有記憶能力，其中的信息任何時候都不會丟失
E． 為了提高軟件的測試效率，應該選擇發現錯誤的可能性大的測試數據
13、對按關鍵字排序好的線性表進行二分查找，該線性表適合的存儲結構為（ ）。
A．鏈接存儲 B．索引存儲 C．散列存儲 D．順序存儲 E．循環存取
14、一個棧的輸入順序為1、2、3、4、5，下列序列中可能是棧的輸出序列的是（ ）。
A．54312 B．24135 C．21543 D．12534 E．12345
15、評價一個算法的好壞有多種指標，下列是算法評價指標的是（ ）。
A． 正確性 B．運行時間 C．占用空間 D．迭代次數 E．簡單性
16、下面描述用多維數組表示的數據結構的語句中，正確的是（ ）。
A． 多維數組存放的都是同一種類型的數據
B． 多維數組各維的下標范圍必須一樣
C． 多維數組在內存中的地址是連續的
D． 多維數組中的下標不能是表達式
E． 多維數組是隨機存取的數據結構
17、若已知一個棧的入棧順序1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn（它是輸入序列的一個排列），則在輸出序列中可能出現的情況是（ ）。
A．PjB．Pk< PjC．PjD．PiE．以上都不可能出現
18、線性表具有如下的結構特點：（ ）
A．均勻性 B．單一性 C．簡單性 D．無序性 E．有序性
19、下列關于數據結構的敘述中正確的是（ ）。
A．數據結構是帶有結構的數據元素的集合
B．線性表的線性存儲結構優于鏈式存儲結構
C．隊列是限定僅在一端進行插入，在另一端進行刪除的線性表
D．二維數組是其數據元素為線性表的線性表
E．圖是一種非線性數據結構
20、任意一棵樹均可惟一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹中，頂點N的左右子女分別是N在原樹里對應頂點的（ ）。
A． 最左子頂點/最鄰近的右兄弟
B． 最右子頂點/最右的兄弟
C．最鄰近的右兄弟/最左的兄弟
D．最鄰近的左兄弟/最鄰近的右兄弟
F． 最鄰近的右兄弟/最右的兄弟
二、 問題解答：（共2題，每題5分，共10分）
1、 光明中學開設數學、英語和信息學三個興趣學習小組，其中數學小組30人，英語小組15人，信息學小組18人，參加三個小組總人數為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題：
program test1；
var n：integer；
function count(n：integer)：integer；
begin
if n=1 then count：=0
else
if n mod 2=0 then count：=count(n div 2)+1
else count：=count(n*3+1)+1；
end；
begin
readln(n)；
writeln(count(n))；
end.
輸入：99
輸出：
第2題：
program test2(input,output);
var
i,j,k,s:integer;
begin
s:=0
for 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;
repeat
a:=a+1;b:=b+a;
until b>=n;
writeln(a);
end.
輸入：415377
輸出：
program test4;
var m,n,i,p,k：integer;
r:array[1…200] of integer;
b:Boolean;
begin
m:=6;n:=2;
for I:=1 to m-1 do r[i]:=i+1;
r[m]:=1;i:=0;p:=1;b:=true;
while b do
begin
i:=i+1;k:=p;p:=r[p];
if k=p then
begin writeln(p);b:=false end
else if i=n+1 then
begin
write(p,‘ ’);i:=0;p:=r[p];r[k]:=p;
end
end
end.
輸出：
四、完善程序（共2題，每題14分，共28分）
第1題（7分）
【問題描述】
設有n種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為XK，今從n種物品中選取若干件（同一種物品可以多次選取），使其重量的和小于等于XK，而價值的和為最大。
【程序清單】
Program package;
const maxxk=400;maxn=20;
type tlist=array[1…maxn] of byte;
tmake=array[0…maxn,0…maxxk] of integer;
var n,xk:integer;
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
① ;
end;
procedure make;
var i,j:byte;
begin
for i:=1 to n do
begin
for j:=1 to w[i]-1 do
f[i,j]:=f[i-1,j];
for j:=w[i] to xk do
if f[i-1,j]>f[i,j-w[i]]+u[i] then ② ;
else ③ ;
end;
end;
procedure print;
var get:tlist;
i,j:byte;
begin
fillchar(get,sizeof(get),0);
i:= ④ ;j:= ⑤ ;
while i>0 do
if f[i,j]=f[i-1,j] then dec(i)
else begin
dec(j,w[i]);
⑥ ;
end;
writeln(‘n=’,n, ‘,’, ‘xk=’,xk);
writeln(‘max worth=’, ⑦ ;
for i:=1 to n do
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之間，重復出現次數最多的01串。
輸入：a,b(0 由0，1組合的數列，由‘.’結尾。
輸出：要求的串。
提示：本程序中將01序列轉換為2進制數存取。
【程序清單】
program shuchuan;
var i,j,s,k,a,b,max:integer;
m:array[1…8192] of integer;
two,v:array[1…20] 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;
if ② then
s:=((s-two[b+1]) mod two[b])+two[b];
inc(m[s]);
if k for i:=a to k-1 do
③ ;
inc(k);
read(c);
end;
for i:=two[b] to two[b+1] do
if m[i]>0 then
for j:=a to b-1 do
m[(i mod two[j])+two[j]]:= ④ ;
max:=0;
for i:=two[a] to two[b+1] do
if m[i]>max then ⑤ ;
for i:=two[a] to two[b+1] do
if m[i]=max then begin
j:=0;k:=I;
repeat
inc(j);v[j]:=k mod 2; ⑥ ;
until ⑦ ;
while j>0 do begin write(v[j]);dec(j) end;
writeln;
end;
end.
信息學命題(四)參考答案
一、 選擇題：（選出每題正確的答案代碼，填在括號里，1—10題為單選題，每小題只有一個正確答案，11—20題為不定項選擇題，每小題有一個或一個以上的正確答案，共20題，每題1.5，共30分）

題號 1 2 3 4 5 6 7 8 9 10
答案 B A B D C B E C B D
題號 11 12 13 14 15 16 17 18 19 20
答案 DE BCE D CE ABCE ACE BCD AE ACDE A
二、問題解答：（共2題，每題5分，共10分）
第1題：
7
第2題：
61
三、寫出程序的運行結果：（共4題，每題8分，共32分）

第1題：
25 第2題：
s=18
第3題：
911 第4題：
4 2 1 3 6 5
四、完善程序（共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]:=1 shl i；
②s>=two[b+1](或k>b)
③inc（m[(s mod two[i])+two[i]]）
④m[(i mod two[j])+two[j]]+m[i]
⑤max:=m[i]
⑥k:=k div 2
⑦k=1