CSP-J阅读程序专题第二题 - 2

第一题
题目：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int lcs(string x, string y) {
    int m = x.size();
    int n = y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

bool isRotation(string x, string y) {
    if (x.size() != y.size()) {
        return false;
    }
    return lcs(x + x, y) == y.size();
}

int main() {
    string x, y;
    cin >> x >> y;
    cout << isRotation(x, y) << endl;
    return 0;
}

假设输入的字符串长度不超过 100，完成下面的判断题和单选题：

判断题

1. （2分）lcs 函数返回的值总是小于或等于两个字符串的长度中的较小值。（ ）
2. （2分）lcs 函数的返回值等于两个输入字符串的最长公共子序列的长度。（ ）
3. （2分）如果两个字符串完全相同，isRotation 函数的返回值一定为 true。（ ）

单选题

1. 如果将 lcs 函数中的 dp[i][j] 替换为 dp[j][i]，程序会（ ）
   A. 程序不会编译通过
   B. 程序运行时会出错
   C. 程序输出会不正确
   D. 程序输出保持不变

2. 当输入为 "abc" 和 "bca" 时，isRotation 函数的返回值为（ ）
   A. true
   B. false
   C. 编译错误
   D. 输出未知

3. 当输入为 "abcd" 和 "dabc" 时，isRotation 函数的返回值为（ ）
   A. true
   B. false
   C. 编译错误
   D. 输出未知

第二题

题目：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestCommonSubsequence(string x, string y) {
    int m = x.size();
    int n = y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

bool areStringsInterleaved(string x, string y, string z) {
    if (x.size() + y.size() != z.size()) {
        return false;
    }

    int lx = 0, ly = 0;
    for (char c : z) {
        if (lx < x.size() && c == x[lx]) {
            lx++;
        } else if (ly < y.size() && c == y[ly]) {
            ly++;
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    string x, y, z;
    cin >> x >> y >> z;
    cout << areStringsInterleaved(x, y, z) << endl;
    return 0;
}

假设输入的字符串长度不超过 100，完成下面的判断题和单选题：

判断题

1. （2分）longestCommonSubsequence 函数返回的值总是小于等于两个输入字符串的长度中的较小值。（ ）
2. （2分）areStringsInterleaved 函数可以判断第三个字符串是否是前两个字符串按相对顺序交错的结果。（ ）
3. （2分）如果两个字符串完全相同，areStringsInterleaved 函数的返回值一定为 false。（ ）

单选题

1. 如果将 longestCommonSubsequence 函数中的 dp[i][j] 替换为 dp[j][i]，程序会（ ）
   A. 程序不会编译通过
   B. 程序运行时会出错
   C. 程序输出会不正确
   D. 程序输出保持不变

2. 当输入为 "abc"，"def" 和 "adbcef" 时，areStringsInterleaved 函数的返回值为（ ）
   A. true
   B. false
   C. 编译错误
   D. 输出未知

3. 当输入为 "abc"，"xyz" 和 "axbycz" 时，areStringsInterleaved 函数的返回值为（ ）
   A. true
   B. false
   C. 编译错误
   D. 输出未知

第三题

题目：

#include <iostream>
#include <vector>
using namespace std;

// 查找数组中是否存在两个数的和等于目标值
bool findPairWithSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    sort(nums.begin(), nums.end());
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << (findPairWithSum(nums, target) ? "Yes" : "No") << endl;
    return 0;
}

假设输入的数组长度不超过 100，完成下面的判断题和单选题：

判断题

1. （2分）程序使用了排序和双指针技术来寻找两个数的和是否等于目标值。（ ）
2. （2分）如果输入数组是降序排列的，程序会首先对数组进行升序排序再执行双指针查找。（ ）
3. （2分）findPairWithSum 函数的时间复杂度是 O(nlogn)，其中 n 是数组的长度。（ ）

单选题

1. 如果输入为数组 [2, 7, 11, 15]，目标值为 9，程序的输出为（ ）
   A. "Yes"
   B. "No"
   C. 编译错误
   D. 程序崩溃

2. 如果将程序中的 sort(nums.begin(), nums.end()); 删除，程序将（ ）
   A. 保持不变，依然正确输出
   B. 程序可能会陷入无限循环
   C. 输出错误结果
   D. 编译错误

3. 如果输入为 [1, 2, 4, 5]，目标值为 10，程序的输出为（ ）
   A. "Yes"
   B. "No"
   C. 编译错误
   D. 输出未知

题目：

#include <iostream>
#include <vector>
using namespace std;

// 查找数组中是否存在两个数的和等于目标值
bool findPairWithSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    sort(nums.begin(), nums.end());
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << (findPairWithSum(nums, target) ? "Yes" : "No") << endl;
    return 0;
}

假设输入的数组长度不超过 100，完成下面的判断题和单选题：

判断题

1. （2分）程序使用了排序和双指针技术来寻找两个数的和是否等于目标值。（ ）
2. （2分）如果输入数组是降序排列的，程序会首先对数组进行升序排序再执行双指针查找。（ ）
3. （2分）findPairWithSum 函数的时间复杂度是 O(nlogn)，其中 n 是数组的长度。（ ）

单选题

1. 如果输入为数组 [2, 7, 11, 15]，目标值为 9，程序的输出为（ ）
   A. "Yes"
   B. "No"
   C. 编译错误
   D. 程序崩溃

2. 如果将程序中的 sort(nums.begin(), nums.end()); 删除，程序将（ ）
   A. 保持不变，依然正确输出
   B. 程序可能会陷入无限循环
   C. 输出错误结果
   D. 编译错误

3. 如果输入为 [1, 2, 4, 5]，目标值为 10，程序的输出为（ ）
   A. "Yes"
   B. "No"
   C. 编译错误
   D. 输出未知

解析

判断题解析：

1. 正确 (√)
   解析：程序通过排序数组，然后使用双指针技术查找两个数的和是否等于目标值。

2. 正确 (√)
   解析：程序使用 sort 函数将输入数组升序排列，然后执行双指针查找。

3. 正确 (√)
   解析：数组排序的时间复杂度为 O(nlogn)，双指针查找的时间复杂度为 O(n)，所以整体时间复杂度为 O(nlogn)。

单选题解析：

1. 正确答案：A
   解析：数组 [2, 7, 11, 15] 中，2 和 7 的和等于 9，所以程序返回 "Yes"。

2. 正确答案：C
   解析：如果不排序，双指针方法将无法正常工作，可能导致错误结果。

3. 正确答案：B
   解析：数组 [1, 2, 4, 5] 中不存在和为 10 的两个数，因此程序返回 "No"。

第四题
题目：

#include <iostream>
#include <vector>
using namespace std;

int minCostPath(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));

    dp[0][0] = grid[0][0];

    // 初始化第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // 初始化第一行
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // 填充剩余部分
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> grid(m, vector<int>(n));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    cout << minCostPath(grid) << endl;
    return 0;
}

