GESP-C++六级 题库

共 136 道题 ,第 2 / 7 页 · 按题型筛选,点「查看答案」核对解析
21 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

设有字符集 {a, b, c, d, e},其出现频率分别为 {5, 8, 12, 15, 20},得到的哈夫曼编码为?( )

A
a: 010b: 011c: 00d: 10e: 11
B
a: 00b: 10c: 011d: 100e: 111
C
a: 10b: 01c: 011d: 100e: 111
D
a: 100b: 01c: 011d: 100e: 00
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
22 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

给定一个二叉树,返回每一层中最大的节点值,结果以数组形式返回,横线处应填入?( )

#include <vector>
#include <queue>
#include <algorithm>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
vector<int> largestValues(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        int maxVal = INT_MIN;
        for (int i = 0; i < sz; ++i) {
            TreeNode* node;
            _______________________________
            maxVal = max(maxVal, node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(maxVal);
    }
    return result;
}
A
node = q.end();
B
node = q.front();
C
q.pop();node = q.front();
D
node = q.front();q.pop();
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
23 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

下面代码实现一个二叉排序树的插入函数(没有相同的数值),横线处应填入?( )

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void insert(TreeNode*& root, int key) {
    if (!root) {
        root = new TreeNode(key);
        return;
    }
    _______________________________
}
A
if (key < root->val)
    insert(root->left, key);
else if (key > root->val)
    insert(root->right, key);
B
if (key < root->val)
    insert(root->right, key);
else if (key > root->val)
    insert(root->left, key);
C
insert(root->left, key);
insert(root->right, key);
D
insert(root->right, key);
insert(root->left, key);
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
24 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中,【不正确】的是?( )

A
哈夫曼编码是一种变长编码,频率高的字符使用较短的编码,频率低的字符使用较长的编码。
B
在构造哈夫曼树时,频率越低的字符离根节点越近,频率越高的字符离根节点越远。
C
哈夫曼编码的生成过程基于贪心算法,每次选择频率最低的两个节点进行合并。
D
哈夫曼编码是一种前缀编码,任何一个字符的编码都不会是另一个字符编码的前缀,因此可以实现唯一解码。
答案与解析
正确答案:B

哈夫曼编码是一种基于字符出现频率的无损数据压缩算法,其核心思想是:

变长编码:频率高的字符用较短的编码,频率低的字符用较长的编码。

前缀编码:任何字符的编码都不是其他字符编码的前缀,确保解码唯一性。

贪心算法:通过合并频率最低的节点构建哈夫曼树。

选项B错误,哈夫曼树的构造规则是:频率越低的字符离根节点越远(路径更长),频率越高的字符离根节点越近(路径更短)。

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

以下代码实现了树的哪种遍历方式?( )

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    traverse(root->left);
    traverse(root->right);
}
A
前序遍历
B
中序遍历
C
后序遍历
D
层次遍历
答案与解析
正确答案:A

树的遍历主要方式:

前序遍历:访问顺序:根节点 → 左子树 → 右子树。

中序遍历:访问顺序:左子树 → 根节点 → 右子树。

后序遍历:访问顺序:左子树 → 右子树 → 根节点。

这段代码实现了树的 前序遍历(根→左→右)。

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

以下关于完全二叉树的代码描述,正确的是?( )

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}
A
该代码用于判断一棵树是否为满二叉树
B
该代码用于判断一棵树是否为完全二叉树
C
该代码用于判断一棵树是否为二叉搜索树
D
该代码用于计算树的高度
答案与解析
正确答案:B

使用队列 q 进行层序遍历,hasNull 标记是否遇到过空节点(初始为 false)。

遍历过程:

每次从队列中取出一个节点 node。

如果 node 是 nullptr:设置 hasNull = true。

如果 node 非空:若之前已遇到空节点(hasNull == true),则直接返回 false(违反完全二叉树的定义)。

否则,将 node 的左右子节点(无论是否为空)加入队列。

代码实现了 完全二叉树的判断逻辑。

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

以下代码实现了二叉排序树的哪种操作?( )

TreeNode* op(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val) {
        root->left = op(root->left, val);
    } else {
        root->right = op(root->right, val);
    }
    return root;
}
A
查找
B
插入
C
删除
D
遍历
答案与解析
正确答案:B

程序中:

if (root == nullptr) return new TreeNode(val)

若目标值不存在,则在叶子节点位置创建新节点。

若目标值更小,递归查找左子树;若目标值更大,递归查找右子树。

这段代码通过递归查找插入位置并动态创建新节点,实现了 二叉排序树的插入操作。

题目详情
28 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2} ,则正确的哈夫曼编码是?( )

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

以下代码实现了二叉树的深度优先搜索(DFS),并统计叶子结点的数量,则横线上应填写?( )

int countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == nullptr && node->right == nullptr) {
            count++;
        }
        if (node->right) s.push(node->right);
        _____________________________________ // 在此处填入代码
    }
    return count;
}
A
if (node->left) s.push(node->left);
B
if (node->left) s.pop(node->left);
C
if (node->left) s.front(node->left);
D
if (node->left) s.push(node->right);
答案与解析
正确答案:A

