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

【第 1 题】

在NOI Linux系统中，列出文件夹内所有文件的命令是（ ）。

{{ select(1) }}

• dir
• display
• ls
• show

【第 2 题】

在C++语言中，容器vector类型不包含函数（ ）。

{{ select(2) }}

• top()
• front()
• back()
• pop_back()

【第 3 题】

已知开放集合S规定，如果正整数$x$属于该集合，则$2x$和$3x$同样属于该集合。若集合包含1，则集合一定包含（ ）。

{{ select(3) }}

• 2024
• 1536
• 2025
• 2026

【第 4 题】

已知由$x$个点组成的森林中有$y$棵树，则此森林中有（ ）条边。

{{ select(4) }}

• $x-y+1$
• $x-y-1$
• $x-1$
• $x-y$

【第 5 题】

如下图所示，$A$到$B$是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让$A,B$不连通，最小代价是（ ），最小代价的不同方案数是（ ）。（只要有一条删除的边不同，就是不同的方案）

{{ select(5) }}

• 4 9
• 3 9
• 4 10
• 2 9

【第 6 题】

某大学计算机系排课，某些课程需要先学才能学习后续的课程，这个排课过程中常用的算法是（ ）。

{{ select(6) }}

• 堆排序
• 拓扑排序
• 插入排序
• 归并排序

【第 7 题】

下图表示一个果园灌溉系统，有 A、B、C、D 四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的有（ ）。

{{ select(7) }}

• B 打开，其他都关上
• AB 都打开，CD 都关上
• A 打开，其他都关上
• D 打开，其他都关上

【第 8 题】

一个$1 \times 8$的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有（ ）种填涂方案。

{{ select(8) }}

• 54
• 55
• 56
• 57

【第 9 题】

某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。最少要安排（ ）个不同的考试时段才能避免冲突？

{{ select(9) }}

• 3
• 4
• 5
• 6

【第 10 题】

#include <iostream> 
using namespace std;
int main()
{
    int a[6] = {1, 2, 3, 4, 5, 6};
    int pi = 0;
    int pj = 5;
    int t, i;
    while (pi < pj)
    {
        t = a[pi];
        a[pi] = a[pj];
        a[pj] = t;
        pi++;
        pj--;
    }
    for (i = 0; i < 6; i++)
        cout << a[i] << ",";
    cout << endl;
    return 0;
}

该程序输出为（ ）。

{{ select(10) }}

• 6,5,4,3,2,1,
• 6,5,4,3,2,1
• ,6,5,4,3,2,1,
• ,6,5,4,3,2,1

【第 11 题】

关于C++语言中类的说法中错误的是（ ）。

{{ select(11) }}

• 以struct声明的类中的成员默认为public形式
• 以class声明的类中的成员默认为private形式
• 以private关键字修饰的类对象，可以直接访问，但不能修改其成员数据
• 类可被认为是包含其成员的名字空间

【第 12 题】

下面的编码组合中，（ ）不是合法的哈夫曼编码。

{{ select(12) }}

• (0, 1, 00, 11)
• (00, 01, 10, 11)
• (0, 10, 110, 111)
• (1, 01, 000, 001)

【第 13 题】

若事件$A$和事件$B$相互独立，二者发生的概率相同，即$P(A)=P(B)$，且$P(A \cup B)=0.64$，则事件$A$发生的概率$P(A)=$（ ）。

{{ select(13) }}

• 0.3
• 0.4
• 0.6
• 0.8

【第 14 题】

将8本不同的书分给5个人，其中3个人各拿一本，1个人拿两本，1个人拿三本，共有（ ）种分配法。

{{ select(14) }}

• 33600
• 36000
• 72000
• 67200

【第 15 题】

随机生成$n$个各不相同的正整数数组元素，快速排序算法的第一轮执行一遍以后，已经被排到正确位置的元素至少有（ ）个。

{{ select(15) }}

• $n/2$
• $n/3$
• 1
• 0

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

阅读程序1

