#P0065. 算法通识与复杂度

算法通识与复杂度

第一讲:算法通识与复杂度分析

本试卷共 25 道题,每题 4 分,满分 100 分。

注意事项:

  • 第 1~18 题、第 20~22 题为单选题,其余为多选题。
  • 假设所有简单的加法、赋值、比较操作都可以在常数时间内完成。
  • 判断时间复杂度时,选择最紧的渐近复杂度,忽略常数倍。
  • 运行时间估算题统一假设计算机每秒执行 10810^8 次简单操作。
  • 内存估算题统一假设 int 占 4 字节、long long 占 8 字节、char 占 1 字节,1 MB=1061\text{ MB}=10^6 字节。
  • 不考虑编译器优化、循环控制开销、输入输出和容器额外开销。

一、单项选择题

第 1 题

以下关于算法的说法,正确的是( )。

{{ select(1) }}

  • 算法必须使用 C++ 编写
  • 算法应当能够在有限的步骤内结束
  • 算法只能用于解决数学问题
  • 算法必须包含循环语句

第 2 题

对于同一个问题,以下说法正确的是( )。

{{ select(2) }}

  • 一个问题只能有一种算法
  • 同一个问题可以使用不同的算法解决
  • 代码越短,算法的运行速度一定越快
  • 只有使用数组才能设计算法

第 3 题

我们经常使用 nn 表示输入规模。在处理一个包含 nn 个整数的数组时,nn 通常表示( )。

{{ select(3) }}

  • 数组中整数的数量
  • 程序运行的秒数
  • 程序代码的行数
  • 计算机的 CPU 数量

第 4 题

在分析算法的时间复杂度时,我们主要关注的是( )。

{{ select(4) }}

  • 程序使用了多少个变量
  • 随着输入规模增大,算法所需操作次数如何增长
  • 程序的代码有多少行
  • 程序使用了多少个头文件

第 5 题

阅读以下代码:

int ans=0;
for(int i=0;i<5;i++){
    ans++;
}

执行结束后,ans 的值为( )。

{{ select(5) }}

  • 4
  • 6
  • 5
  • 10

第 6 题

阅读以下代码:

int ans=0;
for(int i=1;i<=8;i+=2){
    ans++;
}

执行结束后,ans 的值为( )。

{{ select(6) }}

  • 4
  • 5
  • 8
  • 16

第 7 题

阅读以下代码:

int ans=0;
for(int i=1;i<=n;i++){
    ans++;
}

该代码的时间复杂度为( )。

{{ select(7) }}

  • O(1)O(1)
  • O(n)O(n)
  • O(n2)O(n^2)
  • O(2n)O(2^n)

第 8 题

阅读以下代码:

int ans=0;
for(int i=1;i<=100;i++){
    ans++;
}

该代码的时间复杂度为( )。

{{ select(8) }}

  • O(n)O(n)
  • O(100n)O(100n)
  • O(1)O(1)
  • O(n2)O(n^2)

第 9 题

阅读以下代码:

int ans=0;
for(int i=1;i<=n;i++){
    ans++;
}
for(int i=1;i<=n;i++){
    ans++;
}

该代码的时间复杂度为( )。

{{ select(9) }}

  • O(n2)O(n^2)
  • O(1)O(1)
  • O(log⁡n)O(\log n)
  • O(n)O(n)

第 10 题

阅读以下代码:

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

该代码的时间复杂度为( )。

{{ select(10) }}

  • O(n2)O(n^2)
  • O(n)O(n)
  • O(1)O(1)
  • O(n3)O(n^3)

第 11 题

阅读以下代码:

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

该代码的时间复杂度为( )。

{{ select(11) }}

  • O(n2)O(n^2)
  • O(1)O(1)
  • O(n)O(n)
  • O(n3)O(n^3)

第 12 题

阅读以下代码:

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

当 n=16n=16 时,执行结束后 ans 的值为( )。

{{ select(12) }}

  • 4
  • 5
  • 8
  • 16

第 13 题

阅读以下代码:

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

假设 n,mn,m 是两个独立的正整数变量,该代码的时间复杂度为( )。

{{ select(13) }}

  • O(n+m)O(n+m)
  • O(n2)O(n^2)
  • O(m2)O(m^2)
  • O(nm)O(nm)

