一、单项选择题（共15题）

1、关于C++中的常量，以下说法正确的是？

{{ select(1) }}

• 使用#define定义的常量，在程序运行时会单独占用一份内存空间
• const定义的常量在编译阶段会做类型检查，相比#define的安全性更高
• const定义的常量，无法通过任何方式将其修改为其他值
• #define宏定义可以写成传入参数的形式，与自定义函数的功能相同

2、四进制数 $(31.01)_4$ 转换成十六进制数为？

{{ select(2) }}

• $(C.1)_{16}$
• $(C.2)_{16}$
• $(D.1)_{16}$
• $(D.2)_{16}$

3、C++中，数组 bool a[1000]; 占用多少内存空间？

{{ select(3) }}

• $125\ \texttt{Byte}$
• $0.125\ \texttt{KB}$
• $1000\ \texttt{Byte}$
• $1\ \texttt{KB}$

4、以下哪项不是面向对象编程语言

{{ select(4) }}

• C
• C++
• Go
• Python

5、假设有一个链表的节点定义如下：

struct Node { 
    int data; 
    Node* prev; // 前驱
    Node* next; // 后继
};

现在有一个指向链表尾部的指针：Node* tail。如果想要删除该链表的末尾节点，以下哪项操作是正确的？

{{ select(5) }}

• tail->prev->next = NULL; tail=tail->prev; delete tail;
• delete tail; tail->next = NULL; tail=tail->prev;
• tail->prev->next = NULL; delete tail;
• tail=tail->prev; delete tail->next; tail->next=NULL;

6、根节点的高度为 $0$，一棵拥有 $2024$ 个节点的二叉树高度至少为（）。

{{ select(6) }}

• $9$
• $10$
• $11$
• $12$

7、老师正在排课表，一周七天时间内要至少选出两天来安排课程，而且为了保证学习效果，同一周内的两次课程之间至少要间隔一天（例如周一和周三就是间隔一天，而周一周二不是）。请问有多少种排课的方案？

{{ select(7) }}

• $15$
• $25$
• $26$
• $30$

8、中缀表达式 5*2-(3+8)*6 转成后缀表达式为？

{{ select(8) }}

• 5 2 * 3 8 + 6 * -
• 5 2 3 8 + 6 * - *
• 5 2 3 8 6 + * - *
• 5 2 * 3 8 6 + * -

9、有一篇文章仅由 a,b,c,d,e,f,g 小写字母组成，它们在文章中出现的次数分别是 200, 500, 300, 500, 900, 200, 800。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度应为？

{{ select(9) }}

• 1 或 2
• 2 或 3
• 3 或 4
• 4 或 5

10、由 $N$ 个顶点构成的无向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

{{ select(10) }}

• $2\times N$
• $2\times N - 2$
• $2\times N - 1$
• $N^2$

11、元素 $a,b,c,d,e,f,g,h$ 依次入栈，入栈的过程中可能会有出栈操作。小明在操作的过程中将出栈序列记录到了纸上，但其中一段不小心被墨水弄脏看不清了，只留下 $b,e,*,*,*,*,c,a$ 的字样（星号代表看不清的字母）。小明只记得整个过程中，栈中元素的数量没有超过 $4$，请问以下哪项可能是原本小明记录在纸上的完整出栈序列？

{{ select(11) }}

• $b,e,f,h,g,d,c,a$
• $b,e,g,f,h,d,c,a$
• $b,e,d,c,f,g,h,a$
• $b,e,d,g,h,f,c,a$

12、排序算法的稳定性指的是对于关键字相同的元素，排序后是否能保证相对位置（即前后顺序）不发生改变。以下排序算法哪项是稳定排序？

{{ select(12) }}

• 选择排序
• 归并排序
• 快速排序
• 堆排序

13、给定一棵二叉树，其中序遍历结果为：DEBACFG，后序遍历结果为：EDBGFCA。请问这棵树的正确前序遍历结果是什么？