01 #include <bits/stdc++.h>
02 
03 using namespace std;
04 
05 #define ll long long
06 
07 int read() {
08     int x=0, f=1; char ch=' ';
09     while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
10     while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
11     return x*f;
12 }
13 
14 int a[50], len, f[50][65], vis[50][65];
15 
16 int dfs(bool limit, bool lead, int pos, int cha) {
17     if(pos==0) return cha>=30;
18     if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
19     int res=0;
20     int up=limit?a[pos]:1;
21     for(int i=0;i<=up;i++) {
22         res+=dfs(limit&&(i==a[pos]), lead&&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));
23     }
24     if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;
25     return res;
26 }
27 
28 int solve(int x) {
29     len=0;
30     while(x) {
31         a[++len]=x%2;
32         x/=2;
33     }
34     return dfs(1, 1, len, 30);
35 }
36 
37 int main() {
38     int l=read(), r=read();
39     cout<<solve(r)-solve(l-1);
40 }

假设输入的数据不会超过 $10^9$，回答下列问题。

判断题

16、该程序能够计算$[l, r]$区间内所有二进制下有且仅有一个$0$的数字的数量（例如$2=10, 101, 1101$）。

{{ select(16) }}

• 正确
• 错误

17、如果输入$0\ 0$，则该程序获得结果$12$。

{{ select(17) }}

• 正确
• 错误

18、如果输入$2\ 12$，则该程序获得结果$6$。

{{ select(18) }}

• 正确
• 错误

19、第31行代码的执行次数不会超过$60$次。

{{ select(19) }}

• 正确
• 错误

单选题

20、以下说法中正确的是（ ）。

{{ select(20) }}

• 该程序的时间复杂度为$O(\text{NlogN})$。
• 该程序能够将double类型的数无误差地用a表示。
• 输入$15\ 15$时，程序输出为$0$。
• 如果把除main函数前的int全改为ll，程序能够正确处理long long范围内的输入数据。

21、对于以下哪组输入，程序会输出最大值？（ ）

{{ select(21) }}

• $1\ 11$
• $2\ 12$
• $3\ 13$
• $4\ 14$

阅读程序2

01 #include <algorithm>
02 #include <iostream>
03 #include <fstream>
04 #include <vector>
05 using namespace std;
06 
07 const int INF = 1000000000;
08 template<class T> inline int Size(const T&c) { return c.size(); }
09 
10 struct Impossible {};
11 
12 vector<int> breeds;
13 vector<int> volumes;
14 
15 void ReadInput() {
16     int n,b; cin >> n >> b;
17     for(int i=0;i<b;++i) {
18         int v; cin >> v; breeds.push_back(v);
19     }
20     for(int i=0;i<n;++i) {
21         int v; cin >> v; volumes.push_back(v);
22     }
23 }
24 
25 vector<int> knapsack;
26 
27 void ExtendKnapsack() {
28     int t = Size(knapsack);
29     int v = INF;
30     for(int i=0;i<Size(breeds);++i) {
31         int t2 = t - breeds[i];
32         if(t2>=0) v = min(v, 1 + knapsack[t2]);
33     }
34     knapsack.push_back(v);
35 }
36 
37 int Knapsack(int total) {
38     if(total<0) throw Impossible();
39     while(total >= Size(knapsack)) ExtendKnapsack();
40     if(knapsack[total]==INF) throw Impossible();
41     return knapsack[total];
42 }
43 
44 int Solve() {
45     knapsack.assign(1, 0);
46     int carry = 0;
47     int res = 0;
48     for(int i=0;i<Size(volumes);++i) {
49         carry = max(carry-1, 0);
50         int v = volumes[i] - carry;
51         res += Knapsack(v);
52         carry = volumes[i];
53     }
54     return res;
55 }
56 
57 int main() {
58     ReadInput();
59     try {
60         cout<< Solve() << "\n";
61     } catch (Impossible) {
62         cout << "-1\n";
63     }
64 }

假设输入总是满足 $1 \le n, b \le 500$。

判断题

22、knapsack 容器的初始容量是 $1$。

{{ select(22) }}

• 正确
• 错误

23、对如果 total 小于 $0$，Knapsack 函数会抛出 Impossible 异常。

{{ select(23) }}

• 正确
• 错误

24、如果 breeds 不全为 $0$，那么输出一定不为 $0$。

{{ select(24) }}

• 正确
• 错误

单选题

25、若程序输入

4 3
4 2 1
0 4 5 7

{{ select(25) }}

• $0$
• $-1$
• $3$
• $4$

26、下列说法中正确的是（ ）。

{{ select(26) }}

