NOIP 2009普及组初赛试题及解析

一. 单项选择题 （共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.）。

1、关于图灵机下面的说法哪个是正确的：（ ）

A.图灵机是世界上最早的电子计算机。
B.由于大量使用磁带操作，图灵机运行速度很慢。
C.图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
D.图灵机只是一个理论上的计算模型。

正确答案: D
A. 图灵机是世界上最早的电子计算机。
这个说法是不正确的。图灵机是由英国数学家艾伦·图灵提出的一个理论上的计算模型，它并不是一个实际的物理设备。世界上最早的电子计算机是ENIAC，它是在1945年由美国宾夕法尼亚大学研制的。
B. 由于大量使用磁带操作，图灵机运行速度很慢。
这个说法也是不准确的。图灵机是一个理论模型，并没有实际使用磁带进行操作。它更多地是一个计算理论的基础，而不是一个实际的计算设备。
C. 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
这个说法部分正确。图灵机确实是由英国数学家艾伦·图灵提出的，但图灵机本身并没有在二战中为破译德军的密码发挥直接作用。图灵的主要贡献在于他提出的图灵测试，以及对密码学和密码破译的理论研究。实际上，二战中为破译德军的密码发挥重要作用的是其他的计算设备和方法，如ENIGMA密码机和其破解设备。
D. 图灵机只是一个理论上的计算模型。
这个说法是正确的。图灵机是一个抽象的计算模型，它描述了计算的基本原理和可能性，但并没有实际的物理实现。

2、关于计算机内存下面的说法哪个是正确的：（ ）

A.随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B.1MB内存通常是指1024*1024字节大小的内存。
C.计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D.一般内存中的数据即使在断电的情况下也能保留2个小时以上。

正确答案: B
A. 随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
这个说法不准确。随机存储器（Random Access Memory, RAM）之所以被称为“随机”，是因为它可以被访问和修改而不必按照任何特定的顺序。也就是说，你可以随机地访问RAM中的任何位置，而不需要按照某种顺序。但分配给程序的内存位置通常是由操作系统管理的，并不是随机的。
B. 1MB内存通常是指1024*1024字节大小的内存。
这个说法是正确的。在计算机科学中，通常使用二进制单位来表示数据大小。1MB（兆字节）等于1,048,576字节（1024 * 1024字节）。
C. 计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
这个说法是合理的，但略有不完整。通常，计算机的内存层次结构包括寄存器、高速缓存（Cache）、主存（通常所说的内存）和磁盘。寄存器是最快的存储层次，但容量最小；高速缓存比主存快，但容量也较小；主存是通常所说的内存，用于存储正在运行的程序和数据；磁盘是最慢的，但容量最大。
D. 一般内存中的数据即使在断电的情况下也能保留2个小时以上。
这个说法不准确。随机存储器（RAM）是易失性的，意味着当计算机断电时，存储在RAM中的数据会丢失。只有非易失性存储器，如硬盘、闪存等，才能在断电后保留数据。

3、关于BIOS下面说法哪个是正确的：（ ）

A.BIOS是计算机基本输入输出系统软件的简称。
B.BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
C.BIOS一般由操作系统厂商来开发完成。
D.BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

正确答案: A
A. BIOS是计算机基本输入输出系统软件的简称。
这个说法是正确的。BIOS（Basic Input/Output System）即基本输入输出系统，是一组固化在计算机主板上的一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。
B. BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
这个说法部分正确。BIOS确实包含了一些基本的输入输出设备的驱动程序，如键盘、鼠标等。但是，声卡和显卡的驱动程序通常不会包含在BIOS中，而是由操作系统或相应的设备驱动程序来提供。打印机等外部设备的驱动程序通常也不包含在BIOS中。
C. BIOS一般由操作系统厂商来开发完成。
这个说法是不正确的。BIOS通常是由计算机硬件制造商（如主板制造商）来开发和提供的，而不是由操作系统厂商来开发。BIOS与操作系统是相互独立的，BIOS在操作系统加载之前就已经运行，负责硬件的初始化和自检。
D. BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
这个说法是不正确的。BIOS主要负责计算机的硬件初始化和自检，以及提供基本的输入输出功能。它并不提供文件管理功能，如文件拷贝、复制、删除和目录维护等。这些功能通常由操作系统和其文件系统来提供。

