#P0065. 算法通识与复杂度
算法通识与复杂度
第一讲:算法通识与复杂度分析
本试卷共 25 道题,每题 4 分,满分 100 分。
注意事项:
- 第 1~18 题、第 20~22 题为单选题,其余为多选题。
- 假设所有简单的加法、赋值、比较操作都可以在常数时间内完成。
- 判断时间复杂度时,选择最紧的渐近复杂度,忽略常数倍。
- 运行时间估算题统一假设计算机每秒执行 次简单操作。
- 内存估算题统一假设
int占 4 字节、long long占 8 字节、char占 1 字节, 字节。 - 不考虑编译器优化、循环控制开销、输入输出和容器额外开销。
一、单项选择题
第 1 题
以下关于算法的说法,正确的是( )。
{{ select(1) }}
- 算法必须使用 C++ 编写
- 算法应当能够在有限的步骤内结束
- 算法只能用于解决数学问题
- 算法必须包含循环语句
第 2 题
对于同一个问题,以下说法正确的是( )。
{{ select(2) }}
- 一个问题只能有一种算法
- 同一个问题可以使用不同的算法解决
- 代码越短,算法的运行速度一定越快
- 只有使用数组才能设计算法
第 3 题
我们经常使用 表示输入规模。在处理一个包含 个整数的数组时, 通常表示( )。
{{ 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) }}
第 8 题
阅读以下代码:
int ans=0;
for(int i=1;i<=100;i++){
ans++;
}
该代码的时间复杂度为( )。
{{ select(8) }}
第 9 题
阅读以下代码:
int ans=0;
for(int i=1;i<=n;i++){
ans++;
}
for(int i=1;i<=n;i++){
ans++;
}
该代码的时间复杂度为( )。
{{ select(9) }}
第 10 题
阅读以下代码:
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans++;
}
}
该代码的时间复杂度为( )。
{{ select(10) }}
第 11 题
阅读以下代码:
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
ans++;
}
}
该代码的时间复杂度为( )。
{{ select(11) }}
第 12 题
阅读以下代码:
int ans=0;
for(int i=1;i<=n;i*=2){
ans++;
}
当 时,执行结束后 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++;
}
}
假设 是两个独立的正整数变量,该代码的时间复杂度为( )。
{{ select(13) }}
第 14 题
假设 ,阅读以下代码:
for(int i=1;i<=n;i++){
ans++;
}
假设每次 ans++ 代表一次简单操作,计算机每秒执行 次简单操作。
程序运行时间大约为( )。
{{ select(14) }}
- 0.001 秒
- 0.01 秒
- 0.1 秒
- 1 秒
第 15 题
假设 ,,阅读以下代码:
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans++;
}
}
假设每次 ans++ 代表一次简单操作,计算机每秒执行 次简单操作。
程序运行时间大约为( )。
{{ select(15) }}
- 0.0001 秒
- 0.001 秒
- 0.01 秒
- 1 秒
第 16 题
假设 ,阅读以下代码:
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans++;
}
}
假设每次 ans++ 代表一次简单操作,计算机每秒执行 次简单操作。
程序运行时间大约为( )。
{{ select(16) }}
- 0.01 秒
- 1 秒
- 100 秒
- 10000 秒
第 17 题
假设 ,阅读以下代码:
for(int i=1;i<=n;i++){
ans++;
ans++;
ans++;
ans++;
ans++;
}
假设每次 ans++ 代表一次简单操作,计算机每秒执行 次简单操作。
程序运行时间大约为( )。
{{ select(17) }}
- 0.005 秒
- 0.05 秒
- 0.5 秒
- 5 秒
第 18 题
假设 ,,阅读以下代码:
for(int i=1;i<=n;i++){
ans++;
}
for(int j=1;j<=m;j++){
ans++;
}
假设每次 ans++ 代表一次简单操作,计算机每秒执行 次简单操作。
程序运行时间最接近( )。
{{ select(18) }}
- 0.001 秒
- 0.01 秒
- 0.1 秒
- 10 秒
第 19 题(多选)
某道题目的数据范围为:
时间限制为 1 秒。
假设各算法的基本操作次数大致等于复杂度表达式对应的数量,且计算机每秒执行 次简单操作。
以下哪些复杂度在该估算模型下可以在 1 秒内完成?( )
{{ multiselect(19) }}
第 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 题(多选)
某道题目的数据范围为:
时间限制为 1 秒。
假设各算法的基本操作次数大致等于下列复杂度表达式的值,且计算机每秒执行 次简单操作。
以下哪些复杂度在最大数据范围下可以在 1 秒内完成?( )
{{ multiselect(23) }}
第 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 是一个正整数,以下代码片段中,时间复杂度为 的有( )。
{{ 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++; }