首页 › 题库 › GESP编程能力等级认证 › 1.1 树的基本概念

GESP-C++六级 题库

共 95 道题 ,第 5 / 5 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 树的基本概念 清除
81 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

完全二叉树可以用数组存储数据。

A
对
B
错
答案与解析
正确答案:对

完全二叉树比较平衡,因此可以从1开始编号作为根,后续每个节点i,其左右两个孩子的下标为2i,和2i+1。

题目详情
82 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

哈夫曼树是一种二叉树。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
83 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

完全二叉树的任意一层都可以不满。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
84 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

删除单向链表中的节点,只需知道待删除节点的地址即可,无需访问前一个节点。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
85 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉搜索树的查找操作的时间复杂度是O(N)。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
86 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

深度优先搜索(DFS,Depth First Search的简写)属于图算法,其过程是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。(   )(2023年12月C++六级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
87 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉搜索树查找的平均时间复杂度为O(logN)。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
88 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉搜索树可以是空树(没有任何节点)或者单节点树(只有一个节点),或者多节点。如果是多节点,则左节点的值小于父节点的值,右节点的值大于父节点的值,由此推理,右节点树的值都大于根节点的值,左节点树的值都小于根节点的值。(   )(2023年12月C++六级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
89 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

如果节点数为 ,广度搜索算法的最差时间复杂度为O(N)。(2023.9C++六级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
90 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉搜索树的左右子树也是二叉搜索树。(2023.9C++六级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
91 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

路径覆盖

题目描述

给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci ,你需要在满足以上条件的情况下,最小化染色代价之和。 叶子是指 T 中没有子结点的结点。

输入格式

第一行,一个正整数 n ,表示结点数量。 第二行, n−1 个正整数 f2, f3, …, fn ,其中 fi 表示结点 i 的父结点的编号,保证 fi<i 第三行, n 个正整数 c1, c2, …, cn,其中 ci 表示将结点 i 染为黑色所需的代价。

输出格式

一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。

样例

输入样例1

4
1 2 3
5 6 2 3

输出样例1

2

输入样例2

7
1 1 2 2 3 3
64 16 15 4 3 2 1

输出样例2

10

数据范围

对于 40% 的测试点,保证 2 ≤n ≤16

对于另外 20% 的测试点,保证 fi=i-1 对于所有测试点,保证 2 ≤n ≤10^5, 1 ≤ci ≤10^9

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
int n;
int f[N], c[N], cnt[N];
long long ans[N];
vector<int> son[N];

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &f[i]);
        son[f[i]].push_back(i);
        cnt[f[i]]++;
    }

    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);

    for (int i = n; i >= 1; i--) {
        ans[i] = c[i];
        long long sum = 0;
        for (int v : son[i]) {
            sum += ans[v];
        }
        ans[i] = min(ans[i], sum);
    }

    printf("%lld\n", ans[1]);
    return 0;
}
题目详情
92 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

最大因数

时间限制:1 s,内存限制:512 MB

【问题描述】

给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。

对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。

现在有 q 组询问,第 i(1<= i  <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。

两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

【输入描述】

第一行,一个正整数 q,表示询问组数。

接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。

【输出描述】

输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。

【样例输入1】

3
1 3
2 5
4 8

【样例输出1】

1
2
1

【样例输入2】

1
120 650

【样例输出2】

9

【数据范围】

对于60%的测试点,保证 1 <= xi、yi <= 1000。

对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N], cnta, b[N], cntb;
int f[N], t, q;
void factorize(int x, int a[], int &cnt) {
    a[0] = x;
    t = 0;
    for (int i = 2; i * i <= x; i++)
        while (x % i == 0) {
            f[++t] = i;
            x /= i;
        }
    if (x > 1)
        f[++t] = x;
    for (int i = 1; i <= t; i++)
        a[i] = a[i - 1] / f[i];
    cnt = t;
}
int main() {
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        factorize(x, a, cnta);
        factorize(y, b, cntb);
        int px = 0, py = 0;
        while (a[px] != b[py]) {
            if (a[px] > b[py])
                px++;
            else
                py++;
        }
        cout << px + py << endl;
    }
    return 0;
}
题目详情
93 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

树上漫步

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。

小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。

现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。

【输入描述】

第一行,一个正整数 n。

接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。

【输出描述】

一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。

【样例输入1】

3
1 3
2 3

【样例输出1】

2 2 1

【样例输入2】

4
1 3
3 2
4 3

【样例输出2】

3 3 1 3

【数据范围】

对于 20% 的测试点,保证 1<=n<=1000。

