二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√,错误填×)
16.输入的字符串只能由小写字母或大写字母组成。( )
解析：
背景知识：
ASCII编码：
（American Standard Code for Information Interchange）美国国家信息交换标准字符码。用7个二进制数表示1个字符的字符编码。ASCII一共可以表示128种不同的字符。用户使用计算机时，从标准输入设备键盘输入的各种字符，由计算机自动转换后，以ASCII码的形式输入到计算机中。下图为十进制索引表示的ASCII码字符集：
数组
数组（Array）是一种复合数据类型，它由一系列相同类型的元素（Element）组成，数组中的元素通过下标（或称为索引，Index）来访问。
循环结构
循环结构是指在程序中需要反复执行某个功能而设置的一种程序结构。它由循环体中的条件，判断继续执行某个功能还是退出循环。
C++ 编程语言提供了以下几种循环类型：
知识点分类：
C++程序设计-数组-数组的读入与输出
数学-编码-ASCII码
答案解析：
首先分析下题目所给的代码：
通过代码分析可知，本题程序实现的功能是：输入一个字符串，找到字符串中所在的位置是字符串长度n的因子的所有字符，如果这个位置的字符是小写字母，就把它修改为大写字母。
本题描述：输入的字符串只能由小写字母或大写字母组成。
通过对程序的分析可知：输入的字符串除了可以有小写字母或大写字母以外，还可以有数字、特殊字符等。
所以本题的描述是错误的，应该在括号内打×。
17.若将第8行的“i = 1”改为“i = 0”，程序运行时会发生错误（ ）
解析：
通过代码分析可知，本题程序实现的功能是：输入一个字符串，找到字符串中所在的位置是字符串长度n的因子的所有字符，如果这个位置的字符是小写字母，就把它修改为大写字母。
本题描述：若将第8行的“i = 1”改为“i = 0”，程序运行时会发生错误。
通过对程序的分析可知：如果将第8行的i=1改为i=0，那么第10行的
st[i – 1]就等于st[-1]，会发生数组越界，程序运行会出错。
所以本题的描述是正确的，应该在括号内打√。
18. 若将第8行的“i <= n”改为“i * i <= n”，程序运行结果不会改变。（ ）
答案解析：
通过代码分析可知，本题程序实现的功能是：输入一个字符串，找到字符串中所在的位置是字符串长度n的因子的所有字符，如果这个位置的字符是小写字母，就把它修改为大写字母。
本题描述：若将第8行的“i <= n”改为“i * i <= n”，程序运行结果不会改变。
通过对程序的分析可知：
当第8行的循环条件为“i<=n”时，程序将会对输入的字符串中每一个字符进行比对处理；
而第8行的循环条件改为“i*i<=n”时，程序对输入的字符串的比对范围会缩小，有可能会导致有些符合条件位置的字符没有被处理到，导致程序运行结果改变。
也可以通过运行程序进行验证：
当程序第8行的循环条件为“i<=n”时，输入字符串a0b00c00d
则输出结果为：A0B00c00D
当程序第8行的循环条件为“i*i<=n”时，仍然输入a0b00c00d
而输出结果变为：A0B00c00d
两段程序运行的的结果发生了改变。
所以本题的描述是错误的，应该在括号内打×。
19. 若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（ ）
解析：
通过代码分析可知，本题程序实现的功能是：输入一个字符串，找到字符串中所在的位置是字符串长度n的因子的所有字符，如果这个位置的字符是小写字母，就把它修改为大写字母。
本题描述：若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。
通过对程序的分析可知：本题实现的功能是把输入的字符串中特定位置的小写字母修改为大写字母，如果输入的字符串全部是大写字母，那么程序就不会对字符串进行任何修改，输出的字符串应该和输入的字符串完全一致。
也可以通过运行程序进行验证：
当输入字符串ILOVEIOI时，
输出结果为ILOVEIOI。
输入和输出的结果一致。
所以本题的描述是正确的，应该在括号内打√。
20. 若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比，至多有（ ）个字符不同。
A. 18
B. 6
C. 10
D. 1
解析：
通过代码分析可知，本题程序实现的功能是：输入一个字符串，找到字符串中所在的位置是字符串长度n的因子的所有字符，如果这个位置的字符是小写字母，就把它修改为大写字母。
本题中输入的字符串长度为18。本题程序最多修改的字母个数就是字符串长度n的因子的个数。
而数字18共有1，2，3，6，9，18六个因子，所以输出字符串和输入字符串相比，至多有6个字符不同。
所以本题的正确答案应该选择B。
21.若输入的字符串长度为（ ），那么输入的字符串跟输出的字符串相比，至多有36个字符不同。
A. 36
B. 100000
C. 1
D. 128
解析：
通过代码分析可知，本题程序实现的功能是：输入一个字符串，找到字符串中所在的位置是字符串长度n的因子的所有字符，如果这个位置的字符是小写字母，就把它修改为大写字母。
本题要求输入的字符串跟输出的字符串相比，至多有36个字符不同。通过第20题的分析可知，36即为输入字符串的长度n的因数个数。考试时建议使用排除法：
选项A 36=22*32 因数的个数为（2+1）*(2+1)=9个
选项C 1 因数的个数为1个
选项D 128=27 因数的个数为7+1=8个
这样就可以排除掉A、C、D选项。如果时间充足，可以再验证下：
选项B 100000 =25*55 因数的个数为（5+1）*(5+1)=36个
所以本题的正确答案应该选择B。
22. 当m>0时，输出的值一定小于2n。（ ）
解析：
背景知识：
自增自减运算符
在C++等高级程序设计语言中，自增或自减运算符的作用是在运算结束前（前置自增自减运算符）或运算结束后（后置自增自减运算符）将变量的值加（或减）1。例如：
++i 先使i的值自增1，再使用i的值
– – i 先使i的值自减1，再使用i的值
i++ 使用i的值之后，使i的值自增1
i- – 使用i的值之后，使i的值自减1
数组
数组（Array）是一种复合数据类型，它由一系列相同类型的元素（Element）组成，数组中的元素通过下标（或称为索引，Index）来访问。
循环结构
循环结构是指在程序中需要反复执行某个功能而设置的一种程序结构。它由循环体中的条件，判断继续执行某个功能还是退出循环。
C++ 编程语言提供了以下几种循环类型：
| 循环 类型 | 描述 |
| while循环 | 当给定条件为真时，重复语句 |
| for循环 | 多次执行一个语句 |
| do…while循环 | 除了在循环主体结尾测试条件，其他与while语句类似 |
| 嵌套循环 | 在上述三种循环内使用一个或多个循环 |
知识点分类：
C++程序设计-数组-数组的读入与输出
答案解析：
首先分析下题目所给的代码：
通过代码分析可知，本题程序实现的功能是：程序可以视作通过模拟算法选出一系列互不冲突的数对——若数对(x1,y1)和(x2,y2)之间有x1==x2或y1==y2则认为这两个数对存在冲突。按顺序考虑每一个数对（xi,yi）（要求满足前提：在已经选用的数对中，与左值xi匹配的右值小于yi,、与右值yi匹配的左值小于xi）,若该数对与此前己经选用的数对冲突, 则用当前数对替换所冲突的原数对；若无冲突，则直接选用当前数对。
程序中的 :
a[x]用于记录，在已选用的数对中，与左值x相匹配的右值；
b[y]用于记录，在已选用的数对中，与右值y相匹配的左值；
n表示数对左值和右值的取值范围为[l,n]；
ans用于统计剩余多少左值或右值，没有相应数对被选中。
（引用自：知乎ant攻城狮）
由限定条件0<x,y<=n可知，当m>0时，一定存在某个数对被选中，此时ans<2n
所以本题的描述是正确的，应该在括号内打√。
23. 执行完第27行的”++ans”时，ans —定是偶数。（ ）
解析：
根据代码分析可知：
数对是一个左值与一个右值相匹配，所以第29行输出的变量ans的值一定是偶数。
但是27行的++ans在第23行-28行的for循环内部，其中间结果不一定是偶数（有可能是奇数）。
所以本题的描述是错误的，应该在括号内打×。
24. a［i］和b［i］不可能同时大于0。（ ）
解析：
根据代码分析可知：
a[i]用于记录，在已选用的数对中，与左值x相匹配的右值
若不存在则为0。
b[i]用于记录，在已选用的数对中，与右值y相匹配的左值
若不存在则为0。
当数对（i，y）和（x，i）都被选中时，a[i]和b[i]就会同时大于0。
所以本题的描述是错误的，应该在括号内打×。
25. 右程序执行到第13行时，x总是小于y，那么第15行不会被执行。（ ）
解析：
可以使用代入法进行验证：
分别读入x，y的值为 x=3,y=6 x=3,y=7
满足题目给出的x总是小于y条件，但是15行是可以被执行的。
所以本题的描述是错误的，应该在括号内打×。
26. 若m个x两两不同，且m个y两两不同，则输出的值为（ ）
A. 2n-2m
B. 2n+2
C. 2n-2
D. 2n
根据上边的代码分析可以确定，当输入的数对相互不冲突时，程序会直接选用当前输入的数对。
ans的作用是统计数组中还有几个0（没有被数对选中的值）；
n表示数对左值和右值的取值范围为[1,n]；
由此可知最终的输出结果为2n-2m。
所以本题的正确答案应该选择A。
27. 若m个x两两不同，且m个y都相等，则输出的值为（ ）
A. 2n-2
B. 2n
C. 2m
D. 2n-2m
根据上边的代码分析可以确定，当输入的数对相互存在冲突时，程序只会保留最后一组数对。
ans的作用是统计数组中还有几个0（没有被数对选中的值）；
n表示数对左值和右值的取值范围为[1,n]；
由此可知最终的输出结果为2n-2。
所以本题的正确答案应该选择A
28. 如果a数组有重复的数字，则程序运行时会发生错误。（ ）
解析：
背景知识：
二叉树
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
自增自减运算符在C++等高级程序设计语言中，自增或自减运算符的作用是在运算结束前（前置自增自减运算符）或运算结束后（后置自增自减运算符）将变量的值加（或减）1。例如：++i 先使i的值自增1，再使用i的值– – i 先使i的值自减1，再使用i的值i++ 使用i的值之后，使i的值自增1i- – 使用i的值之后，使i的值自减1
数组
数组（Array）是一种复合数据类型，它由一系列相同类型的元素（Element）组成，数组中的元素通过下标（或称为索引，Index）来访问。
函数定义
返回类型 函数名（[参数列表]）
{
函数体//执行语句
}
包括以下几个部分：
函数名：为函数所起的名字，必须是一个有效的C++标识符，给变量命名的规则同样也适用于给函数命名，但要注意，不可以使用C++的保留字作为函数名。
函数参数：包括形式参数和实际参数。
形式参数是用逗号分隔的变量说明列表，这些变量称为函数的形式参数。形式参数用于接收从函数调用程序传给这个函数的数据。
实际参数是用逗号分隔的表达式列表，其中每一个表达式称为实际参数。在函数调用时，需要将实际参数的值传送给对应位置的形式参数，因此它们两个参数的个数必须相同，而且数据类型也必须匹配。
函数体：函数体是使用花括号{ }限定的语句序列，分为说明部分和语句部分，用于描述这个函数所要执行的操作。说明部分用来对函数中使用的变量和函数作说明。语句部分由基本语句组成，函数的功能由函数体内的各个语句的执行来实现。
函数调用
一个函数被定义后，程序中的其他函数就可以使用这个函数，这个使用的过程就称为函数调用。
函数名（实参列表）；
知识点分类：
C++程序设计-函数与递归
数据结构-简单树
答案解析：
首先分析下题目所给的代码：
通过代码分析可知，本题程序实现的功能是：读取数组中的值建立一棵树，每次递归寻找当前区间的最小值为根，然后再划分左子树和右子树建立下一层。
根据上边的代码分析可以确定，若a数组有重复数字，则程序在根据a数组递归构造符合要求的二叉树时，对于相同结点值，会优先考虑位于左侧的树。可见a数组即使有重复的数字，也不会造成程序出错。
所以本题的描述是错误的，应该在括号内打×。
29. 如果b数组全为0,则输出为0。（ ）
解析：
根据上边的代码分析可以确定，程序最终输出的是各结点深度与b值的加权和；而b 数组是每个节点的value，a 数组是每个节点的key，最后计算的是value*depth的值；如果b 数组全为0，那么输出就一定为0。
所以本题的描述是正确的，应该在括号内打√。
30. 当n=100时，最坏情况下，与第12行的比较运算执行的次数最接近的是：（ ）
A. 5000
B. 600
C. 6
D. 100
根据上边的代码分析可以确定，每一层都要做一次，最坏情况下是一开始有序，每次都是第一个是根， 所以要做100 层， 第一次100 次， 每层次数-1 ，1+2+3+…+100 = 5050
所以本题的正确答案应该选择A。
31. 当n=100时，最好情况下，与第12行的比较运算执行的次数最接近的是：（ ）
A. 100
B. 6
C. 5000
D. 600
在最好的情况下，本题程序构造二叉树时，对于每个结点会尽可能平均分配左右子树，也就是每次都是二分。
如果根结点深度为1，那么包含n=100个结点的树的深度最小为logn≈6，此时每选定一层结点，程序都需要执行约n次的第12行的比较运算，因此总执行次数约为nlogn≈600。
所以本题的正确答案应该选择D。
32. 当n=10时，若b数组满足，对任意0<=i<n,都有b［i］ = i + 1,那么输出最大为（ ）。
A. 386
B. 383
C. 384
D. 385
f函数的返回值为：最小值左边的值+最小值右边的值+深度*当前根的权
程序建立的树深度depth值越大，程序输出的值就更大。
当n=10时，程序建立的树最大深度值为10
而对任意0<=i<n,都有b[i]= i + 1
即b[1]=2,b[2]=3…b[n-1]=n
程序输出的最大值为：
1*1+2*2+3*3+…+10*10=1+4+9+…+100=385
所以本题的正确答案应该选择D。
33. 当n=100时，若b数组满足，对任意0<=i<n,都有b［i］=1,那么输出最小为（ ）。
A. 582
B. 580
C. 579
D. 581
f函数的返回值为：最小值左边的值+最小值右边的值+深度*当前根的权
程序建立的树深度depth值越小，程序输出的值就更小。
因此要让输出的值小，程序应该按照完全二叉树来构建二叉树：
根据下图计算完全二叉树深度的公式可知：
100个节点的完全二叉树深度为7。
深度为1的树，节点有1个；
深度为2的树，节点有2个；
……
深度为6的树，节点有32个；
深度为7的树，最大节点有64个，但本题中只剩37个；
当n=100时，程序建立的树最大深度值为7
而对任意0<=i<n,都有b[i]= i + 1
即b[1]=1,b[2]=2…b[n-1]=n-1
100 个节点的每层节点数量为：
1,2,4,8,16,32,37
对应的权值为：
1,2,3,4,5,6,7
则程序输出的最小值为：
1*1+2*2+3*4+4*8+5*16+6*32+7*37=
1+4+12+32+80+192+259=580
所以本题的正确答案应该选择B。
