PAGE1.以下哪個(gè)概念描述了一個(gè)問題可以在有限步驟內(nèi)被解決？

-A.可計(jì)算性

-B.復(fù)雜性

-C.可判定性

-D.不可解性

**參考答案**:A

**解析**:可計(jì)算性描述了一個(gè)問題是否可以通過某種計(jì)算模型在有限步驟內(nèi)被解決。

2.以下哪種模型是圖靈等價(jià)的？

-A.有限狀態(tài)自動(dòng)機(jī)

-B.下推自動(dòng)機(jī)

-C.圖靈機(jī)

-D.線性有界自動(dòng)機(jī)

**參考答案**:C

**解析**:圖靈機(jī)是圖靈等價(jià)的模型，能夠模擬所有其他計(jì)算模型。

3.以下哪個(gè)問題屬于不可判定問題？

-A.停機(jī)問題

-B.最大公約數(shù)問題

-C.最短路徑問題

-D.排序問題

**參考答案**:A

**解析**:停機(jī)問題是不可判定問題，無法通過算法在所有情況下判斷程序是否會(huì)停止。

4.以下哪個(gè)概念描述了問題的求解效率？

-A.可計(jì)算性

-B.復(fù)雜性

-C.可判定性

-D.不可解性

**參考答案**:B

**解析**:復(fù)雜性描述了問題的求解效率，通常用時(shí)間和空間復(fù)雜度來衡量。

5.以下哪個(gè)問題屬于P類問題？

-A.停機(jī)問題

-B.最大公約數(shù)問題

-C.旅行商問題

-D.圖同構(gòu)問題

**參考答案**:B

**解析**:最大公約數(shù)問題可以在多項(xiàng)式時(shí)間內(nèi)解決，屬于P類問題。

6.以下哪個(gè)問題屬于NP類問題？

-A.最大公約數(shù)問題

-B.最短路徑問題

-C.旅行商問題

-D.排序問題

**參考答案**:C

**解析**:旅行商問題目前沒有已知的多項(xiàng)式時(shí)間算法，但可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證解，屬于NP類問題。

7.以下哪個(gè)模型不是圖靈等價(jià)的？

-A.圖靈機(jī)

-B.λ演算

-C.有限狀態(tài)自動(dòng)機(jī)

-D.遞歸函數(shù)

**參考答案**:C

**解析**:有限狀態(tài)自動(dòng)機(jī)的計(jì)算能力有限，無法模擬圖靈機(jī)，因此不是圖靈等價(jià)的。

8.以下哪個(gè)問題屬于可判定問題？

-A.停機(jī)問題

-B.最大公約數(shù)問題

-C.旅行商問題

-D.圖同構(gòu)問題

**參考答案**:B

**解析**:最大公約數(shù)問題可以通過算法在有限步驟內(nèi)解決，屬于可判定問題。

9.以下哪個(gè)概念描述了一個(gè)問題無法通過算法解決？

-A.可計(jì)算性

-B.復(fù)雜性

-C.可判定性

-D.不可解性

**參考答案**:D

**解析**:不可解性描述了一個(gè)問題無法通過任何算法解決。

10.以下哪個(gè)問題屬于NP完全問題？

-A.最大公約數(shù)問題

-B.最短路徑問題

-C.旅行商問題

-D.排序問題

**參考答案**:C

**解析**:旅行商問題屬于NP完全問題，即任何NP問題都可以在多項(xiàng)式時(shí)間內(nèi)歸約到它。

11.以下哪個(gè)模型可以接受上下文無關(guān)語言？

-A.有限狀態(tài)自動(dòng)機(jī)

-B.下推自動(dòng)機(jī)

-C.圖靈機(jī)

-D.線性有界自動(dòng)機(jī)

**參考答案**:B

**解析**:下推自動(dòng)機(jī)可以接受上下文無關(guān)語言，因?yàn)樗哂袟＝Y(jié)構(gòu)。

12.以下哪個(gè)問題屬于NP難問題？

