《算法设计与分析》练习题库及答案
(加粗红字体为2013下新增题目)
一、概念题：请解释下列术语。
1． 数据类型
2． 队列
3． 多项式复杂度
4． 满二叉树
5． NP-难度
6． 算法
7． SIMD(并行算法)
8． 连通图
9． 抽象数据类型
10． 指数复杂度
11． 递归
12． 完全二叉树
13． 状态空间树
14． NP-完全的
15． 算法与过程
16． 有向图与无向图
17． 树
18． P类问题
19.  确定的算法
20.  NP问题
21.  最小生成树
22.  动态规划
23.  数据结构
24. 排序
二、填空题
1. 简单递选分类过程中所需进行移动存储的操作次数较少，其最大值为___________。
2. 一组有序的n个数，采用逐个查算法查一给定的数是否出现在序列中，其算法复杂性为_____________。
3. 动态规划实际上是研究一类__________________的算法，其应用非常广泛。
4. BFS算法的中文名称是______________________算法。
5. 一棵树中              定义为该树的高度或深度。
6. 二分检索树要求树中所有结点中的元素满足        。
7. 比较树的结点由称为    和      的两种结点组成。
8. 外结点用一个    结点表示，在二分检索算法中它表示不成功检索的一种情况。
9. 由根到所有内部结点的距离之和称为    ;由根到所有外部结点的距离之和称为      .
10．max和min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作      次元素比较。
二叉树的基本性质11．如果用分治策略来设计分类算法，则可使最坏情况时间变为o(n logn)。这样的算法称为      。
12. 贪心算法可行的第一个基本要素是                      。
13. 当一个问题的最优解包含着它的子问题的最优解时，称此问题具有        性质。
14. 二路归并模式可以用        树来表示。
15. kruskal算法对于每一个无向连通图g产生一棵                。
16．因为如果有环，则可去掉这个环且不增加这条路径的长度(不含有负长度的环)。如果k是这条最短路径上的一个中间结点，那么—由i到k和由k到j的这两条子路径应分为别是由i到k和．由k到j的最短路径。否则，这条由i到j的路径就不是具有最小长度的路径。于是，      原理成立。
17.为了把动态规划应用于得到一棵最优二分检索树的问题，需要把构造这样的一棵树看成是一系列决策的结果，而且要能列出求取        序列的递推式.
18. 所谓可靠性设计最优化问题是在      的约束下，如何使系统的可靠性达到最优的问题。
19.货郎担问题是求取具有          的周游路线问题。
20.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：__________，__________，__________，__________，__________。
21.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是___________。
22.某一问题可用动态规划算法求解的显著特征是_____________________。
23.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。
三、程序填空题。
1．对二叉树的先根次序周游算法递归表示为：
        procedure  PREORDER(T)
          //T是一棵二元树。T中每个结点有三个信息段：ICHILD，，DATA，RCHILD//
              if T≠0 then call VISIT(T)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。