CSP-J模拟卷3

ID: 2319

客观题

尝试: 206

已通过: 3

难度: 10

上传者:

yhxx

标签>

动态规划

CSP-J

选择题

（2分）C++中用于动态内存分配的运算符是：{{ select(1) }}

malloc
new
alloc
create

（2分）以下关于vector容器的说法正确的是：{{ select(2) }}

size()返回当前分配的内存容量
capacity()返回当前元素数量
push_back()将导致迭代器失效
存储空间是连续分配的

（2分）二进制数110101的按位取反结果是（假设8位）：{{ select(3) }}

00101010
00101011
11101100
11001010

（2分）以下关于函数参数传递的说法错误的是：{{ select(4) }}

传值参数会创建副本
传引用参数可以修改实参
数组参数自动转为指针
const引用不能绑定右值

（2分）表达式(7 ^ 3)的值是：{{ select(5) }}

（2分）以下排序算法最差情况下时间复杂度为O(n²)的是：{{ select(6) }}

快速排序
堆排序
归并排序
基数排序

（2分）关于结构体的说法错误的是：{{ select(7) }}

可以包含成员函数
默认访问权限是public
可以嵌套定义
大小等于各成员大小之和

（2分）以下代码的输出是：

int a = 33, b = 55;
cout << (a & b)^(a | b) << endl;

（2分）关于递归函数的说法错误的是：{{ select(9) }}

必须包含终止条件
可能引发栈溢出
比迭代实现更高效
适合解决分治问题

（2分）以下关于文件操作的说法正确的是：{{ select(10) }}

ifstream用于写入文件
ios::app模式会清空原有内容
tellg()返回当前读位置
seekp()用于调整读位置

（2分）表达式(31 >> 2)的值是：{{ select(11) }}

（2分）关于STL算法的说法正确的是：{{ select(12) }}

sort支持所有容器
find需要有序序列
reverse可以反转vector
unique会自动删除重复元素

（2分）以下代码的时间复杂度是：

for(int i=0; i<n; ++i) 
    for(int j=i; j<n; ++j)
        cout << i*j;

O(n)
O(nlogn)
O(n²)
O(n³)

（2分）以下关于指针的说法错误的是：{{ select(14) }}

指针可以指向数组元素
野指针可能引发运行时错误
空指针的值为NULL
指针运算以字节为单位

（2分）将0x3E转换为十进制的结果是：{{ select(15) }}

阅读理解1

图论题（BFS遍历）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[100];
bool visited[100];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        
        for(int v : adj[u]) {
            if(!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    while(m--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);
    return 0;
}

第16题（1.5分）

BFS的实现方式是递归算法（）{{ select(16) }}

正确
错误

第17题（1.5分）

该程序可以正确处理非连通图（）{{ select(17) }}

正确
错误

第18题（1.5分）

若输入边的顶点编号超过100，程序会越界访问（）{{ select(18) }}

正确
错误

第19题（1.5分）

BFS遍历顺序与边输入顺序有关（）{{ select(19) }}

正确
错误

第20题（3分）

该程序的时间复杂度是：{{ select(20) }}

O(n+m)
O(n²)
O(2ⁿ)
O(n!)

第21题（3分）

输入以下边时访问顺序是： 1-2,1-3,2-4{{ select(21) }}

1→2→3→4
1→3→2→4
取决于编译器实现
由输入顺序决定

阅读理解2

贪心算法（活动选择）

#include <iostream>
#include <algorithm>
using namespace std;
struct Activity { int start, end; };

bool cmp(Activity a, Activity b) {
    // 按结束时间升序排列
    return a.end < b.end;
}

int main() {
    int n;
    cin >> n;
    Activity acts[n];
    for(int i=0; i<n; i++)
        cin >> acts[i].start >> acts[i].end;
    
    sort(acts, acts+n, cmp);
    
    int count = 1, last = acts[0].end;
    for(int i=1; i<n; i++) {
        if(acts[i].start >= last) {
            last = acts[i].end;  // 更新最后选择的活动结束时间
            count++;
        }
    }
    cout << count;
    return 0;
}

第22题（1.5分）

输入

则输出为：

（）{{ select(22) }}

正确
错误

第23题（1.5分）

该算法属于动态规划（）{{ select(23) }}

正确
错误

第24题（1.5分）

初始化时last变量赋值为第一个活动的结束时间（）{{ select(24) }}

正确
错误

第25题（1.5分）

当活动时间完全重叠时算法会选择最早结束的活动（）{{ select(25) }}

正确
错误

第26题（3分）

输入

则输出为（）{{ select(26) }}

第27题（3分）

该算法的时间复杂度主要来源于：{{ select(27) }}

排序操作
贪心选择循环
递归调用
动态规划计算

阅读理解3

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    mergeSort(arr, 0, n-1);
    for(int i=0; i<n; i++) cout << arr[i] << " ";
    return 0;
}