{{ select(13) }}

• ABDECFG
• ABEDCFG
• ABDECGF
• ABEDCGF

14、一张分辨率为 1280x720 的位图图片，在文件管理器中显示的文件大小为 14.06MB，它应该是几位色的位图？

{{ select(14) }}

• 1位色位图
• 8位色位图
• 16位色位图
• 32位色位图

15、对于 $5$ 个节点的有向无环图，图中共有 $(2\rightarrow 1),(2\rightarrow 3),(2\rightarrow 4),(1\rightarrow 3),(4\rightarrow 3),(4\rightarrow 5)$ 条有向边。请问以下哪个选项是不合法的拓扑序。

{{ select(15) }}

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

二、阅读程序（程序输入数据保证不超过数组或字符串定义的范围）

（1）

#include <iostream>
#include <algorithm>
using namespace std;

int y1, m1, y2, m2;

bool check(int y){
	return (y%100!=0 && y%4==0);	
}

int days(int y, int m){
	if(m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12){
		return 31;
	}else if(m==4 || m==6 || m==9 || m==11){
		return 30;
	}else{
		if(check(y)){
			return 29;
		}else{
			return 28;
		}
	}
}

int main(){
	cin >> y1 >> m1 >> y2 >> m2;
	
	int ans=0;
	while(y2>y1 || (y2==y1 && m2>=m1)){
		ans += days(y1,m1);
		m1++;
		if(m1>12){
			m1=1;
			y1++;	
		}
	}
	cout << ans;
	return 0;
}

判断题

16、输入数据 y1=y2 且 m1=m2 时，程序输出结果为 0。

{{ select(16) }}

• 正确
• 错误

17、输入数据 y1=y2 时，输出结果最大不超过 366。（ ）

{{ select(17) }}

• 正确
• 错误

18、输入数据必须保证 y2>y1 或者 y1=y2且m2>=m1，否则程序出现运行时异常导致崩溃。（ ）

{{ select(18) }}

• 正确
• 错误

选择题

19、程序输入 y1=2024，y2=2024，m1=1，m2=4 时，输出结果为？

{{ select(19) }}

• 90
• 91
• 120
• 121

20、程序输入 y1=2000，y2=3000，m1=3，m2=3 时，由于上述程序中存在一处逻辑错误，会导致程序运行结果比实际的正确结果（）？

{{ select(20) }}

• 少 $2$
• 少 $3$
• 多 $2$
• 多 $3$

（2）

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 100005;

char S[MAXN];
char P[MAXN];
int N, M, K;

int resolve(){
    int len1 = strlen(S);
    int len2 = strlen(P);
    int delta = len2 - len1;
    int same = 0;
    int i1 = 0;
    int i2 = 0;
    while(1){
        if(delta < 0){
            return -1;
        }
        
        if(S[i1] == P[i2]){
            i1++;
            same++;
        }else{
            delta--;
        }
        i2++;
        if(i1 >= len1 && i2 >= len2) break;
    }

    if(same == len1 && delta == 0){
        return len2-len1;
    }else{
        return -1;
    }
}

int main(){
    scanf("%s", S);
    scanf("%s", P);
    printf("%d\n", resolve());
    return 0;
}

判断题

21、输入的字符串S和P相等时，输出结果为 -1。（ ）

{{ select(21) }}

• 正确
• 错误

22、输入的字符串S都为大写字母，P都为小写字母，输出结果为 -1。（ ）

{{ select(22) }}

• 正确
• 错误

23、将while循环内部最后一行if语句中的逻辑运算符由 && 改为 ||，不影响程序最终的输出结果。（ ）

{{ select(23) }}

• 正确
• 错误

选择题

24、程序输入 S=Homework，P=hHoomeXworck 时，输出结果为？

{{ select(24) }}

• -1
• 3
• 4
• 5

25、程序输入 S=Homework，P=Hamewock 时，输出结果为？