-A.最大公約數(shù)問題

-B.最短路徑問題

-C.旅行商問題

-D.排序問題

**參考答案**:C

**解析**:旅行商問題屬于NP難問題，即它至少與NP問題一樣難。

13.以下哪個(gè)模型可以接受正則語言？

-A.有限狀態(tài)自動(dòng)機(jī)

-B.下推自動(dòng)機(jī)

-C.圖靈機(jī)

-D.線性有界自動(dòng)機(jī)

**參考答案**:A

**解析**:有限狀態(tài)自動(dòng)機(jī)可以接受正則語言，因?yàn)樗鼪]有棧結(jié)構(gòu)。

14.以下哪個(gè)問題屬于不可計(jì)算問題？

-A.最大公約數(shù)問題

-B.停機(jī)問題

-C.旅行商問題

-D.排序問題

**參考答案**:B

**解析**:停機(jī)問題是不可計(jì)算問題，無法通過算法在所有情況下解決。

15.以下哪個(gè)概念描述了問題的可解性？

-A.可計(jì)算性

-B.復(fù)雜性

-C.可判定性

-D.不可解性

**參考答案**:C

**解析**:可判定性描述了一個(gè)問題是否可以通過算法在有限步驟內(nèi)解決。

16.以下哪個(gè)模型可以接受上下文敏感語言？

-A.有限狀態(tài)自動(dòng)機(jī)

-B.下推自動(dòng)機(jī)

-C.圖靈機(jī)

-D.線性有界自動(dòng)機(jī)

**參考答案**:D

**解析**:線性有界自動(dòng)機(jī)可以接受上下文敏感語言，因?yàn)樗拇鎯?chǔ)空間受輸入長度限制。

17.以下哪個(gè)問題屬于P類問題？

-A.最大公約數(shù)問題

-B.旅行商問題

-C.圖同構(gòu)問題

-D.停機(jī)問題

**參考答案**:A

**解析**:最大公約數(shù)問題可以在多項(xiàng)式時(shí)間內(nèi)解決，屬于P類問題。

18.以下哪個(gè)問題屬于NP類問題？

-A.最大公約數(shù)問題

-B.最短路徑問題

-C.圖同構(gòu)問題

-D.排序問題

**參考答案**:C

**解析**:圖同構(gòu)問題目前沒有已知的多項(xiàng)式時(shí)間算法，但可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證解，屬于NP類問題。

19.以下哪個(gè)模型是圖靈等價(jià)的？

-A.有限狀態(tài)自動(dòng)機(jī)

-B.下推自動(dòng)機(jī)

-C.圖靈機(jī)

-D.線性有界自動(dòng)機(jī)

**參考答案**:C

**解析**:圖靈機(jī)是圖靈等價(jià)的模型，能夠模擬所有其他計(jì)算模型。

20.以下哪個(gè)問題屬于不可判定問題？

-A.最大公約數(shù)問題

-B.停機(jī)問題

-C.旅行商問題

-D.排序問題

**參考答案**:B

**解析**:停機(jī)問題是不可判定問題，無法通過算法在所有情況下判斷程序是否會(huì)停止。

21.以下哪個(gè)問題屬于可判定問題？

-A.停機(jī)問題

-B.給定一個(gè)圖靈機(jī)和輸入，判斷其是否會(huì)在有限步內(nèi)停機(jī)

-C.給定一個(gè)圖靈機(jī)，判斷其是否會(huì)在所有輸入上停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷其是否會(huì)在某個(gè)輸入上停機(jī)

**參考答案**:B

**解析**:可判定問題是指在有限步驟內(nèi)能夠通過算法得到答案的問題。給定一個(gè)圖靈機(jī)和輸入，判斷其是否會(huì)在有限步內(nèi)停機(jī)是一個(gè)可判定問題，因?yàn)榭梢酝ㄟ^模擬圖靈機(jī)的運(yùn)行來判斷。

