再次确认8和23题答案

我们抛开任何网络题解，直接从算法底层和命题规范进行纯逻辑独立演算与核实：

---

一、第 8 题直接推演

【题目重现】

关于 埃氏筛 和 线性筛 的比较，下列说法错误的是( )。

• A. 埃氏筛可能会对同一个合数进行多次标记
• B. 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
• C. 线性筛保证每个合数只被其最小质因子筛到一次
• D. 对于常见范围( $10^7$ )，埃氏筛因实现简单，常数较小，其速度往往优于线性筛

【纯算法原理解析】

1. 核验选项 A 与 C（筛法的本质特征）：
   • 埃氏筛：遇到质数 $p$ 时把 $p$ 的所有倍数标记。对于像 $30 = 2 \times 3 \times 5$ 这样的合数，它在 $p=2, 3, 5$ 时会被重复标记 3 次。因此 A 正确。
   • 线性筛（欧拉筛）：核心是 if (i % p == 0) break;，它严格保证了每个合数只被它的最小质因子筛去一次。因此 C 正确。
2. 核验选项 B 与 D（运行效率与常数实际对比）：
   • 理论复杂度：埃氏筛是 $O(n \log \log n)$，线性筛是 $O(n)$。线性筛理论更优。
   • 实际耗时（以 $10^7$ 为例）：
     • 在 $n = 10^7$ 范围内，$\log \log (10^7) \approx \log(16.1) \approx 2.78$，埃氏筛的内层赋值操作次数大约是 $n \times 2.78 \approx 2.8 \times 10^7$ 次（包含大量对 cache 内存的重复写入）。
     • 欧拉线性筛总标记次数恰好是 $n$ 次，外加遍历质数表的开销。在现代 CPU 体系结构下，欧拉筛的实际运行耗时（无论是耗时还是指令数）在 $10^7$ 范围内普遍优于或明显快于未加位运算极其深度优化的普通埃氏筛。
     • 选项 D 称：“对于常见范围 ($10^7$)，埃氏筛……其速度往往优于线性筛”，这与算法事实不符（如果埃氏筛更快，各大算力竞赛就不会把欧拉筛作为 $10^7$ 规模的首选模板了）。
     • 另外，选项 B 与选项 D 在逻辑上是直接互斥的（B 说“线性筛往往优于埃氏筛”，D 说“埃氏筛往往优于线性筛”），单选题必然在二者中产生错误项。显然错在 D。

【最终结论】 第 8 题答案毫无悬念是：D。

---

二、第 23 题直接推演

【题目重现】

下面代码采用分治算法求解标准 3 柱汉诺塔问题，时间复杂度为 $O(2^n)$ 。

void move(vector<int>&src, vector<int>&tar){    
    int pan= src.back();    
    src.pop_back();    
    tar.push_back(pan); 
}

void dfs(int n, vector<int>&src, vector<int>&buf, vector<int>&tar){    
    if(n== 1){        
        move(src, tar);        
        return;    
    }
    dfs(n- 1, src, tar, buf);    
    move(src, tar);    
    dfs(n- 1, buf, src, tar); 
}

void solveHanota(vector<int>&A, vector<int>&B, vector<int>&C){    
    int n= A.size();    
    dfs(n, A, B, C); 
}

• 正确
• 错误

【纯算法原理解析】 我们把题干中的关键命题点拆成三个独立维度判定：

1. 维度一：是否求解标准 3 柱汉诺塔问题？
   • 起始柱 src，辅助柱 buf，目标柱 tar。
   • $n=1$ 时直接移盘；$n > 1$ 时将前 $n-1$ 个盘经由 tar 移到 buf，把第 $n$ 个盘从 src 移到 tar，再将 $n-1$ 个盘经由 src 从 buf 移到 tar。
   • 这正是标准 3 柱汉诺塔的唯一最优移动方案。
2. 维度二：是否属于分治算法（Divide and Conquer）？
   • 将规模为 $n$ 的大问题，**分解（Divide）**成两个规模为 $n-1$ 的同构子问题和一个规模为 1 的原子操作；
   • 递归**解决（Conquer）**各子问题；
   • **合并（Combine）**操作序列达成全局目标。
   • 在数据结构与算法学术界（如《算法导论》第 4 章、清华大学/北大教材中），汉诺塔是与斐波那契数列、归并排序并列的最经典分治递归教学模型。
3. 维度三：时间复杂度是否为 $O(2^n)$？
   • 设 $n$ 个盘子的递归调用次数和移动次数为 $T(n)$：$$T(1) = 1$$ $$T(n) = 2T(n-1) + 1$$
   • 递推求得：$$T(n) = 2^n - 1$$
   • 渐进时间复杂度为严格的 $O(2^n)$。

