首页 › 题库 › GESP编程能力等级认证 › GESP-C++六级

GESP-C++六级 题库

共 270 道题 ,第 6 / 14 页 · 按题型筛选,点「查看答案」核对解析
101 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

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

A
重叠子问题
B
分治法
C
贪心策略
D
回溯算法
答案与解析
正确答案:A

动态规划的性质主要包括最优子结构、无后效性和有重叠子问题

最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。这意味着问题的最优解可以通过其子问题的最优解来构建。

无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。这一性质确保了动态规划方法的有效性,因为当前阶段的选择不会影响到之前阶段的状态。

有重叠子问题:子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。这一性质是动态规划算法能够通过存储和重用子问题的解来提高效率的关键。

题目详情
102 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

青蛙每次能跳1或2步,下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法,错误的是( )。

int jump_recur(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	return jump_recur(n - 1) + jump_recur(n - 2);
}

int jump_dp(int n) {
	vector<int> dp(n + 1); // 创建一个动态规划数组,用于保存已计算的值
	// 初始化前两个数
	dp[1] = 1;
	dp[2] = 2;
	// 从第三个数开始计算斐波那契数列
	for (int i = 3; i <= n; ++i) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}


A
函数jump_recur()采用递归方式。
B
函数jump_dp()采用动态规划方法。
C
当n较大时,函数jump_recur()存在大量重复计算,执行效率低。
D
函数jump_recur()代码量小,执行效率高。
答案与解析
正确答案:D

状态表示:dp[i]表示青蛙到达第i个台阶的跳法。

状态转移方程:第i个台阶由两个状态转移过来①i-2级跳两步②i-1级跳一部,因此状态转移方程为:dp[i]=dp[i-1]+dp[i-2]

目标状态:dp[n]

int jump_recur(int n)使用递归方式(斐波那契),无记忆化,因此复杂度为指数。

int jump_dp(int n)使用动规(递推)方式,复杂度O(n).

题目详情
103 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

#include <iostream>
#include <queue>

using namespace std;

// 二叉树节点的定义
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 宽度优先搜索(BFS)迭代实现
TreeNode* bfs(TreeNode* root, int a) {
	if (root == nullptr) return nullptr;
	
	queue<TreeNode*> q;
	q.push(root);
	
	while (!q.empty()) {
		TreeNode* node = q.front();
		q.pop();
		
		if (node->val == a)
			return node;
		cout << node->val << " "; // 先访问当前节点
		if (node->left) q.push(node->left); // 将左子节点入队
		if (node->right) q.push(node->right); // 将右子节点入队
	}
	return nullptr;
}

使用以上算法,在以下这棵树搜索数值20时,可能的输出是( )。

A
5 2 -4 3 17 9
B
-4 2 3 5 9 17
C
5 2 17 -4 3 9
D
以上都不对
答案与解析
正确答案:C

该程序使用广搜方式,因此为二叉树层序遍历,答案选C

题目详情
104 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

同上题中的二叉树,阅读以下二叉树的深度优先搜索代码:

#include <iostream>
#include <stack>

using namespace std;

// 非递归深度优先搜索(DFS)
TreeNode* dfs(TreeNode* root, int a) {
	if (root == nullptr) return nullptr;
	
	stack<TreeNode*> stk;
	stk.push(root);
	
	while (!stk.empty()) {
		TreeNode* node = stk.top();
		stk.pop();
		if (node->val == a)
			return node;
			
		cout << node->val << " "; // 访问当前节点
		
		if (node->right) stk.push(node->right); // 先压入右子节点
		if (node->left) stk.push(node->left); // 再压入左子节点
	}
	return nullptr;
}

使用以上算法,在二叉树搜索数值20时,可能的输出是( )。

A
5 2 -4 3 17 9
B
-4 2 3 5 9 17
C
5 2 17 -4 3 9
D
以上都不对
答案与解析
正确答案:A

该题目使用栈代替了DFS的递归形式,由输出和push的顺序,可以知道该题目为先序遍历,因此答案为A。

题目详情
105 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

在上题的树中搜索数值3时,采用深度优先搜索一共比较的节点数为( )。

A
2
B
3
C
4
D
5
答案与解析
正确答案:C

该二叉树中序遍历有序,同时从构造形态上,为一棵二叉排序树,但是程序并不是按照二叉排序树的规则,题目是先序遍历比较,因此比较的节点依次为:5、2、-4、3,共4次。

题目详情
106 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

A

最小权值的节点

B

最大权值的节点

C

随机节点

D

深度最深的节点

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
107 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

A

贪心、动态规划、回溯

B

并发、并行、异步

C

递归、循环、分治

D

封装、继承、多态

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
108 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 6.2 队列

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

A

先进先出

B

先进后出

C

最小值先出

D

随机进出

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
109 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

给定一个简单的类定义如下,(   )语句在类的外部正确地创建了一个 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
这道题暂未补解析。
题目详情
110 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

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
这道题暂未补解析。
题目详情
111 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 2.1 格雷编码

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
这道题暂未补解析。
题目详情
112 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

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

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
这道题暂未补解析。
题目详情
113 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

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
这道题暂未补解析。
题目详情
114 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 6.1 栈

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

操作序列: 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
这道题暂未补解析。
题目详情
115 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

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

A
247
B
248
C
249
D
250
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
116 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

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

A
重叠子问题
B

分治法

C

贪心策略

D

回溯算法

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
117 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

若一棵二叉树的先序遍历为: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
这道题暂未补解析。
题目详情
118 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 综合练习

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

A
更容易实现
B
更节省内存
C
更快速
D
更准确
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
119 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

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
这道题暂未补解析。
题目详情
120 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

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

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
这道题暂未补解析。
题目详情