CCF GESP 2024年6月认证 C++ 4级真题 —— NOI 金牌讲师逐题深度剖析与题解

金牌讲师寄语：
GESP 4级是 CCF 编程能力等级认证中承上启下的枢纽级别，全面接轨 CSP-J（普及组） 的基础核心考点。
本卷聚焦考查：函数调用与形参与实参传递机制、作用域与变量隐藏生命周期、指针运算与多维数组行主序内存模型、基本排序算法（冒泡、直接插入、选择）的机理与复杂度分析、异常处理（try-catch）、引用底层本质 等核心模块。
本题解由 NOI 金牌教练团队精心推导打磨，不仅给出权威答案，更带你透视编译器底层实现与核心避坑指南，助你建立扎实严密的算法竞赛底蕴！

---

快速查对表

单项选择题（15 题，共 30 分）

题号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
官方答案	B			D	B	D		A		B	A	D	A	B	D

判断题（10 题，共 20 分）

题号	16	17	18	19	20	21	22	23	24	25
官方答案	错 (F)	对 (T)			错 (F)	对 (T)

---

一、单项选择题（每题 2 分，共 30 分）

第 1 题

【题目内容】
下列代码中，输出结果是（ ）

#include<iostream>
using namespace std;
int func(int x, int y)
{
	int a = x, b = y;
	int t;
	t = a;
	a = b;
	b = t;
	cout << a << " " << b << " ";
}
int main()
{
	int c, d;
	c = 12;
	d = 24;
	func(12, 24);
	cout << c << " " << d << endl; 
    return 0;
}

• A. 12 24 24 12
• B. 24 12 12 24
• C. 12 12 24 24
• D. 24 24 12 12

【答案】B
【考点】 函数值传递（Pass by Value）与局部变量作用域
【讲师深度解析】

1. 函数内部执行：main 函数中调用 func(12, 24)。进入 func 后，x = 12, y = 24。局部变量 a = 12, b = 24，经三杯水交换后变为 a = 24, b = 12。紧接着在函数内输出 a 和 b，打印 24 12 （末尾带空格）。
2. 实参与形参独立性：C++ 中普通参数传递属于值传递，形参拥有独立的栈空间，func 中的交换操作完全不影响 main 函数中的变量 c 和 d。
3. 返回后执行：回到 main 函数后，执行 cout << c << " " << d << endl;，输出原值 12 24。
4. 综合两次输出，最终屏幕显示为 24 12 12 24。选 B。

---

第 2 题

【题目内容】
下面函数不能正常执行的是（ ）

• 代码A：函数 func() 在 main() 之前定义并实现。
• 代码B：函数 func() 在 main() 之后定义，且在 main() 之前没有任何声明，在 main() 中直接调用 func()。
• 代码C：函数 func() 在 main() 之前完整定义，并在 main() 中调用 func()。
• 代码D：在 main() 之前进行前置声明 int func();，在 main() 中调用，在 main() 之后给出完整定义。

【答案】B
【考点】 C++ 编译顺序与函数前置声明（Function Declaration）
【讲师深度解析】
C++ 编译器按照从上往下的顺序对源码进行单遍语法与语义扫描。

• 在代码 B 中，func() 的定义写在 main() 函数之后，而在 main() 之前既没有函数实现，也没有给出函数原型声明（如 int func();）。
• 当编译器扫描到 main() 内部的 func() 调用时，符号表中找不到该函数的标识符，会产生编译报错（'func' was not declared in this scope），因此代码 B 无法编译执行。选 B。

---

第 3 题

【题目内容】
下面程序输出的是（ ）

#include<iostream>
using namespace std;
int func();
int main()
{
	int i = 2;
	cout << i << endl;
	for(int x = 0; x < 1; x++)
	{
		int i = 10;
		cout << i << endl;
	}
	i = i + 1;
	cout << i << endl;
	{
		i = i * i;
		cout << i << endl; 
	}
}