综上所述，算法类型（分治）、问题名称（标准3柱汉诺塔）、时间复杂度（$O(2^n)$）三处全部完全正确。

【最终结论】 第 23 题答案毫无悬念是：正确（对）。

---

验证确认汇总

• 第 8 题：确认选 D（D 说法错误）。
• 第 23 题：确认选 正确。

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

金牌讲师寄语：
GESP 5级是 CCF 编程能力等级认证的分水岭，其知识体系全面对接 CSP-J/S 核心算法与数据结构。
本卷聚焦考查：单链表结构与快慢指针/哑结点操作、初等数论（唯一分解定理、完全数、欧几里得辗转相除法、埃氏筛与线性筛）、分治算法（归并排序、快速排序及其稳定性与极端复杂度、最大子数组和）、贪心策略（区间排片调度）、二维矩阵二分搜索、汉诺塔递归模型与时间复杂度 等重磅考点。
本题解由 NOI 金牌教练团队全方位深度推演，带你吃透每个算法背后的数学原理与底层代码机理！

---

快速查对表

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

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

判断题（10 题，共 20 分）

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

---

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

第 1 题

【题目内容】
以下哪种情况使用链表比数组更合适?

• A. 数据量固定且读多写少
• B. 需要频繁在中间或开头插入、删除元素
• C. 需要高效随机访问元素
• D. 存储空间必须连续

【答案】B
【考点】 链表与数组的底层物理存储与操作复杂度对比
【讲师深度解析】

1. 数组（顺序表）：物理地址连续，支持 $O(1)$ 时间常数级的随机下标访问（arr[i]）；但若要在头部或中间插入、删除元素，必须搬移后续的大量元素，时间复杂度高达 $O(n)$。
2. 链表（链式存储）：通过指针显式链接各离散结点。在定位到目标前驱结点后，插入和删除操作只需修改常数个指针指向，时间复杂度为 $O(1)$，无需搬移数据。
   因此在“频繁在中间或开头插入、删除元素”的场景下，链表比数组更加合适。选 B。

---

第 2 题

【题目内容】
函数 removeElements 删除单链表中所有结点值等于 $val$ 的结点，并返回新的头结点，其中链表头结点为 $head$ ，则横线处填写( )。

//结点结构体 
struct Node{    
    int val;    
    Node* next;    
    Node(): val(0), next(nullptr){}    
    Node(int x): val(x), next(nullptr){}    
    Node(int x, Node*next): val(x), next(next){} 
};

Node* removeElements(Node* head, int val){    
    Node dummy(0, head);        //哑结点，统一处理头结点    
    Node* cur=&dummy;    
    while(cur->next){        
        if(cur->next->val== val){            
            _______________________        //在此填入代码
        }        
        else{            
            cur= cur->next;        
        }    
    }    
    return dummy.next; 
}

• A. Node* del = cur; cur = del->next; delete del;
• B. Node* del = cur->next; cur->next = del; delete del;
• C. Node* del = cur->next; cur->next = del->next; delete del;
• D. Node* del = cur->next; delete del; cur->next = del->next;

【答案】C
【考点】 单链表结点删除的标准指针操作与内存防泄漏机制
【讲师深度解析】

1. 删除逻辑：cur 是待删除结点的前驱结点，目标删除结点为 cur->next。
2. 三步走安全删除法：
   • 第 1 步：用临时指针暂存待删除结点的地址：Node* del = cur->next;。
   • 第 2 步：调整前驱结点的指针，越过 del 结点直接指向其后继结点：cur->next = del->next;。
   • 第 3 步：调用 delete del; 安全释放该结点的堆内存空间，杜绝内存泄漏（Memory Leak）。
3. 选项陷阱辨析：
   • 选项 D 先执行 delete del;，此时 del 占用的内存已被归还操作系统，再访问 del->next 属于典型的 Use-After-Free（悬垂指针野指针访问），会引发未定义行为崩溃。
     故必须先改指针再释放，选 C。

---

第 3 题

【题目内容】
函数 hasCycle 采用Floyd快慢指针法判断一个单链表中是否存在环，链表的头节点为 $head$ ，即用两个指针在链表上前进: $slow$ 每次走 1 步， $fast$ 每次走 2 步，若存在环， $fast$ 终会追上 $slow$ (相遇);若无环， $fast$ 会先到达 nullptr，则横线上应填写( )。

struct Node{    
    int val;    
    Node*next;    
    Node(int x): val(x), next(nullptr){} 
};

