NOIP2007初赛-提高组试题&答案

WebMaster@RenQingNet.Com(renqing) — Sun,21 Oct 2007 10:52:39 +0800

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不成立时, 命

题"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)

MM群2007七夕模拟赛试题

WebMaster@RenQingNet.Com(renqing) — Sun,19 Aug 2007 21:12:00 +0800

比赛简介:
明月清风相思一日OI也多情
青山秀水迢遥两人携手走天荒
细雪飞雨绵长流水千年爱不变
七夕夜相聚此诉此清风流水肠
路迢迢道长长溯回从之水中央
清风思明月泪一夜OI生百媚
柳依依雪霏霏参商无言鹊桥见
七夕夜两相会诉尽相思又一年

老兔清宫默默言寒蟾冷夜盈盈泪
河汉无情千年阻鹊鸟有义七夕会
织女望断怎堪眠牛郎牵儿不忍寐
纵使今宵离依然愿作星辰两相隔

感谢hh4742献诗:
银灯冷映显示屏轻敲程序也传情
天街夜色凉如水卧看牵牛织女星

守佑有情终能成眷属

“七月七日长生殿,夜半无人私语时.在天愿作比翼鸟,在地愿为连理枝.” 一年一或两度的七夕又来临了…同时,不久前noi结束,又有一些大牛退役了…

为了这个特别的日子,MM群(All cattle but MM)特别举办七夕邀请赛,本次比赛为每人4道题,题目难度可能不均衡,但是平均难度应该与NOIP相平,一般能在100分以上,大牛们随便300.而且本次比赛特别邀请了一对OI GG&MM共同出题～～～就是最有趣的那道.

本次比赛中,我们将采用特殊的评测方式.由于不是绝对的公平(但我们保证没有人能够作弊),所以请大家尽量享受此次比赛的乐趣而不是看重成绩.看到幽默的题目,笑笑吧;看到煽情的题目,哭哭吧.此次比赛是NOIP练习赛但不仅仅是NOIP练习赛,它更是前所未有的,专门为OIer准备的七夕盛宴!

MM和GG是OIer们永远的一个话题,无论是刚退役的大牛,还是前辈,或是正在拼搏中的OIer,祝你们和你们的另一半永远幸福~~~!

题目见附件，可以到RQNOJ(www.rqnoj.cn)进行数据测试点击下载此文件

郁闷的外星猫's Blog - Problem[Del]

NOIP2007初赛-提高组试题&答案

MM群2007七夕模拟赛试题