A.按照打水時間從大到小排隊(duì)，假定排隊(duì)后第i個人的打水時間是ti，平均等待時間T=∑（n-i+1）ti/n 1< =i< =n
B.按照打水時間從大到小排隊(duì)，平均等待時間T=∑ti/n 1< =i< =n
C.按照打水時間從小到大排隊(duì)，平均等待時間T=∑ti/n 1< =i< =n
D.按照打水時間從小到大排隊(duì)，假定排隊(duì)后第i個人的打水時間是ti，平均等待時間T=∑（n-i+1）ti/n 1< =i< =n
您可能感興趣的試卷
你可能感興趣的試題
A.重復(fù)子問題
B.階段性
C.無后向性
D.最優(yōu)子結(jié)構(gòu)性質(zhì)
0-1背包問題：現(xiàn)有一背包容量c=5，n=4。4個物品分別為：
（Wi，Vi）∣（1，3），（3，6），（4，9），（2，7）。如下m表中m[i][j]是前i個物品裝背包容量為j時的最優(yōu)值。
其中第四行的數(shù)據(jù)沒有填寫，分析問題，將第四行的數(shù)據(jù)從如下選項(xiàng)中找出（）。
A.0，3，3，6，8，15
B.0，3，7，7，10，13
C.0，3，7，10，10，13
D.0，3，7，10，13，15
?凸多邊形的三角剖分問題。用動態(tài)規(guī)劃算法求解最優(yōu)三角剖分，首先要分析最優(yōu)解的結(jié)構(gòu)，也就是將問題分解為子問題，并具有最優(yōu)子結(jié)構(gòu)性質(zhì)。下圖是一凸6邊形（ABCDEF）的二種不同劃分為子問題的方法，哪種是正確的將問題劃分為子問題的方案？正確的劃分方案共有幾種不同方式？（）
A.右圖正確，4種
B.右圖正確，9種
C.左圖正確，4種
D.左圖正確，9種
矩陣連乘問題：下圖是動態(tài)規(guī)劃算法計算6個矩陣A1A2A3A4A5A6連乘所生成的信息表
（a）表描述了計算順序
（b）表是m[i][j]的最優(yōu)值表
（c）表是輔助信息表（斷開位置）
分析表格，給出A2A3A4A5A6五個矩陣連乘所需要的最少數(shù)乘次數(shù)，并用加括號的方法表示出其乘法順序（）。
A.15125，（A2A3）（（A4A5）A6）
B.10500，（A2（A3A4））（A5A6）
C.15125，（A2（A3A4））（A5A6）
D.10500，（A2A3）（（A4A5）A6）
動態(tài)規(guī)劃解題的步驟分為四步：
（1）分析最優(yōu)解的結(jié)構(gòu)
（2）建立遞歸關(guān)系
（3）計算最優(yōu)值
（4）構(gòu)造最優(yōu)解
關(guān)于這四個步驟的內(nèi)容描述不正確的是哪個？（）
A.計算最優(yōu)值：以自頂往下的方法計算問題的最優(yōu)值，也就是先求解規(guī)模較大的問題的最優(yōu)值
B.構(gòu)造最優(yōu)解：根據(jù)計算最優(yōu)值時得到的信息構(gòu)造出問題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造
C.建立遞歸關(guān)系：建立關(guān)于問題最優(yōu)值的遞歸定義，即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到
D.分析最優(yōu)解的結(jié)構(gòu)：一個一般化問題可以分解為幾個性質(zhì)相同的子問題，并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)
最新試題
將長度分別為m，n的兩個單鏈表合并為一個單鏈表的時間復(fù)雜度為O（m+n）。
?優(yōu)先隊(duì)列式分支限界法解決0-1背包問題時，下面描述正確的是（）。
關(guān)于使用回溯法求解0-1背包問題，以下說法正確的是（）。
輸入數(shù)組（-1，0，1，-2，3），它的最大子段和是（）。
在隊(duì)列式分支限界法解決裝載問題時，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點(diǎn)時才去更新bestw，其目的是什么？（）
下面哪個問題不是NPC問題？（）
在解決活動安排問題時應(yīng)首先對活動進(jìn)行排序，排序的依據(jù)是（）。
Prim算法適合稀疏圖，其時間復(fù)雜度只與邊的數(shù)目有關(guān)。
馬的遍歷問題能否有可行解，與（）有關(guān)。
舍伍德算法思想是通過引入隨機(jī)化策略將確定性算法改造為隨機(jī)算法，打破原來確定性算法在某些實(shí)例情況下，其時間復(fù)雜性必然遠(yuǎn)高于平均時間復(fù)雜性的規(guī)律。下面哪些算法可以應(yīng)用舍伍德算法思想？（）