NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 25 题

#include<iostream>
using namespace std;
int main()
{
    const int SIZE=100;
    int na,nb,a[SIZE],b[SIZE],i,j,k;
    cin>>na;
    for(i=1;i<=na;i++)
        cin>>a[i];
    cin>>nb;
    for(i=1;i<=nb;i++)
        cin>>b[i];
    i=1;
    j=1;
    while( (i<=na)&&(j<=nb) )
    {
        if(a[i]<=b[j])
        {
            cout<<a[i]<<' ';
            i++;
        }
        else
        {
            cout<<b[j]<<' ';
            j++;
        }
    }
    if(i<=na)
       for(k=i;k<=na;k++)
           cout<<a[k]<<' ';
    if(j<=nb)
       for(k=j;k<=nb;k++)
           cout<<b[k]<<' ';
    return 0;
}

输入： 5 1 3 5 7 9 4 2 6 10 14 输出：_______________

这题考归并排序的合并步骤。拿到题先别急着看代码细节，心里过一遍：两个有序序列怎么合并？比较头元素，小的先输出，指针后移。循环结束谁还有剩余，就全倒出来。按这个思路把代码里的变量对应到具体数字，一步步推演就能得出答案。

最容易栽跟头的地方是循环结束后的剩余处理。很多学生只盯着while里的比较，觉得循环一跑完就结束了，忘了i和j可能一个先跑完，另一个后面还有一截没输出。这题命题人特意在while后面加了两个if块，就是专门挖这个坑。如果漏看了这两个if，或者误以为循环里已经处理了所有元素，最后输出的序列就会缺掉10和14，变成1 2 3 5 6 7 9，这就直接错了。还有种情况是数组下标搞混，题目里数组是从1开始存的，但有些同学习惯0开始，算步骤时容易数错位。

程序阅读——归并两个有序数组

这道题考查的是归并排序中最核心的"合并"（Merge）操作。命题人没有直接给算法描述，而是把一段标准的合并代码放在这里，让你通过阅读程序来模拟执行过程。这种题型在NOIP初赛和GESP高级别考试中非常典型，目的是检验你对算法逻辑的掌控力，而不仅仅是死记硬背代码。既然题目给出了输入数据，我们的任务就是像计算机一样，一行一行、一个数一个数地跑完这段代码。

首先，程序定义了两个数组a和b，大小都是100，但实际只用了前na和nb个元素。输入部分很清楚：先读入na=5，接着读入5个数1, 3, 5, 7, 9存入a[1]到a[5]；再读入nb=4，接着读入4个数2, 6, 10, 14存入b[1]到b[4]。此时，a和b都是升序排列的，这正是归并算法的前提。

接下来是核心逻辑。变量i和j分别指向a和b的当前元素（初始都是1）。while循环的条件是(i<=na)&&(j<=nb)，意思是只要两个数组都还有元素没处理，就继续比较。循环体内有两个分支： 1. 如果a[i]<=b[j]，说明a的当前元素更小或相等，就输出a[i]，然后i++，指向a的下一个元素。 2. 否则（即a[i]>b[j]），说明b的当前元素更小，就输出b[j]，然后j++，指向b的下一个元素。

这个逻辑非常直观：每次从两个有序序列的头部挑出最小的那个，放进输出流，然后那个序列的指针往后挪一位。这其实就是归并排序合并阶段的"比较-输出-移动"三步走。

现在我们来手动模拟这个过程，把每一步的i、j值和输出结果列出来，这样能看得很清楚，也能避免出错。

• 初始状态：i=1, j=1。a[1]=1, b[1]=2。

1<=2成立，输出1，i变为2。

• 当前：i=2, j=1。a[2]=3, b[1]=2。

3<=2不成立，进入else，输出2，j变为2。

• 当前：i=2, j=2。a[2]=3, b[2]=6。

3<=6成立，输出3，i变为3。

• 当前：i=3, j=2。a[3]=5, b[2]=6。

5<=6成立，输出5，i变为4。

• 当前：i=4, j=2。a[4]=7, b[2]=6。

7<=6不成立，输出6，j变为3。

• 当前：i=4, j=3。a[4]=7, b[3]=10。

7<=10成立，输出7，i变为5。

• 当前：i=5, j=3。a[5]=9, b[3]=10。

9<=10成立，输出9，i变为6。

到这里，i已经变成了6，而na是5，所以i<=na不再成立，while循环结束。

注意：很多同学在这里就会停手，认为程序结束了。但千万别急！代码紧接着还有两个if块，专门处理循环结束后可能剩下的元素。

第一个if：if(i<=na)。现在i=6，na=5，条件不成立，所以a数组剩下的部分（其实已经空了）不用输出。

第二个if：if(j<=nb)。现在j=3，nb=4，条件成立！这意味着b数组从第3个元素开始还有没输出的数。程序会执行一个for循环：for(k=j;k<=nb;k++) cout<<b[k]<<' '; 也就是从k=3到k=4，依次输出b[3]和b[4]。 b[3]=10，输出10； b[4]=14，输出14。

至此，整个程序的输出流就完整了。

把刚才while循环里输出的和最后if里输出的拼起来，就是： 1 2 3 5 6 7 9 10 14

这就是正确答案。

命题视角与避坑指南

这道题的命题意图很明显：它想考的不是你会不会写归并排序，而是你能不能读懂一段代码并正确模拟执行。命题人特意在while循环后加了那两个if语句，就是为了挖"剩余元素处理"这个坑。很多学生看到while循环结束，就以为任务完成了，忽略了后面可能还有输出，导致答案少了10和14，直接错选或漏填。这就是典型的"会算法但没读全代码"。

另外，数组下标从1开始也是个细节。如果不小心当成0开始，模拟时i和j的初值、循环边界都会乱套，很容易数错步骤。所以做题时一定要看清题目给的代码，确认数组定义和输入循环的下标范围。

考频与趋势分析

归并排序是信息学竞赛中的高频考点。根据题库统计，近十年共考过51题，覆盖从GESP五级到NOIP提高组初赛等6个级别。具体分布看：2009年2题，2010年1题，2019年2题，2022年1题，2023年6题，2024年14题，2025年15题，2026年9题，还有1题年份未标注。从分赛事看，GESP五级考了33题，八级8题，七级4题，CSP提高级3题，NOIP提高组初赛2题，普及组初赛1题。这说明归并排序在GESP五级中占比极高，是基础中的基础；而在NOIP提高组初赛中也稳定出现。

从数据趋势看，2023年以来考题数量显著上升（2023年6题，2024年14题，2025年15题），尤其是2025年和2026年分别考了15题和9题，显示出命题人近期对归并排序相关内容的重视程度在持续加强。这可能意味着未来几年，归并排序的变体（如三路归并、归并排序的递归实现、或者结合其他排序算法的综合题）出现的概率会更高。

预测

基于上述数据，可以合理预测：未来几年（特别是2027-2029年），归并排序依然是NOIP提高组初赛和GESP五级、八级的必考或常考内容。命题人可能会在现有"合并两个有序数组"的基础上，增加一些干扰项，比如数组元素本身无序需要预处理，或者要求在合并过程中统计逆序对数量，又或者把合并过程嵌入到一个更大的排序框架中考察。但无论如何，"读懂代码并正确模拟"这一核心能力不会变。

暂无足够依据预测具体年份的考题形式，但可以确定的是，只要掌握了归并排序的合并逻辑，并能细心地模拟每一步，这类题就能稳稳拿下。