1. 16人参加1v1单打比赛，决出冠军。比赛采用双败淘汰制：第1轮随机配对，胜者进入胜者组，败者进入败者组。以后每轮在两组内分别配对进行（除非该组只剩1人），如在胜者组战败，则降入败者组；在败者组战败则淘汰，在败者组获胜留在败者组（不会升入胜者组）。如此反复进行直到两组都只剩1人，再进行最后一场决赛决出冠军。那么总共要进行（）场比赛。 {{ select(1) }}

• 15
• 30
• 31
• 120

---

2. 5个人穿5种颜色的衣服坐在5种颜色的椅子上，每人一把椅子。要求每个人的衣服颜色和椅子颜色都不相同。两种坐法不同当且仅当至少有1个人坐的椅子不同，则总共有（）种可能的坐法。 {{ select(2) }}

• 5
• 32
• 44
• 120

---

3. 正整数 $x$ 和 $y$ 的最大公约数 $\gcd(x,y)$ 定义为能同时整除 $x$ 和 $y$ 的最大正整数。例如，$\gcd(12,18)=6$。那么 $\gcd(12345,54321)=()$。 {{ select(3) }}

• 3
• 5
• 7
• 15

---

4. 1至100的整数的乘积末尾有（）个连续的0。 {{ select(4) }}

• 100
• 50
• 24
• 12

---

5. 在三维直角坐标系里任取 $n$ 个整点（坐标都是整数的点），要保证其中一定存在两个点连线的中点也是整点，$n$ 至少是（）。 {{ select(5) }}

• 2
• 3
• 7
• 9

---

6. 同时掷出3枚完全相同的六面骰子，每枚骰子上有1到6的数字。将得到的点数排序后，有（）种不同的结果。 {{ select(6) }}

• 208
• 56
• 216
• 120

---

7. 5个有标号的点在没有重边或者自环的情况下，可组成的不同无向图个数为（）。 {{ select(7) }}

• 10
• 1024
• 15
• 120

---

8. 若某算法的计算时间表示为递推关系式 $T(n)=9T(n/3)+n$，且 $T(1)=1$，则该算法的时间复杂度是（）。 {{ select(8) }}

• $O(n)$
• $O(2^n)$
• $O(n^2)$
• $O(n\log n)$

---

9. 8位二进制补码中，10101011表示的数是十分进制下的（）。 {{ select(9) }}

• 43
• -43
• -85
• -84

---

10. 下列算法中，完全不涉及贪心思想的算法为（）。 {{ select(10) }}

• Kruskal 算法（最小生成树）
• Floyd 算法（多源最短路）
• Dijkstra 算法（单源最短路）
• Kahn 算法（拓扑排序）

---

11. 已知 $a=3$，$b=5$，执行 $a \sim= b \sim= a \sim= b$ 后，$a$ 的值为（ ）。 {{ select(11) }}

• 3
• 5
• 6
• 0

---

12. 已知一个栈的入栈顺序为 $1,2,\dots,n(n\geqslant3)$，第1个出栈的是3，那么第2个出栈的数有（）种可能。 {{ select(12) }}

• $n-1$
• $n-2$
• $n-3$
• $n-4$

---

13. 一个 $n$ 节点无向图没有重边和自环，它是一棵无根树的必要条件不包括（）。 {{ select(13) }}

• 连通
• 有 $n-1$ 条边
• 没有环
• 每个点的度数都大于0

---

14. Dijkstra 算法中没有涉及（）算法思想。 {{ select(14) }}

• 贪心法
• 动态规划
• 二分法
• 调整法

---

15. 将正整数 $n$ 拆成任意多个正整数之和，使这些加数的乘积最大，则加数中不可能出现（）。 {{ select(15) }}

• 1
• 2
• 4
• 5

---

阅读程序（1）：

#include <iostream>
using namespace std;
const int N = 1009;
int n, q[N], x[N];
int main() {
    cin >> n; // 保证输入的数都是正整数，1 <= x[i] <= n <= 1000
    for (int i=1; i<=n; i++) cin >> x[i];
    for (int i=1; i<=n; i++) {
        for (int j=i; j>=x[i]+1; j--) q[j] = q[j-1];
        q[x[i]] = i;
    }
    for (int i=1; i<=n; i++)
        cout << q[i] << " ";
    return 0;
}

16. （1分）如果输出的每个数都不是0，那么输入的x[i]必须互不相同。 {{ select(16) }}

• 正确
• 错误

---

17. （1分）输出的n个数一定是1..n的一个排列（取值在1..n范围内且没有重复）。 {{ select(17) }}

• 正确
• 错误

---

18. 输出的 $n$ 个数中除了 0 以外, 其他数都互不相同。 {{ select(18) }}

• 正确
• 错误

---

19. 如果输入的 $x[i]$ 单调不降, 则输出也单调不降。 {{ select(19) }}

• 正确
• 错误

---

20. 固定 $n$, 对各种符合输入限制的 $x[i]$ 情况, 最好和最坏情况下代码的时间复杂度分别为( )。 {{ select(20) }}

• $O(n), O(n^2)$
• $O(n^2), O(n^2)$
• $O(n), O(n)$
• $O(n\log n), O(n^2)$

---

21. 若输入 8 1 1 2 3 1 1 2 3, 则输出为( )。 {{ select(21) }}

