2003年NOIP提高组初赛真题

一、单项选择题(共10题，每题1.5分，共计15分。每题有且仅有-个正确答案)。
1. 图灵(Alan Turing)是( )。
  • A. 美国人
  • B. 英国人
  • C. 德国人
  • D. 匈牙利人
  • E. 法国人
2. 第一个给计算机写程序的人是( )。
  • A. Alan MathisonTuring
  • B. Ada Lovelace
  • C. John von Neumann
  • D. John Mc-Carthy
  • E. Edsger Wybe Dijkstra
3. 十进制数2003等值于二进制数( )。
  • A. 0100000111
  • B. 10000011
  • C. 110000111
  • D. 11111010011
  • E. 1111010011
4. 假设A=true,B=false,C=true,D=true，逻辑运算表达式A∧B∨C∧D的值是( )。
  • A. true
  • B. false
  • C. 0
  • D. 1
  • E. NULL
5. 一个高度为h的二叉树最小元素数目是( )。
  • A. 2h+1
  • B. h
  • C. 2h-1
  • D. 2h
  • E. 2h-1
6. 已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。
  • A. 5
  • B. 41
  • C. 77
  • D. 13
  • E. 18
7. 下面一段程序是用( )语言书写的。
　　　　int funcl (int n){
　　　　int i，sum=0；
　　　　for (i = 1；i＜=n；i++)
　　　　sum + = i*i；
　　　　return sum；
　　　　}
  • A. FORTRAN
  • B. PASCAL
  • C. C
  • D. PROLOG
  • E. BASIC
8. 设全集E={1，2，3，4，5}，集合A={1,4}，B={1，2, 5}，C={2，4)，则集合(A∩B)∪～C为( )。
  • A. 空集
  • B. {1}
  • C. {3，5}
  • D. {1，5}
  • E. {1，3，5}
9. 表达式(1+34)*5-56／7的后缀表达式为( )
  • A. 1+34*5-56／7
  • B. -*+1 345／567
  • C. 1 34+5*56 7／-
  • D. 1 345*+56 7／-
  • E. 1 34+5 567-*／
10. 下列计算机设备，既是输入设备，又是输出设备的是( )。
  • A. 键盘
  • B. 触摸屏
  • C. 扫描仪
  • D. 投影仪
  • E. 数字化仪
二、不定项选择题(共10题，每题1.5分，共计15分。多选或少选均不得分)。
11. 下列分辨率的显示器所显示出的图像，最清晰的是( )。
  • A. 800*600
  • B. 1024*768
  • C. 640*480
  • D. 1280*1024
  • E. 800*1000
12. 下列说法中，哪个(些)是错误的( )。
  • A. 程序是指令的序列，它有三种结构：顺序、分支和循环。
  • B. 数据总线决定了中央处理器CPU所能访问的最大内存空间的大小。
  • C. 中央处理器CPU内部有寄存器组，用来存储数据。
  • D. 不同厂家生产的CPU所能处理的指令集是相同的。
  • E. 数据传输过程中可能会出错，奇偶校验法可以检测出数据中那一位在传输中出了差错。
13. CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。
  • A. 寄存器
  • B. 硬盘
  • C. 软盘
  • D. 高速缓存
  • E. 光盘
14. 下列电子邮件地址，哪个(些)是正确的( )。
  • A. wang@hotmail.com
  • B. cai@jcc.pc.too1.rf.edu.jp
  • C. 162.105.111. 22
  • D. ccf.edu.cn
  • E. http://www.sina.com
15. 数字图像文件可以用下列哪个(些)软件来编辑( )。
  • A. 画笔(Paintbrush)
  • B. 记事簿(Notepad)
  • C. Photoshop
  • D. WmRAR
  • E. MidiSoft
16. 下列哪个(些)软件不是操作系统软件的名字( )。
  • A. Windows XP
  • B. DOS
  • C. Linux
  • D. OS／2
  • E. Arch／Info
17. 下列哪个(些)不是个人计算机的硬件组成部分( )。
  • A. 主板
  • B. 虚拟内存
  • C. 电源
  • D. 硬盘
  • E. 总线
18. 运算式(2008)10-(3723)8的结果是( )。
  • A. (-1715)10
  • B. (5)10
  • C. (5)16
  • D. (101)2
  • E. (3263)8
