2005普及组c语言解题报告

求2011年九月以及以前的计算机二级考试C语言试题及答案、以及考试内容分析和解题技巧。记住只要C的。

(1)下面叙述正确的是________。

A)算法的执行效率与数据的存储结构无关

B)算法的空间复杂度是指算法程序中指令(或语句)的条数

C)算法的有穷性是指算法必须能在执行有限个步骤之后终止

D)算法的时间复杂度是指执行算法程序所需要的时间

(1)C

知识点:算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度)

评 析：算法的设计可以避开具体的计算机程序设计语言，但算法的实现必须借助程序设计语言中提供的数据类型及其算法。数据结构和算法是计算机科学的两个重要支柱。它们是一个不可分割的整体。算法在运行过程中需辅助存储空间的大小称为算法的空间复杂度。算法的有穷性是指一个算法必须在执行有限的步骤以后结束。算法的时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。

(2)以下数据结构属于非线性数据结构的是________。

A)队列 B)线性表 C)二叉树 D)栈

(2)C

知识点:栈和队列的定义；栈和队列的顺序存储结构及其基本运算

评 析:线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称后进先出表(Last In First Out)。队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素，队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表(First In First Out)。二叉树的数据结构是树型结构，结构中数据元素之间存在着一对多的关系，因此它是一种非线性数据结构。

(3)在一棵二叉树上第8层的结点数最多是________。

A)8 B)16 C)128 D)256

(3)C

知识点：二叉树的定义及其存储结构

评 析:根据二叉树的性质：二叉树第i(I1)层上至多有2i-1个结点。得到第8层的结点数最多是128。

(4)下面描述中，不符合结构化程序设计风格的是________。

A)使用顺序、选择和重复(循环)三种基本控制结构表示程序的控制逻辑

B)自顶向下

C)注重提高程序的执行效率

D)限制使用goto语句

(4)C

知识点：结构化程序设计

评 析：结构化程序设计方法的四条原则是：1．自顶向下：2．逐步求精；3．模块化；4．限制使用goto语句。“自顶向下”是说，程序设计时，应先考虑总体，后考虑细节，先考虑全局目标，后考虑局部目标；“逐步求精’’是说，对复杂问题，应设计一些子目标作过渡，逐步细节化；“模块化”是说，一个复杂问题肯定是由若干稍简单的问题构成，解决这个复杂问题的程序，也应对应若干稍简单的问题，分解成若干稍小的部分。

(5)下面概念中，不属于面向对象方法的是________。

A)对象、消息 B)继承、多态 C)类、封装 D)过程调用

(5)D

知识点:面向对象的程序设计方法、对象、方法、属性及继承与多态性

评 析:面向对象方法是一种运用对象、类、封装、继承、多态和消息等概念来构造、测试、重构软件的方法。面向对象方法从对象出发，发展出对象、类、消息、继承等概念。

(6)在结构化方法中，用数据流程图(DFD)作为描述工具的软件开发阶段是________。

A)可行性分析 B)需求分析 C)详细设计 D)程序编码

(6)B

知识点:结构化设计方法

评 析:软件开发阶段包括需求分析、总体设计、详细设计、编码和测试五个阶段。其中需求分析阶段常用的工具是数据流程图和数据字典。

(7)软件生命周期中所花费用最多的阶段是________。

A)详细设计 B)软件编码 C)软件测试 D)软件维护

(7)D

知识点:软件工程基本概念，软件生命周期概念，软件工具与软件开发环境

评 析:软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。本题中详细设计、软件编码和软件测试都属于软件开发阶段；维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。

(8)数据库系统的核心是________。

A)数据模型 B)DBMS C)软件工具 D)数据库

(8)B

知识点:数据库的基本概念：数据库，数据库管理系统，数据库系统

评 析:数据库管理系统DBMS是数据库系统的核心。DBMS是负责数据库的建立、使用和维护的软件。DBMS建立在操作系统之上，实施对数据库的统一管理和控制。用户使用的各种数据库命令以及应用程序的执行，最终都必须通过DBMS。另外，DBMS还承担着数据库的安全保护工作，按照DBA所规定的要求，保证数据库的完整性和安全性。

(9)下列叙述中正确的是________。

A)数据处理是将信息转化为数据的过程

B)数据库设计是指设计数据库管理系统

C)如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键

字，则称其为本关系的外关键字

D)关系中的每列称为元组，一个元组就是一个字段

(9)C

知识点:数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型

评 析：数据处理是指将数据转换成信息的过程，故选项A叙述错误；设计数据库的目的实质上是设计出满足实际应用需求的实际关系模型，故选项B叙述错误；关系中的行称为元组，对应存储文件中的记录，关系中的列称为属性。对应存储文件中的字段，故D选项叙述错误。

(10)下列模式中，_______是用户模式。

A)内模式 B)外模式 C)概念模式 D)逻辑模式

(10)B

知识点：数据库的基本概念：数据库，数据库管理系统，数据库系统

评 析：数据库管理系统的三级模式结构由外模式、模式和内模式组成。外模式，或称子模式，或称用户模式，是指数据库用户所看到的数据结构，是用户看到的数据视图。模式，或称逻辑模式，是数据库中对全体数据的逻辑结构和特性的描述，是所有用户所见到的数据视图的总和。外模式是模式的一部分。内模式，或称存储模式，或称物理模式，是指数据在数据库系统内的存储介质上的表示。即对数据的物理结构和存取方式的描述。

36)算法的时间复杂度是指_______。

A)执行算法程序所需要的时间

B)算法程序的长度

C)算法执行过程中所需要的基本运算次数

D)算法程序中的指令条数

(36)C

知识点：算法复杂度的概念和意义(时问复杂度与空间复杂度)

评析：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

(37)下列叙述中正确的是_______。

A)线性表是线性结构 B)栈与队列是非线性结构

C)线性链表是非线性结构 D)二叉树是线性结构

(37)A

知识点：线性结构与非线性结构的概念

评析：根据数据结构中各数据元素之间相关联关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： (1)有且只有一个根结点； (2)每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。

(38)下面关于完全二叉树的叙述中，错误的是_______。

A)除了最后一层外，每一层上的结点数均达到最大值

B)可能缺少若干个左右叶子结点

C)完全二叉树一般不是满二叉树

D)具有结点的完全二叉树的深度为[log2n]+l

(38)B

知识点：二叉树的定义及其存储结构

评析：这里考察完全二又树与满二叉树的定义及二叉树的性质。满二叉树指除最后一层外每一层上所有结点都有两个子结点的二叉树。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干子结点(叶子结点)的二叉树。因此选项A是正确的，而选项B是错误的。由定义可知，满二叉树肯定是完全二又树，而完全二又树一般不是满二叉树，因此选项c是正确的叙述。选项D即二又树性质(5)，也是正确的。

