第四届小云雀杯普及组初赛

正在进行… ACM/ICPC 开始于: 2025-9-15 14:45 2000 小时 主持人: 89

初赛模拟卷 2

一、单项选择（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

  1. 在计算机中，TB代表的字节数量？()
  • A. 2102^{10}
  • B. 2202^{20}
  • C. 2302^{30}
  • D. 2402^{40}
  1. TCP 协议属于哪一层协议( ).
  • A. 应用层
  • B. 传输层
  • C. 网络层
  • D. 数据链路层
  1. 若某二叉树的节点数为 15（根节点深度为1），且这些节点要么为叶子节点要么有 2 个儿子节点，则其最深的叶子深度至多为（）
  • A. 6
  • B. 7
  • C. 8
  • D. 9
  1. 以下代码的时间复杂度是（）
long long calc(long long n) {
    long long res = 0;
    for (long long i = 1, j; i * i <= n; i = i + 1) {
        j = i * i;  
        res += j * abs(j - i); 
    }
    return res;
}
  • A. O(n)O(n)
  • B. O(log⁡n)O(\log n)
  • C. O(n)O(\sqrt{n})
  • D. O(n2)O(n^2)
  1. 以下关于算法空间复杂度的描述，正确的是：
  • A. 空间复杂度衡量的是算法运行时临时占用的存储空间大小
  • B. 空间复杂度和时间复杂度总是相同的
  • C. 递归算法的空间复杂度一定是 O(1)O(1)
  • D. 使用越多的变量，空间复杂度就越高
  1. 已知递归函数定义为：
int S(int n, int k) {
    if (n == 0 && k == 0) return 1;
    if (n == 0 || k == 0) return 0;
    return S(n - 1, k - 1) + k * S(n - 1, k);
}

则 S(5,2)S(5,2) 的返回值为（）

  • A. 10
  • B. 15
  • C. 25
  • D. 31
  1. 已知十六进制数 AB，其对应的十进制数为（）
  • A. 171
  • B. 186
  • C. 172
  • D. 202
  1. A,C为真，B，D为假，需要判断以下哪个逻辑表达式为真
  • A. (B∨C)∧(A∨D)
  • B. (¬A∨B)∧C
  • C. (A∧B)∨(C∧D)
  • D. A∧(D∨¬C)∧B
  1. 以下时间复杂度不是 O(n2)O(n^2) 的排序方法是( ).
  • A. 插入排序
  • B. 冒泡排序
  • C. 选择排序
  • D. 归并排序
  1. 已知一棵二叉树的 中序遍历序列 为 D B E A F C，后序遍历序列 为 D E B F C A，则它的 前序遍历序列 是（ ）。
  • A A B D E C F
  • B A B C D E F
  • C A B D F E C
  • D A B D E F C
  1. 有向图中，点的入度之和是边数的 () 倍
  • A. 0.5
  • B. 1
  • C. 2
  • D. 以上答案全错
  1. 10个人围坐一张圆桌吃饭。这张圆桌的座位是完全相同的（即，旋转后座位布局相同的视为同一种入座方式）。如果其中有2个人不想坐在一起，请问一共有多少种不同的入座方式？
  • A. 9!
  • B. 9!*8
  • C. 8!*7
  • D. 8!*9
  1. 若有变量 int a, float x, y, 且 a=7，x=2.5，y=4.7, 则表达式 x+a%3*(int)(x+y)%2/4 的值保留两位小数的结果是( ).
  • A 2.50
  • B 2.75
  • C 3.50
  • D 0.00
  1. 目前个人电脑的( )市场占有率最靠前的厂商包括 Intel、AMD 等公司。
  • A. 显示器
  • B. CPU
  • C. 内存
  • D. 鼠标
  1. 二叉树的（ ）第一个访问的节点是根节点。
  • A. 先序遍历
  • B. 中序遍历
  • C. 后序遍历
  • D. 以上都是

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题2分，选择题每题3分，共40分）