4、关于CPU下面哪个说法是正确的：（ ）

A.CPU全称为中央处理器（或中央处理单元）。
B.CPU可以直接运行汇编语言。
C.同样主频下，32位的CPU比16位的CPU运行速度快一倍。
D.CPU最早是由Intel公司发明的。

正确答案: A
A. CPU全称为中央处理器（或中央处理单元）。
这个说法是正确的。CPU，全称为Central Processing Unit，中文确实可以翻译为中央处理器或中央处理单元。它是计算机的核心部件，负责执行程序指令和处理数据。
B. CPU可以直接运行汇编语言。
这个说法不完全准确。CPU直接执行的是机器语言，而不是汇编语言。汇编语言是一种低级语言，它需要被汇编器转换成机器语言（二进制代码）后，才能被CPU执行。
C. 同样主频下，32位的CPU比16位的CPU运行速度快一倍。
这个说法不准确。CPU的速度不仅取决于其位宽（如16位或32位），还受到许多其他因素的影响，如主频、缓存大小、指令集架构等。32位CPU和16位CPU之间的性能差异远不止速度上的简单比较。
D. CPU最早是由Intel公司发明的。
这个说法不准确。虽然Intel是CPU制造领域的知名公司，但CPU的概念和技术并不是由Intel发明的。CPU的概念可以追溯到早期的计算机设计，而具体的实现和商业化则是由多家公司共同推动的。

5、关于ASCII，下面哪个说法是正确的：（ ）

A.ASCII码就是键盘上所有键的唯一编码。
B.一个ASCII码使用一个字节的内存空间就能够存放。
C.最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。
D.ASCII码是英国人主持制定并推广使用的。

正确答案: B
A. ASCII码就是键盘上所有键的唯一编码。
这个说法是不准确的。ASCII码确实为128个或256个字符提供了编码（取决于具体的ASCII版本），但它并不涵盖键盘上所有的键。例如，许多键盘上的功能键（如F1、F2等）、控制键（如Ctrl、Alt等）以及导航键（如方向键）并没有对应的ASCII编码。
B. 一个ASCII码使用一个字节的内存空间就能够存放。
这个说法是正确的。在标准的ASCII编码中，每个字符使用7位二进制数来表示，但为了与字节（通常是8位）对齐，通常使用一个字节（8位）来存储ASCII码。这样，标准的ASCII字符集只需要7位，但最高位（第8位）通常为0。
C. 最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。
这个说法不准确。标准的ASCII编码只包括128个字符，其中并不包括汉字或其他非英语字符。为了表示更广泛的字符集，人们开发了扩展的ASCII编码，如EBCDIC（Extended Binary Coded Decimal Interchange Code）或各种字符编码方案，如ISO-8859系列、GB2312（用于简体中文）、Big5（用于繁体中文）等。这些编码方案通常使用多于一个字节来表示字符。
D. ASCII码是英国人主持制定并推广使用的。
这个说法不准确。ASCII码实际上是由美国国家标准协会（American National Standards Institute, ANSI）制定的，用于电子通信中的信息交换。虽然其名称中包含“American”，但它被广泛接受为国际标准，并被用于全球范围内的电子通信。

6、下列软件中不是计算机操作系统的是： （ ）

A.Windows     
B.Linux    
C.OS/2     
D.WPS

正确答案: D
A) Windows - 是微软公司开发的操作系统。
B) Linux - 是一种自由和开放源代码的操作系统。
C) OS/2 - 是IBM和微软共同开发的操作系统。
而D) WPS - 是Kingsoft（金山软件）公司开发的一款办公软件套装，它主要包括文字处理、表格、演示和邮件四个组件。WPS并不是操作系统，而是一个应用程序。

7、关于互联网，下面的说法哪一个是正确的：（ ）

A.新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
B.互联网的入网主机如果有了域名就不再需要IP地址。
C.互联网的基础协议为TCP/IP协议。
D.互联网上所有可下载的软件及数据资源都是可以合法免费使用的。

