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

1. 在以下各项中，（ ）不是操作系统软件。

2. 微型计算机中，控制器的基本功能是（ ）。

3. 设字符串S=“Olympic”，S的非空字串的数目是（ ）。

4. 完全二叉树有2*N-1的结点，则它的叶子结点数目是（ ）。

5. 将数组{8，23，4，16，77，-5，53，100}中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（ ）次。

6. 设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（ ）。

7. 与十进制数28.5625相等的四进制数是（ ）

8. 递归过程和函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。

9. TCP/IP 是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际互联协议（IP）。TCP/IP协议把Internet网络系统描述成具有4个层次功能的网络模型，其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。

10. 对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是（）。

1. 下列关于图灵的说法正确的有（ ）。

2. 计算机在工作过程中，若突然停电，（ ）中不会丢失信息不会丢失。

3. 若A=True，B=False，C=True，D=False，以下逻辑运算表达式真的有（ ）。

4. Web2.0是近年来互联网热门概念之一，其核心是互动与分享。下列网站中，（ ）是典型的Web2.0的应用。

5. (2008)10+(5B)16 的结果是（）。

6. 二叉树T，已知其先序遍历是1 2 4 3 5 7 6（数字为节点编号，以下同），后序遍历是4 2 7 5 6 3 1，则该二叉树的中根遍历是（ ）

7. 面向对象的程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序设计的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性、和扩展性。下面关于面向对象的程序设计说法中正确的是（ ）。

8. 设T是一棵有n个定点的树，以下说法正确的是（ ）。

9. NOIP竞赛推荐使用的语言环境有（ ）。

10. 在下列防火墙（Firewall）的说法中，正确的有（ ）。

1. 有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为____________。
答案：7

2. 书架上有21本书，编号从1 到 21 从中选4 本，其中每两本的编号都不相邻的选法一共有___________________种。
答案：3060

1.

var
     i,a,b,c,d:integer;
     f:array[0..3] of integer;
begin
        for i:=0 to 3 do
                read(f[i]);
        a:=f[0]+f[1]+f[2]+f[3];
        a:=a div f[0];
        b:=f[0]+f[2]+f[3];
        c:=(b*f[1]+a) div f[2];
        d:=f[(b div c) mod 4];
        if (f[(a+b+c+d) mod 4]>f[2]) then
        begin
                a:=a+b;
                writeln(a)
        end
else
begin
        c:=c+d;
        writeln(c);
end;
end.

输入： 9  19  29  39
输出：23

2.

procedure foo(a,b,c:integer);
  begin
    if a>b then foo(c,a,b)
else
   writeln(a,',',b,',',c)
end;
var a,b,c:integer;
begin
  readln(a,b,c);
  foo(a,b,c);
end.

输入：2 1 3

输出：1,3,2

3.

procedure f(a,b,c:integer);
begin
  write(a,b,c,'/');
  if (a=3)and(b=2)and(c=1) then exit;
  if (b<c) then f(a,c,b)
else
  if a<b then
   if a<c then f(c,a,b) else f(b,c,a);
end;
var a,b,c:integer;
begin
readln(a,b,c);
f(a,b,c);
end.

输入：1 3 2
输出：132/213/231/312/321/

4.

var
   s:string;
   i,j,len,k:integer;
begin
readln(s);
len:=length(s);
for i:=1 to len do
  if (ord(s[i])>=ord('A')) and (ord(s[i])<=ord('Z')) then
  s[i]::=chr(ord(s[i])-ord('A')+ord('a'));
for i:=1 to len do
if (ord(s[i])<ord('x')) then s:=chr(ord(s[i])+3)
   else
   s[i]:=chr(ord(s[i])-23);
write(s);
write('/');
for j:=1 to 3 do
begin
    i:=1;
  while i<=len-j do
  begin
s[i]:=s[i+j];
i:=i+j;
  end;
end;
writeln(s);
end.

输入：ABCDEFGuvwxyz

输出：defghijxyzabc/hfizxjaybcccc

1. （找第k大的数）给定一个长度为1000000的无序正整数序列，以及另一个数n(1<=n<=1000000)，接下来以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）

Var	 a:array[1..1000000] of integer;
n,m,ans:integer;
procedure swap(var a,b:integer);
var t:integer;
begin
  if  (a<>b) then begin
t:=a; a:=b; b:=t;
end;
end;
Function FindKth(left,right,n:integer):integer;
Var tmp,value,i,j:integer;
begin
  if left=right then exit(left);
  tmp:=random(right-left)+left;
  swap(a[tmp],a[left]);
  value:=  a[left] ;
  i:=left;  j:=right;
while i<j do
  begin
   while (i<j) and ( a[j]<value ) do dec(j);
   if i<j then begin
    a:=a[j];inc(i);
   end else break;
   while (i<j) and ( a[i]>value ) do inc(i);
   if i<j then begin
    a[j]:=a[i]; dec(j);
  end else break;
  end;
   a[i]:=value ;
  if i<n then begin inc(i); exit(FindKth( i,right,n ));end;
  if i>n then begin dec(j); exit( FindKth(left,i,n) );end;
  exit(i);
end;

var i:integer;
begin
  randomize;
   ans:=-1;
m:=5;
for i:=1 to m do
  read(a[i]);
read(n);
ans:=FindKth(1,m,n);
writeln(a[ans]);
end.

2. （矩阵中的数字）有一个n*n（1≤n≤5000)的矩阵a，对于1≤i<n, 1≤j≤n, a[i,j]<a[i+1,j] a[j,i]<a[j,i+1]。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵a中的一个数字k，找出k所在的行列（注意：输入数据保证矩阵中的数各不相同）。

var
    n,k,answerx,answery:integer;
    a:array[1..5000,1..5000] of integer;
Procedure FindKPosition;
Var I,j:integer;
Begin
	i:=n; j:=n;
	while j>0 do begin
           if a[n,j]<k then break;
           dec(j);
        end;
         inc(j) ;
        while a[i,j]<>k do
        begin
           while ( a[i,j]>k ) and (i>1) do dec(i);
           while ( a[i,j]<k ) and (j<=n) do inc(j);
        end;
         answerx:=i ;
         answery:=j ;
end;

var i,j:integer;
begin
   read(n);
   for i:=1 to n do
      for j:=1 to n do
              read(a[i,j]);
      read(k);
      FindKPosition;
   writeln(answerx,' ',answery);
end.