对于所有测试点,保证 1<=n<=200000。

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int cnt[N], bel[N];
void ae(int u, int v) {
    et++;
    to[et] = v;
    nx[et] = h[u];
    h[u] = et;
}
void dfs(int u, int c, int f) {
    bel[u] = c;
    cnt[c]++;
    for (int i = h[u]; i; i = nx[i])
        if (to[i] != f)
            dfs(to[i], c ^ 1, u);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        ae(u, v);
        ae(v, u);
    }
    dfs(1, 0, 0);
    for (int i = 1; i <= n; i++)
        printf("%d%c", cnt[bel[i]], " \n"[i == n]);
    return 0;
}
题目详情
94 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

树上游走

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 1,对于节点 i ,其左儿子的编号为 2×i,右儿子的编号为 2×i+1。

小杨会从节点 s 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:

第1种移动方式: 如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;

第2种移动方式: 移动到当前节点的左儿子;

第3种移动方式: 移动到当前节点的右儿子。

小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过 1012。

输入格式

第一行包含一个正整数 n,s,代表移动次数和初始节点编号。

第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串,代表每次移动的方式,其中 U 代表第1种移动方式,L 代表第2种移动方式,R代表第3种移动方式。

输出格式

输出一个正整数,代表最后所处的节点编号。

输入样例

3 2
URR

输出样例

7

样例解释

小杨的移动路线为 2-1-3-7。

对于全部数据,保证有 1≤n≤106,1≤s≤1012。

答案与解析
参考答案
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e12;
int n;
stack<char> st;
string c;
ll s;
int main(){
	cin >> n >> s >> c;
	for(int i = 0; i < n; i ++){
		if(c[i] == 'U'){
			if(s == 1) continue;
			if(st.size()){
				st.pop();
				continue;
			}
			s >>= 1;
		}else if(c[i] == 'L'){
			if((s << 1) > INF){
				st.push('L');
				continue;
			}
			s = s << 1;
		}else{
			if((s << 1 | 1) > INF){
				st.push('R');
				continue;
			}
			s = s << 1 | 1;
		}
	}
	cout << s << "\n";
	return 0;
}
题目详情
95 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉树

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含n个节点的二叉树,且根节点的编号为1。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行q次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。

小杨想知道q次操作全部完成之后每个节点的颜色。

输入格式

第一行一个正整数n,表示二叉树的节点数量。

第二行n−1个正整数,第i(1≤i≤n−1) 个数表示编号为i+1 的节点的父亲节点编号,数据保证是一棵二叉树。

第三行一个长度为n的01 串,从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。

第四行一个正整数q,表示操作次数。

接下来q行每行一个正整数ai(1≤ai≤n),表示第i次操作选择的节点编号。

输出格式

输出一行一个长度为n的01 串,表示q次操作全部完成之后每个节点的颜色。从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。


输入样例

6
3 1 1 3 4
100101
3
1
3
2

输出样例

010000

样例解释

第一次操作后,节点颜色为:011010

第二次操作后,节点颜色为:000000

第三次操作后,节点颜色为:010000

数据范围

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int son[N][2];
int f[N],col[N],sum[N];
	void dfs(int x,int now){
	now+=sum[x];
	if(now&1)col[x]^=1;
	for(int i=0;i<2;i++){
		if(son[x][i]!=-1)dfs(son[x][i],now);
	}
}
int main(){
	cin>>n;
	memset(son,-1,sizeof son);
	for(int i=2;i<=n;i++){
		cin>>f[i];
		for(int j=0;j<2;j++){
			if(son[f[i]][j]==-1){
				son[f[i]][j]=i;
				break;
			}
		}
	}
	string s;
	cin>>s;
	for(int i=1;i<=n;i++){
		col[i]=s[i-1]-'0';
	}
	int q;
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		sum[x]+=1;
	}
	
	dfs(1,0);
	for(int i=1;i<=n;i++){
		cout<<col[i];
	}
	cout<<"\n";
}

①比较朴素的思路为建树,每次操作时执行DFS,将操作的结果处理,最终输出每个节点颜色,极端情况下每次操作遍历整棵树的话,复杂度O(nq),只能解决40%的数据。

②考虑到程序只要最终结果,因此中间结果没必要完全求得,取反操作的周期为2,具有奇偶性,因此每次操作X时,将X的位置打个标记,表示其将影响X下方的每个节点翻转一次,当所有操作标记完,执行DFS,从root=1出发,统计到达每个节点X时的标记的数量cnt,如果cnt为奇数,则改点颜色取反,否则保持原来颜色。这样只需要O(n+q)的复杂度。

题目详情