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

-A.可計算性

-B.復雜性

-C.可判定性

-D.不可解性

**參考答案**:A

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

2.以下哪種模型是圖靈等價的？

-A.有限狀態(tài)自動機

-B.下推自動機

-C.圖靈機

-D.線性有界自動機

**參考答案**:C

**解析**:圖靈機是圖靈等價的模型，能夠模擬所有其他計算模型。

3.以下哪個問題屬于不可判定問題？

-A.停機問題

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

-C.最短路徑問題

-D.排序問題

**參考答案**:A

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

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

-A.可計算性

-B.復雜性

-C.可判定性

-D.不可解性

**參考答案**:B

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

5.以下哪個問題屬于P類問題？

-A.停機問題

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

-C.旅行商問題

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

**參考答案**:B

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

6.以下哪個問題屬于NP類問題？

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

-B.最短路徑問題

-C.旅行商問題

-D.排序問題

**參考答案**:C

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

7.以下哪個模型不是圖靈等價的？

-A.圖靈機

-B.λ演算

-C.有限狀態(tài)自動機

-D.遞歸函數(shù)

**參考答案**:C

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

8.以下哪個問題屬于可判定問題？

-A.停機問題

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

-C.旅行商問題

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

**參考答案**:B

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

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

-A.可計算性

-B.復雜性

-C.可判定性

-D.不可解性

**參考答案**:D

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

10.以下哪個問題屬于NP完全問題？

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

-B.最短路徑問題

-C.旅行商問題

-D.排序問題

**參考答案**:C

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

11.以下哪個模型可以接受上下文無關語言？

-A.有限狀態(tài)自動機

-B.下推自動機

-C.圖靈機

-D.線性有界自動機

**參考答案**:B

**解析**:下推自動機可以接受上下文無關語言，因為它具有棧結(jié)構(gòu)。

12.以下哪個問題屬于NP難問題？

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

-B.最短路徑問題

-C.旅行商問題

-D.排序問題

**參考答案**:C

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

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

-A.有限狀態(tài)自動機

-B.下推自動機

-C.圖靈機

-D.線性有界自動機

**參考答案**:A

**解析**:有限狀態(tài)自動機可以接受正則語言，因為它沒有棧結(jié)構(gòu)。

14.以下哪個問題屬于不可計算問題？

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

-B.停機問題

-C.旅行商問題

-D.排序問題

**參考答案**:B

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

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

-A.可計算性

-B.復雜性

-C.可判定性

-D.不可解性

**參考答案**:C

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

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

-A.有限狀態(tài)自動機

-B.下推自動機

-C.圖靈機

-D.線性有界自動機

**參考答案**:D

**解析**:線性有界自動機可以接受上下文敏感語言，因為它的存儲空間受輸入長度限制。

17.以下哪個問題屬于P類問題？

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

-B.旅行商問題

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

-D.停機問題

**參考答案**:A

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

18.以下哪個問題屬于NP類問題？

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

-B.最短路徑問題

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

-D.排序問題

**參考答案**:C

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

19.以下哪個模型是圖靈等價的？

-A.有限狀態(tài)自動機

-B.下推自動機

-C.圖靈機

-D.線性有界自動機

**參考答案**:C

**解析**:圖靈機是圖靈等價的模型，能夠模擬所有其他計算模型。

20.以下哪個問題屬于不可判定問題？

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

-B.停機問題

-C.旅行商問題

-D.排序問題

**參考答案**:B

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

21.以下哪個問題屬于可判定問題？

-A.停機問題

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

-C.給定一個圖靈機，判斷其是否會在所有輸入上停機

-D.給定一個圖靈機，判斷其是否會在某個輸入上停機

**參考答案**:B

**解析**:可判定問題是指在有限步驟內(nèi)能夠通過算法得到答案的問題。給定一個圖靈機和輸入，判斷其是否會在有限步內(nèi)停機是一個可判定問題，因為可以通過模擬圖靈機的運行來判斷。

22.關于遞歸可枚舉語言，以下哪個說法是正確的？

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

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

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

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

**參考答案**:B

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

23.以下哪個問題是不可判定的？

-A.給定兩個正則表達式，判斷它們是否等價

-B.給定一個上下文無關文法，判斷它是否生成空語言

-C.給定一個圖靈機，判斷它是否會在所有輸入上停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上停機

**參考答案**:C

**解析**:給定一個圖靈機，判斷它是否會在所有輸入上停機是一個不可判定問題，因為這是停機問題的推廣，而停機問題是不可判定的。

24.關于圖靈機的停機問題，以下哪個說法是正確的？

-A.停機問題是一個可判定問題

-B.停機問題是一個半可判定問題

-C.停機問題是一個不可判定問題

-D.停機問題是一個遞歸問題

**參考答案**:C

**解析**:停機問題是一個不可判定問題，因為不存在一個通用的算法能夠判斷任意圖靈機在給定輸入上是否會停機。

25.以下哪個語言是遞歸的？

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

-B.所有圖靈機在某個輸入上停機的語言

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

-D.所有圖靈機在某個輸入上不停機的語言

**參考答案**:A