22.關(guān)于遞歸可枚舉語言，以下哪個(gè)說法是正確的？

-A.所有遞歸可枚舉語言都是遞歸語言

-B.所有遞歸語言都是遞歸可枚舉語言

-C.遞歸可枚舉語言的補(bǔ)集也是遞歸可枚舉語言

-D.遞歸可枚舉語言的補(bǔ)集一定是遞歸語言

**參考答案**:B

**解析**:遞歸語言是遞歸可枚舉語言的子集，因此所有遞歸語言都是遞歸可枚舉語言。遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言，也不一定是遞歸語言。

23.以下哪個(gè)問題是不可判定的？

-A.給定兩個(gè)正則表達(dá)式，判斷它們是否等價(jià)

-B.給定一個(gè)上下文無關(guān)文法，判斷它是否生成空語言

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)

**參考答案**:C

**解析**:給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)是一個(gè)不可判定問題，因?yàn)檫@是停機(jī)問題的推廣，而停機(jī)問題是不可判定的。

24.關(guān)于圖靈機(jī)的停機(jī)問題，以下哪個(gè)說法是正確的？

-A.停機(jī)問題是一個(gè)可判定問題

-B.停機(jī)問題是一個(gè)半可判定問題

-C.停機(jī)問題是一個(gè)不可判定問題

-D.停機(jī)問題是一個(gè)遞歸問題

**參考答案**:C

**解析**:停機(jī)問題是一個(gè)不可判定問題，因?yàn)椴淮嬖谝粋€(gè)通用的算法能夠判斷任意圖靈機(jī)在給定輸入上是否會(huì)停機(jī)。

25.以下哪個(gè)語言是遞歸的？

-A.所有圖靈機(jī)在所有輸入上停機(jī)的語言

-B.所有圖靈機(jī)在某個(gè)輸入上停機(jī)的語言

-C.所有圖靈機(jī)在所有輸入上不停機(jī)的語言

-D.所有圖靈機(jī)在某個(gè)輸入上不停機(jī)的語言

**參考答案**:A

**解析**:所有圖靈機(jī)在所有輸入上停機(jī)的語言是遞歸的，因?yàn)榭梢詷?gòu)造一個(gè)圖靈機(jī)來模擬輸入圖靈機(jī)的運(yùn)行，并在有限步驟內(nèi)判斷它是否停機(jī)。

26.關(guān)于遞歸可枚舉語言，以下哪個(gè)說法是錯(cuò)誤的？

-A.遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言

-B.遞歸可枚舉語言的補(bǔ)集一定是遞歸語言

-C.遞歸語言是遞歸可枚舉語言的子集

-D.遞歸可枚舉語言是圖靈可識(shí)別語言

**參考答案**:B

**解析**:遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言，也不一定是遞歸語言。因此，選項(xiàng)B是錯(cuò)誤的。

27.以下哪個(gè)問題是遞歸可枚舉的？

-A.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-B.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上不停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上不停機(jī)

**參考答案**:B

**解析**:給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)是一個(gè)遞歸可枚舉問題，因?yàn)榭梢詷?gòu)造一個(gè)圖靈機(jī)來模擬輸入圖靈機(jī)的運(yùn)行，并在它停機(jī)時(shí)輸出“是”。

28.關(guān)于遞歸語言，以下哪個(gè)說法是正確的？

-A.遞歸語言的補(bǔ)集不一定是遞歸語言

-B.遞歸語言的補(bǔ)集一定是遞歸語言

-C.遞歸語言不一定是遞歸可枚舉語言

-D.遞歸語言一定是上下文無關(guān)語言

**參考答案**:B

**解析**:遞歸語言的補(bǔ)集一定是遞歸語言，因?yàn)檫f歸語言的定義要求其補(bǔ)集也是遞歸語言。

29.以下哪個(gè)問題是遞歸的？

-A.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-B.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上不停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上不停機(jī)

**參考答案**:A

