全国第十一届青少年信息学奥林匹克竞赛分区联赛初赛试题 [2005年]

1. 字符串“ababacbab”和字符串“abcba”的最长公共子串是（ ）。

2. 设全集I = {a, b, c, d, e, f, g, h}，集合B 并 A = {a, b, c, d, e, f}， C 交 A = {c, d, e}，~B 交 A= {a, d}，那么集合C 交 B 交 A 交为（ ）。

3. 以下二进制数的值与十进制数23.456 的值最接近的是（ ）。

4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。

5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值综合为（ ）。

6. 下列设备中没有计算功能的是（ ）。

7. Intel的首颗64 位处理器是（ ）。

8. 常见的邮件传输服务器使用（ ）协议发送邮件。

9. 不能在Linux 上使用的网页浏览器是（ ）。

10. 一位艺术史学家有20000 幅1024 * 768 的真彩色图像，如果将这些图像以位图形式保存在CD 光盘上（一张CD 光盘的容量按600M计算），大约需要（ ）张CD光盘。

1. 设A = true，B = false，C = false，D = true，以下逻辑运算表达式值为真的有（ ）。

2. (3725)8 + (B)16的运算结果是（ ）。

3. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（ ）。

4. 设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的有（ ）。

5. 下列外设接口中可以通过无线连接的方式连接设备的是（ ）。

6. 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 的算法时间复杂度为O(n2)，如果处理器A执行程序P时能在一小时内完成的输入规模为n，则处理器B执行程序P时能在一小时内完成的输入规模为（ ）。

7. 以下哪个（些）不是计算机的输出设备（ ）。

8. 以下断电之后将不能保存数据的有（ ）。

9. 下列活动中属于信息学奥赛系列活动的是（ ）。

10. 下列关于高级语言的说法正确的有（ ）。

1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任 意两个元素，最少需要交换次。
答案：5

2. 取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1 根或 2 根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1， 先取者没有必胜策略记为0。当N 分别为100，200，300，400，500 时，先取者有无必 胜策略的标记顺序为（回答应为一个由0 和/或1 组成的字符串）。
答案：11011

1.

var
a, b, c, p, q : integer;
r : array[0..2] of integer;
begin
read(a, b, c);
p := a div b div c;
q := b - c + a + p;
r[0] := a * p div q * q;
r[1] := r[0] * (r[0] - 300);
if (3 * q - p mod 3 <= r[0]) and (r[2] = r[2]) then
r[1] := r[r[0] div p mod 2]
else r[1] := q mod p;
writeln(r[0] - r[1]);
end.
输入：100 7 3

输出：-7452

2.

var
a : array [1..50] of integer;
n, i, sum : integer;
procedure work(p, r: integer);
var
i, j, temp : integer;
begin
if p < r then begin
i := p - 1;
for j := p to r - 1 do
if a[j] >= a[r] then begin
inc(i);
temp := a[i]; a[i] := a[j]; a[j] := temp;
end;
temp := a[i + 1]; a[i + 1] := a[r]; a[r] := temp;
work(p, i);
work(i + 2, r);
end;
end;
begin
read(n);
for i := 1 to n do read(a[i]);
work(1, n);
for i := 1 to n - 1 do sum := sum + abs(a[i + 1] - a[i]);
writeln(sum);
end.
输入：10 23 435 12 345 3123 43 456 12 32 -100

输出：3223

3.

var
str : string;
len, i, j : integer;
nchr : array [0..25] of integer;
mmin : char;
begin
mmin := 'z';
readln(str);
len := length(str);
i := len;
while i >= 2 do begin
if str[i - 1] < str[i] then break;
dec(i);
end;
if i = 1 then begin
writeln('No result!');
exit;
end;
for j := 1 to i - 2 do write(str[j]);
fillchar(nchr, sizeof(nchr), 0);
for j := i to len do begin
if (str[j] > str[i - 1]) and (str[j] < mmin) then
mmin := str[j];
inc(nchr[ord(str[j]) - ord('a')]);
end;
dec(nchr[ord(mmin) - ord('a')]);
inc(nchr[ord(str[i - 1]) - ord('a')]);
write(mmin);
for i := 0 to 25 do
for j := 1 to nchr[i] do
write(chr(i + ord('a')));
writeln;
end.
输入：zzyzcccbbbaaa

输出：zzzaaabbbcccy

4.

var
n : longint;
function g(k : longint) : longint;
begin
if k <= 1 then g := k
else g := (2002 * g(k - 1) + 2003 * g(k - 2)) mod 2005;
end;
begin
read(n);
writeln(g(n));
end.
输入：2005

输出：31

1. 木材加工
题目描述:
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
输入:
第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
输出:
输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。
输入样例:
3 7
232
124
456
输出样例:
114
程序：

var
n, k : integer;
len : array [1..10000] of integer;
i, left, right, mid : integer;
function isok(t : integer) : boolean;
var
num, i : integer;
begin
num := 0;
for i := 1 to n do begin
if num >= k then break;
num := num+len[i] div t ;
end;
if num>=k then isok := true
else isok := false;
end;
begin
readln(n, k);
right := 0;
for i := 1 to n do begin
readln(len[i]);
if right < len[i] then right := len[i];
end;
inc(right);
left:=0 ;
while left+1 < right do begin
mid := (left + right) div 2;
if not isok(mid) then right := mid
else left := mid;
end;
writeln(left);
end.

2. N叉树
题目描述:
我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不是唯一的了。但是我们可以计算满足条件的不同二叉树一共有多少个。这不是一个很困难的问题，稍微复杂一点，我们把这个问题推广到N叉树。
我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比如，对于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以得到6个不同的4叉树（如下图）。

输入:
输入数据包括3行。
第一行是一个正整数N(2 ≤ N ≤ 20)，表示我们要考虑N叉树。
第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。
输出:
输出不同的N叉树的数目。题目中给的数据保证得到的结果小于2^31。
输入样例:
4
abdefgc
defgbca
输出样例:
6
程序：

var
str1, str2 : string;
N, len : integer;
com : array[0..100, 0..100] of longint;
function getcom(x, y : integer) : longint;
begin
if (y = 0) or (x = y) then getcom:=1 
else if com[x][y] <> 0 then getcom := com[x][y]
else begin
com[x][y] := getcom(x - 1, y)+ getcom(x-1,y-1)  ;
getcom := com[x][y];
end;
end;
function count(a, b, c : integer) : longint;
var
sum : longint;
k, s, t, p : integer;
begin
sum := 1; k := 0; s := a + 1; t := c;
if a = b then count := 1
else begin
while s <= b do begin
p := t;
while str1[s] <> str2[t] do inc(t);
sum := sum * count(s, s + t - p, p);
s := s+t-p+1  ;
inc(t)  ; inc(k);
end;
count := sum  * getcom(N, k);
end;
end;
begin
readln(N); readln(str1); readln(str2);
len := length(str1);
writeln(count( 1,len,1  ));
end.