资源描述：
《发老师-东华大学研究生考试试卷格式(a)附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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、
5、y
6、可能大于等于0B、xzÎAC、xyyzÎAD、
7、xy
8、不可能小于等于p3.下推自动机与图灵机的不同之处是(B)。A、下推自动机比图灵机识别的语言多B、下推自动机比图灵机识别的语言少C、下推自动机识别的语言是不可判定D、拥有一个无限的存储带4.如果一个语言是图灵可判定的，则（A）。A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态B、对于一个不属于它串s，不一定有一个判定器判定sC、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态聞創沟燴鐺險爱氇谴净。D、对于一个不属于它串s
9、，图灵机计算s时，一定不会停机5.一个集合在条件（C）下是不可数的。A、该集合为无限集合B、组成该集合的元素是实数C、该集合的规模大于自然数集合的规模D、该集合是一个有限的集合6.对于一个语言，（C）的说法是正确的。A、如果它属于Turing-recognizable，那么，一定属于EXPTIMEB、如果它是NP-hard，那么，一定属于NPC、如果它是NP-complete，那么，一定属于NPD、它一定能被图灵机识别7.如果A£mB且B是可判定的，则（A）。5/5A、A也是可判定的B、A不一定是可判定
10、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元组
11、形式写出下面状态图对应的自动机。q10,1q2q310,110,eq4参考答案：1.Q={q1,q2,q3,q4},2.S={0,1},3.disdescribedas01e残骛楼諍锩瀨濟溆塹籟。q1{q1}{q1,q2}fq2{q3}f{q3}q3f{q4}fq4{q4}{q4}f酽锕极額閉镇桧猪訣锥。4.q1isthestartstate,and5.F={q4}.评分标准：5元组每一部分2分5/52.利用泵引理证明下述语言不是上下文无关的。C={aibjck
12、0£i£j£k}参考答案：令p为泵长令s
13、=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¼彈贸摄尔霁毙攬砖卤庑。然后，构造一个实数x，它的第i位小数与f(i),1£i£n不同，推出矛盾。评分标准：映射5分，实数5分4.给定一个3cnf公式Æ=(x1Úx1Ú
14、x2)Ù(x1Úx2Úx2)Ù(x1Úx2Úx2)，请把它规约为符合语言VERTEX-COVER要求的图。謀荞抟箧飆鐸怼类蒋薔。参考答案：v11x1x1x1x2x2x2x1x2x2v1v2v3v4v5v6v7v8v9x1x1x2x2v10v12v135/5评分标准：画出上图得10分，画出图，但图上只标x没标出顶点V扣2分。厦礴恳蹒骈時盡继價骚。5.请把上述Æ规约为符合语言SUBSET-SUM要求的一个表。参考答案：12c1c2c3Y110100Z110011Y21101Z21010G1100H1100G
15、210H210G31H31T11333评分标准：每列2分三、完成下述操作（30分）1.请根据正则表达式(0È1)*010构造一个NFA,要求写出构造步骤。参考答案：0010È1(0È1)*010(0È1)*010110ee10eeeee010ee10eeee010eeeeee茕桢广鳓鯡选块网羈泪。5/5评分标准：“0”,“1”，“0È1”，“(0È1)*”，“010”各1分，“(0È1)*010”5分;如果没按书上的步骤且结果也能表示出该语
