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

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

试卷总分:100 得分:100

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

1.鄙人列算法中得到的解未必正确的是

A.蒙特卡罗算法

B.拉斯维加斯算法

C.舍伍德算法

D.数值概率算法



2.0-1背包疑问的回溯算法所需的计算时刻为

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）



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

A.分治战略

B.动态规划法

C.贪心法

D.回溯法



4.以下不可以以运用分治法求解的是

A.棋盘掩盖疑问

B.挑选疑问

C.归并排序

D.0/1背包疑问



5.优先行列式分支限界法选择拓展结点的准则是

A.领先先出

B.后进先出

C.结点的优先级

D.随机



6.下列哪一种算法不是随机化算法

A.蒙特卡罗算法

B..拉斯维加斯算法

C..动态规合算法

D..舍伍德算法



7.回溯法解游览售货员疑问时的解空间树是

A.子集树

B.摆放树

C.深度优先生成树

D.广度优先生成树



8.下列随机算法中运转时有时分成功有时分失利的是

A.数值概率算法

B.舍伍德算法

C.拉斯维加斯算法

D.蒙特卡罗算法



9.分支限界法解游览售货员疑问时，活结点表的安排方式是

A.最小堆

B.最大堆

C.栈

D.数组



10.运用分治法求解不需求满意的条件是

A.子疑问有必要是相同的

B.子疑问不可以重复

C.子疑问的解能够兼并

D.原疑问和子疑问运用一样的方法解



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

11.算法的杂乱性没有时刻杂乱性和空间杂乱性之分



12.拉斯维加斯算法找到的解纷歧定是正确解



13.分支限界法与回溯法的求解方针一样



14.处理0/1背包疑问能够运用动态规划、回溯法和分支限界法，其间不需求排序的是动态规划，需求排序的是回溯法，分支限界法



15.设计动态规合算法的首要过程不包含依据计算最优值时得到的信息，结构最优解



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



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



18.使用概率的性质计算近似值的随机算法是数值概率算法，运转时以必定的概率得到正确解的随机算法是蒙特卡罗算法



19.运用回溯法进行状况空间树裁剪分支时一般有两个规范：束缚条件和方针函数的界，N皇后疑问和0/1背包疑问正巧是两种不一样的类型，其间一起运用束缚条件和方针函数的界进行裁剪的是0/1背包疑问，只运用束缚条件进行裁剪的是N皇后疑问



20.分治法的根本思想时将一个规划为n的疑问分化为k个规划较小的子疑问，这些子疑问相互独立且与原疑问一样。递归地解这些子疑问，然后将各个子疑问的解兼并得到原疑问的解