共48道题，当前是第22题

初赛真题

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int Maxn = 10005;
05 int n, b[Maxn];
06 
07 inline void mergesort(int * a, int l, int r) {
08     if (l == r) return;
09     int mid = l + r >> 1;
10     mergesort(a, 1, mid), mergesort(a, mid + 1, r);
11     int i = l, j = mid + 1, cnt = 0;
12     while (i <= mid && j <= r) {
13         if (a[i] <= a[j]) b[++cnt] = a[i++];
14         else b[++cnt] = a[j++];
15     }
16     while (i <= mid) b[++cnt] = a[i++];
17     while (j <= r) b[++cnt] = a[j++];
18     for (i = l; i <= r; i++) a[i] = b[i - l + 1];
19 }
20 
21 int a[Maxn];
22 
23 int main(void) {
24     cin >> n;
25     for (int i = 1; i <= n; i++) cin >> a[i];
26     mergesort(a, 1, n);
27     for (int i = 1; i <= n; i++) cout << a[i] << (i == n ? '\n' : ' ');
28     return 0;
29 }

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

这段代码是对输⼊数据的排序算法，使⽤了归并排序。归并排序的算法时间复杂度很稳定，为 $O(nlogn)$。这段代码中使⽤的输出格式可以保证最后⼀个数字后⾯没有空格并且输出换⾏。要注意的是 '\n' 是转义字符换⾏符，是不会显示出 \n 的。

Question

1. 该算法中 int *a 没有传值

2. 该代码的输出结果会换行

3. 该算法中 mergesort 函数时间复杂度为 $O(nlogn)$

4. 如果输⼊为 5 4 3 9 7 8 则输出为 3 4 7 8 9 \n

5. 该算法的最劣复杂度与哪个排序算法相同( )

6. 下⾯哪句与 i==n?'\n':' ' 相同( )