問(wèn)答題

有11個(gè)待安排的活動(dòng),它們具有下表所示的開始時(shí)間與結(jié)束時(shí)間,如果以貪心算法求解這些活動(dòng)的最優(yōu)安排(即為活動(dòng)安排問(wèn)題:在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合),得到的最大相容活動(dòng)子集合為多少?


您可能感興趣的試卷

你可能感興趣的試題

1.單項(xiàng)選擇題記號(hào)Ω的定義正確的是()。

A.O(g(n))={f(n)∣存在正常數(shù)c和n0使得對(duì)所有n≧n0有:0≦f(n)≦cg(n)}
B.O(g(n))={f(n)∣存在正常數(shù)c和n0使得對(duì)所有n≧0有:0≦g(n)≦(n)}
C.O(g(n))={f(n)∣對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對(duì)所有n≧n0有:0≦f(n)<cg(n)}
D.O(g(n))={f(n)∣對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對(duì)所有n≧n0有:0≦cg(n)<f(n)}

2.單項(xiàng)選擇題記號(hào)O的定義正確的是()。

A.O(g(n))={f(n)∣存在正常數(shù)c和n0使得對(duì)所有n≧n0有:0≦f(n)≦cg(n)}
B.O(g(n))={f(n)∣存在正常數(shù)c和n0使得對(duì)所有n≧0有:0≦g(n)≦(n)}
C.O(g(n))={f(n)∣對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對(duì)所有n≧n0有:0≦f(n)<cg(n)}
D.O(g(n))={f(n)∣對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0>0使得對(duì)所有n≧n0有:0≦cg(n)<f(n)}

3.單項(xiàng)選擇題NP類語(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ǔ)言}

4.單項(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ù)

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

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

最新試題

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

題型:?jiǎn)柎痤}

舉反例證明0/1背包問(wèn)題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品,即只要正在被考慮的物品裝得進(jìn)就裝入背包,則此方法不一定能得到最優(yōu)解(此題說(shuō)明0/1背包問(wèn)題與背包問(wèn)題的不同)。

題型:?jiǎn)柎痤}

一個(gè)算法就是一個(gè)有窮規(guī)則的集合,其中之規(guī)則規(guī)定了解決某一特殊類型問(wèn)題的一系列運(yùn)算,此外,算法還應(yīng)具有以下五個(gè)重要特性:()、()、()、()、()。

題型:填空題

若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},請(qǐng)給出序列X和Y的一個(gè)最長(zhǎng)公共子序列:()

題型:填空題

若n=4,在機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為ai和bi,且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求4個(gè)作業(yè)的最優(yōu)調(diào)度方案,并計(jì)算最優(yōu)值。

題型:?jiǎn)柎痤}

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

題型:?jiǎn)柎痤}

貪心算法總是做出在當(dāng)前看來(lái)()的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮,它所做出的選擇只是在某種意義上的()。

題型:填空題

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

題型:?jiǎn)柎痤}

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

題型:填空題

使用回溯法解0/1背包問(wèn)題:n=3,C=9,V={6,10,3},W={3,4,4},其解空間有長(zhǎng)度為3的0-1向量組成,要求用一棵完全二叉樹表示其解空間(從根出發(fā),左1右0),并畫出其解空間樹,計(jì)算其最優(yōu)值及最優(yōu)解。

題型:?jiǎn)柎痤}