六级(2506)

ID: 1703

客观题

尝试: 1

已通过: 1

难度: 10

上传者:

xiao9di

标签>

GESP

六级

C++ 六级

2025 年 06 ⽉

1 单选题（每题 2 分，共 30 分）

第 1 题下列哪⼀项不是⾯向对象编程的基本特征？

继承
封装
多态
链接

第 2 题 2. 为了让 Dog 类的构造函数能正确地调⽤其⽗类 Animal 的构造⽅法，横线线处应填⼊（）。

class Animal {
public:
    std::string name;

    Animal(std::string str) : name(str) {
            std::cout << "Animal created\n";
        }
    virtual void speak() {
        cout << "Animal speaks" << endl;
    }
};

class Dog : public Animal {
    std::string breed;
public:
    Dog(std::string name, std::string b) : _________________, breed(b) {
            std::cout << "Dog created\n";
        }
    void speak() override {
        cout << "Dog barks" << endl;
    }
};

int main() {
    Animal* p = new Dog("Rex", "Labrador");
    p->speak();
    delete p;
    return 0;
}

Animal(name)
super(name)
Animal::Animal(name)
Animal()

第 3 题代码同上⼀题，代码执⾏结果是（）。

输出 Animal speaks
输出 Dog barks
编译错误
程序崩溃

第 4 题以下关于栈和队列的代码，执⾏后输出是（）。

stack<int> s;
queue<int> q;
for (int i = 1; i <= 3; ++i) {
    s.push(i);
    q.push(i);
}
cout << s.top() << " " << q.front() << endl;

第 5 题在⼀个循环队列中， front 是指向队头的指针， rear 指向队尾的指针，队列最⼤容量为 maxSize 。判断队列已满的条件是（）。

rear == front
(rear + 1) % maxSize == front
(rear - 1 + maxSize) % maxSize == front
(rear - 1) == front

第 6 题（）只有最底层的节点未被填满，且最底层节点尽量靠左填充。

完美⼆叉树
完全⼆叉树
完满⼆叉树
平衡⼆叉树

第 7 题在使⽤数组表⽰完全⼆叉树时，如果⼀个节点的索引为 $i$ （从 0 开始计数），那么其左⼦节点的索引通常是（）。

$(i-1)/2$
$i+1$
$i*2$
$2 * i + 1$

第 8 题已知⼀棵⼆叉树的前序遍历序列为 GDAFEMHZ ，中序遍历序列为 ADFGEHMZ ，则其后序遍历序列为（）。

ADFGEHMZ
ADFGHMEZ
AFDGEMZH
AFDHZMEG

第 9 题设有字符集 {a, b, c, d, e}，其出现频率分别为 {5, 8, 12, 15, 20}，得到的哈夫曼编码为（）。

//A:
a: 010
b: 011
c: 00
d: 10
e: 11

//B:
a: 00
b: 10
c: 011
d: 100
e: 111

//C:
a: 10
b: 01
c: 011
d: 100
e: 111

//D:
a: 100
b: 01
c: 011
d: 100
e: 00

第 10 题 3位格雷编码中，编码 101 之后的下⼀个编码不可能是（）。

第 11 题请将下列 C++ 实现的深度优先搜索（DFS）代码补充完整，横线处应填⼊（）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void dfs(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    __________________________
}
//A:
result.push_back(root->val);
dfs(root->left);
dfs(root->right);

//B:
result.push_back(root->left->val);
dfs(root->right);
dfs(root->left);

//C:
result.push_back(root->left->val);
dfs(root->left);
dfs(root->right);

//D:
result.push_back(root->right->val);
dfs(root->right);
dfs(root->left);

第 12 题给定⼀个⼆叉树，返回每⼀层中最⼤的节点值，结果以数组形式返回，横线处应填⼊（）。

#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();

第 13 题下⾯代码实现⼀个⼆叉排序树的插⼊函数（没有相同的数值），横线处应填⼊（）。

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);

第 14 题以下关于动态规划算法特性的描述，正确的是（）。

⼦问题相互独⽴，不重叠
问题包含重叠⼦问题和最优⼦结构
只能从底⾄顶迭代求解
必须使⽤递归实现，不能使⽤迭代

第 15 题给定个物品和⼀个最⼤承重为的背包，每个物品有⼀个重量和价值，每个物品只能选择放或不放。⽬标是选择若⼲个物品放⼊背包，使得总价值最⼤，且总重量不超过。关于下⾯代码，说法正确的是（）。

int knapsack1D(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) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

该算法不能处理背包容量为 0 的情况
外层循环 i 遍历背包容量，内层遍历物品
从⼤到⼩遍历 w 是为了避免重复使⽤同⼀物品
这段代码计算的是最⼩重量⽽⾮最⼤价值

2 判断题（每题 2 分，共 20 分）

第 1 题构造函数可以被声明为 virtual。

第 2 题给定⼀组字符及其出现的频率，构造出的哈夫曼树是唯⼀的。

第 3 题为了实现⼀个队列，使其出队操作（ pop ）的时间复杂度为 $O(1)$ 并且避免数组删除⾸元素的 $O(n)$ 问题，⼀种常见且有效的⽅法是使⽤环形数组，通过调整队⾸和队尾指针来实现。

第 4 题对⼀棵⼆叉排序树进⾏中序遍历，可以得到⼀个递增的有序序列。

第 5 题如果⼆叉搜索树在连续的插⼊和删除操作后，所有节点都偏向⼀侧，导致其退化为类似于链表的结构，这时其查找、插⼊、删除操作的时间复杂度会从理想情况下的 $O(logn)$ 退化到 $O(n log n)$ 。

第 6 题执⾏下列代码， my_dog.name 的最终值是 Charlie 。

class Dog {
public:
    std::string name;
    Dog(std::string str) : name(str) {}
};

int main() {
    Dog my_dog("Buddy");
    my_dog.name = "Charlie";
    return 0;
}

第 7 题下列 C++ 代码可以成功编译，并且⼦类 Child 的实例能通过其成员函数访问⽗类 Parent 的属性 value 。

class Parent {
private:
    int value = 100;
};
class Child : public Parent {
public:
    int get_private_val() {
        return value; // 尝试访问父类的私有成员
    }
};

第 8 题下列代码中的 tree 向量，表⽰的是⼀棵完全⼆叉树 ( -1 代表空节点)按照层序遍历的结果。

#include <vector>
std::vector<int> tree = {1, 2, 3, 4, -1, 6, 7};

第 9 题在树的深度优先搜索（DFS）中，使⽤栈作为辅助数据结构以实现“先进后出”的访问顺序。

第 10 题下⾯代码采⽤动态规划求解零钱兑换问题：给定 $n$ 种硬币，第 𝐠种硬币的⾯值为 𝑜𝑛𨁛𝐠− 1] ，⽬标⾦额为𝑚𨐠，每种硬币可以重复选取，求能够凑出⽬标⾦额的最少硬币数量；如果不能凑出⽬标⾦额，返回 -1 。

int coinChangeDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a)
                dp[a] = dp[a];
            else
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

#1703. 六级(2506)

状态

开发

支持

#1703. 六级(2506)

六级(2506)

状态

开发

支持

登录