首页 › 试卷 › GESP编程能力等级认证 › GESP-C++六级 › 2024年3月CCF-GESP编程能力等级认证C++编程六级真题

2024年3月CCF-GESP编程能力等级认证C++编程六级真题 VIP

GESP-C++六级 共 27 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

在构建哈夫曼树时,每次应该选择(   )合并。

  • A

    最小权值的节点

  • B

    最大权值的节点

  • C

    随机节点

  • D

    深度最深的节点

查看答案与解析
答案:A
这道题暂未补解析。
2. 单选题

面向对象的编程思想主要包括以下哪些原则(   )?

  • A

    贪心、动态规划、回溯

  • B

    并发、并行、异步

  • C

    递归、循环、分治

  • D

    封装、继承、多态

查看答案与解析
答案:D
这道题暂未补解析。
3. 单选题

在队列中,元素的添加和删除是按照(   )原则进行的。

  • A

    先进先出

  • B

    先进后出

  • C

    最小值先出

  • D

    随机进出

查看答案与解析
答案:A
这道题暂未补解析。
4. 单选题

给定一个简单的类定义如下,(   )语句在类的外部正确地创建了一个 Circle 对象并调用了 getArea 函数?

class Circle {
private:
	double radius;
public:
	Circle(double r) : radius(r) {}
	double getArea() {
		return 3.14 * radius * radius;
	}
};
  • A Circle c = Circle(5.0); c.getArea(c);
  • B Circle c(5.0); getArea(c);
  • C Circle c = new Circle(5.0); c.getArea();
  • D Circle c(5.0); c.getArea();
查看答案与解析
答案:D
这道题暂未补解析。
5. 单选题

以下代码希望能在一棵二叉排序树中搜索特定的值,请在横线处填入(   ),使其能正确实现相应功能。

TreeNode* search(TreeNode* root, int target) {
	if (root == NULL || root->val == target) {
		return root;
	}
	if (_______________) {
		return search(root->left, target);
	} else {
		return search(root->right, target);
	}
}
  • A target < root->left
  • B target < root->val
  • C target > root->val
  • D target > root->left
查看答案与解析
答案:B
这道题暂未补解析。
6. 单选题

3 位格雷编码的正确顺序是(   )。

  • A

    000, 001, 010, 011, 100, 101, 110, 111

  • B

    000, 001, 011, 010, 110, 111, 101, 100

  • C

    000, 010, 001, 011, 100, 110, 101, 111

  • D

    000, 010, 110, 100, 111, 101, 011, 001

查看答案与解析
答案:B
这道题暂未补解析。
7. 单选题

以下动态规划算法的含义与目的是(   )。

int function(vector<int>& nums) {
	int n = nums.size();
	if (n == 0)
		return 0;
	if (n == 1)
		return nums[0];
	vector<int> dp(n, 0);
	dp[0] = nums[0];
	dp[1] = max(nums[0], nums[1]);
	for (int i = 2; i < n; ++i) {
		dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
	}
	return dp[n - 1];
}
  • A 计算数组 nums 中的所有元素的和
  • B 计算数组 nums 中相邻元素的最大和
  • C 计算数组 nums 中不相邻元素的最大和
  • D 计算数组 nums 中的最小元素
查看答案与解析
答案:C
这道题暂未补解析。
8. 单选题

阅读以下广度优先搜索的代码:

void bfs(TreeNode* root) {
	if (root == NULL) {
		return;
	}
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty()) {
		TreeNode* current = q.front();
		q.pop();
		cout << current->val << " ";
		if (current->left) {
			q.push(current->left);
		}
		if (current->right) {
			q.push(current->right);
		}
	}
}

使用以上算法遍历以下这棵树,可能的输出是(   )。

  • A 1 2 8 9 4 5 3 6 7 10 11
  • B 1 2 3 4 5 6 7 8 9 10 11
  • C 1 2 3 8 9 6 4 5 7 10 11
  • D 1 2 3 8 9 4 5 6 7 10 11
查看答案与解析
答案:C
这道题暂未补解析。
9. 单选题

给定一个空栈,执行以下操作序列:

操作序列: push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()

最终栈中的元素是(   )。

  • A 1, 2
  • B 1, 4, 5
  • C 1, 2, 5
  • D 1, 4
查看答案与解析
答案:D
这道题暂未补解析。
10. 单选题

一个有 124 个叶子节点的完全二叉树,最多有(   )个结点。

  • A 247
  • B 248
  • C 249
  • D 250
查看答案与解析
答案:B
这道题暂未补解析。
11. 单选题

在求解最优化问题时,动态规划常常涉及到两个重要性质,即最优子结构和(   )。

  • A 重叠子问题
  • B

    分治法

  • C

    贪心策略

  • D

    回溯算法

查看答案与解析
答案:A
这道题暂未补解析。
12. 单选题

若一棵二叉树的先序遍历为:A, B, D, E, C, F、中序遍历为:D, B, E, A, F, C,它的后序遍历为(   )。

  • A D, E, B, F, C, A
  • B E, D, B, F, C, A
  • C D, E, B, C, F, A
  • D E, D, B, C, F, A
查看答案与解析
答案:A
这道题暂未补解析。
13. 单选题

线性筛法与埃氏筛法相比的优势是(   )。

  • A 更容易实现
  • B 更节省内存
  • C 更快速
  • D 更准确
查看答案与解析
答案:C
这道题暂未补解析。
14. 单选题

