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

1、微型计算机中，控制器的基本功能是（ ）

A. 控制机器各个部件协调工作      
B. 实现算术运算和逻辑运算       
C. 获取外部信息                
D. 存放程序和数据

正确答案: A
中央处理器CPU主要由控制器和运算器组成。
运算器：主要进行算术运算和逻辑运算。
控制器：控制器的基本功能是控制机器各个部件的协调工作。这涉及到指令的解析、执行以及各个部件之间的协调，确保数据能够正确地在内存、处理器、输入输出设备之间流动，是计算机的指挥系统。

2、设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的（B）。

A. (A∧B)∨(C∧D∨┐A) 
B. ((┐A∧B)∨C)∧┐D
C. (B∨C∨D)∧D∧A
D. A∧(D∨┐C)∧B

正确答案: B

p	q	p ∧ q(与)	p ∨ q(或)	┐p(非)	┐p(非)
真	真	真	真	假	假
真	假	假	真	假	真
假	真	假	真	真	假
假	假	假	假	真	真

选项A： (A∧B)∨(C∧D∨┐A)
(A∧B) 为 true∧false，值为 false
(C∧D) 为 true∧false，值为 false
┐A 为 false
(C∧D∨┐A) 为 false∨false，值为 false
(A∧B)∨(C∧D∨┐A) 为 false∨false，值为 false

选项B： ((┐A∧B)∨C)∧┐D
┐A 为 false
(┐A∧B) 为 false∧false，值为 false
((┐A∧B)∨C) 为 false∨true，值为 true
┐D 为 true
((┐A∧B)∨C)∧┐D 为 true∧true，值为 true

选项C： (B∨C∨D)∧D∧A
(B∨C∨D) 为 false∨true∨false，值为 true
(B∨C∨D)∧D 为 true∧false，值为 false
(B∨C∨D)∧D∧A 为 false∧true，值为 false

选项D： A∧(D∨┐C)∧B
┐C 为 false
(D∨┐C) 为 false∨false，值为 false
A∧(D∨┐C) 为 true∧false，值为 false
A∧(D∨┐C)∧B 为 false∧false，值为 false

3、在下列关于图灵奖的说法中，不正确的是（ ）。

A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人
B. 图灵奖有“计算机界诺贝尔奖”之称
C. 迄今为止，还没有华裔计算机科学家获此殊荣
D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵

正确答案: C
实际上，有多位华裔计算机科学家获得了图灵奖。例如，姚期智是第一位获得图灵奖的华人，他在2000年因为“对于计算理论，包括量子计算、密码学及理论计算机科学其他领域的贡献”而获奖。还有其他华裔科学家也陆续获得了这一殊荣。因此，C 选项中的说法是不正确的。

A 选项正确，图灵奖确实是由美国计算机协会（ACM）设立的，用于奖励对计算机事业作出重大贡献的个人。

B 选项也正确，图灵奖在计算机科学领域具有很高的声誉，常常被称为“计算机界的诺贝尔奖”。

D 选项同样正确，图灵奖的名称取自计算机科学和人工智能的先驱、英国科学家阿兰·图灵（Alan Turing）。

图灵奖（Turing Award），全称“A.M. 图灵奖（A.M Turing Award）”，由美国计算机协会（ACM）于1966年设立，专门奖励那些对计算机事业作出重要贡献的个人。 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵（Alan M. Turing）（音译为：阿兰·图灵）。 由于图灵奖对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
每一年的图灵奖一般在下一年的3月下旬颁发，从1966年至2019年共73名获奖者。 按国籍分，美国学者最多，欧洲学者偶见之，华人学者目前仅有2000年图灵奖得主姚期智（现在清华大学、香港中文大学）。 据相关资料统计，截止2019年3月，美国斯坦福大学的图灵奖人数（校友或教职工）位列世界第一（27位）、美国麻省理工学院（26位）位列世界第二、美国加州大学伯克利分校（25位）位列世界第三 ；哈佛大学（14位）和卡耐基梅隆大学（13位）、普林斯顿大学（13位）分列世界第四和第五名。

4、计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。

A. ROM和RAM      
B. CPU       
C.ROM      
D. RAM