{{ select(25) }}

• -1
• 1
• 2
• 3

26、该程序的功能与下列哪个描述最接近？

{{ select(26) }}

• 计算修改几个字母能将P变为S
• 计算删除几个字母能将P变为S
• 计算修改或者删除几个字母能将P变为S
• 计算S和P有多少个字母相同

（3）

#include <iostream>
using namespace std;

const int N = 100001;

int m;
int a[N], b[N], c[N], d[N];
int f[N], g[N];

int main(){
	f[1]=g[1]=1;
	for(int i=2; i<=N; i++){
		if(!a[i]){
			b[m++]=i;
			c[i]=1, f[i]=2;
			d[i]=1, g[i]=i+1;
		}
		for(int j=0; j<m && b[j]*i<=N; j++){
			int k=b[j];
			a[i*k]=1;
			if(i%k==0){
				c[i*k]=c[i]+1;
				f[i*k]=f[i]/c[i*k]*(c[i*k]+1);
				d[i*k]=d[i];
				g[i*k]=g[i]*k+d[i];
				break;
			}else{
				c[i*k]=1;
				f[i*k]=2*f[i];
				d[i*k]=g[i];
				g[i*k]=g[i]*(k+1);
			}
		}
	}
	
	int x;
	cin >> x;
	cout << f[x] << " " << g[x] << endl;
	return 0; 
}

假设输入数据范围是 1~100 的整数，完成下面的判断题和选择题。

判断题

27、如果输入数据不等于 $1$，把 main 函数里的第一行代码删除不影响程序输出结果。（ ）

{{ select(27) }}

• 正确
• 错误

28、第23行代码 f[i] / c[i * k] 可能存在无法整除而向下取整的情况。（ ）

{{ select(28) }}

• 正确
• 错误

29、程序运行到main函数末尾时，数组 f 中的值不是单调递增的，数组 g 中的值是单调递增的。（ ）

{{ select(29) }}

• 正确
• 错误

选择题

30、程序整体时间复杂度为？

{{ select(30) }}

• $O(n)$
• $O(n\log n)$
• $O(n\sqrt{n})$
• $O(n^2)$

31、程序运行到main函数末尾时，数组 f[1]~f[100] 这100个数组元素中，有（）个的值为 $2$？

{{ select(31) }}

• $23$
• $24$
• $25$
• $26$

32、输入数据为 $1000$ 时，程序最终输出？

{{ select(32) }}

• 15 1340
• 15 2340
• 16 1340
• 16 2340

三、完善程序

（1）高精度加法计算。输入两个正整数，用字符串读取，逐位拆分转成整数数组后，以模拟数学中竖式加法“按位相加，满十进一”的思路，实现高精度计算。

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

// 高精度整数结构体
struct INT {
    int len, a[510];
        
    // 传入字符串s，逐位拆分后存入整数数组a
    INT(const char* s){
        memset(a, 0, sizeof(a));
        len = strlen(s);
        for(int i=0; i<len; i++) a[___①___] = s[i] - '0';
    }
        
    // 输出高精度整数
    void print(){
        for(int i = len - 1; i>=0; i--) printf("%d", a[i]);
    }
};

// 重载加法运算符，实现高精度数字相加，返回两数相加的结果
INT operator + (const INT& a1, const INT& a2){
    int f = 0;
    INT r("0");
    r.len = ____②____;
    for(int i=0; i<r.len; i++){
        int c = ____③____;
        f = c/10;
        r.a[i] = c % 10; 
    }
        
    if(f>0) r.a[____④____] = f;
    return r;
}


char S[505];

INT A("0"), A2("0");

int main(){
    scanf("%s", S);
    A = INT(S);
    scanf("%s", S);
    A2 = INT(S);
        
    INT r = A + A2;
    r.print();
    return 0;
} 

33、第 ① 空应填？

{{ select(33) }}

• i
• i+1
• len-i
• len-i-1

