noip2007初赛提高组试题和答案.doc

1、第十三届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言 二小时完成） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、 单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案.） 。1. 在以下各项中。 （ ）不是 CPU 的组成部分。A. 控制器 B. 运算器 C. 寄存器 D. 主板 E. 算术逻辑单元(ALU) 2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( ) 为主。A. 二叉树 B. 多叉树 C. 哈希表 D. B+树 E. 二维表3.在下列各项中，只有（ ）不是计算机存储容量的常用单位。A. Byte B. K

2、B C. MB D. UB E. TB4ASCII 码的含义是（ ） 。 A. 二十进制转换码 B. 美国信息交换标准代码 C. 数字的二进制数码 D. 计算机可处理字符的唯一编码 E. 常用字符的二进制编码 5在 Pascal 语言中，表达式 (23 or 2 xor 5)的值是（ ）A. 18 B. 1 C.23 D.32 E.246在 Pascal 语言中，判断整数 a 等于 0 或 b 等于 0 或 c 等于 0 的正确的条件表达式是（ ）A. not (a0) or (c0) and (b0) C. not (a=0) and (b=0) or (c=0) D.(a=0) and (

3、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 柱上, 从下到上的盘子的编号为（ ） 。 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

4、 8. 与十进制数 17.5625 相对应的 8 进制数是（ ） 。A. 21.5625 B. 21.44 C. 21.73 D. 21.731 E. 前 4 个答案都不对 9. 欧拉图 G 是指可以构成一个闭回路的图，且图 G 的每一条边恰好在这个闭回路上出现一次（即一笔画成） 。在以下各个描述中, 不一定是欧拉图的是：（ ） 。A. 图 G 中没有度为奇数的顶点 B. 包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径) C. 包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径) D. 存在一条回路, 通过每个顶点恰好一次E. 本身为闭迹的图10. 一个无法靠自身的控制终止的循

5、环称为“死循环”，例如在 C 语言程序中，语句“while(1)printf(“*“)；”就是一个死循环，运行它将无休止地打印 *号。下面关于死循环的说法中 , 只有（ ）是正确的。A. 不存在一种算法, 对任何一个程序及相应的输入数据, 都可以判断是否会出现死循环, 因而, 任何编译系统都不做死循环检查 B. 有些编译系统可以检测出死循环C. 死循环属于语法错误， 既然编译系统能检查各种语法错误， 当然也能检查出死循环 D. 死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测的E. 对于死循环，只能等到发生时做现场处理, 没有什么更积极的手段 二、 不定项选择

