計(jì)算理論導(dǎo)引

立華人學(xué)

2022?2022學(xué)年第二學(xué)期討論生期末考試試題參考答案

和評(píng)分標(biāo)準(zhǔn)

考試學(xué)院：計(jì)算機(jī)_____________

考試專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)

考試課程名稱：計(jì)算理論導(dǎo)引與算法簡單性

一、單項(xiàng)選擇題（每空2分，本題共20分）

1.DFA和NFA的區(qū)分在于（B）。

A、NFA能夠識(shí)別的語言DFA不肯定能夠識(shí)別B、對(duì)同一個(gè)輸入串兩者的計(jì)算過程不同

C、DFA能夠識(shí)別的語言NFA不肯定能夠識(shí)別D、NFA比DFA多擁有一個(gè)棧

2.若一個(gè)語言A是非正則的，對(duì)于個(gè)給定的一個(gè)泵長。,若存在一個(gè)串s="yz,|s|2"則

（A）?

A、|y|可能大于等于0

B、xz&A

C>xyyzeA

D、|母|不行能小于等于p

3.下推自動(dòng)機(jī)與圖靈機(jī)的不同之處是（B）。

A、下推自動(dòng)機(jī)比圖靈機(jī)識(shí)別的語言多B、下推自動(dòng)機(jī)比圖靈機(jī)識(shí)別的語言少

C、下推自動(dòng)機(jī)識(shí)別的語言是不行判定D、擁有一個(gè)無限的存儲(chǔ)帶

4.假如一個(gè)語言是圖靈可判定的，則（A）。

A、對(duì)于一個(gè)不屬于它串s,圖靈機(jī)計(jì)算s時(shí)，肯定能夠到達(dá)拒絕狀態(tài)

B、對(duì)于一個(gè)不屬于它串s,不肯定有一個(gè)判定器判定s

C、對(duì)于一個(gè)不屬于它串s,圖靈機(jī)計(jì)算s時(shí)，有可能進(jìn)入無限循環(huán)狀態(tài)

D、對(duì)于一個(gè)不屬于它串s,圖靈機(jī)計(jì)算s時(shí)，肯定不會(huì)停機(jī)

5.一個(gè)集合在條件（C）下是不行數(shù)的。

A、該集合為無限集合

B、組成該集合的元素是實(shí)數(shù)

C、該集合的規(guī)模大于自然數(shù)集合的規(guī)模

D、該集合是一個(gè)有限的集合

6.對(duì)于一個(gè)語言，（C）的說法是正確的。

A、假如它屬于Turing-recognizable,那么，肯定屬于EXPTIME

B、假如它是NP-hard,那么，肯定屬于NP

C、假如它是NP-complete,那么，肯定屬于NP

D、它肯定能被圖靈機(jī)識(shí)別

7.假如44mB且8是可判定的，則（A）。

A、A也是可判定的

B、A不肯定是可判定

C、4是不行判定的

D、A可判定否與B無關(guān)

8.當(dāng)（A）時(shí)，P=NP。

A、語言B是NP完全的且BwP

B、計(jì)算速度快到肯定峰值時(shí)

C、計(jì)算機(jī)內(nèi)存達(dá)到無限

D、計(jì)算機(jī)性價(jià)比很高時(shí)

9.對(duì)于SAT問題（A）的說法是對(duì)的。

A、SAT問題不能用線性時(shí)間算法解決

B、SAT/PSPACE

C、S4T任NSPACE

D、SATgNP

10.假如8是PSPACE-hard,貝U（C）。

A、版NPSPACE

B、BeP

C、BePSPACE

D、8肯定是NP完全的

二、綜合應(yīng)用題（10分+10分+10分+10分+10分,本題共50分）

1.用5元組形式寫出下面狀態(tài)圖對(duì)應(yīng)的自動(dòng)機(jī)。

參考答案：

LQ={ql,q2,q3,q4},

2.￡={0,1},

3.bisdescribedas01e

qi{ql}{ql,q2}

q2{q3}。3}

q36{q4},

q4{q4}{q4}。

4.qlisthestartstate,and

5.F={q4}.

評(píng)分標(biāo)準(zhǔn)：5元組每一部分2分

2.采用泵引理證明下述語言不是上下文無關(guān)的。

C={aibick|O<i<j<k}

參考答案：

令P為泵長

s=apbpcp=uvxyz>

考慮v和y都含有一種符號(hào)和v和y含有一種符號(hào)以上符號(hào)

先判定11網(wǎng)收€6

再判定uyxyhwCl

評(píng)分標(biāo)準(zhǔn)：每步2分

3.證明：實(shí)數(shù)集合是不行數(shù)的。

參考答案：用反證法。假設(shè)實(shí)數(shù)集可數(shù)，則可構(gòu)造出如下映射:

n—Un)

13.14159...

255.55555…

0.12345…

0.50000...

x=0.2111…

然后，構(gòu)造一個(gè)實(shí)數(shù)X,它的第i位小數(shù)與f(i),l<i<n不同，推出沖突。

評(píng)分標(biāo)準(zhǔn)：映射5分，實(shí)數(shù)5分

4.給定一個(gè)3cnf公式0=(xlv_dvx2)人(xR逐/郎2Vx2),請(qǐng)把它規(guī)約為符合語言

VERTEX-COVER要求的圖。

參考答案：

評(píng)分標(biāo)準(zhǔn)：畫出上圖得10分，畫出圖，但圖上只標(biāo)x沒標(biāo)出頂點(diǎn)V扣2分。

5.請(qǐng)把上述。規(guī)約為符合語言SUBSET-SUM要求的一個(gè)表。

參考答案：

12clc2c3

Y110100

Z110011

Y21101

Z21010

G1100

H1100

G210

H210

G31

H31

T11333

評(píng)分標(biāo)準(zhǔn)：M

列2分

三、完成下述操作(30分)

1.請(qǐng)依據(jù)正則表達(dá)式(03)*010構(gòu)造一個(gè)NFA,要求寫出構(gòu)造步驟。

參考答案：

(03)*010

￡￡

評(píng)分標(biāo)準(zhǔn)：“0”，“1”，“Oul”，“（Oul）*"，“010”各1分，“（0ul）*010”5分;假

如沒按書上的步驟且結(jié)果也能表示出該語言，則酌情給8-3分

2.設(shè)計(jì)一個(gè)判定語言R及所｛氣），4與y互為素?cái)?shù)｝的圖靈機(jī)，并用大“O”形式寫出

其時(shí)間簡單度。

參考答案：

E="Oninput<x,y>wherexandyarenaturalnumbersin

binary:

1.Repeatuntilj=0:

2.Assignx<-xmody.

3.Exchangexandy.

4.Output

R="Oninput<x,j>wherexandyarenaturalnumbersin

binary:

1.RunEon<x,y>.

2.Iftheresultis1,accept.Otherwise,reject.^

時(shí)間簡單度O（n）

評(píng)分標(biāo)準(zhǔn)：寫出E得5分，寫出R和O（n）得5分；

假如只寫出一個(gè)圖靈機(jī)且步驟完整，能正確運(yùn)行，且時(shí)間簡單度合理，則也可得10分；其

他狀況依據(jù)所寫的圖靈機(jī)酌情給8-3分