珅泽教育CSP-J第一轮模拟考第二十套

本卷共45题，满分100分。判断题选择“正确/错误”。程序片段所需的标准库头文件视为已正确包含，除题目另有说明外，输入与存储空间有效、运算不发生整数溢出。

一、单项选择题（15题，每题2分，共30分）

第1题

IPv4 地址由多少位二进制数组成（　）。

{{ select(1) }}

• 16
• 32
• 64
• 128

第2题

8 位补码表示的 -1 是（　）。

{{ select(2) }}

• 10000000
• 11111110
• 11111111
• 00000001

第3题

元素 1、2、3、4 依次进栈，进栈过程中可以出栈。下列出栈序列不可能的是（　）。

{{ select(3) }}

• 1 2 3 4
• 4 3 2 1
• 2 1 4 3
• 3 1 2 4

第4题

在无向连通图中，$n$ 个顶点、$n-1$ 条边且无环，则该图是（　）。

{{ select(4) }}

• 完全图
• 树
• 二分图但非树
• 有向无环图

第5题

抛两枚均匀硬币，至少出现一个正面的概率是（　）。

{{ select(5) }}

• $\frac{1}{2}$
• $\frac{1}{3}$
• $\frac{3}{4}$
• $\frac{2}{3}$

第6题

爬楼梯时每次可以走 1 阶或 2 阶，走到第 5 阶共有多少种方法（　）。

{{ select(6) }}

• 5
• 6
• 8
• 13

第7题

有 6 堆石子排成一排，数量依次为：3，2，2，3，4，4，每次只能合并相邻的两堆，合并代价为这两堆石子数量之和，合并后新堆的石子数量为两堆之和。将所有石子合并成一堆的最小总代价是（　）。

{{ select(7) }}

• 46
• 47
• 48
• 49

第8题

一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 $i$（$i>1$ 且为奇数）个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（　）。

{{ select(8) }}

• $i-1$、$2i$
• $i+1$、$2i$
• $i-1$、$2i+1$
• $i+1$、$2i+1$

第9题

以下哪个函数没有递归终止条件，会不断调用自身（不考虑编译优化）（　）？

{{ select(9) }}

• int solve() {
      return 0;
  }
  

• int solve(int x) {
      return x % 2 ? 1 : 0;
  }
  

• void solve() {
      solve();
  }
  

• int solve(int n) {
      if (n <= 0) return 0;
      return solve(n - 1);
  }
  

第10题

设有一个长度为 $n$ 的 01 字符串，其中有 $k$ 个 0。每次操作可以交换相邻两个字符。在最坏情况下将这 $k$ 个 0 移到字符串最右边所需要的交换次数是（　）。

{{ select(10) }}

• $k$
• $\frac{k(k-1)}{2}$
• $(n-k)\times k$
• $\frac{k(2n-k-1)}{2}$

第11题

以下连通无向图中，（　）一定可以用不超过两种颜色进行染色。

{{ select(11) }}

• 完全三叉树
• 平面图
• 边双连通图
• 欧拉图

第12题

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心（　）。

{{ select(12) }}

• 4 个结点的树
• 6 个结点的树
• 7 个结点的树
• 8 个结点的树

第13题

假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（　）。

{{ select(13) }}

• $\Theta\!\left(m\sqrt{\log n\cdot\log\log n}\right)$
• $\Theta(n^2+m)$
• $\Theta\!\left(\frac{n^2}{\log m+m\log n}\right)$
• $\Theta(m+n\log n)$

第14题

假设有一个链表的节点定义如下：

struct Node {
    int data;
    Node* next;
};

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 1，并使新节点成为链表的第一个节点，下面哪个操作是正确的（　）。

{{ select(14) }}

• Node* newNode = new Node;
  newNode->data = 1;
  newNode->next = head;
  head = newNode;
  

• Node* newNode = new Node;
  head->data = 1;
  newNode->next = head;
  head = newNode;
  

• Node* newNode = new Node;
  newNode->data = 1;
  head->next = newNode;
  

• Node* newNode = new Node;
  newNode->data = 1;
  newNode->next = head;
  

第15题

solve(3, 3) 的返回值为（　）。

int solve(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return solve(m - 1, 1);
    return solve(m - 1, solve(m, n - 1));
}

{{ select(15) }}

• 7
• 9
• 29
• 61

二、阅读程序（判断题每题1分，选择题每题3分，共40分）

阅读程序（一）

假定所需头文件已经包含，n 为数组 a 的长度且 n≥1；输入与运算结果均在 int 的有效范围内。

