北语22秋《算法与数据分析》作业2【标准答案】

20秋《算法与数据剖析》作业2

试卷总分:100 得分:100

一、单选题 (共 10 道试题,共 50 分)

1.选用贪心算法的最优装载疑问的首要计算量在于将集装箱依其分量从小到大排序，故算法的时刻杂乱度为

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）



2.鄙人列算法中有时找不到疑问解的是

A.蒙特卡罗算法

B.拉斯维加斯算法

C.舍伍德算法

D.数值概率算法



3.最长公共子序列算法使用的算法是

A.分支边界法

B.动态规划法

C.贪心法

D.回溯法



4.下列算法中一般以深度优先方法系统查找疑问解的是

A.备忘录法

B.动态规划法

C.贪心法

D.回溯法



5.Strassen矩阵乘法是使用啥完成的算法

A.分治战略

B.动态规划法

C.贪心法

D.回溯法



6.以深度优先方法系统查找疑问解的算法称为

A.分支边界算法

B.概率算法

C.贪心算法

D.回溯算法



7.下列算法中不能处理0/1背包疑问的是

A.贪心法

B.动态规划

C.回溯法

D.分支限界法



8.备忘录方法是那种算法的变形

A.分治法

B.动态规划法

C.贪心法

D.回溯法



9.下面关于NP疑问说法正确的是

A.NP疑问都是不可以能处理的疑问

B.P类疑问包括在NP类疑问中

C.NP彻底疑问是P类疑问的子集

D.NP类疑问包括在P类疑问中



10.舍伍德算法是以下的哪一种

A.分支边界算法

B.概率算法

C.贪心算法

D.回溯算法



二、判别题 (共 10 道试题,共 50 分)

11.贪心算法的根本要素是贪心挑选质和最优子结构性质



12.设计动态规合算法的首要过程有5步



13.贪心挑选性质是贪心算法可行的榜首个根本要素，但不是贪心算法与动态规合算法的首要差异



14.回溯法是一种既带有系统性又带有跳动性的查找算法。



15.从分治法的一般设计形式能够看出，用它设计出的程序一般是递归算法。



16.算法是由若干条指令构成的有穷序列，且要满意输入、输出、断定性和有限性四条性质。



17.分治法与动态规划法的不一样点是：合适于用动态规划法求解的疑问，经分化得到的子疑问通常不是相互独立的。而用分治法求解的疑问，经分化得到的子疑问通常是相互独立的



18.舍伍德算法总能求得疑问的一个解。



19.疾速排序算法的功能取决于区分的对称性



20.回溯法查找解空间树时，常用的两种剪枝函数为束缚函数和限界函数。