#GESP202512C6T1. 单选题（每题 2 分，共 30 分）

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

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

第 1 题 在面向对象编程中,下列关于 虚函数 的描述中,错误的是( )。 {{ select(1) }}

  • 虚函数用于支持运行时多态
  • 通过基类指针调用虚函数时,会根据对象实际类型决定调用版本
  • 构造函数可以声明为虚函数以支持多态
  • 基类析构函数常声明为虚函数以避免资源泄漏

第 2 题 执行如下代码,会输出 钢琴:叮咚叮咚 和 吉他:咚咚当当。这体现了面向对象编程的( )特性。

class Instrument {
public:
    virtual void play() {
        cout << "乐器在演奏声音" << endl;
    }
    virtual ~Instrument() {}
};

class Piano : public Instrument {
public:
    void play() override {
        cout << "钢琴:叮咚叮咚" << endl;
    }
};

class Guitar : public Instrument {
public:
    void play() override { 
        cout << "吉他:咚咚当当" << endl;
    }
};

int main() {
    Instrument* instruments[2]; 
    instruments[0] = new Piano();
    instruments[1] = new Guitar();
    for (int i = 0; i < 2; ++i) {
        instruments[i]->play();
    }
    for (int i = 0; i < 2; ++i) {
        delete instruments[i];
    }
    return 0;
}

{{ select(2) }}

  • 继承
  • 封装
  • 多态
  • 链接

第 3 题 关于以下代码,说法正确的是( )。

class Instrument { 
public:
    void play() {
        cout << "乐器在演奏声音" << endl;
    }
    virtual ~Instrument() {}
};

class Piano : public Instrument {
public:
    void play() override { 
        cout << "钢琴:叮咚叮咚" << endl;
    }
};

class Guitar : public Instrument {
public:
    void play() override { 
        cout << "吉他:咚咚当当" << endl;
    }
};

int main() {
    Instrument* instruments[2]; 
    instruments[0] = new Piano();
    instruments[1] = new Guitar();
    for (int i = 0; i < 2; ++i) {
        instruments[i]->play(); 
    }
    for (int i = 0; i < 2; ++i) {
        delete instruments[i]; 
    }
    return 0;
}

{{ select(3) }}

  • 执行代码会输出两行,内容分别为:钢琴:叮咚叮咚 和 吉他:咚咚当当
  • 执行代码会输出两行,内容分别为:乐器在演奏声音 和 乐器在演奏声音
  • 代码编译出现错误
  • 代码运行出现错误

第 4 题 某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A , B , C , D 后,用户按了两次撤销(每次撤销,弹出栈顶一个字符)。此时栈从栈底到栈顶的内容是:( )。 {{ select(4) }}

  • A B
  • A B C
  • A B D
  • B C

第 5 题 假设循环队列数组长度为 N ，其中队空判断条件为： front == rear ，队满判断条件为： (rear + 1) % N == front ，出队对应的操作为： front = (front + 1) % N ，入队对于的操作为： rear = (rear + 1) % N 。循环队列长度 N = 6 ，初始 front = 1 , rear = 1 ，执行操作序列为：入队, 入队, 入队, 出队, 入队, 入队， 则最终 (front, rear) 的值是（ ）。 {{ select(5) }}

  • (2, 5)
  • (2, 0)
  • (3, 5)
  • (3, 0)

第 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) { 
            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) return;
    traverse(root->left); 
    traverse(root->right); 
    cout << root->val << " ";
}

{{ select(7) }}

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

第 8 题 下面代码实现了哈夫曼编码,则横线处应填写的代码是( )。

struct Symbol
{
    char ch;        // 字符
    long long freq; // 频率
    string code;    // 哈夫曼编码
};
struct Node
{
    long long w; // 权值
    int l, r;    // 左右孩子（节点下标），-1 表示空
    int sym;     // 叶子对应符号下标；内部节点为 -1
    Node(long long _w = 0, int _l = -1, int _r = -1, int _sym = -1)
        : w(_w), l(_l), r(_r), sym(_sym) {}
};
// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node> &nodes,
                      const vector<int> &leafIdx, int n, int &pA,
                      const vector<int> &internalIdx, int &pB)
{
    if (pA < n && (pB >= (int)internalIdx.size() ||
                   nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w))
    {
        return leafIdx[pA++];
    }
    else
    {
        return internalIdx[pB++];
    }
}
// DFS 生成编码（左 0，右 1）
static void DFSBuildCodes(int u, const vector<Node> &nodes, Symbol sym[], string &path)
{
    if (u == -1)
        return;
    if (nodes[u].sym != -1)
    { // 叶子
        sym[nodes[u].sym].code = path;
        return;
    }
    path.push_back('0');
    DFSBuildCodes(nodes[u].l, nodes, sym, path);
    path.pop_back();
    path.push_back('1');
    DFSBuildCodes(nodes[u].r, nodes, sym, path);
    path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n)
{
    for (int i = 0; i < n; i++)
        sym[i].code.clear();
    if (n <= 0)
        return -1;
    // 只有一个字符：约定编码为 "0"
    if (n == 1)
    {
        sym[0].code = "0";
        return 0;
    }
    vector<Node> nodes;
    nodes.reserve(2 * n);
    // 1) 建立叶子节点
    vector<int> leafIdx(n);
    for (int i = 0; i < n; i++)
    {
        leafIdx[i] = (int)nodes.size();
        nodes.push_back(Node(sym[i].freq, -1, -1, i));
    }
    // 2) 叶子按权值排序（A 队列）
    sort(leafIdx.begin(), leafIdx.end(),
         [&](int a, int b)
         {
             if (nodes[a].w != nodes[b].w)
                 return nodes[a].w < nodes[b].w;
             return nodes[a].sym < nodes[b].sym; // 稳定一下
         });
    // B 队列（内部节点下标队列）
    vector<int> internalIdx;
    internalIdx.reserve(n);
    int pA = 0, pB = 0;
    // 3) 合并 n-1 次
    for (int k = 1; k < n; k++)
    {
        int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
        int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
        int z = (int)nodes.size();
        ________________________ // 在此处填写代码
    }
    int root = internalIdx.back();
    // 4) DFS 生成编码
    string path;
    DFSBuildCodes(root, nodes, sym, path);
    return root;
}

