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