空缺的位置在 while 循环的末尾,当前代码已经处理了右子树的压栈操作,需要补充左子树的处理逻辑。

程序使用栈(stack<TreeNode*>)来实现 DFS,空缺部分应该是一个类似的逻辑:如果 node 有左子节点,则将其压入栈。

本题答案为选项A。

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

以下代码实现了二叉树的广度优先搜索(BFS),并查找特定值的节点,则横线上应填写?( )

TreeNode* findNode(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        if (current->val == target) {
            return current; // 找到目标节点
        }
        ___________________________________ // 在此处填入代码
    }
    return nullptr; // 未找到目标节点
}
A
if (current->left) q.push(current->left);if (current->right) q.push(current->right);
B
if (current->left) q.pop(current->left);if (current->right) q.pop(current->right);
C
if (current->left) q.front(current->left);if (current->right) q.front(current->right);
D
if (current->left) q.push(current->right);if (current->right) q.push(current->left);
答案与解析
正确答案:A

BFS 遍历:使用队列(queue)来实现 BFS。

初始时,将根节点 root 入队。

在 while 循环中,取出队首节点 current:

如果 current->val == target,则返回 current(找到目标节点)。

空缺部分需要将 current 的子节点(左子节点和右子节点)入队。

本题答案为选项A。

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

N 个节点的双向循环链,在其中查找某个节点的平均时间复杂度是( )。

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

以下关于树的说法,( )是正确的。

A
在一棵二叉树中,叶子结点的度一定是2。
B
满二叉树中每一层的结点数等于 O(2 (层数−1))。
C
在一棵树中,所有结点的度之和等于所有叶子结点的度之和。
D
一棵二叉树的先序遍历结果和中序遍历结果一定相同。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
33 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

已知字符集 {A, B, C, D} 的出现频率如下表所示:

根据哈夫曼编码法,下面( )是正确的哈夫曼树。

A
 ABCD
 / \
A   BCD
    / \
   D   BC
      / \
     B   C
B
 ABCD
 / \
A   BCD
    / \
   B   CD
      / \
     C   D
C
 ABCD
 / \
D   ABC
    / \
   A   BC
      / \
     B   C
D
 ABCD
 / \
C   ABC
    / \
   B   AD
      / \
     A   D
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
34 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

上一题中各字符的哈夫曼编码是( )。

A
A: 0, B: 10, C: 110, D: 111
B
A: 0, B: 10, C: 11, D: 10
C
A: 0, B: 101, C: 100, D: 11
D
A: 11, B: 10, C: 01, D: 00
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
35 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

根据下面二叉树和给定的代码,

#include <iostream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* search(TreeNode* root, int val) {
	cout << root->val << " ";
	if (root == NULL || root->val == val) return root;
	
	if (val < root->val)
		return search(root->left, val);
	else
		return search(root->right, val);
}

给定以下二叉搜索树,调用函数 search(root,7) 时,输出的结果是( )。

    5
   / \
  3   7
 / \ / \
2  4 6  8
A
5 3 7
B
5 7
C
2 3 4 5 6 7
D
8 7
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
36 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

阅读以下二叉树的深度优先搜索算法,横线上应填写( )。

void dfs(TreeNode* root) {
	if (root == nullptr)
		return;
		
	stack<TreeNode*> s;
	s.push(root);
	while (!s.empty()) {
		———————————————————————— // 在此处填入代码
		cout << node->value << " ";
		
		if (node->right) s.push(node->right);
		if (node->left) s.push(node->left);
	}
}
A
TreeNode* node = s.top();
B
TreeNode* node = s.top(); s.pop();
C
TreeNode* node = s.front();
D
TreeNode* node = s.front(); s.pop();
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
37 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

阅读以下二叉树的广度优先搜索的代码,横线上应填写( )。

#include <queue>
void bfs(TreeNode* root) {
	if (root == NULL) return;
	
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty()) {
		———————————————————————— // 在此处填入代码
		cout << node->val << " ";
		if (node->left) {
			q.push(node->left);
		}
		if (node->right) {
			q.push(node->right);
		}
	}
}
A
TreeNode* node = q.top();
B
TreeNode* node = q.top(); q.pop();
C
TreeNode* node = q.front();
D
TreeNode* node = q.front(); q.pop();
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
38 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

使用上题中的宽度优先搜索算法遍历以下这棵树,可能的输出是( )。

  1
   / \
  2   3
 / \   \
8   9   6
   / \   \
  4   5   7
A
1 2 8 9 4 5 3 6 7
B
1 2 3 4 5 6 6 8 9
C
1 2 3 8 9 6 4 5 7
D
8 4 5 9 2 1 3 6 7
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
39 单选题 适中 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行二进制编码,则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。(2024.9-6)

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

给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。(2024.9-6)

A
EDBGFCA
B
EDGBFCA
C
DEBGFCA
D
DBEGFCA
答案与解析
正确答案:A

在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。

题目详情