绍兴市第九届少儿信息学奥林匹克竞赛初赛试题 [2011年]

1. “图灵奖”是计算机科学界的诺贝尔奖。迄今为止，我国只有一位科学家获得该项殊荣。 这位科学家是（ ）

2. 文件都以一个个的图标呈现、通过对这驻图标的操作可以实现对文件的各种操作（打开、 复制、粘贴等）、把文件图标拖放到“回收站”中就可以完成文件删除......这些我们目前在 微软公司的Windows操作系统中熟知的技术称为“图形用户界而”。早期的计算机使用可没这么方便，而是晦涩难懂的命令用户界面（如下图-1所示）。 前面所述典型的图形用户界面技术并不是微软公司首创的。最早将这种图形用户界面H 用到它们自己生产计算机上的公司是（ ）

3. 班级进行班长竞选，需要集成介绍自己的文字、照片材料，并将这些材料在自己演讲时通过教室里连接了计算机的大屏蒂投影机演示。制作这个材料最合适的软件是（ ）

4. 小薇要将自己计算机硬盘中一张电子贺卡（图像文件）以电子邮件的附件形式发送给朋 友（操作界面如图-2所示）。为了将该图像文件作为附件添加到邮件中,应选择的操作是( )

5. 为了将浏览网页时看到的图片保存到自己的计算机上，可以将鼠标移到该图片上，单击鼠标右键，然后在如图-3所示的快捷菜单中选择菜单命令（ ）

6. 下列有关信息使用的行为，最恰当的是（）

7. 为了给自己的QQ设置密码，下列密码中安全性最好的是（ ）

8. 在下列计算机硬件设备中，承担“计算”任务的设备是（ ）

9. 在pascal中，“SHR x”命令的作用是将一个数对应的二进制数各位置上的数字右移x个位置，前面（高位）新位置用零补充。如对二进制数（01100011) 2执行“SHR 2”命令后的结果就是（00011000)2。则，对十进制数23执行命令“SHR 2”后结果为（ ）

10. 二进制加法表达式（1001)2+ (1101)2的计算结果为（ ）

11. 如图-4所示，有数字队列1, 2, 3, 4, ...，9,按照堆栈操作序列“进、进、进、出、进、出、进、出”对右边队列中的数字逐个进行操作。上述操作结束后，堆栈左边队列中存在数字依次为（自左往右）（ ）

12. 有K列处理步骒： ① 输出变量s的值 ② S初始化为零 ③ 输入正整数n ④ 循环变量i从1逐次增加1,直到变为n。i每变一次就执行一次“s:=s+i” 若要计算1+2+3+....+n的和并输出，则上述步骤正确的排列顺序是（ ）

13. 计算机科学中的“图”指的是“有几个点和边组成的特殊图形（如下图-5所示），其中内有数字的圆圈表示点，点之间的直线叫做边”。 我们可用二维数组a[i,j]来表示该图中点之间的关系： 如果点i和j之间有边直接相连，则让a[i,j]=l (当然a[j，i]也为1),否则让a[i,j]=0(当然a[j,i]也为零)。按照这种方法来表示图-5所示的图，则有a[l,2[=l，a[l，3]=0,??，那么 a[2，l], a[3,2]，a[2,4], a[4,5]的值应该依次为（ ）

14. 下表是对原始数列“34, 12, 23, 26, 15, 8, 48”进行从小到大样序的过程（采用冒泡排序），按照下表信息以及冒泡排序算法的思想，则表中第三趟冒泡结束时的数列应为（ ）

15. “全国青少年信息学奥林匹克竞赛”的英文缩写是（ ）

1. 最少公路造价。某市想在6个区域之间建造若干条公路（如图所示，带数字的圆 圈表示区域，虚线表示计划可能建造的所有公路，边上的数字表示该段公路建造需要的资金数目），使得任何两个区域之间都能通过若千条公路到达。比如，图-7所示就是第一种满足要求的公路建造方案，一共需要建造5条公路，总的建造价格是37:图-8所示是第二种满足要求的方案，一共需要建造5条公路，总的建造价格是39。显然，第一种建造方案更省钱。 问：（1)满足要求的公路建造方案中，最少需要建造_____条公路。 (2)在所有满足要求的公路建造方案中，最省钱的方案所需要的费用是_____。
答案：5|30

2. 切蛋糕。当我们刀锋向下在一个蛋糕上从上往下切一刀时，可以知道蛋糕上表痕迹如图-9辦示，此时将蛋糕切成了2块。如果继续切一刀（一共切了 2刀），我们知道可以分别有如图-10和图-11所示的两种情形。显然，图-11所示的蛋糕被切成了更多的块数（图-10所示被切成3块，图-11所示被切成4块)。 问：（1)按上述方法一共切4刀，蛋糕最多能被切成的块数为______。 (2)至少切________刀，蛋糕能被切成56块。
答案：11|10

