单项选择题

1. 以下程序的时间复杂度是()

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
        for (int k = j; k <= n; k++)
            cout << i << " " << j << " " << k << "\n";

{{ select(1) }}

• $O(n^3)$
• $O(n^2)$
• $O(n)$
• $O(n!)$

2. 算法 g(n, m) 最为准确的时间复杂度分析结果为()

int g(int n, int m)
{
    for (int i = 1; i <= n; i++)
        h[i][1] = i;
    for (int j = 1; j <= m; j++)
        h[0][j] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 2; j <= m; j++)
        {
            h[i][j] = numeric_limits<int>::max();
            for (int k = 1; k <= i; k++)
                h[i][j] = min(h[i][j], max(h[i - k][j], h[k - 1][j - 1]) + 1);
        }
    }
    return h[n][m];
}

{{ select(2) }}

• $O(n^{\frac{3}{2}m})$
• $O(nm)$
• $O(n^2m)$
• $O(nm^2)$

3. 该算法最准确的时间复杂度分析结果为()。

#include <iostream>
using namespace std;
int n, k;
int solve1()
{
    int l = 0, r = n;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (mid * mid <= n)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l - 1;
}
double solve2(double x)
{
    if (x == 0)
        return x;
    for (int i = 0; i < k; i++)
        x = (x + n / x) / 2;
    return x;
}
int main()
{
    cin >> n >> k;
    double ans = solve2(solve1());
    cout << ans << ' ' << (ans * ans == n) << endl;
    return 0;
}

{{ select(3) }}

• $𝑂(\log{n}+k)$
• $𝑂(\log{n})$
• $𝑂(n+k)$
• $𝑂(k)$

4. 该程序的时间复杂度是()

#include <iostream>
using namespace std;
int n, stk[105], a[105], top, f[105];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        while (top && a[i] >= a[stk[top]])
        {
            f[stk[top]] = i;
            top--;
        }
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++) cout << f[i] << " ";
    return 0;
}

{{ select(4) }}

• $O(n^2)$
• $O(n)$
• $O(n^3)$
• $O(n*top)$

5. 以下程序的时间复杂度为()。

#include <iostream>
using namespace std;
int f[100005];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            f[j]++;
        }
    }
    for (int i = 1; i <= n; i++) cout << f[i] << " ";
    return 0;
}

{{ select(5) }}

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

6. 一个 $32$ 位整型变量占用()个字节。 {{ select(6) }}

• $1$
• $2$
• $4$
• $8$

7. 在 $8$ 位二进制补码中，$10101011$ 表示的数是十进制下的 ()。 {{ select(7) }}

• $43$
• $-85$
• $-43$
• $-83$

8. 计算机存储数据的基本单位是()。 {{ select(8) }}

• bit
• byte
• GB
• KB

9. 分辨率为 $800\times 600$，$16$ 位色的位图，存储图像信息所需的空间为() {{ select(9) }}

• $937.5$ KB
• $4218.75$ KB
• $4320$ KB
• $2880$ KB

10. 如果 $256$ 种颜色用二进制编码来表示，至少需要 () 位。

{{ select(10) }}

• $6$
• $7$
• $8$
• $9$

11. 某道题的内存限制是 $512$ MB，小红准备开一个 bool 类型的数组，请问她可以最多开一个多大的数组，选择一个和选项最接近的即可。 {{ select(11) }}

• $5*10^8$
• $10^8$
• $10^7$
• $5*10^7$

12. 某位同学在 CSP-J 比赛中开了一个 long long 类型的数组，且该数组大小为 $10^9$，题目的内存限制是 $1GB$，请问他是否会超出内存限制。

{{ select(12) }}

• 会
• 不会