二、判断题

第 1 题 下面定义了一个表示二维坐标点的类 Point , 并提供了一个带参数的构造函数,但第 ② 行 Point b; 会调用编译器自动生成的默认构造函数,将b.x 和 b.y 被初始化为 0.0,程序可以正常编译运行。

class Point { 
public: 
    double x, y;
    Point(double px, double py) : x(px), y(py) {}
    void print() { 
        cout << "(" << x << ", " << y << ")";
    }
};
int main() {
    Point a(3.0, 4.0); // ① ; 
    Point b;            // ②
    a.print();
}

{{ select(1) }}

• 对
• 错

第 2 题 C++ 中的继承支持单继承和多继承,但子类无法直接访问父类的私有成员。 {{ select(2) }}

• 对
• 错

第 3 题 对如下结构的树,执行travel 函数,输出结果是 1 2 3 4 5 。

       1
     /   \
     2   3
   /   \
  4    5

struct Node {
    int val; 
    Node *left, *right; 
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
void travel(Node* root) {
    if (!root) return;
    stack<Node*> s; 
    s.push(root);
    while (!s.empty()) { 
        Node* cur = s.top(); 
        s.pop(); 
        cout << cur->val << " ";
    } 
} 
if (cur->right) s.push(cur->right); 
if (cur->left) s.push(cur->left);

{{ select(3) }}

• 对
• 错

第 4 题 若所有字符出现频率相同,则哈夫曼编码一定会得到完全二叉树。 {{ select(4) }}

• 对
• 错

第 5 题 哈夫曼编码是一种变长的前缀编码,在解码时不需要额外的分隔符就能唯一还原,这是因为在哈夫曼树中,任何一个字符的叶子结点都不会成为另一个字符结点的祖先。 {{ select(5) }}

• 对
• 错

第 6 题 在 C++ 中使用一维数组 vector tree 存储按层序遍历的完全二叉树时,若根节点存储在 tree[0] ,则对于任意非空节点 tree[i] ,其右孩子(如果存在)必然位于 tree[2 * i + 2] 。 {{ select(6) }}

• 对
• 错

第 7 题 在 C++ 中使用栈来非递归地实现二叉树的前序遍历时,为了保证遍历顺序正确,在处理完当前结点后,应该先将该结点的左孩子压入栈中,然后再将右孩子压入栈中。 {{ select(7) }}

• 对
• 错

第 8 题 设二叉树共有 n 个结点,函数 preorderTraversal 以下代码的时间复杂度为 (O(n)) ,空间复杂度为 (O(n))

struct TreeNode {
    int val;
    TreeNode* left; 
    TreeNode* right; 
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void preorder(TreeNode *root, vector<int> &res) { 
    if (root == nullptr) {
        return;
        res.push_back(root->val); 
        preorder(root->left, res); 
        preorder(root->right, res);
    }
}
vector<int> preorderTraversal(TreeNode *root) {
    vector<int> res;
    preorder(root, res); 
    return res;
};

{{ select(8) }}

• 对
• 错

第 9 题 下列代码实现了一个0-1背包的一维动态规划代码,内层循环是经典的逆序写法｡若将内层循环改成正序遍历(即 for (int j = w[i]; j <= W; j++) ),仍能得到正确答案。

int main() { 
    int W = 5;
    int w[] = {2, 3, 4};
    int v[] = {10, 1, 1};
    int n = 3;
    int dp[6] = {0}; 
    for (int i = 0; i < n; i++) { 
        for (int j = W; j >= w[i]; j--) { // ￩ 逆序!
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            cout << dp[W]; 
        }
    }
}

{{ select(9) }}

• 对
• 错

第 10 题 在动态规划问题中,状态空间相同且没有重复计算的情况下,“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。 {{ select(10) }}

• 对
• 错