三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）全排列检查

给定长度为 $n$ 的数组 $a$，判断其是否构成全排列。如果 $1,2,\ldots,n$ 都恰好在数组 $a$ 中出现且仅出现一次，那么就称这个数组是一个全排列。试补全程序。

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

bool is_permutation(vector<int> &a)
{
    int n =     ① ; // 第一问
    vector<int> count(    ② ); // 第二问
    for (int i = 0; i < n; i++)
    {
        if (    ③ ) // 第三问
            count[a[i]]++;
        else
            ④ ; // 第四问
    }
    for (int i = 1; i <= n; i++)
        if (count[    ⑤ ] > 1) // 第五问
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (is_permutation(a))
        cout << "The sequence is a permutation.";
    else
        cout << "The sequence is not a permutation.";
    return 0;
}

选择题

33. ① 处应填（ ）。

{{ select(33) }}

• a.length()
• a.size()
• a.back()
• a.capacity()

34. ② 处应填（ ）。

{{ select(34) }}

• 0
• n
• n + 1
• 1000000000

35. ③ 处应填（ ）。

{{ select(35) }}

• 1 <= a[i] && a[i] <= n
• 1 <= a[i] <= n
• 1 <= a[i] || a[i] <= n
• a[i] < 1 || a[i] > n

36. ④ 处应填（ ）。

{{ select(36) }}

• break
• continue
• return true
• return false

37. ⑤ 处应填（ ）。

{{ select(37) }}

• i
• a[i]
• i – 1
• i / 2

（2）跳跃

给定一个数组 $a[0],a[1],\ldots,a[n-1]$，每次跳跃从当前位置 $x$ 跳至位置 $a[x]$。回答 $q$ 次询问，每次给出 $(x,k)$，输出从 $x$ 跳跃 $k$ 次后的位置编号。试补全程序。

#include <iostream>
using namespace std;

const int N = 100010, LOG = 20;
int a[N], dp[N][LOG];

int main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        dp[i][0] =     ① ; // 第一问
    }
    for (int k = 1; k < LOG; k++)
    {
        for (int i = 0; i < n; i++)
        {
            dp[i][k] =     ② ; // 第二问
        }
    }

    while (q--)
    {
        int x, k;
        cin >> x >> k;
        int u = x;
        for (int j = 0; j < LOG; j++)
        {
            if (    ③ )  // 第三问
            {
                u =     ④ ;  // 第四问
            }
        }
        cout <<     ⑤ << endl;  // 第五问
    }
    return 0;
}

选择题

38. ① 处应填（ ）。

{{ select(38) }}

• i
• a[i]
• 0
• dp[i][1]

39. ② 处应填（ ）。

{{ select(39) }}

• dp[dp[i][k - 1]][k - 1]
• dp[i][k - 1] + dp[i][k - 1]
• dp[i - 1][k - 1]
• dp[k - 1][i]

40. ③ 处应填（ ）。

{{ select(40) }}

• k & j
• k >> j
• (k >> j) & 1
• (k >> j) ^ 1

41. ④ 处应填（ ）。

{{ select(41) }}

• dp[j][u]
• dp[k][u]
• dp[u][j]
• a[u]

42. ⑤ 处应填（ ）。

{{ select(42) }}

• u
• x
• k
• dp[u][0]