公務員考試-邏輯推理模擬題-邏輯與計算-可計算性與計算復雜性

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

-A.停機問題

-B.最短路徑問題

-C.最大流問題

-D.二分查找問題

**參考答案**:A

**解析**:停機問題是經(jīng)典的不可判定問題，即不存在一個通用算法能夠判斷任意程序在給定輸入下是否會停止。

2.以下哪個復雜度類包含所有可以在多項式時間內(nèi)驗證解的問題？

-A.P

-B.NP

-C.EXP

-D.PSPACE

**參考答案**:B

**解析**:NP類包含所有可以在多項式時間內(nèi)驗證解的問題，即給定一個解，可以在多項式時間內(nèi)驗證其正確性。

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

-A.旅行商問題

-B.素數(shù)判定問題

-C.背包問題

-D.圖著色問題

**參考答案**:B

**解析**:素數(shù)判定問題可以在多項式時間內(nèi)解決，因此屬于P類問題。

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

-A.二分查找問題

-B.旅行商問題

-C.線性規(guī)劃問題

-D.最短路徑問題

**參考答案**:B

**解析**:旅行商問題是經(jīng)典的NP完全問題，即它既屬于NP類，又具有NP類問題的完全性。

5.以下哪個復雜度類包含所有可以在指數(shù)時間內(nèi)解決的問題？

-A.P

-B.NP

-C.EXP

-D.PSPACE

**參考答案**:C

**解析**:EXP類包含所有可以在指數(shù)時間內(nèi)解決的問題，即問題的時間復雜度為O(2^poly(n))。

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

-A.停機問題

-B.旅行商問題

-C.布爾可滿足性問題

-D.圍棋的勝負判定問題

**參考答案**:D

**解析**:圍棋的勝負判定問題屬于PSPACE類問題，因為它可以在多項式空間內(nèi)解決。

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

-A.二分查找問題

-B.旅行商問題

-C.線性規(guī)劃問題

-D.最短路徑問題

**參考答案**:B

**解析**:旅行商問題是NP難問題，即它至少與NP類中的任何問題一樣難。

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

-A.圖著色問題

-B.背包問題

-C.最短路徑問題

-D.布爾可滿足性問題

**參考答案**:C

**解析**:最短路徑問題可以在多項式時間內(nèi)解決，因此屬于P類問題。

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

-A.二分查找問題

-B.旅行商問題

-C.線性規(guī)劃問題

-D.最短路徑問題

**參考答案**:B

**解析**:旅行商問題是經(jīng)典的NP完全問題，即它既屬于NP類，又具有NP類問題的完全性。

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

-A.停機問題

-B.最短路徑問題

-C.最大流問題

-D.二分查找問題

**參考答案**:A

**解析**:停機問題是經(jīng)典的不可判定問題，即不存在一個通用算法能夠判斷任意程序在給定輸入下是否會停止。

11.以下哪個復雜度類包含所有可以在多項式時間內(nèi)解決的問題？

-A.P

-B.NP

-C.EXP

-D.PSPACE

**參考答案**:A

**解析**:P類包含所有可以在多項式時間內(nèi)解決的問題，即問題的時間復雜度為O(poly(n))。

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

-A.二分查找問題

-B.旅行商問題

-C.線性規(guī)劃問題

-D.最短路徑問題

**參考答案**:B

**解析**:旅行商問題屬于NP類問題，即給定一個解，可以在多項式時間內(nèi)驗證其正確性。

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

-A.圖著色問題

-B.背包問題

-C.最短路徑問題

-D.布爾可滿足性問題

**參考答案**:C

**解析**:最短路徑問題可以在多項式時間內(nèi)解決，因此屬于P類問題。

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

-A.二分查找問題

-B.旅行商問題

-C.線性規(guī)劃問題

-D.最短路徑問題

**參考答案**:B

**解析**:旅行商問題是經(jīng)典的NP完全問題，即它既屬于NP類，又具有NP類問題的完全性。

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

-A.停機問題

-B.最短路徑問題

-C.最大流問題

-D.二分查找問題

**參考答案**:A

**解析**:停機問題是經(jīng)典的不可判定問題，即不存在一個通用算法能夠判斷任意程序在給定輸入下是否會停止。

16.以下哪個復雜度類包含所有可以在多項式時間內(nèi)驗證解的問題？

-A.P

-B.NP

-C.EXP

-D.PSPACE

**參考答案**:B

**解析**:NP類包含所有可以在多項式時間內(nèi)驗證解的問題，即給定一個解，可以在多項式時間內(nèi)驗證其正確性。

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

-A.旅行商問題

-B.素數(shù)判定問題

-C.背包問題

-D.圖著色問題

**參考答案**:B

**解析**:素數(shù)判定問題可以在多項式時間內(nèi)解決，因此屬于P類問題。

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

-A.二分查找問題

-B.旅行商問題

-C.線性規(guī)劃問題

-D.最短路徑問題

**參考答案**:B

**解析**:旅行商問題是經(jīng)典的NP完全問題，即它既屬于NP類，又具有NP類問題的完全性。

19.以下哪個復雜度類包含所有可以在指數(shù)時間內(nèi)解決的問題？

-A.P

-B.NP

-C.EXP

-D.PSPACE

**參考答案**:C

**解析**:EXP類包含所有可以在指數(shù)時間內(nèi)解決的問題，即問題的時間復雜度為O(2^poly(n))。

