202509 GESP认证 C++编程六级真题试卷

单选题共 15 题

下列关于类的说法，错误的是( )。

A 构造函数不能声明为虚函数，但析构函数可以。 B 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。 C 静态方法属于类而不是某个具体对象，因此推荐用类名::方法(...) 调用。 D 不管基类的析构函数是否是虚函数，都可以通过基类指针/引用正确删除派生类对象。

假设变量 veh 是类 Car 的一个实例，我们可以调用 veh.move() ，是因为面向对象编程有（）性质。

class Vehicle {
private:
    string brand;
public:
    Vehicle(string b) : brand(b) {}
    void setBrand(const string& b) { brand = b; }
    string getBrand() const { return brand; }
    void move() const {
        cout << brand << " is moving..." << endl;
    }
};
class Car : public Vehicle {
private:
    int seatCount;
public:
    Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
    void showInfo() const {
        cout << "This car is a " << getBrand()
            << " with " << seatCount << " seats." << endl;
    }
};

A 继承 (Inheritance) B 封装 (Encapsulation) C 多态 (Polymorphism) D 链接 (Linking)

下面C++代码中 v1 和 v2 调用了相同接口 move() ，但输出结果不同，这体现了面向对象编程的（）特性。

class Vehicle {
private:
    string brand;
public:
    Vehicle(string b) : brand(b) {}
    void setBrand(const string& b) { brand = b; }
    string getBrand() const { return brand; }
    virtual void move() const {
        cout << brand << " is moving..." << endl;
    }
};
class Car : public Vehicle {
private:
    int seatCount;
public:
    Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
    void showInfo() const {
        cout << "This car is a " << getBrand()
            << " with " << seatCount << " seats." << endl;
    }
    void move() const override {
        cout << getBrand() << " car is driving on the road!" << endl;
    }
};
class Bike : public Vehicle {
public:
    Bike(string b) : Vehicle(b) {}
    void move() const override {
        cout << getBrand() << " bike is cycling on the path!" << endl;
    }
};
int main() {
    Vehicle* v1 = new Car("Toyota", 5);
    Vehicle* v2 = new Bike("Giant");
    v1->move();
    v2->move();
    delete v1;
    delete v2;
    return 0;
}

A 继承 (Inheritance) B 继承 (Inheritance) C 多态 (Polymorphism) D 链接 (Linking

栈的操作特点是（）。

A 先进先出 B 先进后出 C 随机访问 D 双端进出

循环队列常用于实现数据缓冲。假设一个循环队列容量为 5 （即最多存放 4 个元素，留一个位置区分空与满），依次进行操作：入队数据1，2，3，出队1个数据，再入队数据4和5，此时队首到队尾的元素顺序是（）。

A [2, 3, 4, 5] B [1, 2, 3, 4] C [3, 4, 5, 2] D [2, 3, 5, 4]

以下函数 createTree() 构造的树是什么类型？

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* createTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

A 满二叉树 B 完全二叉树 C 二叉排序树 D 其他都不对

已知二叉树的中序遍历是 [D, B, E, A, F, C]，先序遍历是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（）。

A [D, E, B, F, C, A] B [D, B, E, F, C, A] C [D, E, B, C, F, A] D [B, D, E, F, C, A]

完全二叉树可以用数组连续高效存储，如果节点从 1 开始编号，则对有两个孩子节点的节点 i ，（）。

A 左孩子位于 2i ，右孩子位于 2i+1 B 完全二叉树的叶子节点可以出现在最后一层的任意位置 C 所有节点都有两个孩子 D 左孩子位于 2i+1 ，右孩子位于 2i+2

设有字符集 {a, b, c, d, e, f} ，其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响正确性）。

A a: 00；b: 01；c: 10；d: 110；e: 111；f: 0 B a: 1100；b: 1101；c: 100；d: 101；e: 111；f: 0 C a: 000；b: 001；c: 01；d: 10；e: 110；f: 111 D a: 10；b: 01；c: 100；d: 101；e: 111；f: 0

10.

下面C++代码生成格雷编码，则横线上应填写（）。

vector<string> grayCode(int n) {
    if (n == 0) return {"0"};
    if (n == 1) return {"0", "1"};
    vector<string> prev = grayCode(n-1);
    vector<string> result;
    for (string s : prev) {
        result.push_back("0" + s);
    }
    for (_______________) { // 在此处填写代码
        result.push_back("1" + prev[i]);
    }
    return result;
}

A int i = 0; i < prev.size(); i++ B int i = prev.size()-1; i >= 0; i-- C auto s : prev D int i = prev.size()/2; i < prev.size(); i++

11.

请将下列树的深度优先遍历C++代码补充完整，横线处应填入（）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void dfs(TreeNode* root) {
    if (!root) return;
    ______<TreeNode*> temp; // 在此处填写代码
    temp.push(root);
    while (!temp.empty()) {
        TreeNode* node = temp.top();
        temp.pop();
        cout << node->val << " ";
        if (node->right) temp.push(node->right);
        if (node->left) temp.push(node->left);
    }
}

A vector B list C queue D stack

12.

令 n 是树的节点数目，下列C++代码实现了树的广度优先遍历，其时间复杂度是（）。

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

O(n)

O(log n)

O(n²)

O(2ⁿ)

13.

在二叉排序树（Binary Search Tree, BST）中查找元素 50 ，从根节点开始：若根值为 60 ，则下一步应去搜索：

左子树

右子树

随机

根节点

14.

删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（），其中 findMax 和 findMin 分别为寻找树的最大值和最小值的函数。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    }
    else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* temp = ____________; // 在此处填写代码
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

