阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第10节：数论

第12题【NOIP】2018

#include <iostream>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
    for (int i = 1; i <= n; ++i)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}
bool getPermutation(int pos) {
    if (pos > n) {
        return isSmall();
    }
    for (int i = 1; i <= n; ++i) {
        if (!isUse[i]) {
            b[pos] = i; isUse[i] = true;
            if (getPermutation(pos + 1)) {
                return true;
            }
            isUse[i] = false;
        }
    }
    return false;
}
void getNext() {
    for (int i = 1; i <= n; ++i) {
        isUse[i] = false;
    }
    getPermutation(1);
32  for (int i = 1; i <= n; ++i) {
33       a[i] = b[i];
34  }
}
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= t; ++i) {
        getNext();
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d", a[i]);
46      if (i == n) putchar('\n'); else putchar(' ');
    }
    return 0;
}

●判断题

1)若t=0,则输入的排列与输出的排列相同。

{{ select(12-1) }}

• 正确
• 错误

(2)此程序的功能是求出给定的排列的上t个排列。

{{ select(12-2) }}

• 正确
• 错误

(3)若将46行去掉，则输出效果不变。

{{ select(12-3) }}

• 正确
• 错误

(4)将32～34行去掉，则输出效果不变。

{{ select(12-4) }}

• 正确
• 错误

●选择题

(5)该程序的时间复杂度为()。

{{ select(12-5) }}

• O(nlogt)
• O(nt)
• O($nt^2$)
• O($n^{2t}$

(6)若输入3 1 1 2 3,则输出()。

{{ select(12-6) }}

• 1 2 3
• 1 3 2
• 2 1 3
• 3 2 1