GESP真题试卷 C++ 6级(2025.12)

一单选题

共 15 道每题 2 分共计 30 分

第 1 题

在面向对象编程中，下列关于虚函数的描述中，错误的是（）。

A

虚函数用于支持运行时多态

B

通过基类指针调用虚函数时，会根据对象实际类型决定调用版本

C

构造函数可以声明为虚函数以支持多态

D

基类析构函数常声明为虚函数以避免资源泄漏

第 2 题

执行如下代码，会输出钢琴：叮咚叮咚和吉他：咚咚当当。这体现了面向对象编程的（）特性。

class Instrument {
public:
    virtual void play() {
        cout << "乐器在演奏声音" << endl;
    }
 
    virtual ~Instrument() {}
};
 
class Piano : public Instrument {
public:
    void play() override {
        cout << "钢琴: 叮咚叮咚" << endl;
    }
};
 
class Guitar : public Instrument {
public:
    void play() override {
        cout << "吉他: 咚咚当当" << endl;
    }
};
 
int main() {
    Instrument* instruments[2];
    instruments[0] = new Piano();
    instruments[1] = new Guitar();
 
    for (int i = 0; i < 2; ++i) {
        instruments[i]->play();
    }
 
    for (int i = 0; i < 3; ++i) {
        delete instruments[i];
    }
    return 0;
}

A

继承

B

封装

C

多态

D

链接

第 3 题

关于以下代码，说法正确的是（）。

class Instrument {
public:
    void play() {
        cout << "乐器在演奏声音" << endl;
    }
 
    virtual ~Instrument() {}
};
 
class Piano : public Instrument {
public:
    void play() override {
        cout << "钢琴: 叮咚叮咚" << endl;
    }
};
 
class Guitar : public Instrument {
public:
    void play() override {
        cout << "吉他: 咚咚当当" << endl;
    }
};
 
int main() {
    Instrument* instruments[2];
    instruments[0] = new Piano();
    instruments[1] = new Guitar();
 
    for (int i = 0; i < 2; ++i) {
        instruments[i]->play();
    }
 
    for (int i = 0; i < 3; ++i) {
        delete instruments[i];
    }
    return 0;
}

A

执行代码会输出两行，内容分别为：钢琴: 叮咚叮咚和吉他: 咚咚当当

B

执行代码会输出两行，内容分别为：乐器在演奏声音和乐器在演奏声音

C

代码编译出现错误

D

代码运行出现错误

第 4 题

某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A，B，C，D 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（）。

A

A B

B

A B C

C

A B D

D

B C

第 5 题

假设循环队列数组长度为 N，其中队空判断条件为：front == rear，队满判断条件为：(rear + 1) % N == front，出队对应的操作为：front = (front + 1) % N，入队对应的操作为：rear = (rear + 1) % N。循环队列长度 N=6，初始 front = 1，rear = 1，执行操作序列为：入队，入队，入队，出队，入队，入队，则最终 (front, rear) 的值是（）。

A

(2, 5)

B

(2, 0)

C

(3, 5)

D

(3, 0)

第 6 题

以下函数 check() 用于判断一棵二叉树是否为（）。

bool check(TreeNode* root) {
    if (!root) return true;
 
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (!cur) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;
}

A

满二叉树

B

完全二叉树

C

二叉搜索树

D

平衡二叉树

第 7 题

以下代码实现了二叉树的（）。

void traverse(TreeNode* root) {
    if (!root) return;
    traverse(root->left);
    traverse(root->right);
    cout << root->val << " ";
}

A

前序遍历

B

中序遍历

C

后序遍历

D

层序遍历

第 8 题

下面代码实现了哈夫曼编码，则横线处应填写的代码是（）。

