DC703阶段测试一 - 题目详情 - 信创计划

ID: 2337

客观题

难度: 9

上传者:

埃拉托斯特尼筛法的时间复杂度是（）
{{ select(1) }}

(O(n))
(O(nloglog n))
(O(nlog n))
(O(n^2))

以下关于线性筛（欧拉筛）的说法，正确的是（） {{ select(2) }}

不能保证每个合数仅被最小的质因数筛掉
时间复杂度为 (O(nlog n))
可以同时求出每个数的最小质因数
空间复杂度高于埃氏筛

线性筛中，判断一个数是否为质数的依据是（） {{ select(3) }}

未被任何质数筛掉
仅被自身的最小质因数筛掉
能被2~√n中的数整除
不在筛数组中标记为合数

线性DP的核心思想是（） {{ select(4) }}

分治
贪心
递推，利用子问题的最优解推导当前问题的最优解
枚举所有可能情况

对于最长上升子序列问题，若使用(O(n^2))的DP算法，状态转移方程中(dp[i])表示（） {{ select(5) }}

前i个元素的最长上升子序列长度
以第i个元素结尾的最长上升子序列长度
前i个元素中最长上升子序列的元素和
第i个元素开始的最长上升子序列长度

01背包问题中，若物品数为n，背包容量为V，时间复杂度优化到一维数组后是（） {{ select(6) }}

(O(nV))
(O(n^2V))
(O(nV^2))
(O(2^n))

完全背包问题与01背包问题的核心区别是（） {{ select(7) }}

物品可以选多次
物品只能选一次
背包容量更大
物品价值更高

多重背包问题中，若每个物品最多选k次，以下哪种优化方法的时间复杂度最低（） {{ select(8) }}

暴力枚举每个物品选0~k次
二进制优化
单调队列优化
以上都不对

对于01背包的一维数组优化，循环顺序应为（） {{ select(9) }}

物品逆序，容量逆序
物品正序，容量逆序
物品逆序，容量正序
物品正序，容量正序

完全背包问题中，计算(dp[j])时，(dp[j - v[i]])的状态是（） {{ select(10) }}

已经处理过第i个物品的状态
未处理第i个物品的状态
任意状态
以上都不对

在下列比赛中:

DC0703阶段测试一