中小学信息学奥赛CSP-J认证 CCF非专业级别软件能力认证-入门组初赛模拟题第三套（阅读程序题）

CSP-J入门组初赛模拟题第三套

二、阅读程序题

(程序输入不超过数组或字符串定义的范围，判断题正确填√错误填X;除特殊说明外，判断题 1.5分，选择题3分，共计40分)

第一题

1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int i,j,n;
5 int x[101],y[101];
6 int main ()
7 {
8	cin>>n;
9	for(i=1;i<=n;i++)cin>>x[i];
10	for(i=1;i<=n-1;i++)
11		for(j=i+1;j<=n;j++)
12			if( x[i]>x[j])
13				y[j]++;
14			else if(x[i]<x[j])
15				y[i]++;
16	for(i=1;i<=n;i++)
17		printf("%5d ",y[i]);
18	cout<<endl;
19	return 0;
20}

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力，此程序主要是实现了一个计数排序的算法。先输入一个整数n，表示接下来要输入n个整数，然后依次将这n个整数存入数组x中。然后使用两个嵌套的循环遍历数组x，比较x[i]和x[j]的大小，如果x[i]>x[j]，则y[j]的值加1，表示在x[j]后面有多少个数比它小；如果x[i]<x[j]，则y[i]的值加1，表示在x[i]后面有多少个数比它大。最后输出数组y中的元素。

判断题

1)、把第13行与第15 行互换位置,结果不会改变

2)、第14 行把 if( x[i]<x[j])删掉效果一样。

3)、第11行把i+1改成1,数组y每个元素的值增加1倍。

4)、数组y[i]中存的是x[i]在数列中从大到小的次序

答案：1 × 2 × 3 √ 4 ×

答案分析：

1、y数组中记录的是大于当前元素的个数，如果交换结果就反了，所以错误

2、删掉效果不一样，因为还有相等的情况，所以错误

3、如果改成1，比较过的数据会在下次数据进行比较时候重复计算

4、y数组中只记录了比当前索引对应元素大的次数，但是最后并没有进行排序，所以严格来说错误

单选题

5)、此程序的时间复杂度是

A、 $O(\log_{2}n)$

B、 $O(n\log_{2}n)$

C、 $O(n^{2})$

D、 $O(n)$

答案：C

答案分析：因为程序中有一个嵌套for循环，所以是n的平方，所以答案C

6)、此程序如果n输入4,然后输人2 4 1 3,输出结果是

A、1 2 3 4

B、2 0 3 1

C、4 3 2 1

D、1 3 0 2

答案：B

答案分析：根据程序分析可以得出y数组中存的是比当前索引对应元素大的个数，比2大的又4和3，也就是2，所以答案B

第二题

1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int n,i,x;
5 int d[11];
6 int main()
7 {
8	cin>>n;
9	for(i=1;i<=n;i++)
10	{
11		cin>>x;
12		d[x]=d[x]+1;
13	}
14	d[0]=0;
15	for(i=1;i<=10;i++)
16		d[i]=d[i-1]+d[i];
17	for(i=1;i<=10;i++)
18		if(d[i]!=d[i-1])
19			printf("%3d:%4d_",i,d[i-1]+1);
20	return 0;
21}

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力，此程序是一个统计输入数字出现次数的程序。

主要思路：

输入一个数字n，表示接下来要输入n个数字；
用数组d[11]来记录每个数字出现的次数，数组下标表示数字，数组值表示该数字出现的次数；
循环n次，输入每个数字x，并将d[x]的值加1；
初始化d[0]=0；
循环10次（i从1到10），将d[i]的值更新为d[i-1]+d[i]，即将前i个数字出现的总次数存储在d[i]中；
再次循环10次，如果d[i]不等于d[i-1]，则输出i和d[i-1]+1

判断题

1)、输入x的只应在[0,n-1]的范围内

2)、把第12行改成“d[x]++”,不影响程序运行结果

3)、对任意在[1,9]之间的数i,都有 d[i-1]<d[i]<d[i+1]

4)、把第18行改成“if(d[i]>d[i-1])”,程序运行的结果会发生改变

答案：1 × 2 √ 3 × 4 ×

答案分析：

1、从程序中可以看出d数组是一个全局数组，大小为11，所以能接受的范围应该是[0-10]，所以错误

2、d[x]++和12行d[x]=d[x]+1 在这里是等价的，所以正确

3、当某个数没有输入的时候，这时候d数组对应的这个下标的值和前一个是一样的

4、d数组中存的数前一个数要么是小于后一个数要么是一样大，所以改成大于是可以的，结果不变

单选题

5)、输人n=10后,接着输人:1 3 4 3 5 2 4 3 5 2后,程序输出结果为

A、1:1 2:2 3:3 4:2 5:3

B、1:1 2:2 3:4 4:7 5:9

C、1:0 2:1 3:2 4:1 5:2

D、1:1 2:2 3:3 4:4 5:5

答案：B

答案分析：从程序分析可以得出，前一个是对应的数字i，后一个是比数字i小的数字出现的次数累加，具体分析如下：

当i=1，输出的是d[0]+1，d[0]=0，所以输出1；

i=2，输出的是d[1]+1，而d[1]=d[0]+1出现的次数=0+1=1，所以输出2；

i=3，输出的是d[2]+1，而d[2]=d[1]+2出现的次数=2+2=4，所以输出4；

所以答案B

6)、把程序第19行改成“print("%3d",i);"后,输人n=10后,接着输人:1 3 4 1 5 4 4 3 5 1后,程序输出结果为

A、1 2 3 4 5

B、3 2 3 2

C、4 3 4 3

D、1 3 4 5

答案：D

答案分析：改成上面输出语句后，由于输入数字里面没有数字2，所以数组d[2]=d[1]，2就不会输出，所以答案D

第三题

1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int j,i,m;
5 int a[10];
6 int main()
7 {
8	for(i=2;i<=6;i++)
9		a[i]=i+1;
10	do
11	{
12		m=2;
13		for(i=3;i<=6;i++)
14			if(a[m]>a[i])m=i;
15		a[m]=a[m]+m;
16		m=1;
17		
18		for(i=2;i<=5;i++)
19			for(j=i+1;j<=6;j++)
20				if(a[i]<a[j])m=0;
21	}while(m==0);
22	printf("%d",a[2]);
23	return 0;
24}