正确答案: C
在计算机工作过程中，若突然停电，只有ROM（只读存储器）中的信息不会丢失。这是因为ROM是设计为只能被反复读取，但不能被修改或删除的数据存储介质。它的数据是以螺旋状的方式从中心向外散开状的方式排列的，这种排列方式使得ROM中的数据即使在断电的情况下也不会丢失。

相比之下，RAM（随机存取存储器）是临时存储数据的，一旦断电，其中的数据就会丢失。CPU（中央处理器）是计算机的运算和控制核心，它本身不存储数据，因此不包含会丢失的信息。

RAM: 是内存的意思，就像你玩的一款单机游戏一样，突然断电后，下次打开游戏需要从头开始
ROM：只读存储器，类似硬盘，就是你下载下来的东西存放的地方，断电以后重新打开，还在硬盘里。

5、完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。

A. $N-1$
B. $N$
C. $2\ast N$
D. $2^N-1$

正确答案: B
两种思路
思路一：二叉树的结点，他的度只有3种，0，1和2。（想想为啥叫二叉树）
因为是完全二叉树，所以度为1的结点只可能是0个或1个（因为完全二叉树的定义是只有最下面的两层结点小于2，）。
因为（性质3）：对于任何一棵二叉树，如果其叶结点数为N0(N0表示度为0的点也就是叶子结点),而度为2的结点为N2，则N0=N2+1，
假设度为0的点数量为x，则度为2的点数量为x-1，
当度为1的点有1个时，则 x+x-1+1 = 2N-1，解得x=N- 1/2 （因为结点必须为整数，所以答案错误）
当度为1的点有0个时，则 x+x-1+0 = 2N-1，解得 x= N；（符合题意）

思路二：（不要作为依据）
结点总数为偶数时：叶结点数=结点总数/2
结点总数为奇数时：叶结点数=(结点总数+1)/2
如果2N-1为偶数，则（2N-1 ）/2 的结果N-1/2 ，如果结果要为整数，则N必须是分数
如果2N-1为奇数，则（（2N-1）+1）/2 的结果为N，结果为整数。

完全二叉树具有如下特性：
除了最后一层外，其他层的节点数都达到最大。
最后一层的节点都集中在左边。

考虑一个完全二叉树，如果我们从最顶层开始数，第i层（i从1开始）最多有2^(i-1)个节点。因此，从第1层到第N-1层（共N-1层），最多有：
$2^0+2^1+...+2^{N-2}=2^{N-1}-1$
这个数表示了除了最后一层之外的所有节点数。
由于总共有2*N - 1个节点，所以最后一层（第N层）的节点数为：
$(2\ast N-1)-(2^{N-1}-1)=N$
因此，叶节点数（都在第N层）为N。

6、在以下各项中，（ ）不是操作系统软件。

A. Solaris      
B. Linux       
C. Windows Vista         
D. Sybase

正确答案: D
A.Solaris 是Sun Microsystems研发的计算机操作系统。它被认为是UNIX操作系统的衍生版本之一。 Solaris仍旧属于私有软件。2005年6月14日，Sun公司将正在开发中的Solaris 11的源代码以CDDL许可开放，这一开放版本就是OpenSolaris。
B.linux 是一款开源操作系统,世界范围内应用非常广，很多服务器系统都是基于linux的
C.windows vista 是微软公司旗下的一款操作系统，生命周期比较短
D.美国Sybase公司研制的一种关系型数据库系统，是一种典型的UNIX或WindowsNT平台上客户机/服务器环境下的大型数据库系统。

7、设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）

A. 6           
B. 5           
C. 4            
D. 3

正确答案: C
栈是一种先进后出的数据结构。进栈顺序是a,b,c,d,e,f。过程如下

操作	栈内	栈外
a进栈	a	空
b进栈	ab	空
b出栈	a	b
c进栈	ac	b
d进栈	acd	b
d出栈	ac	bd
e进栈	ace	bd
f进栈	acef	bd
f出栈	ace	bdf
e出栈	ac	bdfe
c出栈	a	bdfec
a出栈	空	bdfeca

可以看出，栈内最多容纳4个元素。

8、与十进制数28.5625相等的四进制数是（ ）

A. 123.21       
B. 131.22        
C. 130.22       
D. 130.21

正确答案: D
整数部分（除n取余法）：
28/4 = 7 余 0
7/4 = 1 余3
1/4= 0余1
小数部分（乘n取整法）：
0.5625 * 4 = 2.25 整数部分是2
0.25 *4 =1.00 整数部分是1
所以结果是：130.21 (整数部分倒序，小数部分正序)