• A. 2 2 3 9
• B. 2 10 3 9
• C. 2 10 11 121
• D. 2 10 3 100

【答案】B
【考点】 块作用域（Block Scope）与局部变量隐藏（Variable Shadowing）
【讲师深度解析】
一步步追踪变量 i 的作用域与取值：

1. int i = 2; cout << i << endl;：最外层局部变量 i = 2，第 1 行输出 2。
2. 进入 for 循环块：在内部声明了新的局部变量 int i = 10;，内层同名变量暂时**隐藏（遮蔽）**了外层变量，输出 10。循环结束后，内层变量 i 销毁。
3. i = i + 1; cout << i << endl;：此时起作用的是外层的 i（其值依然是 2），执行自增后变为 3，输出 3。
4. 进入独立复合语句块 { i = i * i; cout << i << endl; }：注意该块内没有重新声明 int i，因此修改的就是外层的 i，i = 3 * 3 = 9，输出 9。
   输出序列依次为 2, 10, 3, 9。选 B。

---

第 4 题

【题目内容】
假设变量 a 的地址是 0x6ffe14，下面程序的输出是（ ）。

#include<iostream>
using namespace std;
int main()
{
	int *p;
	int a = 10;
	p = &a;
	p++;
	cout << p << endl;
}

• A. 10
• B. 0x6ffe14
• C. 0x6ffe15
• D. 0x6ffe18

【答案】D
【考点】 指针算术运算与指针步长（Pointer Step Size）
【讲师深度解析】

1. 指针类型步长：p 是指向整型 int 的指针（int*）。在现代操作系统和 C++ 标准环境下，sizeof(int) == 4 字节。
2. 指针自增 p++ 的本质：指针加 1 并不是在内存地址数值上简单加 1，而是向前移动一个基类型所占的内存长度，即：$$\text{新地址} = \text{原地址} + 1 \times sizeof(int) = \text{0x6ffe14} + 4 $$
3. 十六进制加法：0x14 + 0x4 = 0x18。因此输出的新地址为 0x6ffe18。选 D。

---

第 5 题

【题目内容】
如果下列程序输出的地址是 0x6ffe00 ，则 cout<<a+1<<endl; 输出的是（ ）

#include<iostream>
using namespace std;
int main()
{
	int a[2][3] = {0};
	cout << a << endl;
}

• A. 0x6ffe04
• B. 0x6ffe0C
• C. 0x6ffe08
• D. 0x6ffe00

【答案】B
【考点】 二维数组名退化机制与行指针偏移计算
【讲师深度解析】

1. 二维数组名退化的类型：二维数组 a[2][3] 的数组名 a 在表达式中退化为指向其首个元素（即第 0 行整个一维子数组 int[3]）的指针，其类型为行指针 int (*)[3]。
2. 行指针偏移步长：对行指针执行 +1 操作（a + 1），步长为整整一行的字节大小：$$\text{步长} = 3 \times sizeof(int) = 3 \times 4 = 12 \text{ 字节} $$
3. 十六进制地址换算：
   • 12 的十六进制表示为 0xC。
   • 基地址为 0x6ffe00。
   • a + 1 的地址为 0x6ffe00 + 0xC = 0x6ffe0C。选 B。

---

第 6 题

【题目内容】
C++中，关于文件路径说法错误的是（ ）

• A. "GESP.txt"：指定与当前工作目录中的程序文件相同目录中的 GESP.txt 文件
• B. "../data/GESP.txt"：指定与当前工作目录中的程序文件上一级目录下的 data 目录中的 GESP.txt 文件
• C. "./data/GESP.txt"：指定与当前工作目录中的程序文件同级目录下的 data 目录中的 GESP.txt 文件
• D. "GESP.txt"是绝对路径

【答案】D
【考点】 相对路径与绝对路径的概念辨析
【讲师深度解析】

