A. CSP-J模拟卷13

A
    客观题

CSP-J模拟卷13

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

选择题

  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int solve(int n, int k) {
    if (n == 0) return 1;
    if (k == 0) return 0;
    int result = 0;
    for (int i = 1; i <= k && i <= n; i++) {
        result += solve(n - i, k);
    }
    return result;
}
int main() {
    cout << solve(4, 3) << endl;
    return 0;
}

{{ select(1) }}

  • 10
  • 7
  • 6
  • 9
  1. （2分）在C++中，以下哪种循环结构一定会执行至少一次：{{ select(2) }}
  • for循环
  • do-while循环
  • while循环
  • 以上都不是
  1. （2分）二分查找在有序数组arr[] = {1,3,5,7,9,11,13}中查找目标值9，最少需要比较多少次：{{ select(3) }}
  • 1
  • 3
  • 2
  • 4
  1. （2分）关于归并排序的说法错误的是：{{ select(4) }}
  • 是稳定的排序算法
  • 时间复杂度为O(nlogn)
  • 采用分治思想
  • 空间复杂度为O(1)
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int n = 1234;
    int count = 0;
    while (n > 0) {
        if (n % 10 % 2 == 1) count++;
        n /= 10;
    }
    cout << count << endl;
    return 0;
}

{{ select(5) }}

  • 2
  • 4
  • 1
  • 3
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = 8;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    cout << arr[n/2] << endl;
    return 0;
}

{{ select(6) }}

  • 4
  • 3
  • 5
  • 1
  1. （2分）以下代码实现了什么功能：
#include <iostream>
using namespace std;
bool check(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return true;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}
int main() {
    int arr[] = {1, 3, 5, 7, 9};
    cout << check(arr, 5, 6) << endl;
    return 0;
}

{{ select(7) }}

  • 二分查找
  • 线性查找
  • 快速排序
  • 归并排序
  1. （2分）使用邻接矩阵表示图，对于一个n个节点的无向图，其空间复杂度是：{{ select(8) }}
  • O(n)
  • O(n^2)
  • O(n+m)
  • O(nm)
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int parent[1000];
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}
void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) parent[px] = py;
}
int main() {
    for (int i = 1; i <= 5; i++) parent[i] = i;
    unite(1, 2);
    unite(3, 4);
    unite(2, 3);
    cout << (find(1) == find(4) ? 1 : 0) << endl;
    return 0;
}

{{ select(9) }}

  • 0
  • 1
  • 2
  • -1
  1. （2分）有7个不同的球，其中3个红球，2个蓝球，2个白球。将它们排成一排，但同色球不能相邻，有多少种不同的排法：{{ select(10) }}
  • 720
  • 960
  • 912
  • 864
  1. （2分）以下代码的输出结果是：
#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    int arr[] = {3, 1, 4, 1, 5, 9, 2};
    for (int i = 0; i < 7; i++) {
        pq.push(arr[i]);
        if (pq.size() > 4) {
            pq.pop();
        }
    }
    cout << pq.top() << endl;
    return 0;
}

{{ select(11) }}

  • 5
  • 4
  • 3
  • 9
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int sum = 0;
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    sum = sum % 1000;
    cout << sum << endl;
    return 0;
}

{{ select(12) }}

  • 233
  • 388
  • 418
  • 433
  1. （2分）关于Floyd算法的说法正确的是：{{ select(13) }}
  • 使用分治策略
  • 可以检测负权回路
  • 时间复杂度为O(n^3)
  • 只能处理无权图
  1. （2分）在一个长度为n的数组中，找到最大元素需要比较的次数为：{{ select(14) }}
  • n
  • n-1
  • n+1
  • logn
  1. （2分）关于计数排序的说法错误的是：{{ select(15) }}
  • 适用于数据范围很大的情况
  • 不是基于比较的排序算法
  • 时间复杂度为O(n+k)
  • 是稳定的排序算法

阅读理解1（12分）

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

int memo[105][105];
int grid[105][105];
int n, m;