**解析**:給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)是一個(gè)遞歸問題，因?yàn)榭梢詷?gòu)造一個(gè)圖靈機(jī)來模擬輸入圖靈機(jī)的運(yùn)行，并在有限步驟內(nèi)判斷它是否停機(jī)。

30.關(guān)于遞歸可枚舉語言，以下哪個(gè)說法是正確的？

-A.遞歸可枚舉語言的補(bǔ)集一定是遞歸可枚舉語言

-B.遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言

-C.遞歸可枚舉語言的補(bǔ)集一定是遞歸語言

-D.遞歸可枚舉語言的補(bǔ)集一定是上下文無關(guān)語言

**參考答案**:B

**解析**:遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言，也不一定是遞歸語言或上下文無關(guān)語言。

31.以下哪個(gè)問題是不可判定的？

-A.給定一個(gè)上下文無關(guān)文法，判斷它是否生成空語言

-B.給定一個(gè)上下文無關(guān)文法，判斷它是否生成所有字符串

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)

**參考答案**:C

**解析**:給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)是一個(gè)不可判定問題，因?yàn)檫@是停機(jī)問題的推廣，而停機(jī)問題是不可判定的。

32.關(guān)于遞歸語言，以下哪個(gè)說法是錯(cuò)誤的？

-A.遞歸語言的補(bǔ)集一定是遞歸語言

-B.遞歸語言一定是遞歸可枚舉語言

-C.遞歸語言不一定是上下文無關(guān)語言

-D.遞歸語言一定是上下文無關(guān)語言

**參考答案**:D

**解析**:遞歸語言不一定是上下文無關(guān)語言，因?yàn)檫f歸語言的定義與上下文無關(guān)語言的定義不同。

33.以下哪個(gè)問題是遞歸可枚舉的？

-A.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-B.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上不停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上不停機(jī)

**參考答案**:B

**解析**:給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)是一個(gè)遞歸可枚舉問題，因?yàn)榭梢詷?gòu)造一個(gè)圖靈機(jī)來模擬輸入圖靈機(jī)的運(yùn)行，并在它停機(jī)時(shí)輸出“是”。

34.關(guān)于遞歸可枚舉語言，以下哪個(gè)說法是正確的？

-A.遞歸可枚舉語言的補(bǔ)集一定是遞歸可枚舉語言

-B.遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言

-C.遞歸可枚舉語言的補(bǔ)集一定是遞歸語言

-D.遞歸可枚舉語言的補(bǔ)集一定是上下文無關(guān)語言

**參考答案**:B

**解析**:遞歸可枚舉語言的補(bǔ)集不一定是遞歸可枚舉語言，也不一定是遞歸語言或上下文無關(guān)語言。

35.以下哪個(gè)問題是遞歸的？

-A.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-B.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上不停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上不停機(jī)

**參考答案**:A

**解析**:給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)是一個(gè)遞歸問題，因?yàn)榭梢詷?gòu)造一個(gè)圖靈機(jī)來模擬輸入圖靈機(jī)的運(yùn)行，并在有限步驟內(nèi)判斷它是否停機(jī)。

36.關(guān)于遞歸語言，以下哪個(gè)說法是正確的？

-A.遞歸語言的補(bǔ)集不一定是遞歸語言

-B.遞歸語言的補(bǔ)集一定是遞歸語言

-C.遞歸語言不一定是遞歸可枚舉語言

-D.遞歸語言一定是上下文無關(guān)語言

**參考答案**:B

**解析**:遞歸語言的補(bǔ)集一定是遞歸語言，因?yàn)檫f歸語言的定義要求其補(bǔ)集也是遞歸語言。

37.以下哪個(gè)問題是不可判定的？

-A.給定一個(gè)上下文無關(guān)文法，判斷它是否生成空語言

-B.給定一個(gè)上下文無關(guān)文法，判斷它是否生成所有字符串

-C.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在所有輸入上停機(jī)

-D.給定一個(gè)圖靈機(jī)，判斷它是否會(huì)在某個(gè)輸入上停機(jī)