• 绝对路径：从根目录（如 Windows 下的 C:\、D:\ 或 Linux 下的 /）开始书写的完整文件路径，独立于当前执行的工作目录。
• 相对路径：相对于当前程序运行的工作目录开始定位的文件路径。"GESP.txt"、"./data/GESP.txt"、"../data/GESP.txt" 均属于相对路径。
  因此选项 D 称 "GESP.txt" 是绝对路径是完全错误的。选 D。

---

第 7 题

【题目内容】
关于直接插入排序，下列说法错误的是（ ）

• A. 插入排序的最好情况是数组已经有序，此时只需要进行 $n-1$ 次比较，时间复杂度为 $O(n)$
• B. 最坏情况是数组逆序排序，此时需要进行 $\frac{n(n-1)}{2}$（原题写为 $n(n-1)$）次比较以及 $n-1$ 次赋值操作（插入）
• C. 平均来说插入排序算法的复杂度为 $O(n^2)$
• D. 空间复杂度上，直接插入法是就地排序，空间复杂度为 $O(n)$

【答案】D
【考点】 直接插入排序（Insertion Sort）的性能特征与空间复杂度分析
【讲师深度解析】

• 就地排序与额外空间：直接插入排序在排序过程中，只需要常数级别的临时变量（如存放待插入元素的 key 和下标变量 j），并不需要随着元素规模 $n$ 的增长而分配线性大小的额外辅助数组。
• 空间复杂度判定：就地排序（In-place Sort）的辅助空间复杂度为 $O(1)$，绝非 $O(n)$。因此 D 选项说法错误。选 D。

---

第 8 题

【题目内容】
下列程序横线处，应该输入的是 （ ）。

#include<iostream>
using namespace std;
int n, a[10001];
void swap(int &a, int &b)
{
	int t = a;
	a = b;
	b = t;
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = n; i > 1; i--)
		for(int j = 1; j < i; j++)
			if(a[j] > a[j + 1])
				___________________;
	for(int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}

• A. swap(a[j],a[j+1]);
• B. swap(a[j-1],a[j]);
• C. swap(a[j-1],a[j+1]);
• D. swap(&a[j-1],&a[j+1]);

【答案】A
【考点】 冒泡排序（Bubble Sort）基本逻辑与引用传参调用
【讲师深度解析】

1. 算法逻辑：代码实现的是经典的升序冒泡排序。内层循环比较相邻两个元素 a[j] 与 a[j + 1]。若前一个元素大于后一个元素（a[j] > a[j + 1]），则必须交换这两个相邻元素。
2. 函数签名匹配：题中 swap 函数形参为引用 (int &a, int &b)，在调用时直接传入需要交换的两个变量名即可，无需加取地址符。
   因此横线处应填写 swap(a[j], a[j + 1]);。选 A。

---

第 9 题

【题目内容】
下面关于递推的说法不正确的是（ ）。

• A. 递推表现为自己调用自己
• B. 递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的
• C. 递推中，问题的n要求是在计算中确定，不要求计算前就知道n
• D. 斐波那契数列可以用递推实现求解

【答案】A
【考点】 递推（Recurrence）与递归（Recursion）的本质辨析
【讲师深度解析】

• 递归：表现为函数内部直接或间接调用自身，通过自顶向下分解子问题再回溯求解。
• 递推：是一种自底向上根据递推关系式（如 $f[i] = f[i-1] + f[i-2]$）逐步向前计算出目标解的迭代方法，表现为循环迭代结构，绝对不是自己调用自己。
  因此选项 A 将“递归”的特征套用在“递推”上，说法错误。选 A。

---

第 10 题

【题目内容】
关于几种排序算法的说法，下面说法错误的是（ ）。

• A. 选择排序不是一个稳定的排序算法
• B. 冒泡排序算法不是一种稳定的排序算法
• C. 插入排序是一种稳定的排序算法
• D. 如果排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同，则称为一种稳定的排序算法

【答案】B
【考点】 排序算法的稳定性（Stability）概念与判定
【讲师深度解析】