（一）阅读下列程序，回答问题。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, k, s, t, x, a[N];
int find(int x)
{
    int l = 1, r = n, mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (a[mid] <= x)
            r = mid - 1; 
        else
            l = mid + 1; 
    }
    return a[l] == x ? l : -1;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
    {
        cin >> x;
        cout << find(x) << ' ';
    }
    return 0;
}

注意：数据保证，1≤n≤1061 \leq n \leq 10^6，1≤ai,q≤1091 \leq a_i,q \leq 10^9，1≤m≤1061 \leq m \leq 10^6

  • 判断题

  1. 程序中find函数对应的算法为二分查找（）

  2. 下列数据对应的输出为11 8 -1。 ()

11 3
15 15 13 11 9 7 5 3 3 3 1
1 3 6
  • 选择题
  1. 若给出下列输入时，程序输出的结果为（）
5 1
3 1 4 1 5
3
  • A. 1
  • B. 2
  • C. 3
  • D. -1
  1. （4分）下列对于这个程序说法正确的是? ()
  • A. 当保证输入的a数组是单调不增时，程序可以对每次输入的x，找到它在a数组中第一次出现的下标
  • B. 当保证输入的a数组是单调不减时，程序可以对每次输入的x，找到它在a数组中最后一次出现的下标
  • C. 不论a数组是否有序，程序可以对每次输入的x，找到它在a数组中第一次出现的下标
  • D. 上述选项都错

（二）阅读下列程序，回答问题。