正确答案: C
A. 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
这个说法是不准确的。IPv6确实是IPv4的升级和替代品，用于解决IPv4地址耗尽的问题。而IPv5并不是一个被广泛接受或使用的标准。IPv5（有时也被称为IPng，即IP下一代）是一个实验性的协议版本，它没有被广泛采纳，最终被IPv6所取代。
B. 互联网的入网主机如果有了域名就不再需要IP地址。
这个说法是不正确的。域名是为了方便人类记忆而设计的，但网络通信仍然需要IP地址。域名系统（DNS）负责将域名解析成对应的IP地址，这样计算机才能通过网络进行通信。
C. 互联网的基础协议为TCP/IP协议。
这个说法是正确的。TCP/IP（传输控制协议/互联网协议）是互联网通信的基础。它包括TCP（用于确保数据可靠传输）和IP（用于数据包的路由和寻址）以及其他辅助协议，如UDP（用户数据报协议）等。
D. 互联网上所有可下载的软件及数据资源都是可以合法免费使用的。
这个说法是不正确的。互联网上的资源并不都是免费的。许多软件和数据资源受到版权保护，需要付费才能合法使用。此外，即使某些资源可以免费下载，也并不意味着它们是合法的，可能存在版权侵权或其他法律问题。

8、关于HTML下面哪种说法是正确的：（ ）

A.HTML实现了文本、图形、声音乃至视频信息的统一编码。
B.HTML全称为超文本标记语言。
C.网上广泛使用的 Flash动画都是由HTML编写的。
D.HTML也是一种高级程序设计语言。

正确答案: B
A. HTML实现了文本、图形、声音乃至视频信息的统一编码。
这个说法是不准确的。HTML（HyperText Markup Language，超文本标记语言）主要用于创建网页的结构和内容，它主要支持文本、基本的图形和简单的交互元素，但并不直接支持声音和视频的编码。声音和视频通常通过其他技术（如HTML5的 < audio > 和 < video > 标签，或嵌入的第三方播放器）来在网页上呈现。
B. HTML全称为超文本标记语言。
这个说法是正确的。HTML的全称确实是“超文本标记语言”。它是一种用于创建网页的标准标记语言，通过使用各种标记（tags）来描述网页的结构和内容。
C. 网上广泛使用的 Flash动画都是由HTML编写的。
这个说法是不准确的。Flash动画是使用Adobe Flash技术创建的，而不是使用HTML。虽然HTML5引入了一些支持动画和交互性的新特性（如Canvas和SVG），但传统的Flash动画与HTML无关。
D. HTML也是一种高级程序设计语言。
这个说法也是不准确的。HTML不是一种程序设计语言，而是一种标记语言。它用于描述网页的结构和内容，而不是用于执行计算或算法。HTML本身不包含编程逻辑；它主要与CSS（用于样式）和JavaScript（用于交互性和动态内容）等语言结合使用。

9、关于程序设计语言，下面哪个说法是正确的：（ ）

A.加了注释的程序一般会比同样的没有加注释的程序运行速度慢。
B.高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。
C.高级语言相对于低级语言更容易实现跨平台的移植。
D.以上说法都不对。

正确答案: C
A. 加了注释的程序一般会比同样的没有加注释的程序运行速度慢。
这个说法是不正确的。注释对于程序的运行速度没有影响。注释是为了增加代码的可读性和可维护性，它们不会被编译器或解释器执行。因此，注释的有无不会影响程序的执行速度。
B. 高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。
这个说法也是不正确的。高级语言编写的程序可以通过编译器或解释器转换成机器语言，从而在任何支持该语言的硬件系统上运行。虽然高级语言通常用于开发更复杂的应用程序，但它们也可以用于开发运行在低端设备上的程序，只要这些设备有足够的计算能力和内存来执行编译后的代码。
C. 高级语言相对于低级语言更容易实现跨平台的移植。
这个说法是正确的。高级语言通常具有更好的可移植性，因为它们与特定的硬件或操作系统平台的依赖较少。高级语言编写的代码可以通过不同的编译器或解释器在不同的平台上运行，而不需要对源代码进行大量修改。这使得高级语言更容易实现跨平台的移植。
D. 以上说法都不对。
由于C选项是正确的，所以D选项不正确。

