第一题（NOIP2013序列重排）

全局数组变量定义如下：

const int SIZE = 100;
int a[SIZE], n;

功能：将序列 a 的前 p 个数与后 n-p 个数对调，不改变内部相对顺序。例如序列 1,2,3,4,5，p=2 时重排为 3,4,5,1,2。

有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)，空间复杂度为O(n)：

void swap1(int p){
    int i,j,b[SIZE];
    for (i=1;i<=p;i++)
    b[  ①  ]=a[i];
    for (i=p+1;i<=n;i++)
    b[i-p]=  ②  ;
    for (i=1;i<=  ③  ;i++)
    a[i]=b[i];
}

我们也可以用时间换空间，使用时间复杂度为O(n²)，空间复杂度为O(1)的算法：

void swap2(int p){
    int i,j,temp;
    for (i=p+1;i<=n;i++) {
    temp=a[i];
    for (j=i;j>=  ④  ;j--)
    a[j]=a[j-1];
    ⑤  =temp;
    }
}

●选择题
(1)①处应填（ ）。
{{ select(1) }}

• p+i
• n-p+i
• n-p+i-1
• i

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

• a[i]
• a[i-p]
• a[n-i]
• b[i]

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

• n
• p
• p+1
• n-1

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

• 1
• i-p
• n-i
• i-p+1

(5)⑤处应填（ ）。
{{ select(5) }}

• a[i-p+1]
• a[i]
• a[i-p]
• a[i-1]