[GESP六级2606] 六级理论
一、单选题（每题 2 分，共 30 分）
第 1 题 下列关于 C++ 中继承和多态的描述中，错误的是（ ）。
{{ select(1) }}
- 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本。
- 基类析构函数常声明为虚函数，以便通过基类指针正确释放派生类对象。
- 派生类可以重写基类中的虚函数。
- 构造函数可以声明为 virtual ，以便在构造对象时实现动态绑定。
第 2 题 下列代码中， d1->work(); 和 d2->work(); 输出不同结果的主要原因是（ ）。
class Device {
public:
virtual void work() {
cout << "Device is working" << endl;
}
virtual ~Device() {}
};
class Printer : public Device {
public:
void work() override {
cout << "Printer is printing" << endl;
}
};
class Scanner : public Device {
public:
void work() override {
cout << "Scanner is scanning" << endl;
}
};
int main() {
Device* d1 = new Printer();
Device* d2 = new Scanner();
d1->work();
d2->work();
delete d1;
delete d2;
return 0;
}
{{ select(2) }}
- Printer 和 Scanner 使用了相同的构造函数。
- work() 是虚函数，且 d1 和 d2 实际指向不同派生类对象，发生动态绑定。
- d1 和 d2 是不同的指针变量。
- 程序中使用了 delete 释放对象。
第 3 题 下面代码在 main() 中有一行会导致编译错误，请找出来。
class Student {
public:
Student(string n, int s) : name(n), score(s) {}
string getName() {
return name;
}
void setScore(int s) {
score = s;
}
private:
string name;
int score;
};
int main() {
Student stu("Tom", 85);
cout << stu.getName(); // ①
stu.setScore(90); // ②
stu.score = 100; // ③
cout << stu.getName(); // ④
return 0;
}
{{ select(3) }}
- 第 ① 行
- 第 ② 行
- 第 ③ 行
- 第 ④ 行
第 4 题 某文本编辑器把用户输入的字符依次压入栈 S 。用户依次输入 X, Y, Z, W 后，连续执行两次撤销操作。每次撤销都会弹出栈顶一个字符。此时栈从栈底到栈顶的内容是（ ）。
{{ select(4) }}
- X Y
- X Y Z
- Y Z
- X Z
第 5 题 假设循环队列数组长度为 N = 7 ，队空判断条件为 front == rear 。入队和出队操作如下：
const int N = 7;
int q[N];
int front = 3, rear = 3;
void enqueue(int x) {
q[rear] = x;
rear = (rear + 1) % N;
}
void dequeue() {
front = (front + 1) % N;
}
依次执行：
enqueue(10);
enqueue(20);
enqueue(30);
dequeue();
enqueue(40);
dequeue();
enqueue(50);
最终 (front, rear) 的值是（ ）。
{{ select(5) }}
- (5, 1)
- (4, 0)
- (5, 0)
- (3, 1)
第 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 == nullptr) {
hasNull = true;
} else {
if (hasNull) return false;
q.push(cur->left);
q.push(cur->right);
}
}
return true;
}
{{ select(6) }}
- 满二叉树
- 完全二叉树
- 二叉搜索树
- 平衡二叉树
第 7 题 以下代码实现了二叉树的哪种遍历方式？
void traverse(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
traverse(root->left);
traverse(root->right);
}
{{ select(7) }}
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
第 8 题 已知一棵二叉树的先序遍历序列为： A B D E H C F G ，中序遍历序列为： D B H E A F C G ，则该二叉树的后序遍历序列是（ ）。
{{ select(8) }}
- D H E B F G C A
- D E H B F G C A
- H D E B F C G A
- D H E B G F C A
第 9 题 有 6 个字符，它们出现的次数分别为：{3,4,78,12,15} ，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL 的值为（ ）。
{{ select(9) }}
- 113
- 119
- 126
- 31
第 10 题 对 n 个不同符号进行哈夫曼编码。若生成的哈夫曼树共有 63 个结点，则 n 的值是（ ）。
{{ select(10) }}
- 31
- 32
- 63
- 64
第 11 题 在格雷码中，相邻两个编码只能有一位不同。若当前编码为 110 ，则它的下一个编码不可能是（ ）。
{{ select(11) }}
- 010
- 111
- 100
- 001
第 12 题 给定一棵二叉树，采用广度优先搜索 BFS 返回其右视图，其中右视图中的每个节点都是该层最右侧的节点。横线处应填写（ ）。
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
TreeNode* node = q.front();
q.pop();
__________________________
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return result;
}
{{ select(12) }}
- if (i == 0) result.push_back(node->val);
- if (i == sz - 1) result.push_back(node->val);
- result.push_back(q.front()->val);
- if (node->right) result.push_back(node->right->val);
第 13 题 下面代码实现二叉搜索树的插入操作。假设树中不存在重复值，横线处应填写（ ）。
TreeNode* insertNode(TreeNode* root, int x) {
if (root == nullptr) {
return new TreeNode(x);
}
if (x < root->val) {
__________________________
} else {
root->right = insertNode(root->right, x);
}
return root;
}
{{ select(13) }}
- root->left = insertNode(root->left, x);
- root = insertNode(root->left, x);
- root->right = insertNode(root->left, x);
- insertNode(root->left, x);
第 14 题 给定一个整数数组 a ，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数 choose(vector& a) 返回能够得到的最大总和，则横线处应填写（ ）。
int choose(vector<int>& a) {
if (a.empty()) return 0;
int n = a.size();
if (n == 1) return a[0];
vector<int> dp(n, 0);
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for (int i = 2; i < n; ++i) {
dp[i] = __________________________;
}
return dp[n - 1];
}
{{ select(14) }}
- dp[i - 1] + a[i]
- max(dp[i - 1], dp[i - 2] + a[i])
- max(dp[i - 2], a[i])
- dp[i - 1] + dp[i - 2]
第 15 题 下面代码实现 0/1 背包的一维动态规划。第 i 个物品重量为 wt[i] ，价值为 val[i] ，背包容量为 W 。横线处应填写（ ）。
int knapsack(int W, vector<int>& wt, vector<int>& val) {
int n = wt.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; ++i) {
for (int w = W; w >= wt[i]; --w) {
__________________________
}
}
return dp[W];
}
{{ select(15) }}
- dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
- dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);
- dp[w] = dp[w] + val[i];
- dp[w - wt[i]] = max(dp[w], val[i]);
二、判断题（每题 2 分，共 20 分）
第 16 题 C++ 中构造函数可以声明为虚函数，从而实现运行时多态。 {{ select(16) }}
- 正确
- 错误
第 17 题 通过指向 Base 的指针删除 Derived 对象时，一定会先调用 Derived 的析构函数，再调用 Base 的析构函数。
#include <iostream>
using namespace std;
class Base {
public:
~Base() {
cout << "Base destructor" << endl;
}
};
class Derived : public Base {
public:
~Derived() {
cout << "Derived destructor" << endl;
}
};
int main() {
Base* p = new Derived();
delete p;
return 0;
}
{{ select(17) }}
- 正确
- 错误
第 18 题 在 C++ STL 中， stack 的 pop() 函数会返回栈顶元素并将其删除。
{{ select(18) }}
- 正确
- 错误
第 19 题 程序运行后会输出 2 。
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.pop();
cout << q.front() << endl;
return 0;
}
{{ select(19) }}
- 正确
- 错误
第 20 题 下列函数试图将整数 x 插入到一棵二叉搜索树中。假设二叉搜索树满足如下性质：对于任意结点，左子树中所有结点的值均小于该结点的值，右子树中所有结点的值均大于或等于该结点的值。判断该函数是否能够在插入后保持二叉搜索树性质。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertNode(TreeNode* root, int x) {
if (root == nullptr) {
return new TreeNode(x);
}
if (x < root->val) {
root->right = insertNode(root->right, x);
} else {
root->left = insertNode(root->left, x);
}
return root;
}
{{ select(20) }}
- 正确
- 错误
第 21 题 哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。
{{ select(21) }}
- 正确
- 错误
第 22 题 若用数组按层序存储完全二叉树，且根节点下标为 0 ，则下标为 i 的节点左孩子下标为 2 * i + 1 ，右孩子下标为 2 * i + 2 。
{{ select(22) }}
- 正确
- 错误
第 23 题 以下代码可以正确地按层换行输出二叉树的节点值。
void printByLevel(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
for (int i = 0; i < q.size(); ++i) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
cout << endl;
}
}
{{ select(23) }}
- 正确
- 错误
第 24 题 使用栈非递归实现二叉树前序遍历时，若希望先访问左子树，通常应先将右孩子入栈，再将左孩子入栈。
{{ select(24) }}
- 正确
- 错误
第 25 题 动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。
{{ select(25) }}
- 正确
- 错误
