单选题库 - E心E意

EXY-SC-1350

第 151 题

给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 $wt[i]$ 和价值 $val[i]$，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$，则横线上应填写（）。

int knapsack(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) {
            _______________________  // 在此处填写代码
        }
    }
    return dp[W];
}

A

dp[w] = max(dp[w], dp[w] + val[i]);

B

dp[w] = dp[w - wt[i]] + val[i];

C

dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);

D

dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

语言： C++

GESP真题六级

2025.9

单选题号： 15

EXY-SC-1349

第 152 题

删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（），其中 findMax 和 findMin 分别为寻找树的最大值和最小值的函数。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
 
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    }
    else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* temp = ___________;  // 在此处填写代码
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

A

root->left

B

root->right

C

findMin(root->right)

D

findMax(root->left)

语言： C++

GESP真题六级

2025.9

单选题号： 14

EXY-SC-1348

第 153 题

在二叉排序树（Binary Search Tree, BST）中查找元素 $50$，从根节点开始：若根值为 $60$，则下一步应去搜索：

A

左子树

B

右子树

C

随机

D

根节点

语言： C++

GESP真题六级

2025.9

单选题号： 13

EXY-SC-1347

第 154 题

令 $n$ 是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是（）。

void bfs(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

A

$O(n)$

B

$O(\log n)$

C

$O(n^2)$

D

$O(2^n)$

语言： C++

GESP真题六级

2025.9

单选题号： 12

EXY-SC-1346

第 155 题

请将下列树的深度优先遍历代码补充完整，横线处应填入（）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
 
void dfs(TreeNode* root) {
    if (!root) return;
    ______<TreeNode*> temp;        // 在此处填写代码
    temp.push(root);
    while (!temp.empty()) {
        TreeNode* node = temp.top();
        temp.pop();
        cout << node->val << " ";
        if (node->right) temp.push(node->right);
        if (node->left) temp.push(node->left);
    }
}

A

vector

B

list

C

queue

D

stack

语言： C++

GESP真题六级

2025.9

单选题号： 11