第 14 题

假设 n=105n=10^5,阅读以下代码:

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

假设每次 ans++ 代表一次简单操作,计算机每秒执行 10810^8 次简单操作。

程序运行时间大约为( )。

{{ select(14) }}

  • 0.001 秒
  • 0.01 秒
  • 0.1 秒
  • 1 秒

第 15 题

假设 n=104n=10^4,m=102m=10^2,阅读以下代码:

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

假设每次 ans++ 代表一次简单操作,计算机每秒执行 10810^8 次简单操作。

程序运行时间大约为( )。

{{ select(15) }}

  • 0.0001 秒
  • 0.001 秒
  • 0.01 秒
  • 1 秒

第 16 题

假设 n=104n=10^4,阅读以下代码:

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

假设每次 ans++ 代表一次简单操作,计算机每秒执行 10810^8 次简单操作。

程序运行时间大约为( )。

{{ select(16) }}

  • 0.01 秒
  • 1 秒
  • 100 秒
  • 10000 秒

第 17 题

假设 n=106n=10^6,阅读以下代码:

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

假设每次 ans++ 代表一次简单操作,计算机每秒执行 10810^8 次简单操作。

程序运行时间大约为( )。

{{ select(17) }}

  • 0.005 秒
  • 0.05 秒
  • 0.5 秒
  • 5 秒

第 18 题

假设 n=106n=10^6,m=107m=10^7,阅读以下代码:

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

假设每次 ans++ 代表一次简单操作,计算机每秒执行 10810^8 次简单操作。

程序运行时间最接近( )。

{{ select(18) }}

  • 0.001 秒
  • 0.01 秒
  • 0.1 秒
  • 10 秒

第 19 题(多选)

某道题目的数据范围为:

n≤105n\leq 10^5

时间限制为 1 秒。

假设各算法的基本操作次数大致等于复杂度表达式对应的数量,且计算机每秒执行 10810^8 次简单操作。

以下哪些复杂度在该估算模型下可以在 1 秒内完成?( )

{{ multiselect(19) }}

  • O(n)O(n)
  • O(nlog⁡2n)O(n\log_2 n)
  • O(n2)O(n^2)
  • O(50n)O(50n)

第 20 题

阅读以下代码:

int a[1000000];

数组 a 大约占用多少内存?( )

{{ select(20) }}

  • 0.4 MB
  • 4 MB
  • 8 MB
  • 40 MB

第 21 题

阅读以下代码:

long long a[1000][2000];

数组 a 大约占用多少内存?( )

{{ select(21) }}

  • 2 MB
  • 4 MB
  • 8 MB
  • 16 MB

第 22 题

阅读以下代码:

long long a[100000];
int b[200000];

假设只计算这两个数组占用的空间,它们总共大约需要多少内存?( )。

{{ select(22) }}

  • 0.8 MB
  • 1.2 MB
  • 1.6 MB
  • 2.4 MB

第 23 题(多选)

某道题目的数据范围为:

n≤104,m≤102n\leq 10^4,\quad m\leq 10^2

时间限制为 1 秒。

假设各算法的基本操作次数大致等于下列复杂度表达式的值,且计算机每秒执行 10810^8 次简单操作。

以下哪些复杂度在最大数据范围下可以在 1 秒内完成?( )

{{ multiselect(23) }}

  • O(n+m)O(n+m)
  • O(nm)O(nm)
  • O(n2m)O(n^2m)
  • O(m5)O(m^5)

第 24 题(多选)

某道题目的内存限制为 8 MB。

假设程序除下面给出的数组外不占用其他内存,以下哪些数组可以在 8 MB 内存限制内存放?( )

{{ multiselect(24) }}

  • int a[1000][1000];
  • long long b[1000][1000];
  • int c[2000][2000];
  • char d[2000][2000];

第 25 题(多选)

假设 n 是一个正整数,以下代码片段中,时间复杂度为 Θ(n)\Theta(n) 的有( )。

{{ multiselect(25) }}

  • for(int i=1;i<=n;i++){
        ans++;
    }
    
  • for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans++;
        }
    }
    
  • for(int i=1;i<=n;i++){
        for(int j=1;j<=5;j++){
            ans++;
        }
    }
    
  • for(int i=1;i<=n*n;i++){
        ans++;
    }