You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

一、单项选择题（共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. 奇偶校验编码是常见的校验编码方式。对于二进制编码 AnAn-1…A2A1，奇偶校验编码在编码的最后增加一位校验位 G，并将原编码与校验位作为整体发送。校验位分为奇校验位与偶校验位，奇校验位保证 AnxorAn-1xor…xorA2xorA1xorG=1，偶校验位保证 AnxorAn-1xor…xorA2xorA1xorG=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分）

（1）

判断题

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

• √
• ×

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

• √
• ×

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

   {{ select(18) }}

• √
• ×

选择题

4. 当输入为“15078 0 1”时，变量 nx,ny 的值分别为多少？（ ） {{ select(19) }}

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

5. 当输入为“23270 0 1”时，输出为（ ）。 {{ select(20) }}

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

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

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

（2）

判断题

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

• √
• ×

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

• √
• ×

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

• √
• ×

单选题

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

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

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

• 𝑂(𝑛 + 𝑘2)
• 𝑂(𝑛2)
• 𝑂(𝑛𝑘)
• 𝑂 (𝑛2/𝑘 )

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

• 2
• 6
• 7
• 8

（3）

判断题

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

• √
• ×

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

• √
• ×

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

• √
• ×

单选题

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

• 1
• y – x
• y – x + 1
• y – x + 2

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

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

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

• 4

• 5

• 6

• 7

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

  （1） 优美的进制 问题：给出整数 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; 
}

单选题

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

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

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

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

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

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

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

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

5. ⑤处应填（ ）。 {{ 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;
}

单选题

6. ①处可以填（ ） {{ select(39) }}

• 753005
• 10000000000
• 725041
• 2024

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

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

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

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

9. ④处应填（ ）。 {{ 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))

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

• 1
• 7
• 8
• 2