struct Symbol {
	char ch; //字符
	long long freq; //频率
	string code; //哈夫曼编码
};
struct Node {
	long long w; //权值
	int l, r; //左右孩子（节点下标），-1 表示空
	int sym; // 叶子对应符号下标；内部节点为 -1
	Node(long long _w=0, int _l=-1, int _r=-1, int _sym=-1)
	: w(_w), l(_l), r(_r), sym(_sym) {}
};
// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node>& nodes,
					  const vector<int>& leafIdx, int n, int& pA,
					  const vector<int>& internalIdx, int& pB) {
	if (pA < n && (pB >= (int)internalIdx.size() ||
				   nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {
		return leafIdx[pA++];
	}
	else {
		return internalIdx[pB++];
	}
}
// DFS 生成编码（左 0，右 1）
static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {
	if (u == -1) return;
	if (nodes[u].sym != -1) { // 叶子
		sym[nodes[u].sym].code = path;
		return;
	}
	path.push_back('0');
	DFSBuildCodes(nodes[u].l, nodes, sym, path);
	path.pop_back();
	path.push_back('1');
	DFSBuildCodes(nodes[u].r, nodes, sym, path);
	path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n) {
	for (int i = 0; i < n; i++) sym[i].code.clear();
	if (n <= 0) return -1;
	// 只有一个字符：约定编码为 "0"
	if (n == 1) {
		sym[0].code = "0";
		return 0;
	}
	vector<Node> nodes;
	nodes.reserve(2 * n);
	// 1) 建立叶子节点
	vector<int> leafIdx(n);
	for (int i = 0; i < n; i++) {
		leafIdx[i] = (int)nodes.size();
		nodes.push_back(Node(sym[i].freq, -1, -1, i));
	}
	// 2) 叶子按权值排序（A 队列）
	sort(leafIdx.begin(), leafIdx.end(),
		 [&](int a, int b) {
			 if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;
			 return nodes[a].sym < nodes[b].sym; // 稳定一下
		 });
	// B 队列（内部节点下标队列）
	vector<int> internalIdx;
	internalIdx.reserve(n);
	int pA = 0, pB = 0;
	// 3) 合并 n-1 次
	for (int k = 1; k < n; k++) {
		int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
		int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
		int z = (int)nodes.size();
		________________________ // 在此处填写代码
	}
	int root = internalIdx.back();
	// 4) DFS 生成编码
	string path;
	DFSBuildCodes(root, nodes, sym, path);
	return root;
}

A

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
internalIdx.push_back(z);

B

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1));
leafIdx.push_back(z);

C

internalIdx.push_back(z);
nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));

D

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));
leafIdx.push_back(z);

第 9 题

以下关于哈夫曼编码的说法，正确的是（）。

A

哈夫曼编码是定长编码

B

哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀

C

哈夫曼编码一定唯一

D

哈夫曼编码不能用于数据压缩

第 10 题

以下函数实现了二叉排序树（BST）的（）操作。

TreeNode* op(TreeNode* root, int x) {
    if (!root) return new TreeNode(x);
    if (x < root->val)
        root->left = op(root->left, x);
    else
        root->right = op(root->right, x);
    return root;
}

A

查找

B

插入

C

删除

D

遍历

第 11 题

下列代码实现了树的深度优先遍历，则横线处应填入（）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
 
void dfs(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        cout << node->val << " ";
        if (node->right) st.push(node->right);
        ___________________
    }
}

A

if (node->left) st.push(node->left);

B

if (node->left) st.pop(node->left);

C

if (node->left) st.front(node->left);

D

if (node->left) st.push(node->right);

第 12 题

给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 x 的结点，则横线处应填入（）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
 
TreeNode* bfsFind(TreeNode* root, int x) {
    if (!root) return nullptr;
 
    queue<TreeNode*> q;
    q.push(root);
 
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (cur->val == x) return cur;
        __________________
    }
    return nullptr;
}

A

q.push(cur);

B

if (cur->right) q.push(cur->right);

C

if (cur->left)

q.push(cur->left);

if (cur->right)

q.push(cur->right);

D

q.push(cur->left);

q.push(cur->right);

第 13 题

在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（）。

bool find(Node* root, int x) {
    while (root) {
        if (root->val == x) return true;
        root = (x < root->val) ? root->left : root->right;
    }
    return false;
}

A

最坏情况下，访问结点数是 O(log⁡n)

B

最坏情况下，访问结点数是 O(n)

C

无论如何，访问结点数都不超过树高的一半

D

一定比在普通二叉树中搜索快

第 14 题

0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（）。

for each item (w, v):
    for (int j = W; j >= w; --j)
        dp[j] = max(dp[j], dp[j-w] + v);

A

内层 j 必须从小到大，否则会漏解

B

内层 j 必须从大到小，否则同一件物品会被用多次

C

j 从大到小或从小到大都一样

D

只要 dp 初始为 0，方向无所谓

第 15 题

以下关于动态规划的说法中，错误的是（）。

A

动态规划方法通常能列出递推公式。

B

动态规划方法的时间复杂度通常为状态的个数。

C

动态规划方法有递推和递归两种实现形式。

D

对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

CCF GESP 2025年12月认证 C++ 6级