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

1. 关于图灵机下面的说法哪个是正确的：

2. 关于计算机内存，下列说法哪个是正确的：

3. 下列关于BIOS的说法哪个是正确的：

4. 关于CPU下面那个说法是正确的：

5. 关于ASCII，下面哪个说法是正确的：

6. 下列软件中不是计算机操作系统的是：

7. 关于互联网，下面的说法哪一个是正确的：

8. 关于HTML语言下面哪种说法是正确的：

9. 关于程序设计语言，下面哪种说法是正确的：

10. 已知大写字母A的ASCII编码为65（十进制），则大写字母J的十进制ASCII编码为：

11. 十进制小数125.125对应的八进制数是

12. 有六个元素FEDCBA 从左到右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？

13. 表达式 a*(b+c)-d 的后缀表达式是

14. 一个包含n个分支节点（非叶节点）的非空二叉树，它的叶节点数目最多为：

15. 快速排序最坏情况下的算法复杂度为：

16. 又一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：

17. 排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：

18. 已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？

19. 全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：

20. 在参加NOI系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：

1. 小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而…… a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有 __________ 种。
答案：70

2. 有如下的一段程序： 1. a:=1; 2. b:=a; 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7. g:=a*f+c; 现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在_______单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。
答案：5

1.

var    a, b: integer;
function work(a, b: integer): integer;
begin
    if a mod b <> 0 then  work := work(b, a mod b)
    else
   work := b;
end;
begin
    read(a, b);  writeln(work(a, b));
end.
 输入：20 12
输出：4

2.

var    a, b: array[0..2] of integer;  i, j, tmp: integer;
begin
    for i := 0 to 2 do  read(b[i]);
    for i := 0 to 2 do  begin
        a[i] := 0;
        for j := 0 to i do   begin
            inc(a[i], b[j]); inc(b[a[i] mod 3], a[j]);
        end;
    end;
    tmp := 1;
    for i := 0 to 2 do  begin
      a[i]:= a[i] mod 10; b[i]:= b[i] mod 10;tmp:= tmp* (a[i] + b[i])
    end;
    writeln(tmp);
end.
输入：2 3 5
输出：416

3.

const c = 2009;
var    n, p, s, i, j, t: integer;
begin
    read(n, p);  s := 0;   t := 1;
    for i := 1 to n do    begin
        t := t * p mod c;
for j := 1 to i do  s := (s + t) mod c;
    end;
    writeln(s);
end.
输入：11 2
输出：782

4.

var  a: string;    n: integer;
procedure getnext(var str: string);
var    l, i, j, k: integer;    temp: char;
begin
    l := length(str);    k := l - 1;
    while (k >= 1) and (str[k] > str[k + 1]) do  dec(k);
    i := k + 1;
    while (i <= l) and (str[i] > str[k]) do  inc(i);
    temp := str[k]; str[k] := str[i - 1]; str[i - 1] := temp;
    for i := l downto k + 1 do
        for j := k + 1 to i - 1 do
            if str[j] > str[j + 1] then   begin
                temp := str[j]; str[j] := str[j + 1];str[j + 1] := temp;
            end;
end;
begin
    read(a);   read(n);
    while n > 0 do    begin
        getnext(a);        dec(n);
    end;
    write(a);
end.
输入：NOIP 3
输出：NPOI

1. （最大连续子段和）给出一个数列（元素个数不超过100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为 4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8 时，输出16和7。

var    a: array[1..100] of integer;
    n, i, ans, len, tmp, beg: integer;
begin
    read(n);
    for i := 1 to n do  read(a[i]);
    tmp := 0;ans := 0;len := 0;
    beg :=   _0   ;
    for i := 1 to n do    begin
        if tmp + a[i] > ans then    begin
            ans := tmp + a[i];   len := i - beg;
        end
        else if (   tmp+a[i]=ans   ) and (i - beg > len) then  len := i - beg;
        if tmp + a[i]    <0    then     begin
            beg :=    i      ;      tmp := 0;
        end
        else         tmp:= tmp+a[i]    ;
    end;
    writeln(ans, ' ', len);
end.

2. （国王放置）在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x, y)格，国王的攻击的区域是：(x-1,y-1), (x-1,y), (x-1,y+1), (x, y-1), (x,y+1), (x+1,y-1), (x+1,y), (x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。

var    n, m, k, ans: integer; 
   hash: array[0..4, 0..4] of integer;
procedure work(x, y, tot: integer);
var    i, j: integer;
begin
    if tot = k then  begin
        inc(ans);  exit;
    end;
    repeat
        while hash[x, y] <> 0 do  begin
            inc(y);
            if y = m then   begin
                inc(x);    y :=    0   ;
            end;
            if x = n then   exit;
        end;
        for i := x - 1 to x + 1 do
            if (i >= 0) and (i < n) then
                for j := y - 1 to y + 1 do
                    if (j >= 0) and (j <= m) then
       inc(hash[i,j])      ;
      work(x,y,tot+1)      ;
        for i := x - 1 to x + 1 do
            if (i >= 0) and (i < n) then
                for j := y - 1 to y + 1 do
                    if (j >= 0) and (j <= m) then        dec(hash[i,j])      ;
        inc(y);
        if y = m then  begin
            inc(x);  y := 0;
   end;
        if x = n then   exit;
    until false;
end;
begin
    read(n, m, k);    ans := 0;
    fillchar(hash, sizeof(hash), 0);
          work(0,0,0)      ;
    writeln(ans);
end.