• ExtendKnapsack 函数本质上实现了一个背包功能，并且在复杂度上比普通背包更优秀。
• knapsack[$i$] 表示和为 $i$ 时最少使用 breeds 中的数的个数（可重复使用，使用几次计几个）。
• 这段代码的时间复杂度是 $O(K \ast N)$（$K$ 指的是 b 数组的值域，$N$ 指的是 b 数组的大小）。
• 若 volume[$i$] 都为一个值的话，程序要么输出 $0$，要么输出 $-1$。

阅读程序3

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define N 2000005
04 int n,a[N];
05 pair<int,int>dp[N][10],ans;
06 string s,b="?bessie";
07 pair<int,int> add(pair<int,int> x,pair<int,int> y)
08 {
09     return {x.first+y.first,x.second+y.second};
10 }
11 pair<int,int> Max(pair<int,int> x,pair<int,int> y)
12 {
13     if(x.first==y.first)
14     {
15         if(x.second<y.second)
16             return x;
17         return y;
18     }
19     if(x.first>y.first)
20         return x;
21     return y;
22 }
23 int main()
24 {
25     cin >> s;
26     n=s.size();
27     s=" "+s;
28     for(int i=1;i<=n;i++)
29     {
30         scanf("%d",&a[i]);
31     }
32     for(int i=0;i<=n;i++)
33     {
34         for(int j=0;j<=6;j++)
35         {
36             dp[i][j]={-100,100};
37         }
38     }
39     dp[0][0]={0,0};
40     for(int i=1;i<=n;i++)
41     {
42         dp[i][0]=dp[i-1][0];
43         if(s[i]==b[6])
44             dp[i][0]=Max(dp[i][0],add(dp[i-1][5],{1,0}));
45         for(int j=1;j<=5;j++)
46         {
47             dp[i][j]=add(dp[i-1][j],{0,a[i]});
48             if(s[i]==b[j])
49                 dp[i][j]=Max(dp[i][j],dp[i-1][j-1]);
50         }
51     }
52     for(int i=0;i<=5;i++)
53     {
54         ans=Max(ans,dp[n][i]);
55     }
56     printf("%d %d",ans.first,ans.second);
57 }

输入数据 n、c、nums[i]≤${2 \times 10^5}$，且均为正整数。

判断题

27、本题中 ans.second 表示的是满足字符串 bessie 出现次数最多的条件时最小的删除代价和。

{{ select(27) }}

• 正确
• 错误

28、如果将第 6 行代码修改为 string s,b="?beef";，程序将变成求 s 删除去若干字符后最多能出现多少个 beef 以及求满足 beef 出现次数最多的前提下最小的删除代价和。

{{ select(28) }}

• 正确
• 错误

单选题

29、dp[$i$][$j$].first 的含义是（ ）。

{{ select(29) }}

• 通过删除一些字符，字符串前 $i$ 位匹配到 bessie 的第 $j$ 位的，之前匹配了 dp[$i$][$j$].first 个 bessie。
• 通过删除一些字符，字符串前 $i$ 位匹配到 bessie 的第 $j$ 位的，之前匹配了 dp[$i$][$j$].second 个 bessie。
• 通过删除一些字符，字符串前 $i$ 位有 $j$ 个 bessie，并且最后匹配到字符串 b 的 dp[$i$][$j$].first - 1 位。
• 通过删除一些字符，字符串前 $i$ 位有 $j$ 个 bessie，并且最后匹配到字符串 b 的 dp[$i$][$j$].first 位。

30、如果本题中输入：

Besgiraffesiebessiebessie

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

则程序输出为（ ）。

{{ select(30) }}

• $1\ 18$
• $2\ 13$
• $1\ 0$
• $3\ 7$

31、对于以下哪种情况，程序可能会发生运行错误或者输出错误答案？（ ）

{{ select(31) }}

• 输入了一个长度为 $0$ 的字符串。
• 输入了一个长度为 $200000+2$ 的字符串，并且数组 $a$ 的平均值不超过 $10000$。
• 输入了一个长度为 $200000$ 的字符串，并且数组 $a$ 的平均值超过 $100000$。
• 输入了一个长度为 $200000+100$ 的字符串，并且 $a$ 都是 $1$。

32、下列说法中正确的是（ ）。

{{ select(32) }}