(39)结构化程序设计主要强调的是_______。

A)程序的规模 B)程序的易读性

C)程序的执行效率 D)程序的可移植性

(39)B

知识点：结构化程序设计

评析：结构化程序设计主要强调的足结构化程序清晰易读，可理解性好，程序员能够进行逐步求精、程序证明和测试．以保证程序的正确性。

(40)在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是_______。

A)概要设计 B)详细设计 C)可行性分析 D)需求分析

(40)D

知识点：软件工程基本概念，软件生命周期概念，软件工具与软件开发环境

评析：通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。也就是说，软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。软件生命周期的主要活动阶段为：

① 可行性研究和计划制定。确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可行方案，制定完成开发任务的实施计划。

②需求分析。对待开发软件提出的需求进行分析并给出详细定义，即准确地确定软件系统的功能。编写软件规格说明书及初步的用户手册，提交评审。

③软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。

④软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划。

⑤软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。

⑥运行和维护。将已交付的软件投入运行，并存运行使用中不断地维护，根据新提出的需求进行必要而且可能的扩充和删改。

(41)数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是_______。

A)控制流 B)加工 C)数据存储 D)源和潭

(41)A

知识点：结构化分析方法，数据流图，数据字典，软件需求规格说明书

评析：数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。数据流图中的主要图形元素有：加工(转换)、数据流、存储文件(数据源)、源和潭。

(42)软件需求分析一般应确定的是用户对软件的_______。

A)功能需求 B)非功能需求 C)性能需求 D)功能需求和非功能需求

(42)D

知识点：结构化设计方法

评析：软件需求分析中需要构造一个完全的系统逻辑模型，理解用户提出的每一功能与性能要求，是用户明确自己的任务。因此，需求分析应确定用户对软件的功能需求和非功能需求。

(43)下述关于数据库系统的叙述中正确的是_______。

A)数据库系统减少了数据冗余

B)数据库系统避免了一切冗余

C)数据库系统中数据的一致性是指数据类型的一致

D)数据库系统比文件系统能管理更多的数据

(43)A

知识点：数据库的基本概念：数据库，数据库管理系统，数据库系统

评析：由于数据的集成性使得数据可为多个应JH=j所共享，特别是在网络发达的今天，数据库与网络的结合扩大了数据关系的应用范围。数据的共享自身义可极大地减少数据冗余性，不仅减少了不必要的存储空间，更为重要的是可以避免数据的不一致性。所谓数据的一致性是指在系统中同一数据的不同出现应保持相同的值，而数据的不一致性指的是同一个数据在系统的不同拷贝处有不同的值。

(44)关系表中的每一横行称为一个_______。

A)元组 B)字段 C)属性 D)码

(44)A

知识点：数据库的基本概念：数据库．数据库管理系统，数据库系统

评析：在关系数据库中，关系模型采用二维表来表示，简称“表”。二维表是由表框架及表元组组成。在表框架中，按行可以存放数据，每行数据称为元组。

(45)数据库设计包括两个方面的设计内容，它们是_______。

A)概念设计和逻辑设计 B)模式设计和内模式设计

C)内模式设计和物理设计 D)结构特性设计和行为特性设计

(45)A

知识点：数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略

评析：数据库设计可分为概念设计与逻辑设计。数据库概念设计的目的是分析数据问内存语义关联，在此基础上建立一个数据的抽象模型。数据库逻辑设计的主要工作是将E-R图转换为指定的RDBMS中的关系模型。

(61)字符(char)型数据在微机内存中的存储形式是________。

A)反码 B)补码

C)EBCDIC码 D)ASCII码

(61)D

知识点：字符数据在内存中的存储形式

评析：将一个字符常量放到一个字符变量中，实际上并不是把该字符本身放到内存单元中去，而是将该字符的ASCII码值放到存储单元中。

71)算法的空间复杂度是指_______。

A)算法程序的长度 B)算法程序中的指令条数

C)算法程序所占的存储空间 D)算法执行过程中所需要的存储空间

(71)D

知识点：算法的复杂度

评析：一个算法的空间复杂度，一般是指执行这个算法所需的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

(72)下列关于栈的叙述中正确的是_______。

A)在栈中只能插入数据 B)在栈中只能删除数据

C)栈是先进先出的线性表 D)栈是先进后出的线性表

(72)D

知识点：栈的输入输出操作

评析：栈是限定在一端进行插入与删除的线性表。

栈是按照“先进后出”的或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。

(73)在深度为5的满二叉树中，叶子结点的个数为_______。

A)32 B)31 C)16 D)15

(73)C

知识点：二叉树的概念

评析：所谓满二叉树是指除最后一层外，每层上的所有结点都有两个子结点。也就是说，在满二又树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2k-1个结点，且深度为m的满二叉树有2m个结点。

在满二叉树中，最后一层的结点个数就是叶子结点的个数，本题中深度为5，故叶子结点数为25-1=24==16。

(74)对建立良好的程序设计风格，下面描述正确的是_______。

A)程序应简单、清晰、可读性好 B)符号名的命名要符合语法

C)充分考虑程序的执行效率 D)程序的注释可有可无

(74)A

知识点：程序设计风格

评析：要形成良好的程序设计风格，主要应注重和考虑下述一些因素：符号名的命名应具有一定的实际含义，以便于对程序功能的理解；正确的注释能够帮助读者理解程序；程序编写应优先考虑清晰性，除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。

(75)下面对对象概念描述错误的是_______。

A)任何对象都必须有继承性 B)对象是属性和方法的封装体

C)对象问的通讯靠消息传递 D)操作是对象的动态性属性

(75)A

知识点：对象的概念

评析：对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。

(76)下面不属于软件工程的3个要素的是_______。

A)工具 B)过程 C)方法 D)环境

(76)D

知识点：软件：[程的要素

评析：软件工程包括3个要素，即方法、工具和过程。

(77)程序流程图(PFD)中的箭头代表的是_______。

A)数据流 B)控制流 C)调用关系 D)组成关系

(77)B

知识点：软件设计工具

评析：程序流程图(PFD)是一种传统的、应用广泛的软件过程设计表示工具，通常也称为程序框图，其箭头代表的是控制流。

(78)在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是_______。

A)数据库系统 B)文件系统 C)人工管理 D)数据项管理

(78)A

知识点：数据管理技术的发展

评析：在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是数据库系统。

C语言 普及组的模拟题

一、选择题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题，即

每题有且只有一个正确答案，选对得分；后10题为不定项选择题，即每题有1至5个正确答案，只

有全部选对才得分）。

