单选题库 - E心E意

EXY-SC-1110

第 391 题

阅读以下用动态规划解决的 0-1 背包问题的函数，假设背包的容量 $W$ 是 $10kg$，假设输入 $4$ 个物品的重量 $weights$ 分别为 $1,3,4,6$（单位为 $kg$），每个物品对应的价值 $values$ 分别为 $20,30,50,60$，则函数的输出为（）。

#include <iostream>
#include <vector>
using namespace std;
 
// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
 
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
 
    return dp[n][W];
}

A

90

B

100

C

110

D

140

语言： C++

GESP真题六级

2024.9

单选题号： 15

EXY-SC-1109

第 392 题

动态规划通常用于解决（）。

A

无法分解的问题

B

可以分解成相互依赖的子问题的问题

C

可以通过贪心算法解决的问题

D

只能通过递归解决的问题

语言： C++

GESP真题六级

2024.9

单选题号： 14

EXY-SC-1108

第 393 题

对上题中的二叉搜索树，当输入数组为 $[5,3,7,2,4,6,8]$ 时，构建二叉搜索树，并采用如下代码实现的遍历方式，得到的输出是（）。

#include <iostream>
using namespace std;
 
// 遍历二叉搜索树，输出结点值
void traversal(tree_node* root) {
    if (root == nullptr) {
        return;
    }
 
    traversal(root->left);
    cout << root->val << " ";
    traversal(root->right);
}

A

5 3 7 2 4 6 8

B

2 3 4 5 6 7 8

C

2 4 3 6 8 7 5

D

2 4 3 5 6 7 8

语言： C++

GESP真题六级

2024.9

单选题号： 13

EXY-SC-1107

第 394 题

二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组（假设数组中没有数值相等的元素），构造一个对应的二叉搜索树，横线上应填写（）：

// 定义二叉树的结点结构
struct tree_node {
    int val;
    tree_node* left;
    tree_node* right;
 
    tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {
    if (root == nullptr) {
        return new tree_node(val);
    }
 
    ________________________ // 在此处填入代码
 
    return root;
}
 
// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {
    tree_node* root = nullptr;
 
    for (int i = 0; i < size; ++i) {
        root = insert(root, arr[i]);
    }
 
    return root;
}

A

if (val < root->val)
    root->left = insert(root->left, val);
else
    root->right = insert(root->right, val);

B

if (val > root->val)
    root->left = insert(root->left, val);
else
    root->right = insert(root->right, val);

C

if (val < root->val)
    root->left = insert(root, val);
else
    root->right = insert(root, val);

D

if (val > root->val)
    root->left = insert(root, val);
else
    root->right = insert(root, val);

语言： C++

GESP真题六级

2024.9

单选题号： 12

EXY-SC-1106

第 395 题

上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写（）。

#include <queue>
 
int max_depth_bfs(tree_node* root) {
    if (root == nullptr) {
        return 0; // 如果树为空，深度为 0
    }
 
    queue <tree_node*> q;
    q.push(root);
    int depth = 0;
 
    // 使用队列进行层序遍历
    while (!q.empty()) {
        ________________________  // 在此处填入代码
        for (int i = 0; i < level_size; ++i) {
            tree_node* node = q.front();
            q.pop();
 
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
 
    return depth;
}

A

int level_size = q.size(); depth++;

B

int level_size = 2; depth++;

C

int level_size = q.size(); depth += level_size;

D

int level_size = 2; depth += level_size;

语言： C++

GESP真题六级

2024.9

单选题号： 11