6、题 （共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数大于或等于 1。多选或少选均不得分） 。11. 设 A=B=true，C=D=false，以下逻辑运算表达式值为真的有（ ） 。A. (A B) (CDA) B. ( ( (AB)C)D)C. A(BC D)D D. (A(D C) B12. 命题“PQ”可读做 P 蕴含 Q， 其中 P、Q 是两个独立的命题. 只有当命题 P 成立而命题 Q 不成立时， 命题“PQ“的值为 false， 其它情况均为 true. 与命题“PQ“等价的逻辑关系式是（ ） 。A. PQ B. PQ C. (PQ) D. ( QP )13. (

7、2070)16+(34)8 的结果是（ ） 。A. (8332)10 B. (208C)16C. (100000000110)2 D. (20214)814. 已知 7 个节点的二叉树的先根遍历是 1 2 4 5 6 3 7(数字为结点的编号，以下同 )， 后根遍历是 4 6 5 2 7 3 1， 则该二叉树的可能的中根遍历是（ ）由 X2Studio.Net 收集 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. 冗余数据是指可以由以他数据导出的数据，例如，数据库中已存放了学生的数学、语文、和英语的

8、三科成绩，如果还存放三科成绩的总分，则总分就可以看做冗余数据。冗余数据往往会造成数据的不一致，例如上面 4 个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中， 正确的是（ ） 。 A. 应该在数据库中消除一切冗余数据B. 与用高级语言编写的数据处理系统相比， 用关系数据库编写的系统更容易消除冗余数据C. 为了提高查询效率， 在数据库中可以适当保留一些冗余数据， 但更新时要做相容性检验D. 做相容性检验会降低效率， 可以不理睬数据库中的冗余数据16.在下列各软件中，属于 NOIP 竞赛（复赛）推荐使用的语言环境有（ ） 。A. gcc B. g+

9、C. Turbo C D. free pascal17. 以下断电之后将仍能保存数据的有（ ） 。A. 硬盘 B. ROM C. 显存 D. RAM18. 在下列关于计算机语言的说法中，正确的有（ ） 。A. 高级语言比汇编语言更高级， 是因为它的程序的运行效率更高B. 随着 Pascal、C 等高级语言的出现， 机器语言和汇编语言已经退出了历史舞台C. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 D. C 是一种面向过程的高级计算机语言19. 在下列关于算法复杂性的说法中， 正确的有（ ） 。A. 算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间B. 算法的时

10、间复杂度，是指对于该算法的一种或几种主要的运算， 运算的次数与问题的规模之间的函数关系 C. 一个问题如果是 NPC 类的， 就意味着在解决该问题时， 不存在一个具有多项式时间复杂度的算法. 但这一点还没有得到理论上证实，也没有被否定 D. 一个问题如果是 NP 类的，与 C 有相同的结论 由 X2Studio.Net 收集20. 近 20 年来， 许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具. 在下列关于递归的说法中， 正确的是（ ） 。 A. 在 1977 年前后形成标准的计算机高级语言“FORTRAN77“禁止在程序使用递归， 原因之一是该方法可能会占用更多的内

11、存空间. B. 和非递归算法相比， 解决同一个问题， 递归算法一般运行得更快一些 C. 对于较复杂的问题， 用递归方式编程往往比非递归方式更容易一些D. 对于已定义好的标准数学函数 sin(x)， 应用程序中的语句“y=sin(sin(x);”就是一种递归调用 三问题求解（共 2 题，每题 5 分，共计 10 分）1给定 n 个有标号的球，标号依次为 1，2，n。将这 n 个球放入 r 个相同的盒子里，不允许有空盒，其不同放置方法的总数记为 S(n,r)。例如， S(4,2)=7，这 7 种不同的放置方法依次为(1) , (234) , (2) , (134) , (3) , (124) ,

12、(4) , (123) , (12) , (34) , (13) , (24) , (14) , (23)。当 n=7，r=4 时，S(7,4)= 。2N 个人在操场里围成一圈，将这 N 个人按顺时针方向从 1 到 N 编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为 J(N)，例如，J(5)=3，J(10)=5，等等。则 J(400)= 。（提示：对 N=2m+r 进行分析，其中 0r 10) Theny:=y+(q1*100-q3) div (pp4 mod 3*5)Elsey:=y+2

13、0+(q2*100-q3) div (pp4 mod 3*5);writeln(x,y);end.输入：6 6 5 5 3输出： 2. program s402;var a,b:integer;x,y:integer;procedure fun(a,b:integer);var k:integer;begink:=a; a:=b; b:=k;end;begina:=3; b:=6;x:=a; y:=b;fun(x,y);write(No.1:,a,b, );fun(a,b);writeln(No.2:,a,b);end.输出: 3. program S403;var a1:array1.50

14、of integer;var i,j,t,t2,n,n2:integer;beginn:=50;for i:=1 to n do a1:=0;n2:=round(sqrt(n);for i:=2 to n2 doIf (a1 = 0) Thenbegint2:=n div i;for j:=2 to t2 do a1i*j:=1;end;t:=0;for i:=2 to n doIf (a1 = 0) Thenbeginwrite(i:4); inc(t);if(t mod 10=0) then writeln;end;writeln;end.输出： 4. program S404;const

15、 n=12;ch2:array0.12 of char=(q,A,S,O,R,T,E,X,A,M,P,L,E);var k:integer;ch:array0.12 of char;procedure shift(k,n:integer);var v:char;j:integer;beginv:=chk; j:=k+k;while (j=bound) then begin writeln(Data error!); ; end; b:=1; for i:=1 to n do begin p:=0; b:=b*2; for to m do if ( ) then p:=1-p; gr:=p; e

16、nd; for i:=n do write(gr); writeln; end.2 （连续邮资问题）某国发行了 n 种不同面值的邮票，并规定每封信上最多允许贴 m 张邮票。在这些约束下，为了能贴出1，2，3，maxvalue连续整数集合的所有邮资，并使maxvalue 的值最大，应该如何设计各邮票的面值 ?例如，当 n=5 和 m=4 时，面值设计为（1，3，11，15，32） ，可使 maxvalue 达到最大值 70（或者说 ,用这些面值的 1 至 4 张邮票可以表示不超过 70 的所有邮资，但无法表示邮资 71） 。而用其他面值的 1 至 4 张邮票如果可以表示不超过 k 的所有邮资，必

17、有 k70）由 X2Studio.Net 收集下面是用递归回溯求解连续邮资问题的程序。数组 x1：n 表示 n 种不同的邮票面值，并约定各元素按下标是严格递增的。数组 bestx1：n存放使 maxvalue 达到最大值的邮票面值（最优解） ，数组 ymaxl用于记录当前已选定的邮票面值 x1：i能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。program S502;const NN=20;maxint=30000;maxl=500;var bestx,x:array 0.NN of integer;y:array 0.maxl of integer;j,n,m,maxvalue:in

18、teger;procedure result;var j:integer;beginwriteln(max=,maxvalue);for j:=1 to n do write(bestxj:4);writeln;end;procedure backtrace(i,r:integer);var j,k:integer;z: array0.maxl of integer;beginfor j:=0 to doif (yjn) thenbeginif (r-1maxvalue) thenbeginmaxvalue:= ;for j:=1 to n do bestxj:=xj;end;exit;end

19、;for k:=0 to maxl do zk:=yk;for j:= to r dobeginx:=j; ;for k:=0 to maxl do yk:=zk;end;end;beginmaxvalue:=0;writeln(input n,m:);readln(n,m);for j:=1 to maxl do yj:=maxint;y0:=0; x0:=0; x1:=1;backtrace(2,1);result;end.NOIP2007 提高组答案（PASCAL) 一、单项选择题：（每题 1.5 分） 1. D 2. E 3. D 4. B 5. A 6. B 7. D 8. B 9.

20、 D 10. A 二、 不定项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数大于或等于1。多选或少选均不得分） 。 11. ABC 12. AD 13. ABD 14. ABD 15. BC 16. ABD 17. AB 18. CD 19. BC 20. AC 三、问题求解：（共 2 题，每题 5 分，共计 10 分） 1350 2289 四、阅读程序写结果（共 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 bound*2 exit j:=0 (j mod b-(b div 2)=0 downto 1 2 xi-2*(m-1) j+xi-1*k j+xi-1*k （同 2） r-1 xi-1+1 backtrace(i+1,r)