bool hasCycle(Node*head){    
    if(!head || !head->next)        
        return false;    
    Node* slow= head;    
    Node* fast= head->next;    
    while(fast&& fast->next){        
        if(slow== fast) return true;        
        _______________________        //在此填入代码    
    }    
    return false; 
}

• A. slow = slow->next; fast = fast->next->next;
• B. slow = fast->next; fast = slow->next->next;
• C. slow = slow->next; fast = slow->next->next;
• D. slow = fast->next; fast = fast->next->next;

【答案】A
【考点】 Floyd 判圈算法（龟兔赛跑算法 / 快慢双指针）
【讲师深度解析】
Floyd 快慢指针的核心操作是：

• 慢指针 slow 每次前进 1 个结点：slow = slow->next;
• 快指针 fast 每次前进 2 个结点：fast = fast->next->next;
  如果链表中包含环，快指针相对慢指针每轮靠近 1 个结点，必定在有限步内追上慢指针（相遇 slow == fast）；若无环，快指针必先触及链表末尾的 nullptr。选 A。

---

第 4 题

【题目内容】
函数 isPerfectNumber 判断一个正整数是否为完全数(该数是否即等于它的真因子之和)，则横线上应填写( )。一个正整数 $n$ 的真因子包括所有小于 $n$ 的正因子，如28的真因子为1， 2， 4， 7， 14。

bool isPerfectNumber(int n){    
    if(n<= 1) return false;    
    int sum= 1;    
    for(int i= 2;______; i++){        
        if(n% i== 0){            
            sum+= i;            
            if(i!= n/i) sum+= n/i;        
        }    
    }    
    return sum== n; 
}

• A. i <= n
• B. i*i <= n
• C. i <= n/2
• D. i < n

【答案】B
【考点】 因子成对性与 $O(\sqrt{n})$ 因子枚举优化
【讲师深度解析】

1. 因子的成对性：一个正整数 $n$ 的因数总是成对出现的（即若 $i$ 是 $n$ 的因子，则 $\frac{n}{i}$ 也必定是 $n$ 的因子）。
2. 循环界限分析：代码内部已有逻辑 sum += i; if(i != n/i) sum += n/i;，即每次枚举一个因数 $i$ 时，都会同时将对称的因数 $\frac{n}{i}$ 一并累加进总和。
3. 为了避免因子的重复累加，枚举只需进行到 $\sqrt{n}$ 为止，即循环终止条件应为 $i \le \sqrt{n}$，在整型下写作 i * i <= n。选 B。

---

第 5 题

【题目内容】
以下代码计算两个正整数的最大公约数(GCD)，横线上应填写( )。

int gcd0(int a, int b){    
    if(a< b){        
        swap(a, b);    
    }    
    while(b!= 0){        
        int temp= a% b;        
        a= b;        
        b= temp;    
    }    
    return______; 
}

• A. b
• B. a
• C. temp
• D. a * b

【答案】B
【考点】 欧几里得辗转相除法（Euclidean Algorithm）
【讲师深度解析】
辗转相除法根据定理 $\gcd(a, b) = \gcd(b, a \bmod b)$。
循环迭代中：

• 计算余数 temp = a % b；
• 将除数作为新的被除数：a = b；
• 将余数作为新的除数：b = temp。
  当 b == 0 时循环结束，此时上一轮最后的非零余数已经被转移存放在变量 a 中，因此最终的最大公约数就是 a。选 B。

---

第 6 题

【题目内容】
函数 sieve 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入( )。

vector<bool> sieve(int n){    
    vector<bool> is_prime(n+1, true);    
    is_prime[0]= is_prime[1]= false;    
    for(int i= 2; i<= n; i++){        
        if(is_prime[i]){            
            for(int j=______; j<= n; j+= i){                
                is_prime[j]= false;            
            }        
        }    
    }    
    return is_prime; 
}

• A. i
• B. i+1
• C. i*2
• D. i*i

【答案】D
【考点】 埃氏筛法（Sieve of Eratosthenes）的标准平方优化
【讲师深度解析】

1. 埃氏筛的核心原理：每发现一个质数 $i$，就将其所有的合数倍数标记为 false。
2. 平方起点优化：对于质数 $i$，形如 $k \times i$（其中 $k < i$）的合数，在前面外层循环枚举到 $k$ 的某个质因数时，早已经全部被提前标记过了。
3. 因此，由质数 $i$ 负责首次标记的最小合数是 $i \times i$。内层循环从 j = i * i 开始，可以避免大量的冗余遍历，这是标准埃氏筛的最佳实践。选 D。

---

第 7 题

【题目内容】
函数 linearSieve 实现线性筛法(欧拉筛)，横线处应填入( )。