1. 稳定性的定义：如选项 D 所述，如果待排序序列中有两个相等的元素，排序后它们的相对次序保持不变，则称该算法为稳定排序。
2. 算法稳定性分类：
   • 冒泡排序：只有当前者严格大于后者时才交换（>），两个相等的数不会跨越交换，因此冒泡排序是稳定的排序算法。
   • 直接插入排序：在向有序区插入时，遇到相等元素停在其后方插入，是稳定的。
   • 选择排序：由于从无序区选出最小值后与首位元素发生远距离跨越交换，会打乱相等元素的相对顺序，是不稳定的。
     因此选项 B 声称“冒泡排序不是一种稳定的排序算法”是错误的。选 B。

---

第 11 题

【题目内容】
数组 {45, 66, 23, 1, 10, 97, 52, 88, 5, 33} 进行从小到大冒泡排序过程中，第一遍冒泡过后的序列是（ ）。

• A. {45, 23, 1, 10, 66, 52, 88, 5, 33, 97}
• B. {45, 66, 1, 23, 10, 97, 52, 88, 5, 33}
• C. {45, 66, 23, 1, 10, 52, 88, 5, 33, 97}
• D. {45, 66, 23, 1, 10, 97, 52, 88, 33, 5}

【答案】A
【考点】 冒泡排序单趟模拟与全局最大值浮动过程
【讲师深度解析】
我们严格追踪第一趟相邻两两比较交换的过程：

• 初始序列：45, 66, 23, 1, 10, 97, 52, 88, 5, 33
• 比较 45 与 66：$45 < 66$，不交换 $\rightarrow [45, 66, 23, 1, 10, 97, 52, 88, 5, 33]$
• 比较 66 与 23：$66 > 23$，交换 $\rightarrow [45, 23, 66, 1, 10, 97, 52, 88, 5, 33]$
• 比较 66 与 1：$66 > 1$，交换 $\rightarrow [45, 23, 1, 66, 10, 97, 52, 88, 5, 33]$
• 比较 66 与 10：$66 > 10$，交换 $\rightarrow [45, 23, 1, 10, 66, 97, 52, 88, 5, 33]$
• 比较 66 与 97：$66 < 97$，不交换 $\rightarrow [45, 23, 1, 10, 66, 97, 52, 88, 5, 33]$
• 比较 97 与 52：$97 > 52$，交换 $\rightarrow [45, 23, 1, 10, 66, 52, 97, 88, 5, 33]$
• 比较 97 与 88：$97 > 88$，交换 $\rightarrow [45, 23, 1, 10, 66, 52, 88, 97, 5, 33]$
• 比较 97 与 5：$97 > 5$，交换 $\rightarrow [45, 23, 1, 10, 66, 52, 88, 5, 97, 33]$
• 比较 97 与 33：$97 > 33$，交换 $\rightarrow [45, 23, 1, 10, 66, 52, 88, 5, 33, 97]$
  最终第一趟将最大数 97 冒泡沉底至序列末端，前部变为 {45, 23, 1, 10, 66, 52, 88, 5, 33, 97}。选 A。

---

第 12 题

【题目内容】
下面的排序算法程序中，横线处应该填入的是（ ）。

int a[8]={ 2,3, 4, 5, 6,2,3,1};
for (int i=1;i<8;i++)
{
    int key = a[i];
    int j=i-1;
    while(a[j]>key && j>=0)
    {
        ________;
        j -= 1;
    }
    a[j + 1]= key;
}

• A. a[j]=a[j-1];
• B. a[j]=a[j+1];
• C. a[j+1]=a[j-1];
• D. a[j+1]=a[j];

【答案】D
【考点】 直接插入排序（Insertion Sort）的有序区元素后移操作
【讲师深度解析】
在插入排序中：

1. 当前待插入的值保存在 key = a[i] 中。
2. j 从 i-1 开始向前扫描有序序列。只要当前检查的元素 a[j] 比 key 大，就必须把该元素向后搬移一位，为 key 腾出空位。
3. 将下标 j 处的元素搬移到其后一位 j+1 处，赋值语句为：a[j + 1] = a[j];。选 D。