19. 已知元素(8，25，14，87，5l，90，6，19，20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在5l前面；90在87后面；20在14后面；25在6前面；19在90后面。 ( )
  • A. 20，6，8，51，90，25，14，19，87
  • B. 51，6，19，20，14，8，87，90，25
  • C. 19，20，90，7，6，25，5l，14，87
  • D. 6，25，51，8，20，19，90，87，14
  • E. 25，6，8，51，87，90，19，14，20
20. 假设我们用d=(a1，a2，．．．，a5)，表示无向图G的5个顶点的度数，下面给出的哪(些)组d值合理的( )。
  • A. {5，4，4，3，1}
  • B. {4，2，2，1，1}
  • C. {3，3，3，2，2}
  • D. {5，4，3，2，1}
  • E. {2，2，2，2，2)
三．问题求解(共2题，每题5分，共计10分)
21. 无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_________个顶点。
22. 某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程分别为c1，c2，c3，c4，c5，c6，S(ci)为学习ci的学生集合。已知S(ci)∩S(c6)≠?，i=1，2，．．．，5，S(ci)∩S(ci+1)≠?，i=1，2，3，4，S(c5)∩S(c1)≠? ，问至少安排_________天才能考完这6门课程。
四．阅读程序(共4题，每题8分，共计32分)
23. 
program Programl;
　 var a,b,c,d,sum：1ongint; 
　 begin
　　　read (a,b,c,d);
　　　a := a mod 23; b := b mod 28; c := c mod 33 ; 
　　　sum := a* 5544 + b * 14421 + c*1288 - d;
　　　sum := sum + 21252; sum := sum mod 21252;
　　　if (sum = 0) then sum := 21252;
　　　writeln(sum);
　 end． 
输入：283 102 23 320
输出：____①_____
24. 
program Program2;
const
 u：array[1..4] of integer = (0,5,3,1);
 v：array[1..4] 0f integer = (0,7,6,5);
var a,b,c,d,e,f,x,y,z： integer; 
begin
 read (a,b,c,d,e,f);
 z := f + e + d + (c+3) div 4; y := 5 * d + u [ c mod 4 ];
 if (b>y) then
　　begin
　　　z := z+ (b-y+8) div 9;
　　　x := ((b-y+8) div 9 * 9- (b-y)) * 4+11*e+V[c mod 4];
　　　end
　　else
　　　x := (y-b) *4+11*e+v[c mod 4];
　　if (a>x) then
　　　z := z + (a-x+35) div 36;
 writeln(z);
end． 
输入;4 7 9 20 56 47
输出：____①_____
25. 
program Programg3;
var m,n：integer; Mark ：boo1ean;
function test (m,N ：integer)：integer;
var i,p ：integer; flag ：boolean;
begin
　m := m - 1; i := 0; flag := False;
　for p:= 2*N downto (N+1) do
　begin
　　i:= (i+m) mod p;
　　if ( i<N ) then
　　　begin
　　　　test := 0; flag := True; Break;
　　　end
　end;
　if not(flag) then test:=1;
end;
begin
read(n); m := 1; Mark := False;
repeat
　if (test (m,n) = 1) then
　begin writeln(m); break; end;
　m := m+1;
until Mark;
end． 
输入：7
输出：____①_____
26. 
program Programg4;
var m,n,i,j：integer;
　 p,w,a,b：array[0..19] of integer;
begin
 read(n); m:= 0;
 for i:= 0 to n-1 do
 begin read (p[i]); b[i] :=1; end;
 for i := 0 to n-1 do
　 begin
　　 if (i>0) then
　　 a[m]:= p[i]-p[i-1]
　　 else 
　　 a[m]:= p[i];
　　 m:= m+1：
　　 while ((m>1) and (a[rn-1]=0)) do
　　 begin m := m-1; b[m] := l; end;
　　 if (m>0) then
　　　 w[i]:=b[m-1]
　　 else
　　　 w[i]:=b[0];
　　　 a[m-1] := a[m-1]-1;
　　　 for j := 0 to m-1 do b[j] := b[j]+1;
　　　 while ((m>1) and (a[m-1]=0)) do
　　　 begin
　　　　 m := m-1; b[m] :=1;
　　　 end;
　　end;
　　for i := 0 to n-1 do
　　 begin
　　　 write(w[i]); write(' ');
　　 end;
　　writeln(' ');
end． 
输入：9
      4 6 6 6 6 8 9 9 9
输出：____①_____
五．完善程序(共2题，第1题每空3分；第2题每空2分。共计28分)
27. 翻硬币

　　题目描述：

　　一摞硬币共有m枚,每一枚都是正面朝上。取下最上面的一枚硬币,将它翻面后放回原处。然后取下最上面的2枚硬币,将他们一起翻面后再放回原处。再取3枚,取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始,重复刚才的做法。这样一直做下去,直到这摞硬币中的每一枚又都是正面朝上为止。例如,m为1时,翻两次即可。

　　输入：仅有的一个数字是这摞硬币的枚数m,0＜m＜1000。

　　输出：为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。

　　输入样例：30

　　输出样例：899

　　程 序：

program Programl;
var m：integer;
function solve (m：integer) ： integer;
　var i,t,d：integer;
　　　flag ：boolean;
　begin
　　if (m = 1) then
　　　　solve :=  ____①_____ 
　　else begin
　　　　　d := 2*m+1;t :=2;I :=1;flag :=False;
　　　　　repeat
　　　　　　if (t=1) then
　　　　　　　begin
　　　　　　　　solve:= ____②_____ ; flag:=True; 
　　　　　　　end
　　　　　　else if ( ____③_____ ) then
　　　　　　　　　　begin
　　　　　　　　　　　solve:= I * m-1;flag :=True
　　　　　　　　　　end
　　　　　　　　　else
　　　　　　　　　　t := ____④_____ ;
　　　　　　I := i+1;
　　　　　until flag;
　　　　end
　　end;
　begin
　　read (m); if (( ____⑤_____ ) and (m<1000)) then
　　　　writeln ( ____⑥_____ );
　end.
28. OIM地形

二维离散世界有一种地形叫OIM（OI Mountain）。这种山的坡度只能上升（'/'）或下降（'\'），而且两边的山脚都与地平线等高，山上所有地方都不低于地平线。例如：

　　/\　　　　　　　　/\

　 /　\/\ 是一座OIM：而/　\ 不是。

　　　　　　　　　　 　　\/

这个世界的地理学家们为了方便记录，给OIM所有可能的形状用正整数编好号，而且每个正整数恰好对应一种山形。他们规定，若两座山的宽度不同，则较宽的编号较大；若宽度相同，则比较从左边开始第1个坡度不同的地方，坡度上升的编号较大。以下三座OIM的编号由小到大递增：

　　/\　　/\　　　/\　/\

　 /　\/\　/　\/\/\　/　\/　\。显然/\的编号为1。但是地理学家在整理记录时发觉，查找编号与山形的对应关系不是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应给他们写一个程序，输入编号，能马上输出山形。

　　输 入：

　　一个编号(编号大小不超过600，000，000)，

　　输 出：

　　输入编号所对应的山形，l座山所占行数恰为它的高度，即山顶上不能有多余空行。

　　输入样例：

　　15

　　输出样例：

　　　　/\　/\

　　　 /　\/　\



　　程 序：

program Programg2;
const
　L ：integer=19; SZ ：integer=50;
　Up ：char='/';DN ：char'\';
Var
　i,nth,x,y,h,e,f：integer;
　m ：array[0..1,0..38,0..19]0f integer;
　pic：array[0..49,0..49]of char;
procedure init;
　var k,s,a,b,c：integer;
　begin
　　for a := 0 to 1 do
　　　for b :=0 to 2*L do
　　　　for c:=0 to L do
　　　　　m[a,b,c]:=0; m[0,0,0]:=1;
　　for k:=0 to 2*L-1 do
　　begin
　　　for s:=1 to L do
　　　begin 
　　　　m[0,k+1,s]:=m[0,k,s+1]+m[1,k,s+1];
　　　　m[1,k+1,s]:= ____①_____ ;
　　　end;
　　　　m[0,k+1,0]:=m[0,k,1]+m[1,k,1];
　　　end; 
　　end：
　　procedure draw(k,s,nth： integer);
　　begin
　　　if(k=0) then exit;
　　　if ((nth-m[1,k,s])>=0)then
　　　　begin
　　　　　nth:= nth-m[1,k,s];
　　　　　if (y＞h) then ____②_____ ;
　　　　　pic[y,x]:= UP; y:=y+1;x:=x+l; draw( ____③_____ );
　　　　end
　　　　else begin
　　　　　　y:=y-1; pic[y,x]:=DN; x:=x+1; draw(k-1,s-l,nth);
　　　　　end;
　　end：
begin
　init;
　read(nth);
　for e:= 0 to SZ-1 do
　　for f:=0 to SZ-l do
　　　pic[e,f]:=' ';
　　　x:=0;
　　　y:=0;
　　　h:=0;
　　　i:=0;
while((nth-m[0,2*i,0])>=0)do
begin
　nth:=nth-m[0,2*i,0];
　____④_____ ;
end;
draw( ____⑤_____ );
for i := h downto 0 do
begin
　for e :=0 to x-1 do
　write(pic[i,e]);
　writeln(' ');
end;
end.
查看参考答案