vector<int> linearSieve(int n){    
    vector<bool> is_prime(n+1, true);    
    vector<int> primes;    
    for(int i= 2; i<= n; i++){        
        if(is_prime[i]) primes.push_back(i);        
        for(int p: primes){            
            if(p* i> n) break;            
            is_prime[p* i]= false;            
            if(________) break;        
        }    
    }    
    return primes; 
}

• A. i % p == 0
• B. p % i == 0
• C. i == p
• D. i * p == n

【答案】A
【考点】 欧拉线性筛法（Euler's Sieve）的核心剪枝条件
【讲师深度解析】

1. 欧拉筛的线性保证：线性筛之所以能达到严格的 $O(n)$ 时间复杂度，核心在于保证每个合数只被它的最小质因子筛去一次。
2. 条件推导：当 i % p == 0 时，说明当前质数 p 正好是 i 的最小质因子。如果继续让更大的质数 $p'$ 去筛 $p' \times i$，因为 $i$ 含有因数 $p$，所以数 $p' \times i$ 的最小质因子实际上是 $p$ 而不是 $p'$，这就违背了“只被最小质因子筛掉”的原则，会导致重复标记。
3. 因此，一旦遇到 i % p == 0，必须立即 break 退出内层循环。横线处应填 i % p == 0。选 A。

---

第 8 题

【题目内容】
关于 埃氏筛 和 线性筛 的比较，下列说法错误的是( )。

• A. 埃氏筛可能会对同一个合数进行多次标记
• B. 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
• C. 线性筛保证每个合数只被其最小质因子筛到一次
• D. 对于常见范围( $10^7$ )，埃氏筛因实现简单，常数较小，其速度往往优于线性筛

【答案】D
【考点】 筛法时间复杂度与常数特征综合对比
【讲师深度解析】

• 复杂度对比：埃氏筛的理论时间复杂度为 $O(n \log \log n)$，而线性筛为严格的 $O(n)$。
• 实际运行表现：对于 $10^7$ 这样的大数据规模，埃氏筛由于会对合数（特别是包含较多质因子的数，如 30, 60, 210 等）进行反复多次重复标记，其计算操作量明显增加；而线性筛因每个合数只访问一次，其执行速度在 $10^7$ 级别明显快于埃氏筛。选项 D 声称“埃氏筛的速度往往优于线性筛”是完全错误的。选 D。

---

第 9 题

【题目内容】
唯一分解定理描述的是( )。

• A. 每个整数都能表示为任意素数的乘积
• B. 每个大于 1 的整数能唯一分解为素数幂乘积(忽略顺序)
• C. 合数不能分解为素数乘积
• D. 素数只有两个因子:1 和自身

【答案】B
【考点】 算术基本定理（唯一分解定理 / Fundamental Theorem of Arithmetic）
【讲师深度解析】
唯一分解定理（算术基本定理）：任何一个大于 1 的正整数 $N$，都可以唯一地表示成素数乘积的形式：

$$N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

其中 $p_1 < p_2 < \dots < p_k$ 为素数，$a_i$ 为正整数。若不计质因数的排列顺序，该分解表示是唯一的。因此选项 B 是严谨准确的描述。选 B。

---

第 10 题

【题目内容】
给定一个 $n \times n$ 的矩阵 $matrix$ ，矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第 $k$ 小的元素，则两处横线上应分别填写( )。

//统计矩阵中<= x的元素个数：从左下角开始
int countLE(const vector<vector<int>>& matrix, int x){    
    int n=(int)matrix.size();    
    int i= n- 1, j= 0, cnt= 0;    
    while(i>= 0&& j< n){        
        if(matrix[i][j]<= x){            
            cnt+= i+ 1;            
            ++j;        
        }        
        else{            
            --i;        
        }    
    }    
    return cnt; 
}

int kthSmallest(vector<vector<int>>& matrix, int k){    
    int n=(int)matrix.size();    
    int lo= matrix[0][0];    
    int hi= matrix[n- 1][n- 1];
    while(lo< hi){        
        int mid= lo+(hi- lo)/ 2;        
        if(countLE(matrix, mid)>= k){
            ________________    //在此处填入代码
        } else{
            ________________    //在此处填入代码
        }    
    }    
    return lo; 
}

• A. hi = mid - 1; 和 lo = mid + 1;
• B. hi = mid; 和 lo = mid;
• C. hi = mid; 和 lo = mid + 1;
• D. hi = mid + 1; 和 lo = mid;

【答案】C
【考点】 二分答案（Binary Search on Answer）与单调搜索区间的开闭端点维护
【讲师深度解析】

