阅读程序2题C++ 求解

Question

1.【NOIP2012】

01 #include <iostream>
02 using namespace std;
03 int n,i,j,a[100][100];
04 int solve(int x,int y) {
05 int u,v;
06 if(x==n) return a[x][y];
07 u=solve(x+1,y);
08 v=solve(x+1,y+1);
09 if(u>v) 
10 return a[x][y]+u;
11 else 
12 return a[x][y]+v;
13 }
14 int main() {
15 cin>>n;
16 for(i=1; i<=n; i++)
17 for(j=1; j<=i; j++) cin>>a[i][j];
18 cout<<solve(1,1)<<endl;
19 return 0;
20 }

判断题
（1）该程序读入 n+n*n 个整数。 （ ）
（2）该程序能正常运行。 （ ）
（3）输出结果均为整数。 （ ）
（4）该程序有多组测试数据。 （ ）
选择题
（5）若输入为：
5
2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8
输入结果为（ ）
 A. 11 B. 12 C. 13 D. 14

2.【NOIP2013】

01 #include <iostream>
02 #include <cstring>
03 using namespace std;
04 const int SIZE = 100
05 int n, m, p, count, a[SIZE][SIZE];
06
07 void colour(int x, int y) {
08 count++;
09 a[x][y] = 1;
10 if ((x > 1) && (a[x - 1][y] == 0)) colour(x - 1, y);
11 if ((y > 1) && (a[x][y - 1] == 0)) colour(x, y - 1);
12 if ((x < n) && (a[x + 1][y] == 0)) colour(x + 1, y);
13 if ((y < m) && (a[x][y + 1] == 0)) colour(x, y + 1);
14 }
15
16 int main() {
17 int i, j, x, y, ans;
18 memset(a, 0, sizeof(a));
19 cin >> n >> m >> p;
20 for (i = 1; i <= p; i++) {
21 cin >> x >> y;
22 a[x][y] = 1;
23 }
24 ans = 0;
25 for (i = 1; i <= n; i++)
26 for (j = 1; j <= m; j++)
27 if (a[i][j] == 0) {
28 count = 0;
29 colour(i, j);
30 if (ans < count) ans = count;
31 }
32 cout << ans << endl;
33 return 0;
34 }

判断题
（1）由于没有赋初值，该程序会运行错误。 （ ）
（2）如果将第 18 行去掉，程序结果会发生改变。 （ ）
（3）如果将第 30 行的 ans<count 改成 ans<=count，输出结果会发生改变。 （ ）
（4）该程序有可能输出 114514。 （ ）
选择题
（5）若输入为：
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
则输出结果为（ ）
 A. 114514 B. 1919810 C. 7 D. 8
（6）该程序的时间复杂度为（ ）
 A. O(1) B. O(n) C. O(n*m) D. O(2n)

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

1. 判断题 （1）错误。程序读入的整数数量为 n+n*(n+1)/2，而不是 n+n*n。 （2）正确。程序能正常运行。 （3）正确。输出结果均为整数。 （4）错误。该程序只有一组测试数据。

选择题 （5）解答过程：根据输入的数据，我们可以画出一个6x5的矩阵，然后按照题目要求进行计算。最后得到的结果为13，所以答案为C。

1. 判断题 （1）错误。程序已经对数组a进行了赋初值操作。 （2）正确。如果将第18行去掉，程序结果会发生改变。 （3）错误。如果将第30行的 ans<count 改成 ans<=count，输出结果不会发生改变。 （4）错误。该程序不可能输出114514。

选择题 （5）解答过程：根据输入的数据，我们可以画出一个6x5的矩阵，然后按照题目要求进行计算。最后得到的结果为7，所以答案为C。

（6）解答过程：该程序的时间复杂度为O(n*m)，因为需要遍历整个矩阵进行计算。所以答案为C。