1.

先自学阅读材料，然后分析程序并写出程序运行结果。
【阅读材料】在PASCAL语言中，分支结构语句除了 IF语句之外还有CASE语句，CASE 语句的使用格式如下：
Case表达式of
常数表1: 语句1;
常数表2: 语句2;
.......;
Else 语句 n;
End;
  程序运行时先计算表达式的值，如果表达式的值在常数表1中则执行语句1，然后退出case语句;如果表达式的值在常数表2中则执行语句2,然后退出case语句......；如果表达式的值在前面所有常量表中都没有出现则执行else后面的语句n，然后退出case语句。 
program test_2011_1;
var
x, y, s: integer;
begin
readln(x, y);
case x mod y of   {mod表示取余运算，如8 mod 3 的值为 2}
1,2:s:=1;
0:s:=3;
else s:=2;
end;
writeln(s);
end.

(1)输入：12 3
(2)输入：123 8
输出：3|2

2.

program test_2011_2;
var
x,y:integer;
begin
x:=12;y:=31;
x:=x+y;y:=x-y;x:=x-y;
write(x,‘ ’，y);
end.
输出：31 12

3.

Program test_2011_3;
var
sum:array[0..10, 0..10] of integer;
s,num:array[1.. 10] of integer;
a, b, c, d, n, m, ans, now, i, j: integer;
begin
readln(n, m);
for i:=1 to 10 do s[i]:=0;
for i:=0 to 10 do
for j:=0 to 10 do sum[i, j]:=0;
for a := 1 to n do
begin
for b := 1 to m do
begin
read(num[b]);
s[b]:=s[b] + num[b];
sum [a, b] := sum[a, b-1] + s[b];
end;
readln;
end;
ans:= -32766;
for a := 1 to n do
 for b := 1 to m do
  for c := a to n do
    for d := b to m do
	begin
	  now:=sum[c, d] - sum[a-1, d] - sum[c, b-1] + sum[a-1, b-1];
	  if ans<now then ans:= now;
	end;
  writeln(ans);
end.
(1)输入：
1 3
12 3 -4
输出：
(1)输入：
3 3
12 -10 21
-2 9 3
1 4 -6

输出：15|33

4.

program test_2011_4;
var
i, j, k, x, n, ans, s: integer;
a:array[1..500] of integer;
f:boolean;
begin
readln (n, x);
for i:=1 to n do read(a[i]);
i:=1;j:=n;f:=false;s:=0;
while (i<=j) and not f do
begin
k:=trunc((i+j)/2);s:=s+1;
if x=a[k] then
begin
ans:=k;f:=true;
end
else if x<a[k] then j:=k-1 else i:=k+1; end;
if f then write(ans,’ ’，s) else write(s);
end.
(1) 输入：
4 11
7 9 11 17

(2) 输入：
20 256
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 101 105 109 110 138
输出：3 2|5