---

第 13 题

【题目内容】
下面的程序中，如果输入 10 0 ，会输出（ ）。

#include<iostream>
using namespace std;

double Division(int a, int b)
{
	if(b == 0)
		throw "Division by zero condition!";
	else
		return ((double)a / (double)b);
}

void func()
{
	int len, time;
	cin >> len >> time;
	cout << Division(len, time) << endl;
}

int main()
{
	try{
		func();
	}
	catch(const char* errmsg)
	{
		cout << errmsg << endl;
	}
	catch(const int errmsg)
	{
		cout << errmsg << endl;
	}
	return 0;
}

• A. Division by zero condition!
• B. 0
• C. 10
• D. 100

【答案】A
【考点】 C++ 异常处理机制（跨函数栈展开与类型匹配捕获）
【讲师深度解析】

1. 异常抛出：输入 len = 10, time = 0。进入 Division(10, 0)，由于 b == 0，执行 throw "Division by zero condition!";。抛出的对象是一个字符串字面量，其静态类型为 const char*。
2. 栈展开与捕获：函数 Division 中断并逐层回退调用栈，进入 main 函数的 catch 块匹配：
   • 第一个捕获块 catch(const char* errmsg) 的参数类型与抛出的异常类型严格精确匹配。
   • 程序执行该 catch 块，打印出 errmsg 的内容：Division by zero condition!。选 A。

---

第 14 题

【题目内容】
10条直线，最多可以把平面分为多少个区域（ ）。

• A. 55
• B. 56
• C. 54
• D. 58

【答案】B
【考点】 平面分割递推数学模型（蛋糕切分问题）
【讲师深度解析】

1. 递推模型建立：
   设 $f(n)$ 表示 $n$ 条直线最多能将平面分割成的区域数。
   • 当加入第 $n$ 条直线时，为了让新产生的区域最多，这条直线必须与前面已有的 $n-1$ 条直线都相交（两两不平行），且任意 3 条直线不交于同一点。
   • 这样第 $n$ 条直线会被已有的 $n-1$ 条直线分割成 $n$ 段线段/射线，每一段都将其穿过的原有区域一分为二，即增加 1 个新区域。
   • 得到经典递推方程：$$f(n) = f(n-1) + n$$
2. 通项公式与求和：
   • 边界初始状态：0 条直线时有 1 个平面，即 $f(0) = 1$。
   • 累加得通项公式：$$f(n) = 1 + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2} $$
3. 计算代入：
   当 $n = 10$ 时：$$f(10) = 1 + \frac{10 \times 11}{2} = 1 + 55 = 56$$ 因此 10 条直线最多可以把平面分为 56 个区域。选 B。

---

第 15 题

【题目内容】
下面程序中，如果语句 cout<<p<<endl; 输出的是 0x6ffe00 ，则 cout<<++p<<endl; 输出的是（ ）

int x[10][10][10]={{0}};
int *p;
p=&x[0][0][0];
cout<<p<<endl;
cout<<++p<<endl;

• A. 0x6ffe0c
• B. 0x6ffe09
• C. 0x6ffe06
• D. 0x6ffe04

【答案】D
【考点】 指针类型与基本寻址步长
【讲师深度解析】

1. 辨析指针维度与基类型：虽然数组 x 是三维数组，但指针 p 声明为普通的一级整型指针 int *p;。它赋值为指向首个整型元素 &x[0][0][0]。
2. 自增步长：因为 p 的基类型为 int，对 p 执行前缀自增 ++p，指针向后移动一个 int 的大小，即移动 sizeof(int) = 4 个字节。
3. 十六进制地址累加：
   • 原地址：0x6ffe00
   • 新地址：0x6ffe00 + 4 = 0x6ffe04。选 D。

---

