首页 > 试题广场 >

则输出为( )

[单选题]
#include<bits/stdc++.h>
using namespace std;
vector<int>g[10];
int ans = 0;
void dfs(int x){
if(g[x].size() == 0){
ans++;
return;
}
for(int i = 0; i < g[x].size(); ++i){
dfs(g[x][i]);
}
}
int main(){
int n, x;
scanf("%d", &n);
for(int i = 2; i <= n; ++i){
scanf("%d", &x);
g[x].push_back(i);
}
dfs(1);
cout<<ans<<endl;
return 0;
}


上述程序的输入为:
9
1 2 2 1 5 6 6 6
则输出为( )
  • 4
  • 5
  • 6
  • 7
g是一个数组vector。ans其实记录的是g[x].vector的长度为0的个数。main函数中主要是给g赋值。赋值结果如下:
g[1] :(这个vector里面有值)2, 5
g[2] : 3, 4
g[5] : 6
g[6] : 7, 8, 9
dfs函数中的for循环其实就是将每个g[x]中的vector中的值赋给dfs自己(的形参int x)。main函数中的dfs(1)为递归起点。于是:
由语句dfs(1), 然后因为g[1]的vector里面有值2和5,所以g[1].size = 2,不等于0,不满足if条件,ans不自增。 然后进入 for循环。因为g[1][0] = 2,于是执行dfs(2) .
由dfs(2),然后因为g[2]的vector里面有值3和4,所以g[2].size = 2,不等于0,不满足if条件,ans不自增。然后因为g[2][0] = 3,于是执行dfs(3).
由dfs(3),然后因为g[3]的vector里面没有值,所以g[3].size = 0,满足条件,ans自增。
然后就可以总结出前面的结论:dfs函数中的for循环其实就是将每个g[x]中的vector中的值赋给dfs自己(的形参int x),ans其实记录的是g[x].vector的长度为0的个数。然后就可以发现g[x](x为为2,5,3,4,6,7,8,9)中vector大小为0的只有(在main函数中未赋值的)g[3],g[4],g[7],[8],g[9],所以ans=5.
以上。(也不知道自己有没有表达清楚。。。orz)
发表于 2019-09-02 09:33:28 回复(0)
发表于 2019-09-12 17:31:35 回复(0)
求解
发表于 2019-09-01 21:55:01 回复(0)