假设输入的网格大小不超过 100×100，完成下面的判断题和单选题：

判断题

1. （2分）程序使用动态规划方法来计算从网格左上角到右下角的最小路径和。（ ）
2. （2分）如果输入的所有数字都为正数，minCostPath 函数的返回值一定为一个大于 0 的整数。（ ）
3. （2分）程序中的 dp 数组用于存储从起点到每个网格点的最小路径和。（ ）

单选题

1. 如果输入的网格为：

   3 3
   1 2 3
   4 8 2
   1 5 3
   

   程序的输出是（ ）
   A. 8
   B. 12
   C. 11
   D. 10

2. 如果将 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] 替换为 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]，程序将计算（ ）
   A. 最小路径和
   B. 最大路径和
   C. 路径长度
   D. 网格中最大的数值

3. 当输入为一个 1×1 的网格时，程序的输出将是（ ）
   A. 网格中的唯一值
   B. 0
   C. 1
   D. 错误输出

第五题
题目：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    stack<int> s;
    heights.push_back(0);
    int maxArea = 0;
    
    for (int i = 0; i < heights.size(); ++i) {
        while (!s.empty() && heights[s.top()] > heights[i]) {
            int height = heights[s.top()];
            s.pop();
            int width = s.empty() ? i : i - s.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        s.push(i);
    }
    
    heights.pop_back();
    return maxArea;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) {
        return 0;
    }
    
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n, 0);
    int maxArea = 0;
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
        }
        maxArea = max(maxArea, largestRectangleArea(heights));
    }
    
    return maxArea;
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<char>> matrix(m, vector<char>(n));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }
    cout << maximalRectangle(matrix) << endl;
    return 0;
}

假设输入的矩阵大小不超过 100×100，完成下面的判断题和单选题：

判断题

1. （2分）largestRectangleArea 函数是通过栈的方式来计算直方图中最大的矩形面积的。（ ）
2. （2分）heights 数组记录的是从每一行的某一列开始向上的连续 ‘1’ 的高度。（ ）
3. （2分）如果矩阵中全是 ‘0’，则 maximalRectangle 函数的输出将为 0。（ ）

单选题

1. 如果输入的矩阵为：

   3 3
   1 0 1
   1 1 1
   0 1 1
   

   程序的输出是（ ）
   A. 4
   B. 6
   C. 3
   D. 2

2. 如果将 heights.push_back(0); 删除，程序的表现将会（ ）
   A. 保持不变
   B. 计算结果错误
   C. 编译错误
   D. 超时

3. 如果输入为：

   4 4
   0 1 0 0
   1 1 1 0
   1 1 1 1
   1 0 0 1
   

   程序的输出是（ ）
   A. 4
   B. 5
   C. 6
   D. 7

答案：

判断题：

1. 正确
   largestRectangleArea 函数使用栈来存储直方图的高度，逐步计算最大矩形面积。

2. 正确
   heights 数组记录每列的连续 ‘1’ 的高度，如果遇到 ‘0’，高度会被重置为 0。

3. 正确
   如果矩阵中全是 ‘0’，则没有可形成的矩形，因此函数输出为 0。

单选题：

1. 正确答案：A
   解析：矩阵中最大的矩形是第二行的 1 1 1 和第三行的 1 1 组成的 2×2 矩形，面积为 4。