第28题（1.5分）

递归终止条件if (l >= r) return;改成if (l > r) return;结果不变（） {{ select(28) }}

正确
错误

第29题（1.5分）

合并操作的时间复杂度是O(n)（）{{ select(29) }}

正确
错误

第30题（3分）

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

O(1)
O(n)
O(nlogn)
O(n²)

第31题（3分）

递归调用的最大深度是（）{{ select(31) }}

O(n)
O(log n)
O(n log n)
O(n²)

第32题（3分）

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

O(n)
O(nlogn)
O(n²)
O(2ⁿ)

第33题（3分）

若将第21行改为if(L[i] < R[j])，则输出结果会（）{{ select(33) }}

变为不稳定排序
出现重复元素
无法正确排序
导致栈溢出

编程填空1（15分）

（不相交区间的最大权重和）

问题描述
给定 $n$ 个区间，每个区间 $i$ 有起始时间 $s_i$ 、结束时间 $e_i$ 和权重 $w_i$ 。请选择若干个区间，使得这些区间两两不相交（即任意两个区间的起始和结束时间不重叠），并最大化选中区间的权重总和。

输入格式
第一行包含整数 $n$ （ $1 \leq n \leq 10^5$ ），表示区间的数量。
接下来的 $n$ 行，每行包含三个整数 $s_i, e_i, w_i$ （ $1 \leq s_i < e_i \leq 10^9$ ， $1 \leq w_i \leq 10^9$ ），分别表示第 $i$ 个区间的起始时间、结束时间和权重。

输出格式
输出一个整数，表示选中区间的最大权重和。

样例输入

样例输出

样例解释
选择区间 $[1,3,2]$ 和 $[3,6,4]$ ，总权重为 $2 + 4 = 6$ ，是所有不相交区间组合中最大的。

数据范围

对于30%的数据： $n \leq 100$
对于60%的数据： $n \leq 1000$
对于100%的数据： $n \leq 10^5$ ， $1 \leq s_i < e_i \leq 10^9$ ， $1 \leq w_i \leq 10^9$

程序实现

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

struct Interval {
    int start, end, weight;
};

int main() {
    int n;
    cin >> n;
    vector<Interval> intervals(n);
    for (int i = 0; i < n; ++i) {
        cin >> intervals[i].start >> intervals[i].end >> intervals[i].weight;
    }
    
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.end < b.end;
    });
    
    vector<long long> dp(n, 0);  
    dp[0] = intervals[0].weight;
    
    for (int i = 1; i < n; ++i) {
        
        long long include = intervals[i].weight;
       
        int left = 0, right = i - 1;
        int idx = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (⑤) {
                idx = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (idx != -1) {
            include += ①;
        }
        
        long long exclude = ②;
        
  
        dp[i] = ③;
    }
    
 
    long long max_sum = 0;
    for (int i = 0; i < n; ++i) {
        max_sum = ④;
    }
    
    cout << max_sum << endl;
    return 0;
}

问题34（3分）①处应填入的代码是：{{ select(34) }}

dp[idx]
dp[i-1]
intervals[idx].weight
profit[idx]

问题35（3分）②处应填入的代码是：{{ select(35) }}

dp[i-1]
dp[idx]
intervals[i-1].weight
profit[i-1]

问题36（3分）③处应填入的代码是：{{ select(36) }}

max(include, exclude)
min(include, exclude)
include + exclude
include * exclude

问题37（3分）④处应填入的代码是：{{ select(37) }}

max(max_sum, dp[i])
min(max_sum, dp[i])
max_sum + dp[i]
max_sum * dp[i]

