2014年义乌市小学信息学奥林匹克竞赛试题(附答案)

2014年义乌市小学信息学奥林匹克竞赛试题

（小学组 pascal语言 二小时完成）姓名：一、 单选（每题1.5分共30分）

1、与十进制数29等值的二进制数是（A ）

A． 11101 B.11001 C.10111 D.11011 2、右图是一张黑白两色位图，假如使用0表示白色，1表示黑色那么

这幅黑白两色位置对应的二进制编码为（B ）

A．0100011 B.1011100 C.1000011 D.0100001

3、上题中的黑白两色位置如果要在计算机内部完整地保存，在不进行压缩的前提下，最少需要多少存储空间（C）

A． 8Byte B. 8KB C. 8bit D.8MB

4、下列计算机设备中，属于存储设备的是（B）

A．键盘 B.RAM C.显示器 D.CPU

5、下列选项中，对计算机运行速度的快慢没有影响的是：（D）

A．CPU B.内在 C.硬盘缓存 D.显示器的屏幕尺寸

6、下面是计算机操作系统的是（D）

A．Free Pascal B.Adobe Photoshop C.Microsoft Word D.Linux

7、下列关于计算机病毒的描述中，正确的是（C）

A．如果某人有感冒病毒，那么他使用的计算机就有可能感染病毒，并最终发展为计算机病毒

B.如果计算机在生产厂家组装时周围环境不好（有灰尘等），计算机就会有计算机病毒

C.计算机病毒实质上是一段计算机程序

D.计算机病毒只能通过计算机网络传播

8、关于网页中的超链接，下列说法正确的是：（A）

A．超链接的HTML标志是<a> B.一张网页只能包含一个超链接

C. 将网页保存为文本文件后，超链接依然存在

D.超链接的对象只能是另一张网页。

9、下面列出的文件，不能用windows附件中画图程序打开的是（C）

A．apple.bmp B.banana.jpg C.orange.raw D.pear.png

10、关于电子邮件的叙述，正确的是（B）

A．发送方和接收方必须同时开机才能传送电子邮件

B.打开电子邮件的附件可能会传染计算机病毒

C.同一个E－Mail帐号不能同时设置在多台计算机上

D.发送电子邮件是，接收方地址不能与发送方相同。

11、为了能在Internet上浏览网页，需要在我们的电脑上安装浏览器，国产如360安全浏览器，腾讯TT浏览器。下列不属于浏览器软件的是（D）

A．Internet Explorer B.Google Chrome C.Opera D.Fireworks

12、下列有关算法的理解，不正确的是（C）

A．计算机算法必须要有结果输出

B.算法的每一步必须是明确的、无异议的

C.对于顺序结构、选择结构、循环结构这三种算法流程，解决同一个问题只能用一种结构

D.递归算法就是在某个过程或函数中，自己调用了自己。

13、若变量a的值是13，b的值是100，x的值是8。下列各表达式中，结果是true的是（C）

A．’a’>’x’ B.(a>=b) and (a<>x)

C. (a-b)>x or x>(b div a) D.(b div a)*a=b or (b div x)*x=b

14、在pascal表达式中，变量 a的初始值是24，变量b的初始值是5，变量 c的初始值是3。下列哪个表达式的运算值和其他不一样？（B）

A．sqrt(a+1) B.trunc(a/b) C.round(a/b) D.c div a +b

15、数组在计算机内在中一般是按行优先的顺序连续存放的，对于二维数组a[1..5,1..9],每个元素占两个字节，已知a[1,1]的起始地址是1000，则a[5，5]的起始地址是：（B）

A．1082 B.1080 C.1068 D.1066

16、对于一组数{6、13、27、29、52、27、81}，现要对其从小到大排序，采用纯粹的冒泡排序算法，需要两两比较次数是（B）

A．42次 B.21次 C.49次 D.2次

17、已知一个顺序表由128个从小到大排列的整数组成，那么依次采用顺序查找算法，最坏情况下的查找次数是（A）

A．128 B.64 C.7 D.10

18、地面上有标号为A、B、C的三根细柱，一开始A柱上穿有5个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，4，5，将A柱上的盘子经过B柱移入C柱，也可以在B柱上暂存，但最终都要移入C柱。每次只能移动一个盘（不能多个盘叠在一起移）。那么C柱上的盘子从下到上编号不可能出现的是（D）

A．1 2 3 4 5 B.5 4 3 2 1 C.1 4 5 3 2 D.1 5 4 2 3

