#YHCSPJ0002. CSP-J模拟卷2

CSP-J模拟卷2

选择题

  1. （2分）以下关于IP地址的说法错误的是：{{ select(1) }}
  • IPv4地址由32位二进制数组成
  • IPv6地址由128位二进制数组成
  • 127.0.0.1是本地回环地址
  • 私有IP地址可以直接在互联网上路由
  1. （2分）在C++中，以下哪个运算符优先级最高：{{ select(2) }}
  • ++
  • ∗*
  • ()()
  • ==
  1. （2分）以下关于链表的说法正确的是：{{ select(3) }}
  • 链表在内存中是连续存储的
  • 链表查找元素的时间复杂度是O(1)
  • 链表插入和删除元素的时间复杂度是O(1)
  • 链表比数组更适合随机访问
  1. （2分）以下关于快速排序的说法错误的是：{{ select(4) }}
  • 平均时间复杂度为O(nlogn)
  • 最坏时间复杂度为O(n^2)
  • 是不稳定的排序算法
  • 空间复杂度为O(n)
  1. （2分）以下关于堆的说法正确的是：{{ select(5) }}
  • 堆是一种完全二叉树
  • 堆排序是稳定的排序算法
  • 大顶堆的根节点值小于子节点
  • 堆的插入操作时间复杂度是O(n)
  1. （2分）以下关于HTTP协议的说法错误的是：{{ select(6) }}
  • HTTP是无状态协议
  • HTTP/1.1默认使用持久连接
  • HTTP/2使用二进制分帧传输
  • HTTP/3基于TCP协议
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int x = 5;
    cout << (x & 3) << endl;
    return 0;
}

{{ select(7) }}

  • 0
  • 1
  • 2
  • 3
  1. （2分）以下关于栈的常见操作时间复杂度正确的是：{{ select(8) }}
  • 入栈操作时间复杂度为O(n)
  • 出栈操作需要遍历整个栈
  • 获取栈顶元素需要O(logn)时间
  • 所有基本操作都是O(1)时间复杂度
  1. （2分）表达式A+B*C的后缀表示法是：{{ select(9) }}
  • ABC*+
  • +A*BC
  • AB*C+
  • ABC+*
  1. （2分）关于无向图顶点数与边数的关系，以下说法正确的是：{{ select(10) }}
  • n个顶点的无向图最多有n(n-1)/2条边
  • n个顶点的连通图至少有n条边
  • 边数不可能等于顶点数
  • 完全图的边数总是偶数
  1. （2分）杨辉三角第6行的数字除了两端的数字的和是：{{ select(11) }}
  • 14
  • 30
  • 32
  • 62
  1. （2分）以下代码的输出结果是：
#include <iostream>
using namespace std;
int main() {
    int a = 5, b = 2;
    cout << (a / b) << endl;
    return 0;
}

{{ select(12) }}

  • 2
  • 2.5
  • 3
  • 编译错误
  1. （2分）以下关于Dijkstra算法的说法正确的是：{{ select(13) }}
  • 可以处理带负权边的图
  • 时间复杂度为O(n^2)
  • 使用贪心策略
  • 不能用于有向图
  1. （2分）将10个相同的苹果分给3个小朋友，每人至少分到1个，有多少种不同的分法？{{ select(14) }}
  • 36
  • 45
  • 55
  • 66
  1. （2分）以下关于基数排序的说法错误的是：{{ select(15) }}
  • 适用于整数排序
  • 时间复杂度为O(n)
  • 是稳定的排序算法
  • 需要额外的存储空间

阅读理解1（12分）

#include <iostream>
using namespace std;

int mystery(int n) {
    if (n <= 1) return n;
    return mystery(n-1) + mystery(n-2);
}

int main() {
    int n;
    cin >> n;
    cout << mystery(n);
    return 0;
}

第16题（1.5分）

当n=30的时候，mystery函数的返回值会溢出。（ ）{{ select(16) }}

  • 正确
  • 错误

第17题（1.5分）

当n=5时，mystery函数会被调用15次。（ ）{{ select(17) }}

  • 正确
  • 错误

第18题（1.5分）

该算法的时间复杂度是O(2^n)。（ ）{{ select(18) }}

  • 正确
  • 错误

第19题（1.5分）

输入9时输出为55。（ ）{{ select(19) }}

  • 正确
  • 错误

第20题（3分）

该程序的空间复杂度是（ ）{{ select(20) }}

  • O(1)
  • O(n)
  • O(2^n)
  • O(n^2)

第21题（3分）

该算法可以通过（ ）优化为线性时间复杂度{{ select(21) }}

  • 递推算法
  • 贪心算法
  • 分治算法
  • 回溯算法

阅读理解2（12分）

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

vector<int> graph[100];
bool visited[100];

