CSP 2020 第一轮（初赛）模拟

（满分：100 分 考试时间：120 分钟）

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

1. 以补码存储的 8位有符号整数 10110111的十进制表示为

{{ select(1) }}

• −73
• 183
• −72
• 72

2. 现有一段 24分钟的视频文件，它的帧率是 30 Hz，分辨率是 1920×1080，每帧图像都是 32位真彩色图像，使用的视频编码算法达到了 25%的压缩率。则这个视频文件占用的存储空间大小约是

{{ select(2) }}

• 668GiB
• 334GiB
• 85GiB
• 500GiB

3. 链接器的功能是

{{ select(3) }}

• 把源代码转换成特定硬件平台的机器指令
• 把机器指令组合成完整的可执行程序
• 把源代码转换成可执行程序
• 把高级语言翻译成低级语言

4. 对一个 𝑛个顶点，𝑚条边的带正权有向简单图使用 Dijkstra 算法计算 单源最短路时，如果再使用一个可以在 Θ(log ⁡𝑛)时间复杂度内查询堆内最 小值、在 Θ($\sqrt{𝑛}$)时间复杂度内合并两个堆、在 Θ(1)时间复杂度内将堆内一个元素变小、在 Θ(log ⁡𝑛) 时间复杂度内弹出堆内最小值的堆优化 Dijkstra 算法，则整个 Dijkstra 算法的时间复杂度为

{{ select(4) }}

• Θ(𝑛$\sqrt{𝑛}$+𝑚log⁡ 𝑛)
• Θ((𝑛+𝑚)log⁡ 𝑛)
• Θ(𝑚+𝑛 log ⁡𝑛)
• Θ(𝑚$\sqrt{𝑛}$+𝑛 log ⁡𝑛)

5. 具有 𝑛个顶点，𝑚条边的连通图采用邻接矩阵存储结构，进行深度优先遍历运算的时间复杂度为

{{ select(5) }}

• Θ($𝑛^3$)
• Θ($𝑛^2$)
• Θ(𝑛+𝑚)
• Θ($𝑚^2$)

6. 下列算法中，没有运用分治思想的一项是

{{ select(6) }}

• 归并排序算法
• 求二叉树的前序遍历
• 快速排序算法
• 求二叉树的层次遍历

7. 前缀表达式 * + a b + c d 的中缀形式是

{{ select(7) }}

• (a + b) * (c + d)
• a + b * c + d
• a * b + c * d
• (d + c) * (b + a)

8. 有 5个从 1 到 5 标号的小球和 5 个同样标号的盒子，现将小球随机放入盒子，每个盒子仅放 1 个小球，问每个盒子中的小球都与盒子标号不同的概率是

{{ select(8) }}

• $\frac{24}{625}$​
• $\frac7{20}$​
• $\frac{43}{120}$​
• $\frac{11}{30}$

9. 设 x=true,y=false,z=true。以下逻辑运算表达式值为 true 的是

{{ select(9) }}

• (¬𝑥∨𝑦)∧𝑧
• (𝑦∧𝑧)∨(𝑥∧𝑦)
• (𝑥∧𝑦)∨𝑧
• (𝑥∧𝑧)∧𝑦

10. 假设某算法的计算时间表示为递推关系式 𝑇(𝑛)=3𝑇(𝑛2)+Θ(𝑛)，𝑇(1)=Θ(1)，则算法的时间复杂度为

{{ select(10) }}

• Θ(𝑛)
• Θ($𝑛^{ log⁡_{2}{3} }$)
• Θ(𝑛 log ⁡𝑛)
• Θ($𝑛^{ log⁡_{2}{3} }$log ⁡𝑛)

11. A 班有 5 名风纪委员，B 班有 4 名风纪委员，C 班有 3 名风纪委员。现在需要这些同学中选取 6 名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有几种不同的方案？

{{ select(11) }}

• 9
• 12
• 15
• 18

12. 以下排序算法中最好情况下时间复杂度与最坏情况下时间复杂度相同的是

{{ select(12) }}

• 选择排序
• 冒泡排序
• 插入排序
• 快速排序

13. 有 4个结点和 4 条边的有标号简单无向图的数量是

{{ select(13) }}

• 15
• 16
• 6
• 4

14. 1946 年，（ ）提出了存储程序原理，奠定了现代电子计算机基本结构，开创了程序设计的新时代。

{{ select(14) }}

