练习题 -- 数据结构与算法 >> 算法策略
共 6 题
第 1/6 题
★★
分治法的时间复杂度一般通过什么来分析？
正确答案: D
【算法-算法策略】
题目：分治法时间复杂度分析：
✅ 正确答案：D.以上都是
错误选项：
❌ A.递归树
❌ B.主定理
❌ C.数学归纳
📖 解析：递归树/主定理/数学归纳都可用于分治复杂度分析。
题目：分治法时间复杂度分析：
✅ 正确答案：D.以上都是
错误选项：
❌ A.递归树
❌ B.主定理
❌ C.数学归纳
📖 解析：递归树/主定理/数学归纳都可用于分治复杂度分析。
第 2/6 题
★
下列问题适合用贪心算法解决的是：
正确答案: C
【算法-算法策略】
题目：适合贪心算法的问题：
✅ 正确答案：C.哈夫曼编码
错误选项：
❌ A.0/1背包
❌ B.最长公共子序列
❌ D.旅行商
📖 解析：哈夫曼有贪心选择性质。0/1背包需DP。
📌 拓展：典型贪心算法：哈夫曼编码、Prim/Kruskal最小生成树、Dijkstra最短路径、部分背包、活动选择。
题目：适合贪心算法的问题：
✅ 正确答案：C.哈夫曼编码
错误选项：
❌ A.0/1背包
❌ B.最长公共子序列
❌ D.旅行商
📖 解析：哈夫曼有贪心选择性质。0/1背包需DP。
📌 拓展：典型贪心算法：哈夫曼编码、Prim/Kruskal最小生成树、Dijkstra最短路径、部分背包、活动选择。
第 3/6 题
★★
贪心算法和动态规划的共同点是：
正确答案: B
【算法-算法策略】
题目：贪心和DP的共同点：
✅ 正确答案：B.都要求最优子结构
错误选项：
❌ A.都保证全局最优
❌ C.都使用分治
❌ D.都可解决0/1背包
📖 解析：贪心和DP都要求最优子结构。但贪心还需贪心选择性质。
📌 拓展：典型贪心算法：哈夫曼编码、Prim/Kruskal最小生成树、Dijkstra最短路径、部分背包、活动选择。
题目：贪心和DP的共同点：
✅ 正确答案：B.都要求最优子结构
错误选项：
❌ A.都保证全局最优
❌ C.都使用分治
❌ D.都可解决0/1背包
📖 解析：贪心和DP都要求最优子结构。但贪心还需贪心选择性质。
📌 拓展：典型贪心算法：哈夫曼编码、Prim/Kruskal最小生成树、Dijkstra最短路径、部分背包、活动选择。
第 4/6 题
★★
以下问题中，既可以用贪心算法又可以用动态规划解决的是：
正确答案: B
【算法-算法策略】
题目：既可用贪心又可用DP的是：
✅ 正确答案：B.部分背包
错误选项：
❌ A.0/1背包
❌ C.最长公共子序列
❌ D.矩阵连乘
📖 解析：部分背包选单价最高即可（贪心最优）。0/1背包需DP。
📌 拓展：典型贪心算法：哈夫曼编码、Prim/Kruskal最小生成树、Dijkstra最短路径、部分背包、活动选择。
题目：既可用贪心又可用DP的是：
✅ 正确答案：B.部分背包
错误选项：
❌ A.0/1背包
❌ C.最长公共子序列
❌ D.矩阵连乘
📖 解析：部分背包选单价最高即可（贪心最优）。0/1背包需DP。
📌 拓展：典型贪心算法：哈夫曼编码、Prim/Kruskal最小生成树、Dijkstra最短路径、部分背包、活动选择。
第 5/6 题
★
动态规划算法的基本思想是：
正确答案: B
【算法-算法策略】
题目：DP的基本思想是：
✅ 正确答案：B.自底向上填表
错误选项：
❌ A.自顶向下递归
❌ C.随机搜索
❌ D.DFS
📖 解析：DP从小问题逐步推到大问题，表存中间结果避免重复。
题目：DP的基本思想是：
✅ 正确答案：B.自底向上填表
错误选项：
❌ A.自顶向下递归
❌ C.随机搜索
❌ D.DFS
📖 解析：DP从小问题逐步推到大问题，表存中间结果避免重复。
第 6/6 题
★★
动态规划与分治法的关键区别：
正确答案: B
【算法-算法策略】
题目：DP与分治法的关键区别：
✅ 正确答案：B.子问题重叠
错误选项：
❌ A.DP更慢
❌ C.DP用递归
❌ D.DP不用表
📖 解析：DP特点：最优子结构+子问题重叠（用表避免重复）。分治子问题独立。
题目：DP与分治法的关键区别：
✅ 正确答案：B.子问题重叠
错误选项：
❌ A.DP更慢
❌ C.DP用递归
❌ D.DP不用表
📖 解析：DP特点：最优子结构+子问题重叠（用表避免重复）。分治子问题独立。