1.微型计算机的性能主要取决于（ ）。

A）内存 B）主板 C）中央处理器 D）硬盘 E）显示器

2. 128KB的存储器用十六进制表示，它的最大的地址码是( )

A)10000 B)EFFF C)1FFFF D)FFFFF E)FFFF

3.能将高级语言程序转换为目标程序的是( ).

A)调试程序 B)解释程序 C)编辑程序 D)编译程序 E)连接程序

4．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )B

A)01011110 B)00001111 C)01011100 D)11001110 E)11001010

5.计算机病毒传染的必要条件是( ) 。

A)在内存中运行病毒程序

B)对磁盘进行读写操作

C)在内存中运行含有病毒的可执行程序

D)复制文件

E)删除文件

6. TCP／IP协议共有( )层协议

A)3 B)4 C)5 D)6 E)7

7.192.168.0.1是属于( ).

A)A类地址 B)B类地址 B)C类地址 D)D类地址 E)E类地址

8.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第

一趟扫描的结果是( ).

A)(24,21,35,54,67, 78,63,73,89)

B)(24,35,21,54,67, 78,63,73,89)

C)(24,21,35,54,67, 63,73,78,89)

D)(21,24,35,54,63, 67,73,78,89)

E)(24,21,35,54,67, 63,73,78,89)

9.一棵n个结点的完全二叉树,则二叉树的高度h为( ).

A)n/2 B)log2n C)(log2n)/2 D) [log2n]+1 E)2n-1

10.下图对该图进行广度优先拓朴排序得到的顶点序列正确的是( ).

A)1,2,3,4,5,6

B)1,3,2,4,5,6

C)1,3,2,4,6,5

D)1,2,3,4,6,5,

E)1,3,2,4,5,6

11.下列属于冯.诺依曼计算机模型的核心思想是( ).

A)采用二进制表示数据和指令;

B)采用”存储程序”工作方式

C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)

D)结构化程序设计方法

E)计算机软件只有系统软件

12.下列属于输入设备的是( ).

A)打印机 B)扫描仪 C)光笔 D)鼠标 E)显示器

13.算式(1000)10-(100)16-(10)8的结果是( ).

A)(890)10 B)(986)8 C)(1011100000)2 D)(2E0)16 E)(736)10

14.下面关于算法的正确的说法是( )

A)算法必须有输出

B)算法必须在计算机上用某种语言实现

C)算法不一定有输入

D)算法必须在有限步执行后能结束

E)算法的每一步骤必须有确切的定义

15.下列关于十进制数100的正确说法是( ).

A)原码为01100100B

B)反码为64H

C)反码为9BH

D)补码为64H

E)补码为9BH

16.关于windows系统中的窗口和对话框的说法正确的是( ).

A)对话框能移动和改变大小

B)窗口能移动和改变大小

C)对话框只能移动和但不能改变大小

D)对话框不能移动但能改变大小

E)窗口能移动和但不能改变大小

17．下列逻辑运算正确的是（ ）。

A) A·（A + B ）= A

B) A +（A·B）= A

C) A·（B + C ）= A·B + A·C

D) A +（B·C）=（A + B）·（A + C）

E) A+1=A

18.下列关于排序说法正确的是( ).

A)插入排序、冒泡排序是稳定的

B)选择排序的时间复杂性为O(n2)

C)选择排序、希尔排序、快速排序、堆排序是不稳定的

D)希尔排序、快速排序、堆排序的时间复杂性为O(nlog2n)

E)快速排序是速度最快的排序

19.对于一个大小为3的栈，若输入队列为123456，则下列输出队列有可能的是（ ）。

A)123456 B)654321 C)432165 D)431256 E)321654

20. 设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key % 13,其中% 是求余数

运算。用二次探查法解决冲突,则对于序列(8、31、20、33、18、53、27),则下列说法正确

的是( ) 。

A)27在1号格子中

B)33在6号格子中

C)31在5号格子中

D)20在7号格子中

E)18在4号格子中

二．问题求解（5分*2=10分）

1．一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少种？

如 m=2，n=3 时有4种选法分别是：两种小球的个数分别为03，12，21，30．问：当m=4，n=4时

选法数=__________。

2．如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，…….有

nm个度为m的结点,则该树中叶结点的的个数=______________.

1、C语言中没有逻辑量，在给出逻辑运算结果时，以 代表“真”，用 代表“假”。

2、一个C源程序中至少应包括一个 。

3、C源程序的基本单位是 。

4、为表示关系X≥Y≥Z,应使用C语言表达式 。

5、若有以下定义：double w[10]；则w数组元素下标的上限是 ，下限是 。

6、若有以下定义：double w[5];则数组w下标的上限是 。

7、执行语句：for（i=1；i++4;）后;变量i的值是 。

6、在C语言中的实型变量分为两种类型，它们是 、 。

7、语句”printf(“%x,%o”,16,12);”的输出结果是 。

8、当a=5,b=4,c=1时，表达式ab!=c的值是 。

9、若有定义：char c=’\010’;则变量c中包含的字符数为 。

10、C语言中的标识符只能由三种字符组成，它们是 、 、 。

11、若k为int 型且赋值11。请写出运算k++后表达式的值为 ，变量的值为 。

12、在C语言程序中，如果对函数f的类型未加显说明，则函数f的隐含类型是 。

13、二维数组中元素在内存中的存放顺序是 。

14、设有定义int a=12，b=12；则语句 printf（”%d %d\n”，–a，++b）；的输出结果是：

。

15、当a=3，b=2，c=1时，表达式f=abc的值为______________________。

16、C语言中的文件类型有 、 。

二、选择题

1、C语言可执行程序的开始执行点是（ ）

A、 程序中第一条可执行语言 B、 程序中第一个函数

C、 程序中的main函数 D、 包含文件中的第一个函数

2、以下叙述中不正确的是（ ）

A、在函数中，通过return语句传回函数值

B、在函数中，可以有多条return语句

C、在C中，main后的一对圆括号中也可以带有形参

D、在C中，调用函数，必需在一条独立的语句中完成

3、对C程序在作逻辑运算时判断操作数真、假的表述，下列哪一个是正确的（ ）。

A、0为假，非0为真 B、只有1为真

C、-1为假，1为真 C、0为真，非0为假

4、以下字符中，不正确的C语言转义字符是（ ）

A、‘\t’ B、 ‘\011’ C、‘\n’ D、 ‘\018

5、C语言中运算对象必需是整型的运算符是（ ）

A、% B、/ C、！ D、**

6、putchar函数可以向终端输出一个( )

A、整型变量表达式值 B、实型变量值

C、字符串 D、字符或字符型变量值

