算法设计与分析算法考试2011Algo——Answer可看性强点

VIP免费
2025-01-13 2 0 36.21KB 6 页 5.9玖币
侵权投诉
判断题
1. 一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。
2. NP 完全问题比其他所有 NP 问题都要难。
3. 回溯法用深度优先法或广度优先法搜索状态空间树。
4. 在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。
5.
P
类和
NP
类问题的关系用
P⊂NP
来表示是错误的。
6. 若近似算法 A求解某极小化问题一实例的解为
sa
，且已知该问题的最优解为
sa/3
，则该近似算法的
性能比为 3。
7. 通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。
8. 若P2 多项式时间转化为(polynomial transforms to) P1，则 P2 至少与 P1 一样难。
9. 快速排序算法的平均时间复杂度是
O(nlogn)
，使用随机化快速排序算法可以将平均时间复杂度降
得更低。
10. 基于比较的寻找数组
A[1, … , n]
中最大元素的问题下届是
Ω(n/3)
。
11.
12. 若
f
(
n
)
=Ω
(
g
(
n
)
)
，
g
(
n
)
=Ω
(
h
(
n
)
)
，则
f
(
n
)
=Ω
(
h
(
n
)
)
13. 若
f
(
n
)
=O
(
g
(
n
)
)
，则
g
(
n
)
=Ω(f
(
n
)
)
14. 贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。
15. Las Vegas 算法只要给出解就是正确的。
16. 一个完全多项式近似方案是一个近似方案
{Aε}
，其中每一个算法
Aε
在输入实例
I
的规模的多项式时
间内运行。
判断题：
1-5: T F F T F 6-10: F T T F F 11-16: F T T T T F
问答题
1. 二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？
此时的查找和插入算法的复杂性如何？
2. 何谓为多项式算法？如何将一 Monte Carlo 算法转化为 Las Vegas 算法？
3. 构造 AVL 树和 2-3 数的主要目的是什么？它们各自有什么样的查找和插入的效率？
4. 写出 0/1 背包问题的一个多项式等价(Polynomial Equivalent)的判定问题，并说明为什么它们是多项式
等价的。
5. 下面问题是否属于 NP 问题？为什么？
问题表述：给定图
G=(N , A)
中的两个点
p
、
q
，整数
c
和
t
，图
G
中每条边的长度
cij
及便利这条边
的时间
tij
，问图
G
中是否存在一条由
p
到
q
的路径，使得其长度大于
c
，且遍历时间小于
t
？
问答题：
1.（1）属于减可变规模的应用。（2）当关键字的个数等于二叉查找树的高度时表现出最差的效率。时间
复杂度为 O(n)。（3）此时查找和插入算法在最坏情况（查找当前序列的最大值或者插入最大值）的时间
复杂度都是 O(n)。
2.（1）伪多项式时间算法是 NPC 的一种，存在复杂度是关于实例规模和实例所有参数中绝对值最大数是
成多项式关系的算法。
（2）Monte Carlo 算法每次都能得到问题的解，但不保证所得解的准确性；Las Vegas 算法是每次不一定得
到问题的解，只要得到的解一定是正确的解；可以在 Monte Carlo 算法后加上一个验证算法，如果正确就
得到解，如果错误就不能生成问题的解，这样 Monte Carlo 算法便转化为了 Las Vegas 算法。
3. 构建 AVL 树和 2-3 树能够平衡左右子树的高度，减少树的层数，使得平均搜索效率更高。
插入和查找的时间复杂度均为 O(logn)。
4. 0/1 背包问题的一个多项式等价判定问题是整数划分问题。
5. 属于 NP 问题。
分治题
1. 写出一个求解下列问题的分治算法，推导其时间复杂性并与蛮力法相比较。
给定互不相等的 n个数的一个序列
a1, a2, … , an
，若其中某两个数
ai
和
aj
的关系为：
ai>aj
且
i<j
，
则称
ai
和
aj
是逆序的。要求计算该序列中的逆序个数，即具有逆序关系的元素对的总数目。
2.
A[1, … , n]
为一个整数序列，
A
中的整数
a
如果在
A
中出现次数多余
⌊n/2⌋
，那么
a
称为多数元素。
例如，在序列
1,3,2,3,3,4,3
中3是多数元素，因为出现了 4次，大于
⌊7/2⌋
。求 A的多数元素问题
的蛮力算法复杂性如何？设计一个具有变治思想的算法，提高蛮力算法的效率，写出伪代码并分析其
事件复杂性。
动态规划题
1. 某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。
时期（月） 需要量（产品单位）
1 2
2 3
3 2
4 4
已知：对每个月来讲，生产一批产品的固定成本费为3（千元），若不生成，则为零。每生产单
位产品的成本费为1（千元）。同时，在任何一个月内，生产能力所允许的最大生产批量为不超过 6
个单位。
又知：每单位产品的库存费用为每月0.5（千元），同时要求在第一个月开始之初，及在第四个月
末，均无产品库存。
问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用最低？写
出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。
2. 用动态规划方法手工求解以下问题
有8万元的投资可以投给3个过目，每个项目在不同筒子数额下（以万元为单位）的利润如下表
投资额
盈利
项目
01234567 8
项目 1 0 5 15 40 80 90 95 98 100
项目 2 0 5 15 40 60 70 73 74 75
项目 3 0 4 26 40 45 50 51 52 53
请安排投资计划，使总的利润最大。
写出你所设的状态变量、决策变量、状态转移方程与递推关系式和手工求解的详细步骤及结构。
分支定界题
1. 用分支定界法求解以下问题：
某部门欲建立联通分布于五个区的共50 个站点的有线通讯网络，每两个站点之间的线路敷设费用
由对成矩阵 C给出，任意两站点之间敷设线路需建设的地井数目由对称矩阵 U给出。
摘要：

判断题1.一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。2.NP完全问题比其他所有NP问题都要难。3.回溯法用深度优先法或广度优先法搜索状态空间树。4.在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。5.P类和NP类问题的关系用P⊂NP来表示是错误的。6.若近似算法A求解某极小化问题一实例的解为sa，且已知该问题的最优解为sa/3，则该近似算法的性能比为3。7.通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。8.若P2多项式时间转化为(polynomialtransformsto)P1，则P2至少与P1一样难。9.快速排...

展开>> 收起<<
算法设计与分析算法考试2011Algo——Answer可看性强点.docx

共6页,预览2页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：6 页 大小：36.21KB 格式：DOCX 时间：2025-01-13

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

高考理综 人际关系 力的合成 配电装置 动力学连接体 全宋诗作者索引 公务员考试
/ 6
评分 收藏
分享
立即下载 VIP免费下载
客服
关注