19、满二叉树一种特殊的二叉树，它除了最底下一层的结点没有任何子结点外其

他所有节点都有两个儿子结点，如右图是一颗3层的满二叉树。那么，一棵有5

层满二叉树，一共有几个结点？（C）

A．15 B.16 C.31 D.31

20、下列图中，不能用“一笔画”（经过每条边一次且仅一次）画出的图是：（B）

A．图20.1 B.图20.2 C.图20.3 D.图20.4

二、 问题求解（每题5分，共10分）

1、某酒店共有9层楼，除第一层安排大堂和餐厅、第七层安排会议室以外，其余的楼层都是客房。每个客房的编号是一个三位数：第一位表示楼层号，第二、第三位表示房间号，房间号从1开始。如801就表示八楼的第1个房间，844表示八楼的第44个房间 用这种编号方法最多可以标识 693 个房间。

2、“完全二叉树”又是另外一种特殊的二叉树，这种二叉树除最后一层外，其余层的结点个数也都达到最大；而最后一层的所有结点都分布在左边连续的位置上。比如下图中图2.1是完全二叉树，图2.3不是。完全二叉树可以用一个数组来保存，图2.1的完全二叉树各结点对应的数组元素如图2.2所示。由此我们可以计算：倘若第k个结点的右孩子如果存在的话，应当放在数组的第 23 号位置。

三、 阅读程序（每题8分，共32分）

1、

program ywnoip01;

var

x,y,z:longint;

begin

readln(x,y);

x:=x+y;

y:=x-y;

x:=x-y;

writeln(x,’ ’,y);

end.

输入：37 19

输出： 19 37

2、

program ywnoip02;

var

sum,max:longint;

begin

readln(max);

sum:=0;

for i:=1 to max do

begin

if i mod 2=0 then

sum:sum+i;

end;

writeln(sum);

end.

输入：200

输出： 10100

3、

program ywnoip03;

var

n:integer;

function f(n:integer):longint;

begin

if n=0 then

f:=1

else if n<0 then

f:=f(n+1)-n

else

f:=f(n-1)-n

end;

readln(n);

writeln(f(f(n)));

end.

输入：3

输出： 16

4 .

program ywniop04

const

s = ′0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ′;

base = 16;

var

i , j , n , tmp : interger ;

a : array [1..100] of char;

begin

readln ( n ) ;

i : = 0 ;

while n > 0 do

begin

inc ( i ) ;

tmp : = n mod base ;

a[i] : = s[tmp + 1] ;

n : = n div base

end ;

if i = 0 then

write (0)

else

for j : = i downto 1 do

write ( a[j] ) ;

writeln ;

end .

输入 ： 16154

输出 ： 3F1A

四、 完善程序（第1题每空2分，第2题每空3分，共28分）

1．【同洞寻宝（一）】经过艰苦跋涉，杰克和他的朋友们终于找到了埋藏在山洞的宝藏。幽幽漫长的山洞中包含了n个房间，每个房间中k堆金币，每堆金币都有一定的价值。由于时间限制，

每个房间只够拿一堆金币—— 很显然，肯定拿那堆价值最大的金币。输入数据的第一行是房间数n。接下来的n行每行描述了房间的金币情况：第一个数是金币的堆数k，然后是k个整数，表示每一堆金币的价值。那么杰克他们总共能拿到多少金币呢？输出这个总价值。

【输入样例】

4

3 2 2 5

5 3 3 4 4 1

2 30 23

5 10 20 30 20 30

【输出样例】

TOTAL = 69

【程序说明】 房间中的每堆金币读入到a[i]数组中。max(x)函数能求出a[1..x]中的最大值。 program ywniop05;

i , j , k , n , total : integer ;

a : array [ 1.. 100] of integer ;

function max (x : integer ) : integer ;

var

i : integer ;

begin

max : = a[1];

for i: = 2 to x do

if ①max<a[i] then

②max:=a[i] ;

end;

begin

③readln(n) ;

total : = 0 ;

for i := 1 to n do

begin

④read(k) ;

for j : = 1 to k do

Read ( a[j] );

Readln ;

total : = ⑤total+max(k) ;

end;

writeln ( ′TOTAL = ′ ,total ) ;

end .

2．【同洞寻宝（二）】杰克和他的朋友们从山洞的每个房间都拿出了最大的那堆金币，总计n堆金币。现在他们发现又要面临一个新问题：如何消耗最少的体力，把这n堆金币合并成一堆？合并所消耗的体力等于每次合并两堆金币的重量之和（假设金币的价值和重量相等）。每次合并，他们会把两堆金币合并到一起，n堆金币经过n-1次合并之后就只剩一堆了。

