




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
PAGE1.以下哪個問題屬于不可判定問題?
-A.停機問題
-B.最短路徑問題
-C.最大流問題
-D.二分查找問題
**參考答案**:A
**解析**:停機問題是經典的不可判定問題,即不存在一個通用算法能夠判斷任意程序在給定輸入下是否會停止。
2.以下哪個復雜度類包含所有可以在多項式時間內驗證解的問題?
-A.P
-B.NP
-C.EXP
-D.PSPACE
**參考答案**:B
**解析**:NP類包含所有可以在多項式時間內驗證解的問題,即給定一個解,可以在多項式時間內驗證其正確性。
3.以下哪個問題屬于P類問題?
-A.旅行商問題
-B.素數判定問題
-C.背包問題
-D.圖著色問題
**參考答案**:B
**解析**:素數判定問題可以在多項式時間內解決,因此屬于P類問題。
4.以下哪個問題屬于NP完全問題?
-A.二分查找問題
-B.旅行商問題
-C.線性規劃問題
-D.最短路徑問題
**參考答案**:B
**解析**:旅行商問題是經典的NP完全問題,即它既屬于NP類,又具有NP類問題的完全性。
5.以下哪個復雜度類包含所有可以在指數時間內解決的問題?
-A.P
-B.NP
-C.EXP
-D.PSPACE
**參考答案**:C
**解析**:EXP類包含所有可以在指數時間內解決的問題,即問題的時間復雜度為O(2^poly(n))。
6.以下哪個問題屬于PSPACE類問題?
-A.停機問題
-B.旅行商問題
-C.布爾可滿足性問題
-D.圍棋的勝負判定問題
**參考答案**:D
**解析**:圍棋的勝負判定問題屬于PSPACE類問題,因為它可以在多項式空間內解決。
7.以下哪個問題屬于NP難問題?
-A.二分查找問題
-B.旅行商問題
-C.線性規劃問題
-D.最短路徑問題
**參考答案**:B
**解析**:旅行商問題是NP難問題,即它至少與NP類中的任何問題一樣難。
8.以下哪個問題屬于P類問題?
-A.圖著色問題
-B.背包問題
-C.最短路徑問題
-D.布爾可滿足性問題
**參考答案**:C
**解析**:最短路徑問題可以在多項式時間內解決,因此屬于P類問題。
9.以下哪個問題屬于NP完全問題?
-A.二分查找問題
-B.旅行商問題
-C.線性規劃問題
-D.最短路徑問題
**參考答案**:B
**解析**:旅行商問題是經典的NP完全問題,即它既屬于NP類,又具有NP類問題的完全性。
10.以下哪個問題屬于不可判定問題?
-A.停機問題
-B.最短路徑問題
-C.最大流問題
-D.二分查找問題
**參考答案**:A
**解析**:停機問題是經典的不可判定問題,即不存在一個通用算法能夠判斷任意程序在給定輸入下是否會停止。
11.以下哪個復雜度類包含所有可以在多項式時間內解決的問題?
-A.P
-B.NP
-C.EXP
-D.PSPACE
**參考答案**:A
**解析**:P類包含所有可以在多項式時間內解決的問題,即問題的時間復雜度為O(poly(n))。
12.以下哪個問題屬于NP類問題?
-A.二分查找問題
-B.旅行商問題
-C.線性規劃問題
-D.最短路徑問題
**參考答案**:B
**解析**:旅行商問題屬于NP類問題,即給定一個解,可以在多項式時間內驗證其正確性。
13.以下哪個問題屬于P類問題?
-A.圖著色問題
-B.背包問題
-C.最短路徑問題
-D.布爾可滿足性問題
**參考答案**:C
**解析**:最短路徑問題可以在多項式時間內解決,因此屬于P類問題。
14.以下哪個問題屬于NP完全問題?
-A.二分查找問題
-B.旅行商問題
-C.線性規劃問題
-D.最短路徑問題
**參考答案**:B
**解析**:旅行商問題是經典的NP完全問題,即它既屬于NP類,又具有NP類問題的完全性。
15.以下哪個問題屬于不可判定問題?
-A.停機問題
-B.最短路徑問題
-C.最大流問題
-D.二分查找問題
**參考答案**:A
**解析**:停機問題是經典的不可判定問題,即不存在一個通用算法能夠判斷任意程序在給定輸入下是否會停止。
16.以下哪個復雜度類包含所有可以在多項式時間內驗證解的問題?
-A.P
-B.NP
-C.EXP
-D.PSPACE
**參考答案**:B
**解析**:NP類包含所有可以在多項式時間內驗證解的問題,即給定一個解,可以在多項式時間內驗證其正確性。
17.以下哪個問題屬于P類問題?
-A.旅行商問題
-B.素數判定問題
-C.背包問題
-D.圖著色問題
**參考答案**:B
**解析**:素數判定問題可以在多項式時間內解決,因此屬于P類問題。
18.以下哪個問題屬于NP完全問題?
-A.二分查找問題
-B.旅行商問題
-C.線性規劃問題
-D.最短路徑問題
**參考答案**:B
**解析**:旅行商問題是經典的NP完全問題,即它既屬于NP類,又具有NP類問題的完全性。
19.以下哪個復雜度類包含所有可以在指數時間內解決的問題?
-A.P
-B.NP
-C.EXP
-D.PSPACE
**參考答案**:C
**解析**:EXP類包含所有可以在指數時間內解決的問題,即問題的時間復雜度為O(2^poly(n))。
20.以下哪個問題屬于PSPACE類問題?
-A.停機問題
-B.旅行商問題
-C.布爾可滿足性問題
-D.圍棋的勝負判定問題
**參考答案**:D
**解析**:圍棋的勝負判定問題屬于PSPACE類問題,因為它可以在多項式空間內解決。
21.以下哪個問題屬于P類問題?
-A.旅行商問題
-B.二分圖匹配問題
-C.哈密頓路徑問題
-D.背包問題
**參考答案**:B
**解析**:二分圖匹配問題可以在多項式時間內解決,因此屬于P類問題。其他選項均為NP完全問題。
22.以下哪個問題屬于NP完全問題?
-A.線性規劃問題
-B.質數判定問題
-C.子集和問題
-D.最長公共子序列問題
**參考答案**:C
**解析**:子集和問題是一個著名的NP完全問題,其他選項中的問題可以在多項式時間內解決。
23.以下哪個算法的時間復雜度是指數級的?
-A.快速排序算法
-B.歸并排序算法
-C.窮舉搜索算法
-D.二分查找算法
**參考答案**:C
**解析**:窮舉搜索算法的時間復雜度是指數級的,其他選項中的算法的時間復雜度都是多項式級的。
24.以下哪個問題可以在多項式時間內驗證解的正確性?
-A.旅行商問題
-B.停機問題
-C.最大流問題
-D.圖著色問題
**參考答案**:A
**解析**:旅行商問題是一個NP問題,可以在多項式時間內驗證解的正確性。停機問題是不可判定問題,無法在多項式時間內驗證解的正確性。
25.以下哪個問題不屬于可判定問題?
-A.最小生成樹問題
-B.停機問題
-C.最短路徑問題
-D.二分圖匹配問題
**參考答案**:B
**解析**:停機問題是一個著名的不可判定問題,無法通過任何算法得到確定的結果。其他選項中的問題都是可判定問題。
26.以下哪個問題的復雜度類與其它三個不同?
-A.最大流問題
-B.最小生成樹問題
-C.最短路徑問題
-D.旅行商問題
**參考答案**:D
**解析**:旅行商問題是一個NP完全問題,而其他三個問題都是P類問題,可以在多項式時間內解決。
27.以下哪個問題是最優解可以在多項式時間內找到的?
-A.圖著色問題
-B.背包問題
-C.最短路徑問題
-D.哈密頓路徑問題
**參考答案**:C
**解析**:最短路徑問題可以在多項式時間內解決,而其他三個問題都是NP完全問題,無法在多項式時間內找到最優解。
28.以下哪個問題的復雜度類與其它三個不同?
-A.質數判定問題
-B.最大流問題
-C.線性規劃問題
-D.子集和問題
**參考答案**:D
**解析**:子集和問題是一個NP完全問題,而其他三個問題都是P類問題,可以在多項式時間內解決。
29.以下哪個問題屬于NP類問題?
-A.最大流問題
-B.最小生成樹問題
-C.最短路徑問題
-D.圖著色問題
**參考答案**:D
**解析**:圖著色問題是一個NP類問題,無法在多項式時間內找到最優解,但可以在多項式時間內驗證解的正確性。其他三個問題都是P類問題。
30.以下哪個問題不屬于P類問題?
-A.二分查找問題
-B.線性規劃問題
-C.最大流問題
-D.旅行商問題
**參考答案**:D
**解析**:旅行商問題是一個NP完全問題,無法在多項式時間內解決,而其他三個問題都是P類問題。
31.以下哪個問題可以在多項式時間內解決?
-A.圖著色問題
-B.背包問題
-C.最短路徑問題
-D.哈密頓路徑問題
**參考答案**:C
**解析**:最短路徑問題可以在多項式時間內解決,而其他三個問題都是NP完全問題,無法在多項式時間內解決。
32.以下哪個問題屬于NP完全問題?
-A.線性規劃問題
-B.最大流問題
-C.子集和問題
-D.最小生成樹問題
**參考答案**:C
**解析**:子集和問題是一個著名的NP完全問題,而其他三個問題都是P類問題,可以在多項式時間內解決。
33.以下哪個問題不屬于NP類問題?
-A.旅行商問題
-B.圖著色問題
-C.最大流問題
-D.背包問題
**參考答案**:C
**解析**:最大流問題是一個P類問題,可以在多項式時間內解決,而其他三個問題都是NP類問題。
34.以下哪個問題屬于P類問題?
-A.圖著色問題
-B.背包問題
-C.最短路徑問題
-D.哈密頓路徑問題
**參考答案**:C
**解析**:最短路徑問題可以在多項式時間內解決,因此屬于P類問題。其他三個問題都是NP完全問題。
35.以下哪個問題不屬于NP完全問題?
-A.旅行商問題
-B.圖著色問題
-C.最大流問題
-D.背包問題
**參考答案**:C
**解析**:最大流問題是一個P類問題,可以在多項式時間內解決,而其他三個問題都是NP完全問題。
36.以下哪個問題屬于NP類問題?
-A.線性規劃問題
-B.最大流問題
-C.子集和問題
-D.最小生成樹問題
**參考答案**:C
**解析**:子集和問題是一個NP類問題,無法在多項式時間內找到最優解,但可以在多項式時間內驗證解的正確性。其他三個問題都是
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 農業文化遺產可視化知識圖譜構建
- 煤氣化渣二氧化硅對聚丙烯除味性能的研究與應用
- 公園生活垃圾管理辦法
- 十年職場經驗分享與職業規劃
- 江西涉密采購管理辦法
- 通信工程技術規范
- 積極心理學應用:心理健康教育長效機制構建
- 利率市場化改革對中小企業融資效率的影響機制研究
- 基于乘客決策行為的城市軌道交通系統韌性評估研究
- 2025年 重大安全事故
- 中職《接觸器聯鎖正反轉控制線路》公開課PPT
- 05-衣之鏢-輔行訣湯液經法用藥圖釋義
- LS/T 3240-2012湯圓用水磨白糯米粉
- GB/T 15298-1994電子設備用電位器第一部分:總規范
- 新教科版六下科學4-6《生命體中的化學變化》教案
- 2023高中學業水平合格性考試歷史重點知識點歸納總結(復習必背)
- 自然指數NatureIndex(NI)收錄的68種自然科學類期刊
- 手術報告審批單
- 《專業導論光電信息科學與工程》教學大綱
- 廣東省湛江市各縣區鄉鎮行政村村莊村名明細
- 少兒美術國畫- 少兒希望 《紫藤課件》
評論
0/150
提交評論