#CS409. 阅读程序-树和图

阅读程序-树和图

阅读程序

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

第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

第2题【NOIP】2008

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m) {
	int i, root_m;
07	if(spos_f > epos_f)
08		return;
	for(i = spos_m; i <= epos_m; i++)
		if(first[spos_f] == mid[i]) {
			root_m = i;
			break;
		}
	solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
	solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
	cout << first[spos_f];
17 }
18 int main() {
19	char first[MAX], mid[MAX];
	int len;
	cin >> len;
	cin >> first >> mid;
	solve(first, 0, len - 1, mid , 0, len - 1);
	cout << endl;
	return 0;
}

●判断题

(1)将19行移到17行和18行之间，程序不会出错。

{{ select(2-1) }}

  • 正确
  • 错误

(2)将07行和08行去掉，程序可以得出相同的结果

{{ select(2-2) }}

  • 正确
  • 错误

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

{{ select(2-3) }}

  • 正确
  • 错误

(4)将19行的char改为int类型，程序可以得到相同的结果

{{ select(2-4) }}

  • 正确
  • 错误

●选择题

(5)输人为

7
ABDCEGF
BDAGECF

时，输出为()。

{{ select(2-5) }}

  • DBGEFCA
  • DRGFECA
  • GBDEFCA
  • ABCDEFG

(6)该程序要解决的间题是()。

{{ select(2-6) }}

  • 给出先序遍历和后序通历求中序遍历
  • 给出先序遍历和中序通历求后序遍历
  • 给出中序通历和后序遍历求前序遍历
  • 给出前序遍历和中序遍历求层序遍历

第3题【NOIP】2012

#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep) {
	ans = ans + dep*(s1[x] - 'A' + 1);
	if (lefts[x] >= 0) calc(lefts[x], dep+1);
	if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x) {
	if (lefts[x] >= 0) check(lefts[x]);
	s3 = s3 + s1[x];
	if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th) {
	if (th == n) {
19		s3 = "";
		check(0);
		if (s3 == s2) {
			ans = 0;
			calc(0, 1);
			cout<<ans<<endl;
		}
		return;
	}
	if (lefts[x] == -1 && rights[x] == -1) {
		lefts[x] = th;
		father[th] = x;
		dfs(th, th+1);
		father[th] = -1;
		lefts[x] = -1;
	}
	if (rights[x] == -1) {
		rights[x] = th;
		father[th] = x;
		dfs(th, th+1);
		father[th] = -1;
		rights[x] = -1;
	}
	if (father[x] >= 0)
		dfs(father[x], th);
}
int main() {
	cin>>s1;
	cin>>s2;
48	n = s1.size();
	memset(lefts, -1, sizeof(lefts));
	memset(rights, -1, sizeof(rights));
	memset(father, -1, sizeof(father));
	dfs(0, 1);
}

●判断题

(1)将19行去掉，程序运行结果与原来一致。

{{ select(3-1) }}

  • 正确
  • 错误

(2)该程序时间复杂度为O(n3n^3)。

{{ select(3-2) }}

  • 正确
  • 错误

(3)将02行去掉，程序运行结果与原来一致。

{{ select(3-3) }}

  • 正确
  • 错误

(4)48行函数时间复杂度为O(1)。

{{ select(3-4) }}

  • 正确
  • 错误

●选择题

(5)当输入为

ABCDEF
BCAEDF

,输出为()。

{{ select(3-5) }}

  • 54
  • 55
  • 56
  • 57

(6)此程序主要执行的算法思路是()。

{{ select(3-6) }}

  • 深搜
  • 广搜
  • 动规
  • 分治

第4题【NOIP】2018