10、已知大写字母A的ASCII编码为65（10进制），则大写字母J的10进制ASCII编码为：（ ）

A.71     
B.72    
C.73    
D.以上都不是

正确答案:D
大写字母A的ASCII编码是65。因此，我们可以按照字母表的顺序来计算大写字母J的ASCII编码：
A的ASCII编码是65
B的ASCII编码是66
C的ASCII编码是67
…
J的ASCII编码是65 + 9 = 74

11、十进制小数125.125对应的8进制数是（ ）

A.100.1    
B.175.175     
C.175.1   
D.100.175

正确答案: C
要将十进制小数125.125转换为八进制数，我们需要分别转换整数部分和小数部分。
首先，转换整数部分125：
125 / 8 = 15 余 5
15 / 8 = 1 余 7
1 / 8 = 0 余 1
因此，整数部分125转换为八进制是175。

接下来，转换小数部分0.125：
0.125 * 8 = 1.0 （这里1.0表示八进制的1和十进制的0）
由于小数部分只有一位，并且乘以8后得到了整数，因此小数部分0.125转换为八进制是0.1。
综合整数部分和小数部分，十进制小数125.125对应的八进制数是175.1。

12、有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ （ ）

A.EDCFAB    
B.DECABF   
C.CDFEBA    
D.BCDAEF

正确答案: C
A：F进栈，E进栈，E出栈，D进栈，D出栈，C进栈，C出栈，F出栈，B进栈，A进栈，A出栈，B出栈。
B：F进栈，E进栈，D进栈，D出栈，E出栈，C进栈，C出栈，B进栈，A进栈，Ａ出栈，Ｂ出栈,F出栈。
C：F进栈，E进栈，D进栈，C进栈，C出栈，D出栈，此时栈顶是E，F无法先出栈。C错。
D：F进栈，E进栈，D进栈，C进栈，B进栈，B出栈，C出栈，D出栈，Ａ进栈，A出栈，E出栈,Ｆ出栈。

13、表达式a*(b+c)-d的后缀表达式是： （ ）

A.abcd*+-    
B.abc+*d-    
C.abc*+d-   
D.-+*abcd

正确答案: B
中缀表达式转后缀，一共三种方法。①画二叉树　②堆栈法　③画括号
主要介绍第二种，规则如下：
（1）如果遇到操作数，我们就直接将其输出。
（2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
（3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
（4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止（即把优先级高的弹出）。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。
（5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

14、一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：（ ）

A.2n + 1    
B.2n-1    
C.n-1   
D.n+1  

正确答案: D
根据二叉树的性质３：对于任何一棵二叉树，如果其叶结点数为N0(N0表示度为0的点也就是叶子结点)，而度为2的结点为N2，则N0=N2+1。

推算过程如下：
已知树的分支结点总数为n，（分支结点就是指度为1或者度为2点），则有N1+N2=N;
将N0=N2+1带入得N1+N0-1=N
移项得：N0=N+1-N1。当N1为0时，N0有最大值为N+1
也可以用特殊值带入求解。

15、快速排序最坏情况下的算法时间复杂度为： （ ）

A. $O(lo{g}_{2}n)$
B. $O(n)$
C. $O(nlo{g}_{2}n)$
D. $O(n^2)$

正确答案: D
快排平均时间复杂度$O(nlo{g}_{2}n)$，最好$O(nlo{g}_{2}n)$，最坏$O(n^2)$
快速排序在最坏情况下发生当输入数组已经是完全有序的（或几乎完全有序的）。在这种情况下，每次划分操作只能将一个元素放到其最终位置上，导致每次递归调用处理的子数组大小几乎相同。因此，快速排序在最坏情况下会退化为类似于冒泡排序的行为，每次递归调用都会处理大约n/2个元素，导致递归树的高度为n。因此，最坏情况下的时间复杂度是$O(n^2)$。

16、有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素： （ ）

A. 11次     
B. 12次     
C. 13次     
D. 14次