9、设字符串S=”Olympic”，S的非空子串的数目是（ ）

A. 28     
B. 29       
C. 16            
D. 17

正确答案: A
1个字符的子串（7个）:”O” “l” “y” “m” “p” “i” “c”,
2个字符（6个）：”Ol” “ly” “ym” “mp” “pi” “ic”.
… …
6个字符（2个）：“Olympi” “lympic”
7个字符（1个）:Olympic
所以：共有7+6+5+4+3+2+1=28

方法2：字串公式： n(n+1)/2 +1 。n表示你字符串的长度。最后一个加1表示加的是空串，这个题说非空字串，那么就是n(n+1) /2 结果是28

10、Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（ ）是典型的Web2.0应用。

A. Sina         
B. Flickr          
C. Yahoo            
D. Google

正确答案: B
Web2.0 确实强调用户的互动和分享，与此相关的网站通常提供用户生成内容、社交媒体互动、在线协作等功能。在给出的选项中，我们可以分析每个网站的特点来确定哪个是典型的 Web2.0 应用。

A. Sina（新浪）: 新浪是中国的一个主要门户网站，它提供了新闻、博客、微博等多种服务。尤其是新浪微博，它允许用户发布状态、分享信息、互动评论，这体现了 Web2.0 的互动与分享特性。

B. Flickr: Flickr 是一个图片分享网站，用户可以在上面上传、分享和管理自己的照片。它也允许用户对照片进行标注、评论和分享，这同样是 Web2.0 应用的典型特征。

C. Yahoo（雅虎）: 雅虎是一个早期的门户网站，虽然它现在也提供了搜索、新闻、邮件等多种服务，但它并没有像新浪微博或 Flickr 那样突出用户的互动和分享。

D. Google（谷歌）: 谷歌主要提供搜索、广告、邮件等服务。虽然它有像 Google+ 这样的社交服务，但相比新浪微博和 Flickr，它的社交和分享功能并不那么突出。

11、递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。

 A. 队列
 B. 多维数组
 C. 线性表
 D. 栈

正确答案: D
在递归过程或函数调用时，处理参数和返回地址通常使用的数据结构是栈。这是因为函数调用遵循后进先出（LIFO）的原则，当一个函数被调用时，它的参数、返回地址以及局部变量等信息被压入栈中。当函数执行完毕后，这些信息会从栈中弹出，控制权返回到调用该函数的位置。

