北语24春《算法与数据分析》作业4【标准答案】

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

试卷总分:100 得分:100

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

1.下面是贪心算法的根本要素的是

A.堆叠子疑问

B.结构最优解

C.贪心挑选性质

D.界说最优解



2.最大效益优先是下列哪项的一种查找方法

A.分支边界法

B.动态规划法

C.贪心法

D.回溯法



3.用分支限界法设计算法的第二步是

A.对于所给疑问，界说疑问的解空间（对解进行编码

B.断定易于查找的解空间结构（按树或图安排解）

C.以广度优先或以最小消耗（最大收益）优先的方法查找解空间

D.在查找过程顶用剪枝函数防止无效查找



4.下列算法中一般以自底向上的方法求解最优解的是

A.备忘录法

B.动态规划法

C.贪心法

D.回溯法



5.分支限界法与回溯法的一样点是

A.求解方针一样

B.查找方法一样

C.对拓展结点的拓展方法一样

D.都是一种在疑问的解空间树T中查找疑问解的算法



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



14.任何可用计算机求解的疑问所需的时刻都与其规划无关。



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



16.分支限界法首要有行列式（FIFO）分支限界法和优先行列式分支限界法。



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



18.疑问的最优子结构性质是该疑问不可以用动态规合算法或贪心算法求解的要害特征。



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



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