**解析**:所有圖靈機在所有輸入上停機的語言是遞歸的，因為可以構(gòu)造一個圖靈機來模擬輸入圖靈機的運行，并在有限步驟內(nèi)判斷它是否停機。

26.關于遞歸可枚舉語言，以下哪個說法是錯誤的？

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

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

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

-D.遞歸可枚舉語言是圖靈可識別語言

**參考答案**:B

**解析**:遞歸可枚舉語言的補集不一定是遞歸可枚舉語言，也不一定是遞歸語言。因此，選項B是錯誤的。

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

-A.給定一個圖靈機，判斷它是否會在所有輸入上停機

-B.給定一個圖靈機，判斷它是否會在某個輸入上停機

-C.給定一個圖靈機，判斷它是否會在所有輸入上不停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上不停機

**參考答案**:B

**解析**:給定一個圖靈機，判斷它是否會在某個輸入上停機是一個遞歸可枚舉問題，因為可以構(gòu)造一個圖靈機來模擬輸入圖靈機的運行，并在它停機時輸出“是”。

28.關于遞歸語言，以下哪個說法是正確的？

-A.遞歸語言的補集不一定是遞歸語言

-B.遞歸語言的補集一定是遞歸語言

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

-D.遞歸語言一定是上下文無關語言

**參考答案**:B

**解析**:遞歸語言的補集一定是遞歸語言，因為遞歸語言的定義要求其補集也是遞歸語言。

29.以下哪個問題是遞歸的？

-A.給定一個圖靈機，判斷它是否會在所有輸入上停機

-B.給定一個圖靈機，判斷它是否會在某個輸入上停機

-C.給定一個圖靈機，判斷它是否會在所有輸入上不停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上不停機

**參考答案**:A

**解析**:給定一個圖靈機，判斷它是否會在所有輸入上停機是一個遞歸問題，因為可以構(gòu)造一個圖靈機來模擬輸入圖靈機的運行，并在有限步驟內(nèi)判斷它是否停機。

30.關于遞歸可枚舉語言，以下哪個說法是正確的？

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

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

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

-D.遞歸可枚舉語言的補集一定是上下文無關語言

**參考答案**:B

**解析**:遞歸可枚舉語言的補集不一定是遞歸可枚舉語言，也不一定是遞歸語言或上下文無關語言。

31.以下哪個問題是不可判定的？

-A.給定一個上下文無關文法，判斷它是否生成空語言

-B.給定一個上下文無關文法，判斷它是否生成所有字符串

-C.給定一個圖靈機，判斷它是否會在所有輸入上停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上停機

**參考答案**:C

**解析**:給定一個圖靈機，判斷它是否會在所有輸入上停機是一個不可判定問題，因為這是停機問題的推廣，而停機問題是不可判定的。

32.關于遞歸語言，以下哪個說法是錯誤的？

-A.遞歸語言的補集一定是遞歸語言

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

-C.遞歸語言不一定是上下文無關語言

-D.遞歸語言一定是上下文無關語言

**參考答案**:D

**解析**:遞歸語言不一定是上下文無關語言，因為遞歸語言的定義與上下文無關語言的定義不同。

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

-A.給定一個圖靈機，判斷它是否會在所有輸入上停機

-B.給定一個圖靈機，判斷它是否會在某個輸入上停機

-C.給定一個圖靈機，判斷它是否會在所有輸入上不停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上不停機

**參考答案**:B

**解析**:給定一個圖靈機，判斷它是否會在某個輸入上停機是一個遞歸可枚舉問題，因為可以構(gòu)造一個圖靈機來模擬輸入圖靈機的運行，并在它停機時輸出“是”。

34.關于遞歸可枚舉語言，以下哪個說法是正確的？

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

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

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

-D.遞歸可枚舉語言的補集一定是上下文無關語言

**參考答案**:B

**解析**:遞歸可枚舉語言的補集不一定是遞歸可枚舉語言，也不一定是遞歸語言或上下文無關語言。

35.以下哪個問題是遞歸的？

-A.給定一個圖靈機，判斷它是否會在所有輸入上停機

-B.給定一個圖靈機，判斷它是否會在某個輸入上停機

-C.給定一個圖靈機，判斷它是否會在所有輸入上不停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上不停機

**參考答案**:A

**解析**:給定一個圖靈機，判斷它是否會在所有輸入上停機是一個遞歸問題，因為可以構(gòu)造一個圖靈機來模擬輸入圖靈機的運行，并在有限步驟內(nèi)判斷它是否停機。

36.關于遞歸語言，以下哪個說法是正確的？

-A.遞歸語言的補集不一定是遞歸語言

-B.遞歸語言的補集一定是遞歸語言

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

-D.遞歸語言一定是上下文無關語言

**參考答案**:B

**解析**:遞歸語言的補集一定是遞歸語言，因為遞歸語言的定義要求其補集也是遞歸語言。

37.以下哪個問題是不可判定的？

-A.給定一個上下文無關文法，判斷它是否生成空語言

-B.給定一個上下文無關文法，判斷它是否生成所有字符串

-C.給定一個圖靈機，判斷它是否會在所有輸入上停機

-D.給定一個圖靈機，判斷它是否會在某個輸入上停機