int dfs(int x, int y) {

    if (x < 0 || x >= n || y < 0 || y >= m) {
        return 0;
    }
    
  
    if (memo[x][y] != -1) {
        return memo[x][y];
    }
    
   
    int result = grid[x][y];
    
  
    int maxPath = 0;
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
            grid[nx][ny] > grid[x][y]) {
            maxPath = max(maxPath, dfs(nx, ny));
        }
    }
    
    memo[x][y] = result + maxPath;
    return memo[x][y];
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    memset(memo, -1, sizeof(memo));
    
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            maxSum = max(maxSum, dfs(i, j));
        }
    }
    
    cout << maxSum << endl;
    return 0;
}

第16题（1.5分）

该程序使用了递归+记忆化搜索的动态规划算法。（ ）{{ select(16) }}

  • 正确
  • 错误

第17题（1.5分）

dfs函数的边界条件是防止数组越界。（ ）{{ select(17) }}

  • 正确
  • 错误

第18题（1.5分）

算法只能在数值递增的方向上移动。（ ）{{ select(18) }}

  • 正确
  • 错误

第19题（1.5分）

如果输入3 3\n1 2 3\n4 5 6\n7 8 9，输出为45。（ ）{{ select(19) }}

  • 正确
  • 错误

第20题（3分）

memo数组的作用是（ ）{{ select(20) }}

  • 存储输入数据
  • 存储中间结果避免重复计算
  • 存储路径信息
  • 检查边界条件

第21题（3分）

如果去掉memset(memo, -1, sizeof(memo))这行，程序可能会（ ）{{ select(21) }}

  • 运行正常
  • 产生错误结果
  • 编译错误
  • 性能更好

阅读理解2（12分）

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

struct Node {
    int x, y, dist;
};

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool visited[101][101];
char maze[101][101];

int bfs(int startX, int startY, int endX, int endY, int n, int m) {
    queue<Node> q;
    q.push({startX, startY, 0});
    visited[startX][startY] = true;
    
    while (!q.empty()) {
        Node current = q.front();
        q.pop();
        
        if (current.x == endX && current.y == endY) {
            return current.dist;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                !visited[nx][ny] && maze[nx][ny] != '#') {
                visited[nx][ny] = true;
                q.push({nx, ny, current.dist + 1});
            }
        }
    }
    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }
    cout << bfs(0, 0, n-1, m-1, n, m) << endl;
    return 0;
}

第22题（1.5分）

该程序使用BFS算法求解最短路径问题。（ ）{{ select(22) }}

  • 错误
  • 正确

第23题（1.5分）

如果将队列改为栈，算法仍能正确工作。（ ）{{ select(23) }}

  • 正确
  • 错误

第24题（1.5分）

该算法能保证找到最短路径。（ ）{{ select(24) }}

  • 错误
  • 正确

第25题（1.5分）

dx和dy数组定义了四个移动方向。（ ）{{ select(25) }}

  • 错误
  • 正确

第26题（3分）

该算法的时间复杂度是（ ）{{ select(26) }}

  • O(n+m)
  • O(n^2+m^2)
  • O(nm)
  • O(nm log(nm))

第27题（3分）

如果起点和终点相同，函数返回值是（ ）{{ select(27) }}

  • -1
  • 0
  • 1
  • 未定义

阅读理解3（16分）

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    vector<int> lis;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
        if (it == lis.end()) {
            lis.push_back(arr[i]);
        } else {
            *it = arr[i];
        }
    }
    
    cout << lis.size() << endl;
    return 0;
}

第28题（1.5分）

该程序求解的是最长递增子序列的长度。（ ）{{ select(28) }}

  • 错误
  • 正确

第29题（1.5分）

使用了二分查找优化算法效率。（ ）{{ select(29) }}

  • 错误
  • 正确

第30题（3分）

该算法的时间复杂度是（ ）{{ select(30) }}

  • O(n^2)
  • O(n)
  • O(nlogn)
  • O(2^n)

第31题（3分）

lower_bound函数的作用是（ ）{{ select(31) }}

  • 查找第一个大于目标值的位置
  • 查找第一个大于等于目标值的位置
  • 查找最后一个小于目标值的位置
  • 查找目标值的位置

第32题（3分）

若输入为5\n1 3 2 4 5，输出为（ ）{{ select(32) }}

  • 5
  • 3
  • 4
  • 6

第33题（4分）

