(发老师-东华大学研究生考试试卷格式A4答案.docVIP

东 华 大 学 2012~ 2013学年第 一 学期研究生期 末 考试试题参考答案和评分标准 考试学院： 计算机 考试专业： 计算机科学与技术 考试课程名称： 计算理论导引与算法复杂性 一、单项选择题（每空2分，本题共0分） 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，不一定有一个判定器判定sC、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态 D、对于一个不属于它串s，图灵机计算s时，一定不会停机 5. 一个集合在条件（ ）。 AB、C、D、 6. 对于一个语言，（C ）的说法是正确的。 A、 B、C、D、?mB且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、SAT问题不能用线性时间算法解决 B、SAT?PSPACE C、SAT?NSPACE D、SAT?NP 10． 如果B是PSPACE-hard，则（）。 A、B?NPSPACE B、B?P C、B?PSPACE D、B一定是NP完全的二、综合应用题 (分+分+分+分本题共分) 参考答案： 1.Q ={q1, q2, q3, q4}, 2. S ={0,1}, 3. d is described as 0 1 e q1 {q1} {q1,q2} f q2 {q3} f {q3} q3 f {q4} f q4 {q4} {q4} f 4. q1 is the start state, and 5. F={q4}. 评分标准：5元组每一部分2分 2. 利用泵引理证明下述语言不是上下文无关的。 C={aibjck|0?i?j?k} 参考答案： 令p为泵长 令s=apbpcp =uvxyz， 考虑v和y都含有一种符号和v和y含有一种符号以上符号 先判定uv0xy0z?C? 再判定uv2xy2z?C? 评分标准：每步2分 3. 证明：实数集合是不可数的。 然后，构造一个实数x，它的第i位小数与 f(i),1￡i￡n 不同，推出矛盾。 评分标准：映射5分，实数5分 4.给定一个3cnf公式?=(x1úx1úx2)ù(x1úx2úx2)ù(x1úx2úx2)，请把它规约为语言VERTEX-COVER。评分标准：画出上图得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