填空题X 纠错

0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。

参考答案：

O(n*2n)；O(min{nc,2n})

进入题库练习
查答案就用赞题库小程序 还有拍照搜题 语音搜题 快来试试吧
无需下载 立即使用

你可能喜欢

填空题

以深度优先方式系统搜索问题解的算法称为（）。

参考答案：回溯法
点击查看答案进入题库练习

填空题

动态规划算法的基本思想是将待求解问题分解成若干（），先求解（），然后从这些（）的解得到原问题的解。

参考答案：子问题；子问题；子问题
点击查看答案进入题库练习

填空题

用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。

参考答案：一个（最优）解
点击查看答案进入题库练习

填空题

若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）

参考答案：{B，A，B，C，D}或{C，A，B，C，D}或{C，A，D，C，D｝
点击查看答案进入题库练习

填空题

某一问题可用动态规划算法求解的显著特征是（）。

参考答案：该问题具有最优子结构性质
点击查看答案进入题库练习

填空题

算法的复杂性有（）和（）之分，衡量一个算法好坏的标准是（）。

参考答案：时间复杂性；空间复杂性；时间复杂度高低
点击查看答案进入题库练习

填空题

一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：（）、（）、（）、（）、（）。

参考答案：确定性；有穷性；可行性；0个或多个输入；一个或多个输出
点击查看答案进入题库练习

问答题

用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。

参考答案：1.斜线标识的部分完成的功能为：提前更新bestw值；2.这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxload...
点击查看答案进入题库练习

问答题

已知非齐次递归方程：其中，b、c是常数，g（n）是n的某一个函数。则f（n）的非递归表达式为：现有Hanoi塔问题的递归方程为：，求h（n）的非递归表达式。

参考答案：

利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：

点击查看答案进入题库练习

问答题

求证：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。

参考答案：对于任意f1（n）∈O（f（n）），存在正常数c1和自然数n1，使得对所有n≧n1，有f1（n）≦c1f（n）...
点击查看答案进入题库练习
赞题库

赞题库-搜题找答案

（已有500万+用户使用）


  • 历年真题

  • 章节练习

  • 每日一练

  • 高频考题

  • 错题收藏

  • 在线模考

  • 提分密卷

  • 模拟试题

无需下载 立即使用
手机版 电脑版

版权所有©考试资料网(ppkao.com)All Rights Reserved