• 艾伦·麦席森·图灵（Alan Mathison Turing）
• 约翰·冯·诺依曼（John von Neumann）
• 克劳德·艾尔伍德·香农（Claude Elwood Shannon）
• 罗伯特·塔扬（Robert Tarjan）

15. 在计算机非专业级别软件能力认证 CSP-S 进行时，下列行为中被允许的是

{{ select(15) }}

• 使用 SSH 协议远程登录其它计算机以获取试题等文件
• 写程序在评测环境中修改输入文件
• 使用 U 盘拷贝题目及下发文件或自己的代码供赛后复盘
• 通过枚举输入文件的可能情况获得答案并写入源代码

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

1.程序一

#include <cstdio>
#include <cstring>

using namespace std;

char s[10000];
int cnt[26];

int main() {
	scanf("%s", s);
	for (int i = 0; i < strlen(s); ++i) {
		if (cnt[s[i] - 'a'] <= 50) {
			s[strlen(s)] = s[i];
		}
	++cnt[s[i] - 'a'];
	}
	printf("%s\n", s);
	return 0;
}

假设设初始时输入的字符串长度不超过 500，且不是空串。完成下面的判断题和单选题。

• 判断题

16. 将程序第 11 行中的 ++i 改为 i++，程序运行结果不会改变（ ）

{{ select(16) }}

• 正确
• 错误

17. 将程序第 11 行改为 for(int i=0,len=strlen(s);i<len;++i)， 程序的运行结果不会改变，同时程序的运行效率将得到提升（ ）

{{ select(17) }}

• 正确
• 错误

18. 对于任意一个出现了 a到 z中所有的字符、且各字符出现的次数不小于 50 的字符串 𝑏，总存在一个字符串 𝑎，使得将字符串 𝑎 输入程序后的运行结果为字符串 𝑏。（ ）

{{ select(18) }}

• 正确
• 错误

19. 程序的输出字符串长度一定不小于 1300（注：1300=50×26。（ ）

{{ select(19) }}

• 正确
• 错误

• 单选题

20. 设输入字符串长度为 𝑥(1≤𝑥≤500)，输出字符串长度为 𝑦，则关于 𝑥和 𝑦 的大小关系正确的是（ ）。

{{ select(20) }}

• 对于全部的输入字符串，都有 𝑥=𝑦。
• 对于全部的输入字符串，都有 𝑥<𝑦。
• 存在一部分输入字符串，使得 𝑥=𝑦；也存在一部分输入字符串，使得 𝑥<𝑦；但是不存在 𝑥>𝑦 的情况。
• 存在一部分输入字符串，使得 𝑥=𝑦；也存在一部分输入字符串，使得 𝑥>𝑦；还存在一部分输入字符串，使得 𝑥<𝑦。

21. (4分）设字符串 𝑤为 abcd...z，即从 a 到 z 在 𝑤中依次出现一次，共 26个字符。若输入为 𝑤重复出现两次的结果（即 abcdefg...zabcdefg...z，则输出结果为（ ）。

{{ select(21) }}

• 𝑤 重复出现 50 次的结果。
• 𝑤 重复出现 51 次的结果。
• 𝑤 重复出现 52 次的结果。
• 𝑤 重复出现 53 次的结果。

2.程序二

#include <cstdio>
 
const int N = 5010;
const int M = 20010;
const int inf = 1073741823;

int e, bg[N], nx[M], to[M], wt[M];
inline void link(int u, int v, int w) {
    to[++e] = v;
    nx[e] = bg[u];
    wt[e] = w;
    bg[u] = e;
}

int n, m, u, v, w;
int f[N], h[N << 1];

void update(int x, int y) {
    x += n - 1;
    for (h[x] = y; x; x >>= 1)
        h[x >> 1] = f[h[x]] < f[h[x^1]] ? h[x] : h[x^1];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i != m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        link(u, v, w);
    }
    int nn = n << 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j != nn; ++j)
            h[j] = 0;
        for (int j = 0; j <= n; ++j)
            f[j] = inf;
        f[i] = 0;
        update(i, i);
        for (int j = i; true; j = h[1]) {
            if (f[j] == inf) break;
            for (int k = bg[j]; k; k = nx[k]) {
                if (f[j] + wt[k] < f[to[k]]) {
                    f[to[k]] = f[j] + wt[k];
                    update(to[k], to[k]);
                }
            }
            update(j, 0);
        }
        for (int j = 1; j <= n; ++j)
            printf("%d%c", f[j], "\n "[j != n]);
    }
    return 0;
}

