2004年NOIP提高组初赛真题

一、 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。

1. 设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合(A-B)∪(~C∩B) 为（ ）。

• A. {a, b, c, d}
• B. {a, b, d, e}
• C. {b, d, e}
• D. {b, c, d, e}
• E. {d, f, g}

2. 由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个。

• A. 40320
• B. 39600
• C. 840
• D. 780
• E. 60

3. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ ）。

• A. 1, 2, 3, 4, 5
• B. 1, 2, 4, 5, 7
• C. 1, 3, 5, 4, 6
• D. 1, 3, 5, 6, 7
• E. 1, 3, 6, 5, 7

4. 满二叉树的叶结点个数为N，则它的结点总数为（ ）。

• A. N
• B. 2 * N
• C. 2 * N – 1
• D. 2 * N + 1
• E. 2N – 1

5. 二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。

• A. 4 2 5 7 6 3 1
• B. 4 2 7 5 6 3 1
• C. 4 2 7 5 3 6 1
• D. 4 7 2 3 5 6 1
• E. 4 5 2 6 3 7 1

6. 十进制数100.625等值于二进制数（ ）。

• A. 1001100.101
• B. 1100100.101
• C. 1100100.011
• D. 1001100.11
• E. 1001100.01

7. 下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。

• A. CPU
• B. 图形卡（显卡）
• C. 光驱
• D. 主板
• E. 内存

8. 下列哪个网络上常用的名字缩写是错误的（ ）。

• A. WWW（World Wide Web）
• B. URL（Uniform Resource Locator）
• C. HTTP（Hypertext Transfer Protocol）
• D. FTP（Fast Transfer Protocol）
• E. TCP（Transfer Control Protocol）

9. 用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ ）。

• A. 针式打印机
• B. 喷墨打印机
• C. 激光打印机
• D. 笔式绘图仪
• E. 喷墨绘图仪

10. 一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（ ）。

• A. 调制解调器
• B. 路由器
• C. 网卡
• D. 网关
• E. 网桥

二、 不定项选择题 （共10题，每题1.5分，共计15分。多选或少选均不得分）。

11. 美籍匈牙利数学家冯•诺依曼对计算机科学发展所做出的贡献包括（ ）。

• A. 提出理想计算机的数学模型，成为计算机科学的理论基础。
• B. 提出存储程序工作原理，对现代电子计算机的发展产生深远影响。
• C. 设计出第一台具有存储程序功能的计算机EDVAC。
• D. 采用集成电路作为计算机的主要功能部件。
• E. 指出计算机性能将以每两年翻一番的速度向前发展。

12. 下列哪个（些）是64位处理器（ ）。

• A. Intel Itanium
• B. Intel Pentium III
• C. AMD Athlon64
• D. AMD Opteron
• E. IBM Power 5

13. (2004)10 + (32)16的结果是（ ）。

• A. (2036)16
• B. (2054)10
• C. (4006)8
• D. (100000000110)2
• E. (2036)10

14. 下列哪个（些）不是数据库软件的名称（ ）。

• A. MySQL
• B. SQL Server
• C. Oracle
• D. Outlook
• E. Foxpro

15. 下列哪个（些）不是计算机的存储设备（ ）。

• A. 文件管理器
• B. 内存
• C. 显卡
• D. 硬盘
• E. U盘

16. 下列哪个（些）软件属于操作系统软件（ ）。

• A. Microsoft Word
• B. Windows XP
• C. Foxmail
• D. 金山影霸
• E. Red Hat Linux

17. 下列说法中正确的有（ ）。

• A. CPU的基本功能就是执行指令。
• B. CPU的主频是指CPU在1秒内完成的指令周期数，主频越快的CPU速度一定越快。
• C. 内部构造不同的CPU运行相同的机器语言程序，一定会产生不同的结果。
• D. 在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。
• E. 数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。

18. 彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ）。

• A. 红
• B. 白
• C. 蓝
• D. 绿
• E. 橙

19. 下列哪个（些）程序设计语言支持面向对象程序设计方法（ ）。

• A. C++
• B. Object Pascal
• C. C
• D. Smalltalk
• E. Java

20.
某大学计算机专业的必修课及其先修课程如下表所示：
请你判断下列课程安排方案哪个（些）是合理的（ ）。

• A. C0, C1, C2, C3, C4, C5, C6, C7
• B. C0, C1, C2, C3, C4, C6, C7, C5
• C. C0, C1, C6, C7, C2, C3, C4, C5
• D. C0, C1, C6, C7, C5, C2, C3, C4
• E. C0, C1, C2, C3, C6, C7, C5, C4

三．问题求解（共2题，每题5分，共计10分）

21. 75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有_________名儿童没有玩过其中任何一种。

22. 已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案：_________。

四．阅读程序（共4题，每题8分，共计32分）

23.

program progam1;
var
	u: array [0..3] of integer;
	a, b, c, x, y, z: integer;