7、下列各语句定义了数组，其中哪一个是正确的（ ）。

A、int a[5],b[2,3]； B、char no(30)；

C、int x[]； D、int x[5]={1,2,3}；

8、数组定义为”int a[4][5];”, 引用”*(a+1)+2″表示（ ）。

A、a[1][0]+2 B、 a数组第1行第2列元素的地址

C、a[0][1]+2 D、 a数组第1行第2列元素的值

9、a是int类型变量，c是字符变量。下列输入语句中哪一个是错误的（ ）。

A、scanf (“%d, %c”,a, c); B、scanf (” %d%c”, a, c);

C、scanf (” %d%c”, a,c ); D、scanf ( “d=% d, c=%c”,a, c);

10、将整型变量a、b中的较小值为变量c赋值，下列语句中正确的是（ ）。

A、c= =(ab)? a:b; B、c=if(ab)a else b;

C、c=(ab)? a:b; D、(ab)? c=a:c=b;

11、将整型变量a、b中的较大值为变量c赋值，下列语句中正确的是（ ）。

A、c= =(ab)? a:b; B、c=(ab)? a:b;

C、c=if(ab)a else b; D、(ab)? c=a:c=b;

12、逻辑运算符中，运算优先级按从高到低依次为（ ）。

A、, !, || B、||，, ! C、, ||, ! D、！，, ||

13、在C语言程序中（ ）

A、 函数的定义可以嵌套，但函数的调用不可以嵌套

B、 函数的定义和函数的调用均不可以嵌套

C、 函数的定义不可以嵌套，但函数的调用可以嵌套

D、 函数的定义和函数的调用均可以嵌套

14、C语言中的文件类型只有（ ）

A、索引文件和文本文件两种 B、ASCII文件和二进制文件两种

C、文本文件一种 D、 二进制文件一种

15、若变量已正确定义并赋值，符合C语言语法的表达式是（ ）

A、a=7+b+c，a++ B、a=a+7； C、int（12.3%4） D、a=a+7=c+b

16、设有int a[ ]={10,11,12},*p=a[0]；则执行完*p++;*p+=1;后a[0],a[1],a[2]的值依次是 （ ）

A.10,11,12 B.11,12,12 C.10,12,12 D.11,11,12

17、已知ch是字符型变量，下面正确的赋值语句是（ ）

A、ch=’\123’ B、ch=’xfff’ C、ch=’\08’ D、ch=’\’

18、以下函数调用语句中，含有的实参个数是（ ）

A、1 B、2 C、4 D、5

Func（（exp1，exp2），（exp3，exp4，exp5））；

19、以下叙述中正确的是 （ ）

A、 输入项可以是一个实型常量，如 scanf（”%f “，3.5）;

B、 只有格式控制，没有输入项，也能正确输入数据到内存，如： scanf（”a=%d，b=%d”）；

C、 当输入一个实型数据时，格式控制可以规定小数点后的位数，如:scanf（”%4.2f”，f）；

D、 当输入数据时，必须指明变量地址，例如： scanf（”%f”，f）；

20、程序运行输出了错误的结果，可以排除下列哪一个因素（ ）。

A．算法错误 B、运行时输入数据错误

C、未通过编译 D、系统资源配置不当

21、要为字符型变量a赋初值，下列语句中哪一个是正确的（ ）。

A、char a=’3’; B、char a=”3″;

C、char a=%; D、char a=*;

22、数组定义为”int a[4][5];”, 引用”a[1]+3″表示（ ）。

A、a数组第1行第3列元素的地址 B、a数组第1行第3列元素的值

C、a数组第4行的首地址 D、a数组第4列的首地址

三、程序阅读

1、以下程序的输出结果为 。

main()

{ int x=2;

while (x–);

printf(“%d\n”,x);

}

2、以下程序的运行结果是 。

main()

{ int m=5;

if (m++ 5) printf(“%d\n”,m);

else printf(“%d\n”, m――);

}

3、当执行以下程序段后，i的值为 、j的值为 、k的值为 。

int a,b,c,d,i,j,k;

a=10; b=c=d=5; i=j=k=0;

for( ; ab; ++b) i++;

while (a++c) j++;

do k++; while (ad++);

4、以下程序的输出结果是 。

main（）

{ int k=2，m=4，n=6；

int *pk=k, *pm=m, *p;

*(p=n)=*pk*(*pm);

printf(“%d\n”,n);

}

5、以下程序的输出结果是 。

fun1(int a, int b)

{ int c;

a+=a; b+=b;

c=fun2 ( a, b );

return c*c;

}

fun2( int a, int b)

{ int c;

c=a*b%3;

return c;

}

main()

{ int x=11,y=19;

printf(“%d\n”, fun1(x,y));

}

6、以下程序的输出结果是 z= , r= 。

func(int a, int b)

{ int c;

c=a+b;

return c;

}

main()

{ int x=6,y=7,z=8,r;

r=func((x–,y++,x+y),z–);

printf(“z=%d,r=%d\n”,z,r);

}

7、以下程序的输出结果为 .

main()

{ int aa[3][3]={{2},{4},{6}},i,*p=aa[0][0];

for(i=0;i2;i++)

{ if(i==0)

aa[i][i+1]=*p+1;

else ++p;

printf(“%d”,*p);

}

printf(“\n”);

}

8、下列程序运行的输出结果： ， 。

#define X 5

#define Y X+1

#define Z Y*X/2

main()

{ int a;

a=Y;

printf(“%d,%d\n”,Z,–a);

}

四、程序填空

findmax返回数组s中最大元素的下标，数组中元素的个数由t传入，请填空 。

findmax（int s[ ], int t）

{ int k,p;

for(p=0, k=p; pt; p++)

if (s[p]s[k]) ;

return ;

}

有以下程序段：

s=1.0;

for (k=1; k=n; k++) s=s+1.0/(k*(k+1));

printf(“%f\n”,s);

请填空，使下面的程序段的功能完全与之等同。

s=0.0;

;

k=0;

do

{ s=s+d;

;

d=1.0/(k*(k+1));

}

while( );

printf(“%f\n”,s);

3、 以下程序统计从终端输入的字符中每个大写字母的个数，4、 num[0]中统计字母A的个数，5、 其他依次类推。用回车符结束输入，6、 请填空。

#include “stdio.h”

#include “ctype.h”

main()

{ int num[26]={0}, i ;

char c;

while(（ ）!=’\n’)

if (isupper(c)) num[ ]+=1;

for( i=0; i26; i++)

if (num[i]) printf(“%c: %d\n”, i+’A’,num[i]);

}

4、以下fun函数的功能是将一个字符串的内容颠倒过来，请填空。

#include “string.h”

void fun(char str[])

