算法分析复习题目及答案.pdfVIP

一。选择题

1、二分搜索算法是利用（A）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法

2、下列不是动态规划算法基本步骤的是（A）。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最

优解

7、衡量一个算法好坏的标准是（C）。

A运行速度快B占用空间少C时间复杂度低D代码短

8、以下不可以使用分治法求解的是（D）。

A棋盘覆盖问题B选择问题C归并排序D0/1背包问题

14．哈弗曼编码的贪心算法所需的计算时间为（B）。

nn

A、O（n2）B、O（nlogn）C、O（2）D、O（n）

18.下面是贪心算法的基本要素的是（C）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解

24.（D）是贪心算法与动态规划算法的共同点。

A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质

25.矩阵连乘问题的算法可由（B）设计实现。

A、分支界限算法B、动态规划算法C、贪心算法D、

回溯算法

27、Strassen矩阵乘法是利用（A）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法

29、使用分治法求解不需要满足的条件是（A）。

A子问题必须是一样的

B子问题不能够重复

C子问题的解可以合并

D原问题和子问题使用相同的方法解

30、下面问题（B）不能使用贪心法解决。

A单源最短路径问题BN皇后问题

C最小花费生成树问题D背包问题

31、下列算法中不能解决0/1背包问题的是（A）

A贪心法B动态规划C回溯法D分支限界法

34．实现合并排序利用的算法是（A）。

A、分治策略B、动态规划法C、贪心法D、回溯法

35．下列是动态规划算法基本要素的是（D）。

A、定义最优解B、构造最优解C、算出最优解D、子问题

重叠性质

36．下列算法中通常以自底向下的方式求解最优解的是（B）。

A、分治法B、动态规划法C、贪心法D、回溯法

38、合并排序算法是利用（A）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法

40、背包问题的贪心算法所需的计算时间为（B）

n