以上程序的输入是一张带边权的有向图，完成下面的判断题和单选题。

• 判断题

22. 将程序中所有的 != 替换为 <，程序将仍然正常运行且输出的结 果不会改变。（ ）

{{ select(22) }}

• 正确
• 错误

23. 为了保证程序正常运行，输入的边数必须不大于 2×${10}^4$。（ ）

{{ select(23) }}

• 正确
• 错误

24. 程序的输出是一个 𝑛×𝑛 的整数矩阵。（ ）

{{ select(24) }}

• 正确
• 错误

25. 将程序第 34行的 j=0 替换为 j=1，程序将仍然正常运行且输 出的结果不会改变。（ ）

{{ select(25) }}

• 正确
• 错误

• 单选题

26. 当输入的图中所有边的边权均为一个相同的正整数，且有 ∑𝑤𝑖<1073741823 时，update 函数被调用的次数为（ ）。

{{ select(26) }}

• Θ($𝑛^2$)
• Θ(𝑛𝑚)
• Θ($𝑛^2$+𝑛𝑚)-
• Θ(𝑛 min⁡(𝑛,𝑚))

27. (4分）当输入的边权均为正整数时，程序在最坏情况下的时间复杂度为（ ）。

{{ select(27) }}

• Θ($𝑛^3$)
• Θ($𝑛^2$log ⁡𝑛+𝑛𝑚)
• Θ(𝑛𝑚 log ⁡𝑛)
• Θ($𝑛^2$𝑚)

3.程序三：

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

#define N 105
#define INF 1e9

int dis1[N][N], dis2[N][N];
int mp[N][N], n, m;

void fun1(int dis[N][N]) {
  static bool vis[N];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dis[i][j] = mp[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) vis[j] = 0;
    for (int k = 1; k <= n; k++) {
      int now = 0;
      for (int j = 1; j <= n; j++) {
        if (!vis[j] && (!now || dis[i][now] > dis[i][j]))
          now = j;
      }
      vis[now] = 1;
      for (int j = 1; j <= n; j++) {
        if(!vis[j]&&dis[i][j] > dis[i][now]+mp[now][j]){
          dis[i][j] = dis[i][now] + mp[now][j];
        }
      }
    }
  }
}
void fun2(int dis[N][N]) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dis[i][j] = mp[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = 1; k <= n; k++) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j) mp[i][j] = 0;
      else mp[i][j] = INF;
    }
  }
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    mp[u][v] = w;
  }
  fun1(dis1);
  fun2(dis2);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dis1[i][j] != dis2[i][j])
        ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

以上程序的输入数据满足 1≤𝑛≤100,1≤𝑚≤$\frac{𝑛(𝑛−1)}{2}$，且只保证不存在重边，即不存在 ($𝑢_𝑖,𝑣_𝑖)=(𝑢_𝑗,𝑣_𝑗)(𝑖≠𝑗)$，边权 $𝑤_𝑖∈[1,{10}^6]$。如果 𝑢 到 𝑣 不可达，则认为距离为 INF。完成下面的判断题和单选题。

• 判断题

28. 该代码的 𝑑𝑖𝑠1[𝑖][𝑗]不一定是 𝑖到 𝑗 的最短路。（ ）

{{ select(28) }}

• 正确
• 错误

29. 输出可能为 1。（ ）

{{ select(29) }}

• 正确
• 错误

30. 将第 19行的 𝑘≤𝑛 修改为 𝑘<𝑛，不影响答案。( )

{{ select(30) }}

• 正确
• 错误

31. 对于稀疏图（𝑛,𝑚不同阶），fun1() 对于单个 𝑖 求 $𝑑𝑖𝑠[𝑖][𝑗](1≤𝑗≤𝑛)$，最快可以做到 Θ((𝑛+𝑚)log⁡ 𝑚) 。( )

{{ select(31) }}

• 正确
• 错误

• 单选题

32. 对于以下的输入数据，输出结果为（ ）

5 8
3 2 2
2 4 2
1 4 3
3 1 2
4 3 3
5 2 3
1 5 1
1 2 2

{{ select(32) }}

• 2
• 3
• 4
• 5

33. 若输入数据 𝑛=5 ，输出 𝑎𝑛𝑠 的最大可能值为（ ）

{{ select(33) }}

• 4
• 5
• 6
• 7

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

1.程序一

