5.阅读程序和完善程序概述
1 

从本章开始,本书分析考试的后两道大题:阅读程序和完善程序。阅读程序一共有
3大题,共40 分,是CSP-J/S考试中的一大拉分点。该题首先让考生阅读程序,然后利用判
断题和选择题考查考生对程序的理解深度。本题所考查的知识点非常多,主要包括计算机
语言、多重循环的嵌套、数组的操作等。对于阅读程序题,考生一定要细心,程序从主函数
main开始顺序执行,要注意循环的判断条件以及程序的输入和输出细节。

完善程序一共2有大题,共30 分。完善程序题将程序的核心部分空出一些空格,让考
生从四个选项中选出正确的答案补充完全整个程序。该题型一般都会告诉考生程序要完成
的功能,考查考生对于各类算法的设计思路、实现过程等具体步骤。要想补充完善程序,首
要点就是弄清楚程序实现的思路和方法,然后具体了解程序实现的细节。

5.常用解题方法
2 

阅读程序题和完善程序题主要考查考生以下几个方面的能力: 

.程序设计语言的掌握情况; 
.程序中基本算法的掌握情况; 
.数学的知识面及运算能力; 
.细心、耐心的计算思维
。
该部分的解题也是有规律可循的,本书主要总结了以下两种解题方法
。
2. 
模拟法
5.1 
在CSP-J/S的阅读程序题中,当考生无法得知程序所要完成的功能时,最简单且最有
效的方法就是“模拟法”。所谓“模拟法”就是利用人脑模拟程序的执行过程,只要题目不是
很复杂,这种方法就比较奏效。但在模拟过程中,要特别注意各个变量变化时书写的认真和
整洁,因为一个变量的计算错误就会引起整个程序结果的错误。

当程序涉及数组、循环、双重循环、递归调用等稍微复杂的语句时,这些过程模拟往往涉
及较多的变量变化,稍不留神就可能会导致整个程序的错误。为了让整个过程整洁有序,从
而快速发现程序的运行规律,设计表格以进一步模拟是非常有必要的。


1 20 
案例5-1 模拟法演示(1) 
1 #include <iostream> 
2 using namespace std; 
3 int main() 
4 { 
5 int a, b, u, i, num; 
6 cin>>a>>b>>u; 
7 num =0; 
8 for (i =a; i <=b; i++) 
9 if ((i*i %u) ==1) 
10 num++; 
11 cout<<num<<endl; 
12 return 0; 
13 } 
【分析】 该题通过观察很难找出功能说明,但程序并不复杂,可以直接使用模拟法。模
拟法的一般思路为:首先将程序涉及的变量和表达式列举出来,然后从main函数的第一句
开始,利用人脑“模拟”程序的执行,一边执行一边记录变量和表达式值的变化,直至找到规
律或程序执行结束。该题的模拟过程如表5-1所示。
表5-1 案例5-1模拟过程
序号a b u num i i*i% u 备 注
1 3 10 8 0 初始化 
2 1 3 1 开始循环
3 1 4 0 
4 2 5 1 
5 2 6 4 
6 3 7 1 
7 3 8 0 
8 4 9 1 
9 4 10 4 结束循环 
案例5-2 模拟法演示(2) 
1 #include<cstdio> 
2 using namespace std; 
3 int n; 
4 int a[100]; 
5 int main(){ 
6 scanf("%d",&n); 
7 for(int i=1;i<=n;++i){ 
8 scanf("%d",&a[i]);

1 21 
9 } 
10 int ans=1; 
11 for(int i=1;i<=n;++i){ 
12 if(i>1&&a[i]<a[i-1]) 
13 ans=i; 
14 while(ans<n && a[i]>=a[ans+1]) 
15 ++ans; 
16 printf("%d ",ans); 
17 } 
18 printf("\n"); 
19 return 0; 
20 } 
. 判断题
(1)第16行输出ans时,ans的值一定大于i。( ) 
(2)程序输出的ans小于或等于n。( ) 
(3)若将12行的“<”改为“! =”,则程序的输出结果不会改变。( ) 
(4)当程序执行到第16行时,若ans-i>2,则a[i+1]<=a[i]。( ) 
. 选择题
(5)若输入的a数组是一个严格单调递增的数列,则此程序的时间复杂度是( )。
A.O(logn) B.O(n2) C.O(nlogn) D. O(n) 
(6)最坏情况下,此程序的时间复杂度是( )。
A.O(n2) B.O(logn) C.O(n) D.O(nlogn) 
【分析】 阅读该题,可以发现程序里面就是数组的操作,直观上看不出程序的功能,这
时需要利用一组数据验证程序的功能,选择数据时,如果题目中有数据,则可以直接选择题
目中的数据;如果题目中没有数据,则根据题目构造一组数据。
本题没有直接给出测试数据,但可以构造一组数据:3213。下面根据这组数据对题
目进行具体分析,如表5-2和表5-3所示。
(1)数据初始化(6~10行)
表5-2 案例5-2数据初始化
变量n a[1] a[2] a[3] ans 
变量值3 2 1 3 1 
(2)数据处理(11~17行) 
表5-3 案例5-2数据处理
变 量i ans a[i] a[i-1] a[ans+1] 输出
变量值1 1 2 1 
2 2 3 2 
2 2 1 2