int solve(int n, int a[])
{
    std::vector<int> f(n + 1);
    f[0] = 0;
    f[1] = a[0];
    for (int i = 1; i < n; ++i)
    {
        f[i + 1] = std::min(f[i], f[i - 1]) + a[i];
    }
    return std::min(f[n], f[n - 1]);
}

第16题

当传入的 a 数组为 {10, 15, 20} 时，函数的返回值为 15。（ ）

{{ select(16) }}

• 正确
• 错误

第17题

把 std::vector<int> f(n + 1); 改成 std::vector<int> f(n); 会造成编译错误。（ ）

{{ select(17) }}

• 正确
• 错误

第18题

当传入的 a 数组为 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1} 时，函数的返回值为（ ）。

{{ select(18) }}

• 1
• 2
• 6
• 7

第19题

当传入的 a 数组为 {10, 15, 30, 5, 5, 10, 20} 时，函数的返回值为（ ）。

{{ select(19) }}

• 5
• 15
• 20
• 30

第20题

当传入的 a 数组为 {3, 2, 5, 1, 4, 6} 时，函数的返回值为（ ）。

{{ select(20) }}

• 3
• 5
• 7
• 9

阅读程序（二）

假定所需头文件已经包含，n 为正整数，涉及的数组下标合法，输入与运算结果均在 int 的有效范围内；讨论 square_free[60] 时取 n>60。

int solve(int n)
{
    std::vector<int> square_free(n);

    for (int i = 1; i < n; ++i)
        square_free[i] = i;

    for (int p = 2; p * p < n; ++p)
    {
        int p2 = p * p;
        for (int j = p2; j < n; j += p2)
        {
            while (square_free[j] % p2 == 0)
            {
                square_free[j] /= p2;
            }
        }
    }

    int sum = 0;
    std::vector<int> cnt(n, 0);
    for (int i = 1; i < n; ++i)
    {
        sum += cnt[square_free[i]];
        cnt[square_free[i]]++;
    }

    return sum;
}

第21题

当 n = 5 时，函数返回 1。（ ）

{{ select(21) }}

• 正确
• 错误

第22题

当 n = 10 时，函数返回 4。（ ）

{{ select(22) }}

• 正确
• 错误

第23题

当 n = 101 时，函数返回 105。（ ）

{{ select(23) }}

• 正确
• 错误

第24题

该函数的时间复杂度为 $\Theta(n\log n)$。（ ）

{{ select(24) }}

• 正确
• 错误

第25题

square_free[60] 最终存储的是 4。（ ）

{{ select(25) }}

• 正确
• 错误

第26题

solve(30) 的返回值为（ ）。

{{ select(26) }}

• 15
• 17
• 19
• 21

第27题

变量 cnt 的作用是（ ）。

{{ select(27) }}

• 统计每个无平方因子核出现的次数
• 统计每个数字出现的次数
• 统计完全平方数的个数
• 统计质数的个数

第28题

若 $1\le i<n$，满足 square_free[i] = 1 的数字个数为（ ）。

{{ select(28) }}

• $\lfloor\sqrt n\rfloor-1$
• $\lfloor\sqrt n\rfloor+1$
• $\lfloor\sqrt{n-1}\rfloor$
• $\lfloor\sqrt n\rfloor$

阅读程序（三）

假定所需头文件已经包含，输入为合法字符串，运算结果在 int 的有效范围内。

using std::string;

string reduce(string s)
{
    string t = "";
    for (unsigned i = 1; i < s.size(); ++i) {
        t += s[i];
    }
    return t;
}

int solve(string a, string b)
{
    if (a == "") {
        return 0;
    }
    else if (b == "") {
        return 0;
    }
    else if (a[0] == b[0]) {
        return solve(reduce(a), reduce(b)) + 1;
    }
    else {
        int x = solve(reduce(a), b);
        int y = solve(a, reduce(b));
        return std::max(x, y);
    }
}

第29题

solve("", "") 的返回值为 1。（ ）

{{ select(29) }}

• 正确
• 错误

第30题

solve("abc", "acb") 的返回值为 2。（ ）

{{ select(30) }}

• 正确
• 错误

第31题

reduce("apple") 的返回值是 "appl"。（ ）

{{ select(31) }}

• 正确
• 错误

第32题

对于任意两个字符串 a 和 b，solve(a,b) 的返回值（ ）。

{{ select(32) }}

• 一定小于等于 a 的长度，也一定小于等于 b 的长度
• 一定小于 a 的长度，也一定小于 b 的长度
• 一定大于等于 a 和 b 中较短字符串的长度
• 等于 a 和 b 中较短字符串的长度

第33题

如果在调用 solve(a,b) 之前，先对 a 与 b 分别按相同的字符顺序从小到大排序，那么答案（ ）。

{{ select(33) }}