如果要输出具体的最长递增子序列，需要额外记录（ ）{{ select(33) }}

  • 每个元素的前驱
  • 每个元素的后继
  • 子序列的起始位置
  • 子序列的结束位置

编程填空1（15分）

（数字三角形路径和）给定一个数字三角形，从顶部开始，找到一条到底部的路径，使得路径上数字的和最大。每步只能向下或向右下移动。

样例1： 输入：

4
7
3 8
8 1 0
2 7 4 4

输出：30 解释：路径 7 → 8 → 8 → 7 = 30

样例2： 输入：

3
5
6 2
1 3 4

输出：14

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

int triangle[105][105];
int memo[105][105];
int n;

int dfs(int row, int col) {
  
    if (①) {
        return 0;
    }
    
   
    if (②) {
        return memo[row][col];
    }
    
    int down = dfs(row + 1, col);
    int right_down = ③;
    
    memo[row][col] = ④;
    return memo[row][col];
}

int main() {
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    
    memset(memo, -1, sizeof(memo));
    
    int result = ⑤;
    cout << result << endl;
    
    return 0;
}

第34题（3分）①处应填（ ）{{ select(34) }}

  • row < 0 || col < 0
  • row > n || col >= row
  • row >= n || col > row
  • row == n && col == row

第35题（3分）②处应填（ ）{{ select(35) }}

  • memo[row][col] == -1
  • memo[row][col] != -1
  • memo[row][col] > 0
  • memo[row][col] < 0

第36题（3分）③处应填（ ）{{ select(36) }}

  • dfs(row - 1, col + 1)
  • dfs(row, col + 1)
  • dfs(row + 1, col + 1)
  • dfs(row + 1, col - 1)

第37题（3分）④处应填（ ）{{ select(37) }}

  • max(down, right_down) + triangle[row][col]
  • triangle[row][col] + max(down, right_down)
  • triangle[row][col] * max(down, right_down)
  • max(down + triangle[row][col], right_down)

第38题（3分）⑤处应填（ ）{{ select(38) }}

  • dfs(n-1, 0)
  • dfs(1, 0)
  • dfs(0, 0)
  • dfs(0, 1)

编程填空2. （15分）

（最小生成树）给定一个连通无向图，求其最小生成树的权值和。使用Kruskal算法实现。

样例1： 输入： 4 5 1 2 1 1 3 3 2 3 1 2 4 6 3 4 4 输出：6

样例2： 输入： 3 3 1 2 2 2 3 3 1 3 1 输出：6

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

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int parent[1001];

int find(int x) {
    if (parent[x] != x) {
        ①;
    }
    return parent[x];
}

void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        ②;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    Edge edges[m];
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    
    ③;
    
    for (int i = 1; i <= n; i++) {
        ④;
    }
    
    int result = 0;
    int edgeCount = 0;
    
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        
        if (find(u) != find(v)) {
            unite(u, v);
            ⑤;
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }
    
    cout << result << endl;
    return 0;
}

第39题（3分）①处应填（ ）{{ select(39) }}

  • return find(parent[x])
  • parent[x] = find(parent[x])
  • parent[x] = parent[parent[x]]
  • x = parent[x]

第40题（3分）②处应填（ ）{{ select(40) }}

  • parent[x] = y
  • parent[fy] = fx
  • parent[y] = x
  • parent[fx] = fy

第41题（3分）③处应填（ ）{{ select(41) }}

  • sort(edges, edges + n)
  • sort(edges, edges + m)
  • sort(edges + 1, edges + m + 1)
  • 以上都不对

第42题（3分）④处应填（ ）{{ select(42) }}

  • parent[i] = 0
  • parent[i] = i
  • parent[i] = -1
  • parent[0] = i

第43题（3分）⑤处应填（ ）{{ select(43) }}

  • edgeCount += w
  • result = max(result, w)
  • result += w
  • result = min(result, w)

cspj初赛模拟赛3

未参加
状态
已结束
规则
IOI
题目
1
开始于
2025-9-4 17:45
结束于
2025-9-4 19:21
持续时间
1.6 小时
主持人
参赛人数
9
  1. Language
  2. 兼容模式
  3. 主题
  2. 浙ICP备2025154918号
  3. Worker 0, 66ms
  4. Powered by Hydro v5.0.0-beta.8 Community