二、判断题（每题 2 分，共 20 分）

第 16 题

【题目内容】
int& a 和 &a 是一样的，都是取 a 的地址。

【答案】错（错误）
【考点】 引用声明符 & 与取地址运算符 & 的语法与语义区别
【讲师深度解析】

• 在类型声明中：int& a 中的 & 是类型修饰符，表示声明一个整型变量的引用（别名）；
• 在执行表达式中：&a 中的 & 是单目取地址运算符，用于计算并获取变量 a 在内存中的首地址。
  两者的语法含义和运行期动作截然不同，说法错误。

---

第 17 题

【题目内容】
以下代码不能够正确执行。

#include<iostream>
using namespace std;
int main()
{
	int a = 20;
	int& ra;
	ra = &a;
	cout << ra << endl;
	return 0;
}

【答案】对（正确）
【考点】 引用（Reference）必须在定义时初始化的硬性语法规则
【讲师深度解析】
在 C++ 中，引用一旦创建就必须绑定到某个合法的左值对象上，因此：

1. int& ra; 没有提供初始化目标，编译器会直接报错：error: 'ra' declared as reference but not initialized。
2. 后续的 ra = &a; 更是类型错误（试图把地址 int* 赋给整型）。
   代码在编译阶段即无法通过，确实“不能够正确执行”。说法正确。

---

第 18 题

【题目内容】
引用是一个指针常量。

【答案】对（正确）
【考点】 引用在 C++ 编译器底层的实现本质
【讲师深度解析】

1. 底层实现剖析：在主流现代 C++ 编译器（如 GCC/Clang/MSVC）内部，引用的底层实现机制就是一个指针常量（Type * const）。
2. 指针常量特性：指针常量要求定义时必须初始化绑定地址，且初始化后不能再更改指向其他的内存单元（指针本身不可变），但可以通过解引用修改目标地址中的数据。这与 C++ 中引用的“必须初始化且不能重新绑定”的语法行为完全一致。在 GESP 官方教学考查标准中，认定该命题为正确。

---

第 19 题

【题目内容】
下面程序两个输出结果是一样的。

#include<iostream>
using namespace std;
int main()
{
	int a[2][3] = {0};
	cout << a << endl;
	cout << &a[0][0] << endl;
	return 0;
}

【答案】对（正确）
【考点】 二维数组在物理内存中的首地址一致性
【讲师深度解析】

1. 二维数组 a[2][3] 在内存中是连续分配的一整块空间。
2. a 退化为指向第 0 行整个数组的行指针，其保存的内存地址即为二维数组的物理起始地址；
3. &a[0][0] 是获取第 0 行第 0 个基本元素的物理内存地址。
   尽管它们的指针类型不同（前者类型为 int(*)[3]，后者类型为 int*），但在数值上，这两个地址指向同一块内存起始位置，输出打印出的十六进制地址完全相同。说法正确。

---

第 20 题

【题目内容】
函数不可以调用自己。

【答案】错（错误）
【考点】 函数递归调用（Recursion）基础概念
【讲师深度解析】
在 C++ 等图灵完备的高级程序设计语言中，函数不仅可以调用其他函数，完全可以直接或间接调用自身，这种程序设计范式被称为递归（Recursion）（如递归求斐波那契数列、汉诺塔、DFS 深度优先搜索等）。说法错误。

---

第 21 题

【题目内容】
函数参数传递过程中，如果传常量值、常量引用和常量指针都是不能被修改的，它们可以防止函数对实参的值或地址进行修改。

【答案】对（正确）
【考点】 const 限定符在参数传递中的保护机制
【讲师深度解析】

• 常量引用（const Type&）：形参作为实参的别名，但被 const 修饰，在函数内部禁止对其进行赋值操作，既避免了数据拷贝开销，又保护了实参内容不被篡改；
• 常量指针（const Type*）：指针指向的目标数据被 const 限定为只读，无法通过解引用去修改实参所指向的值；
• 常量值传递（const Type）：在函数局部限制了该形参变量本身只读。
  它们均起到了在函数调用中防范意外修改实参的保护屏障作用。说法正确。