20.以下哪個問題屬于PSPACE類問題？

-A.停機問題

-B.旅行商問題

-C.布爾可滿足性問題

-D.圍棋的勝負判定問題

**參考答案**:D

**解析**:圍棋的勝負判定問題屬于PSPACE類問題，因為它可以在多項式空間內(nèi)解決。

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

-A.旅行商問題

-B.二分圖匹配問題

-C.哈密頓路徑問題

-D.背包問題

**參考答案**:B

**解析**:二分圖匹配問題可以在多項式時間內(nèi)解決，因此屬于P類問題。其他選項均為NP完全問題。

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

-A.線性規(guī)劃問題

-B.質(zhì)數(shù)判定問題

-C.子集和問題

-D.最長公共子序列問題

**參考答案**:C

**解析**:子集和問題是一個著名的NP完全問題，其他選項中的問題可以在多項式時間內(nèi)解決。

23.以下哪個算法的時間復雜度是指數(shù)級的？

-A.快速排序算法

-B.歸并排序算法

-C.窮舉搜索算法

-D.二分查找算法

**參考答案**:C

**解析**:窮舉搜索算法的時間復雜度是指數(shù)級的，其他選項中的算法的時間復雜度都是多項式級的。

24.以下哪個問題可以在多項式時間內(nèi)驗證解的正確性？

-A.旅行商問題

-B.停機問題

-C.最大流問題

-D.圖著色問題

**參考答案**:A

**解析**:旅行商問題是一個NP問題，可以在多項式時間內(nèi)驗證解的正確性。停機問題是不可判定問題，無法在多項式時間內(nèi)驗證解的正確性。

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

-A.最小生成樹問題

-B.停機問題

-C.最短路徑問題

-D.二分圖匹配問題

**參考答案**:B

**解析**:停機問題是一個著名的不可判定問題，無法通過任何算法得到確定的結果。其他選項中的問題都是可判定問題。

26.以下哪個問題的復雜度類與其它三個不同？

-A.最大流問題

-B.最小生成樹問題

-C.最短路徑問題

-D.旅行商問題

**參考答案**:D

**解析**:旅行商問題是一個NP完全問題，而其他三個問題都是P類問題，可以在多項式時間內(nèi)解決。

27.以下哪個問題是最優(yōu)解可以在多項式時間內(nèi)找到的？

-A.圖著色問題

-B.背包問題

-C.最短路徑問題

-D.哈密頓路徑問題

**參考答案**:C

**解析**:最短路徑問題可以在多項式時間內(nèi)解決，而其他三個問題都是NP完全問題，無法在多項式時間內(nèi)找到最優(yōu)解。

28.以下哪個問題的復雜度類與其它三個不同？

-A.質(zhì)數(shù)判定問題

-B.最大流問題

-C.線性規(guī)劃問題

-D.子集和問題

**參考答案**:D

**解析**:子集和問題是一個NP完全問題，而其他三個問題都是P類問題，可以在多項式時間內(nèi)解決。

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

-A.最大流問題

-B.最小生成樹問題

-C.最短路徑問題

-D.圖著色問題

**參考答案**:D

**解析**:圖著色問題是一個NP類問題，無法在多項式時間內(nèi)找到最優(yōu)解，但可以在多項式時間內(nèi)驗證解的正確性。其他三個問題都是P類問題。

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

-A.二分查找問題

-B.線性規(guī)劃問題

-C.最大流問題

-D.旅行商問題

**參考答案**:D

**解析**:旅行商問題是一個NP完全問題，無法在多項式時間內(nèi)解決，而其他三個問題都是P類問題。

31.以下哪個問題可以在多項式時間內(nèi)解決？

-A.圖著色問題

-B.背包問題

-C.最短路徑問題

-D.哈密頓路徑問題

**參考答案**:C

**解析**:最短路徑問題可以在多項式時間內(nèi)解決，而其他三個問題都是NP完全問題，無法在多項式時間內(nèi)解決。

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

-A.線性規(guī)劃問題

-B.最大流問題

-C.子集和問題

-D.最小生成樹問題

**參考答案**:C

**解析**:子集和問題是一個著名的NP完全問題，而其他三個問題都是P類問題，可以在多項式時間內(nèi)解決。

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

-A.旅行商問題

-B.圖著色問題

-C.最大流問題

-D.背包問題

**參考答案**:C

**解析**:最大流問題是一個P類問題，可以在多項式時間內(nèi)解決，而其他三個問題都是NP類問題。

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

-A.圖著色問題

-B.背包問題

-C.最短路徑問題

-D.哈密頓路徑問題

**參考答案**:C

**解析**:最短路徑問題可以在多項式時間內(nèi)解決，因此屬于P類問題。其他三個問題都是NP完全問題。

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

-A.旅行商問題

-B.圖著色問題

-C.最大流問題

-D.背包問題

**參考答案**:C

**解析**:最大流問題是一個P類問題，可以在多項式時間內(nèi)解決，而其他三個問題都是NP完全問題。

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

-A.線性規(guī)劃問題

-B.最大流問題

-C.子集和問題

-D.最小生成樹問題

**參考答案**:C

**解析**:子集和問題是一個NP類問題，無法在多項式時間內(nèi)找到最優(yōu)解，但可以在多項式時間內(nèi)驗證解的正確性。其他三個問題都是