資源簡介

第十七屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組 Pascal語言 兩小時完成 ）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、單項選擇題（共20題，每題1.5分。共計30分。每題有且僅有一個正確選項。）
1．在二進制下，1100011 +（ ）= 1110000。
A．1011 B．1101 C．1010 D．1111
2．字符“A”的ASCII碼為十六進制41，則字符“Z”的ASCII碼為十六進制的（ ）。
A．66 B．5A C．50 D．視具體的計算機而定
3．右圖是一棵二叉樹，它的先序遍歷是（ ）。
A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF
4．寄存器是（ ）的重要組成部分。
A．硬盤 B．高速緩存 C．內存 D．中央處理器（CPU）
5．廣度優先搜索時，需要用到的數據結構是（ ）。
A．鏈表 B．隊列 C．棧 D．散列表
6．在使用高級語言編寫程序時，一般提到的“空間復雜度”中的“空間”是指（ ）。
A．程序運行時理論上所占的內存空間
B．程序運行時理論上所占的數組空間
C．程序運行時理論上所占的硬盤空間
D．程序源文件理論上所占的硬盤空間
7．應用快速排序的分治思想，可以實現一個求第K大數的程序。假定不考慮極端的最壞情況，理論上可以實現的最低的算法時間復雜度為（ ）。
A．O(n2)B．O(n log n)C．O(n) D．O(1)
8．為解決Web應用中的不兼容問題，保障信息的順利流通，（ ）制定了一系列標準，涉及HTML、XML、CSS等，并建議開發者遵循。
A．微軟 B．美國計算機協會（ACM） C．聯臺國教科文組織 D．萬維網聯盟（W3C）
9．體育課的鈴聲響了，同學們都陸續地奔向操場，按老師的要求從高到矮站成一排。每個同學按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學，并站在他的后面。這種站隊的方法類似于（ ）算法。
A．快速排序 B．插入排序 C．冒泡排序 D．歸并排序
10．1956年（ ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉頓（Walter Brattain)，以表彰他們對半導體的研究和晶體管效應的發現。
A．諾貝爾物理學獎
B．約翰 馮 諾依曼獎
C．圖靈獎
D．高德納獎（Donald E．Knuth Prize）
二、不定項選擇題（共10題，每題1．5分，共計15分。每題有一個或多個正確選項。多選或少選均不得分。）
1．如果根結點的深度記為1，則一棵恰有2011個葉子結點的二叉樹的深度可能是（ ）。
A．10 B．11 C．12 D．2011
2．在布爾邏輯中，邏輯“或”的性質有（ ）。
A．交換律：P V Q = Q V P
B．結臺律：P V ( Q V R ) = ( P V Q ) V R
C．冪等律：P V P = P
D．有界律：P V 1 = 1 （1表示邏輯真）
3．一個正整數在十六進制下有100位，則它在二進制下可能有（ ）位。
A．399 B．400 C．401 D．404
4．匯編語言（ ）。
A．是一種與具體硬件無關的程序設計語言
B．在編寫復雜程序時，相對于高級語言而言代碼量較大，且不易調試
C．可以直接訪問寄存器、內存單元、I/O端口
D．隨著高級語言的誕生，如今已完全被淘汰，不再使用
5．現有一段文言文，要通過二進制哈夫曼編碼進行壓縮。簡單起見，假設這段文言文只由4個漢字“之”、“乎”、“者”、“也”組成，它們出現的次數分別為700、600、300、400。那么，“也”字的編碼長度可能是（ ）。
A．1 B．2 C．3 D．4
6．生物特征識別，是利用人體本身的生物特征進行身份認證的一種技術。目前，指紋識別、虹膜識別、人臉識別等技術己廣泛應用于政府、銀行、安全防衛等領域。以下屬于生物特征識別技術及其應用的是（ ）。
A．指靜脈驗證 B．步態驗證 C．ATM機密碼驗證 D．聲音驗證
7．對于序列“7、5、1、9、3、6、8、4”，在不改變順序的情況下，去掉（ ）會使逆序對的個數減少3。
A．7 B．5 C．3 D．6
8．計算機中的數值信息分為整數和實數（浮點數）。實數之所以能表示很大或者很小的數，是由于使用了（ ）。
A．階碼 B．補碼 C．反碼 D．較長的尾數
9．對右圖使用Dijkstra算法計算S點到其余各點的最短路徑
長度時，到B點的距離d[B]初始時賦為8，在算法的執行過程
中還會出現的值有（ ）。
A．3 B．7 C．6 D．5
10．為計算機網絡中進行數據交換而建立的規則、標準或約定的集合成為網絡協議。下列英文縮寫中，（ ）是網絡協議。
A．HTTP B．TCP/IP C．FTP D．WWW
三、問題求解（共2題，每題5分，共計10分）
1．平面圖是可以畫在在平面上，且它的邊僅在頂點上才能相交的簡單
無向圖。4個頂點的平面圖至多有6條邊，如右圖所示。那么，5個頂
點的平面圖至多有______條邊。
2．定義一種字符串操作，一次可以將其中一個元素移到任意位置。舉例說明，對于字符串”BcA”，可以將A移到B之前，變成字符串”ABC”。如果要將字符串”DACHEBGIF”變成”ABCDEFGHI”，最少需要________次操作。
四、閱讀程序寫結果（共4題，每題8分，共計32分）
1．
Const
SIZE = 100;
var
n, i, sum, x : integer;
a : array[1..SIZE] of integer;
begin
readln(n);
fillchar(a, sizeof(a), 0);
for i:= 1 to n do
begin
read(x);
inc(a[x]);
end;
i := 0;
sum := 0;
while sum < (n div 2 + 1) do
begin
inc(i);
sum :=sum + a[i];
end;
writeln(i);
end．
輸入：
11
4 5 6 6 4 3 3 2 3 2 1
輸出：
2．
var
n : integer;
procedure f2(x, y : integer);
forward;
procedure f1(x, y : integer);
begin
if x < n then
f2(y, x + y);
end;
procedure f2(x, y : integer);
begin
write(x, ’ ’);
f1(y, x + y);
end;
begin
readln(n);
f1(0, 1);
end．
輸入：30
輸出：_____________
3．
const
V = 100;
var
visited : array[1..v] of boolean;
e : array[1..V, 1..V] of integer;
n, m, ans, i, j, a, b, c : integer;
procedure dfs(x, len : integer);
var
I : integer;
begin
visited[x] := true;
if len > ans then
ans := len;
for i := 1 to n do
if (not visited[i]) and (e[x, i] <> -1) then
dfs(i, len + e[x, i]);
visited[x] := false;
end;
begin
readln(n, m);
for i := 1 to n do
for j := 1 to n do
e[i][j] := -1;
for i := 1 to m do
begin
readln(a, b, c);
e[a][b] := c;
e[b][a] := c;
end;
for i := 1 to n do
visited[i] := false;
ans := 0;
for i := 1 to n do
dfs(i, 0);
writeln(ans);
end.
輸入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
輸出：__________
4.
const
SIZE = 10000;
LENGTH = 10;
var
sum : longint;
n, m, i, j : integer;
a : array[1..SIZE, 1..LENGTH] of integer;
function h(u, v : integer) : integer;
var
ans, i : integer;
begin
ans := 0;
for i := 1 to n do
if a[u][i] <> a[v][i] then
inc(ans);
h := ans;
end;
begin
readln(n);
filichar(a, sizeof(a), 0);
m := 1;
repeat
i := 1;
while (i <= n) and (a[m][i] = 1) do
inc(i);
if i > n then
break;
inc(m);
a[m][i] :=1;
for j := i + 1 to n do
a[m][j] := a[m - 1][j];
until false;
sum :=0;
for i := 1 to m do
for j := 1 to m do
sum := sum + h(i, j);
writeln(sum);
end.
輸入：7
輸出：____________
五、完善程序（第1題，每空2分，第2題，每空3分，共計28分）
1. （大整數開方）輸入一個正整數n（1≤n<10100），試用二分法計算它的平方根的整數部分。
const
SIZE = 200;
type
hugeint = record
len : integer;
num : array[1..SIZE] of integer;
end;
//len表示大整數的位數；num[1]表示個位、num[2]表示十位，以此類推
var
s : string;
i : integer;
target, left, middle, right : hugeint;
function times(a, b : hugeint) : hugeint:
var
i, j : integer;
ans : hugeint;
begin
filIchar(ans, sizeof(ans), 0);
for i := 1 to a.1en do
for j := 1 to b.1en do
___①___ := ans.num[i + j — 1] + a.num[i] * b.num[j];
for i := 1 to a.len + b.1en do
begin
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;
___②___;
if ans.num[a.1en + b.1en] > 0
then ans.len := a.1en + b.1en
else ans.len :=a.1en + b.1en – 1;
end;
times := ans;
end;
function add(a, b : hugeint) : hugeint;
var
i : integer;
ans : hugeint;
begin
fillchar(ans.num, sizeof(ans.num), 0);
if a.1en > b.1en
then ans.len := a.1en
else ans.len := b.len;
for i := 1 to ans.1en do
begin
ans.num[i] :=___③___;
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;
ans.num[i] := ans.num[i] mod 10;
end;
if ans.num[ans.1en + 1] > 0
then inc(ans.len);
add:=ans;
end;
function average(a, b : hugeint) : hugeint;
var
i : integer;
ans : hugeint;
begin
ans := add(a, b);
for i := ans.1en downto 2 do
begin
ans.num[i - 1] := ans.num[i - 1] + (___④___) * 10;
ans.num[i] := ans.num[i] div 2;
end;
ans.num[i] := ans.num[i] div 2;
if ans.num[ans.len] = 0
then dec(ans.len);
average := ans;
end;
function plustwo(a : hugeint) : hugeint;
var
i : integer;
ans : hugeint;
begin
ans := a;
ans.num[1] := ans.num[1] + 2;
i := 1;
while(i <= ans.len) and (ans.num[i] >= 10) do
begin
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;
ans.num[i] := ans.num[i] mod 10;
inc(i);
end;
if ans.num[ans.len + 1] > 0
then___⑤___;
plustwo := ans;
end;
function over(a, b : hugeint) : boolean;
var
i : integer;
begin
if(___⑥___)then
begin
over := false;
exit;
end;
if a.1en > b.1en then
begin
over := true;
exit;
end;
for i := a.len downto 1 do
begin
if a.num[i] < b.num[i] then
begin
over := false;
exit;
end;
if a.num[i] > b.num[i] then
begin
over := true;
exit;
end;
end;
over := false;
end;’
begin
readln(s);
fillchar(target.num, sizeof(target.num), 0);
target.1en := 1ength(s);
for i := 1 to target.1en do
target.num[i] := ord(s[target.1en – i + 1]) - ___⑦___;
filichar(left.num, sizeof(1eft.num), 0);
left.1en := 1;
left.num[i] := 1;
right := target;
repeat
middle := average(1eft, right);
if over(___⑧___)
then right := middle
else 1eft := middle;
until over(plustwo(1eft), right);
for i := left.1en downto 1 do
write(1eft.num[i]);
writeln;
end.
2. （笛卡爾樹）對于一個給定的兩兩不等的正整數序列，笛卡爾樹是這樣的一棵二叉樹：首先，它是一個最小堆，即除了根結點外，每個結點的權值都大于父節點的權值；其次，它的中序遍歷恰好就是給定的序列。例如，對于序列7、2、12、1、10、5、15、3，下圖就是一棵對應的笛卡爾樹。現輸入序列的規模n（1≤n<100）和序列的n個元素，試求其對應的笛號爾樹的深度d(根節點深度為1)，以及有多少個葉節點的深度為d。
const
SIZE = 100;
INFINITY = 1000000;
var
n, maxDeep, num, i : integer;
a : array[1..SIZE] of integer;
procedure solve(1eft, right, deep : integer);
var
i, j, min : integer;
begin
if deep > maxDeep then
begin
maxDeep := deep;
num := 1;
end
else if deep = maxDeep then
___①___;
min := INFINITY;
for i := 1eft to right do
if min > a[i] then
begin
min := a[i];
___②___;
end;
if left < j then
___③___;
if j < right then
___④___;
end;
begin
readln(n);
for i := 1 to n do
read(a[i]);
maxDeep := 0;
solve(1, n, 1);
writeln(maxDeep, ‘ ’, num);
end.
寫在后面：化了整整三個晚上，終于把這資料給整好了。從掃描、校對到排版，真想不到有如此多的錯誤（可能是我的掃描儀太差了），雖然很累，卻很開心。以前都是我享用別人的奧賽資料，今天終于輪到我貢獻一下了。分享畢竟是快樂的！感謝所有熱衷于網絡資料分享的人們，還有我自己。
——江郎 2011-10-25
CCF NOIP2011提高組（Pascal語言）參考答案與評分標準
一、單項選擇題（共10題，每題1.5分，共計15分）
1 2 3 4 5 6 7 8 9 10
B B A D B A C D B A
二、不定項選擇題（共10題，每題1.5分，共計15分，多選或少選均不得分）
1 2 3 4 5 6 7 8 9 10
CD ABCD AB BC BC ABD CD A BCD ABC
三、問題求解（共2題，每題5分，共計10分）
1．9
2．4
四、閱讀程序寫結果（共4題，每題8分，共計32分）
1．3
2．1 2 5 13 34
3．150
4．57344
五、完善程序（第1題，每空2分，第2題，每空3分，共計28分）
（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）
1．① ans.num[i + j - 1]
② ans.num[i] := ans.num[i] mod 10;
③ ans.num[i] + a.num[i] + b.num[i];
④ ans.num[i] mod 2 (或 ans.num[i] and 1)
⑤ inc(ans.len) （或 ans.len := ans.len + 1）
⑥ a.len < b.len
⑦ ord('0')(或48）
⑧ times(middle, middle), target
2．① inc(num) (或 num := num + 1)
② j := i
③ solve(left, j - 1, deep + 1)
④ solve(j + 1, right, deep + 1)
PAGE
13

展開更多......

收起↑