您可能感兴趣的试卷
你可能感兴趣的试题
有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为多少？
A.O（g（n））={f（n）∣存在正常数c和n0使得对所有n≧n0有：0≦f（n）≦cg（n）}
B.O（g（n））={f（n）∣存在正常数c和n0使得对所有n≧0有：0≦g（n）≦（n）}
C.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n0>0使得对所有n≧n0有：0≦f（n）<cg（n）}
D.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n0>0使得对所有n≧n0有：0≦cg（n）<f（n）}
A.O（g（n））={f（n）∣存在正常数c和n0使得对所有n≧n0有：0≦f（n）≦cg（n）}
B.O（g（n））={f（n）∣存在正常数c和n0使得对所有n≧0有：0≦g（n）≦（n）}
C.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n0>0使得对所有n≧n0有：0≦f（n）<cg（n）}
D.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n0>0使得对所有n≧n0有：0≦cg（n）<f（n）}
A.NP={L∣L是一个能在非多项式时间内被一台NDTM所接受的语言}
B.NP={L∣L是一个能在非多项式时间内被一台DTM所接受的语言}
C.NP={L∣L是一个能在多项式时间内被一台DTM所接受的语言}
D.NP={L∣L是一个能在多项式时间内被一台NDTM所接受的语言}
最新试题
何谓最优子结构性质？
若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）
写出最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree））。
求证：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。
举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是（）、（）、（）。
写出设计动态规划算法的主要步骤。
设S=｛X1，X2，···，Xn｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形：（1）在二叉搜索树的内结点中找到X=Xi，其概率为bi。（2）在二叉搜索树的叶结点中确定X∈（Xi，Xi+1），其概率为ai。在表示S的二叉搜索树T中，设存储元素Xi的结点深度为Ci；叶结点（Xi，Xi+1）的结点深度为di，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]=｛Xi，Xi+1，···，Xj｝最优值为m[i][j]，W[i][j]= ai-1+bi+···+bj+aj，则m[i][j]（1<=i<=j<=n）递归关系表达式为什么？
许多可以用贪心算法求解的问题一般具有2个重要的性质：（）性质和（）性质。
已知非齐次递归方程：其中，b、c是常数，g（n）是n的某一个函数。则f（n）的非递归表达式为：现有Hanoi塔问题的递归方程为：，求h（n）的非递归表达式。