122 

续表

变量
i 
ans 
a[i] a[i-1] a[ans+1] 输出
2 1 3 2 
3 2 3 1 3 
3 3 

通过数据分析可以得出:整个程序的含义是找到每个a[后第一个大于a[的位置
(注:如果存在, 序号范围为0n1), 
i] 
i] 
i] 
则输出

位置n。
则输出位置序号, ~-如果不存在大于a[的数, 

判断题(1)解析: 

如果12 行的if成立,而14 行的while不成立,则ans的值与i相等。

参考答案:错误。

判断题(2)解析: 

从15 行看,ans<n 才会执行ans++,如果ans==n,则会退出while循环,所以不会

超过n。

参考答案:正确

判断题(3)解析: 

将“<”改成“!=”,多出了一些比较操作,最后结果不受影响。

参考答案:正确

判断题(4)解析: 

过a[
解析:由an-as是第一个大于a[的, i+1] as1]都不会超

i]。
si>2 可见,ni] 所以从a[到a[n

参考答案:正确

选择题(5)解析: 

解析:如果输入数据为单调递增,则12 行的if就不会成立,也就是ans只增不减,所以
时间复杂度为O(n)。

参考答案:D 

选择题(6)解析: 

解析:最坏情况下,12 行的if总是成立(a单调降), 此时14 行也会一直运行到ans=n, 

时间复杂度为n+(n-1)+…+1=O(n2)。
参考答案:A 

5.2 
先猜测、后验证
2.
模拟法虽然奏效,但如果考生对整个程序要完成的功能不理解,则会造成求解的速度很
慢。如果考生知道了程序的功能,那么对阅读程序的效率的提高很大。所以,在阅读程序
中,考生可以借助以前阅读程序的功底以及程序中变量和函数一些常用的写法提示,大胆地
猜测程序的功能,然后再进行验证,这就要求学员在平时学习时一方面要及时总结经典或者


1 23 
常用的功能代码段,另一方面要按照程序设计的经典写法进行书写,以提升自己程序的可
读性。
1.变量的常用含义
搞懂或者猜出变量的含义对于程序的理解至关重要。在变量的定义上,程序员喜欢使
用英语单词或者英语单词的缩写、简写等方式表达变量含义,从而逐渐形成了一些固定的使
用习惯,例如:sum 表示累加求和的结果,count表示累加计数等。表5-4列举了一些常用
的变量使用习惯和含义。
表5-4 程序中常用的变量及其含义
序号变量名英文单词全拼/含义
1 ans answer/计算答案
2 ret return/返回值
3 res result/计算结果
4 flag 标识,多用于记录状态
5 done 完成
6 error 错误,多用于记录错误信息
7 found 找到,多用于bool变量
8 success 成功
9 ok 完成
10 num number/数字
11 value 值
12 cnt count/统计
13 target 目标
14 record 记录
15 foo 确实存在东西的普遍替代语
16 tmp/temp 临时变量
序号变量名英文单词全拼/含义
17 index 索引,多用于数组下标
18 first 第一,多用于比较
19 second 第二,多用于比较
20 last 最后,多用于比较
21 begin 开始,多用于指针位置
22 end 结束,多用于指针位置
23 start 开始,多用于指针位置
24 node 节点,多用于链表
25 op 操作符,多用于链表
26 min 最小值,多用于比较
27 max 最大值,多用于比较
28 avg 平均值,多用于计算
29 total 总和,多用于统计
30 preNode 上一个节点,用于链表
31 curNode 当前节点,用于链表
32 nextNode 下一个节点,用于链表
2.算法的结构
很多常用算法都有一些基本的结构,了解并掌握这些结构不仅能在阅读程序上快速地
判断出程序的功能,而且在今后编写程序上也能根据算法结构快速地写出程序。这里列举
几例,其他结构需要考生在学习过程中整理。
(1)二分算法 
while(l<=r) 
{ 
mid=(l+r)/2 
… 
if(…)

1 24 
l=mid+1; 
else 
r=mid-1; 
}
这里的l代表left,r代表right,mid代表middle。
(2)数据链表 
data[next[i]] 
这里的data数组存储数据域,next数组存储指针域。
(3)变量交换位置 
if(…){ 
t =a[i]; 
a[i]=a[j]; 
a[j]=t; 
}
当满足某一条件时,交换数组中a[i]和a[j]的位置。
(4)将连续数字字符转换成整数 
num=0; 
c =cin.get(); 
while(c>='0'&&c<='9') { 
num=num*10+c-'0'; 
c=cin.get(); 
}
(5)辗转相除求最大公约数 
while(b!=0){ 
temp=b; 
b=a%b; 
a=temp; 
}r
eturn a; 
返回值a就是数值a和b的最大公约数。
下面我们利用该方法实现一个题目。
案例5-3 猜测验证法演示(1) 
1 #include <iostream> 
2 using namespace std; 
3 const int maxn=10000; 
4 int n; 
5 int a[maxn]; 
6 int b[maxn]; 
7 int f(int l,int r,int depth){

1 25 
8 if(l>r) 
9 return 0; 
10 int min=maxn,mink; 
11 for(int i=l;i<=r;++i){ 
12 if(min>a[i]){ 
13 min=a[i]; 
14 mink=i; 
15 } 
16 } 
17 int lres=f(l,mink-1,depth+1); 
18 int rres=f(mink+1,r,depth+1); 
19 return lres+rres+depth*b[mink]; 
20 } 
21 int main(){ 
22 cin >>n; 
23 for(int i=0;i<n;++i) 
24 cin>>a[i]; 
25 for(int i=0;i<n;++i) 
26 cin>>b[i]; 
27 cout<<f(0,n-1,1)<<endl; 
28 return 0; 
29 } 
. 判断题
(1)如果a数组有重复的数字,则程序运行时会发生错误。( ) 
(2)如果b数组全为0,则输出为0。( ) 
. 选择题
(3)当n=100时,最坏情况下,与第12行的比较运算执行的次数最接近的是( )。
A.5000 B .6 00 C. 6 D.100 
(4)当n=100时,最好情况下,与第12行的比较运算执行的次数最接近的是( )。
A.100 B . 6 C. 5000 D.600 
(5)当n=10时,若b数组满足:对任意0≤i<n都有b[i]=i+1,那么输出最大为
( )。
A.386 B . 38 3 D. 385 C.384 
(6)当n=100时,若b数组满足:对任意0≤i<n都有b[i]=1,那么输出最小为
( )。
A.582 B . 580 C. 579 D. 581 
【分析】 阅读该题,可以发现里面有函数的递归调用,根据函数f(intl,intr,int 
depth)参数中l、r、depth这三个单词,很容易联想到二叉树中的左子树left、右子树right和
树的深度depth。由此可大胆推测这是一个有关二叉树的题目。
再根据min变量代表的为最小值,可以推算出mink为数组a中从l到r位置中最小数
值的序号。
最后根据17、18、19三行,可以推算出从l到mink-1构成lres为左子树,从mink+1 
到r构成rres为右子树,返回值lres+rres+depth*b[mink]代表一棵根节点最小的二叉树

各节点深度depth与对应数组b值的加权和。
有了这个分析之后,再根据结果判断题目就会简单很多。下面是对题目的具体解析。
判断题(1)解析: 
对于该题,最直接的方法就是采用验证法。构造一个数组a[]={1,1,1},代入程序运

行一下,会发现程序不会出现错误,而是会优先选择最左侧的那个1进行计算。
参考答案:错误
判断题(2)解析: 
解析:根据返回值的计算公式lres+
res+depth*b[mink],这里的lres和
res分别代

表左子树和右子树的值,其计算需要递归计算,真正影响计算结果的是depth*b[mink],若

数组b全为0,则该项结果必为0,从而加权和的最后结果显然为0
。
参考答案:正
确
选择题(3)解析
:
最坏情况一般都是极端情况,该题很容易发现最坏情况为如下数组
:


a[]={1,2,3,4,5,6,7,…,100}

这种情况下,程序所构造的二叉树的每个节点仅有一个子节点,而程序将递归100层。
第12行的比较运算,第i层需要进行100-i+1次,所以总执行次数为100+99+98+…+ 
1≈5000 。

参考答案:A 
选择题(4)解析: 
跟最坏情况相反,所谓的最佳情况就是在构造二叉树时,每一构造都尽可能均分其左右

子树,这样就可以保证二叉树的深度最小。假设根节点深度为1,则含n=100个节点的树
的深度最小为logn≈7,对于每一层节点,第12行的比较运算,程序总共执行约n次,因此总
执行次数约为nlogn≈600 。

参考答案:
D
选择题(5)解析
:
首先计算出数组b的值为
b[]={1,2,3,4,5,6,7,8,9,10}


要使输出的值最大,就要使得depth*b[mink]最大,也就是程序所构造的二叉树的深
度depth应尽可能地大,这也就是第3题中的最坏情况。定义根节点深度为1,则含10个节
点的二叉树的最大深度为10,因此输出最大值为1×1+2×2+3×3…+10×10=385 。

参考答案:
D
选择题(6)解析
:
首先计算出数组b的值为
b[]={1,1,1,1,1,1,1,1,1,1}


该题要使输出值最小,就要使得depth*b[mink]最小,由于数组b的值都一样,所以只
要使得depth最小就行了。而相同节点,完全二叉树的depth最小,所以本题要构造一棵完
全二叉树,该树中深度为1的节点共1个,深度为2的节点共2个,深度为3的节点共4个
……深度为6的节点共32个,剩余37个节点的深度为7,因此输出最小值为1×1+2×2+ 
3×4…+6×32+7×37=580 。

参考答案:B