在函数调用过程中形成嵌套时，则应使最后被调用的函数最先返回，递归函数执行时也是如此。例如，用递归方式求4的阶乘(以f(n)表示求n的阶乘)的过程如下所示：
f(4)=4f(3)
=4(3f(2))
=4(3*(2f(1)))
=4(3*(21)
=4(32)
=46
=24
显然，要求4的阶乘，需要通过递归调用求出3的阶乘，要求出3的阶乘，必须先求出2的阶乘，依此类推，求出1的阶乘后才能得到2的阶乘，然后才能得到3和4的阶乘。该求解过程中的函数调用和返回需要满足后调用先返回的特点，因此需要使用栈结构。

12、(2008)10 + (5B)16的结果是（ ）。

A.(833)16
B.(2089)10
C.(4163)8
D.(100001100011)2

正确答案: A
为了计算(2008)10 + (5B)16的结果，我们首先需要把两个数都转换为相同的数制，然后进行相加。这里，我们可以选择将它们都转换为十进制数，或者将其中一个转换为另一个的数制。

首先，我们转换(5B)16为十进制数：
(5B)16 = 5 × 16^1 + B × 16^0
= 5 × 16 + 11 × 1
= 80 + 11
= 91
现在，我们有两个十进制数：(2008)10 和 (91)10。将它们相加：
(2008)10 + (91)10 = 2008 + 91 = 2099

接下来，我们将结果(2099)10转换回十六进制以匹配选项：
2099 / 16 = 131 … 3
131 / 16 = 8 … 3
所以，(2099)10 = (833)16。
因此，(2008)10 + (5B)16的结果是(833)16。

13、二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。

A. 4 2 5 7 6 3 1           
B. 4 2 7 5 6 3 1 
C. 7 4 2 5 6 3 1           
D. 4 2 7 6 5 3 1

正确答案: B
先根（序）遍历：根结点、左子树、右子树。
中根（序）遍历：左子树，根结点，右子树。
后跟（序）遍历：左子树，右子树，根结点。
先画出出二叉树（可以尝试补0）：
①首先看先根遍历的 1 2 4 ，和中根遍历的2 4 1，说明1 是根结点，2 4 都是是左子树的一部分，剩余都是右子树一部分；
②再看先序的2 4 ，然后中根遍历 2 4 1，已知1是根结点，所以2是下面一层的根节点，4是2的右子树（图1）；
③再看先跟3 5 7 6 和中根5 7 3 6，说明3是右子树的根节点，5 7 是左子树，6是右子树（图2）
④看先序遍历 5 7 和中序遍历5 7 ，说明5是根结点，7是右子树（图3）

14、将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。

A. 4            
B. 5           
C. 6            
D. 7

正确答案: B
(每次从后面（未排好序的元素）选取最大的元素进行交换)
第一次交换8 和100 ：100 23 4 16 77 -5 53 8
第二次交换23和77： 100 77 4 16 23 -5 53 8
第三次交换4和53： 100 77 53 16 23 -5 4 8
第四次交换16和23：100 77 53 23 16 -5 4 8
第五次交换-5和8：100 77 53 23 16 8 4 -5

15、对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）

A. 1            
B. 2           
C. 3             
D. 4

正确答案: B
所谓二分查找通俗来讲就是一分为2，对半查找。
第一次中间值是56，没有找到然后分成两部分（5，13，19，21，37）和（64，75，88，92，100）。
然后对左半部分进行二分查找，中间值是19，查找成功，一共2次

16、面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（ ）

A. 面向对象程序设计通常采用自顶向下设计方法进行设计。
B. 面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。
C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C++、JAVA、C#等。
D. 面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk语言仍然被视为面向对象语言的基础。

正确答案: A
程序设计的方法包括：结构化设计和面向对象设计方法。
不能说与面向对象相反的是什么，只能说结构化是不同于面向对象的设计方法.
C和pascal都是结构化的设计方法。
C++是面向对象设计方法。
在结构化程序设计中采用的是自顶向下、逐步求精的方法。可以说，是大问题化成小问题，逐个求解。
面向对象的三大特点：继承、封装、多态
C语言是面向过程的语言，C++、JAVA，C#等是面向对象的语言
Smalltalk是面向对象语言的基础。

17、在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（ ）

A. 512          
B. 256         
C. 384          
D. 128

正确答案: B
在32×32点阵的字库中，每个汉字由32行和32列的点组成。
每个点需要一个二进制位（bit）来表示，即0表示该点不存在，1表示该点存在。
因此，每个汉字的字模占用32位×32行 = 1024位。
但是，通常计算机存储单位以字节（Byte）为单位，1字节 = 8位（bit）。
所以，每个汉字的字模需要1024位 ÷ 8 = 128字节。
对于“北”和“京”两个字来说，它们的字模占用字节数之和就是128字节 + 128字节 = 256字节。

18、设T是一棵有n个顶点的树，下列说法不正确的是（ ）

A. T有n条边                     
B. T是连通的
C. T是无环的                     
D. T有n-1条边

正确答案: A
树是一种特殊的无向图，具有以下性质：
1.树是连通的，即任意两个顶点之间都存在一条路径。
2.树是无环的，即树中不存在环。
3.树有n个顶点，则它必定有n-1条边。

根据这些性质，我们可以分析给定的选项：
A. T有n条边 - 这个说法是不正确的。一棵树如果有n个顶点，那么它应该只有n-1条边。
B. T是连通的 - 这个说法是正确的，因为树是连通的。
C. T是无环的 - 这个说法是正确的，因为树是无环的。
D. T有n-1条边 - 这个说法是正确的，因为一棵树如果有n个顶点，那么它应该只有n-1条边。

19、下列不属于NOIP竞赛推荐使用的语言环境的是（ ）。

A. Dev-C++     
B. Visual C++     
C. free pascal      
D.Lazarus

正确答案: B
A. Dev-C++ - 这是一个流行的、免费的C++集成开发环境（IDE），经常被用于学习和竞赛编程。
B. Visual C++ - 这是微软的一个C++开发环境，虽然它功能强大，但它通常不是NOIP竞赛推荐使用的环境，因为Visual C++更多的是一个面向专业开发者的工具，而不是一个轻量级、易于学习和使用的环境。
C. Free Pascal - Pascal是一种教学常用的编程语言，Free Pascal是其一个开源的实现，适用于竞赛编程。
D. Lazarus - Lazarus是一个免费的Pascal编程环境，它基于Free Pascal，也适用于竞赛编程。

20、在C++程序中，表达式200|10的值是（ ）

A. 20         
B. 1            
C. 220         
D. 202

正确答案: D
| 符号表示按位或（bitwise OR）运算。这个运算符对两个数的二进制表示进行操作，
只要两个数中的至少一个的某一位是1，那么结果的该位就是1。

现在，让我们计算表达式 200 | 10 的值。
首先，我们需要将这两个数转换为二进制形式：
200 的二进制是 11001000
10 的二进制是 00001010
11001000 (200)
00001010 (10)
11001010
11001010 在十进制中等于 202

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

1、书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_________种。满足 A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有______种摆法。

正确答案: 12 4
首先，考虑所有黑皮的书都排在一起的摆法。
由于C和D是黑皮的，我们可以先将它们看作一个整体，记作一个’单元’。这样，我们就有3个’单元’：A、B（红皮）和CD（黑皮）。
这3个’单元’的排列方式有3!（3的阶乘）种，即3 × 2 × 1 = 6种。
但是，C和D之间也有2种排列方式（C在D左边或D在C左边），所以总的摆法是6 × 2 = 12种。
接下来，考虑A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起的摆法。
首先，将A和B看作一个整体（红皮单元），C和D看作一个整体（黑皮单元）。
现在，我们有2个’单元’：红皮单元和黑皮单元。红皮单元必须在黑皮单元的左边，所以只有1种排列方式。
但是，红皮单元内部（A和B）有2!（2的阶乘）种排列方式，即2 × 1 = 2种。同样，黑皮单元内部（C和D）也有2!种排列方式，即2 × 1 = 2种。
因此，总的摆法是1 × 2 × 2 = 4种。

2、有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为( )。

	城市1	城市2	城市3	城市4	城市5	城市6
城市1	0	2	3	1	12	15
城市2	2	0	2	5	3	12
城市3	3	2	0	3	6	5
城市4	1	5	3	0	7	9
城市5	12	3	6	7	0	2
城市6	15	12	5	9	2	0

正确答案: 7
方法一:
根据已知的距离矩阵，城市1到城市6的直接距离是15。然而，我们需要找到的是通过其他城市作为中转站的最短路径。
通过检查每一对顶点，我们可以发现以下路径：
城市1 → 城市2 → 城市5 → 城市6
这条路径的总距离是：
城市1到城市2的距离：2
城市2到城市5的距离：3
城市5到城市6的距离：2
总距离 = 2 + 3 + 2 = 7
因此，城市1到城市6的最短距离确实是7。

方法二:
图论中的最短路径问题，使用Dijkstra算法，
【1】不断运行广度优先算法找可见点，计算可见点到源点的距离长度
【2】从当前已知的路径中选择长度最短的将其顶点加入S作为确定找到的最短路径的顶点。
7(1->2->5->6)

节点 ① ② ③ ④ ⑤ ⑥
是否标记 F F F F F F
距离 0 0 0 0 0 0
第一步，选取开始节点①。标记为T，同时扩展与①节点有联系的节点。
节点 ① ② ③ ④ ⑤ ⑥
是否标记 T F F F F F
距离 0 2 3 1 12 15
第二步，选取当前未被扩展的距离最小的节点④，扩展和④相关的所有节点。
节点 ① ② ③ ④ ⑤ ⑥
是否标记 T F F T F F
距离 0 2 3 1 8 10
说明：节点④到节点②的距离是1+5大于原来的2，所以不修改。
节点④到节点⑤的距离是1+7小于原来的12，所以修改。
依次类推。
第三步, 选取当前未被扩展的距离最小的节点②，扩展和②相关的所有节点。
节点 ① ② ③ ④ ⑤ ⑥
是否标记 T T F T F F
距离 0 2 3 1 5 10
第四步, 选取当前未被扩展的距离最小的节点③，扩展和②相关的所有节点。
节点 ① ② ③ ④ ⑤ ⑥
是否标记 T T T T F F
距离 0 2 3 1 5 8
第五步, 选取当前未被扩展的距离最小的节点⑤，扩展和⑤相关的所有节点。
节点 ① ② ③ ④ ⑤ ⑥
是否标记 T T T T T F
距离 0 2 3 1 5 7
结果到达⑥，最小距离就是7.

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

1、阅读程序写结果:

#include<iostream>
using namespace std;
int main(){
	int i, a, b, c, d, f[4];
	for(i = 0; i < 4; i++) cin >> f[i];
	a = f[0] + f[1] + f[2] + f[3];
	a = a / f[0];
	b = f[0] + f[2] + f[3];
	b = b / a;
	c = (b * f[1] + a) / f[2];
	d = f[(b / c ) % 4];
	if(f[(a + b + c + d) % 4] > f[2])
		cout << a + b<< endl;
	else 
		cout << c + d << endl;
	return 0;
}

输入: 9 19 29 39
输出: ________

正确答案: 23
f[4] = {9,19,29,39}
a = 9 + 19 + 29 + 39 = 96
a = 96 / 9 = 10
b = 9 + 29 + 39 = 77
b = 77 / 10 = 7
c = (7 * 19 + 10) / 29 = 4
d = f[1] = 19
f[(a + b + c + d) % 4] > f[2]
f[(10 + 7 + 4 + 19) % 4] > f[2]
f[0] > f[2] —> false
c + d = 23

2、阅读程序写结果:

#include<iostream>
using namespace std;
void foo(int a, int b, int c){
    if(a > b) 
        foo(c, a, b);
    else
        cout<<a<<','<<b<<','<<c<<endl;
}
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    foo(a, b, c);
    return 0;
}

