動(dòng)態(tài)規(guī)劃解題的步驟分為四步：
（1）分析最優(yōu)解的結(jié)構(gòu)
（2）建立遞歸關(guān)系
（3）計(jì)算最優(yōu)值
（4）構(gòu)造最優(yōu)解
關(guān)于這四個(gè)步驟的內(nèi)容描述不正確的是哪個(gè)？（）
A.計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問(wèn)題的最優(yōu)值，也就是先求解規(guī)模較大的問(wèn)題的最優(yōu)值
B.構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問(wèn)題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造
C.建立遞歸關(guān)系：建立關(guān)于問(wèn)題最優(yōu)值的遞歸定義，即問(wèn)題的最優(yōu)值通過(guò)子問(wèn)題的最優(yōu)值合并得到
D.分析最優(yōu)解的結(jié)構(gòu)：一個(gè)一般化問(wèn)題可以分解為幾個(gè)性質(zhì)相同的子問(wèn)題，并且問(wèn)題的最優(yōu)解可以通過(guò)子問(wèn)題的最優(yōu)解合并得到，也就是要滿(mǎn)足最優(yōu)子結(jié)構(gòu)性質(zhì)
您可能感興趣的試卷
你可能感興趣的試題
A.O（n）
B.O（nlogn）
C.O（logn）
D.O（n2）
A.結(jié)構(gòu)清晰
B.容易用數(shù)學(xué)歸納法證明算法的正確性
C.遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問(wèn)題的非遞歸算法要少
D.可讀性強(qiáng)
A.6
B.101
C.51
D.7
A.這是因?yàn)闅w并排序把問(wèn)題劃分為子問(wèn)題時(shí)的時(shí)間復(fù)雜性是O（1），而快速排序劃分為子問(wèn)題是使用partition（）函數(shù)，其時(shí)間復(fù)雜性是O（n）
B.因?yàn)闅w并排序把問(wèn)題劃分為兩個(gè)子問(wèn)題時(shí)其規(guī)模大致相等，是原來(lái)規(guī)模的n/2，而快速排序劃分為子問(wèn)題是使用partition（）函數(shù)，劃分為子問(wèn)題時(shí)不能保證二個(gè)子問(wèn)題的規(guī)模大致相同，在極端狀況下，每次都只劃分為1個(gè)子問(wèn)題，其規(guī)模為原問(wèn)題規(guī)模n-1，因此快速排序在極端狀況下的時(shí)間復(fù)雜性的遞歸定義為T(mén)（n）=T（n-1）+O（n）
C.因?yàn)榭焖倥判驅(qū)?wèn)題劃分為子問(wèn)題的個(gè)數(shù)比歸并排序要多
D.歸并排序的分和合的時(shí)間復(fù)雜性之和低于快速排序的分和合的時(shí)間復(fù)雜性之和
A.不能，因?yàn)樗豢梢杂梅?、治、合三個(gè)步驟完成計(jì)算
B.不能，因?yàn)樗粷M(mǎn)足分治法的第四個(gè)適應(yīng)條件（子問(wèn)題是相互獨(dú)立的，也就是沒(méi)有重復(fù)子問(wèn)題）
C.能，因?yàn)樗鼭M(mǎn)足分治法的四個(gè)適應(yīng)條件
D.能，因?yàn)樗梢杂梅?、治、合三個(gè)步驟完成計(jì)算
最新試題
已知某樓房共20層，如果采用二分查找，最多猜（）次就能猜出任意一個(gè)樓層。
下列關(guān)于效率的說(shuō)法正確的是（）。
在解決活動(dòng)安排問(wèn)題時(shí)應(yīng)首先對(duì)活動(dòng)進(jìn)行排序，排序的依據(jù)是（）。
馬的遍歷問(wèn)題能否有可行解，與（）有關(guān)。
Prim算法適合稀疏圖，其時(shí)間復(fù)雜度只與邊的數(shù)目有關(guān)。
在使用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同，即將一個(gè)問(wèn)題分成大小相等的多個(gè)子問(wèn)題的處理方法是行之有效的。
在一個(gè)至少包含三個(gè)頂點(diǎn)的加權(quán)連通單向圖中，假定邊的權(quán)重互不相同，則權(quán)重最大的邊不可能被包含在任何最小生成樹(shù)中。
關(guān)于使用回溯法求解0-1背包問(wèn)題，以下說(shuō)法正確的是（）。
輸入數(shù)組（-1，0，1，-2，3），它的最大子段和是（）。
?優(yōu)先隊(duì)列式分支限界法解決0-1背包問(wèn)題時(shí)，下面描述正確的是（）。