noiP2007年提高组初赛试卷及参考答案（Pascal语言）
[color=#000000][size=2]第十三届全国青少年[url=http://www.oinew.com/]信息[/url]学奥林匹克联赛初赛试题[/size][/color][color=#000000][size=2]（ 提高组 [b]Pas[url=http://www.oinew.com/]c[/url]al [/b]语言 二小时完成 ）[/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2]●●[font="Times] [/font][/size][/color]全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效[font="Times] [/font]●●
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2]一、[font="Times] [/font][/size][/color]单项选择题[font="Times] [/font]（共[font="Times] 10 [/font]题，每题[font="Times] 1.5 [/font]分，共计[font="Times] 15 [/font]分。每题有且仅有一个正确答案[font="Times].[/font]）。
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]1. [/font][/size][/color]在以下各项中。（[font="Times] [/font]）不是[font="Times] [url=http://www.oinew.com/]c[/url]PU [/font]的组成部分。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]控制器[font="Times] B. [/font]运算器[font="Times] [url=http://www.oinew.com/]c[/url]. [/font]寄存器[font="Times] D. [/font]主板[font="Times] E. [/font]算术逻辑单元[font="Times](ALU) [/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]2. [/font][/size][/color]在关系[url=http://www.oinew.com/]数据[/url]库中[font="Times], [/font]存放在数据库中的[url=http://www.oinew.com/]数据[/url]的逻辑[url=http://www.oinew.com/]结构[/url]以[font="Times]( )[/font]为主。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]二叉树[font="Times] B. [/font]多叉树[font="Times] [url=http://www.oinew.com/]c[/url]. [/font]哈希表[font="Times] D. B+[/font]树[font="Times] E. [/font]二维表
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]3.[/font][/size][/color]在下列各项中，只有（[font="Times] [/font]）不是[url=http://www.oinew.com/]计算机[/url]存储容量的常用单位。
[color=#000000][size=2][font="Times]A. Byte B. KB [url=http://www.oinew.com/]c[/url]. MB D. UB E. TB[/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]4[/font][/size][/color]．[font="Times]AS[url=http://www.oinew.com/]c[/url]II[/font]码的含义是（[font="Times] [/font]）。[font="Times] [/font]
[color=#000000][size=2][font="Times]A. [/font][/size][/color]二—十进制转换码[font="Times] B. [/font]美国[url=http://www.oinew.com/]信息[/url]交换标准代码[font="Times] [url=http://www.oinew.com/]c[/url]. [/font][url=http://www.oinew.com/]数字[/url]的二进制数码[font="Times] [/font]
[color=#000000][size=2][font="Times]D. [/font][/size][/color][url=http://www.oinew.com/]计算机[/url]可处理字符的唯一编码[font="Times] E. [/font]常用字符的二进制编码[font="Times] [/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]5[/font][/size][/color]．在[font="Times] Pas[url=http://www.oinew.com/]c[/url]al [/font][url=http://www.oinew.com/]语言[/url]中，表达式[font="Times] (23 or 2 xor 5)[/font]的值是（[font="Times] [/font]）
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]A. 18 B. 1 [url=http://www.oinew.com/]c[/url].23 D.32 E.24[/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]6[/font][/size][/color]．在[font="Times] Pas[url=http://www.oinew.com/]c[/url]al [/font][url=http://www.oinew.com/]语言[/url]中，判断整数[font="Times]a [/font]等于[font="Times] 0 [/font]或[font="Times]b[/font]等于[font="Times] 0[/font]或[font="Times][url=http://www.oinew.com/]c[/url][/font]等于[font="Times]0 [/font]的正确的条件表达式是（[font="Times] [/font]）
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]A. not ((a0) or (b0) or ([url=http://www.oinew.com/]c[/url]0)) [/font][/size][/color]
[color=#000000][size=2][font="Times]B. not ((a0) and (b0) and ([url=http://www.oinew.com/]c[/url]0)) [/font][/size][/color]
[color=#000000][size=2][font="Times]C. not ((a=0) and (b=0)) or ([url=http://www.oinew.com/]c[/url]=0) [/font][/size][/color]
[color=#000000][size=2][font="Times]D.(a=0) and (b=0) and ([url=http://www.oinew.com/]c[/url]=0) [/font][/size][/color]
[color=#000000][size=2][font="Times]E. not ((a=0) or (b=0) or ([url=http://www.oinew.com/]c[/url]=0)) [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]7. [/font][/size][/color]地面上有标号为[font="Times]A[/font]、[font="Times]B[/font]、[font="Times][url=http://www.oinew.com/]c[/url][/font]的[font="Times]3[/font]根细柱[font="Times], [/font]在[font="Times]A[/font]柱上放有[font="Times]10[/font]个直径相同中间有孔的圆盘[font="Times], [/font]从上到下次依次编号为[font="Times]1, 2, 3, [/font]……，将[font="Times]A[/font]柱上的部分盘子经过[font="Times]B[/font]柱移入[font="Times][url=http://www.oinew.com/]c[/url][/font]柱[font="Times], [/font]也可以在[font="Times]B[/font]柱上暂存。如果[font="Times]B[/font]柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么[font="Times], [/font]在[font="Times][url=http://www.oinew.com/]c[/url][/font]柱上[font="Times], [/font]从下到上的盘子的编号为（[font="Times] [/font]）。[font="Times] [/font]
[color=#000000][size=2][font="Times]A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 [url=http://www.oinew.com/]c[/url]. 2 4 3 1 7 6 [/font][/size][/color]
[color=#000000][size=2][font="Times]D. 2 4 3 6 7 5 E. 2 1 4 3 7 5 [/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]8. [/font][/size][/color]与十进制数[font="Times]17.5625[/font]相对应的[font="Times]8[/font]进制数是（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. 21.5625 B. 21.44 [url=http://www.oinew.com/]c[/url]. 21.73 [/font][/size][/color]
[color=#000000][size=2][font="Times]D. 21.731 E. [/font][/size][/color]前[font="Times]4[/font]个答案都不对[font="Times] [/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]9. [/font][/size][/color]欧拉图[font="Times]G[/font]是指可以构成一个闭回路的图，且图[font="Times]G[/font]的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中[font="Times], [/font]不一定是欧拉图的是：（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]图[font="Times]G[/font]中没有度为奇数的顶点[font="Times] [/font]
[color=#000000][size=2][font="Times]B. [/font][/size][/color]包括欧拉环游的图[font="Times]([/font]欧拉环游是指通过图中每边恰好一次的闭路径[font="Times]) [/font]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. [/font][/size][/color]包括欧拉闭迹的图[font="Times]([/font]欧拉迹是指通过途中每边恰好一次的路径[font="Times]) [/font]
[color=#000000][size=2][font="Times]D. [/font][/size][/color]存在一条回路[font="Times], [/font]通过每个顶点恰好一次
[color=#000000][size=2][font="Times]E. [/font][/size][/color]本身为闭迹的图
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]10. [/font][/size][/color]一个无法靠自身的控制终止的循环称为“死循环”，例如在[font="Times][url=http://www.oinew.com/]c[/url][/font][url=http://www.oinew.com/]语言[/url]程序中，语句“[font="Times]while(1)printf("*")[/font]；”就是一个死循环，运行它将无休止地打印[font="Times]*[/font]号。下面关于死循环的说法中[font="Times], [/font]只有（[font="Times] [/font]）是正确的。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]不存在一种[url=http://www.oinew.com/]算法[/url][font="Times], [/font]对任何一个程序及相应的输入[url=http://www.oinew.com/]数据[/url][font="Times], [/font]都可以判断是否会出现死循环[font="Times], [/font]因而[font="Times], [/font]任何编译系统都不做死循环检查[font="Times] [/font]
[color=#000000][size=2][font="Times]B. [/font][/size][/color]有些编译系统可以检测出死循环
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. [/font][/size][/color]死循环属于语法错误，[font="Times] [/font]既然编译系统能检查各种语法错误，[font="Times] [/font]当然也能检查出死循环[font="Times] [/font]
[color=#000000][size=2][font="Times]D. [/font][/size][/color]死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测的
[color=#000000][size=2][font="Times]E. [/font][/size][/color]对于死循环，只能等到发生时做现场处理[font="Times], [/font]没有什么更积极的手段[font="Times] [/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2]二、[font="Times] [/font][/size][/color]不定项选择题[font="Times] [/font]（共[font="Times] 10 [/font]题，每题[font="Times] 1.5 [/font]分，共计[font="Times] 15 [/font]分。每题正确答案的个数大于或等于[font="Times] 1[/font]。多选或少选均不得分）。
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]11. [/font][/size][/color]设[font="Times]A=B=true[/font]，[font="Times][url=http://www.oinew.com/]c[/url]=D=false[/font]，以下逻辑运算表达式值为真的有（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. ([/font][/size][/color]﹁[font="Times]A[/font]∧[font="Times]B)[/font]∨[font="Times]([url=http://www.oinew.com/]c[/url][/font]∧[font="Times]D[/font]∨[font="Times]A) B. [/font]﹁ [font="Times]( ( (A[/font]∧[font="Times]B)[/font]∨[font="Times][url=http://www.oinew.com/]c[/url])[/font]∧[font="Times]D)[/font]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. A[/font][/size][/color]∧[font="Times](B[/font]∨[font="Times][url=http://www.oinew.com/]c[/url][/font]∨[font="Times]D)[/font]∨[font="Times]D D. (A[/font]∧[font="Times](D[/font]∨[font="Times][url=http://www.oinew.com/]c[/url])) [/font]∧[font="Times]B[/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]12. [/font][/size][/color]命题“[font="Times]P[/font]→[font="Times]Q[/font]”可读做[font="Times]P[/font]蕴含[font="Times]Q[/font]，[font="Times] [/font]其中[font="Times]P[/font]、[font="Times]Q[/font]是两个独立的命题[font="Times]. [/font]只有当命题[font="Times]P[/font]成立而命题[font="Times]Q[/font]不成立时，[font="Times] [/font]命题[font="Times]"P[/font]→[font="Times]Q"[/font]的值为[font="Times]false[/font]，[font="Times] [/font]其它情况均为[font="Times]true. [/font]与命题[font="Times]"P[/font]→[font="Times]Q"[/font]等价的逻辑关系式是（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]﹁ [font="Times]P[/font]∨[font="Times]Q B. P[/font]∧[font="Times]Q [url=http://www.oinew.com/]c[/url]. [/font]﹁ ([font="Times]P[/font]∨[font="Times]Q[/font])[font="Times] D.[/font] ﹁(﹁[font="Times]Q[/font]∧[font="Times]P [/font])
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]13. (2070)16+(34)8[/font][/size][/color]的结果是（[font="Times] [/font]）。
[color=#000000][font="Times][size=2]A. (8332)10 B. (208[url=http://www.oinew.com/]c[/url])16[/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][font="Times][size=2][url=http://www.oinew.com/]c[/url]. (100000000110)2 D. (20214)8[/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]14. [/font][/size][/color]已知[font="Times]7[/font]个节点的二叉树的先根遍历是[font="Times]1 2 4 5 6 3 7([/font][url=http://www.oinew.com/]数字[/url]为结点的编号，以下同[font="Times])[/font]，[font="Times] [/font]后根遍历是[font="Times]4 6 5 2 7 3 1[/font]，[font="Times] [/font]则该二叉树的可能的中根遍历是（[font="Times] [/font]）[font="Times] [/font]
[color=#000000][size=2][font="Times]A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 [/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 [/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]15. [/font][/size][/color]冗余数据是指可以由以他数据导出的数据，例如，数据库中已存放了学生的数学、语文、和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看做冗余数据。冗余数据往往会造成[url=http://www.oinew.com/]数据[/url]的不一致，例如上面[font="Times]4[/font]个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余[url=http://www.oinew.com/]数据[/url]的说法中，[font="Times] [/font]正确的是（[font="Times] [/font]）。[font="Times] [/font]
[color=#000000][size=2][font="Times]A. [/font][/size][/color]应该在数据库中消除一切冗余[url=http://www.oinew.com/]数据[/url]
[color=#000000][size=2][font="Times]B. [/font][/size][/color]与用高级[url=http://www.oinew.com/]语言[/url]编写的[url=http://www.oinew.com/]数据[/url]处理系统相比，[font="Times] [/font]用关系数据库编写的系统更容易消除冗余[url=http://www.oinew.com/]数据[/url]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. [/font][/size][/color]为了提高查询效率，[font="Times] [/font]在数据库中可以适当保留一些冗余[url=http://www.oinew.com/]数据[/url]，[font="Times] [/font]但更新时要做相容性检验
[color=#000000][size=2][font="Times]D. [/font][/size][/color]做相容性检验会降低效率，[font="Times] [/font]可以不理睬数据库中的冗余[url=http://www.oinew.com/]数据[/url]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]16.[/font][/size][/color]在下列各软件中，属于[font="Times] [url=http://www.oinew.com/]noi[/url]P [/font][url=http://www.oinew.com/]竞赛[/url]（复赛）推荐使用的[url=http://www.oinew.com/]语言[/url]环境有（[font="Times] [/font]）。
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]A. gc[url=http://www.oinew.com/]c[/url] B. g++[/font][/size][/color]
[color=#000000][size=2][font="Times]C. Turbo C D. free pas[url=http://www.oinew.com/]c[/url]al[/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]17. [/font][/size][/color]以下断电之后将仍能保存[url=http://www.oinew.com/]数据[/url]的有（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]硬盘[font="Times] B. ROM [url=http://www.oinew.com/]c[/url]. [/font]显存[font="Times] D. RAM[/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]18. [/font][/size][/color]在下列关于[url=http://www.oinew.com/]计算机[/url][url=http://www.oinew.com/]语言[/url]的说法中，正确的有（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. [/font][/size][/color]高级语言比汇编[url=http://www.oinew.com/]语言[/url]更高级，[font="Times] [/font]是因为它的程序的运行效率更高
[color=#000000][size=2][font="Times]B. [/font][/size][/color]随着[font="Times]Pas[url=http://www.oinew.com/]c[/url]al[/font]、[font="Times][url=http://www.oinew.com/]c[/url][/font]等高级[url=http://www.oinew.com/]语言[/url]的出现，[font="Times] [/font]机器语言和汇编[url=http://www.oinew.com/]语言[/url]已经退出了历史舞台
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. [/font][/size][/color]高级语言程序比汇编[url=http://www.oinew.com/]语言[/url]程序更容易从一种计算机移植到另一种[url=http://www.oinew.com/]计算机[/url]上[font="Times] [/font]
[color=#000000][size=2][font="Times]D. [url=http://www.oinew.com/]c[/url][/font][/size][/color]是一种面向过程的高级[url=http://www.oinew.com/]计算机[/url][url=http://www.oinew.com/]语言[/url]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]19. [/font][/size][/color]在下列关于[url=http://www.oinew.com/]算法[/url]复杂性的说法中，[font="Times] [/font]正确的有（[font="Times] [/font]）。
[color=#000000][size=2][font="Times]A. [/font][/size][/color][url=http://www.oinew.com/]算法[/url]的时间复杂度，是指它在某台[url=http://www.oinew.com/]计算机[/url]上具体实现时的运行时间
[color=#000000][size=2][font="Times]B. [/font][/size][/color]算法的时间复杂度，是指对于该[url=http://www.oinew.com/]算法[/url]的一种或几种主要的运算，[font="Times] [/font]运算的次数与问题的规模之间的函数关系[font="Times] [/font]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. [/font][/size][/color]一个问题如果是[font="Times]NP[url=http://www.oinew.com/]c[/url][/font]类的，[font="Times] [/font]就意味着在解决该问题时，[font="Times] [/font]不存在一个具有多项式时间复杂度的[url=http://www.oinew.com/]算法[/url][font="Times]. [/font]但这一点还没有得到理论上证实，也没有被否定[font="Times] [/font]
[color=#000000][size=2][font="Times]D. [/font][/size][/color]一个问题如果是[font="Times]NP[/font]类的，与[font="Times][url=http://www.oinew.com/]c[/url][/font]有相同的结论[font="Times] [url=http://www.x2studio.net/][/url][/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]20. [/font][/size][/color]近[font="Times]20[/font]年来，[font="Times] [/font]许多[url=http://www.oinew.com/]计算机[/url]专家都大力推崇递归[url=http://www.oinew.com/]算法[/url]，认为它是解决较复杂问题的强有力的工具[font="Times]. [/font]在下列关于递归的说法中，[font="Times] [/font]正确的是（[font="Times] [/font]）。[font="Times] [/font]
[color=#000000][size=2][font="Times]A. [/font][/size][/color]在[font="Times]1977[/font]年前后形成标准的[url=http://www.oinew.com/]计算机[/url]高级[url=http://www.oinew.com/]语言[/url][font="Times]"FORTRAN77"[/font]禁止在程序使用递归，[font="Times] [/font]原因之一是该方法可能会占用更多的内存空间[font="Times]. [/font]
[color=#000000][size=2][font="Times]B. [/font][/size][/color]和非递归[url=http://www.oinew.com/]算法[/url]相比，[font="Times] [/font]解决同一个问题，[font="Times] [/font]递归[url=http://www.oinew.com/]算法[/url]一般运行得更快一些[font="Times] [/font]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]. [/font][/size][/color]对于较复杂的问题，[font="Times] [/font]用递归方式编程往往比非递归方式更容易一些
[color=#000000][size=2][font="Times]D. [/font][/size][/color]对于已定义好的标准数学函数[font="Times]sin(x)[/font]，[font="Times] [/font]应用程序中的语句“[font="Times]y=sin(sin(x));[/font]”就是一种递归调用[font="Times] [/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2]三．问题求解（共[font="Times] 2 [/font][/size][/color]题，每题[font="Times] 5 [/font]分，共计[font="Times] 10 [/font]分）
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]1[/font][/size][/color]．给定[font="Times]n[/font]个有标号的球，标号依次为[font="Times]1[/font]，[font="Times]2[/font]，…，[font="Times]n[/font]。将这[font="Times]n[/font]个球放入[font="Times]r[/font]个相同的盒子里，不允许有空盒，其不同放置方法的总数记为[font="Times]S(n,r)[/font]。例如，[font="Times]S(4,2)=7[/font]，这[font="Times]7[/font]种不同的放置方法依次为[font="Times]{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}[/font]。当[font="Times]n=7[/font]，[font="Times]r=4[/font]时，[font="Times]S(7,4)=[u] [/u][/font]。
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]2[/font][/size][/color]．[font="Times]N[/font]个人在操场里围成一圈，将这[font="Times]N[/font]个人按顺时针方向从[font="Times]1[/font]到[font="Times]N[/font]编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为[font="Times]J(N)[/font]，例如，[font="Times]J(5)=3[/font]，[font="Times]J(10)=5[/font]，等等。
[color=#000000][size=2]则[font="Times]J(400)=[u] [/u][/font][/size][/color]。
[color=#000000][size=2][font="Times] [/font][/size][/color]（提示：对[font="Times]N=2m+r[/font]进行分析，其中[font="Times]0[/font]≤[font="Times]rm[/font]）。[font="Times] [/font]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2]四．阅读程序写结果（共[font="Times] 4 [/font][/size][/color]题，每题[font="Times] 8 [/font]分，共计[font="Times] 32 [/font]分）
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][/size][/color]
[color=#000000][size=2][font="Times]1. [url=http://oinew.com/]Program[/url] s401;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] p,q:array[0..5] of integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] i,x,y:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] y:=20;[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=0 to 4 do read(p[i]);[/font][/size][/color]
[color=#000000][font="Times][size=2] readln;[/font][/size][/color]
[color=#000000][font="Times][size=2] q[0]:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7;[/font][/size][/color]
[color=#000000][font="Times][size=2] q[1]:=p[0]+p[1] div ((p[2]+p[3]) div p[4]);[/font][/size][/color]
[color=#000000][font="Times][size=2] q[2]:=p[0]*p[1] div p[2];[/font][/size][/color]
[color=#000000][font="Times][size=2] q[3]:=q[0]*q[1];[/font][/size][/color]
[color=#000000][font="Times][size=2] q[4]:=q[1]+q[2]+q[3];[/font][/size][/color]
[color=#000000][font="Times][size=2] x:=(q[0]+q[4]+2)-p[(q[3]+3) mod 4];[/font][/size][/color]
[color=#000000][font="Times][size=2] if (x>10) then[/font][/size][/color]
[color=#000000][font="Times][size=2] y:=y+(q[1]*100-q[3]) div (p[p[4] mod 3]*5)[/font][/size][/color]
[color=#000000][font="Times][size=2] else[/font][/size][/color]
[color=#000000][font="Times][size=2] y:=y+20+(q[2]*100-q[3]) div (p[p[4] mod 3]*5);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln(x,',',y);[/font][/size][/color]
[color=#000000][size=2][font="Times]end.[/font][/size][/color]
[color=#000000][size=2][font="Times]/*[/font][/size][/color]注：本例中，给定的输入[url=http://www.oinew.com/]数据[/url]可以避免分母为[font="Times] 0 [/font]或下标越界。[url=http://www.x2studio.net/][/url][font="Times] */[/font]
[color=#000000][size=2]输入：[font="Times]6 6 5 5 3[/font][/size][/color]
[color=#000000][size=2]输出：[u][font="Times] [/font][/size][/color][/u]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times]2. [url=http://oinew.com/]Program[/url] s402;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] a,b:integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] x,y:^integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]pro[url=http://www.oinew.com/]c[/url]edure fun(a,b:integer);[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] k:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] k:=a; a:=b; b:=k;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] a:=3; b:=6;[/font][/size][/color]
[color=#000000][font="Times][size=2] x:=@a; y:=@b;[/font][/size][/color]
[color=#000000][font="Times][size=2] fun(x^,y^);[/font][/size][/color]
[color=#000000][font="Times][size=2] write('No.1:',a,',',b,' ');[/font][/size][/color]
[color=#000000][font="Times][size=2] fun(a,b);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('No.2:',a,',',b);[/font][/size][/color]
[color=#000000][size=2][font="Times]end.[/font][/size][/color]
[color=#000000][size=2]输出[font="Times]: [u] [/u][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]3. [url=http://oinew.com/]Program[/url] S403;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] a1:array[1..50] of integer;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] i,j,t,t2,n,n2:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] n:=50;[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=1 to n do a1[i]:=0;[/font][/size][/color]
[color=#000000][font="Times][size=2] n2:=round(sqrt(n));[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=2 to n2 do[/font][/size][/color]
[color=#000000][font="Times][size=2] if(a1[i]=0) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] t2:=n div i;[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=2 to t2 do a1[i*j]:=1;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] t:=0;[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=2 to n do[/font][/size][/color]
[color=#000000][font="Times][size=2] if (a1[i]=0) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] write(i:4); in[url=http://www.oinew.com/]c[/url](t);[/font][/size][/color]
[color=#000000][font="Times][size=2] if(t mod 10=0) then writeln;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln;[/font][/size][/color]
[color=#000000][font="Times][size=2] end.[/font][/size][/color]
[color=#000000][size=2]输出：[u][font="Times] [/font][/size][/color][/u]
[u][color=#000000][font="Times][size=2] [/font][/size][/color][/u]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]4. [url=http://oinew.com/]Program[/url] S404;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]onst n=12;[/font][/size][/color]
[color=#000000][font="Times][size=2] ch2:array[0..12] of [url=http://www.oinew.com/]c[/url]har[/font][/size][/color]
[color=#000000][font="Times][size=2] =('q','A','S','O','R','T','E','X','A','M','P','L','E');[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] k:integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] ch:array[0..12] of [url=http://www.oinew.com/]c[/url]har;[/font][/size][/color]
[color=#000000][size=2][font="Times]pro[url=http://www.oinew.com/]c[/url]edure shift(k,n:integer);[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] v:[url=http://www.oinew.com/]c[/url]har;[/font][/size][/color]
[color=#000000][font="Times][size=2] j:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] v:=[url=http://www.oinew.com/]c[/url]h[k]; j:=k+k;[/font][/size][/color]
[color=#000000][font="Times][size=2] while (j
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] if (j
[color=#000000][font="Times][size=2] if (ord(v)
[color=#000000][font="Times][size=2] begin ch[j div 2]:=[url=http://www.oinew.com/]c[/url]h[j]; j:=j*2; end[/font][/size][/color]
[color=#000000][font="Times][size=2] else[/font][/size][/color]
[color=#000000][font="Times][size=2] exit;[/font][/size][/color]
[color=#000000][font="Times][size=2] [url=http://www.oinew.com/]c[/url]h[j div 2]:=v;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]pro[url=http://www.oinew.com/]c[/url]edure hpsrt;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] k:integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] tmp:[url=http://www.oinew.com/]c[/url]har;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=n div 2 downto 1 do shift(k,n);[/font][/size][/color]
[color=#000000][font="Times][size=2] write('No.1: ');[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=1 to n do write([url=http://www.oinew.com/]c[/url]h[k]);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln;[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=n downto 1 do[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] tmp:=ch[1]; ch[1]:=ch[k]; [url=http://www.oinew.com/]c[/url]h[k]:=tmp;[/font][/size][/color]
[color=#000000][font="Times][size=2] shift(1,k-1);[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=0 to n do ch[k]:=[url=http://www.oinew.com/]c[/url]h2[k];[/font][/size][/color]
[color=#000000][font="Times][size=2] hpsrt;[/font][/size][/color]
[color=#000000][font="Times][size=2] write('No.2: ');[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=1 to n do write([url=http://www.oinew.com/]c[/url]h[k]);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln;[/font][/size][/color]
[color=#000000][size=2][font="Times]end.[/font][/size][/color]
[color=#000000][size=2]输出：[u][font="Times] [/font][/size][/color][/u]
[u][color=#000000][font="Times][size=2] [/font][/size][/color][/u]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2]五．完善程序[font="Times] ([/font][/size][/color]前[font="Times] 5 [/font]空，每空[font="Times] 2 [/font]分，后[font="Times] 6 [/font]空，每空[font="Times] 3 [/font]分，共[font="Times] 28 [/font]分[font="Times])[/font]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]1[/font][/size][/color]．[font="Times]([/font]格雷码[font="Times] Gray [url=http://www.oinew.com/]c[/url]ode) [/font]
[color=#000000][size=2][font="Times]Gray [url=http://www.oinew.com/]c[/url]ode[/font][/size][/color]是一种二进制编码，编码顺序与相应的十进制数的大小不一致。其特点是，对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数间也仅有一个二进制位不同，以[font="Times]4[/font]位二进制数为例，编码如下：[font="Times] [/font]
[size=2]十进制数[/size]
[size=2]格雷码[/size]
[size=2]十进制数[/size]
[size=2]格雷码[/size]
[size=2]0[/size]
[size=2]0000[/size]
[size=2]8[/size]
[size=2]1100[/size]
[size=2]1[/size]
[size=2]0001[/size]
[size=2]9[/size]
[size=2]1101[/size]
[size=2]2[/size]
[size=2]0011[/size]
[size=2]10[/size]
[size=2]1111[/size]
[size=2]3[/size]
[size=2]0010[/size]
[size=2]11[/size]
[size=2]1110[/size]
[size=2]4[/size]
[size=2]0110[/size]
[size=2]12[/size]
[size=2]1010[/size]
[size=2]5[/size]
[size=2]0111[/size]
[size=2]13[/size]
[size=2]1011[/size]
[size=2]6[/size]
[size=2]0101[/size]
[size=2]14[/size]
[size=2]1001[/size]
[size=2]7[/size]
[size=2]0100[/size]
[size=2]15[/size]
[size=2]1000[/size]
[url=http://www.x2studio.net/][size=2][/size][/url]
[color=#000000][size=2]如果把每个二进制的位看做一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数[font="Times]-[/font][/size][/color]模转换等领域。[font="Times] [/font]
[color=#000000][size=2]下面程序的任务是：由键盘输入二进制的位数[font="Times]n(n，再输入一个十进制数[font="Times]m(0[/font]≤[font="Times]mn)[/font]，然后输出对应于[font="Times]m[/font]的格雷码[font="Times]([/font]共[font="Times]n[/font]位，用数组[font="Times]gr[ ][/font]存放[font="Times]) [/font]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://oinew.com/]Program[/url] s501; [/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] bound[/font][/size][/color]，[font="Times]m[/font]，[font="Times]n[/font]，[font="Times]i[/font]，[font="Times]j[/font]，[font="Times]b[/font]，[font="Times]p:integer; [/font]
[color=#000000][size=2][font="Times]gr:array[0..14]of integer; [/font][/size][/color]
[color=#000000][size=2][font="Times]begin [/font][/size][/color]
[color=#000000][size=2][font="Times]bound:=1; [/font][/size][/color]
[color=#000000][size=2][font="Times]writeln('input n[/font][/size][/color]，[font="Times]m'); [/font]
[color=#000000][size=2][font="Times]readln(n[/font][/size][/color]，[font="Times]m); [/font]
[color=#000000][size=2][font="Times]for i:=1 to n do bound:=[/font][/size][/color][u][ [/u][u]① ][/u][font="Times]; [/font]
[color=#000000][size=2][font="Times]if (m=bound) then [/font][/size][/color]
[color=#000000][size=2][font="Times]begin [/font][/size][/color]
[color=#000000][size=2][font="Times]writeln('Data error!'); [/font][/size][/color]
[color=#000000][size=2][u][ [/u][u]② ][/u][font="Times]; [/font][/size][/color]
[color=#000000][size=2][font="Times]end; [/font][/size][/color]
[color=#000000][size=2][font="Times]b:=1; [/font][/size][/color]
[color=#000000][size=2][font="Times]for i:=1 to n do [/font][/size][/color]
[color=#000000][size=2][font="Times]begin [/font][/size][/color]
[color=#000000][size=2][font="Times]p:=0; b:=b*2; [/font][/size][/color]
[color=#000000][size=2][font="Times]for[/font][/size][/color][u][ [/u][u]③ ][/u][font="Times] to m do [/font]
[color=#000000][size=2][font="Times]if ([/font][/size][/color][u][ [/u][u]④ ][/u][font="Times] ) then [/font]
[color=#000000][size=2][font="Times]p:=1-p; [/font][/size][/color]
[color=#000000][size=2][font="Times]gr:=p; [/font][/size][/color]
[color=#000000][size=2][font="Times]end; [/font][/size][/color]
[color=#000000][size=2][font="Times]for i:=n[/font][/size][/color][u][ [/u][u]⑤ ][/u][font="Times] do [/font]
[color=#000000][size=2][font="Times]write(gr); [/font][/size][/color]
[color=#000000][size=2][font="Times]writeln; [/font][/size][/color]
[color=#000000][size=2][font="Times]end.[/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times][/font][/size][/color]
[color=#000000][size=2][font="Times]2[/font][/size][/color]．（连续邮资问题）某国发行了[font="Times]n[/font]种不同面值的邮票，并规定每封信上最多允许贴[font="Times]m[/font]张邮票。在这些约束下，为了能贴出[font="Times]{1[/font]，[font="Times]2[/font]，[font="Times]3[/font]，…，[font="Times]maxvalue}[/font]连续整数集合的所有邮资，并使[font="Times]maxvalue[/font]的值最大，应该如何设计各邮票的面值[font="Times]?[/font]例如，当[font="Times]n=5[/font]和[font="Times]m=4[/font]时，面值设计为（[font="Times]1[/font]，[font="Times]3[/font]，[font="Times]11[/font]，[font="Times]15[/font]，[font="Times]32[/font]），可使[font="Times]maxvalue[/font]达到最大值[font="Times]70[/font]（或者说[font="Times],[/font]用这些面值的[font="Times]1[/font]至[font="Times]4[/font]张邮票可以表示不超过[font="Times]70[/font]的所有邮资，但无法表示邮资[font="Times]71[/font]）。而用其他面值的[font="Times]1[/font]至[font="Times]4[/font]张邮票如果可以表示不超过[font="Times]k[/font]的所有邮资，必有[font="Times]k[/font]≤[font="Times]70[/font]）
[color=#000000][size=2]下面是用递归回溯求解连续邮资问题的程序。数组[font="Times]x[1[/font][/size][/color]：[font="Times]n][/font]表示[font="Times]n[/font]种不同的邮票面值，并约定各元素按下标是严格递增的。数组[font="Times]bestx[1[/font]：[font="Times]n][/font]存放使[font="Times]maxvalue[/font]达到最大值的邮票面值（最优解），数组[font="Times]y[maxl][/font]用于记录当前已选定的邮票面值[font="Times]x[1[/font]：[font="Times]i][/font]能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。
[color=#000000][size=2][font="Times][url=http://oinew.com/]Program[/url] S502;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]onst NN=20;[/font][/size][/color]
[color=#000000][font="Times][size=2] maxint=30000;[/font][/size][/color]
[color=#000000][font="Times][size=2] maxl=500;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] bestx,x:array [0..NN] of integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] y:array [0..maxl] of integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] j,n,m,maxvalue:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]pro[url=http://www.oinew.com/]c[/url]edure result;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] j:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('max=',maxvalue);[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=1 to n do write(bestx[j]:4);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]procedure backtra[url=http://www.oinew.com/]c[/url]e(i,r:integer);[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] j,k:integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] z: array[0..maxl] of integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[size=2][font="Times][color=#000000] for j:=0 to[/font][/size][/color][color=#000000][u][ [/u][u]① ][/u][font="Times]do[/font][/color]
[color=#000000][font="Times][size=2] if (y[j]
[color=#000000][font="Times][size=2] for k:=1 to m-y[j] do[/font][/size][/color]
[color=#000000][size=2][font="Times] if (y[j]+k[u] [/u][u]② [/u][font="Times]]) then[/font]
[color=#000000][size=2][font="Times] y[[/font][/size][/color][u] [/u][u]③ [/u][font="Times]]:=y[j]+k;[/font]
[color=#000000][font="Times][size=2] while (y[r]
[color=#000000][font="Times][size=2] if (i>n) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] if (r-1>maxvalue) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[size=2][font="Times][color=#000000] maxvalue:=[/font][/size][/color][color=#000000][u][ [/u][u]④ ][/u][font="Times] ;[/font][/color]
[color=#000000][font="Times][size=2] for j:=1 to n do bestx[j]:=x[j];[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] exit;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=0 to maxl do z[k]:=y[k];[/font][/size][/color]
[size=2][font="Times][color=#000000] for j:=[/font][/size][/color][color=#000000][u][ [/u][u]⑤ ][/u][font="Times] to r do[/font][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] x[i]:=j;[/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color][u][ [/u][u]⑥ ][/u][font="Times];[/font]
[color=#000000][font="Times][size=2] for k:=0 to maxl do y[k]:=z[k];[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] maxvalue:=0;[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('input n,m:');[/font][/size][/color]
[color=#000000][font="Times][size=2] readln(n,m);[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=1 to maxl do y[j]:=maxint;[/font][/size][/color]
[color=#000000][font="Times][size=2] y[0]:=0; x[0]:=0; x[1]:=1;[/font][/size][/color]
[color=#000000][font="Times][size=2] backtra[url=http://www.oinew.com/]c[/url]e(2,1);[/font][/size][/color]
[color=#000000][font="Times][size=2] result;[/font][/size][/color]
[color=#000000][size=2][font="Times]end.[/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][url=http://www.oinew.com/]noi[/url]P2007年提高组（Pas[url=http://www.oinew.com/]c[/url]al[url=http://www.oinew.com/]语言[/url]）参考答案与评分标准[/size][/color]
[color=#000000][size=2] [/size][/color]
[color=#000000][size=2]一、单项选择题：（每题1.5分）[/size][/color]
[color=#000000][size=2] 1. D 2. E 3. D 4. B 5. A [/size][/color]
[color=#000000][size=2]6. B 7. D 8. B 9. D 10. A[/size][/color]
[size=2] [/size]
[size=2]二、 不定项选择题 （共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。[/size]
[color=#000000][size=2]11. AB[url=http://www.oinew.com/]c[/url] 12. AD 13. ABD 14. ABD 15. B[url=http://www.oinew.com/]c[/url] [/size][/color]
[color=#000000][size=2] 16. ABD 17. AB 18. [url=http://www.oinew.com/]c[/url]D 19. B[url=http://www.oinew.com/]c[/url] 20. A[url=http://www.oinew.com/]c[/url][/size][/color]
[size=2][color=#000000]三、问题求解：（[/size][/color]共2题，每题5分，共计10分）
[color=#000000][size=2]1．350[/size][/color]
[color=#000000][size=2] 2．289[/size][/color]
[size=2][color=#000000]四、阅读程序写结果（共[/size][/color]4题，每题8分，共计32分）
[color=#000000][size=2]1 129,43[/size][/color]
[size=2][color=#000000]2 [/size][/color]No.1:3,6 No.2:3,6
[size=2][color=#000000]3 [/size][/color]2 3 5 7 11 13 17 19 23 29
[size=2] 31 37 41 43 47[/size]
[color=#000000][size=2]4 No.1: XTORSEAAMPLE[/size][/color]
[size=2]No.2: AAEELMOPRSTX[/size]
[size=2]五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)[/size]
[size=2] （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） [/size]
[size=2]1 [color=#000000][font=宋体]①[/font][/size][/color] bound*2
[size=2] [color=#000000][font=宋体]② [/font][/size][/color]exit
[size=2] [color=#000000][font=宋体]③[/font][/size][/color] j:=0
[size=2] [color=#000000][font=宋体]④ [/font][/size][/color][color=#000000][font=宋体](j mod b-(b div 2))=0 [/font][/color]
[size=2] [color=#000000][font=宋体]⑤ [/font][/size][/color][color=#000000][font=宋体]downto 1[/font][/color]
[color=#000000][size=2]2 [font=宋体]①[/font][/size][/color] x[i-2]*(m-1)
[size=2] [color=#000000][font=宋体]②[/font][/size][/color] j+x[i-1]*k
[size=2][color=#000000][font=宋体]③[/font][/size][/color] j+x[i-1]*k [font=宋体]（同[/font]2[font=宋体]）[/font]
[size=2] [color=#000000][font=宋体]④[/font][/size][/color] r-1
[size=2] [color=#000000][font=宋体]⑤[/font][/size][/color] x[i-1]+1
[size=2] [color=#000000][font=宋体]⑥[/font][/size][/color] backtra[url=http://www.oinew.com/]c[/url]e(i+1,r)
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2]完整程序：[/size][/color]
[color=#000000][size=2][font="Times][url=http://oinew.com/]Program[/url] S501;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] bound,m,n,i,j,b,p:integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] gr:array[0..14] of integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] bound:=1;[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('input n,m');[/font][/size][/color]
[color=#000000][font="Times][size=2] readln(n,m);[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=1 to n do bound:=bound*2 ;[/font][/size][/color]
[color=#000000][font="Times][size=2] if (m=bound) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('Data error!');[/font][/size][/color]
[color=#000000][font="Times][size=2] exit ;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] b:=1;[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=1 to n do[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] p:=0; b:=b*2;[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=0 to m do[/font][/size][/color]
[color=#000000][font="Times][size=2] if (j mod b-(b div 2))=0 then[/font][/size][/color]
[color=#000000][font="Times][size=2] p:=1-p;[/font][/size][/color]
[color=#000000][font="Times][size=2] gr[i]:=p;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] for i:=n downto 1 do[/font][/size][/color]
[color=#000000][font="Times][size=2] write(gr[i]);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln;[/font][/size][/color]
[color=#000000][size=2][font="Times]end.[/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times] [/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://oinew.com/]Program[/url] S502;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]c[/url]onst NN=20;[/font][/size][/color]
[color=#000000][font="Times][size=2] maxint=30000;[/font][/size][/color]
[color=#000000][font="Times][size=2] maxl=500;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] bestx,x:array [0..NN] of integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] y:array [0..maxl] of integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] j,n,m,maxvalue:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]pro[url=http://www.oinew.com/]c[/url]edure result;[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] j:integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('max=',maxvalue);[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=1 to n do write(bestx[j]:4);[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]procedure backtra[url=http://www.oinew.com/]c[/url]e(i,r:integer);[/font][/size][/color]
[color=#000000][size=2][font="Times][url=http://www.oinew.com/]var[/url] j,k:integer;[/font][/size][/color]
[color=#000000][font="Times][size=2] z: array[0..maxl] of integer;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=0 to x[i-2]*(m-1) do[/font][/size][/color]
[color=#000000][font="Times][size=2] if (y[j]
[color=#000000][font="Times][size=2] for k:=1 to m-y[j] do[/font][/size][/color]
[color=#000000][font="Times][size=2] if (y[j]+k
[color=#000000][font="Times][size=2] y[j+x[i-1]*k]:=y[j]+k;[/font][/size][/color]
[color=#000000][font="Times][size=2] while (y[r]
[color=#000000][font="Times][size=2] if (i>n) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] if (r-1>maxvalue) then[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] maxvalue:=r-1 ;[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=1 to n do bestx[j]:=x[j];[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] exit;[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=0 to maxl do z[k]:=y[k];[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=x[i-1]+1 to r do[/font][/size][/color]
[color=#000000][font="Times][size=2] begin[/font][/size][/color]
[color=#000000][font="Times][size=2] x[i]:=j;[/font][/size][/color]
[color=#000000][font="Times][size=2] backtra[url=http://www.oinew.com/]c[/url]e(i+1,r);[/font][/size][/color]
[color=#000000][font="Times][size=2] for k:=0 to maxl do y[k]:=z[k];[/font][/size][/color]
[color=#000000][font="Times][size=2] end;[/font][/size][/color]
[color=#000000][size=2][font="Times]end;[/font][/size][/color]
[color=#000000][size=2][font="Times]begin[/font][/size][/color]
[color=#000000][font="Times][size=2] maxvalue:=0;[/font][/size][/color]
[color=#000000][font="Times][size=2] writeln('input n,m:');[/font][/size][/color]
[color=#000000][font="Times][size=2] readln(n,m);[/font][/size][/color]
[color=#000000][font="Times][size=2] for j:=1 to maxl do y[j]:=maxint;[/font][/size][/color]
[color=#000000][font="Times][size=2] y[0]:=0; x[0]:=0; x[1]:=1;[/font][/size][/color]
[color=#000000][font="Times][size=2] backtra[url=http://www.oinew.com/]c[/url]e(2,1);[/font][/size][/color]
[color=#000000][font="Times][size=2] result;[/font][/size][/color][color=#000000][size=2]end.[/size][/color]
页:
[1]