正确答案: B
在二分查找算法中，每次比较都将搜索范围缩小一半。对于一个由4000个元素构成的顺序表，我们可以计算最多需要多少次比较来确定是否存在所查找的元素。
假设需要比较的次数为 x，则每次比较后搜索范围减半，可以用以下不等式表示：
2^x >= 4000
解这个不等式，我们得到：
x >= log2(4000)
x >= 12
由于 x 必须是整数，所以 x 的最小值是 12。因此，最多需要12次比较就能确定是否存在所查找的元素。

17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：（ ）

A. 冒泡排序     
B. 插入排序     
C. 归并排序     
D. 快速排序

正确答案: D

A. 冒泡排序 - 是稳定的。在冒泡排序中，相邻元素两两比较，如果顺序错误则交换位置，相同元素不会交换位置，因此相同元素的前后顺序不会改变。
B. 插入排序 - 也是稳定的。插入排序在每次插入一个元素时，都会保持已排序部分的有序性，并且相同元素不会交换位置。
C. 归并排序 - 是稳定的。归并排序是通过将两个已排序的子数组合并成一个有序数组来实现的，合并过程中相同元素不会交换位置。
D. 快速排序 - 是不稳定的。快速排序是通过递归地将数组划分为两个子数组，然后对子数组进行排序来实现的。在划分过程中，使用了一个基准元素，所有小于基准的元素被移到左边，所有大于基准的元素被移到右边。这个过程中，相同元素的前后顺序可能会发生改变。

18、已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？（ ）

A. n      
B. n+1     
C. n-1     
D. n*(n-1)

正确答案: A
性质: 有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。

19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：（ ）

A. http://www.noi.com/                     
B. http://www.noi.org/
C. http://www.noi.cn/                        
D. http://www.xinxixue.com/

正确答案: C
首先，.com 通常用于商业公司，而 .org 通常用于组织或非营利机构。考虑到全国信息学奥林匹克是一个竞赛活动，它更可能使用 .org 或 .cn（代表中国）这样的域名后缀。
这个网址包含了 noi（代表全国信息学奥林匹克）和 .cn（代表中国），符合一个国家级竞赛官方网站的命名标准。

20、在参加NOI系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：（ ）

A.携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B.在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C.通过互联网搜索取得解题思路。
D.在提交的程序中启动多个进程以提高程序的执行效率。

正确答案: B
A项：比赛中，有时候会允许带书写工具和手表等的。
C项：不会连外网
D项：会造成服务器宕机。

二. 问题求解（共2题，每题5分，共计10分）

1、小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有__________种。

答案: 70
【解析】排列组合
A=a1->a2->a3，
B=b1->b2->b3->b4->b5
从b1开始，而且完成了任务A，b1—a1—a2—a3–， 剩余四个空，就是从剩余的空中往里插入元素即可。

方式1：
可以推论，n个物体要放到m个位置上，并满足a[1]<a[2]<a[3]…<a[n],可以推论出，a[1]<a[2]<a[3]<…<a[n]<n+1; 实际上就是在n+m-1个位置中选n个位置。

方式2：
b1在第一个位置，其前方没有任何数，但a1,a2,a3前方可以有数字，就可以理解成，B中的某些任务和a1,a2,a3一共需要占多个空，只要把B中任务挑选位置放好，剩余的自然是A的任务。
所以分类讨论
(1)假设完成任务A：只有1种（顺序选择B剩余任务）
(2)假设完成任务A和b2。则(a1,a2,a3,b2)四种，已知a1,a2,a3顺序不能颠倒，所以用插空法，b2插到a1,a2,
a组成的4个空中，C(4,1)=4种
(3)假设完成任务A和b2,b3。C(5,2)=10种。可以按照方式1，2个物体放到4个位置上，也可也理解，a1,a2,a3,b1,b2一共组成5个位置，从中选出2个位置给b1,b2。剩余的A只有一种方法。
(3)假设完成任务A和b2,b3,b4。 C(6,3)=20种
(4)假设完成任务A和b2,b3,b4,b5。C(7,4)=35种
一共1+4+10+20+35=70种

