计算理论导引--研究生考试试卷格式

东华大学2010~2011学年第二学期研究生期末考试试题参考答案和评分标准考试学院：计算机考试专业：计算机科学与技术考试课程名称：计算理论导引与算法复杂性一、单项选择题（每空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|可能大于等于0B、xzAC、xyyzAD、|xy|不可能小于等于p3.下推自动机与图灵机的不同之处是(B)。A、下推自动机比图灵机识别的语言多B、下推自动机比图灵机识别的语言少C、下推自动机识别的语言是不可判定D、拥有一个无限的存储带4.如果一个语言是图灵可判定的，则（A）。A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态B、对于一个不属于它串s，不一定有一个判定器判定sC、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态D、对于一个不属于它串s，图灵机计算s时，一定不会停机5.一个集合在条件（C）下是不可数的。A、该集合为无限集合B、组成该集合的元素是实数C、该集合的规模大于自然数集合的规模D、该集合是一个有限的集合6.对于一个语言，（C）的说法是正确的。A、如果它属于Turing-recognizable，那么，一定属于EXPTIMEB、如果它是NP-hard，那么，一定属于NPC、如果它是NP-complete，那么，一定属于NPD、它一定能被图灵机识别7.如果AmB且B是可判定的，则（A）。A、A也是可判定的B、A不一定是可判定C、A是不可判定的D、A可判定否与B无关8.当（A）时，P=NP。A、语言B是NP完全的且BPB、计算速度快到一定峰值时C、计算机内存达到无限D、计算机性价比很高时9.对于SAT问题（A）的说法是对的。A、SAT问题不能用线性时间算法解决B、SATPSPACEC、SATNSPACED、SATNP10．如果B是PSPACE-hard，则（C）。A、BNPSPACEB、BPC、BPSPACED、B一定是NP完全的二、综合应用题(10分+10分+10分+10分+10分,本题共50分)1．用5元组形式写出下面状态图对应的自动机。参考答案：1.Q={q1,q2,q3,q4},2.={0,1},3.isdescribedas01q1{q1}{q1,q2}q2{q3}{q3}q3{q4}q4{q4}{q4}4.q1isthestartstate,and5.F={q4}.评分标准：5元组每一部分2分q10,1q2q310,110,q42.利用泵引理证明下述语言不是上下文无关的。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分。x1x1x1x2x2x2x1x2x2v1v2v3v4v5v6v7v8v9x1x1x2x2v10v12v13nf(n)13.14159255.5555530.1234540.50000x=0.2111v115.请把上述规约为符合语言SUBSET-SUM要求的一个表。参考答案：12c1c2c3Y110100Z110011Y21101Z21010G1100H1100G210H210G31H31T11333评分标准：每列2分三、完成下述操作（30分）1.请根据正则表达式(01)*010构造一个NFA,要求写出构造步骤。参考答案：00101(01)*010(01)*0101101001010010评分标准：“0”,“1”，“01”，“(01)*”，“010”各1分，“(01)*010”5分;如果没按书上的步骤且结果也能表示出该语言，则酌情给8-3分2.设计一个判定语言RELPRIME={x,y|x与y互为素数}的图灵机，并用大“O”形式写出其时间复杂度。参考答案：E=“Oninputx,ywherexandyarenaturalnumbersinbinary:1.Repeatuntily=0:2.Assignxxmody.3.Exchangexandy.4.Outputx.”R=“Oninputx,ywherexandyarenaturalnumbersinbinary:1.RunEonx,y.2.Iftheresultis1,accept.Otherwise,reject.”时间复杂度O(n)评分标准：写出E得5分，写出R和O(n)得5分；如果只写出一个图灵机且步骤完整，能正确运行，且时间复杂度合理，则也可得10分；其他情况根据所写的图灵机酌情给8-3分。3.以你熟悉的形式写出一个解决团问题的算法，并用大“O”形式写出其时间复杂度和空间复杂度。本题为个人发挥题，没有固定答案。评分标准：1）算法书写规范易懂得2分；2）算法书写规范易懂且正确得6分；3）算法书写规范易懂、正确，时间复杂度和空间复杂度正确得10分；