1. 【山脉】（3+3+3+3=12分）
绍兴的南部是山区，小薇站在这些山脉的某座山峰上向南眺望，看到的是一座座的山峰。现在小薇告诉你自北向南所有山峰的高度，并且告诉你她目前所在的山峰，当她站在该山峰上向南眺望时一共能看到多少座山峰。为了方便计算，小薇还制定下列规定：
(1)所有的山脉自北向南成一条直线排列。这就意味着如果南部的某座山峰（比如说自北向南的第i座山峰）髙度小于北面的山峰（比如说自北向南的第i-1座，或者也可以是第i-2座，第i-3座...），则南面的这座山峰小薇将无法看到。
(2)如果南面山峰高度等于北面山峰高度，则南面的山峰也无法看到。
输入数据第一行包含两个整数n和x。n表示总的山峰数量（不超过100), x表示小薇 当前所在山峰的编号（自北向南顺序编号，x<n)。第二行包含n个整数，依次表示自北向 南成一条直线排列的山峰的高度值（单位都是“米”)。
输出数据包含一行一个整数，表示小薇站在第x座山峰上向南眺望时最多能看到的山峰的个数。
下面是用来解决该问题的程序，请完替程序。
输入样例1:
10 4
34 23 35 22 21 19 25 29 31 28
输出样例1:
4 //看到的山脉高度依次是：21、25、29、31
输入样例2:
12 3
45 32 44 45 47 48 51 54 54 53 59 61
输出样例2:
7 //看到的山脉高度依次是：45、47、48、51、54、59、61

program test_2011_5;
var
 i, h, s, x, n: integer;
 a:array[1.. 100] of integer;
begin
 readln(n, x);
 for i:=1 to n do read(a[i]);
 s:=1;h:=a[x+1];
 for i:=x+2 to n do begin
 if a[i]>h then
  begin
   h:=a[i]; inc(s) ;
  end;
 end;
 write (s);
end.

2. 【猪圈】（2+2+3+3+3+3*16分）
小薇的外公有一个养猪场，一共养了C头猪，养猪场里有S个宽度都为1米的猪圈， 每个猪圈最多养1头猪。由于年久失修，猪圈前面的木护栏都需要更换了。
木材商最多只能提供给小薇的外公M块木板（每块木板的长度可以任意选择)，外公当然想用最少的钱把那些有猪的猪圈前面用木板拦起来，外公想请小薇帮助计算一下，要把那些有猪的猪圈前面用木板拦起来，最少需要的木板总长度是多少？参加信息学奥赛的小薇当然会用程序来解决这个问题。
己知输入数据的第一行是三个整数M (1<=M<=50), S（1<=S<=200), C (1<=C<=S), 接下来共有C行，每行包含一个整数X (1<=X<=S)，表示某头猪所在猪圈的编号。
小薇的程序要求能输出一行一个整数，表示所需木板的最小总长度。
请帮助小薇完善下面的程序。
输入样例1:
2 104
2
4
6
8
输出样例2:
6
【样例1数据说明】
由于最多只有两块板可以使用，所以第一块板将2到4号猪圈拦起来，第二块板将6到8号猪圈拦起来，这是需要木板总长度最少的方案，总共需要3+3=6米的长度。

输入样例2:
50 30 6
30
25
5
15
10
20
输出样例2:
6
【样例2数据说明】
由于最多可以使用50块板，而只有6个猪圈有猪。只要选择6块长度都为1米的木板， 依次将6个猪圈拦起来即可。最少的总长度就是1+1+1+1+1+1=6米。

program test_2011_6;
type arr=array[l.. 10000]of longint;
var
  a, b:arr;
  j，m, c, s, sum:longint;
  procedure swap(var x, y:longint);
  var
    t:longint;
  begin
    t:=x; x:=y ；y:=t ；
  end;
begin
  readln(m, s, c); sum:=0;
  if m>c then writeln( c )else
  begin
  for i:=l to c do readln(a[i]);
    for i:=l to c-1 do
	  for j:= c downto i+1 do
	    if a[j-l]>a[j] then swap(a[j-l], a[j]);
  j:=l；
  for i:=l to c-1 do
  begin
    b[j]:=a[i+l]-a[i];
	j:= j+1 ；
  end;
  for i:=l to c-2 do
    for j:=c-l downto i+1 do
	  if b[j-l]>b[j] then swap(b[j-l], b[j]);
  for j:=l to c-m do
  begin
    sum:=sum+b[j];
  end;
  writeln ( sum );
  end;
end.