1、東華大學(xué)20122013學(xué)年第一學(xué)期研究生期末考試一試題參照答案和評(píng)分標(biāo)準(zhǔn)考試學(xué)院：計(jì)算機(jī)考試專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)考試課程名稱：計(jì)算理論導(dǎo)引與算法復(fù)雜性一、單項(xiàng)選擇題（每空2分，本題共20分）DFA和NFA的差異在于（B）。A、NFA能夠識(shí)其他語(yǔ)言DFA不用然能夠鑒別B、對(duì)同一個(gè)輸入串兩者的計(jì)算過(guò)程不同樣C、DFA能夠識(shí)其他語(yǔ)言NFA不用然能夠鑒別D、NFA比DFA多擁有一個(gè)棧2.若一個(gè)語(yǔ)言A是非正則的，對(duì)于個(gè)給定的一個(gè)泵長(zhǎng)p,若存在一個(gè)串s=xyz,|s|p，則（A）。A、|y|可能大于等于0B、xzAC、xyyzAD、|xy|不能能小于等于p下推自動(dòng)機(jī)與圖靈機(jī)的不同樣之處是(B)。A、下

2、推自動(dòng)機(jī)比圖靈機(jī)識(shí)其他語(yǔ)言多B、下推自動(dòng)機(jī)比圖靈機(jī)識(shí)其他語(yǔ)言少C、下推自動(dòng)機(jī)識(shí)其他語(yǔ)言是不能判斷D、擁有一個(gè)無(wú)量的儲(chǔ)藏帶若是一個(gè)語(yǔ)言是圖靈可判斷的，則（A）。A、對(duì)于一個(gè)不屬于它串s，圖靈機(jī)計(jì)算s時(shí)，必然能夠到達(dá)拒絕狀態(tài)B、對(duì)于一個(gè)不屬于它串s，不用然有一個(gè)判斷器判斷sC、對(duì)于一個(gè)不屬于它串s，圖靈機(jī)計(jì)算s時(shí)，有可能進(jìn)入無(wú)量循環(huán)狀態(tài)D、對(duì)于一個(gè)不屬于它串s，圖靈機(jī)計(jì)算s時(shí)，必然不會(huì)停機(jī)5.一個(gè)會(huì)集在條件（C）下是不能數(shù)的。、該會(huì)集為無(wú)量會(huì)集B、組成該會(huì)集的元素是實(shí)數(shù)C、該會(huì)集的規(guī)模大于自然數(shù)會(huì)集的規(guī)模D、該會(huì)集是一個(gè)有限的會(huì)集對(duì)于一個(gè)語(yǔ)言，（C）的說(shuō)法是正確的。A、若是它屬于Turing-re

3、cognizable，那么，必然屬于EXPTIMEB、若是它是NP-hard，那么，必然屬于NPC、若是它是NP-complete，那么，必然屬于NP、它必然能被圖靈機(jī)鑒別1/5若是AmB且B是可判斷的，則（A）。A、A也是可判斷的B、A不用然是可判斷C、A是不能判斷的D、A可判斷否與B沒(méi)關(guān)當(dāng)（A）時(shí)，P=NP。A、語(yǔ)言B是NP完滿的且BPB、計(jì)算速度快到必然峰值時(shí)C、計(jì)算機(jī)內(nèi)存達(dá)到無(wú)量D、計(jì)算機(jī)性價(jià)比很高時(shí)對(duì)于SAT問(wèn)題（A）的說(shuō)法是對(duì)的。A、SAT問(wèn)題不能夠用線性時(shí)間算法解決B、SATPSPACEC、SATNSPACED、SATNP10若是B是PSPACE-hard，則（C）。A、BNPS

4、PACEB、BPC、BPSPACED、B必然是NP完滿的二、綜合應(yīng)用題(10分+10分+10分+10分+10分,本題共50分)1用5元組形式寫出下面狀態(tài)圖對(duì)應(yīng)的自動(dòng)機(jī)。0,10,1q11q20,q31q4參照答案：1.Q=q1,q2,q3,q4,2.=0,1,3.isdescribedas01q1q1q1,q2q2q3q3q3q4q4q4q44.q1isthestartstate,and5.F=q4.評(píng)分標(biāo)準(zhǔn)：5元組每一部分2分2/5利用泵引理證明下述語(yǔ)言不是上下文沒(méi)關(guān)的。C=aibjck|0ijk參照答案：令p為泵長(zhǎng)令s=apbpcp=uvxyz，考慮v和y都含有一種符號(hào)和v和y含有一種符號(hào)

5、以上符號(hào)00先判斷uvxyzC?再判斷uv2xy2zC?證明：實(shí)數(shù)會(huì)集是不能數(shù)的。參照答案：用反證法。假設(shè)實(shí)數(shù)集可數(shù)，則可構(gòu)造出以下照射：nf(n)13.14159255.5555530.1234540.50000 x=0.2111爾后，構(gòu)造一個(gè)實(shí)數(shù)x，它的第i位小數(shù)與f(i),1in不同樣，推出矛盾。評(píng)分標(biāo)準(zhǔn)：照射5分，實(shí)數(shù)5分4.給定一個(gè)3cnf公式=(x1x1x2)(x1x2x2)(x1x2x2)，請(qǐng)把它規(guī)約為吻合語(yǔ)言VERTEX-COVER要求的圖。參照答案：v10 x1x1v11x2x2v13v12v4v1x1x1x1v7v9v6v8x1x2v3v5x2x2x2x2v23/5評(píng)分標(biāo)準(zhǔn)

6、：畫出上圖得10分，畫出圖，但圖上只標(biāo)x沒(méi)標(biāo)出極點(diǎn)V扣2分。5.請(qǐng)把上述規(guī)約為吻合語(yǔ)言SUBSET-SUM要求的一個(gè)表。參照答案：12c1c2c3Y110100Z110011Y21101Z21010G1100H1100G210H210G31H31T11333評(píng)分標(biāo)準(zhǔn)：每列2分三、完成下述操作（30分）1.請(qǐng)依照正則表達(dá)式(01)*010構(gòu)造一個(gè)NFA,要求寫出構(gòu)造步驟。參照答案：001100110(01)*10100100(01)*01014/5010評(píng)分標(biāo)準(zhǔn)：“0”,“1”，“01”，“(01)*”，“010”各1分，“(01)*010”5分;若是沒(méi)按書上的步驟且結(jié)果也能表示出該語(yǔ)言，則酌情

7、給8-3分2.設(shè)計(jì)一個(gè)判斷語(yǔ)言RELPRIME=|x與y互為素?cái)?shù)的圖靈機(jī)，并用大“O”形式寫出其時(shí)間復(fù)雜度。參照答案：E=“Oninputwherexandyarenaturalnumbersinbinary:1.Repeatuntily=0:2.Assignxxmody.Exchangexandy.Outputx.”R=“Oninputwherexandyarenaturalnumbersinbinary:RunEon.Iftheresultis1,accept.Otherwise,reject.”時(shí)間復(fù)雜度O(n)評(píng)分標(biāo)準(zhǔn)：寫出E得5分，寫出R和O(n)得5分；若是只寫出一個(gè)圖靈機(jī)且步驟完滿，能正確運(yùn)行，且時(shí)間復(fù)雜度合理，則也可得10分；其他情況依照所寫的圖靈機(jī)酌情給8-3分。3.以你熟悉的形式寫出一個(gè)解決團(tuán)問(wèn)題的