# csp-j 初赛模拟题（一）
*信奥赛*

csp-j 初赛模拟题（一）试题部分

## 目录

[TOC]


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

## 1,以下关于C++语言的说法错误的是（ ）。
A. C++中的变量可以是字母或数字开头
B. 在函数内部声明的局部变量在函数每次被调用时被创建，在函数执行完后被销毁
C. 定义的整数常量可以带一个后缀，后缀是U和L的组合，U表示无符号整数（unsigned），L表示长整数（long）
D. for循环在传统意义上可用于实现无限循环

## 2,有7个元素，按照一定顺序进入栈S，出栈序列为1、2、3、4、5、6、7，请问下列初始序列不能通过进出栈得到给定的出栈序列的是（ ）。
A. 1325467
B. 2154376
C. 4231765
D. 6543217

## 3,运行以下代码后，y的值将变成（ ）。
```
int x = 25;
int *p = &x;
int y = 30;
int *q = &y;
(*q)++;
q = p;
(*q)++;
p = q;
(*p)++;
```
A 30
B 31
C 26
D 27

## 4,以下关于队和链表的描述正确的是（ ）。
A. 一个队列可以用一个链表来实现，一个链表也可以存储等价的信息
B. 可以用一个链表实现一个基础的链表
C. 可以用一个队列来实现一个基础的链表
D. 说法错误的是：队列比链表需要的存储空间更大


## 5,用单向链表可以高效实现栈的入栈、出栈和向栈顶的读操作（ ），不可能得到 d、c、e、a、b 的出栈序列。
A. 用单向链表可以高效实现栈的入栈、出栈和向栈顶的读操作，不可能得到 d、c、e、a、b 的出栈序列
B. 单向链表可以实现一个基础的链表
C. 弹出一个复杂顶项的时间复杂度均可做到 O(1)
D. 单向链表不能用实现队列

## 6,对表达式 (a-(b-c)d-e)/f 的后缀表达式为（ ），其中 +、-、、/ 是运算符。
A. abc-*de-f/
B. ab-cd-*e-f/
C. abc-*d-e-f/
D. a-bcd-*e-f/

## 7,假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 25%、30%、14%、30%、21%。若使用哈夫曼编码的方式对字符进行不定长的二进制编码，每次字符符合条件并能保证左兄弟等于右兄弟（左兄弟编码为 0，右儿子编码为 1），则字符串 bceda 的编码结果为（ ）。
A. 01001100110
B. 0001101001
C. 000110100110
D. 01010100110

## 8,一棵有 n 个节点的满二叉树，如果执行如下操作：删除该棵裸树最左边的节点的点 p 和 p 的整棵子树，最左边的节点是指从根节点开始一直向左（左右子节点没有左子节点的点。重复执行操作直到是根节点，则最终剩下的树的节点数为（ ）。
A. 2^(n-1)-1
B. 2^(n-1)-1
C. 1
D. 2^(n-1)

## 9,一个具有 N 个节点和 (N-1) 条边的有向图，不存在自环，在最坏情况下，最少需要添加（ ）条边才能使整个图保证任意两个点之间都有边路经可达。
A. N
B. N-1
C. 1
D. 2^(n-1)

## 10. 有一个 \( n \) 个顶点 \( m \) 条边的图，以下关于存储该图的说法错误的是（ ）。
A. 如果使用邻接表存储，遍历整个图的时间复杂度为 \( O(n+m) \)
B. 如果只是想要查询是否存在从 \( u \) 到 \( v \) 的边，在不考虑空间使用的情况下，使用邻接矩阵比使用邻接表更快
C. 使用链式前向星存图时，虽然不能快速查询一条边是否存在，但是可以方便地对一个点的出边进行排序
D. 如果使用邻接矩阵存储，需要保证这张图中没有重边

## 11. 当使用数组模拟队列时，设 \( q \) 是队列对应的数组，\( \text{head} \) 是队头对应的数组下标，\( \text{tail} \) 是队尾对应的数组下标。如果想要完成在队列末尾插入元素 \( a \)，并将队首弹出，以下操作能完成的是（ ）。
A. \( q[--\text{head}] = a \); \( \text{tail}++ \);
B. \( q[++\text{tail}] = a \); \( \text{head}++ \);
C. \( q[\text{tail}++] = a \); \( \text{head}-- \);
D. \( q[\text{head}--] = a \); \( \text{tail}-- \);

## 12. 以下关于排序算法的说法中，错误的是（ ）。
A. 在最坏情况下，冒泡排序要执行 \( \frac{n(n-1)}{2} \) 次交换操作
B. 插入排序的最优时间复杂度为 \( O(n) \)
C. 当使用归并排序将两个长为 \( n \) 的有序数组合并时，时间复杂度为 \( O(n \log(n)) \)
D. 排序算法的稳定性是指相等的元素经过排序之后相对顺序是否发生了改变

