c语言背包问题_背包问题贪心算法_背包问题 贪心算法(2)

12.实现循环赛日程表利用的算法是（ A ）。

A 分治策略 B 动态规划法

C 贪心法 D 回溯法

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

A 子问题必须是一样的 B 子问题不能够重复

C 子问题的解可以合并 D 原问题和子问题使用相同的方法解

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

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

15.以下( C )不能不能性时间完成排序

A 计数排序 B 基数排序 C 堆排序 D 桶排序

16.下列哪一种算法是随机化算法（ D ）

A 贪心算法 B 回溯法 C 动态规划算法 D 舍伍德算法

17. 下列算法中通常以自底向上的方式求解最优解的（ B ）。 A 分治法 B 动态规划法 C 贪心法 D 回溯法

18. n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 ( A ) 说法不正确？A

A 让水桶大的人先打水，可以使得每个人排队时间之和最小

B 让水桶小的人先打水，可以使得每个人排队时间之和最小

C 让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水

D 若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样

19.哈弗曼编码的贪心算法所需的计算时间为 ( B )。

A O(n2n) B O(nlogn) C O(2n) D O(n)

20.下面关于NP问题说确的是(B )

A NP问题都是不可能解决的问题

B P类问题包含在NP类问题中

C NP完全问题是P类问题的子集

D NP类问题包含在P类问题中

21.背包问题贪心算法所需的计算时间为( B ) 

A O(n2n) B O(nlogn) C O(2n) D O(n)

22.背包问题的回溯算法所需的计算时间为（ A ） 

A O(n2n) B O(nlogn) C O(2n) D O(n)

23.采用最大效益优先搜索方式的算法是（ A ） 

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

24. 在的个数是 （ A ）

A ( 4k – 1）/3 B 2k /3 C 4k D 2k

25. 下列随机算法中运行时有时候成功有时候失败的是（C ）

A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法

26. 实现大整数的乘法是利用的算法（ C ）。

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

二、填空题

1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。

2.矩阵连乘问题的算法可由 动态规划 设计实现。

3.从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。

4.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。

5.快速排序算法的性能取决于 划分的对称性 。

6.使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（ logn ）。

三、解答题

1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度

2. 分析最有搜索二叉树和0/1背包的时间复杂度

3. 试用动态规划算法实现最大子矩阵和问题：求n×m矩阵A的一个子矩阵，使其各元素之各为最大

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23877-2.html