begin
	read(u[0], u[1], u[2], u[3]);
	a := u[0] + u[1] + u[2] + u[3] - 5;
	b := u[0] * (u[1] - u[2] div u[3] + 8);
	c := u[0] * u[1] div u[2] * u[3];
	x := (a + b + 2) * 3 - u[(c + 3) mod 4];
	y := (c * 100 - 13) div a div (u[b mod 3] * 5);
	if((x+y) mod 2 = 0) then z := (a + b + c + x + y) div 2;
	z := (a + b + c – x - y) * 2;
	writeln(x + y - z);
end.
输入：2 5 7 4
输出：____①_____

24.

program program2;
var
	i, number, ndata, sum: integer;
	data: array[1..100] of integer;
procedure solve(s, sign, n: integer);
var i: integer;
begin
    for i := s to ndata do begin
        inc(sum, sign * (number div (n * data[i])));
        solve(i + 1, -sign, n * data[i]);
    end;
end;
begin
	read(number ,ndata);
	sum := 0;
	for i := 1 to ndata do read(data[i]);
	solve(1, 1, 1);
	writeln(sum);
end.
输入：1000 3 5 13 11
输出：____①_____

25.

program program3;
var c: array[1..3] of string[200];
    s: array[1..10] of integer;
    m, n, i: integer;
procedure numara;
var cod: boolean;
     i, j, nr: integer;
begin
	for j := 1 to n do begin
		nr := 0; cod := true;
		for i := 1 to m do
			if c[i, j] = '1' then begin
				if not cod then begin
					cod := true; inc(s[nr]); nr := 0;
				end
			end
			else begin
				if cod then begin
					nr := 1; cod := false;
				end
				else inc(nr);
			end;
		if not cod then inc(s[nr]);
	end;
end;
begin
	readln(m, n);
	for i := 1 to m do readln(c[i]);
	numara;
	for i := 1 to m do
		if s[i] <> 0 then write(i, ' ', s[i], ' ');
end.
输入：
3 10
1110000111
1100001111
1000000011
输出：____①_____

26.

program program4;
const
	u: array[0..2] of integer = (1, -3, 2);
	v: array[0..1] of integer = (-2, 3);
var
	i, n, sum: integer;
function g(n: integer): integer;
var i, sum: integer;
begin
	sum := 0;
	for i := 1 to n do inc(sum, u[i mod 3] * i);
	g := sum;
end;
begin
	sum := 0;
	read(n);
	for i := 1 to n do inc(sum, v[i mod 2] * g(i));
	writeln(sum);
end.
输入：103
输出：____①_____

五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)

27. Joseph

题目描述:

原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。

现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。

输入:

仅有的一个数字是k（0 < k <14）。

输出:

使得最先出列的k个人都是坏人的m的最小值。

输入样例:

4

输出样例:

30

程序：

program program1;
var
	i, k, m, start: longint;
	find: boolean;
function check(remain: integer): boolean;
var result: integer;
begin
	result:=  ____①_____  mod remain;
	if(  ____②_____  )then begin
		start := result; check := true;
	end
	else check := false;
end;
begin
	find := false;
	read(k);
	m := k;
	while (  ____③_____  ) do begin
		find := true; start := 0;
		for i := 0 to k-1 do
			if( not check(  ____④_____  )) then begin
				find := false; break;
			end;
		inc(m);
	end;
	writeln(  ____⑤_____  );
end.

28. 逻辑游戏

题目描述:

一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。

对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。



输入:

输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。

输入的第一行是n（0
输出:

当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。

输入样例:

3

1 1 2

1 2 2

1 1 2

输出样例:

YES

程序：

program program2;
const
	d: array[0..7] of integer = (1, 0, -1, 0, 0, 1, ____①_____  );
var
	orig, n, i, j, ns: integer;
    a: array[0..101, 0..101] of integer;
    bun: boolean;
procedure plimba(x, y: integer);
var i, x1, y1: integer;
begin
	a[x, y] := -a[x, y];
	if (abs(a[x - 1, y]) <> orig) and ((  ____②_____  <> a[x - 1, y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
	if (abs(a[x + 1, y]) <> orig) and ((a[x + 1, y - 1] <> a[x + 1,y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
	if (abs(a[x, y - 1]) <> orig) and ((  ____③_____ <> a[x, y - 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
	if (abs(a[x, y + 1]) <> orig) and ((a[x - 1, y + 1] <> a[x,y + 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
	for i := 0 to 3 do begin
		x1 := x + d[2 * i];y1:=y+ ____④_____ ;
		if (x1 >= 1) and (x1 <= n) and (y1 >= 1) and (y1 <= n) and 
(  ____⑤_____  ) then plimba(x1, y1);
	end;
end;
begin
	bun := true;
	read(n);
	for i := 0 to n+1 do 
for j := 0 to n+1 do a[i, j] := 0;
	a[0, 0] := -1; a[n + 1, 0] := -1;
	a[0, n + 1] := -1; a[n + 1, n + 1] := -1;
	for i := 1 to n do 
for j := 1 to n do read(a[i, j]);
	for i := 1 to n do 
for j := 1 to n do 
if a[i, j] > -1 then begin
				ns := 0;  ____⑥_____  ;
				plimba(i, j);
				if ns mod 2 = 1 then bun := false;
			end;
	if bun then writeln('YES');
	if not bun then writeln('NO');
end.