一、单选题（每题 2 分，共 30 分）

第 1 题 下列关于 C++ 中类的描述,正确的是( )｡ {{ select(1) }}

• 如果类没有用户声明的构造函数,那么编译器会隐式声明一个默认构造函数
• 类的析构函数可以被重载,一个类可以有多个析构函数
• 类中的所有成员都必须声明为 public
• 类和结构体在 C++ 中没有区别,包括默认访问权限也相同

第 2 题 下列代码中,s1->draw(); 和 s2->draw(); 输出不同结果的主要原因是( )｡

class Shape { 
public: 
    virtual void draw() {
        cout << "绘制图形" << endl;
    }
    virtual ~Shape() {}
};
class Circle : public Shape {
public:
    void draw() override { 
        cout << "绘制圆形" << endl;
    }
};
class Rectangle : public Shape {
public:
    void draw() override { 
        cout << "绘制矩形" << endl;
    }
};
int main() { 
    Shape* s1 = new Circle(); 
    Shape* s2 = new Rectangle();
    s1->draw();
    s2->draw();
    delete s1;
    delete s2; 
    return 0;
}

{{ select(2) }}

• draw() 是普通成员函数
• Shape 中的 draw() 被声明为虚函数
• Circle 和 Rectangle 中使用了 public 继承
• 指针变量名不同

第 3 题 下面的代码在 main() 中有一行会导致编译错误,请找出来｡

class Pet { 
public:
    Pet(string n, int a) : name(n), age(a) {}
    string getName() { return name; } 
    void birthday() { age++; } 
private: 
    string name;
    int age;
};
int main() {
    Pet cat("奶茶", 2);
    cout << cat.getName(); // ①
    cat.birthday // ②
    cat.name = "大橘" // ③
    cout << cat.getName(); // ④
}

{{ select(3) }}

• 第 ① 行
• 第 ② 行
• 第 ③ 行
• 第 ④ 行

第 4 题 游乐园的过山车每次限坐 4 人,用循环队列管理排队(容量 MAX=5 ,空一格判满)｡下面代码执行后,循环队列是否已满?rear 的值是多少?

const int MAX = 5;
int queue[MAX];
int front = 0, rear = 0;
// 入队 
void enqueue(int x) { 
    queue[rear] = x; 
    rear = (rear + 1) % MAX;
}
// 出队
void dequeue() { 
    front = (front + 1) % MAX;
}
int main() { 
    enqueue(1); 
    enqueue(2); 
    enqueue(3); 
    enqueue(4);
    dequeue(); 
    dequeue(); 
    enqueue(5); 
    enqueue(6);
}

{{ select(4) }}

• 已满,rear = 1
• 未满,rear = 1
• 已满,rear = 2
• 未满,rear = 4

第 5 题 在以下计算机系统应用场景中,最适合使用循环队列的是( )｡ {{ select(5) }}

• 函数调用过程中,保存局部变量和返回地址
• 表达式求值中的运算符优先级处理
• 操作系统中的进程优先级调度(高优先级先执行)
• 生产者和消费者问题中的共享缓冲区

第 6 题 在二叉搜索树(BST)中,若中序遍历的序列为{1, 2, 3, 4, 5},且先序遍历的第一个序列元素为3,则下列说法正确的是( )｡ {{ select(6) }}

• 该树一定是一棵完全二叉树｡
• 元素4和5不可能是兄弟节点｡
• 元素1所在节点的深度可能大于3(根节点深度为1)｡
• 元素2一定是元素1的父节点｡

第 7 题 某二叉树共有10个结点,记为A~J,已知它的先序遍历序列为:A B D H I E C F J G,中序遍历序列为:H D I B E A F J C G,则该二叉树的后序遍历序列是( )｡ {{ select(7) }}

• H I D E B J F G C A
• H I D B E J F G C A
• I H D E B J F G C A
• H I D E B F J G C A

第 8 题 下列关于树的遍历的说法中,正确的一项是( )｡ {{ select(8) }}

• 对任意一棵树进行深度优先遍历,所得序列一定唯一｡
• 已知一棵二叉树的先序遍历和后序遍历序列,可以唯一确定这棵二叉树｡
• 已知一棵二叉树的先序遍历和中序遍历序列,可以唯一确定这棵二叉树｡
• 已知一棵二叉树的先序遍历序列,可以唯一确定这棵二叉树｡