2. 正确答案：B
   解析：删除 heights.push_back(0); 后，程序无法处理栈中剩余的高度，导致无法正确计算出矩形的最大面积。

3. 正确答案：C
   解析：最大的矩形区域是第三行三个连续 ‘1’ 和第二行三个 ‘1’，形成 3×2 的矩形，面积为 6。

第六题
题目：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kadaneMaxSubarraySum(vector<int>& nums) {
    int currentMax = nums[0], globalMax = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        currentMax = max(nums[i], currentMax + nums[i]);
        globalMax = max(globalMax, currentMax);
    }
    return globalMax;
}

int circularMaxSubarraySum(vector<int>& nums) {
    int nonCircularMax = kadaneMaxSubarraySum(nums);
    
    int totalSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        totalSum += nums[i];
        nums[i] = -nums[i];
    }
    
    int circularMax = totalSum + kadaneMaxSubarraySum(nums);
    
    if (circularMax == 0) {
        return nonCircularMax;
    }
    
    return max(nonCircularMax, circularMax);
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << circularMaxSubarraySum(nums) << endl;
    return 0;
}

问题：

假设输入的数组大小 n 不超过 30,000，数组的元素为 [-30,000, 30,000] 之间的整数，完成下面的判断题和单选题：

判断题：

1. （2分）kadaneMaxSubarraySum 函数是用来计算非环形的最大子数组和的。（ ）
2. （2分）程序通过将数组的每个元素取反，间接计算出环形的最大子数组和。（ ）
3. （2分）如果数组中所有元素均为负数，程序返回的结果一定是 kadaneMaxSubarraySum 函数的值。（ ）

单选题：

1. 如果输入的数组为：

   6
   5 -3 5 -2 2 6
   

   程序的输出是（ ）
   A. 12
   B. 14
   C. 13
   D. 15

2. 将 if (circularMax == 0) return nonCircularMax; 删除，程序的输出将会（ ）
   A. 保持不变
   B. 输出错误
   C. 超时
   D. 编译错误

3. 如果输入为：

   5
   -1 -2 -3 -4 -5
   

   程序的输出是（ ）
   A. -1
   B. 0
   C. -5
   D. 1

第七题
题目：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(NULL), right(NULL) {}
};

Node* buildTree(const vector<int>& arr, int& idx) {
    if (idx >= arr.size() || arr[idx] == -1) {
        idx++;
        return NULL;
    }
    Node* root = new Node(arr[idx++]);
    root->left = buildTree(arr, idx);
    root->right = buildTree(arr, idx);
    return root;
}

void levelOrderTraversal(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node* curr = q.front();
            q.pop();
            cout << curr->data << " ";
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
        cout << endl;
    }
}

Node* mergeTrees(Node* t1, Node* t2) {
    if (!t1) return t2;
    if (!t2) return t1;
    t1->data += t2->data;
    t1->left = mergeTrees(t1->left, t2->left);
    t1->right = mergeTrees(t1->right, t2->right);
    return t1;
}

int main() {
    int n;
    cin >> n;
    vector<int> tree1(n);
    for (int i = 0; i < n; i++) {
        cin >> tree1[i];
    }

    int m;
    cin >> m;
    vector<int> tree2(m);
    for (int i = 0; i < m; i++) {
        cin >> tree2[i];
    }

    int idx1 = 0, idx2 = 0;
    Node* root1 = buildTree(tree1, idx1);
    Node* root2 = buildTree(tree2, idx2);

    Node* mergedRoot = mergeTrees(root1, root2);

    levelOrderTraversal(mergedRoot);

    return 0;
}

问题：

假设输入的树用层序遍历方式表示，其中 -1 表示该位置为空。数组的大小不超过 10,000，元素为 [-100, 100] 之间的整数。

判断题：

1. （2分）mergeTrees 函数是将两棵树的节点相加，如果某个节点在某棵树中不存在，则用另一棵树对应的节点值。（ ）
2. （2分）levelOrderTraversal 函数的作用是按层次顺序遍历输出一棵树的节点值。（ ）
3. （2分）如果两棵树的节点完全相同，那么 mergeTrees 合并后的树与原始树完全相同。（ ）

单选题：

1. 如果输入的树为：

   7
   1 3 -1 5 -1 -1 -1
   7
   2 1 -1 -1 4 -1 -1
   

   程序的输出是（ ）
   A.

   3
   4 1
   5 4
   

   B.

   3
   1 4
   4 5
   

   C.

   3
   4 1
   5 -1
   

   D.

   3
   4 1
   -1 5
   

2. 将 if (!t1) return t2; 改为 if (!t1 && !t2) return NULL;，程序的输出将会（ ）
   A. 保持不变
   B. 输出错误
   C. 只会处理两棵完全相同结构的树
   D. 合并结果与结构无关

3. 如果输入为：

   5
   -1 -1 -1 -1 -1
   5
   2 3 -1 -1 -1
   

   程序的输出是（ ）
   A.

   2
   3
   

   B.

   -1
   -1 -1
   

   C.

   2
   -1 -1
   

   D.

   2
   3 -1