CSP 校队 9.8 进阶摸底

本题用于校队赛前能力摸底。建议限时 28 分钟。题目故意设置了较强区分度；不会的题先跳过，不查资料、不讨论。

请直接在页面中选择答案后提交。

---

第 1 题

执行下面的 C++ 代码，输出结果是？

int x = 13, y = 7;
cout << ((x ^ y) + (x & y));

{{ select(1) }}

• 12
• 13
• 15
• 18

第 2 题

执行下面的代码，输出结果是？

int x = 44;
x &= (x - 1);
x &= (x - 1);
cout << x;

{{ select(2) }}

• 28
• 32
• 36
• 40

第 3 题

执行表达式 0x3A ^ 0x0F，其十进制结果是？

{{ select(3) }}

• 45
• 51
• 53
• 55

第 4 题

下面代码的时间复杂度是？

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++)
        ans++;

{{ select(4) }}

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

第 5 题

下面代码的时间复杂度是？

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        ans++;

{{ select(5) }}

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

第 6 题

下面代码的时间复杂度是？

for (long long i = 1; i * i <= n; i++)
    ans++;

{{ select(6) }}

• O(log n)
• O(sqrt(n))
• O(n)
• O(n log n)

第 7 题

下面代码的时间复杂度是？

for (int i = 1; i <= n; i++) {
    for (int j = i; j > 0; j /= 2)
        ans++;
}

{{ select(7) }}

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

第 8 题

阅读函数，输出结果是？

int f(int n) {
    if (n <= 1) return 1;
    return f(n / 2) + 1;
}
cout << f(20);

{{ select(8) }}

• 4
• 5
• 6
• 20

第 9 题

元素 1,2,3,4,5 按顺序入栈。在入栈过程中允许随时出栈。下面哪一个可能是完整的出栈序列？

{{ select(9) }}

• 3 5 4 1 2
• 3 2 5 4 1
• 2 4 1 5 3
• 5 3 4 2 1

第 10 题

阅读程序，输出结果是？

queue<int> q;
stack<int> s;
for (int i = 1; i <= 4; i++) q.push(i);
while (!q.empty()) {
    s.push(q.front());
    q.pop();
}
while (!s.empty()) {
    cout << s.top();
    s.pop();
}

{{ select(10) }}

• 1234
• 2143
• 3412
• 4321

第 11 题

一棵有 100 个结点的完全二叉树中，叶子结点的数量是？

{{ select(11) }}

• 49
• 50
• 51
• 64

第 12 题

一个无向图中所有顶点的度数之和为 38，则该图的边数是？

{{ select(12) }}

• 19
• 38
• 76
• 无法确定

第 13 题

对一个长度为 1000 的有序数组进行标准二分查找，最坏情况下比较次数最合理的是？

{{ select(13) }}

• 9 次
• 10 次
• 100 次
• 1000 次

第 14 题

数组 7, 3, 5, 1, 6, 2 中共有多少个逆序对？

{{ select(14) }}

• 8
• 9
• 10
• 11

第 15 题

阅读程序，输出结果是？

int a = 0;
for (int i = 1; i <= 8; i++) {
    if (i & 1) a ^= i;
    else a += i;
}
cout << a;

{{ select(15) }}

• 4
• 6
• 8
• 10

第 16 题

若 n <= 2 * 10^5，在通常的 CSP C++ 竞赛环境中，下面哪种复杂度最适合作为主算法？

{{ select(16) }}

• O(n!)
• O(2^n)
• O(n log n)
• O(n^2)