资源描述：
《发老师-东华大学研究生考试试卷格式(a4)答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、东华大学2012~2013学年第一学期研究生期末考试试题参考答案和评分标准考试学院：计算机考试专业：计算机科学与技术考试课程名称：计算理论导引与算法复杂性一、单项选择题（每空2分，本题共20分）1.DFA和NFA的区别在于（B）。A、NFA能够识别的语言DFA不一定能够识别B、对同一个输入串两者的计算过程不同C、DFA能够识别的语言NFA不一定能够识别D、NFA比DFA多拥有一个栈2.若一个语言A是非正则的，对于个给定的一个泵长p,若存在一个串s=xyz,
2、s
3、³p，则（A）。A、
4、y
5、可能大于等于0B、xzÎAC、xyyzÎAD、
6、xy
7、不可能小于等
8、于p3.下推自动机与图灵机的不同之处是(B)。A、下推自动机比图灵机识别的语言多B、下推自动机比图灵机识别的语言少C、下推自动机识别的语言是不可判定D、拥有一个无限的存储带4.如果一个语言是图灵可判定的，则（A）。A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态B、对于一个不属于它串s，不一定有一个判定器判定sC、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态D、对于一个不属于它串s，图灵机计算s时，一定不会停机5.一个集合在条件（C）下是不可数的。A、该集合为无限集合B、组成该集合的元素是实数C、该集合的规模大于自然数集合
9、的规模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）的说法是对
10、的。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元组形式写出下面状态图对应的自动机。q10,1q2q310,110,eq4参考答案：1.Q={q1,q2,q3,q4},2.S={0,1},3.disdescribedas01eq1{q1}{q1,q2}fq2{q3}f{q3}q3f{q4}fq4{q4
11、}{q4}f4.q1isthestartstate,and5.F={q4}.评分标准：5元组每一部分2分2.利用泵引理证明下述语言不是上下文无关的。C={aibjck
12、0£i£j£k}参考答案：令p为泵长令s=apbpcp=uvxyz，考虑v和y都含有一种符号和v和y含有一种符号以上符号先判定uv0xy0zÎC?再判定uv2xy2zÎC?评分标准：每步2分3.证明：实数集合是不可数的。参考答案：用反证法。假设实数集可数，则可构造出如下映射：nf(n)13.14159¼255.55555¼30.12345¼40.50000¼¼¼x=0.2111¼然后，构
13、造一个实数x，它的第i位小数与f(i),1£i£n不同，推出矛盾。评分标准：映射5分，实数5分4.给定一个3cnf公式Æ=(x1Úx1Úx2)Ù(x1Úx2Úx2)Ù(x1Úx2Úx2)，请把它规约为符合语言VERTEX-COVER要求的图。参考答案：v11x1x1x1x2x2x2x1x2x2v1v2v3v4v5v6v7v8v9x1x1x2x2v10v12v13评分标准：画出上图得10分，画出图，但图上只标x没标出顶点V扣2分。5.请把上述Æ规约为符合语言SUBSET-SUM要求的一个表。参考答案：12c1c2c3Y110100Z110011Y2110
14、1Z21010G1100H1100G210H210G31H31T11333评分标准：每列2分三、完成下述操作（30分）1.请根据正则表达式(0È1)*010构造一个NFA,要求写出构造步骤。参考答案：0010È1(0È1)*010(0È1)*010110ee10eeeee010ee10eeee010eeeeee评分标准：“0”,“1”，“0È1”，“(0È1)*”，“010”各1分，“(0È1)*010”5分;如果没按书上的步骤且结果也能表示出该语言，则酌情给8-3分2.设计一个判定语言RELPRIME={
15、x与y互为素数}的图灵机，并用大“
16、O”形式写出其时间复杂度。参考答案：E=“Oninputwherexandyaren