1. 二分单调性：countLE(matrix, mid) 统计矩阵中 $\le mid$ 的元素个数，该函数随 $mid$ 递增具有单调不减性。
2. 分支判断：
   • 当 countLE(matrix, mid) >= k 时：说明矩阵中 $\le mid$ 的元素个数已经达到了 $k$ 个，因此第 $k$ 小的数可能就是 $mid$，也可能比 $mid$ 更小。所以搜索区间的上界应收缩为 hi = mid;（不能是 mid - 1，否则可能漏掉正解）。
   • 当 countLE(matrix, mid) < k 时：说明 $\le mid$ 的元素总数还不足 $k$ 个，目标值必定严格大于 $mid$。所以下界必须收缩为 lo = mid + 1;。
     两处依次填写 hi = mid; 和 lo = mid + 1;。选 C。

---

第 11 题

【题目内容】
下述C++代码实现了快速排序算法，下面说法错误的是( )。

int partition(vector<int>& arr, int low, int high){    
    int i= low, j= high;    
    int pivot= arr[low];                //以首元素为基准    
    while(i< j){
        while(i< j&& arr[j]>= pivot) j--;  //从右往左查找        
        while(i< j&& arr[i]<= pivot) i++;  //从左往右查找
        if(i< j) swap(arr[i], arr[j]);    
    }    
    swap(arr[i], arr[low]);                
    return i;                             
}

void quickSort(vector<int>& arr, int low, int high){    
    if(low>= high) return;    
    int p= partition(arr, low, high);    
    quickSort(arr, low, p- 1);    
    quickSort(arr, p+ 1, high); 
}

• A. 快速排序之所以叫"快速"，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。
• B. 在平均情况下，划分的递归层数为 $O(\log n)$ ，每层中的总循环数为 $O(n)$ ，总时间为 $O(n \log n)$ 。
• C. 在最差情况下，每轮划分操作都将长度为 $n$ 的数组划分为长度为 0 和 $n-1$ 的两个子数组，此时递归层数达到 $O(n)$ ，每层中的循环数为 $O(n)$ ，总时间为 $O(n^2)$ 。
• D. 划分函数 partition 中"从右往左查找"与"从左往右查找"的顺序可以交换。

【答案】D
【考点】 双指针快速排序基准归位机制与扫描顺序陷阱
【讲师深度解析】

1. 基准位置决定的扫描次序：代码中以最左端首元素为基准（pivot = arr[low]），最后需要执行 swap(arr[i], arr[low]); 将基准数交换到指针相遇位置 $i$。
2. 为何必须先从右向左查：
   • 先从右往左移动 $j$（查找 $< pivot$ 的元素），再从左往右移动 $i$（查找 $> pivot$ 的元素）。这样当 $i$ 与 $j$ 相遇时，相遇点所指的元素必定是小于等于 pivot 的（或者是刚与较小元素交换过的位置，或者是 $j$ 停在了一个较小数上），此时把 arr[i] 与 arr[low] 交换能够正确保证左半段全部 $\le pivot$。
   • 如果颠倒顺序（先从左往右查）：相遇时指针很可能停留在大于 pivot 的元素上，此时与 arr[low] 交换就会把一个较大的数换到了数组首位，导致划分彻底错误！
     因此两者的查找顺序绝不能随意交换。选项 D 说法错误。选 D。

---

第 12 题

【题目内容】
下述C++代码实现了归并排序算法，则横线上应填写( )。

void merge(vector<int>&nums, int left, int mid, int right){
    //左子数组区间为[left, mid],右子数组区间为[mid+1, right]    
    vector<int> tmp(right- left+ 1);    
    int i= left, j= mid+ 1, k= 0;    
    while(i<= mid&& j<= right){        
        if(nums[i]<= nums[j])            
            tmp[k++]= nums[i++];        
        else            
            tmp[k++]= nums[j++];    
    }    
    while(i<= mid){        
        tmp[k++]= nums[i++];    
    }
    while(________){    //在此处填入代码		
        tmp[k++]= nums[j++];    
    }    
    for(k= 0; k< tmp.size(); k++){        
        nums[left+ k]= tmp[k];    
    } 
}

• A. i < mid
• B. j < right
• C. i <= mid
• D. j <= right

【答案】D
【考点】 归并排序（Merge Sort）合并双指针剩余元素处理
【讲师深度解析】

1. 两路归并过程：待合并的两个有序子区间分别是左区间 $[left, mid]$（由指针 $i$ 遍历）和右区间 $[mid+1, right]$（由指针 $j$ 遍历）。
2. 剩余段清空：当第一阶段双指针比较循环结束后，某一侧区间可能尚有剩余元素：
   • 前一段 while(i <= mid) 处理左半段的剩余元素；
   • 后一段显然用来处理右半段的剩余元素，右区间的合法终点是 right，因此循环条件应为 j <= right。选 D。