2、有如下的一段程序，现在要把这段程序分配到若干台（数量充足）用电缆连接的 PC 上做并行执行。每台 PC 执行其中的某几个语句，并可随时通过电缆与其他 PC 通讯，交换一些中间结果。假设每台 PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在[ ]单位时间内执行完毕。
注意：任意中间结果只有在某台 PC 上已经得到，才可以被其他 PC 引用。例如若语句 4 和 6 被分别分配到两台 PC 上执行，则因为语句 6 需要引用语句 4 的计算结果，语句 6 必须在语句 4 之后执行。

1. a=1;
2. b=a;
3. d=-a;
4. e=a+d;
5. c=2*d;
6. f=b+e-d;
7. g=a*f+c;

正确答案: 5

三. 阅读程序写结果（共4题，每题8分，共计32分）

1、阅读程序写结果：

#include <iostream>
using namespace std;int a,b;int work(int a,int b){if (a%b)return work(b,a%b);return b;
}int main(){cin >> a >> b;cout << work(a,b) << endl;return 0;
}

输入: 20 12
输出: ____

正确答案: 4
简单的函数递归调用。
if(),括号中表示条件表达式，如果条件表达式成立就执行下面的语句，也就是括号中不为零就继续。如果a对b取余的结果不为0，那么就返回(b,a%b)。否则返回b
传入20，12后，20%12=8，return(12,8)
传入12，8后，12%8=4，return(8,4)
传入8，4后，12%4=0，结果为0，return b;

2、阅读程序写结果：

#include <iostream>
using namespace std;
int main(){int a[3],b[3];int i,j,tmp;for (i=0;i<3;i++)cin >> b[i];for (i=0;i<3;i++){a[i]=0;for (j=0;j<=i;j++){a[i]+=b[j];b[a[i]%3]+=a[j];}}tmp=1;for (i=0;i<3;i++){a[i]%=10;b[i]%=10;tmp*=a[i]+b[i];}cout << tmp << endl;return 0;
}

输入: 2 3 5
输出: ____

正确答案: 416

b[3] = {2, 3, 5} a[3] = {0,0,0}

b[3] = {2, 3, 47} a[3] = {2，5，26}

3、阅读程序写结果：

#include <iostream>
using namespace std;const int c=2009;int main(){int n,p,s,i,j,t;cin >> n >> p;s=0;t=1;for(i=1;i<=n;i++){t=t*p%c;for(j=1;j<=i;j++)s=(s+t)%c;}cout << s << endl;return 0;
}

输入: 11 2
输出: ____

正确答案: 782

n = 11 t = 1, p = 2, c = 2009, s = 0

4、阅读程序写结果：

#include <iostream>
using namespace std;const int maxn=50;
void getnext(char str[]){int l=strlen(str),i,j,k,temp;k=l-2;while(k>=0&&str[k]>str[k+1]) k--;i=k+1;while(i<l&&str[i]>str[k]) i++;temp=str[k];str[k]=str[i-1];str[i-1]=temp;for(i=l-1;i>k;i--)for(j=k+1;j<i;j++)if(str[j]>str[j+1]){temp=str[j];str[j]=str[j+1];str[j+1]=temp;}return ;
}int main(){char a[maxn];int n;cin >> a >> n;while(n>0){getnext(a);n--;}cout << a << endl;return 0;
}

输入: NOIP 3
输出: ____

正确答案: NPOI

实际上就是每次传入四个字母，按照要求把字母进行位置调换。

四. 完善程序 (前4空，每空2.5分，后6空，每空3分，共28分)

1、（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7

#include <iostream>
using namespace std;int a[101];
int n,i,ans,len,tmp,beg;int main(){cin >> n;for (i=1;i<=n;i++)cin >> a[i];tmp=0;ans=0;len=0;beg= [    ①    ] ;for (i=1;i<=n;i++){if (tmp+a[i]>ans){ans=tmp+a[i];len=i-beg;}else if ( [       ②        ] &&i-beg>len)len=i-beg;if (tmp+a[i] [   ③   ]  ){beg=   [  ④    ] ;tmp=0;}else[	   ⑤        ];}cout << ans << " " << len << endl;return 0;
}

正确答案:

