算法分析復習試題目和答案(編輯修改稿)
2025-07-21 22:02 本頁面
【文章內(nèi)容簡介】 。A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法51下列哪一種算法是隨機化算法（D ）A. 貪心算法B. 52. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的（B ）。A、重疊子問題 B、最優(yōu)子結(jié)構(gòu)性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解53．采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復雜度為 ( B ) 。A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）54. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 ( D ) 。A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法55. 實現(xiàn)最長公共子序列利用的算法是（B ）。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法二、 填空題 時間 復雜性和 空間 復雜性之分。程序是 算法用某種程序設計語言的具體實現(xiàn)。算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。 動態(tài)規(guī)劃 設計實現(xiàn)。拉斯維加斯算法找到的解一定是 正確解。算法是指解決問題的 一種方法 或 一個過程 。從分治法的一般設計模式可以看出，用它設計出的程序一般是 遞歸算法 。問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 回溯法 。數(shù)值概率算法常用于 數(shù)值問題 的求解。1計算一個算法時間復雜度通常可以計算 循環(huán)次數(shù) 、 基本操作的頻率 或計算步。1利用概率的性質(zhì)計算近似值的隨機算法是__數(shù)值概率算法，運行時以一定的概率得到正確解的隨機算法是__蒙特卡羅算法_____________________。1解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動態(tài)規(guī)劃 ，需要排序的是 回溯法 ，分支限界法 。1使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個標準：約束條件和目標函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數(shù)的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。1 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。1矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設計實現(xiàn)。1拉斯維加斯算法找到的解一定是 正確解。 貪心選擇 質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。21. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。，且要滿足輸入、 輸出 、確定性和 有限性 四條性質(zhì)。2大整數(shù)乘積算法是用 分治法 來設計的。2以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。2舍伍德算法總能求得問題的 一個解 。2 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 分治策略 的一種排序算法。. 最優(yōu)子結(jié)構(gòu) 性質(zhì)和 重疊子問題 性質(zhì) 。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 隊列式（FIFO） 分支限界法和 優(yōu)先隊列式 分支限界法。32．分支限界法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。33．回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。 規(guī)模 有關。 劃分的對稱性 。三、算法填空void Knapsack(int n,float M,float v[],float w[],float x[]){ Sort(n,v,w)。 int i。 for (i=1。i=n。i++) x[i]=0。 float c=M。 for (i=1。i=n。i++) { if
畢業(yè)設計相關推薦
鄂ICP備17016276號-1