## 13. 十六进制数 \( 6C.5 \) 对应的二进制数是（ ）。
A. \( 1101100.0011 \)
B. \( 1101100.0101 \)
C. \( 1101011.1 \)
D. \( 1101011.11 \)

## 14. 定义字符串的字典序排序为以第 \( i \) 个字符作为第 \( i \) 关键字比较大小，且空字符小于字符集内任何字符。定义一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 \( adbc \) 字典序第 6 小的子串是（ ）。
A. \( ad \)
B. \( db \)
C. \( bc \)
D. \( adbc \)

## 15. 对于下面这个函数，运行 \( f(4, 5) \) 得到的结果是（ ）。
```cpp
int f(int m, int n)
{
    if (m == 0)
        return 0;
    if (n == 0)
        return 1;
    if (n > m)
        return f(m, n - 1) * n;
    else
        return f(m - 1, n - 1) * m;
}
```
A. 0  
B. 120  
C. 96  
D. 100  

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

##（一）阅读下列程序。
```cpp
01 #include <iostream>
02 
03 using namespace std;
04 
05 int main()
06 {
07     unsigned long long x;
08     long long y;
09     cin >> x >> y;
10     x = x ^ x << 2;
11     y = y & (unsigned long long)(-1);
12     unsigned long z = ((x > y) >> 30) & (1 <= 5 ? 3 : -1);
13     cout << z << endl;
14     return 0;
15 }
16
```

假设输入的 \( x \), \( y \) 是满足 \( -2^{64} < x, y < 2^{64}-1 \) 的整数。完成下面的判断题和选择题。

### 判断题

16， 将第12行的 unsigned 改为 signed long long，程序行为不变。（ ）
17， 程序输出一定是 “0” “1” “2” “3” 中的一个。（ ）
18， 当输入为 “4 5” 时，输出为 “0”。（ ）
19， （2分）当输入的 \( x \), \( y \) 满足 \( 0 < x, y < 100 \) 时，输出均为 “0”。（ ）

### 选择题
20， （4分）当输入为 “-2 -1” 时，输出为（ ）。
A. 31  
B. 0  
C. 1  
D. 2

好的，我会帮你提取题目中的文字内容，并且不会在代码部分添加行号。

##（二）阅读下列程序。

```cpp
#include <iostream>
using namespace std;

int f(int n, int m)
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int sum = 0, p = 1;
        for (int t = 0; t <= n; t++)
        {
            int r = t + 1;
            if (r > n)
                continue;
            for (int i = p; i <= n; i++)
                if (i > r)
                    break;
                else
                    sum += i;
            if (sum >= m)
                ans++;
            p++;
        }
    }
    return ans;
}

int g(int n, int m)
{
    static int sum[1000];
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + i;
    int ans = 0;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)
            if (sum[r] - sum[l - 1] >= m)
                ans++;
    return ans;
}

int main()
{
    int n, m;
    cin >> n >> m;
    cout << f(n, m) << endl;
    cout << g(n, m) << endl;
    return 0;
}
```

假设输入的 \(n, m\) 是满足 \(0 < n, m < 1000\) 的正整数，完成下面的判断题和选择题。

- 判断题
  21. 当输入为“5 5”时，输出的第二行为“12”。（）
  22. 输出的第二行总是比第一行数字大。（）
  23. 当 \(n=1\) 时，无论 \(m\) 是多少，答案一定是“0”或者“1”。（）

- 选择题
  24. 算法 \(f(n, m)\) 最为准确的时间复杂度分析结果为（）。
      A. \(O(n)\)
      B. \(O(n^2)\)
      C. \(O(n^3)\)
      D. \(O(n^2 \log n)\)

  25. 当输入为“10 30”时，输出的第一行为（）。
      A. 15
      B. 16
      C. 17
      D. 18

  26. 当输入为“20 210”时，输出的第一行为（）。
      A. 210
      B. 10
      C. 118
      D. 1

##（三）阅读下列程序。

```cpp
#include <iostream>
using namespace std;

int calc(int n)
{
    int mx = 0, val = 1;
    while (true)
    {
        if (val * 4 > n)
            break;
        mx++;
        val <<= 2;
    }
    int x = 0, adder = 1 << mx;
    for (int i = mx; i >= 0; i--)
    {
        if (n >= val)
        {
            while (n >= val)
                n -= val;
            x += adder;
        }
        val >>= 2;
        adder >>= 1;
    }
    return x;
}

int main()
{
    int n;
    cin >> n;
    cout << calc(n) << endl;
    return 0;
}
```

假设输入的 \(n\) 是满足 \(0 < n < 5001\) 的正整数，完成下面的判断题和选择题。

### 判断题