#include <stdio.h>
int n, d[100];
bool v[100];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
07		scanf("%d", d + i);
		v[i] = false;
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
12		if (!v[i]) {
			for (int j = i; !v[j]; j = d[j]) {
				v[j] = true;
			}
			++cnt;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

●判断题

(1)将第7行的d+i换成&d[i],程序运行不受影响。

{{ select(4-1) }}

  • 正确
  • 错误

(2)第12行的!v[i]与v[i]==false语句意思一致。

{{ select(4-2) }}

  • 正确
  • 错误

(3)程序的输出结果cnt至少等于1。

{{ select(4-3) }}

  • 正确
  • 错误

(4)若输人的数组d中有重复的数字，则程序会进入死循环。

{{ select(4-4) }}

  • 正确
  • 错误

●选择题

(5)若输入数字为5 1 2 3 4 5,则输出为()

{{ select(4-5) }}

  • 0
  • 1
  • 2
  • 5

(6)若输入数字为10 7 1 4 3 2 5 9 8 0 6,则输出为( )。

{{ select(4-6) }}

  • 3
  • 6
  • 7
  • 8

第5题【NOIP】2011

#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
    int i;
    visited[x]= true;
    if(len>ans)
       ans=len;
    for(i=1;i<=n;i++)
       if( (!visited[i]) && (e[x][i]!=-1) )
          dfs(i,len+e[x][i]);
    visited[x]=false;
}
int main()
{
    int i,j,a,b,c;
    cin>>n>>m;
    for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
          e[i][j]=-1;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        e[a][b]=c;
        e[b][a]=c;
    }
    for(i=1;i<=n;i++)
       visited[i]=false;
    ans=0;
    for(i=1;i<=n;i++)
       dfs(i,0);
    cout<<ans<<endl;
    return 0;
}

●判断题

(1)输入的数据应满足a,b<100。

{{ select(5-1) }}

  • 正确
  • 错误

(2)该程序实现的是多源最短路。

{{ select(5-2) }}

  • 正确
  • 错误

(3)在没有重边与自环的情况下，m最大为n2n^2

{{ select(5-3) }}

  • 正确
  • 错误

(4)对于一个n个点的边权均为w的完全图，输出为(n—1)*w。

{{ select(5-4) }}

  • 正确
  • 错误

●选择题

(5)求该程序消耗空间约为()

{{ select(5-5) }}

  • 100MB
  • 1GB
  • 40KB
  • 100KB

(6)

输人：

46
12 10
23 20
34 30
41 40
13 50
24 60

输出()。

{{ select(5-6) }}

  • 150
  • 60
  • 210
  • 10

第6题【NOIP】2010

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool  map[SIZE][SIZE],found;
bool successful(){
    int i;
    for(i=1;i<=n;i++)
        if(!map[r[i]][r[i%n+1]])
           return false;
    return true;
}
14 void swap(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
void perm(int left,int right)
{
    int i;
    if(found)
       return ;
    if(left>right){
        if(successful()){
            for(i=1;i<=n;i++)
                cout<<r[i]<<' ';
            found=true;
        }
        return ;
    }
    for(i=left;i<=right;i++){
        swap(r+left,r+i);
        perm(left+1,right);
        swap(r+left,r+i);
    }
}
int main()
{
    int x,y,i;
    cin>>n>>m;
44  memset(map,false,sizeof(map));
    for(i=1;i<=m;i++){
        cin>>x>>y;
        map[x][y]=true;
48      map[y][x]=true;
    }
    for(i=1;i<=n;i++)
       r[i]=i;
    found=false;
    perm(1,n);
    if(!found)
        cout<<"No solution!"<<endl;
    return 0;
}

●判断题

(1)在44行前加一个左斜杠，程序能正常运行，结果不变。

{{ select(6-1) }}

  • 正确
  • 错误

(2)去掉14行的*,运行结果不变。

{{ select(6-2) }}

  • 正确
  • 错误

(3)将48行删去不影响输出结果

{{ select(6-3) }}

  • 正确
  • 错误

(4)将map类型改为int不会影响运行结果。

{{ select(6-4) }}

  • 正确
  • 错误

●选择题

(5)该程序时间复杂度为()

{{ select(6-5) }}

  • O(nmlogn×mnlogm)O(n^{mlogn}×m^{nlogm})
  • O(n * m)
  • O(m! * n)
  • O(n! * n)

(6)输入：9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9输出()

{{ select(6-6) }}

  • 1 2 3 4 5 6 7 8 9
  • 9 8 7 2 4 3 5 1 6
  • 3 2 7 1 6 9 5 4 8
  • 1 6 9 5 4 8 3 2 7
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 粤ICP备2022142345号-1
  4. Worker 0, 13ms
  5. Powered by Hydro v4.14.1 Community