問答題請列舉幾個常見的NP完全問題。
您可能感興趣的試卷
你可能感興趣的試題
2.單項選擇題n個人拎著水桶在一個水龍頭前面排隊打水，水桶有大有小，請問他們怎樣排隊，才能使得總的排隊時間最短。（）
A.水桶大的人先打水
B.水桶小的人先打水
C.按照什么順序都一樣
D.先到的人先打水
3.單項選擇題在尋找n個元素中第k小元素問題中，如使用快速排序算法思想，運用分治算法對n個元素進行劃分，應如何選擇劃分基準？下面（）答案解釋最合理。
A.隨機選擇一個元素作為劃分基準
B.取子序列的第一個元素作為劃分基準
C.用中位數(shù)的中位數(shù)方法尋找劃分基準
D.以上皆可行。但不同方法，算法復雜度上界可能不同
4.單項選擇題給出一個由n個數(shù)組成的序列A[1…n]，要求找出它的最長單調(diào)上升子序列，設m[i]（1≤i≤n），表示以A[i]結(jié)尾的最長單調(diào)上升子序列的長度，則m[1]=1，m[i]（1
A.m[i]=1+max{0，m[k]（A[k]<A[i]，1≤k<i）}
B.m[i]=1+m[k]（k=i-1&&i>1）
C.m[i]=1+max{0，m[k]（A[k]≤A[i]，1≤k<i）}
D.m[i]=max{0，m[k]（A[k]<A[i]，1≤k<i）}
5.單項選擇題將一個正整數(shù)n表示成一系列正整數(shù)之和，n=n1+n2+…+nk（其中，n1≥n2≥…≥nk≥1，k≥1）正整數(shù)n的一個這種表示稱為正整數(shù)n的一個劃分。正整數(shù)n的不同的劃分個數(shù)總和稱為正整數(shù)n的劃分數(shù)，記作p（n）；另外，在正整數(shù)n的所有不同劃分中，將最大加數(shù)n1不大于m的劃分個數(shù)記作q（n，m）。則當n=10時，p（n）=（）。
A.q（8，8）
B.1+q（9，9）
C.2+q（10，8）
D.ABC都正確
最新試題
有一個問題的蒙特卡洛算法，給定一個實例，已知運行一次其答案是錯誤的概率是1/8，現(xiàn)運行k次該算法，其答案一直不變，問該答案的正確率是（）。
題型：單項選擇題
序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為（）。
題型：單項選擇題
下列關于效率的說法正確的是（）。
題型：多項選擇題
?優(yōu)先隊列式分支限界法解決0-1背包問題時，下面描述正確的是（）。
題型：多項選擇題
下面哪個問題不是NPC問題？（）
題型：單項選擇題
下列關于貪心算法與動態(tài)規(guī)劃算法說法正確的是（）。
題型：多項選擇題
有這樣一種算法，運行一次一定能找到問題的解，有時不知其是否正確，可以確定的是該解高概率（大于50%）是正確的。這種算法是（）。
題型：單項選擇題
用漸進表示法分析算法復雜度的增長趨勢。
題型：判斷題
在一個至少包含三個頂點的加權連通單向圖中，假定邊的權重互不相同，則權重最大的邊不可能被包含在任何最小生成樹中。
題型：判斷題
輸入數(shù)組（-1，0，1，-2，3），它的最大子段和是（）。
題型：單項選擇題