#include <iostream>
using namespace std;
#define MAXN 41
int pf[MAXN][MAXN];
int f(int n, int m) {
    if (n <= 1 || m < 3)
        return 1;
    if (pf[n][m] != -1)
        return pf[n][m];
    int ans = 0;
    for (int i = 0; i < m; i += 3)
        ans += f(n - 1, i);
    pf[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            pf[i][j] = -1;
    cout << f(n, m);
    return 0;
}

注意：输入的 1≤n,m≤401\le n,m \le 40

  • 判断题
  1. f(n,m)函数中，m永远不可能是奇数。（）
  2. 将 n≤1n \le 1 改成 n≤2n \le 2,存在n变化前后f(n,m)答案不变的 (n,m) （）
  3. 将8，9，13行去除后，答案可能会改变（）
  4. 输入 2 5 得到的答案为 3。 ()
  • 选择题
  1. 选出下列输入中执行结果和其他不同的一项（）

A.

2 5

B.

2 6

C.

2 4

D.

2 3
  1. （4分）输入后输出2的合法输入有多少种? ()

A. 3

B. 39

C. 117

D. 40

（三）阅读下列程序，回答问题。

#include <bits/stdc++.h>
int n, r, num[10000];
bool mark[10000];
void print()
{
    for (int i = 1; i <= r; i++)
        printf("%d ", num[i]);
    printf("\n");
}
void search(int x)
{
    for (int i = 1; i <= n; i++)
        if (!mark[i])
        {
            num[x] = i;
            mark[i] = true;
            if (x == r)
                print();
            search(x + 1);
            mark[i] = false;
        }
}
int main()
{
    scanf("%d%d", &n, &r);
    search(1);
    return 0;
}
  • 判断题

  1. 若 n < r ，则程序无输出（）

  2. 程序结束时，对任意 1≤i≤n1 \leq i \leq n ， mark[i] == 0。（）

  3. 此程序的时间复杂度为 O(n)O(n) ()

  • 选择题
  1. （4分）若输入为 6 3 ，则函数 print 的执行次数为？

A. 60
B. 120
C. 6 D. 720

  1. （4分）若输入为 7 4 ，则输出的最后一行为（）

A. 1 2 3 4
B. 4 5 6 7
C. 4 3 2 1 D. 7 6 5 4

三、完善程序（单选题，每小题3分，共计30分）

（一）完善程序第一题

题目描述

在一个 n × m 的矩形网格图A中，每个格子都有一个整数值。需要找到满足以下条件的格子对 (a,b) 和 (c,d)：格子中的整数 A[a][b] 和 A[c][d] 相等，且它们的位置满足 ∣a−c∣=∣b−d∣>0。要求计算出满足这些条件的格子对的总数，特别的，格子对 ((a, b), (c, d) 和 ((c, d), (a, b)) 视为两个不同的对。 1 <= n, m <= 1000 1 <= A[i][k] <= 1000

#include <bits/stdc++.h>
using namespace std;

int a[1005][1005];
int n, m, ans;

int f(int x, int y)
{
    int p = ___31___;
    int xx = x, yy = y;
    int sum = 0;
    while (xx < n && yy > 1)
    {
        ____32____
        if (a[xx][yy] == p)
            sum += 2;
    }
    ____33____
    while (____34____)
    {
        xx++;yy++;
        if (a[xx][yy] == p)
            ____35____;
    }
    return sum;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans += f(i, j);
    cout << ans;
    return 0;
}

选择题（每个空有A、B、C、D四个选项）

  1. 31处应填入（）
  • A. a[i][j]
  • B. a[x][y]
  • C. a[xx][yy]
  • D. f[xx][yy]
  1. 32处应填入（）
  • A. x--; y++;
  • B. x++; y++;
  • C. x--; y--;
  • D. x++; y--;
  1. 33处应填入（）
  • A. xx = x;
  • B. xx = x; yy = y;
  • C. xx = 0; yy = 0;
  • D. xx = 1; yy = 1;
  1. 34处应填入（）
  • A. xx < n && yy > 1
  • B. xx < n || yy > 1
  • C. xx < n && yy < m
  • D. xx < n || yy < m
  1. 35处应填入（）
  • A. sum += 1
  • B. sum += 2
  • C. sum += a[xx][yy]
  • D. sum += p

（二）

题目描述

实现一个中缀表达式求值程序，支持以下运算：

  • 四种基本运算符：加 +、减 -、乘 *、除 /；
  • 支持括号嵌套：( 和 )；
  • 所有操作数为 0~9 的数字，即参与运算的数字为 0 ~ 9；
  • 不考虑负号作为负数标志； 输出最终计算结果。

保证运算过程中所有数均在 long long 范围内。

#include <bits/stdc++.h>
using namespace std;


string s;
stack <char> s1;
stack <long long> s2;

void pop_()
 {
    char c = ___36____;
    s1.pop();
    long long num1 = s2.top();
    s2.pop();
    long long num2 = s2.top();
    s2.pop();
    long long res = 0;
    if (c == '+') res = num1 + num2;
    else if (c == '-') ____37_____;
    else if (c == '*') res = num1 * num2;
    else res = num2 / num1;
    s2.push(res);
 }

int main()
 {
    cin >> s;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(') s1.push('(');
        else if (s[i] == ')')
        {
            while (_____38______)
                pop_();
            s1.pop();
        }
        else if (s[i] <= '9' && s[i] >= '0')
            s2.push(s[i] - '0');
        else
        {
            if (s[i] == '+' || s[i] == '-')
            {
                while (!s1.empty() && s1.top() != '(')
                    pop_();
            }
            else
            {
                while (!s1.empty() && (____39_____))
                    pop_();
            }
            s1.push(s[i]);
        }
    }
    while (!s1.empty())
        ____40_____;
    cout << s2.top();
    return 0;
 }

  1. 36处应填入（）
    A. s1.top() B. s2.top() C. s[0] D. s[1]

  2. 37处应填入（）
    A. res = num2 - num1 B. res = num1 - num2 C. res -= num2 D. res -= num1

  3. 38处应填入（）
    A. s1.top() != '(' B. s1.top() != ')' C. s2.top() != '(' D. s2.top() != ')'

  4. 39处应填入（）
    A. s1.top() == '+' || s1.top() == '-') B. s1.top() == '+' && s1.top() == '-') C. s1.top() == '*' || s1.top() == '/') D. s1.top() == '*' && s1.top() == '/')

  5. 40处应填入（）
    A. s1.pop() B. s2.pop() C. pop_() D. s2.top() = pop_()

我们会在赛后检查代码相似度。

状态
正在进行…
规则
ACM/ICPC
题目
1
开始于
2025-9-15 14:45
结束于
2025-12-7 22:45
持续时间
2000 小时
主持人
参赛人数
89
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 18ms
  4. Powered by Hydro v5.0.0-beta.8 Community