一、 填空题(本题 10 分,每空 1 分)
1、算法的复杂性是 的度量,是评价算法优劣的重要依据。
2、设 n 为正整数,利用大“O(·)”记号,将下列程序段的执行时间表示为 n 的函数,则下面
程序段的时间复杂度为 。
i=1; k=0;
while(i<n) { k=k+10*i;i++; }
3、计算机的资源最重要的是 和 资源。因而,算法的复杂性有 和 之分。
4、f(n)= 6×2
n
+n
2
,f(n)的渐进性态 f(n)= O( )
5、递归是指函数 或者 通过一些语句调用自身。
6、分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题,这些子问题
互相 且与原问题相同。
二、选择题(本题 20 分,每小题 2 分)
1、分支限界法与回溯法都是在问题的解空间树 T 上搜索问题的解,二者( )。
A.求解目标不同,搜索方式相同 B.求解目标不同,搜索方式也不同
C.求解目标相同,搜索方式不同 D.求解目标相同,搜索方式也相同
2、回溯法在解空间树 T 上的搜索方式是( )。
A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先
3、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( )。
A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题
4、以下关于判定问题难易处理的叙述中正确的是( )。
A.可以由多项式时间算法求解的问题是难处理的
B.需要超过多项式时间算法求解的问题是易处理的
C.可以由多项式时间算法求解的问题是易处理的
D.需要超过多项式时间算法求解的问题是不能处理的
5、设 f(N),g(N)是定义在正数集上的正函数,如果存在正的常数 C 和自然数 N0,使得当
N≥N0 时有 f(N)≤Cg(N),则称函数 f(N)当 N 充分大时有上界 g(N),记作 f(N)=O(g(N)),即
f(N)的阶( )g(N)的阶。
A.不高于 B.不低于 C.等价于 D.逼近
6、对于含有 n 个元素的子集树问题,最坏情况下其解空间的叶结点数目为( )。
A.n! B.2
n
C.2
n+1
-1 D. 2
n
-1
7、程序可以
不满足
以下( )特征
A.输入 B.输出 C.确定性 D.有限性
8、以下( )
不能
在线性时间完成排序
A.计数排序 B.基数排序 C.堆排序 D.桶排序
9、以下( )
不一定
得到问题的最优解
A.贪心算法 B.回溯算法 C.分支限界法 D.动态规划法
10、以下()不包括在图灵机结构中
A. 控制器 B. 读写磁头 C.计算器 D. 磁带
三、简答题(本题 20 分,每小题 5 分)
1、设有 n=2
k
个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:
① 每个选手必须与其他 n-1 名选手比赛各一次;
② 每个选手一天至多只能赛一次;
③ 循环赛要在最短时间内完成。
(1)如果 n=2
k
,循环赛最少需要进行几天;
1- 6
评论1