---

第 13 题

【题目内容】
假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 $movies$ ，其中 movies[i] = [start_i， end_i] 表示第 $i$ 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为( )。

int maxMovies(vector<vector<int>>& movies){    
    if(movies.empty()) return 0;
    sort(movies.begin(), movies.end(),[](const vector<int>& a, const vector<int>& b){
        return______;//在此处填入代码
    });
    int count= 1;    
    int lastEnd= movies[0][1];
    for(int i= 1; i< movies.size(); i++){        
        if(movies[i][0]>= lastEnd){            
            count++;
            ______= movies[i][1];//在此处填入代码
        }    
    }
    return count; 
}

• A. a[0] < b[0] 和 lastEnd
• B. a[1] < b[1] 和 lastEnd
• C. a[0] < b[0] 和 movies[i][0]
• D. a[1] < b[1] 和 movies[i][0]

【答案】B
【考点】 贪心算法（Greedy Algorithm）之经典区间调度问题（Activity Selection Problem）
【讲师深度解析】

1. 贪心选择性质：为了能够容纳更多不冲突的电影，每一次我们都应该优先选择结束时间最早的那部电影，这样可以给后面的电影留下最多的空闲时间。
2. 排序准则：因此数组必须按照结束时间（即下标 1）升序排序：return a[1] < b[1];。
3. 状态更新：当检查到某部电影的开始时间不早于上一部选定电影的结束时间（movies[i][0] >= lastEnd）时，该电影入选，同时必须将当前占用的结束时间更新为该电影的结束时间，即 lastEnd = movies[i][1];。
   两空分别填写 a[1] < b[1] 和 lastEnd。选 B。

---

第 14 题

【题目内容】
给定一个整数数组 $nums$ ，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是( )。

int crossSum(vector<int>& nums, int left, int mid, int right){    
    int leftSum= INT_MIN, rightSum= INT_MIN;    
    int sum= 0;    
    for(int i= mid; i>= left; i--){        
        sum+= nums[i];        
        leftSum= max(leftSum, sum);    
    }    
    sum= 0;    
    for(int i= mid+ 1; i<= right; i++){        
        sum+= nums[i];        
        rightSum= max(rightSum, sum);    
    }    
    return leftSum+ rightSum; 
}

int helper(vector<int>& nums, int left, int right){    
    if(left== right)        
        return nums[left];    
    int mid= left+(right- left)/ 2;    
    int leftMax= helper(nums, left, mid);    
    int rightMax= helper(nums, mid+ 1, right);    
    int crossMax= crossSum(nums, left, mid, right);    
    return max({leftMax, rightMax, crossMax}); 
}

int maxSubArray(vector<int>& nums){    
    return helper(nums, 0, nums.size()- 1); 
}

• A. 上述代码采用分治算法实现
• B. 上述代码采用贪心算法
• C. 上述代码时间复杂度为 $O(n \log n)$
• D. 上述代码采用递归方式实现

【答案】B
【考点】 最大子段和（Maximum Subarray）的分治策略与复杂度递归方程
【讲师深度解析】

1. 算法策略：该算法将原数组从中间分成左右两半，分别递归求解左半段最大和 leftMax、右半段最大和 rightMax，并通过 crossSum 线性扫描求出横跨左右两半的最大和 crossMax，最后三者取最大值。这是教科书级别典型的分治算法（Divide and Conquer），通过递归实现。
2. 复杂度推导：递归关系式为 $T(n) = 2T(n/2) + O(n)$，根据主定理（Master Theorem），时间复杂度为 $O(n \log n)$。
3. 本算法完全没有采用贪心策略，因此选项 B 说法错误。选 B。

---

第 15 题

【题目内容】
给定一个由非负整数组成的数组 $digits$ ，表示一个非负整数的各位数字，其中最高位在数组首位，且 $digits$ 不含前导0(除非是0本身)。下面代码对该整数执行 +1 操作，并返回结果数组，则横线上应填写( )。

vector<int> plusOne(vector<int>& digits){    
    for(int i=(int)digits.size()- 1; i>= 0;--i){        
        if(digits[i]< 9){            
            digits[i]+= 1;            
            return digits;        
        }
        ________________    //在此处填入代码
    }    
    digits.insert(digits.begin(), 1);    
    return digits; 
}

• A. digits[i] = 0;
• B. digits[i] = 9;
• C. digits[i] = 1;
• D. digits[i] = 10;

