22秋《算法与数据分析》作业_2

22秋《算法与数据分析》作业_2

动态规划算法的基本要素为

1.最优子结构性质与贪心选择性质

2.重叠子问题性质与贪心选择性质

3.最优子结构性质与重叠子问题性质

4.预排序与递归调用

下面哪种函数是回溯法中为避免无效搜索采取的策略

0.递归函数

1..剪枝函数

2.。随机数函数

3..搜索函数

回溯法的效率不依赖于下列哪些因素

0.满足显约束的值的个数

1..计算约束函数的时间

2..计算限界函数的时间

3..确定解空间的时间

下列哪一种算法是随机化算法

0.贪心算法

1..回溯法

2..动态规划算法

3..舍伍德算法

分支限界法与回溯法的相同点是

0.求解目标相同

1.搜索方式相同

2.对扩展结点的扩展方式相同

3.都是一种在问题的解空间树T中搜索问题解的算法

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

0.蒙特卡罗算法

1..拉斯维加斯算法

2..动态规划算法

3..舍伍德算法

衡量一个算法好坏的标准是

0.运行速度快

1.占用空间少

2.时间复杂度低

3.代码短

回溯法搜索状态空间树是按照什么的顺序

0.中序遍历

1.广度优先遍历

2.深度优先遍历

3.层次优先遍历

Strassen矩阵乘法是利用什么实现的算法

0.分治策略

1.动态规划法

2.贪心法

3.回溯法

背包问题的贪心算法所需的计算时间为

0.O（n2n）

1.O（nlogn）

2.O（2n）

3.O（n）

蒙特卡罗算法得到的解未必正确

1.对

2.错

贪心选择性质是贪心算法可行的第一个基本要素，但不是贪心算法与动态规划算法的主要区别

1.对

2.错

回溯法在问题的解空间树中，按扩展结点优先策略，从根结点出发搜索解空间树

1.对

2.错

动态规划法通常以自底向下的方式求解最优解

1.对

2.错

数值概率算法运行时有时候成功有时候失败

1.对

2.错

使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是N皇后问题

1.对

2.错

备忘录方法是动态规划法的变形

1.对

2.错

问题的最优子结构性质是该问题不可用动态规划算法或贪心算法求解的关键特征。

1.对

2.错

常见的分支限界法的算法框架有3种

1.对

2.错

广度优先是回溯法的一搜索方式

1.对

2.错

实现循环赛日程表利用的算法是分治策略

1.对

2.错

贪心选择性质是贪心算法与动态规划算法的共同点

1.对

2.错

二分搜索算法是利用动态规划法实现的算法

1.对

2.错

算法的“确定性”指的是组成算法的每条指令是清晰的，有歧义的。

1.对

2.错

分治法与动态规划法的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的

1.对

2.错