输入: 3 1 2
输出: ____

正确答案: 2,3,1
该程序是一个递归函数foo，它接受三个整数参数a、b和c。函数的目的是输出这三个数的升序排列。
函数foo的工作流程如下：
如果a大于b，则递归调用foo(c, a, b)。
否则，输出a、b和c的值（以逗号分隔）。
现在，让我们分析给定的输入：3 1 2。
初始调用：foo(3, 1, 2)
因为3 > 1，所以递归调用foo(2, 3, 1)
递归调用1：foo(2, 3, 1)
因为2 < 3，所以输出2,3,1
因此，输出结果是：2,3,1。

3、阅读程序写结果:

#include <iostream>
using namespace std;
void func(int ary[], int n ){
    int i=0, j, x;
    j=n-1;
    while(i<j){
        while (i<j&&ary[i]>0) i++;
        while (i<j&&ary[j]<0) j--;
        if (i<j){
            x=ary[i];
            ary[i++]=ary[j];
            ary[j--]=x;
        }
    }
}
int main(){
    int a[20], i, m;
    m=10;
    for(i=0; i<m; i++){
        cin>>a[i];
    }
    func(a, m);
    for (i=0; i<m; i++)
        cout<<a[i]<<" ";
    cout<< endl;
    return 0;
}

