算法分析与设计试卷
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 的过程.
guopengjiu
- 粉丝: 0
- 资源: 1
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
评论2