單項(xiàng)選擇題NP類(lèi)語(yǔ)言在圖靈機(jī)下的定義為()

A.NP={L∣L是一個(gè)能在非多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語(yǔ)言}
B.NP={L∣L是一個(gè)能在非多項(xiàng)式時(shí)間內(nèi)被一臺(tái)DTM所接受的語(yǔ)言}
C.NP={L∣L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)DTM所接受的語(yǔ)言}
D.NP={L∣L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM所接受的語(yǔ)言}


您可能感興趣的試卷

你可能感興趣的試題

1.單項(xiàng)選擇題k帶圖靈機(jī)的空間復(fù)雜性S(n)是指()

A.k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí),在某條帶上所使用過(guò)的最大方格數(shù)
B.k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí),在k條帶上所使用過(guò)的方格數(shù)的總和
C.k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí),在k條帶上所使用過(guò)的平均方格數(shù)
D.k帶圖靈機(jī)處理所有長(zhǎng)度為n的輸入時(shí),在某條帶上所使用過(guò)的最小方格數(shù)

2.單項(xiàng)選擇題常見(jiàn)的兩種分支限界法為()

A.廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法
B.隊(duì)列式(FIFO)分支限界法與堆棧式分支限界法
C.排列樹(shù)法與子集樹(shù)法
D.隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法

3.單項(xiàng)選擇題回溯法的效率不依賴于以下哪一個(gè)因素?()

A.產(chǎn)生x[k]的時(shí)間
B.滿足顯約束的x[k]值的個(gè)數(shù)
C.問(wèn)題的解空間的形式
D.計(jì)算上界函數(shù)bound的時(shí)間
E.滿足約束函數(shù)和上界函數(shù)約束的所有x[k]的個(gè)數(shù)
F.計(jì)算約束函數(shù)constraint的時(shí)間

5.單項(xiàng)選擇題分支限界法在問(wèn)題的解空間樹(shù)中,按()策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。

A.廣度優(yōu)先
B.活結(jié)點(diǎn)優(yōu)先
C.擴(kuò)展結(jié)點(diǎn)優(yōu)先
D.深度優(yōu)先

最新試題

簡(jiǎn)單描述回溯法基本思想。

題型:?jiǎn)柎痤}

已知非齊次遞歸方程:其中,b、c是常數(shù),g(n)是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為:現(xiàn)有Hanoi塔問(wèn)題的遞歸方程為:,求h(n)的非遞歸表達(dá)式。

題型:?jiǎn)柎痤}

何謂最優(yōu)子結(jié)構(gòu)性質(zhì)?

題型:?jiǎn)柎痤}

計(jì)算機(jī)的資源最重要的是()和()資源。因而,算法的復(fù)雜性有()和()之分。

題型:填空題

何謂P、NP、NPC問(wèn)題?

題型:?jiǎn)柎痤}

二分搜索算法是利用()實(shí)現(xiàn)的算法。

題型:填空題

在進(jìn)行問(wèn)題的計(jì)算復(fù)雜性分析之前,首先必須建立求解問(wèn)題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是()、()、()。

題型:填空題

通過(guò)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)≤240),去掉其中任意s個(gè)數(shù)字后,剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s,尋找一種方案,使得剩下的數(shù)字組成的新數(shù)最小。 【樣例輸入】 178543 S=4 【樣例輸出】 13

題型:?jiǎn)柎痤}

動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干(),先求解(),然后從這些()的解得到原問(wèn)題的解。

題型:填空題

描述0-1背包問(wèn)題。

題型:?jiǎn)柎痤}