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

1. C++是一种面向对象的程序设计语言。在C++中，下面哪个关键字用于声明一个类，其缺省继承方式为private继承？（ ）{{ select(1) }}

• union
• struct
• class
• enum

2. 下述代码实现的数据结构是（ ）。

int data[100], f = 1, r; 
void insert(int value) { 
    data[++r] = value; 
} 
void pop() { 
    f++; 
}

{{ select(2) }}

• 链表
• 栈
• 队列
• 平衡树

3. C++语言中，以0b开头的数为（ ）进制数。{{ select(3) }}

• 二进制
• 八进制
• 十进制
• 十六进制

4. 根结点的高度为1，高度为5的完全二叉树至少有（ ）个结点。{{ select(4) }}

• 15
• 16
• 31
• 32

5. 右图所示的二叉树，其后序遍历的结果是什么？（ ）

{{ select(5) }}

• acedgbf
• fbacdge
• edgcabf
• egdcfba

6. 考虑右图所示的数字电路，有关逻辑门的含义已在图中标出。高电平表示true，低电平表示false。当x，y，z的输入依次为低电平、高电平、高电平时，输出为（ ）。

{{ select(6) }}

• 高电平
• 低电平
• 电路故障
• 高阻

7. 十进制数10.375转换为八进制数的结果为（ ）。{{ select(7) }}

• 10.5
• 10.3
• 12.5
• 12.3

8. 假设有一组字符{g, h, i, j, k, l}，它们对应的频率分别为8%，14%，17%，20%，23%，18%。请问以下哪个选项是字符g，h，i，j，k，l分别对应的一组哈夫曼编码？（ ）{{ select(8) }}

• g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
• g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
• g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
• g: 110, h: 111, i: 101, l: 100, k: 0, j: 01

9. 中缀表达式((6 – 3) * 2 + 7) / (5 ^ (3 * 4 + 2))对应的后缀表达式为（ ）。{{ select(9) }}

• / + * - 6 3 2 7 ^ 5 + * 3 4 2
• 6 3 2 - * 7 + 5 3 4 * 2 + ^ /
• 6 3 – 2 * 7 + 5 3 4 * 2 + ^ /
• 6 3 – 2 * 7 + 3 4 * 2 + 5 ^ /

10. 将3个相同的红球和3个相同的黑球装入三个不同的袋中，每袋均装2个球，则不同的装法总数为（ ）。{{ select(10) }}

• 7
• 8
• 9
• 10

11. 从2至8的7个整数中随机取2个不同的数，这两个数互质的概率为（ ）。{{ select(11) }}

• 1/6
• 1/3
• 1/2
• 2/3

12. 以下哪一种算法典型地使用了分治法的思想来解决问题？（ ）{{ select(12) }}

• 线性搜索
• 快速排序
• 冒泡排序
• 插入排序

13. 奇偶校验编码是常见的校验编码方式。对于二进制编码$A_{n}A_{n - 1}...A_{2}A_{1}$，奇偶校验编码在编码的最后增加一位校验位G，并将原编码与校验位作为整体发送。校验位分为奇校验位与偶校验位，奇校验位保证$A_{n}xorA_{n - 1}xor...xorA_{2}xorA_{1}xorG = 1$，偶校验位保证$A_{n}xorA_{n - 1}xor...xorA_{2}xorA_{1}xorG = 0$。下列编码与校验位对应正确的是（ ）。{{ select(13) }}

• 编码11100111奇校验位0
• 编码01100010偶校验位0
• 编码00010010奇校验位1
• 编码11100010偶校验位1

14. 下列关于NOI系列活动的有关说法，错误的是（ ）。{{ select(14) }}

• NOI考试对C++语言的使用没有限制。
• 选手不可以携带草稿纸、手机、U盘等进入考场。
• 主办单位CCF的全称为中国计算机学会。
• 在CSP第一轮考试中舞弊，可能会被给予取消考试资格、禁赛等处罚。

15. 考虑右图所示的无向图，度最大的结点为（ ）号结点。

{{ select(15) }}

• 3
• 4
• 5
• 6

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

（一）

#include <bits/stdc++.h> 
using namespace std; 
int x, y; 
unsigned int n; 
int main() { 
    cin >> n >> x >> y; 
    unsigned int mask = 0xff; 
    int x8 = x << 3; 
    int y8 = y << 3; 
    unsigned int nx = (n >> x8) & mask, ny = (n >> y8) & mask; 
    n &= (~(mask << x8)); 
    n &= (~(mask << y8)); 
    n |= (nx << y8); 
    n |= (ny << x8); 
    cout << "0x"; 
    cout << std::hex << n << endl; 
    return 0; 
} 

假设输入的n是32位无符号整数范围内的整数，x，y是不超过3的自然数，完成下面的判断题和单选题。

判断题

16. 代码中mask变量的值转化为二进制的低16位结果是0000 0000 1111 1111。（ ）{{ select(16) }}

• 正确
• 错误

17. 当输入$x = 0$的时候，nx表示n中最低八位对应的字节的数据。（ ）{{ select(17) }}

• 正确
• 错误

18. 去掉程序第11行至第12行中(~(mask << x8))和(~(mask << y8))两处中的最内层括号不会改变程序的结果。（ ）{{ select(18) }}

• 正确
• 错误

单选题

19. 当输入为“15078 0 1”时，变量nx，ny的值分别为多少？（ ） (提示：十进制数15078与十六进制数3AE6相同) {{ select(19) }}

• 0xE6, 0x3A
• 0x6, 0xE0
• 0x6, 0xE
• 0x6, 0xA

20. 当输入为“23270 0 1”时，输出为（ ）。 (提示：十进制数23270与十六进制数5AE6相同) {{ select(20) }}

• 0x5A6E
• 0x5E6A
• 0xA56E
• 0xE65A

21. 以下哪一个变量的类型修改可能影响程序的输出？（ ）{{ select(21) }}

• 将x，y修改为unsigned int类型。
• 将x8，y8修改为short类型。
• 将mask修改为int类型。
• 将nx，ny修改为unsigned long long类型。

（二）

#include <bits/stdc++.h> 
using namespace std; 
int n, k; 
int func(vector <int> &nums) { 
    int ret = 0; 
    for(int i = n; i > k; i--) { 
        if(nums[i] > nums[i - k]) { 
            swap(nums[i], nums[i - k]); 
            ret++; 
        }
    } 
    return ret; 
} 
int main() { 
    cin >> n >> k; 
    vector <int> a(n + 1, 0); 
    for(int i = 1; i <= n; i++) 
        cin >> a[i]; 
    int counter = 0, previous = -1; 
    while(counter != previous){ 
        previous = counter; 
        counter += func(a); 
    } 
    for(int i = 1; i <= n; i++) 
        cout << a[i] << ","; 
    cout << endl << counter << endl; 
    return 0; 
} 

假设输入的n，k是不超过100000的正整数，输入的a[i]是不超过$10^9$的整数，k小于等于n，完成下面的判断题和单选题。

判断题

22. 当输入的k为1，程序将a从小到大排序。（ ）{{ select(22) }}

• 正确
• 错误

23. 在题目限制的输入规模下，counter可能会溢出。（ ）{{ select(23) }}

• 正确
• 错误

24. (1分)当输入为“8 1 1 9 2 3 4 6 8 7”，输出共有18个可见字符。（ ）{{ select(24) }}

• 正确
• 错误

单选题

25. 当输入的k为1，该程序的排序方法最接近（ ）。{{ select(25) }}

• 冒泡排序
• 选择排序
• 计数排序
• 插入排序

26. 该程序的时间复杂度为（ ）。{{ select(26) }}

• $O(n + k^{2})$
• $O(n^{2})$
• $O(nk)$
• $O(\frac{n^{2}}{k})$

27. 当输入为“8 3 1 5 2 6 3 7 4 8”，输出的第一行第三个数字为（ ）。{{ select(27) }}

• 2
• 6
• 7
• 8

（三）

#include <iostream> 
#include <vector> 
#include <queue> 
using namespace std; 
const int MAXN = 200001; 
int main() { 
    int n, m, l, r, w; 
    cin >> n >> m; 
    vector <int> dist(MAXN, -1); 
    vector <bool> vis(MAXN, false); 
    vector <vector <pair<int, int> > > go(MAXN); 
    for(int i = 1; i <= m; i++) { 
        cin >> l >> r >> w; 
        go[l].push_back(make_pair(r + 1, w));  // 14
        go[r + 1].push_back(make_pair(l, -w)); // 15
    }
    queue <int> q;  // 17
    dist[1] = 0, vis[1] = true; 
    q.push(1); 
    while(!q.empty()) { 
        int x = q.front(); q.pop(); 
        for(auto i : go[x]) { 
            if(!vis[i.first]) { 
                vis[i.first] = true; 
                dist[i.first] = dist[x] + i.second; 
                q.push(i.first); 
            }
        }
    } // 29
    if(dist[n + 1] == -1) cout << "sorry" << endl; 
    else cout << dist[n + 1] << endl; 
    return 0; 
} 

假设输入的n，m是不超过200000的正整数，程序第13行每次输入的l，r保证$1 <= r$，完成下面的判断题和单选题。

判断题

28. 交换程序的第14行与第15行，不影响程序运行的结果。（ ）{{ select(28) }}

• 正确
• 错误

29. 输入的r的最大值为n时，程序可以正常运行。（ ）{{ select(29) }}

• 正确
• 错误

30. 在程序的第17行至第29行，相同的数可能重复进入队列。（ ）{{ select(30) }}

• 正确
• 错误

选择题

31. 当输入的l最小值为x，输入的r的最大值为y，最多有（ ）个元素进入过队列。{{ select(31) }}

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

32. 当输入的n为偶数，且$r = l + 1$时，m至少为（ ）时输出不为sorry。{{ select(32) }}

• $n/2$
• $n/2 + 1$
• $n/2 - 1$
• $n$

33. 当输入为“5 3 1 3 4 3 4 2 4 5 3”时，输出为（ ）。{{ select(33) }}

• 4
• 5
• 6
• 7

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

（一）（优美的进制）

问题：给出整数n；k进制是优美的，当且仅当n在k进制下至少有两位，且每一位的数值都不同。求对于给定的n，有哪些进制是优美的，不存在则输出-1。试补全程序。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int vis[MAXN],a[MAXN];
vector<int> ans;
int check(int k){ 
    int x=n,top=0;
    for(int i=0;i<=k;i++)vis[i]=0;
    while (①){
        a[++top]=②;
        x=③;
    }
    if(top<2)
        return 0;
    for(int i=1;i<=top;i++){
        if(④)
            return 0;
        vis[a[i]]=1;
    }
    return 1;
}
int main(){
    cin>>n;
    for(int i=⑤;i<=n;i++){
        if(check(i))
            ans.push_back(i);
    }
    if(ans.empty()){
        cout<<-1;
    }
    for (int i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";
    return 0;
}

34. ①处应填（ ）{{ select(34) }}

• $x > 0$
• $x > 1$
• $x/k > 0$
• $x/k > 1$

35. ②处应填（ ）{{ select(35) }}

• x/k
• x%k
• (x - 1)/k + 1
• (x - 1)%k + 1

36. ③处应填（ ）{{ select(36) }}

• x/k
• x%k
• (x - 1)/k + 1
• (x - 1)%k + 1

37. ④处应填（ ）。{{ select(37) }}

• $vis[i]==1$
• $vis[a[i]]==0$
• $vis[i]==0$
• $vis[a[i]]==1$

38. ⑤处应填（ ）。{{ select(38) }}

• 1
• $n - 1$
• 2
• 0

(2)(好运的日期)一个日期可以用x年y月z日来表示。我们称一个日期是好运的,当且 仅当xy(w-z+1)为质数,其中 W 为x年y月的总天数。输入x,y,z,判断其对应的日期是否 好运。保证x是不超过2024的正整数,y是不超过12的正整数,x,y,z可以构成一个合法 的日期。试补全线性筛法算法,空间限制512MiB。

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

const int MAXW = ①;
const int days[13] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int prime[MAXW], cnt;
bool not_prime[MAXW];

void linear_prime(int n) {
    --n;
    not_prime[0] = not_prime[1] = true;
    for (int i = 2; i <= n; i++) {
        if (not_prime[i] == false)
            prime[++cnt] = i;
        for (int j = 1; ②; j++) {
            not_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                ③;
        }
    }
}

bool check(int n) {
    return ④;
}

int main() {
    linear_prime(MAXW);
    int x, y, z, w;
    cin >> x >> y >> z;
    if (y == ⑤)
        w = check(x) ? 29 : 28;
    else
        w = days[y];
    if (not_prime[x * y * (w – z + 1)])
        cout << "unlucky" << endl;
    else
        cout << "lucky" << endl;
    return 0;
}

39. ①处应填（ ）{{ select(39) }}

• 753005
• 10000000000
• 725041
• 2024

40. ②处应填（ ）{{ select(40) }}

• j <= cnt
• i * prime[j] <= n
• (j <= cnt) && (i * prime[j] <= n)
• (i <= cnt) && (prime[i] * prime[j] <= n)

41. ③处应填（ ）{{ select(41) }}

• not_prime[i] = true
• return
• continue
• break

42. ④处应填（ ）。{{ select(42) }}

• n % 4==0
• (n%400==0 ||(n%4==0 && n%100!=0))
• (n%4==0 && n%100!=0)
• (n%100==0 ||(n%4==0 && n%100!=0))

43. ⑤处应填（ ）。{{ select(43) }}

• 1
• 7
• 8
• 2