1. 0
2. tmp + a[i] = = ans / a[i] + tmp == ans / ans == a[i]+tmp
3. <0
4. i
5. tmp+=a[i] / tmp=tmp+a[i]

选择一个新数，如果比原来大，那么就赋值给最大值，如果和原来一样，原值保留。如果加起来后比原来还小，则抛弃掉此值，同时把 “前面数的和“ 还有 “个数“ 全部重置（和重置为0，个数变为当前的i），其余情况保留当前值即可。
【①】 0 ； 很明显，变量初始化，赋值为0，送分题
【②】 tmp+a[i] == ans 或者 a[i]+tmp == ans 或者an s== a[i]+tmp ； 已知ans初值为0，根据上个if的条件，判断的是tmp+a[i]和tmp的大于关系
那么此空判断的应该是tmp+a[i]和tmp的等于关系。
【③】 <0 ; 上面的填完了大于和等于的情况，这里应该填小于的情况，但是不能填ans。因为ans有赋值，这里的意思就是如果出现了负数，
【④】 i； 下方tmp重置为0，所以beg这个时候也是重置，但是重置为i
【⑤】tmp+=a[i] 或者 tmp=temp+a[i] ； 其余情况把a[i]累加到tmp中，让tmp在循环中起作用

2、(国王放置) 在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0 ~ m-1

#include <iostream>
using namespace std;int n,m,k,ans;
int hash[5][5];
void work(int x,int y,int tot){int i,j;if (tot==k){ans++;return;}do{while (hash[x][y]){y++;if (y==m){x++;y=[     ①     ];}if (x==n)return;}for (i=x-1;i<=x+1;i++)if (i>=0&&i<n)for (j=y-1;j<=y+1;j++)if (j>=0&&j<m)[	        ②         ];[        ③         ];for (i=x-1;i<=x+1;i++)if (i>=0&&i<n)for (j=y-1;j<=y+1;j++)if (j>=0&&j<m)[	     ④     ];y++;if (y==m){x++;y=0;}if (x==n)return;}while (1);
}
int main(){cin >> n >> m >> k;ans=0;memset(hash,0,sizeof(hash));[        ⑤       ] ;cout << ans << endl;return 0;
}

正确答案：

1. 0
2. hash[i][j]++ / hash[i][j]= hash[i][j]+1 / ++hash[i][j]
3. work(x,y,tot+1)
4. hash[i][j]-- / hash[i][j]= hash[i][j]-1 / --hash[i][j]
5. work(0,0,0)

跟八皇后类型类似，递归回溯。
递归回溯法两种结构：

结构1： int Search(int k){for (i=1; i<=算符种数; i++)if (满足条件) {保存结果if (到目的地) 输出解;else Search(k+1);恢复：保存结果之前的状态 {回溯一步 }}
}

结构2： int Search(int k) {if  (到目的地) 输出解;elsefor (i=1; i<=算符种数; i++)if  (满足条件){保存结果;Search(k+1);恢复：保存结果之前的状态{回溯一步}            　}
}

【①】0；这段while代码实际上是在遍历hash数组，y到了m后，x增加1，同时y重置为0，下面的x如果到头了，直接返回。
【②】 hash[i][j]++ 或者 hash[i][j] = hash[i][j]+1 或者++ hash[i][j] ； 上面的嵌套for循环实际上在标记某个点的八个方向，把这个点进行加1操作，这样下次遍历的时候就可以认为这个已经访问过了，从而访问别的点。
【③】work(x,y,tot+1) ； 上面表示放置了一个国王，所以这个地方开始放置下一个国王，递推做法，开始放置下一个国王。
【④】hash[i][j]– 或者 hash[i][j] = hash[i][j]-1 或者– hash[i][j] ； 【解析】后退一步，所以hash[i][j]– 。也可以看出下方的代码和上面的部分代码一致，表示回溯一步之后的下一个点看其是否符号条件。
【⑤】work(0,0,0) ；主函数内，初始化之后，是函数的调用，而且本文定义了一个函数，从来没用过，这个地方是函数调用。根据后面函数参数猜想，这个地方应该是x和y坐标，还有国王的数量。