NOIP2007年提高组（Pascal语言）初赛试题及答案
一、单项选择题题目:
1. 在以下各项中, ( D ) 不是CPU的组成部分 A. 控制器 B. 运算器 C. 寄存器 D. 主板
E. 算术逻辑单元(ALU)
2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( E )为主 A. 二叉树 B. 多叉树 C. 哈希表 D. C+树 E. 二维表
3. 在下列各项中, 只有( D )不是计算机的存储容量常用单位 A. Byte B. KB C. MB D. UB E. TB
4. ASCII码的含义是 ( B ) A. 二—十进制转换码 B. 美国信息交换标准代码 C. 数字的二进制数码
D. 计算机可处理字符的唯一编码 E. 常用字符的二进制编码
5. 在Pascal语言中, 表达式(23 or 2 xor 5)的值是( A ) A. 18 B. 1 C. 23 D. 32 E. 24
6. 在Pascal语言中, 判断整数a等于0或b等于0或c等于0的正确的条件表达式是( B )
A. not ((a<>0) or (b<>0) or (c<>0)) B. not ((a<>0) and (b<>0) and (c<>0)) C. not ((a=0) and (b=0) and (c=0))
D. (a=0) and (b=0) and (c=0)
E. not ((a=0) or (b=0) or (c=0))
7. 地面上有标号为A、B、C的3根细柱, 在A柱上方有10个直径相同中间有孔的圆盘, 从上到下次编号为1, 2, 3, ??，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么, 在C柱上, 从下到上的盘子的编号为( D ). A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 E. 2 1 4 3 7 5
8. 与十进制数17.5625相对应的8进制数是( B ) A. 21.5625 B. 21.44 C. 21.73 D. 21.731
E. 前4个答案都不对
9. ??在以下各个描述中, 不一定是欧拉图的是:D A. 图G中没有度为奇数的顶点
B. 包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径) C. 包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径) D. 存在一条回路, 通过每个顶点恰好一次
10. ??, 关于死循环的说法中, 只有( A )是正确的.
A. 不存在一种算法, 对任何一个程序及相应输入数据, 都可以判断是否会出现死循环, 因而, 任何编译系统都不作死循环检查. B. 有些编译系统可以检测出死循环.
C. 死循环属于语法错误, 既然编译系统能检查各种语法错误, 当然也可以检查出死循环.
D. 死循环与多进程中出现的\死锁\差不多, 而死锁是可以检查的, 因而, 死循环也是可以检测的
E. 对于死循环, 只能等待发生时作现场处理, 没有什么更积极的手段. 二、不定项选择题目
11. 设A=B=true, C=D=false, 以下逻辑表达是值为真的是( ABC ) ......那3个符号不会打
12. 命题“P->Q”可读做P蕴含Q, 其中P、Q是两个独立的命题. 只有命题P成立而命题Q不成立时, 命题\的值为False, 其它情况均为true. 与命题\等角的逻辑关系式是( AD )
A.(非P)并Q .D.非((非Q)交P)
13. (2070)16+(34)8的结果是 ABD A. (8332)10 B. (208C)16
C. (100000000110)2 D. (20214)8
14. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(??), 后根遍历是4 6 5 2 7 3 1, 则该二叉树的可能的中根遍历是(ABD ) A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3
15. ??下面关于冗余数据的说法中, 正确的是( BC ) A. 应该在数据库中清除一切冗余数据.
B. 与高级语言编写的数据处理系统相比, 用关系数据库编写的系统更容易消除冗余数据.
C. 为高查询效率, 在数据库中可以适当保留一些冗余数据, 但更新时要做相容性检查.
D. 作相容性检查会降低效率, 可以不理睬数据库中的冗余数据.
16. 下列各软件中, 属于NOIP竞赛(复赛)推荐使用的语言环境有(ABD ) A. gcc B. g++
C. Turbo C
D. free pascal
17. 以下断电后仍能保存数据的有( AB ) A. 硬盘 B. ROM C. 显存 D. RAM
18. 在下列关于计算机语言的说法中, 正确的有( CD )
A. 高级语言比汇编语言更高级, 是因为他的程序的运行效率更高.
B. 随着Pascal、C等高级语言的出现, 机器语言和汇编语言已经退出了历史舞台.
C. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上. D. C是一种面向过程的高级计算机语言.
19. 在下列关于算法复杂度的说法中, 正确的有( BC )
A. 算法的时间复杂度, 是指它在某台计算机上具体是现实的运行时间.
B. 算法的时间复杂度, 是指对于该算法的一种或几种主要的运算, 运算的次数与问题的规模之间的函数关系.
C. 一个问题如果是NPC类问题, 就意味着在解决该问题时, 不存在一个具有多项式时间复杂度的算法, 但这一点还没有得到理论上证实, 也没有被否定. D. 一个问题如果是NP类, 与C有相同的结论.
20. ??在下列关于递归的说法中, 正确的是( AC )
A. 在1977年前后形成编成的计算机高级语言\禁止程序使用递归, 原因之一是该方法可能会占用更多的内存空间.
B. 和非递归算法相比, 解决同一个问题, 递归算法一般运行得更快一些. C. 对于较复杂的问题, 用递归方式变成往往比非递归方式更容易一些. D. 对于已定义好的标准数学函数sin(x), 应用程序中的语句\就是一种递归调用.
二、问题求解（共2题，每题5分，共计10分）。
1、（子集划分）将n个数（1，2，…，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=______________。
（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。）
2、（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？___________ B A
三、阅读程序写结果（共4题，每题8分，共计32分。） 1、program j301; var i,a,b,c,x,y:integer; p:array[0..4] of integer; begin y:=20;
for i:=0 to 4 do read(p[i]); readln;
a:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7; b:=p[0]+p[1] div ((p[2]+p[3]) div p[4]); c:=p[0]*p[1] div p[2];
x:=a+b-p[(p[3]+3) mod 4]; if (x>10)
then y:=y+(b*100-a) div (p[p[4] mod 3]*5) else
y:=y+20+(b*100-c) div (p[p[4] mod 3]*5); writeln(x,',',y); end.
{注：本例中，给定的输入数据可以避免分母为0或数组元素下表越界。} 输入：6 6 5 5 3 输出：______________________
2、program j302; var a,b:integer; var x,y:^integer;
procedure fun(a,b:integer); var k:integer;
begin k:=a; a:=b; b:=k; end; begin
a:=3; b:=6; x:=@a; y:=@b; fun(x^,y^); writeln(a,',',b); end.
输出：_______________________________
3、program j303;
var a1:array[1..50] of integer; var i,j,t,t2,n,n2:integer; begin n:=50;
for i:=1 to n do a1[i]:=0; n2:=round(sqrt(n)); for i:=2 to n2 do if (a1[i]=0) then begin
t2:=n div i;
for j:=2 to t2 do a1[i*j]:=1; end; t:=0;
for i:=2 to n do