{ int i,j,k;

for(i=0,j= ; ij; i++, )

{ k=str[i]; str[i]=str[j]; str[j]=k; }

}

5、以下程序的功能是：从键盘上输入若干学生的成绩，统计并输出最高成绩和最低成绩，当输入负数时结束输入。请填空。

main()

{ float x,amax,amin;

scanf(“%f”,x);

amax=x; amin=x;

while( )

{ if ( xamax ) amax=x;

else if （xamin） ;

;

}

printf(“\namax=%f\namin=%f\n”,amax,amin);

}

6、输入若干字符，分别统计数字字符的个数、英文字母的个数，当输入换行符时输出统计结果，运行结束。

#include stdio.h

void main()

{ char ch; ;

while(( )!=’\n’)

{if(ch=’0’ch=’9′) s1++;

if((ch=’a’ ch=’z’)|| ) s2++;}

printf(“%d,%d\n”,s1,s2);

}

编程题

输入一行数字字符（以回车符结束输入），请用数组元素作为计数器来统计每个数字字符的个数,并输出统计结果。用下标为0的元素统计字符’0’的个数，下标为1的元素统计字符’1’的个数，…。

#includestdio.h

main()

{

}

2、下面findmax函数将计算数组中的最大元素及其下标值和地址值，请编写*findmax（）函数。

#includestdio.h

*findmax(int *s, int t, int *k)

{

}

main()

{ int a[10]={12,23,34,45,56,67,78,89,11,22},k,*add;

add=findmax(a,10,k);

printf(“%d,%d,%o\n”,a[k],k,add);

}

3、编写程序，求1－3＋5－7＋…－99＋101的值。

#include stdio.h

main()

{ }

4、以下程序将字符串中的第m个字符开始的全部字符复制成另一个字符串，在主函数中输入字符串及m的值并输出复制结果，在被调用函数copystr中完成复制。请编写copystr函数。

#includestdio.h

#includestring.h

main()

{ int m;

char str1[80], str2[80];

printf(“Please input a string :\n”);

gets(str2);

printf(“Input m:\n”);

scanf(“%d”,m);

if (strlen(str2)m ) printf(“error input！\n”);

else

{ copystr(str1,str2,m);

printf(“Result is :%s\n”,str1);

}

}

void copystr(char *p1,char *p2,int m)

{

}

编写函数invert将数组中的数按颠倒的顺序重新存放。在操作时，只能借助一个临时存储单元而不得另外开辟数组。

/*参数n为数组中的元素个数*/

void invert(int a[ ],int n)

{

}

6、函数maxmin完成的功能是：对传送过来的三个数选出最大和最小数，并通过形参传回调用函数。试编写该函数，

main()

{ int a, b, c, max,min;

printf(“please input three integer：\n”);

scanf(“%d,%d,%d”,a,b,c);

maxmin(a,b,c,max,min);

printf(“a=%d,b=%d,max=%d,min=%d\n”,a,b,c,max,min);

}

void maxmin(int a, int b, int c, int *max, int *min)

{

}

2005年第11届信息学奥林匹克pascal普及组试题求助

program circle;

const

max_k = 100;

type

TLarge = array[0..max_k-1] of integer;

var

k,i:integer;

n_str:string;

n,t,p,p_new,r,r_new:TLarge;

s:set of 0..9;

function set_large(var a:TLarge; s:string):boolean;

var

i,count:integer;

first:boolean;

begin

result := false;

count := 0;

first := true;

for i := length(s) downto 1 do

if ((not first) or (s[i] ‘ ‘)) then

begin

first := false;

a[count] := ord(s[i]) – ord(‘0’);

if (a[count] 0) or (a[count] 9) then

exit;

inc(count);

if (count = k) then

break;

end;

for count := count to k-1 do

a[count] := 0;

result := true;

end;

procedure print_large(var a:TLarge);

var

first:boolean;

i:integer;

begin

first := true;

for i := k-1 downto 0 do

if (not first) or (a[i] 0) then

begin

first := false;

write(a[i]);

end;

if (first) then

write(‘0’);

writeln;

end;

procedure adjust_large(var a:TLarge);

var

i,r,t:integer;

begin

r := 0;

for i := 0 to k-1 do

begin

t := r + a[i];

a[i] := t mod 10;

r := t div 10;

end;

end;

procedure add_large(var a,b:TLarge);

var

i:integer;

begin

for i := 0 to k-1 do

inc(a[i],b[i]);

adjust_large( a );

end;

procedure multi_large(var a,b:TLarge);

var

c:TLarge;

i,j:integer;

begin

set_large(c,’0′);

for i := 0 to k-1 do

for j := 0 to i do

inc(c[i],a[j]*b[i-j]);

adjust_large( c );

a := c;

end;

begin

write(‘input N: ‘);

readln(n_str);

write(‘input K: ‘);

readln( k );

if (not set_large(n,n_str)) then

exit;

set_large(r,’1′);

p := n;

for i := 0 to k-1 do

begin

t := n;

set_large(p_new,’1′);

set_large(r_new,’0′);

s := [];

while (not (t[i] in s)) do

begin

s := s + [t[i]];

multi_large(t,p);

multi_large(p_new,p);

add_large(r_new,r);

end;

if (t[i] n[i]) then

begin set_large(r,’0′); break end;

r := r_new;

p := p_new;

end;

print_large( r );

readln;

end.

c语言求高精度n!用数组求怎么做

涉及到大整数的问题

建议使用java的BigInteger类

用C需要编写一个函数，使用数组来储存每个位的值

这里我用C++写了一个类，你自己先看看

————————————————

//BigCount.h头文件

#includestdio.h

#include iostream.h

#includemath.h

#includestring.h

#includestdlib.h

#define MAX 1000