输入: 5 4 -6 -11 6 -59 22 -6 1 10
输出: ____

正确答案: 5 4 10 1 6 22 -59 -6 -11 -6
稍微复杂一点的函数调用，通过不断的给a数组赋值更新a数组的内容，比较坑的一点是ary[i++]和ary[j–]
这两个操作，a[i++] 其值等同于a[i]，然后i再自增1。 如果写a[++i],则是i先自增1再对a数组赋值。
x=ary[i];
ary[i++]=ary[j];
ary[j–]=x;
这三行代码的意思就是 交换a[i]和a[j]的值，然后i++ ,j—
PS:如果学过排序算法的话，可以想想快排的部分。那么这道题就比较简单了。如果看不透此题思想，手动模拟出错的概率很大。

4、阅读程序写结果:

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m){
    int i, root_m;
    if(spos_f > epos_f)
        return;
    for(i = spos_m; i <= epos_m; i++)
        if(first[spos_f] == mid[i]){
            root_m = i;
            break;
        }
    solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
    solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
    cout << first[spos_f];
}
int main(){
    char first[MAX], mid[MAX];
    int len;
    cin >> len;
    cin >> first >> mid;
    solve(first, 0, len - 1, mid , 0, len - 1);    
    cout << endl;
    return 0;
}

输入：
7
ABDCEGF
BDAGECF
输出: ________

正确答案: DBGEFCA

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

