北京語言大學《算法與數(shù)據(jù)分析》20秋作業(yè)4答案

1、北京語言大學算法與數(shù)據(jù)分析20秋作業(yè)4答案下面是貪心算法的基本要素的是()。A.重疊子問題B.構造最優(yōu)解C.貪心選擇性質D.定義最優(yōu)解最大效益優(yōu)先是下列哪項的一種搜索方式?()A.分支界限法B.動態(tài)規(guī)劃法C.貪心法D.回溯法用分支限界法設計算法的第二步是()。A.針對所給問題，定義問題的解空間(對解進行編碼B.確定易于搜索的解空間結構(按樹或圖組織解)C.以廣度優(yōu)先或以最小耗費(最大收益)優(yōu)先的方式搜索解空間D.在搜索過程中用剪枝函數(shù)避免無效搜索下列算法中通常以自底向上的方式求解最優(yōu)解的是()。A.備忘錄法B.動態(tài)規(guī)劃法C.貪心法D.回溯法分支限界法與回溯法的相同點是()。A.求解目標相同B.

2、搜索方式相同C.對擴展結點的擴展方式相同D.都是一種在問題的解空間樹T中搜索問題解的算法實現(xiàn)大整數(shù)的乘法是利用()的算法。A.貪心法B.動態(tài)規(guī)劃法C.分治策略D.回溯法矩陣連乘問題的算法可由什么設計實現(xiàn)?()A.分支界限算法B.動態(tài)規(guī)劃算法C.貪心算法D.回溯算法分支限界法解最大團問題時，活結點表的組織形式是()。A.最小堆B.最大堆C.棧D.數(shù)組回溯法搜索狀態(tài)空間樹是按照什么的順序?()A.中序遍歷B.廣度優(yōu)先遍歷C.深度優(yōu)先遍歷D.層次優(yōu)先遍歷廣度優(yōu)先是什么的一種搜索方式?()A.分支界限法B.動態(tài)規(guī)劃法C.貪心法D.回溯法以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。()A.錯誤B.正確

3、算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質。()A.錯誤B.正確分治法的基本思想時將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。()A.錯誤B.正確任何可用計算機求解的問題所需的時間都與其規(guī)模無關。()A.錯誤B.正確分治法與動態(tài)規(guī)劃法的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的。()A.錯誤B.正確分支限界法主要有隊列式(FIFO)分支限界法和優(yōu)先隊列式分支限界法。()A.錯誤B.正確拉斯維加斯算法找到的解不一定是正確解。()A.錯誤B.正確問題的最優(yōu)子結構性質是該問題不可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。()A.錯誤B.正確解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。()A.錯誤B.正確利用概率的性質計算近似值的隨機算法是數(shù)值概率算法，運行時以一定的概率得到正確解的隨機算法是蒙特卡羅算法。()A.錯誤B.正確 參考答案：C參考答案：A參考答案：B參考答案：B參考答案：D參考答案：C參考答案：B參考答案：B參考答案：C參考答案：