共48道题，当前是第10题

初赛真题

01 #include<cstdio>
02 int n, r, num[10000];
03 bool mark[10000];
04 void print() {
05     for (int i = 1; i <= r; i++)
06         printf("%d ", num[i]);
07     printf("\n");
08 }
09 void search(int x) {
10     for (int i = 1; i <= n; i++)
11         if (!mark[i]) {
12             num[x] = i;
13             mark[i] = true;
14             if (x == r) print();
15             search(x + 1);
16             mark[i] = false;
17         }
18 }
19 int main() {
20     scanf("%d%d", & n, & r);
21     search(1);
22     return 0;
23 }

1. A。
2. A。
3. B。
4. B。
5. B。
6. D。

这段代码是在计算从 $1 \dots n$中挑选出 $r$ 个数字，能够组成多少不同的数列。通过公式我们可以得知一共有 $C^r_n * r!$ 种不同的数列。代码当中采用的是暴力搜索的方式，搜索出了每一种可能并且输出，复杂度为 $O(n2^n)$ 。通过 $mark[i]$ 来标记某一个数字是否被选，来进行枚举和输出。

Question

1. 若 n < r ，则程序无输出。（ ）

2. 程序结束时，对任意 $1 \leq i \leq n$ ， mark[i] == 0

3. 此程序的时间复杂度为 $O(n)$

4. 若输入为 4 3 ，则输出中数字 1 和 2 的个数不同。（ ）

5. 若输入为 6 3 ，则函数 print 的执行次数为（ ）

6. 若输入为 7 4 ，则输出的最后一行为（ ）