• 在本段程序中 Max({1,4},{2,3}) 返回 {1,4}。
• 将第 36 行代码 dp[i][j]={-100,100}; 改成 dp[i][j]={-1,1};，程序仍能运行并且输出正确答案。
• 在一些情况下，dp[n][6] 也可能是正确答案。
• 这段代码的时间复杂度是 $O(N \log N)$，其中 $N$ 代表字符串的长度。

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

程序填空1

（大整数除法）给定两个正整数 $p$ 和 $q$，其中 $p$ 不超过 $10^{100}$，$q$ 不超过 $100000$，求 $p$ 除以 $q$ 的商和余数。

输入：第一行是 $p$ 的位数 $n$，第二行是正整数 $p$，第三行是正整数 $q$。 输出：两行，分别是 $p$ 除以 $q$ 的商和余数。

#include <iostream>
using namespace std;
int p[100];
int n, i, q, rest;
char c;
int main()
{
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> c;
        p[i] = c - '0';
    }
    cin >> q;
    rest = (1);
    i = 1;
    while ((2) && i < n)
    {
        rest = rest * 10 + p[i];
        i++;
    }
    if (rest < q)
        cout << 0 << endl;
    else
    {
        cout << (3);
        while (i < n)
        {
            rest = (4);
            i++;
            cout << rest / q;
        }
        cout << endl;
    }
    cout << (5) << endl;
    return 0;
}

33、① 处应填（ ）

{{ select(33) }}

• p[0]
• p[1]
• 0
• 1

34、② 处应填（ ）

{{ select(34) }}

• rest<=q
• rest<q
• *p<=q
• p[1]<q

35、③ 处应填（ ）

{{ select(35) }}

• rest%q
• n/q
• rest/q
• n%q

36、④ 处应填（ ）

{{ select(36) }}

• rest*10+p[i]
• rest%q*10
• (rest*10+p[i])%q
• rest%q*10+p[i]

37、⑤ 处应填（ ）

{{ select(37) }}

• rest%q
• n/q
• rest/q
• n%q

程序填空2

（最长路径）给定一个有向无环图，每条边长度为 1，求图中的最长路径长度。（第五空 2 分，其余 3 分）

输入：第一行是结点数 $n$（不超过 $100$）和边数 $m$，接下来 $m$ 行，每行两个整数 $a,b$，表示从结点 $a$ 到结点 $b$ 有一条有向边。结点编号从 $0$ 到 $(n-1)$。输出：最长路径长度。

提示：先进行拓扑排序，然后按照拓扑序计算最长路径。

.

#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100];     // 记录每个结点的入度
int len[100];        // 记录以各结点为终点的最长路径长度
int queue[100];      // 存放拓扑排序结果
int main()
{
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            graph[i][j] = 0;
    for (i = 0; i < n; i++)
        degree[i] = 0;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b;
        graph[a][b] = 1;
        (1);
    }
    tail = 0;
    for (i = 0; i < n; i++)
        if ((2))
        {
            queue[tail] = i;
            tail++;
        }
    head = 0;
    while (tail < n - 1)
    {
        for (i = 0; i < n; i++)
            if (graph[queue[head]][i] == 1)
            {
                (3);
                if (degree[i] == 0)
                {
                    queue[tail] = i;
                    tail++;
                }
            }
        (4);
    }
    ans = 0;
    for (i = 0; i < n; i++)
    {
        a = queue[i];
        len[a] = 1;
        for (j = 0; j < n; j++)
            if (graph[j][a] == 1 && len[j] + 1 > len[a])
                len[a] = len[j] + 1;
        if ((5))
            ans = len[a];
    }
    cout << ans << endl;
    return 0;
}

38、①处应填（ ）。

{{ select(38) }}

• degree[b]++
• degree[a]++
• graph[b][a] = 1;
• a--,b--

39、②处应填（ ）。

{{ select(39) }}

• degree[i]==1
• degree[i]==0
• degree[i]++
• degree[i]--

40、③处应填（ ）。

{{ select(40) }}

• degree[i]==1
• degree[i]==0
• degree[i]--
• degree[i]++

41、④处应填（ ）。

{{ select(41) }}

• head--
• head=1
• head=0
• head++

42、⑤处应填（ ）。

{{ select(42) }}

• ans<len[a]
• ans<=len[a]
• ans>0
• ans!=0