算法设计与分析算法考试算法题答案

VIP免费
2025-01-13 2 0 29.98KB 6 页 5.9玖币
侵权投诉
判断题
 一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。 对
  完全问题比其他所有  问题都要难。 错
 回溯法用深度优先法或广度优先法搜索状态空间树。 错
 在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。 错

P
类和
NP
类问题的关系用
P⊂NP
来表示是错误的。 错
 若近似算法 求解某极小化问题一实例的解为
sa
，且已知该问题的最优解为
sa/3
，则该近似算法的
性能比为 。 错
 通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。 对
 若 多项式时间转化为，则  至少与  一样难。 错
 快速排序算法的平均时间复杂度是
O(nlogn)
，使用随机化快速排序算法可以将平均时间复杂度降
得更低。 错
 基于比较的寻找数组
A[1, … , n]
中最大元素的问题下届是
Ω(n/3)
。
对

错
 若
f
(
n
)
=Ω
(
g
(
n
)
)
，
g
(
n
)
=Ω
(
h
(
n
)
)
，则
f
(
n
)
=Ω
(
h
(
n
)
)
对
 若
f
(
n
)
=O
(
g
(
n
)
)
，则
g
(
n
)
=Ω(f
(
n
)
)
对
 贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。 错
  ! 算法只要给出解就是正确的。 对
 一个完全多项式近似方案是一个近似方案
{Aε}
，其中每一个算法
Aε
在输入实例
I
的规模的多项式时
间内运行。 错
问答题
 二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？
此时的查找和插入算法的复杂性如何？
减治策略有 个主要的变种，包括减常量、减常数因子和减可变规模。二叉查找树
属于减可变规模变种的应用。当先后插入的关键字有序时，构成的二叉查找树蜕变为单
支树，树的深度等于 ，此时二叉查找树表现出最差的效率，查找和插入算法的时间效
率都属于 "。
 何谓为多项式算法？如何将一 # $ 算法转化为  ! 算法？
伪多项式算法：算法的时间复杂度是输入数据的多项表达式，但确实输入长度的指数时间算法
# $ 算法每次都能得到问题的解，但不保证所得解的准确性； ! 算法是每次不一定得
到问题的解，只要得到的解一定是正确的解；可以在 # $ 算法后加上一个验证算法，如果正
确就得到解，如果错误就不能生成问题的解，这样 # $ 算法便转化为了  ! 算法。
 构造  树和 % 数的主要目的是什么？它们各自有什么样的查找和插入的效率？
构建  树和 % 树能够平衡左右子树的高度，减少树的层数，使得平均搜索效率更高。
插入和查找的时间复杂度均为 &!。
 写出 ' 背包问题的一个多项式等价()*+ 的判定问题，并说明为什么它们是多项式
等价的。
判定问题 ,：从 #件物品中，取出若干件放在空间为 -的背包里，是否存在一个方案，
所获价值≥.？。每件物品的体积为-，-//-，与之相对应的价值为 0//
。
若判定问题 ,存在多项式时间的解法，则反复调用该算法就可以在多项式时间内解决
' 背包的优化问题。因而这个判定问题与原问题多项式等价。
 下面问题是否属于  问题？为什么？
问题表述：给定图
G=(N , A)
中的两个点
p
、
q
，整数
c
和
t
，图
G
中每条边的长度
cij
及便利这条边
的时间
tij
，问图
G
中是否存在一条由
p
到
q
的路径，使得其长度大于
c
，且遍历时间小于
t
？
这个问题属于  问题。因为若给出该问题的一个解，可以在多项式时间内检验这个解
的正确性。如给出一条由 到)的路径，可以在多项式时间内计算出它的长度及遍历时间，
然后分别与$和进行比较，从而可以判断这个解的对错。
分治题
 写出一个求解下列问题的分治算法，推导其时间复杂性并与蛮力法相比较。
给定互不相等的 个数的一个序列
a1, a2, … , an
，若其中某两个数
ai
和
aj
的关系为：
ai>aj
且
i<j
，
则称
ai
和
aj
是逆序的。要求计算该序列中的逆序个数，即具有逆序关系的元素对的总数目。
1*23
+4 ! 5607040
8
563
270924:3
1*23
;< =24>>9=2
8
56=596
8
51*::625::63
?
 
8
51*::6259::63
1*:24%:3''只增加这一句便可求逆序数
?
?
=24
8
;< =24
51*::625::63
?
 
8
;< 9=2
51*::6259::63
?
@23@=1*3@::
8
57::625@63
?
?
摘要：

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

展开>> 收起<<
算法设计与分析算法考试算法题答案.docx

共6页,预览2页

还剩页未读， 继续阅读

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

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

热门标签

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