【答案】A
【考点】 高精度加法与逢十进一模拟
【讲师深度解析】
从最低位（数组末尾）向前扫描：

• 如果当前位小于 9（digits[i] < 9），直接加 1 后便无需再向前进位，可以直接返回结果数组。
• 如果当前位等于 9，加 1 之后产生进位变为 10，则本位必须置为 0（digits[i] = 0;），继续向前一位循环处理进位。
• 如果整个循环执行完毕都没有返回（例如全为 9 的情况，如 999 变为 000），则需要在最高位最前面补上一个进位 1（digits.insert(digits.begin(), 1); 得到 1000）。
  因此横线处应填写 digits[i] = 0;。选 A。

---

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

第 16 题

【题目内容】
基于下面定义的函数，通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被9整除，则它的各位数字之和能被9整除。

bool isDivisibleBy9(int n){    
    return n% 9== 0; 
}

bool isDigitSumDivisibleBy9(int n){    
    int sum= 0;    
    string numStr= to_string(n);    
    for(char c: numStr){        
        sum+=(c-'0');    
    }    
    return sum% 9== 0; 
}

【答案】正确
【考点】 数论模算术性质（弃九法原理）
【讲师深度解析】
根据同余定理：因为 $10 \equiv 1 \pmod 9$，所以对于任意正整数 $N = a_k 10^k + \dots + a_1 10 + a_0$，都有：

$$N \equiv \sum_{i=0}^{k} a_i \pmod 9$$

即一个整数能否被 9 整除，与其各个数位数字之和能否被 9 整除是完全等价的充分必要条件。代码通过比较两个函数的布尔值返回值，能够正确完成该数论性质的验算。判断为正确。

---

第 17 题

【题目内容】
假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4，6) 函数返回2。

void findMusicalPattern(int rhythm1, int rhythm2){    
    int commonDivisor= gcd(rhythm1, rhythm2);    
    int patternLength=(rhythm1* rhythm2)/ commonDivisor;    
    return patternLength； 
}

【答案】错误
【考点】 最大公约数（GCD）与最小公倍数（LCM）的关系
【讲师深度解析】

1. 代码计算目标：commonDivisor 是两数的最大公约数 $\gcd(4, 6) = 2$。接着代码计算 patternLength = (4 * 6) / 2 = 24 / 2 = 12。
2. 根据公式 $\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$，该函数计算并返回的是两者的最小公倍数 12，而不是最大公约数 2。题目描述声称返回 2，结论错误。

---

第 18 题

【题目内容】
下面递归实现的斐波那契数列的时间复杂度为 $O(n)$ 。

void move(vector<int>&src, vector<int>&tar){    
    int pan= src.back();    
    src.pop_back();    
    tar.push_back(pan); 
}

void dfs(int n, vector<int>&src, vector<int>&buf, vector<int>&tar){    
    if(n== 1){        
        move(src, tar);        
        return;    
    }
    dfs(n- 1, src, tar, buf);    
    move(src, tar);    
    dfs(n- 1, buf, src, tar); 
}

void solveHanota(vector<int>&A, vector<int>&B, vector<int>&C){    
    int n= A.size();    
    dfs(n, A, B, C); 
}

【答案】错误
【考点】 汉诺塔（Tower of Hanoi）递归递归树与指数级复杂度分析
【讲师深度解析】

1. 题面混淆辨析：题目描述文字声称是“递归实现的斐波那契数列”，但给出的代码分明是**汉诺塔问题（Tower of Hanoi）**的标准分治递归求解。
2. 时间复杂度分析：递归方程为 $T(n) = 2T(n-1) + O(1)$，展开可知总操作步数为 $2^n - 1$，其时间复杂度是标准的指数级 $O(2^n)$，绝非线性 $O(n)$。无论从题意还是复杂度判定，该说法均完全错误。

---

第 19 题

【题目内容】
链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。

【答案】正确
【考点】 链表存储结构优缺点与 CPU 缓存行（Cache Line）局部性原理
【讲师深度解析】

• 优势：插入删除无需搬移内存，修改指针即可完成，时间复杂度 $O(1)$；
• 劣势：
  1. 不支持随机寻址，访问第 $k$ 个元素需要 $O(k)$ 顺序遍历；
  2. 每个结点除了数据域外还需额外存储指针域，存在内存开销；
  3. 结点的物理内存地址离散分布，严重破坏了空间局部性（Spatial Locality），导致 CPU 缓存命中率极低（Cache Miss 严重）。
     该总结全面而准确，判断为正确。

---

第 20 题

【题目内容】
二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。