void dfs(int node) {
    visited[node] = true;
    for(int neighbor : graph[node]) {
        if(!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

int main() {
    int n, m, u, v;
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int components = 0;
    for(int i=1; i<=n; i++) {
        if(!visited[i]) {
            dfs(i);
            components++;
        }
    }
    cout << components << endl;
    return 0;
}

第22题（1.5分）

该程序计算了图的连通分量数量。（ ）{{ select(22) }}

  • 正确
  • 错误

第23题（1.5分）

若将第15行的graph[v].push_back(u);删除，程序功能不变。（ ）{{ select(23) }}

  • 正确
  • 错误

第24题（1.5分）

该算法适用于有向图。（ ）{{ select(24) }}

  • 正确
  • 错误

第25题（1.5分）

若输入数据为4 3\n1 2\n2 3\n4 1，输出为1。（ ）{{ select(25) }}

  • 正确
  • 错误

第26题（3分）

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

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

第27题（3分）

若将dfs改为bfs，需要使用的数据结构是（ ）{{ select(27) }}

  • 栈
  • 队列
  • 优先队列
  • 堆

阅读理解3（16分）

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

struct Item {
    int value;
    int weight;
};

bool cmp(Item a, Item b) {
    return (double)a.value/a.weight > (double)b.value/b.weight;
}

int main() {
    int W, n;
    cin >> W >> n;
    Item items[n];
    for(int i=0; i<n; i++) {
        cin >> items[i].value >> items[i].weight;
    }
    sort(items, items+n, cmp);
    
    double totalValue = 0.0;
    for(int i=0; i<n; i++) {
        if(W >= items[i].weight) {
            totalValue += items[i].value;
            W -= items[i].weight;
        } else {
            totalValue += items[i].value * ((double)W / items[i].weight);
            break;
        }
    }
    cout << totalValue << endl;
    return 0;
}

第28题（1.5分）

该程序解决了0-1背包问题。（ ）{{ select(28) }}

  • 正确
  • 错误

第29题（1.5分）

若将第12行的>改为<，程序输出结果会改变。（ ）{{ select(29) }}

  • 正确
  • 错误

第30题（3分）

该算法的时间复杂度主要取决于（ ）{{ select(30) }}

  • 输入规模n
  • 背包容量W
  • 排序算法
  • 价值重量比

第31题（3分）

该算法使用了（ ）策略{{ select(31) }}

  • 动态规划
  • 贪心
  • 分治
  • 回溯

第32题（3分）

若输入为50 3\n60 10\n100 20\n120 30，输出为（ ）{{ select(32) }}

  • 220
  • 240
  • 250
  • 260

第33题（4分）

对于该问题，最优解的时间复杂度是（ ）{{ select(33) }}

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

编程填空1（15分）

（删数问题）键盘输入一个高精度的正整数n（不超过250位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的n和k，寻找一种方案使得剩下的数字组成的新数最小。

样例1： 输入： 175438 4 输出：13

样例2： 输入： 1432219 3 输出：1219

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

int main() {
    string num;
    int k;
    cin >> num >> k;
    
    string result;
    for (char digit : num) {
        while (!result.empty() && k > 0 && digit < result.back()) {
            ①;
            ②;
        }
        ③;
    }
    
    while (k > 0 && !result.empty()) {
        ④;
        ⑤;
    }
    
    cout << (result.empty() ? "0" : result) << endl;
    return 0;
}

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

  • result.pop_back();
  • k++;
  • result += digit;
  • continue;

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

  • result.pop_back();
  • k--;
  • result += digit;
  • continue;

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

  • result.pop_back();
  • k++;
  • result += digit;
  • continue;

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

  • result.pop_back();
  • k++;
  • result += digit;
  • continue;

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

  • result.pop_back();
  • k--;
  • result += digit;
  • continue;

编程填空2. （15分）

（P1111 修复公路）A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。给出A地区的村庄数N和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，及修复完成时间。问最早什么时候任意两个村庄能够通车。

样例1： 输入： 4 4 1 2 6 1 3 4 1 4 5 4 2 3 输出：5 解释：最早在第5天所有村庄可以通车

样例2： 输入： 3 1 1 2 5 3 输出：-1 解释：无法连接所有村庄

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

struct Edge {
    int u, v, t;
};

bool cmp(Edge a, Edge b) {
    return a.t < b.t;
}

int parent[1001];

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

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].t;
    }
    sort(edges, edges + M, cmp);
    
    for (int i = 1; i <= N; i++) {
        ②;
    }
    
    int components = N;
    int max_t = 0;
    for (int i = 0; i < M; i++) {
        int u = edges[i].u, v = edges[i].v, t = edges[i].t;
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) {
            parent[root_v] = root_u;
            components--;
            max_t = max(max_t, t);
            if (components == 1) {
                ③;
            }
        }
    }
    
    if (components > 1) {
        ④;
    } else {
        ⑤;
    }
    
    return 0;
}

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

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

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

  • parent[i] = i;
  • visited[i] = true;
  • edges[i].t = 0;
  • continue;

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

  • break;
  • cout << max_t << endl;
  • return max_t;
  • continue;

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

  • cout << -1 << endl;
  • return -1;
  • break;
  • continue;

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

  • cout << max_t << endl;
  • return max_t;
  • break;
  • continue;
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 浙ICP备2025154918号
  3. Worker 0, 75ms
  4. Powered by Hydro v4.19.1 Community