{{ select(8) }}

  • nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); internalIdx.push_back(z);
  • nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); leafIdx.push_back(z);
  • nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); internalIdx.push_back(z);
  • nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); leafIdx.push_back(z);

第 9 题 以下关于哈夫曼编码的说法,正确的是( )。 {{ select(9) }}

  • 哈夫曼编码是定长编码
  • 哈夫曼编码中,没有任何一个字符的编码是另一个字符编码的前缀
  • 哈夫曼编码一定唯一
  • 哈夫曼编码不能用于数据压缩

第 10 题 以下函数实现了二叉排序树(BST)的( )操作。

TreeNode* op(TreeNode* root, int x) { 
    if (!root) return new TreeNode(x);
    if (x < root->val) 
        root->left = op(root->left, x);
    else
        root->right = op(root->right, x);
    return root; 
}

{{ select(10) }}

  • 查找
  • 插入
  • 删除
  • 遍历

第 11 题 下列代码实现了树的深度优先遍历,则横线处应填入( )。

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void dfs(TreeNode *root)
{
    if (!root)
        return;
    stack<TreeNode *> st;
    st.push(root);
    while (!st.empty())
    {
        TreeNode *node = st.top();
        st.pop();
        cout << node->val << " ";
        if (node->right)
            st.push(node->right);
        ________________________
    }
}

{{ select(11) }}

  • if (node->left) st.push(node->left);
  • if (node->left) st.pop(node->left);
  • if (node->left) st.front(node->left);
  • if (node->left) st.push(node->right);

第 12 题 给定一棵普通二叉树(节点值没有大小规律),下面代码判断是否存在值为 x 的结点,则横线处应填入( )。

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode *bfsFind(TreeNode *root, int x)
{
    if (!root)
        return nullptr;
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *cur = q.front();
        q.pop();
        if (cur->val == x)
            return cur;
        ________________________
    }
    return nullptr;
}

{{ select(12) }}

  • q.push(cur);
  • if (cur->right) q.push(cur->right);
  • if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right);
  • q.push(cur->left); q.push(cur->right);

第 13 题 在二叉排序树(Binary Search Tree, BST)中,假设节点值互不相同。给定如下搜索函数,以下说法一定正确的是( )。

bool find(Node* root, int x) {
    while (root) { 
        if (root->val == x) return true;
        root = (x < root->val) ? root->left : root->right;
    } 
    return false;
}

{{ select(13) }}

  • 最坏情况下,访问结点数是 O(log⁡n)O(\log n)
  • 最坏情况下,访问结点数是 O(n)O(n)
  • 无论如何,访问结点数都不超过树高的一半
  • 一定比在普通二叉树中搜索快

第 14 题 0/1 背包(每件物品最多选一次)问题通常可用一维动态规划求解,核心代码如下。则下面说法正确的是( )。

for each item (w, v):
    for (int j = W; j >= w; --j)
        dp[j] = max(dp[j], dp[j-w] + v);

{{ select(14) }}

  • 内层 j 必须从小到大,否则会漏解
  • 内层 j 必须从大到小,否则同一件物品会被用多次
  • j 从大到小或从小到大都一样
  • 只要 dp 初始为 0 ,方向无所谓

第 15 题 以下关于动态规划的说法中,错误的是( )。 {{ select(15) }}

  • 动态规划方法通常能够列出递推公式。
  • 动态规划方法的时间复杂度通常为状态的个数。
  • 动态规划方法有递推和递归两种实现形式。
  • 对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。
  1. Language
  2. 兼容模式
  3. 主题
  2. 晋ICP备2025064124号
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.0 Community