• 一定变大
• 一定变小
• 一定不变
• 可能变大，也可能不变

第34题

solve("3127846590", "0123456789") 函数返回的是（ ）。

{{ select(34) }}

• 4
• 5
• 6
• 10

第35题

若两个字符串 a、b 的长度均为 n，采用常规二维动态规划逐个计算所有前缀组合，完成相同任务，其紧确时间复杂度为（ ）。

{{ select(35) }}

• $\Theta(n)$
• $\Theta(n^2)$
• $O(n\log n)$
• $O(2^n)$

三、完善程序（每题3分，共30分）

完善程序第1题：食堂相遇

有 $N$ 名学生，其中第 $i$ 名学生进入食堂的时间为 $A_i$，离开食堂的时间为 $B_i$。两名学生如果同时出现在食堂里，称他们是一对相遇的学生。请统计有多少对学生是相遇的。如果一名学生的进入时间与另一名学生的离开时间相同，也算相遇。

代码中的 S[i]、T[i] 分别保存同一名学生的进入时间、离开时间，且 S[i] <= T[i]。

using i64 = long long;
i64 solve(int N,int S[],int T[])
{
    std::sort(S, S + N);
    std::sort(T, T + N);
    int i = _____(1)_____;
    int j = _____(2)_____;
    int cnt = 0;
    i64 meet = 0;
    while (i < N)
    {
        if (_____(3)_____) {
            _____(4)_____;
            cnt++;
            i++;
        }
        else {
            cnt--;
            _____(5)_____;
        }
    }
    return _____(6)_____;
}

第36题

（1）、（2）处应填（　）。

{{ select(36) }}

• 0，0
• 0，N - 1
• N - 1，0
• N - 1，N - 1

第37题

（3）处应填（　）。

{{ select(37) }}

• S[i] < T[j]
• S[i] <= T[j]
• S[i] > T[j]
• S[i] >= T[j]

第38题

（4）处应填（　）。

{{ select(38) }}

• meet++
• meet += j - i - 1
• meet += j - i
• meet += cnt

第39题

（5）处应填（　）。

{{ select(39) }}

• j++
• j--
• meet += j - i
• meet += cnt

第40题

（6）处应填（　）。

{{ select(40) }}

• meet
• cnt
• meet + cnt
• meet - cnt

完善程序第2题：两组等和的最大值

给定 $n=256$ 个正整数 $a_0,\ldots,a_{255}$。每个元素的数据范围是 $0<a_i\leq 2^{10}$。可以删去任意多的数字，要求剩下的数字可以分成两组，且两组数字之和完全相等，返回这个和的最大值。

const int n = 256;
int a[n];
const int maxa = 1 << 10;
const int maxd = n * maxa;
int mem[2][maxd];

int fetch(int i, int d)
{
    if (d < 0)
    {
        return _____(1)_____;
    }
    else if (d >= maxd)
    {
        return _____(2)_____;
    }
    else if (i == n)
    {
        if (d == 0)
        {
            return 0;
        }
        else
        {
            return -maxd;
        }
    }
    else
    {
        return _____(3)_____;
    }
}

void store(int i, int d)
{
    int x = _____(4)_____;
    int y = _____(5)_____;
    int z = fetch(i + 1, d);
    mem[i % 2][d] = std::max(x, std::max(y, z));
}

int solve()
{
    for (int i = n; i > 0; --i)
    {
        for (int d = 0; d < maxd; d++)
        {
            _____(6)_____;
        }
    }
    return _____(7)_____;
}

第41题

（1）处应填（　）。

{{ select(41) }}

• fetch(i, 0)
• fetch(i, -d)
• fetch(i + 1, d)
• fetch(i + 1, -d)

第42题

（2）、（3）处应填（　）。

{{ select(42) }}

• maxd，mem[0][d]
• maxd，mem[i % 2][d]
• -maxd，mem[0][d]
• -maxd，mem[i % 2][d]

第43题

（4）处应填（　）。

{{ select(43) }}

• store(i - 1, d + a[i])
• fetch(i + 1, d - a[i])
• fetch(i + 1, d) - a[i]
• fetch(i + 1, d + a[i]) + a[i]

第44题

（5）处应填（　）。

{{ select(44) }}

• store(i - 1, d + a[i])
• fetch(i + 1, d - a[i])
• fetch(i + 1, d) + a[i]
• fetch(i + 1, d - a[i]) + a[i]

第45题

（6）、（7）处应填（　）。

{{ select(45) }}

• store(i - 1, d)，fetch(0, 0) / 2
• store(i - 1, d)，fetch(n - 1, 0) / 2
• store(i - 1, -d)，fetch(0, 0) / 2
• store(i - 1, -d)，fetch(n - 1, 0) / 2