class BigCount{

private:

int math1[MAX],math2[MAX],mathOK[MAX];

int w1,w2;

//w1是整数1的位数 w2是整数2的位数

//char str1[MAX],str2[MAX];

public:

BigCount()

{

int i=0;

for(;iMAX;i++)

{

math1[i]=0;

math2[i]=0;

mathOK[i]=0;

}

w1=w2=0;

}

int Diversion(char *str1,char *str2)

{

int p=0,k=0;

p=strlen(str1)-1;

w1=p+1;

while(p=0) //转换第一个大整数

{

if(*(str1+p)’9′ || *(str1+p)’0′) {cout”输入的数字不合法，失败!”endl;exit(0);}

math1[k]=*(str1+p)-‘0’;

k++;

p–;

}

k=0;p=0;

p=strlen(str2)-1;

w2=p+1;

while(p=0)

{

if(*(str2+p)’9′ || *(str2+p)’0′) {cout”输入的数字不合法，失败!”endl;exit(0);}

math2[k]=*(str2+p)-‘0’;

k++;

p–;

}

if(w1w2) k=w1-1;

if(w1=w2) k=w2-1;

return(k); //返回值是两个整数中位数最多的那个数的位数

}

char *Add(char s1[],char s2[]) //两个整数相加的方法

{

int k=0,p=0;

int jw=0;

int w1,w2; //每个字符串的长度

char r[MAX]={‘\0’},*str=r;

char str1[MAX]={‘\0’},str2[MAX]={‘\0’};

int math1[MAX]={0},math2[MAX]={0};

strcpy(str1,s1); //复制字符串

strcpy(str2,s2);

w1=strlen(str1);//计算长度

w2=strlen(str2);

if(w1w2) k=w1-1; //得到两个整数的最长长度

else k=w2-1;

Diversion(str1,str2,math1,math2); //转换着两个字符串为相应的单数字数组

p=0;

while(p=k)//依次加上每一位（在数组中）

{

mathOK[p]=math1[p]+math2[p]+jw;

if(mathOK[p]9) {jw=1;mathOK[p]=mathOK[p]%10;}

else jw=0;

p++;

}

if(jw==1) {mathOK[p]=1;k=k+1;} //最后（最大）一位超过10，则添加一位并进位

for(p=k;p=0;p–) //输出答案并返回这个字符串

{

r[k-p]=mathOK[p]+’0′;

}

return(str);

}

void Diversion(char *str1,char *str2,int *m1,int *m2)

//对两个字符串，分别转换成单个数字的数组，保存到m1 m2

{

int k=0,p=0;

p=strlen(str1)-1;

while(p=0) //转换第一个大整数

{

if(*(str1+p)’9′ || *(str1+p)’0′) {cout”输入的数字不合法，失败!”endl;exit(0);}

m1[k]=*(str1+p)-‘0’;

k++;

p–;

}

k=0;p=0;

p=strlen(str2)-1;

while(p=0)

{

if(*(str2+p)’9′ || *(str2+p)’0′) {cout”输入的数字不合法，失败!”endl;exit(0);}

m2[k]=*(str2+p)-‘0’;

k++;

p–;

}

}

int Add(int *m1,int *m2,int n1,int n2)//单个整数的相加方法

{

int i,tmp,ws,k=0,jw=0;

int math[MAX]={0},*p=math;

int math1[MAX]={0},math2[MAX]={0};

memcpy(math1,m1,sizeof(int)*n1);

memcpy(math2,m2,sizeof(int)*n2);

for(i=0;in1/2;i++)

{

tmp=math1[i];

math1[i]=math1[n1-i-1];

math1[n1-i-1]=tmp;

}

for(i=0;in2/2;i++)

{

tmp=math2[i];

math2[i]=math2[n2-i-1];

math2[n2-i-1]=tmp;

}

if(n1n2) ws=n1;

else ws=n2;

while(kws)

{

math1[k]=math1[k]+math2[k]+jw;

if(math1[k]9) {math1[k]=math1[k]%10;jw=1;}

else jw=0;

k++;

}

if(jw==1) {math1[k]=1;k++;}

for(i=0;ik/2;i++)

{

tmp=math1[i];

math1[i]=math1[k-i-1];

math1[k-i-1]=tmp;

}

for(i=0;ik;i++)

{

printf(“\n—–%d “,math1[i]);

}

printf(“——–\n”);

return(k);

}

void IntToStr(int x,char *ptr) //long int型转成char型

{

char str[MAX]={‘\0’},*p=str,tmp;

int i,n;

i=0;

for(n=x;n!=0;n=n/10) //这样的结果是个位在前

{

if((tmp=n%10+’0′)’9′ || tmp’0′) {cout”整数载入错误”endl;exit(0);}

str[i]=tmp;

i++;

}

n=strlen(str);

for(i=0;in/2;i++)//颠倒位置

{

tmp=str[i];

str[i]=str[n-i-1];

str[n-i-1]=tmp;

}

strcpy(ptr,p);

return;

}

char *ArrayToStr(int m[MAX],int n) //整数的单个数集转换成字符串

{

char str[MAX]={‘\0’},*p=str,tmp;

for(int i=0;in;i++)

{

if((tmp=m[i]+’0′)’9′ || tmp’0′) {cout”整数载入错误”endl;exit(0);}

str[i]=tmp;

}

return(p);

}

int StrToArray(char *str,int *math) //返回这个整数的数位长度

{

int p,k;

p=strlen(str)-1; //字符串长度

k=0; //整数位数

printf(“字符串是%s\n”,str);

while(k=p) //转换大整数

{

if(*str’9′ || *str’0′) {printf(“输入的数字不合法，失败!(%d)\n”,*str);exit(0);}

math[k]=*str-‘0’;

k++;

str++;

}

return(k);

}

char *Mult(char *str1,char *str2)

//任意整数字符串相乘，返回结果字符串

{

int i,j,k,w1,w2;

int den=1; //计算结果的符号问题

char str[MAX]={‘\0’},*p=str,*x=”0″;

char f[MAX]={‘\0’},*f1=f; //中间保存变量

char txt[MAX]={‘\0’},*text=txt; //结果变量

char *s1=str1,*s2=str2,sss1[MAX]={‘\0’},sss2[MAX]={‘\0’};

int math1[MAX]={0},math2[MAX]={0};

if(*str1==’-‘) {den=den*(-1);s1=str1+1;} //判断符号

if(*str2==’-‘) {den=den*(-1);s2=str2+1;}

Diversion(s1,s2,math1,math2); //把字符串转换成单个数字数组

w1=strlen(s1);

w2=strlen(s2);

for(i=0;iw1;i++)//双层循环来做乘法的算法

{

for(j=0;jw2;j++)

{

k=i+j;

//printf(“%d*%d\n”,math1[i],math2[j]);测试用

IntToStr(math1[i]*math2[j],p);//把本次计算值转换成字符串

while(k0)//根据相乘的两个数字所在的位数，后面添加相应位个0

{

strcat(p,x);

k–;

}

//printf(“本次计算之前f1 %s\n”,f1);测试用

text=Add(f1,p); //把这个数与结果相加并保存到text字符串

strcpy(f1,text); //这次的结果拷贝又给f1，以便下次使用Add方法

//printf(“本次计算结果%s\n”,f1);测试用

}

}

if(strlen(text)==0) text[0]=’0′;//哈哈，万一计算结果是’\0’，我们就给他一个0

else if(den==-1) //如果结果是负号 处理：将所有字符向后移一位，前面加’-‘

{

i=strlen(text);

while(i)

{

*(text+i)=*(text+i-1);

i–;

}

*text=’-‘;

}

return(text);//返回

}

};

