2019 算法导论(中国矿业大学) 最新满分章节测试答案
本答案对应课程为:点我自动跳转查看
本课程起止时间为:2019-09-20到2019-10-21
本篇答案更新状态:已完结
【作业】6 分支限界法 分支限界法作业
1、 问题:简述分支限界支法的搜索策略
评分规则: 【 分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] 。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。
】
2、 问题:假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。
评分规则: 【 
】
3、 问题:•在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。
评分规则: 【 
下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。
】
4、 问题:
给定一个图G,使用优先队列式分支限界法求解这个图的最大团。
评分规则: 【 
】
【作业】1 算法概述 算法概述作业
小提示:本节包含奇怪的同名章节内容
1、 问题:请解释大O表示法 、大W 表示法、q表示法的区别。
评分规则: 【 
】
2、 问题:某厂商A新研制的处理器运行速度为B公司同类产品的81倍。对于计算复杂性分别为
的各算法，若用B公司的计算机在1小时内能解输入规模为的问题，那么用A公司的计算机在同样的时间内分别能解输入规模为多大的问题？
评分规则: 【 1求解正确无误
】
3、 问题:
评分规则: 【 
】
【作业】2 分治与递归 分治与递归作业题
小提示:本节包含奇怪的同名章节内容
1、 问题:请分析对比不同排序算法的时间复杂度（至少对比分5种以上的排序算法）
评分规则: 【 1、内容阐述正确2、逻辑结构清晰
】
2、 问题:一个递归算法的递归公式如下： 
请分析该算法的时间复杂度。
评分规则: 【 求解过程清晰、无误
】
3、 问题:假设数组A包含有n个不同正整数（已经按升序排列），给定正整数L和U（L
】
4、 问题:假设K是含有m个不同数的数组，请设计算法找出该数组的中位数。（1）给出描述算法的伪代码。（2）分析并给出该算法的时间复杂性上界O。
评分规则: 【 1、可执行正确的代码2、代码逻辑结构清晰，执行效率高，输出结果正确
】
5、 问题:现有n枚外观相同的硬币和一架天平，已知硬币中有一枚重量较轻的硬币是假币，要求设计一个高效的算法来检测出这枚假币。请写出分治法求解该问题的详细步骤，并分析其时间复杂性。
评分规则: 【 
1、内容阐述正确2、逻辑结构清晰
】
6、 问题:一个递归算法的递归公式如下： 请分析该算法的时间复杂度。
评分规则: 【 
】
本文章不含期末不含主观题！！
本文章不含期末不含主观题！！
支付后可长期查看
有疑问请添加客服QQ 2356025045反馈
如遇卡顿看不了请换个浏览器即可打开
请看清楚了再购买哦，电子资源购买后不支持退款哦