27，当输入为“10”时，输出为“3”。（）
28，在给定的数据范围内，输出结果的最大值为“95”。（）
29，输入的 \(n\) 越大，输出结果越大。（）
30，该算法是在计算 \(n\) 开根后的结果。（）

### 选择题

31, 有（）种不同的输入 \(n\)，可以使最后的输出为“5”。
A. 1
B. 9
C. 7
D. 15

32, 该算法最准确的时间复杂度分析结果为（）。
A. \(O(\log n)\)
B. \(O(\log \log n)\)
C. \(O(n)\)
D. \(O(n^2)\)

33, 当输入的 n 满足 4096 < n 时，所有输出结果最大值减去最小值的差值为（ ）。 
A. 64
B. 31
C. 32
D. 28

三、完善程序（单选题，每小题 3 分，共计 30 分）
（一）（非对应排列）对于一个长度为 n 的排列，如果这个排列中所有的元素都不在自己原来的位置上，就称这个排列是一个非对应排列。求所有长度为 n 的排列中有多少个是非对应排列。试补全程序。

```
01 #include <iostream>
02 using namespace std;
04 int n, ans, A[15];
06 bool vis[15];
07 void dfs(const int p)
09 {
10     if (p > n)
11     {
12         ans++;
13         return;
14     }
15     for (int i = 1; i <= n; i++)
16         if (①)
17         {
18             ②;
19             dfs(p + 1);
20             ③;
21         }
22     }
23 }
24 int main()
25 {
26     cin >> n;
27     dfs(1);
28     cout << ans << endl;
29     return 0;
30 }
31

```
34, ① 处应填（ ）。 
A. 0 
B. p > n + 1
C. true
D. A[p] != p

35, ② 处应填（ ）。
A. Vis[i] == true && i != p
B. A[p] == i && i != p
C. Vis[i] == false && i != p
D. A[p] == i && i != p

36, ③ 处应填（ ）。
A. A[p] = i
B. A[i] = p
C. Vis[i] = true
D. Vis[i] = false

37, ④ 处应填（ ）。
A. A[p] = 0
B. A[i] = 0
C. Vis[i] = false
D. Vis[i] = true

38, ⑤ 处应填（ ）。
A. dfs(1, n)
B. dfs(n)
C. dfs(1)
D. dfs(n+1)

（二）（最大子树和）现在有一个 n 个节点的树，每个点有权，点权可能是正数也可能是负数。现在想要求，在任何一个节点都可以做根节点的情况下，点权和最大的子树的点权和是多少。试补全程序。

```
01 #include <iostream>
02 #include <vector>
03 using namespace std;
05 const int N = 105;
07 int n, ans, total, sum[N], value[N];
08 vector<int> E[N];
10 void dfs(int u, int fa)
12 {
13     sum[u] = value[u];
14     for (vector<int>::iterator it = E[u].begin(); it != E[u].end(); it++)
15     {
16         ____①____;
17         if (v == fa)
18             continue;
19         dfs(v, u);
20         ____②____;
21         ____③____;
22     }
23     ____④____;
24 }

26 int main()
27 {
28     cin >> n;
29     for (int i = 1; i <= n; i++)
30     {
31         cin >> value[i];
32         total += value[i];
33     }
34     for (int i = 1; i < n; i++)
35     {
36         int u, v;
37         cin >> u >> v;
38         ____⑤____;
39     }
40     dfs(1, 0);
41     cout << ans << endl;
42     return 0;
43 }
```

39, ① 处应填（ ）。
A. int v = *it
B. int v = it
C. int v = &it
D. int v = E[it]

40, ② 处应填（ ）。
A. ans = max(ans, total - sum[u])
B. ans = max(ans, total - sum[u] + sum[v])
C. ans = max(ans, sum[u] - sum[v])
D. ans = max(ans, total - sum[v])

41, ③ 处应填（ ）。
A. sum[u] += sum[v]
B. total -= sum[v]
C. sum[v] += sum[u]
D. total += sum[v]

42, ④ 处应填（ ）。
A. ans = max(ans, sum[fa])
B. ans = max(ans, total - sum[u])
C. ans = max(ans, sum[u])
D. ans = max(ans, sum[fa] - sum[u])

43, ⑤ 处应填（ ）。
A. E[u][v] = 1; E[v][u] = 1;
B. E[u][u] = 1; E[v][v] = 1;
C. E[u].push_back(v); E[v].push_back(u);
D. E[u].push_back(u); E[v].push_back(v);

------
***操作记录***
作者：[zhao](https://www.lingyuzhao.top//index.html?search=4 "zhao")
操作时间：2025-08-09 21:58:59 星期六 【时区：UTC 8】
事件描述备注：保存/发布
 中国 天津市 天津
[](如果不需要此记录可以手动删除，每次保存都会自动的追加记录)