【答案】正确
【考点】 二分查找算法的核心前提与物理结构依赖
【讲师深度解析】

1. 有序性前提：二分查找依赖中间元素与目标值的大小比较来舍弃半边区间，无序数据无法二分。
2. 结构依赖：二分查找必须能够在 $O(1)$ 时间内快速跳转访问到区间的正中元素（arr[mid]）。如果是普通的非数组链表，定位 mid 需要 $O(n)$ 线性遍历，使得二分查找彻底退化失效。因此其只能应用于支持随机寻址的数组（或类数组结构）。判断为正确。

---

第 21 题

【题目内容】
线性筛关键是"每个合数只会被最小质因子筛到一次"，因此为 $O(n)$ 。

【答案】正确
【考点】 欧拉线性筛法（Euler Sieve）的时间复杂度本质
【讲师深度解析】
普通埃氏筛会有重复筛除（例如 30 被 2、3、5 都标记过一次）。欧拉筛通过 if (i % p == 0) break; 强制使得每个合数只在枚举到其唯一的最小质因子时才被标记并筛除，整个筛法中每个合数被访问标记的次数严格为 1 次，外层和内层的总循环步数与范围 $n$ 呈严格线性关系，故时间复杂度为完美的 $O(n)$。判断为正确。

---

第 22 题

【题目内容】
快速排序和归并排序都是稳定的排序算法。

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

• 归并排序（Merge Sort）：在合并两段有序数组时，只要设定 nums[i] <= nums[j] 时优先取左边的元素，就能保证相等元素的相对顺序不变，属于稳定的排序算法；
• 快速排序（Quick Sort）：基准数在与左右指针相遇点进行远距离交换时，非常容易跨越相同的元素，打乱原有相同元素的相对顺序，属于不稳定的排序算法。
  故“快速排序也是稳定排序”说法错误。

---

第 23 题

【题目内容】
下面代码采用分治算法求解标准 3 柱汉诺塔问题，时间复杂度为 $O(2^n)$ 。

void move(vector<int>&src, vector<int>&tar){    
    int pan= src.back();    
    src.pop_back();    
    tar.push_back(pan); 
}

void dfs(int n, vector<int>&src, vector<int>&buf, vector<int>&tar){    
    if(n== 1){        
        move(src, tar);        
        return;    
    }
    dfs(n- 1, src, tar, buf);    
    move(src, tar);    
    dfs(n- 1, buf, src, tar); 
}

void solveHanota(vector<int>&A, vector<int>&B, vector<int>&C){    
    int n= A.size();    
    dfs(n, A, B, C); 
}

【答案】正确
【考点】 汉诺塔问题的分治思想与指数复杂度判定
【讲师深度解析】
汉诺塔求解分为三步经典分治：

1. 将前 $n-1$ 个盘子借助目标柱转移到辅助柱：dfs(n-1, src, tar, buf);
2. 将底部的第 $n$ 个盘子直接移到目标柱：move(src, tar);
3. 将辅助柱上的 $n-1$ 个盘子借助起始柱转移到目标柱：dfs(n-1, buf, src, tar);
   递归式为 $T(n) = 2T(n-1) + 1$，总移动次数为 $2^n - 1$，渐近时间复杂度为 $O(2^n)$。判断为正确。

---

第 24 题

【题目内容】
所有递归算法都可以转换为迭代算法。

【答案】正确
【考点】 计算理论与显式栈模拟递归
【讲师深度解析】
在图灵可计算性理论与程序设计语言原理中：

1. 函数递归调用在操作系统底层本质上依赖于**系统调用栈（Call Stack）**保存现场、局部变量与返回地址。
2. 任何递归程序都可以通过显式引入一个自定义的栈（std::stack）数据结构，配合循环语句模拟入栈、出栈与状态跳转，改写为功能完全等价的非递归（迭代）算法。
   因此在计算机科学中，该命题为经典真命题。判断为正确。

---

第 25 题

【题目内容】
贪心算法总能得到全局最优解。

【答案】错误
【考点】 贪心算法的最优子结构与贪心选择性质适用局限性
【讲师深度解析】
贪心算法在每一步决策时，都采取在当前状态下最好或最优的选择（局部最优）。但由于它缺乏全局回溯和动态权衡机制，只有当问题满足“最优子结构”和“贪心选择性质”时，局部最优才能推导至全局最优（如哈夫曼编码、最小生成树 Kruskal 算法）。对于许多常见问题（如 0-1 背包问题、任意面额找零钱问题），贪心算法往往只能得到局部次优解甚至完全错误的解，必须使用动态规划或搜索求解。因此“总能得到全局最优解”说法错误。