阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第7节：搜索算法

第1题【NOIP】2012

#include <iostream>
using namespace std;
int n,i,j,a[100][100];
int solve(int x,int y)
{
    int u,v;
    if(x==n) return a[x][y];
    u=solve(x+1,y);
    v=solve(x+1,y+1);
    if(u>v) return a[x][y]+u;
    else return a[x][y]+v;    
}

int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++) cin>>a[i][j];
    cout<<solve(1,1)<<endl;
    return 0;    
}

●判断题

(1)该程序读入n+n*n个整数。

{{ select(1-1) }}

• 正确
• 错误

(2)该程序能正常运行。

{{ select(1-2) }}

• 正确
• 错误

(3)输出结果均为整数。

{{ select(1-3) }}

• 正确
• 错误

(4)该程序有多组测试。

{{ select(1-4) }}

• 正确
• 错误

●选择题

(5)若输人为：

5
2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8

则结果是()。

{{ select(1-5) }}

• 11
• 12
• 13
• 14

第2题【NOIP】2013

#include <stdio.h>
#include <string.h>
#define SIZE 100
int n, m, p, count;
int a[SIZE][SIZE];

void colour(int x, int y) {
	count++;
	a[x][y] = 1;
	if ((x > 1) && (a[x - 1][y] == 0))colour(x - 1, y);
	if ((y > 1) && (a[x][y - 1] == 0))colour(x, y - 1);
	if ((x < n) && (a[x + 1][y] == 0))colour(x + 1, y);
	if ((y < m) && (a[x][y + 1] == 0))colour(x, y + 1);
}

int main() {
	int i, j, x, y, ans;
18	memset(a, 0, sizeof(a));
	scanf("%d%d%d", &n, &m, &p);
	for (i = 1; i <= p; i++) {
		scanf("%d%d", &x, &y);
		a[x][y] = 1;
	}
	ans = 0;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			if (a[i][j] == 0) {
				count = 0;
				colour(i, j);
30				if (ans < count)ans = count;
			}
	printf("%d", ans);
	return 0;
}

●判断题

(1)由于没有赋初值，该程序会运行错误

{{ select(2-1) }}

• 正确
• 错误

(2)如果将第18行去掉，程序结果会发生改变。

{{ select(2-2) }}

• 正确
• 错误

(3)如果将第30行的ans<cnt改成ans<=cnt,输出结果会发生改变

{{ select(2-3) }}

• 正确
• 错误

(4)该程序有可能输出114514

{{ select(2-4) }}

• 正确
• 错误

●选择题

(5)若输入为：

6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4

则输出结果是( )。

{{ select(2-5) }}

• 114514
• 1919810
• 7
• 8

(6)该程序的时间复杂度为( )。

{{ select(2-6) }}

• O(1)
• O(n)
• O(n*m)
• O($2^n$)