———————————–

//user.cpp—–main()文件

#include “BigCount.h”

main()

{

int t;

BigCount temp;

char str1[1000],*p1=str1,str2[1000],*p2=str2;

char ok[1000],*asp=ok;

cout”输入一个数字,任意大:”endl;

cint;

temp.IntToStr(1,p1);

for(int i=1;i=t;i++)

{

temp.IntToStr(i,p2);

p1=temp.Mult(p1,p2);

}

printf(“%s\n”,p1);

}

注意：当输入的数字过大，计算时间会很久 222!使用3秒

C语言中的问题不明白为什么 新人麻烦详细解释一下谢谢

这里scanf指定逗号为输入的分隔符号。所以输入时数字和字符之间必须有逗号。

scanf不指定分隔符时，默认以空白字符（空格、回车、制表符）为分隔符。

PS：如果写%d%c不指定分隔符号。由于第二个变量是字符型，输入时中间不要加空格符，否则会将空白符号做为字符接收。

求noip2007（普及组pascal语言）复赛第二题和第三题的标程

NOIP 2007 普及组解题报告

1．奖学金

(scholar.pas／c／cpp)

【问题描述】

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数：学号、总分)是：

7 279

5 279

这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和)，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：

5 279

7 279

则按输出错误处理，不能得分。

【输入】

输入文件scholar.in包含行n+1行：

第l行为一个正整数n，表示该校参加评选的学生人数。

第2到年n+l行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1～n(恰好是输入数据的行号减1)。

所给的数据都是正确的，不必检验。

【输出】

输出文件scholar.out共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。

【输入输出样例l】

scholar.in scholar.out

6

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98 6 265

4 264

3 258

2 244

1 237

【输入输出样例2】

scholar.in scholar.out

8

80 89 89

88 98 78

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98 8 265

2 264

6 264

1 258

5 258

【限制】

50％的数据满足：各学生的总成绩各不相同

100％的数据满足：6=n=300

【试题分析】

简单的排序。因为n=300，所以选择排序不会超时。

存储方面只需存储三个数：学好、语文成绩和总分。

【参考程序】

program a1(input,output);

var

n,x,y,z,i,j:integer;

a:array[1..300,1..3] of integer;

procedure swap(var a,b:integer); {交换过程}

var

s:integer;

begin

s:=a;

a:=b;

b:=s;

end;

begin

assign(input,’scholar.in’);

assign(output,’scholar.out’);

reset(input);

rewrite(output);

readln(n);

for i:=1 to n do

begin

readln(x,y,z);

a[i,1]:=i;

a[i,2]:=x;

a[i,3]:=x+y+z;

end;

for i:=1 to n-1 do {选择排序}

for j:=i+1 to n do

if (a[i,3]a[j,3]) or ((a[i,3]=a[j,3]) and (a[i,2]a[j,2])) or ((a[i,1]a[j,1]) and (a[i,3]=a[j,3]) and (a[i,2]=a[j,2])) then

begin

swap(a[i,1],a[j,1]);

swap(a[i,2],a[j,2]);

swap(a[i,3],a[j,3]);

end;

for i:=1 to 5 do

writeln(a[i,1],’ ‘,a[i,3]);

close(input); {文件不要忘记关闭}

close(output);

end.

2．纪念品分组

(group.pas／c／cpp)

【题目描述】

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【输入】

输入文件group.in包含n+2行：

第1行包括一个整数w，为每组纪念品价格之和的上限。

第2行为一个整数n，表示购来的纪念品的总件数。

第3～n+2行每行包含一个正整数pi(5=pi=w)，表示所对应纪念品的价格。

【输出】

输出文件group.out仅一行，包含一个整数，即最少的分组数目。

【输入输出样例】

group.in group.out

100

9

90

20

20

30

50

60

70

80

90 6

【限制】

50％的数据满足：l=n=15

100％的数据满足：1=n=30000，80=w=200

【试题分析】

贪心法，先排序，然后按以下贪心策略：

设s为所需的组数。i,j为两个指针，开始时指向头和尾。

1． 如果a[i]+a[j]=w，s=:s+1，i:=i+1，j:=j-1。

2． 如果a[i]+a[j]w，s:=s+1，j:=j-1。

因为n=300000,所以用选择排序可能会超时，最好用快速排序。

【参考程序1】

program a2_1(input,output);

var

a:array[1..30000] of integer;

w,n,i,j,s:integer;

procedure qsort(h,t:integer);

var

p,i,j:integer;

begin

i:=h;

j:=t;

p:=a[i];

repeat

while (a[j]p) and (ji) do j:=j-1;

if ji then

begin

a[i]:=a[j];

i:=i+1;

while (a[i]p) and (ij) do i:=i+1;

if ij then

begin

a[j]:=a[i];

j:=j-1;

end;

end;

until i=j;

a[i]:=p;

i:=i+1;

j:=j-1;

if it then qsort(i,t);

if jh then qsort(h,j);

end;

begin

assign(input,’group.in’);

assign(output,’group.out’);

reset(input);

rewrite(output);

readln(w);

readln(n);

for i:=1 to n do readln(a[i]);

qsort(1,n); {快速排序}

i:=1;

j:=n;

s:=0;

while i=j do {贪心法}

begin

if i=j then

begin

s:=s+1;

break;

end;

if a[i]+a[j]=w then

begin

i:=i+1;

j:=j-1;

s:=s+1;

end;

if a[i]+a[j]w then

begin

s:=s+1;

j:=j-1;

end;

end;

writeln(s);

close(input);

close(output);

end.

【深入思考】

快速排序的程序比较难编，是否能有一种比较好编得排序方法呢？答案是肯定的。设p数组的下标为5至200，每读入一个数字x，就将p[x]加1，这样数字全部读入后就是有序的了，效率甚至比快速排序还高。这样的话贪心部分也要有所改变。

【参考程序2】

program a2_2(input,output);

var

p:array[5..200] of integer;

x,i,w,n,j,s:integer;

begin

assign(input,’group.in’);

assign(output,’group.out’);

reset(input);

rewrite(output);

readln(w);

readln(n);

for i:=5 to 200 do p[i]:=0; {数组清0}

for i:=1 to n do {读入数据}

begin

readln(x);

p[x]:=p[x]+1;

end;

i:=5;

j:=200;

s:=0;

while i=j do {贪心法}

begin

while p[i]=0 do i:=i+1; {找到不为空的数据}

while p[j]=0 do j:=j-1;

if ij then break;

if i=j then {处理i=j的情况}

if i*2=w then

begin

while p[i]=2 do

begin

p[i]:=p[i]-2;

s:=s+1;

