第1个回答 2012-07-17
NOIP2007年提高组（Pascal语言）初赛试题2007年10月24日 星期三 13:231. 在以下各项中, ( 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不成立时, 命
题"P->Q"的值为False, 其它情况均为true. 与命题"P->Q"等角的逻辑关系式是( AD )
还是不会打那几个符号
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. 近20年来, 许多计算机专家都大力推崇递归算法, 认为它是解决较复杂问题的强有力的工具. 在下
列关于递归的说法中, 正确的是( AC )
A. 在1977年前后形成标准的计算机高级语言"FORTRAN77"禁止在程序使用递归, 原因之一是该方法可能
会占用更多的内存空间.
B. 和非递归算法相比, 解决同一个问题, 递归算法一般运行得更快一些.
C. 对于较复杂的问题, 用递归方式编程往往比非递归方式更容易一些.
D. 对于已定义好的标准数学函数sin(x), 应用程序中的语句"y=sin(sin(x));"就是一种递归调用.
三、问题求解：（共2题，每题5分，共计10分）
1．350
2．289
四、阅读程序写结果（共4题，每题8分，共计32分）
1 129,43
2 No.1:3,6 No.2:3,6
3 2 3 5 7 11 13 17 19 23 29
31 37 41 43 47
4 No.1: XTORSEAAMPLE
No.2: AAEELMOPRSTX
五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)
（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科
学委员会审查）
1.格雷码 Gray Code
Gray Code是一种二进制编码……特点是，对于两个相邻的十进制数，对应的两个GrayCode只有一个二进
制位不同。最大和最小的两个数也叫相邻。3位的(原题是4位的)例子如下：
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 010
由于……，GrayCode应用于……领域。
下面的程序：输入n(<16),m(0<=m<2^n)(都是十进制),输出对应于m的n位格雷码(用gr[]存放)
program s501;
var bound,m,n,i,j,b,p:integer;
gr:array[0..14]of integer;
begin
bound:=1;
writeln('input n,m');
readln(n,m);
for i:=1 to n do bound:=[___1___];
if (m<0)or(m>=bound) then
begin
writeln('Data error!');
[___2___];
end;
b:=1;
for i:=1 to n do
begin
p:=0; b:=b*2;
for [___3___] to m do
if ( [___4___] ) then
p:=1-p;
gr:=p;
end;
for i:=n [___5___] do
write(gr);
writeln;
end.
1 ① bound*2
② return 或 exit(0)
③ j=0
④(j%b-(b/2))==0
⑤ i>=1;i—- 或 i>0;i--
2. 连续邮资
n 种邮票面值，最多贴m张。如何设计面值，使得能够贴出尽量大的maxv,使得{1,2,3,...,maxv}的都能
贴出来。例如，n=5,m=4 则答案为{1,3,11,15,32}，可以maxv=70，就是1..70都能贴出来。
下面是这个程序，x[1..n]表示n中面值，且严格递增。bestx[1..n]存放最优解的x[1..n]。y[1..maxl]
记录当前的x[1..i]能够贴出来的各种邮资所需最少张数。
2 ① x[i-2]*(m-1)
② j+x[i-1]*k
③ j+x[i-1]*k （同2）
④ r-1
⑤ x[i-1]+1
⑥ backtrace(i+1,r)