---

第 22 题

【题目内容】
下面代码输出的值等于0。

#include<iostream>
using namespace std;
int main()
{
	int *p = NULL;
	cout << p << endl;
	return 0;
}

【答案】对（正确）
【考点】 空指针 NULL 的输出表现形式
【讲师深度解析】

1. 在 C++ 中，宏 NULL 被定义为整数常量 0（或 0L）。
2. 当把一个值为 NULL 的对象指针（如 int* p = NULL;）传入 std::cout 打印时，标准流将其视为空地址，并输出表示空指针的数值 0（或在部分早期环境中输出 0x0）。在 GESP 官方判卷规范中，该题输出确为 0，判断为正确。

---

第 23 题

【题目内容】
在下面这个程序里， a[i][j] 和一个普通的整型变量一样使用。

#include<iostream>
using namespace std;
int main()
{
	int a[10][10] = {0};
	for(int i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			if(i == j)
			{
				a[i][j] = 1;
			}
		}
	}
	return 0;
}

【答案】对（正确）
【考点】 二维数组元素的左值与变量语义
【讲师深度解析】
多维数组 a 中的每个具体带完整下标的单元 a[i][j]，在内存中都对应一块独立分配且连续的 int 大小物理空间。在语法和语义上，a[i][j] 是一个合法的可修改左值，可以像普通 int 变量一样参与赋值、加减运算、逻辑判断或函数传参。说法正确。

---

第 24 题

【题目内容】
一个一维数组，至少含有一个自然数N，是一个合法的数列。可以在一维数组末尾加入一个自然数M，M不能超过一维数组末尾元素的一半，形成一个新的合法的一维数组，如果N=6，那么可以有6个不同的合法数组。

【答案】对（正确）
【考点】 递归/递推构造合法数列（经典数论组合问题）
【讲师深度解析】
依题意规则：新元素 $M$ 必须满足 $1 \le M \le \lfloor \text{末尾元素} / 2 \rfloor$。
当起始自然数 $N = 6$ 时，初始数组为 {6}。我们进行分支树状穷举：

1. 长度为 1：
   • {6} （1 个）
2. 在 6 后面追加元素 $M \le 6 / 2 = 3$（$M$ 可取 1, 2, 3）：
   • 追加 1：{6, 1}（末尾 1 无法再追加，因为 $1/2 = 0 < 1$）
   • 追加 2：{6, 2}
   • 追加 3：{6, 3}
3. 在长度为 2 的数组末尾继续追加：
   • 从 {6, 2} 出发：可追加 $M \le 2 / 2 = 1$，得到 {6, 2, 1}
   • 从 {6, 3} 出发：可追加 $M \le 3 / 2 = 1$，得到 {6, 3, 1}
4. 统计所有合法数组：
   ① {6}
   ② {6, 1}
   ③ {6, 2}
   ④ {6, 3}
   ⑤ {6, 2, 1}
   ⑥ {6, 3, 1}
   总共有且仅有 6 个不同的合法数组。说法完全正确。

---

第 25 题

【题目内容】
插入排序算法中，平均时间复杂度是 $O(n^2)$ ，最坏的情况逆序情况下，达到最大时间复杂度。

【答案】对（正确）
【考点】 插入排序（Insertion Sort）的综合时间复杂度分析
【讲师深度解析】

• 最坏情况（逆序）：当待排序数据呈完全倒序排列时，第 $i$ 个元素插入时必须与前面所有的 $i-1$ 个元素逐一比较并后移，总比较和移动次数为 $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = O(n^2)$，达到最大时间复杂度；
• 平均情况：随机序列下，元素平均需要向前移动一半距离，总操作次数仍为 $\approx \frac{n^2}{4} = O(n^2)$，平均时间复杂度为 $O(n^2)$。说法完全正确。