比如，n=3时表示共有3堆金币，每堆重量分别是2、1、9。一种合并方案是2和9合并，新堆重量是11，耗费体力为11；接着11与1合并，新堆重量是12，耗费体力为12，因此总消耗体力是11+12=23。另一种方案是：1和2合并，新堆重量是3，耗费体力为3；接着3现9合并，新堆重量是12，耗费体力为12，因此总消耗体力是3+12=15。可以证明这就是最少耗费体力。

输入数据的第一行是n，表示金币的堆数；第二行是每堆金币的重量（价值）。输出最少耗费体力数。

【输入样例】

3

2 1 9

【输出样例】

15

【程序说明】 程序中sort(x)过程式的功能是对a[x n]中的数进行从小到大排序，然后将重量最小的两堆金币合并，合并后的新值放入数列中重新排序，再取出重量最小的两堆合并。。。。。每次合并后将体力消耗值累加到sum变量中，经过n-1次合并后，所有金币后，所有金币都合并成了一堆，输出sum就是最少的消耗体力值。

program ywniop06;

var

i ,sum,n:integer;

a: array[1..100] of integer ;

procedure sort (x :integer) ;

var

i ,j ,temp : integer ;

begin

for i : = ① x to n-1 do

for j : = n downto ② i+1 do

if ③a[j]<a[j-1] then

begin

tmp : = a[j]

a[j] : = a[j-1]

a[j-1]: = tmp

end ;

end ;

begin

readln(n) ;

for i : = 1 to n do

read (a [i] ) ;

④sum:=0 ;

sort ( 1 ) ;

for i : =1 to n-1 do

begin

a[ i +1 ] : = a[ i ] + a [ i +1 ] ;

sum:= ⑤sum+a[i+1] ;

⑥sort(i+1) ;

end ;

writeln (sum) ;

end .

2012年义乌小学组信息学奥赛试题答案

一、选择题

ABCBD

第1题十进制转二进制短除法或29＝16+8+4+1＝2^4+2^3+2^2+2^0=二进制数10000+1000+100+1＝11101 第2题1011100

第3题1个字节B，8个位bit

第4题可以存储的是RAM

第5题 显示器是输出设备，不参与数据运算，所以与计算机快慢无关

DCACB

第6题Linux

第7题

第8题。.RAW图像就是CMOS或者CCD图像感应器将捕捉到的光源信号转化为数字信号的原始数据，不能用画图直接打开

第9题

第10题 Fireworks是图像处理软件

DCCBB

第11题

第12题算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。

第13题

第14题

第15题 起始地址+（数组元数个数-1）*每个变量所占字节数

BADCB

第16题7个数字组成的数，用冒泡从小到大排序for i:=1 to 6 do for j:=i+1 to 7 do所以循环次数是6+5+4+3+2+1＝21次

第17题顺序表最坏情况是放在最后一个。

第18题用栈去验证

第19题5层满二叉树有几个结点，就是求2^0+2^1+2^2+2^3+2^4+ +2^n＝2^(n+1)-1,所以2^5-1 第20题就是“一笔画”问题，一笔画特点：1、图形中没有单数点，一定可以一笔画成，画时可以以任

意一个双数点为起点；2、图形中只有2个单数点的，一定可以一笔画成，画时必须以一个单数点为起点，最后以另一个单数点为终点。3、凡是图形中单数点多于2个时，此图不能一笔画成。

二、问题求解

1、693

（这一题是9层，去除2层没有房间，只有7层有房间，每个房间编号是3个数字，第1个数字是层数，所以每层最多可以编号99个房间，共99*7个房间可以编号。）

2、23

（这一题有歧义，是指第K个结点还是指第W个结点的位置？我是按第W个结点的位置来做的。）

三、阅读程序

1、

19 37

(分析：互换位置)

2、

10100

(分析：求200以内的偶数等差数列和 （首项+尾项）*项数/公差)

3、

16

（分析：递归）

4、

3F1A

（分析：10进制转16进制）

四、程序填空

1、

①max<a[i] ②max:=a[i] ③ readln(n) ④read(k) ⑤total+max(k)

2、

①x ②i+1 ③a[j]<a[j-1] ④sum:=0 ⑤sum+a[i+1] ⑥sort(i+1)

本文来源：https://www.bwwdw.com/article/9ndi.html