• 1 1 2 3 1 1 2 3
• 6 7 8 5 2 3 4 1
• 1 6 7 8 5 2 3 4
• 5 3 4 1 8 6 7 2

---

阅读程序（2）：

#include <bits/stdc++.h>
using namespace std;
const int N = 10009;
int n, cur, nxt[N];

int main() {
    cin >> n; // 保证 n 是 1..10000 范围内的整数
    for (int i=1; i<=n; ++i) nxt[i] = i % n + 1;
    for (cur=1; n>1; --n) {
        nxt[cur] = nxt[nxt[cur]];
        cur = nxt[cur];
    }
    cout << cur << endl;
    return 0;
}

22. 程序运行结束后, 除了最后的 cur, 其他 nxt 的值都为 0。 {{ select(22) }}

• 正确
• 错误

---

23. 若将 for 循环内的两句合并为 cur = nxt[cur] = nxt[nxt[cur]];, 则运行结果不会改变。 {{ select(23) }}

• 正确
• 错误

---

24. 若将 for 循环中的条件 n>1 改为 n>0, 则运行结果不会改变。 {{ select(24) }}

• 正确
• 错误

---

25. 假如强行输入 n=-1, 程序会异常退出。 {{ select(25) }}

• 正确
• 错误

---

26. 如上代码的时间复杂度是( )。 {{ select(26) }}

• $O(n)$
• $O(n\log n)$
• $O(n\sqrt n)$
• $O(n^2)$

---

27. 若输入 10000, 则输出为( )。 {{ select(27) }}

• 3616
• 3617
• 3618
• 3619

---

阅读程序（3）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[10009], s[509][10009], n, m;
int main() {
    cin >> n >> m; // 保证 1 <= n <= 10000, 1 <= m <= 250000, 1 <= x[i] <= 1000000
    for (ll i = 1; i <= n; i++) cin >> x[i];
    ll D = max(1LL, (ll) sqrt(m));
    for (ll d = 1; d <= D; d++)
        for (ll i = 1; i <= n; i++)
            if (i > d) s[d][i] = s[d][i - d] + x[i];
            else s[d][i] = x[i];
    for (ll i, d, k; m--;) {
        cin >> i >> d >> k; // 保证输入的 1 <= i, d, k <= n
        k = min(k, (n - i) / d + 1);
        if (d <= D) {
            if (i > d) cout << s[d][i + (k - 1) * d] - s[d][i - d] << endl;
            else cout << s[d][i + (k - 1) * d] << endl;
        } else {
            ll sum = 0;
            for (int j = 0; j < k; ++j) sum += x[i + j * d];
            cout << sum << endl;
        }
    }
    return 0;
}

28. 将所有整数类型longlong都换成int,结果不变,因为输入数据都在int范围内。 {{ select(28) }}

• 正确
• 错误

---

29. 假如k没有截断（去掉 k = min(k, (n - i) / d + 1); 这句）,但问询的i,d,k保证了 $i+(k-1)*d \leq 500$,那么程序结果不会改变。 {{ select(29) }}

• 正确
• 错误

---

30. 代码占用的内存空间大致为5MB。 {{ select(30) }}

• 正确
• 错误

---

31. 在不影响时间复杂度的情况下,可以把空间复杂度优化到 $O(n+m)$。 {{ select(31) }}

• 正确
• 错误

---

32. 此代码最坏情况下的时间复杂度是( )。 {{ select(32) }}

• $O(nm)$
• $O(n^2)$
• $O(n\sqrt m)$
• $O(m\sqrt n)$

---

33. 假如强行将以下某个变量的值输入为负数（其他变量仍为正数）,一定会导致数组下标越界的是( )。 {{ select(33) }}

• n
• i
• d
• k

---

完善程序（1）：

#include <bits/stdc++.h>
using namespace std;
int n, ans, sum;
int main() {
    cin >> n;
    for (int i=1,j; i<=①; ++i) {
        for (j=i, ②; ③; j++) sum += j;
        if (④) ans++;
    }
    cout << ans << endl;
    // 该程序的时间复杂度是 ⑤
    return 0;
}

34. ①处应填（ {{ select(34) }}

• n
• n/2
• $(n+1)/2$
• n/2+1

---

35. ②处应填（ {{ select(35) }}

• sum=0
• sum=i
• sum++
• sum+=j

---

36. ③处应填（ {{ select(36) }}

• j<=n
• j<n
• sum<=n
• sum<n

---

37. ④处应填（ {{ select(37) }}

• sum>=n
• sum+j==n
• sum==n
• j-i>=2

---

38. ⑤处应填（ {{ select(38) }}

• O(n)
• O(nlog n)
• O(n√n)
• O(n²)

---

完善程序（2）：

#include <iostream>
using namespace std;
int n, x, s, cnt;
int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> x;
        if (①) ②;
        if (③) ④;
        else ⑤;
    }
    cout << s << endl;
    return 0;
}

39. ①处应填（ {{ select(39) }}

• cnt > 0
• cnt >= 0
• cnt == 0
• cnt

---

40. ②处应填（ {{ select(40) }}

• s = cnt
• s = x
• s = i
• s = n

---

41. ③处应填（ {{ select(41) }}

• x < s
• x > s
• x == s
• x == cnt

---

42. ④处应填（ {{ select(42) }}

• cnt++
• cnt--
• cnt = i
• cnt = 0

---

43. ⑤处应填（ {{ select(43) }}

• cnt++
• cnt--
• cnt = i
• cnt = 0

---