阅读程序

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

第9节：树和图

第1题【NOIP】2016

#include <iostream>
#include <cstring>
using namespace std;
int map[100][100];
int sum[100], weight[100];
int visit[100];
int n;
void dfs(int node) {
	visit[node] = 1;
	sum[node] = 1;
	int v, maxw = 0;
	for (v = 1; v <= n; v++)    {
		if (!map[node][v] || visit[v])
			continue;
		dfs(v);
		sum[node] += sum[v];
		if (sum[v] > maxw)
			maxw = sum[v];
	}
	if (n - sum[node] > maxw)
		maxw = n - sum[node];
	weight[node] = maxw;
}
int main() {
25	memset(map, 0, sizeof(map));
26	memset(sum, 0, sizeof(sum));
27	memset(weight, 0, sizeof(weight));
28	memset(visit, 0, sizeof(visit));
	cin >> n;
	int i, x, y;
	for (i = 1; i < n; i++) {
		cin >> x >> y;
		map[x][y] = 1;
		map[y][x] = 1;
	}
	dfs(1);
	int ans = n, ansN = 0;
38	for (i = 1; i <= n; i++)
		if (weight[i] < ans) {
			ans = weight[i];
			ansN = i;
		}
	cout << ansN << " " << ans << endl;
	return 0;
}

●判断题

(1)ansN和ans的值不可能一样。

{{ select(1-1) }}

• 正确
• 错误

(2)25～28行删掉后程序照样输出正常结果。

{{ select(1-2) }}

• 正确
• 错误

(3)本程序的时间复杂度为O(n)。

{{ select(1-3) }}

• 正确
• 错误

(4)38行的i++改为++i程序照样输出正常结果。

{{ select(1-4) }}

• 正确
• 错误

●选择题

(5)输入为

11
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10

输出为()

{{ select(1-5) }}

• 2 5
• 3 4
• 4 5
• 3 5

(6)n为11时，ans的值最小为()

{{ select(1-6) }}

• 4
• 5
• 6
• 7