34、第 ② 空应填？

{{ select(34) }}

• max(a1.len, a2.len)
• min(a1.len, a2.len)
• a1.len+a2.len
• a1.len+a2.len+1

35、第 ③ 空应填？

{{ select(35) }}

• min(a1.len, a2.len)
• min(a1.len, a2.len) + f
• a1.a[i] + a2.a[i]
• a1.a[i] + a2.a[i] + f

36、第 ④ 空应填？

{{ select(36) }}

• 1
• r.len
• r.len++
• ++r.len

（2）井字棋。

井字棋是一种在 $3 \times 3$ 格子棋盘上进行的连珠游戏，游戏由分别代表 O 和 X 的两个游戏者轮流在格子里留下标记，任意三个相同标记形成一条直线（横、竖、对角线均可），则为获胜。一旦有胜利的一方，或是标记已经布满棋盘，则游戏结束不再继续落子。

则根据棋盘上 O 和 X 标记的分布，对应的游戏状态有 $5$ 种：

• Impossible : 按照游戏规则，不可能出现的棋局排布；
• Playing : 游戏进行中，尚未决出结果；
• OWin : 代表 O 的一方获胜；
• XWin : 代表 X 的一方获胜；
• Tie : 平局，标记已经布满棋盘但仍未决出胜负。

现已知 $T$ 组井字棋棋盘上 O 和 X 标记的分布，请编写程序判断每一组棋局对应的状态。

输入数据中 $0$ 表示对应位置为空白，$1$ 表示对应位置有 O 标记，$2$ 表示对应位置有 X 标记。例如以下是一种平局的情况：

2 1 2
2 1 2
1 2 1

注意：

① 如棋局排布不符合规则，即使有连成直线的三个相同标记也属于 Impossible。

② 游戏没有固定的先后手顺序，可由玩家自行确定。

#include <cstdio>
#include <algorithm>
using namespace std;

int T;
int A[5][5];

// 判断执x棋的一方是否三子连珠
bool check(int x){
    for(int i=1; i<=3; i++){
        bool srow = true;
        bool scol = true;
        for(int j=1; j<=3; j++){
            if(A[i][j] != x) srow = false;
            if(A[j][i] != x) scol = false;
        }
        if(____①____) return true;
    }

    if(A[1][1] == x && A[2][2] == x && A[3][3] == x) return true;
    if(A[3][1] == x && A[2][2] == x && A[1][3] == x) return true;
    return false;
}

int main(){
    int no = 0, nx = 0;
    for(int i=1; i<=3; i++){
        for(int j=1; j<=3; j++){
            scanf("%d", &A[i][j]);
            if(A[i][j] == 1) no++;
            else if(A[i][j] == 2) nx++;
        }
    }

    if(____②____) {
        printf("Impossible\n");
        return 0;
    }

    bool owin = check(1);
    bool xwin = check(2);
    if((owin && xwin) || (owin && nx > no) || (xwin && no > nx)){
        ____③____
        return 0;
    }

    if(!owin && !xwin){
        if(____④____) printf("Tie\n");
        else printf("Playing\n");
        return 0;
    }

    if(owin) printf("OWin\n");
    if(xwin) printf("XWin\n");
    return 0;
}

37、第 ① 空应填？

{{ select(37) }}

• srow || scol
• srow && scol
• !(srow || scol)
• !(srow && scol)

38、第 ② 空应填？

{{ select(38) }}

• no == 0 || nx == 0
• no > 5 || nx > 5
• no - nx > 0 || nx - no > 0
• no - nx > 1 || nx - no > 1

39、第 ③ 空应填？

{{ select(39) }}

• printf("Tie\n");
• printf("Impossible\n");
• printf("Playing\n");
• printf("666\n");

40、第 ④ 空应填？

{{ select(40) }}

• nx+no == 9
• nx==no+1 || no==nx+1
• nx==no
• nx!=no