东华大学
2012~ 2013学年第一学期研究生期末考试试题参考答案
和评分标准
考试学院：计算机
考试专业：计算机科学与技术
考试课程名称：计算理论导引与算法复杂性
一、单项选择题（每空2分，本题共20分）
1. DFA和NFA的区别在于（B ）。
A、NFA能够识别的语言DFA不一定能够识别
B、对同一个输入串两者的计算过程不同
C、DFA能够识别的语言NFA不一定能够识别
D、NFA比DFA多拥有一个栈
2. 若一个语言A是非正则的，对于个给定的一个泵长p,若存在一个串s=xyz,|s|≥p，则
（A ）。
A、|y|可能大于等于0
B、xz∈A
C、xyyz∈A
D、|xy|不可能小于等于p
3. 下推自动机与图灵机的不同之处是( B )。
A、下推自动机比图灵机识别的语言多
B、下推自动机比图灵机识别的语言少
C、下推自动机识别的语言是不可判定
D、拥有一个无限的存储带
4. 如果一个语言是图灵可判定的，则（A）。
A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态
B、对于一个不属于它串s，不一定有一个判定器判定s
C、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态
D、对于一个不属于它串s，图灵机计算s时，一定不会停机
5. 一个集合在条件（ C ）下是不可数的。
A、该集合为无限集合
B、组成该集合的元素是实数
C、该集合的规模大于自然数集合的规模
D、该集合是一个有限的集合
6. 对于一个语言，（C ）的说法是正确的。
A、如果它属于Turing-recognizable，那么，一定属于EXPTIME
B、如果它是NP-hard，那么，一定属于NP
C、如果它是NP-complete，那么，一定属于NP
D、它一定能被图灵机识别
7. 如果A≤m B且B是可判定的，则（A）。
A、A也是可判定的
B、A不一定是可判定
C、A是不可判定的
D、A可判定否与B无关
8. 当（A）时，P=NP。
A、语言B是NP完全的且B∈P
B、计算速度快到一定峰值时
C、计算机内存达到无限
D、计算机性价比很高时
9. 对于SAT问题（A ）的说法是对的。
A、SAT问题不能用线性时间算法解决
B、SAT∉PSPACE
C、SAT∉NSPACE
D、SAT∉NP
10．如果B是PSPACE-hard，则（C）。
A、B∉NPSPACE
B、B∈P
C、B∈PSPACE
D、B一定是NP完全的
二、综合应用题(10分+10分+10分+10分+10分,本题共50分)
1．用5元组形式写出下面状态图对应的自动机。
参考答案：
1.Q ={q1, q2, q3, q4},
2. ∑={0,1},
3. δ is described as 0 1 ε
q1 {q1} {q1,q2} φ
q2 {q3} φ{q3}
q3 φ{q4} φ
q4 {q4} {q4}φ
4. q1 is the start state, and
5. F={q4}.
评分标准：5元组每一部分2分
2. 利用泵引理证明下述语言不是上下文无关的。
C ={a i b j c k |0≤i ≤j ≤k} 参考答案： 令p 为泵长
令s =a p b p c p =uvxyz ，
考虑v 和y 都含有一种符号和v 和y 含有一种符号以上符号 先判定uv 0xy 0z ∈C? 再判定uv 2xy 2z ∈C? 评分标准：每步2分
3. 证明：实数集合是不可数的。
参考答案：用反证法。
假设实数集可数，则可构造出如下映射：
然后，构造一个实数x ，它的第i 位小数与 f(i),1≤i ≤n 不同，推出矛盾。
评分标准：映射5分，实数5分
4.给定一个3cnf 公式∅=(x 1∨x 1∨x 2)∧(x 1∨x 2∨x 2)∧(x 1∨x 2∨x 2)，请把它规约为符合语言VERTEX-COVER 要求的图。
参考答案：
x 1
x 1
x 1
x 2
x 2
x 2
x 1
x 2
x 2
v 1 v 2
v 3 v 4
v 5
v 6 v 7 v 8
v 9
x 1
x 1
x 2 x 2
v 10 v 12 v 13
n f(n) 1 3.14159⋯ 2 55.55555⋯ 3 0.12345⋯ 4 0.50000⋯
x=0. 2 1 1 1
⋯ v 11
评分标准：画出上图得10分，画出图，但图上只标x没标出顶点V扣2分。
5.请把上述∅规约为符合语言SUBSET-SUM要求的一个表。
参考答案：
1 2 c1 c2 c3
Y1 1 0 1 0 0
Z1 1 0 0 1 1
Y2 1 1 0 1
Z2 1 0 1 0
G1 1 0 0
H1 1 0 0
G2 1 0
H2 1 0
G3 1
H3 1
T 1 1 3 3 3
评分标准：每列2分
三、完成下述操作（30分）
1.请根据正则表达式(0⋃1)*010构造一个NFA,要求写出构造步骤。
参考答案：
评分标准：“0”,“1”，“0⋃1”，“(0⋃1)*”，“010”各1分，“(0⋃1)*010”5分;如果没按书上的步骤且结果也能表示出该语言，则酌情给8-3分
2.设计一个判定语言RELPRIME={<x,y>|x与y互为素数}的图灵机，并用大“O”形式写出其时间复杂度。
参考答案：
E=“On input <x,y> where x and y are natural numbers in
binary:
1. Repeat until y=0:
2. Assign x←x mod y.
3. Exchange x and y.
4.Output x.”
R=“On input <x,y> where x and y are natural numbers in
binary:
1. Run E on <x,y>.
2. If the result is 1, accept. Otherwise, reject.”
时间复杂度O(n)
评分标准：写出E得5分，写出R和O(n)得5分；
如果只写出一个图灵机且步骤完整，能正确运行，且时间复杂度合理，则也可得10分；其他情况根据所写的图灵机酌情给8-3分。
3. 以你熟悉的形式写出一个解决团问题的算法，并用大“O”形式写出其时间复杂度和空间复杂度。
本题为个人发挥题，没有固定答案。
评分标准：1）算法书写规范易懂得2分；
2）算法书写规范易懂且正确得6分；
3）算法书写规范易懂、正确，时间复杂度和空间复杂度正确得10分；。