1. (装备穿戴问题） 有 𝑛件装备，穿戴第 𝑖 件装备需要玩家的力量值至少为$𝑎_𝑖$，穿戴该装备后会让玩家的力量值增加 $𝑏_𝑖$。现在请问玩家的初始力量值最小是多少，才能以某种顺序穿戴上所有的装备？

输入：第一行是一个整数 𝑛(1≤𝑛≤${10}^3$)；第二行有 𝑛个整数，第 𝑖个整数表示 $𝑎_𝑖$(0≤$𝑎_𝑖$≤${10}^9$)；第三行有 𝑛 个整数，第 𝑖 个整数表示$𝑏_𝑖$(0≤$𝑏_𝑖$≤${10}^6$)。

提示：使用二分+贪心的方法解决这个问题，先对装备按顺序进行排序，然后二分答案，并贪心地进行选择。

试补全程序。

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1005;

int n;
int a[maxn], b[maxn], c[maxn];

bool Comp(const int &x, const int &y) { 
    // 你可以简单地认为括号内的内容等价于 (int x, int y)
    return ①;
}

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        int u = c[i];
        if (②) {
            x += b[u];
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    for (int i = 1; i <= n; ++i) c[i] = i;
    sort(c + 1, c + 1 + n, Comp);
    int ans = 1145141919;
    for (int l=1, r=ans, mid=(l+r)/2; ③; mid=(l+r)/2)
        if (check(mid)) {
            ans = mid;
            ④;
        } else {
            ⑤;
        }
    printf("%d\n", ans);
    return 0;
}

34. ①处应填（ ）

{{ select(34) }}

• a[x] > a[y]
• a[x] < a[y]
• a[x] >= a[y]
• a[x] <= a[y]

2. ②处应填（ ）

{{ select(35) }}

• x < a[i]
• x < a[u]
• x >= a[i]
• x >= a[u]

36. ③处应填（ ）

{{ select(36) }}

• l < r
• l <= r
• check(l)
• check(r)

37. ④处应填（ ）

{{ select(37) }}

• r = mid - 1
• r = mid + 1
• l = mid - 1
• l = mid + 1

38. ⑤处应填（ ）

{{ select(38) }}

• r = mid - 1
• r = mid + 1
• l = mid - 1
• l = mid + 1

本题共 15 分

2、程序二

2. 小 A 最近喜欢上了一款音游，并希望在结算时得到特定分数，例如 1919810分。这款音游的得分计算方式如下：一共有 𝑛个音符，将一千万（${10}^7$）分平分给所有音符得到基础得分 𝑥=$\frac{{10}^7}{𝑛}$（保留非整数部分），其中有 𝑚个音符根据是否击中可以获得 𝑥+1 分或者 0 分，剩下的 𝑛−𝑚个音符根据击中精度可以获得 𝑥+1，𝑥，$\frac{𝑥}{2}$，0 分中的一个，最后将总得分向下取整即可得到最终得分。

给定 𝑛,𝑚，小 A 想知道他可以得到多少种不同的分数。

输入为两个非负整数，分别表示 𝑛,𝑚；满足，1≤𝑛≤${10}^7$,0≤𝑚≤𝑛。输出为一个正整数表示答案。试补全程序。

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    if(m==n) {
        cout<<①<<endl;
        return 0;
    }
    long long M=10000000;
    int ans=②;
    int lst=0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j>=0;--j) {
            int lower=max(0,③);
            int upper=i-j;
            int base=④;
            ans+=upper-lower+1;
            if(lower+base<=lst) ans-=lst-(lower+base)+1;
            lst=⑤;
        }
    }
    cout<<ans<<endl;
    return 0;
}

39. ① 处应填（ ）。

{{ select(39) }}

• -1
• n-1
• n
• n+1

40. ② 处应填（ ）。

{{ select(40) }}

• -1
• 0
• 1
• n

41. ③ 处应填（ ）。

{{ select(41) }}

• i - (n - m) - 1
• i - (n - m) - j
• i - (n - m)
• i - (n - m) + 1

42. ④ 处应填（ ）。

{{ select(42) }}

• (2*i+j) * M / (2*n)
• (2*i-j) * M / (2*n)-
• i * M / n + j * M / (2*n)
• i * M / n - j * M / (2*n)

43. ⑤ 处应填（ ）。

{{ select(43) }}

• base + upper
• base + upper + 1
• base + lower
• base + lower + 1

本题共 15 分