算法设计与分析算法考试2011Algo——Answer

VIP免费
2025-01-13 0 0 36.15KB 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. 二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？
此时的查找和插入算法的复杂性如何？
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. 写出一个求解下列问题的分治算法，推导其时间复杂性并与蛮力法相比较。
给定互不相等的 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给出。
设计一线路敷设总费用为最小的无环网络，使得徐建设的总地井数目不超过 UMAX，且需跨区敷
设的线路总数目不超过 DMAX(个站点所属的区由向量 D给出)。
1) 说明你是如何构造搜索树的。（要求是二叉搜索树）
2) 说明算法遍历搜索树的原则。（何时以及如何前进、分支、回溯、剪枝等等）
3) 你设计的分支定界算法的“界”是什么，他为什么是正确的和有效的？
4) 写出伪代码。
2. 用分支定界法求解以下问题：
A国与B国之间尚未直接通商。与 A国直接通商的有 20 个国家（C1, C2, …, C20）；与B国直接通
商的为另外 30 个国家（C21, C22, …, C50）。上述50 个国家之间并不是每两个国家都直接通商，任意
两国之间的贸易税率由对称矩阵 R给出，其中
∞
代表两国不能直接通商。
A国某公司与B国一公司欲通过某几个中间国家的公司完成一笔贸易，各个国家的进出口贸易通
关等手续所需办理时间由向量 T给出。请安排一中转贸易计划，使得该交易所产生的向各中转国缴纳
的税费最低，且整个交易能够在时间 t内完成。
1) 说明你是如何构造搜索树的。（要求是二叉搜索树）
2) 说明算法遍历搜索树的原则。（何时以及如何前进、分支、回溯、剪枝等等）
3) 你设计的分支定界算法的“界”是什么，他为什么是正确的和有效的？
4) 写出伪代码。
摘要：

判断题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.15KB 格式：DOCX 时间：2025-01-13

开通VIP享超值会员特权

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

作者详情

相关内容

更多

热门标签

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