A root->left B root->right C findMin(root->right) D findMax(root->left)

15.

给定 n个物品和一个最大承重为 W的背包，每个物品有一个重量 wt[i]和 val[i]价值，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 W，则横线上应填写（）。

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<int> dp(W+1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= wt[i]; --w) {
            ________________________ // 在此处填写代码
        }
    }
    return dp[W];
}

A dp[w] = max(dp[w], dp[w] + val[i]); B dp[w] = dp[w - wt[i]] + val[i]; C dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]); D dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

判断题共 10 题

当基类可能被多态使用，其析构函数应该声明为虚函数。

A 正确 B 错误

哈夫曼编码是最优前缀码，且编码结果唯一。

A 正确 B 错误

一个含有 100个节点的完全二叉树，高度为 8 。

A 正确 B 错误

在 C++ STL 中，栈（ std::stack ）的 pop 操作返回栈顶元素并移除它。

A 正确 B 错误

循环队列通过模运算循环使用空间。

A 正确 B 错误

一棵有 n个节点的二叉树一定有 n-1 条边。

A 正确 B 错误

以下C++代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 4 2 5 1 3 6 。

// 1
// / \
// 2 3
// / \ \
// 4 5 6
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr || !st.empty()) {
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

A 正确 B 错误

下面代码实现的二叉排序树的查找操作时间复杂度是 O(h)，其中 h 为树高。

TreeNode* searchBST(TreeNode* root, int val) {
    while (root && root->val != val) {
        root = (val < root->val) ? root->left : root->right;
    }
    return root;
}

A 正确 B 错误

下面C++代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 O(2ⁿ)。

int fib_dp(int n) {
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

A 正确 B 错误

10.

有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下C++代码能找到小猴子吃到最甜的香蕉组合。

// bananas：香蕉的甜度
void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
    vector<int> selected;
    int i = bananas.size() - 1;
    while (i >= 0) {
        if (i == 0) {
            selected.push_back(0);
            break;
        }
        if (dp[i] == dp[i-1]) {
            i--;
        } else {
            selected.push_back(i);
            i -= 2;
        }
    }
    reverse(selected.begin(), selected.end());
    cout << "小猴子吃了第: ";
    for (int idx : selected)
        cout << idx+1 << " ";
    cout << "个香蕉" << endl;
}
int main() {
    vector<int> bananas = {1, 2, 3, 1}; // 每个香蕉的甜
    vector<int> dp(bananas.size());
    dp[0] = bananas[0];
    dp[1] = max(bananas[0], bananas[1]);
    for (int i = 2; i < bananas.size(); i++) {
        dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
    }
    findSelectedBananas(bananas, dp);
    return 0;
}

A 正确 B 错误

问答题共 2 题

试题名称：划分字符串

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 题目描述

小 A 有一个由 n个小写字母组成的字符串 s。他希望将 s划分为若干个子串，使得子串中每个字母至多出现一次。

例如，对于字符串 street 来说， str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串tree 中 e 出现了两次。

额外地，小 A 还给出了价值 a₁,a₂....a_n，表示划分后长度为 i 的子串价值为 a_i。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？

3.1.2 输入格式

第一行，一个正整数 n ，表示字符串的长度。

第二行，一个包含 n个小写字母的字符串。

第三行， n个正整数a₁,a₂....a_n ，表示不同长度的子串价值。

3.1.3 输出格式

一行，一个整数，表示划分后子串价值之和的最大值。

3.1.4 样例

3.1.4.1 输入样例 1

street

2 1 7 4 3 3

3.1.4.2 输出样例 1

3.1.4.3 输入样例 2

blossoms

1 1 2 3 5 8 13 21

3.1.4.4 输出样例 2

3.1.5 数据范围

试题名称：货物运输

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

A 国有 n 座城市，依次以1,2,...n 编号，其中 1 号城市为首都。这 n 座城市由 n-1 条双向道路连接，第 i 条道路（ 1=<i<=n）连接编号为 u_i,v_i的两座城市，道路长度为L_i。任意两座城市间均可通过双向道路到达。

现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。

3.2.2 输入格式

第一行，一个正整数 n，表示 A 国的城市数量。

接下来 n-1 行，每行三个整数 u_i,v_{i,L_i}，表示一条双向道路连接编号为u_i,v_i 的两座城市，道路长度为 L_i。

3.2.3 输出格式

一行，一个整数，表示你设计的路线所经过的道路长度总和。

3.2.4 样例

3.2.4.1 输入样例 1

1 2 6

1 3 1

3 4 5

3.2.4.2 输出样例 1

3.2.4.3 输入样例 2

1 2 1

2 3 1

3 4 1

7 6 1

6 5 1

5 1 1

3.2.4.4 输出样例 2

3.2.5 数据范围

提交试卷

退出练习

正在提交