end;

s:=s+p[i];

end

else

s:=s+p[i];

if i+j=w then {处理i+j=w的情况}

if p[i]p[j] then

begin

s:=s+p[j];

p[i]:=p[i]-p[j];

p[j]:=0;

end

else

begin

s:=s+p[i];

p[j]:=p[j]-p[i];

p[i]:=0;

end;

if i+jw then {处理i+jw的情况}

begin

s:=s+p[j];

p[j]:=0;

end;

end;

writeln(s);

close(input);

close(output);

end.

3、守望者的逃离

(escape.pas/c/cpp)

【问题描述】

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务写写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为整数秒。距离的单位为米(m)。

【输入】

在输入文件escape.in仅一行，包括空格隔开的三个非负整数M,S,T。

【输出】

在输出文件escape.out包括两行：

第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。

第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。

【输入输出样例1】

escape.in escape.out

39 200 4 No

197

【输入输出样例1】

escape.in escape.out

36 255 10 Yes

6

【限制】

30%的数据满足：1=T=10,1=S=100

50%的数据满足：1=T=1000,1=S=10000

100%的数据满足：1=T=300000,0=M=1000,1=S=108.

【试题分析】

典型的动态规划。

设f[i,j]为第i秒，魔法值为j时可行的最大距离。

f[i,j]:=max{f[i-1,j]+17,f[i-1,j-10]+60,f[i-1,j+4]} (当j≥10时);

f[i,j]:=max{f[i-1,j]+17,f[i-1,j+4]} (当j10时)

按题目所说，最大魔法值为1000，最大时间为300000秒，那么需要300000000的数组，空间会溢出，所以使用两个一维数组来迭代，只需2000的数组，但是时间复杂度为O(t*m)，有可能会超时。

【参考程序1】

program a3(input,output);

var

a,b:array[0..10000]of longint;

m,s,t,i,j:longint;

function max(a,b,c:longint):longint; {三个数找最大值}

var

k:longint;

begin

if ab then k:=a else k:=b;

if kc then k:=c;

max:=k;

end;

begin

assign(input,’escape.in’);

assign(output,’escape.out’);

reset(input);

rewrite(output);

readln(m,s,t);

for i:=0 to 10000 do {数组清0}

begin

a[i]:=0;

b[i]:=0;

end;

for i:=1 to t do

begin

for j:=0 to 9 do

begin

b[j]:=max(a[j]+17,a[j+4],0); {动态规划}

if b[j]=s then

begin

writeln(‘Yes’); {找到最小解，提前退出}

writeln(i);

close(input);

close(output);

halt;

end;

end;

for j:=10 to m do

begin

b[j]:=max(a[j]+17,a[j+4],a[j-10]+60); {动态规划}

if b[j]=s then

begin

writeln(‘Yes’); {找到最小解，提前退出}

writeln(i);

close(input);

close(output);

halt;

end;

end;

a:=b;

end;

writeln(‘No’); {无解}

writeln(a[m]);

close(input);

close(output);

end.

{注：此程序两个点超时}

【深入思考】

前面的动态规划时间复杂度太高，是否能想出更优的算法呢？思考一下，可以发现，中间的过程无非就是闪烁加恢复魔法，有时再走几步，我们用ms数组记录，闪烁加恢复魔法可走的最大距离，再和走路比较，选出最优方案，存入ts数组，这样的话，时间复杂度只有O(t),比前面的算法好得多。

【参考程序2】

program a3_2(input,output);

var

m,s,t,ti:longint;

ms:array[1..2,0..300000] of longint;

ts:array[0..300000] of longint;

begin

assign(input,’escape.in’);

assign(output,’escape.out’);

reset(input);

rewrite(output);

readln(m,s,t);

ms[2,0]:=m;

ts[0]:=0;

for ti:=1 to t do {动态规划}

begin

if ms[2,ti-1]=10 then {如果能使用闪烁，就是用}

begin

ms[1,ti]:=ms[1,ti-1]+60;

ms[2,ti]:=ms[2,ti-1]-10;

end

else

begin

ms[1,ti]:=ms[1,ti-1]; {恢复魔法值}

ms[2,ti]:=ms[2,ti-1]+4;

end;

if ts[ti-1]+17ms[1,ti] then ts[ti]:=ts[ti-1]+17 else ts[ti]:=ms[1,ti]; {找出大的值}

if ts[ti]=s then {如果顺利逃出，输出结果}

begin

writeln(‘Yes’);

writeln(ti);

close(input);

close(output);

halt;

end;

end;

writeln(‘No’); {无法逃出，输出结果}

writeln(ts[t]);

close(input);

close(output);

end.

{此程序所有测试点全部通过}

4．Hanoi双塔问题

(hanoi.pas/c/cpp)

【问题描述】

给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺

寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘足不加区分的(下图为n=3的情形)。现要将

这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：

(1)每次只能移动一个圆盘；

(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；

任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

【输入】

输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。

【输出】

输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。

【输入输出样例1】

hanoi.in hanoi.out

1 2

【输入输出样例2】

hanoi.in hanoi.out

2 6

【限制】

对于50％的数据，1=n=25

对于100％的数据，l=n=200

【提示】

设法建立An与An-1的递推关系式。

【试题分析】

不难发现：

An=2An-1+2（特别的，A1=2）

证明如下：

要将A柱上的2n个盘子移到C柱上，最佳的策略就是先将(2n-2)个盘子借助C柱移到B柱上，所需的次数为An-1，再将A柱上最大的两个盘子直接移到C柱上，所需的次数为2，最后将B柱上的(2n-2)个盘子借助A柱移到C柱上，所需的次数为An-1。总次数An=An-1+2+An-1=An=2An-1+2。

进而，可以得出：

An=2n+1-2

然后使用高精度计算。

【参考程序】

program a4(input,output);

var

n,i,j:integer;

a:array[1..100] of 0..9;

procedure ppp(k:integer); {高精度计算2n+1}

var

i,j,w,s:integer;

begin

a[1]:=1;

w:=0;

for i:=1 to k do

for j:=1 to 100 do

begin

s:=a[j]*2+w;

a[j]:=s mod 10;

w:=s div 10; {进位}

end;

end;

begin

assign(input,’hanoi.in’);

assign(output,’hanoi.out’);

reset(input);

rewrite(output);

readln(n);

ppp(n+1);

if a[1]=2 then {减2的处理}

a[1]:=a[1]-2

else

begin

a[1]:=a[1]+8;

a[2]:=a[2]-1;

end;

i:=100;

while a[i]=0 do i:=i-1; {计算位数}

for j:=i downto 1 do write(a[j]); {反序输出}

writeln;

close(input);

close(output);

end.