《算法设计与分析》复习题.doc资源-CSDN文库

版权申诉

48 浏览量 2022-05-08 19:16:46 上传评论收藏 144KB DOC 举报

资源推荐

资源详情

资源评论

填空

1．直接或间接地调用自身的算法称为递归。

2．算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。

3．以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。

4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保

存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度

为 h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。

5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题

结论的，叫做算法方案方案；另一类是不能通过若干个步骤直截了当地得出结论，而是

需要反复验证才能解决的，叫做启发式方案方案。

6．算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。

7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3 个基本

计算模型是随机存取机、随机存取存储程序机、图灵机。

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

9．计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空

间之分。

10．贪心算法总是做出在当前看来最优的选择。也就是说贪心算法并不从整体最优考虑，

它所做出的选择只是在某种意义上的局部最优解。

11．许多可以用贪心算法求解的问题一般具有 2 个重要的性质：最优子结构的性质和

贪心选择的性质。

12．常见的两种分支限界法为队列式和优先队列式。

13．解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是回溯

法，不需要排序的是动态规划和分支限界法。

14．f ( n ) = 6 × 2

n

+ n

2

，f(n)的渐进性态 f ( n ) = O (  2^n  )。

15．对于含有 n 个元素的排列树问题，最好情况下计算时间复杂性为，最坏情况下计

算时间复杂性为 n! 。

16．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的

一个上界。

17．回溯法的求解过程，即在问题的解空间树中，按深度优先策略从根结点出发搜索

解空间树。

18．分支限界法的求解过程，即在问题的解空间树中，按广度优先策略从根结点出发

搜索解空间树。

19．多项式的上界为 2^ n 。

20．用分支限界法解布线问题时，对空间树搜索结束的标志是活结点表为空。

21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，

N 皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的

界进行裁剪的是 0-1

背包，只使用约束条件进行裁剪的是 N

皇后。

简答

1. 算法分析的目的是什么？

分析算的的效率以求改进

第 1 页共 8 页

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

内容反馈

版权申诉

老帽爬新坡

粉丝: 83
资源: 2万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip