算法设计与分析算法考试算法设计与分析往年试题答案
VIP免费
2025-01-13
2
0
34.67KB
6 页
5.9玖币
侵权投诉
算法设计与分析往年试题答案
一、 判断题
1. 一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。
对。
2. NP 完全问题比其他所有 NP 问题都要难。
NP 问题分为 NP-hard 问题和 NP 完全问题，NP 完全问题是最难的，但是 NP-hard 问题又包含 NP 完全问题。
错：NP 完全问题至少同其他所有 NP 问题一样难。
3. 回溯法用深度优先法或广度优先法搜索状态空间树。
错：回溯法用深度优先法搜索状态空间树。
4. 在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。
错：在动态规划中，各个阶段所确定的决策构成一个决策序列，通常称为一个策略。
5.
P
类和
NP
类问题的关系用
P⊂NP
来表示是错误的。
错：P中所有问题均属于 NP。
P：存在求解判定问题 P1 的多项式时间算法。
NP：对 P1 的每一个肯定实例均存在一个多项式时间内的验证。（对一个实例为肯定实例的证明称为该实例的
证书。）
NPcomplete:P1 是一个 NP 问题，且 NP 中所有问题都可以多项式转化为 P1.
NPhard：NP 中所有问题都可以多项式转化为 P1。
NPhard 问题范围大于 NPcomplete 问题范围。
6. 若近似算法 A求解某极小化问题一实例的解为
sa
，且已知该问题的最优解为
sa/3
，则该近似算法的性能比为
3。
错：性能比是所有实例可能的精确率的上界。3只是这一实例的精确率，不是所有实例的。
7. 通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。
对。
8. 若P2 多项式时间转化为(polynomial transforms to) P1，则 P2 至少与 P1 一样难。
错：应该是 p1 至少和 p2 一样难，有可能 p1 更难。
总是可以在可比时间内用 P1 的算法解决 P2，但不能说 P1 和P2 一样难。事实上，有时候可能 P2 简单而 P1 更
难。
9. 快速排序算法的平均时间复杂度是
O(nlogn)
，使用随机化快速排序算法可以将平均时间复杂度降得更低。
错。
10. 基于比较的寻找数组
A[1, …, n]
中最大元素的问题下界是
Ω(n/3)
。
对：下界理论：问题的下界不唯一，越高越好。算法最优：下界=上界
几个问题的下界：
（1） 排序问题：
Ω
(
n logn
)
（2） 找最大：
Ω(n/2)
或
Ω(n−1)
（3） 找最大最小：
Ω(3n
2−2)
下界是用分治策略得到的结果：将数组均分成两部分，在每部分中找出最大
值和最小值，在比较这两部分的最大值和最小值。
（4） 找第二大元素：
Ω(n+logn−2)
找第一大元素需要比较 n-1 次，第一是通过两两配对比较中较大的元
素中最大的元素，第二大元素师两两比较中第二大的元素，再找到第二大元素需要 logn-1 次比较，加
在一起得到如上结果。
11.
O
(
f
(
n
)
)
+O
(
g
(
n
)
)
=O¿
错。应该是 max，O代表的是算法的上界。
12. 若
f
(
n
)
=Ω
(
g
(
n
)
)
，
g
(
n
)
=Ω
(
h
(
n
)
)
，则
f
(
n
)
=Ω
(
h
(
n
)
)
对：
Ω
相当于小于等于。
1
13. 若
f
(
n
)
=O
(
g
(
n
)
)
，则
g
(
n
)
=Ω(f
(
n
)
)
对：O相当于大于等于。
14. 贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。
错：贪心算法每一步必须满足：可行的（即它必须满足问题的约束）、局部最优、不可撤销。
贪心算法通常包含一个用以寻找局部最优解的迭代过程，在某些实例中这些局部最优解转变成了全局最优解，
而在另外一些实例中则无法找到全局最优解。
15. Las Vegas 算法只要给出解就是正确的。
对。
16. 一个完全多项式近似方案是一个近似方案
{Aε}
，其中每一个算法
Aε
在输入实例
I
的规模的多项式时间内运行。
错：题目中定义的是多项式近似方案。
完全多项式近似方案：是一个近似方案
{Aε}
，其中每一个算法
Aε
在输入实例
I
的规模和
1/ε
两者的多项式时间
内运行
二、 问答题
1. 二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？此时的查
找和插入算法的复杂性如何？
（1） 二叉查找树属于减治策略中减少可变规模变种中的应用；
（2） 当树的高度=节点个数-1，即树是一颗严格歪树时表现出最差的效率；
（3）此时查找和插入算法的时间复杂度为 O(n)。
减治法的三种变种：
（1） 减去一个常量：
递归法求
an
;
插入排序；最坏
n2
平均
n2/4
快速排序+插入排序
拓扑排序：减一
生成排序：减一 要求 1-n 的排序先求 1-（n-1）的排序
生成子集：减一
（2） 减去一个常数因子：
二分搜索
假币问题
俄式乘法
约瑟夫问题
（3） 减去可变规模
欧几里得除法
插值查找：最差O(n)
二叉查找树:最差O(n) 平均 O(logn)
变治的 3种类型：
（1） 实例化简：变换为同样问题的一个更简单或更方便的实例
预排序：如果列表是有序的，许多问题更容易求解。
-检验数组中元素的唯一性：先对数组排序，然后只检查连续元素，如果该数组有相等的元素则一定有一对
元素是相互紧挨着的 复杂度：排序+查找紧邻元素是否相同即 O（nlogn+n）=o(nlogn)。
-查找数字列表中出现频率最高的一个数：先对输入排序（之后有相等的数值都会邻接在一起），求出该有
序数组中邻接次数最多的等值元素。
高斯消去：把n个线性方程构成的 n元联立方程组变换为一个等价的方程组，该方程组有一个上三角系数
矩阵，该矩阵主对角线下的元素都为 0.
LU 分解
2
摘要：
展开>>
收起<<
算法设计与分析往年试题答案一、判断题1.一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。对。2.NP完全问题比其他所有NP问题都要难。NP问题分为NP-hard问题和NP完全问题，NP完全问题是最难的，但是NP-hard问题又包含NP完全问题。错：NP完全问题至少同其他所有NP问题一样难。3.回溯法用深度优先法或广度优先法搜索状态空间树。错：回溯法用深度优先法搜索状态空间树。4.在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。错：在动态规划中，各个阶段所确定的决策构成一个决策序列，通常称为一个策略。5.P类和NP类问题的关系用P⊂NP来表示是...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
工程建设招标投标合同（附件）VIP免费
2024-11-15 16 -
工程建设招标投标合同（动员预付款银行保证书）VIP免费
2024-11-15 11 -
工程建设招标设标合同条件（第1部分）VIP免费
2024-11-15 11 -
工程建设招标设标合同合同条件（第3部分）VIP免费
2024-11-15 10 -
工程建设招标设标合同合同条件（第2部分）VIP免费
2024-11-15 13 -
工程建设监理委托合同VIP免费
2024-11-15 14 -
工程建设监理合同标准条件VIP免费
2024-11-15 11 -
工程技术资料目录VIP免费
2024-11-15 13 -
工程技术咨询服务合同VIP免费
2024-11-15 13 -
工程建设招标投标合同（投标邀请书）VIP免费
2024-11-15 35
分类：计算机
价格：5.9玖币
属性：6 页
大小：34.67KB
格式：DOCX
时间：2025-01-13
渝公网安备50010702506394
