算法分析与设计试卷 计算机科学系
需积分: 10 70 浏览量
2010-01-12
19:30:40
上传
评论
收藏 27KB DOC 举报
算法分析与设计试卷
2007 秋, 计算机科学系
姓名: 学号: 专业:
一. 翻译以下专业词汇: （21 分）
1. Dynamic programming
2. Feasible solution
3. Reduction
4. Prefix
5. Component design
6. Local replacement
7. Intractability
二. 请回答以下问题: （32 分）
1. 算法的时间复杂性是如何度量的?
2. 为什么说在算法的时间和空间关系上, 时间是决定性因素(dominant factor)?
3. 我们通常所说的有效 (efficient) 算法或实际可行算法是指何种算法?
4. 字符串的子串 (substring) 和 子序列 (subsequence) 有何不同?
5. 每一个 NP 问题都是难解的吗?
6. Turing 归约与 Karp 归约有何相同? 有何差异?
7. 一个最大化问题的近似比为 C 的相对近似算法可以给我们什么样的保证?
8. 如果从问题
1
多项式时间归约为问题问题
2
, 说明问题
1
比问题
2
难还是简单?
三. 对于任何正整数 n 以下算法计算 n!. 其时间复杂性几何? 是多项式时间的吗? （11 分）
m=1
For i=1 to n do
m=m*i
Endfor
Output m
四. （12 分）
1. 画出字符串 S=acabcac 的后缀树(suffix tree)及其隐含后缀树 (implicit suffix tree).
2. 构造一族 0,1 字符串, 使得其后缀树各边上所标记的子串长度之和的增长速度大于
(n), 这里的 n 为字符串的长度.
五. 关于 NP-Completeness： （12 分）
1. 写出通常证明一个问题 是 NP-complete 的过程.
资源评论