1、（字符串替换）给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S’由26个字母组成，它是a-z的任一排列，大小写不定，S’规定了每个字母对应的替换字母：S’中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S’中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换；…… 以此类推。

#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule(){
    int i;
    for (i = 0;i < 26;i++){
        if (  ①  )
               change[i] -= 'A' - 'a';  //
    }
}
void ChangeString(){
    int i;
    for (i = 0;i <strlen(str);i ++){
          if (  ②  )
                str[i] = change[str[i] - 'A'] -'a' + 'A'; 
          else
                 ③ 
    }
}
int main(){
	int i;
	cin >> str ;
    cin >> change;
    CheckChangeRule();
     ④
    cout << str << endl;
    return 0;
}

正确答案：
1.change[i] >= ‘A’ && change[i] <= ‘Z’ / change[i] <= ‘Z’
2.str[i] >= ‘A’ && str[i] <= ‘Z’ / str[i] <= ‘Z’
3.str[i] = change[str[i] - ‘a’];
4.ChangeString();

在CheckChangeRule函数中，我们遍历change字符串，如果某个字符是大写字母，则将其转换为小写字母。这是为了处理str中的小写字母替换。
在ChangeString函数中，我们遍历str字符串，根据每个字符是大写还是小写，使用对应的change规则进行替换。
在main函数中，我们首先读入str和change字符串，然后调用CheckChangeRule和ChangeString函数进行替换操作，最后输出替换后的str字符串。

1.根据上面函数的名字，可以猜想这个函数的目的是检查转换规则，下面的代码是 ‘A’是64，‘a‘是97，Change[i] -= -32 实际上就是 change[i] +=32 也就是将大写字母转换成小写字母，所以上面的if是检查是否是大写字母 。
2.根据下面的代码是将把无规律的ASCII码转换为字母对应的顺序(字母表顺序)（例如：设str[i]装的字符是A,则str[i]的值就为64，即64-64=0，变成了change[0]。），再由-‘a’+’A’得，str[i]=change[str[i]-‘A’]-32；（由题知，被替换的字母如果是大写字母，则替换字母也为大写字母）所以②处应该填判断大写字母
3.如果为小写字母，则不需要转换
4.main函数中少了一个函数调用，所以这里填写函数调用

2、（找第 k 大的数） 给定一个长度为 $10^6$的无序正整数序列, 以及另一个数$n(1<=n<=10^6)$, 然后以类似快速排序的方法找到序列中第n大的数（关于第n 大的数：例如序列 {1,2,3,4,5,6}中第 3 大的数是4）

#include <iostream>
using namespace std;

int a[1000001],n,ans = -1;
void swap(int &a,int &b){
    int c;
    c = a; a = b;    b = c;
}

int FindKth(int left, int right, int n){
    int tmp,value,i,j;
    if (left == right) return left;
    tmp = rand()% (right - left) + left;
    swap(a[tmp],a[left]);
    value =[       ①       ];
    i = left;
    j = right;
    while (i < j){
        while (i < j && [       ②       ]) j --;
        if (i < j) {a[i] = a[j]; i ++;} else break;
        while (i < j && [       ③     ]) i ++;
        if (i < j) {a[j] = a[i]; j - -;} else break;
    }
    [      ④       ]  
    if (i < n) return  FindKth([         ⑤        ] );
    if (i > n) return [         ⑥           ]        
    return i;
}

int main(){
    int i;
    int m = 1000000;
    for (i = 1;i <= m;i ++)
        cin >> a[i];
    cin >> n;
    ans = FindKth(1,m,n);
    cout << a[ans];
    return 0;
}

正确答案:
1.a[left]
2.a[j]<value / a[j]<=value / value>a[j] / value>=a[j]
3.a[i]>value / a[i]>=value
4.a[i]=value;
5.i+1,right,n
6.FindKth(left,i-1,n);

1.快排的思想，找一个基准，然后剩余的数跟基准比较，比基准大的往右放，比基准小的往左放，这里是用value作为基准
2.快排思想，找到一个比基准大的数，并把它放到左侧，因为题目中说的是找第K大的数，所以是从大到小排列，比基准大的要放到左侧。
3.找到一个比基准小的值，放到基准右侧
4.将value值赋值给a[i]
5.递归调用，重新划分区间
6.递归调用，重新划分区间