以下代码使用了辗转相除法求解最大公因数,请在横线处填入(   ),使其能正确实现相应功能。

int gcd(int a, int b) {
	while (b != 0) {
		______________________
	}
	return a;
}
  • A int temp = b; b = a / b; a = temp;
  • B int temp = a; a = b / a; b = temp;
  • C int temp = b; b = a % b; a = temp;
  • D b = a % b; a = b;
查看答案与解析
答案:C
这道题暂未补解析。
15. 单选题

下面的代码片段用于反转单链表,请进行(   )修改,使其能正确实现相应功能。

ListNode* reverseLinkedList(ListNode* head) {
	ListNode* prev = nullptr;
	ListNode* current = head;
	while (current != nullptr) {
		ListNode* next = current->next;
		current->next = next;
		prev = current;
		current = next;
	}
	return prev;
}
  • A current->next = next; 应该改为 current->next = prev;
  • B ListNode* next = current->next; 应该改为 ListNode* next = prev->next;
  • C current != nullptr 应该改为 current->next != nullptr
  • D ListNode* prev = nullptr; 应该改为 ListNode* prev = head;
查看答案与解析
答案:A
这道题暂未补解析。

二、判断题

16. 判断题

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

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
17. 判断题

在动态规划中,状态转移方程的作用是定义状态之间的关系。(   )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
18. 判断题

继承是将已有类的属性和方法引入新类的过程。(   )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
19. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
20. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
21. 判断题

在宽度优先搜索中,通常使用队列来辅助实现。(   )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
22. 判断题

哈夫曼编码的主要应用领域是有损数据压缩。(   )

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
23. 判断题

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

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
24. 判断题

栈的基本操作包括入栈(push)和出栈(pop)。(   )

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
25. 判断题

使用哈夫曼编码对一些字符进行编码,如果两个字符的频率差异最大,则它们的编码可能出现相同的前缀。(   )

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。

三、简答题

26. 简答题

游戏

题面描述

你有四个正整数n,a,b,c,并准备用它们玩一个简单的小游戏。

在一轮游戏操作中,你可以选择将n减去a,或是将n减去b。游戏将会进行多轮操作,直到当n≤c时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同,当且仅当游戏操作轮数不同,或是某一轮游戏操作中,一种操作序列选择将n减去a,而另一种操作序列选择将n减去b。如果a=b,也认为将n减去a与将n减去b是不同的操作。

由于答案可能很大,你只需要求出答案对1000000007取模的结果。

输入格式

一行四个正整数n,a,b,c。保证1≤a,b,c≤n。

输出格式

一行一个整数,表示不同的游戏操作序列数量对1000000007取模的结果。


样例输入1

1 1 1 1

样例输出1

1

样例输入2

114 51 4 1

样例输出2

176

样例输入3

114514 191 9 810

样例输出3

384178446

数据范围

对于20的测试点,保证a=b=c=1,n≤30。

对于40的测试点,保证c=1,n≤103。

对于所有测试点,保证1≤n≤2×105。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; using namespace std; const int N = 2e5 + 5; const int mod = 1e9 + 7; int n, a, b, c; int f[N &lt;&lt; 1]; int ans; int main() { scanf("%d%d%d%d", &amp;n, &amp;a, &amp;b, &amp;c); f[N + n] = 1; for (int i = n; i &gt; c; i--) { f[N + i - a] = (f[N + i - a] + f[N + i]) % mod; f[N + i - b] = (f[N + i - b] + f[N + i]) % mod; } for (int i = 0; i &lt;= N + c; i++) ans = (ans + f[i]) % mod; printf("%d\n", ans); return 0; }</pre>
这道题暂未补解析。
27. 简答题

好斗的牛

问题描述

你有109个牛棚,从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是,你的牛很好斗,如果他们附近有其他的牛,他们就会不安分地去挑事。其中,第i头牛的攻击范围是(ai,bi),这意味着,如果他的左边ai个牛棚或右边bi个牛棚里有其他牛,他就会去挑事。

你想留下连续的一段牛棚,并把其他牛棚都卖掉。请问你最少需要留下多少牛棚,才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里,且没有牛会挑事?

输入描述

第一行 1 个正整数N。

接下来一行N个用空格隔开的正整数a1,...,aN。

接下来一行 个用空格隔开的正整数b1,...,bN。

输出描述

输出一行一个整数,表示你最少需要留下多少牛棚。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

2
1 2
1 2

样例输出 1

4

样例解释 1

你可以留下 个牛棚,并如此安排你的牛:

样例输入 2

3
1 2 3
3 2 1

样例输出 2

7

数据规模

对于20的测试点,保证N=2;

对于另外20的测试点,保证N=3;

对于80的测试点,保证N≤8;

对于所有测试点,保证N≤9,ai,bi≤1000。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int N; vector&lt;int&gt; a, b; int ans = 1e9; int main() { cin &gt;&gt; N; a.resize(N); b.resize(N); for (int i = 0; i &lt; N; ++i) { cin &gt;&gt; a[i]; } for (int i = 0; i &lt; N; ++i) { cin &gt;&gt; b[i]; } vector&lt;int&gt; permutation; permutation.resize(N); for (int i = 0; i &lt; N; i ++) permutation[i] = i; do { int curr_len = N; for (int i = 1; i &lt; N; ++i) { curr_len += max(b[permutation[i - 1]], a[permutation[i]]); } ans = min(ans, curr_len); } while(next_permutation(permutation.begin(), permutation.end())); cout &lt;&lt; ans &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。