單項選擇題設(shè)置頂點集合S，初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應(yīng)的最短特殊路徑長度。每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有Ⅴ中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。這是（）的基本思想。
A.Dijkstra算法
B.Huffman編碼
C.Prim算法
D.Kruskal算法
您可能感興趣的試卷
你可能感興趣的試題
1.單項選擇題Dijkstra算法是解單源最短路徑問題的一個（）算法。
A.動態(tài)規(guī)劃
B.分治
C.回溯
D.貪心
2.單項選擇題哈夫曼算法以（）的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。
A.自左向右
B.自右向左
C.自頂向下
D.自底向上
3.單項選擇題設(shè)有n個活動的集合E={1，2，…，n}，其中每個活動都要求使用同一資源，而在同一時間內(nèi)只有一個活動使用這一資源，只有一個活動能使用這一資源。能夠得到活動安排問題的最優(yōu)解的貪心策略是（）。
A.開始最早的活動優(yōu)先
B.時間最短活動優(yōu)先
C.結(jié)束時間早的活動優(yōu)先
D.以上都可以
4.單項選擇題下面（）不能使用貪心算法來求解。
A.單源最短路徑
B.活動安排問題
C.0-1背包問題
D.哈夫曼編碼
5.單項選擇題矩陣連乘算法所需的計算空間復(fù)雜度為（）。
A.O（n）
B.O（n2）
C.O（n!）
D.O（logn）
最新試題
Prim算法適合稀疏圖，其時間復(fù)雜度只與邊的數(shù)目有關(guān)。
題型：判斷題
下列關(guān)于貪心算法與動態(tài)規(guī)劃算法說法正確的是（）。
題型：多項選擇題
分支限界法中，擴展出的孩子結(jié)點在入隊時，存儲該孩子結(jié)點的父結(jié)點的地址和左孩子標志。其目的是什么？（）
題型：單項選擇題
應(yīng)用分支限界法的三個關(guān)鍵問題包括（）。
題型：多項選擇題
序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為（）。
題型：單項選擇題
在使用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同，即將一個問題分成大小相等的多個子問題的處理方法是行之有效的。
題型：判斷題
關(guān)于分支限界法的基本思想，下列描述正確的是（）。
題型：多項選擇題
在隊列式分支限界法解決裝載問題時，為什么在其改進算法中，每次進入左分支都要檢查更新bestw，而不是等搜索到達葉子結(jié)點時才去更新bestw，其目的是什么？（）
題型：單項選擇題
關(guān)于使用回溯法求解0-1背包問題，以下說法正確的是（）。
題型：多項選擇題
將長度分別為m，n的兩個單鏈表合并為一個單鏈表的時間復(fù)雜度為O（m+n）。
題型：判斷題