问题38（3分）⑤处应填入的代码是：{{ select(38) }}

intervals[mid].end <= intervals[i].start
intervals[mid].end < intervals[i].start
intervals[mid].end > intervals[i].start
intervals[mid].end >= intervals[i].start

编程填空2（15分）

（树的重心）

问题描述
给定一棵有 $n$ 个节点的无根树，树的重心是指树中的一个节点，如果将这个节点删除，那么剩下的各个子树的大小都不超过原树大小的一半。请找出树的所有重心。

输入格式
第一行包含整数 $n$ （ $1 \leq n \leq 10^5$ ），表示树的节点数。
接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ （ $1 \leq u, v \leq n$ ），表示节点 $u$ 和 $v$ 之间有一条边。

输出格式
输出所有重心的节点编号，按升序排列。

样例输入

样例输出

1 2

样例解释
删除节点1后，剩下的子树大小分别为3和1，均不超过原树大小的一半（2.5）；删除节点2后，剩下的子树大小分别为1、1和2，均不超过2.5。因此节点1和2都是重心。

数据范围

对于30%的数据： $n \leq 100$
对于60%的数据： $n \leq 1000$
对于100%的数据： $n \leq 10^5$

程序实现

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

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int n, sz[MAXN];
vector<int> centroids;

void dfs(int u, int parent) {

    ____①____
    
    bool is_centroid = true;
    for (int v : adj[u]) {
        if (v != parent) {
           
            ____②____
            
           
            ____③____
            
        
            if (sz[v] > n / 2) {
                is_centroid = false;
            }
        }
    }
   
    if (____④____) {
        is_centroid = false;
    }
    
    if (is_centroid) {
        ____⑤____
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    sort(centroids.begin(), centroids.end());
    for (int c : centroids) {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}

问题39（3分）①处应填入的代码是：{{ select(39) }}

sz[u] = 1;
sz[u] = 0;
sz[u] = adj[u].size();
sz[u] = n;

问题40（3分）②处应填入的代码是：{{ select(40) }}

dfs(v, u);
dfs(v, parent);
dfs(u, v);
dfs(parent, u);

问题41（3分）③处应填入的代码是：{{ select(41) }}

sz[u] += sz[v];
sz[v] += sz[u];
sz[u] = max(sz[u], sz[v]);
sz[v] = max(sz[v], sz[u]);

问题42（3分）④处应填入的代码是：{{ select(42) }}

if (n - sz[u] > n / 2)
if (sz[u] > n / 2)
if (n - sz[u] < n / 2)
if (sz[u] < n / 2)

问题43（3分）⑤处应填入的代码是：{{ select(43) }}

centroids.push_back(u);
centroids.push_back(parent);
centroids.push_back(v);
centroids.push_back(sz[u]);

#YHCSPJ0003. CSP-J模拟卷3

选择题

阅读理解1

图论题（BFS遍历）

第16题（1.5分）

第17题（1.5分）

第18题（1.5分）

第19题（1.5分）

第20题（3分）

第21题（3分）

阅读理解2

贪心算法（活动选择）

第22题（1.5分）

第23题（1.5分）

第24题（1.5分）

第25题（1.5分）

第26题（3分）

第27题（3分）

阅读理解3

第28题（1.5分）

第29题（1.5分）

第30题（3分）

第31题（3分）

第32题（3分）

第33题（3分）

编程填空1（15分）

程序实现

问题34（3分）①处应填入的代码是：{{ select(34) }}

问题35（3分）②处应填入的代码是：{{ select(35) }}

问题36（3分）③处应填入的代码是：{{ select(36) }}

问题37（3分）④处应填入的代码是：{{ select(37) }}

问题38（3分）⑤处应填入的代码是：{{ select(38) }}

编程填空2（15分）

程序实现

问题39（3分）①处应填入的代码是：{{ select(39) }}

问题40（3分）②处应填入的代码是：{{ select(40) }}

问题41（3分）③处应填入的代码是：{{ select(41) }}

问题42（3分）④处应填入的代码是：{{ select(42) }}

问题43（3分）⑤处应填入的代码是：{{ select(43) }}

状态

开发

支持

还没有账户？

登录