第 9 题 有6 个字符,它们出现的次数分别为:{2, 3, 3, 4, 6, 8} ,现在用哈夫曼编码为这些字符编码,最小加权路径长度WPL(每个字符的出现次数乘以它的编码长度,再把每个字符结果加起来)的值为( )｡ {{ select(9) }}

• 58
• 60
• 62
• 64

第 10 题 对n个不同符号的符号进行哈夫曼编码｡若生成的哈夫曼树共有m个结点,则m的值是()｡ {{ select(10) }}

• 60
• 58
• 57
• 56

第 11 题 关于格雷编码(Gray Code),下列说法正确的是( )｡ {{ select(11) }}

• 格雷编码中,编码位数越多,相邻编码之间变化的位数也越多
• 格雷编码中,相邻两个编码的二进制位恰好有一位不同
• 格雷编码就是把普通二进制编码按位取反后得到的结果
• 格雷编码不能用于数字电路和状态转换的设计中

第 12 题 给定一棵二叉树,采用广度优先搜索 (BFS) 算法,返回右视图所有节点的值｡其中右视图定义为:二叉树的右视图是从树的右侧看过去时可见的节点集合,即右视图中的每个节点都是某一层中最右侧的节点｡

struct TreeNode {
    int val;
    TreeNode* left; 
    TreeNode* right; 
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
vector<int> rightSideView(TreeNode* root) { 
    unordered_map<int, int> rightmostValueAtDepth;
    int max_depth = -1;
    queue<TreeNode*> nodeQueue;
    queue<int> depthQueue; 
    nodeQueue.push(root);
    depthQueue.push(0);
    while (!nodeQueue.empty()) { 
        TreeNode* node = nodeQueue.front(); 
        nodeQueue.pop();
        int depth = depthQueue.front(); 
        depthQueue.pop();
        if (node != NULL) { 
            max_depth = max(max_depth, depth);
            rightmostValueAtDepth[depth] = node->val;
            nodeQueue.push(node->left);
            nodeQueue.push(node->right);
            depthQueue.push(________);
            depthQueue.push(________);
        }
    }
    vector<int> rightView; 
    for (int depth = 0; ________; ++depth) { 
        rightView.push_back(rightmostValueAtDepth[depth]);
    }; 
    return rightView;
}

{{ select(12) }}

• depth、depth、depth < max_depth
• depth + 1、depth + 1、depth <= max_depth
• depth + 1、depth + 1、depth < max_depth
• depth、depth、depth <= max_depth

第 13 题 下列关于树的深度优先搜索(DFS)的说法中,正确的是( )｡ {{ select(13) }}

• 对树进行 DFS 时,一定是按层从上到下依次访问结点
• 对任意一棵树进行 DFS,得到的遍历序列唯一
• 对一棵树进行 DFS 时,常借助递归或栈实现
• DFS 只能用于二叉树,不能用于普通树

第 14 题 小朋友们去邻里拜年,每个家里有不同数量的糖果｡规则是:不能连续进入两个相邻的房子(即不能同时取相邻两家的糖果)｡目标是拿到最多糖果｡以下是代码实现,请补全横线｡

int visit(vector<int>& nums) { 
    if (nums.empty()) { 
        return 0;
    }
    int size = nums.size(); 
    if (size == 1) { 
        return nums[0];
    }
    vector<int> dp = vector<int>(size, 0); 
    dp[0] = nums[0]; 
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < size; i++) { 
        dp[i] = ______; // 在此处填写代码
    } 
    return dp[size - 1];
}

{{ select(14) }}

• dp[i] = dp[i - 1] + nums[i];
• dp[i] = max(dp[i - 1], dp[i - 2] * nums[i]);
• dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
• dp[i] = dp[i - 2] + nums[i];

第 15 题 元宵节晚上,小朋友沿着一条发光石板路前进,每次可向前走 1 块或 2 块石板｡动态规划定义如下: dp[i] = dp[i - 1] + dp[i - 2] ,下面关于 dp[i] 的含义最合适的是( )｡ {{ select(15) }}

• 走到第 i 块石板的不同走法数量
• 走到第 i 块石板时,已经走过的石板总数
• 从第 i 块石板走回起点的最少步数
• 从第 i 块石板走回起点的最大步数