計算機科學導論-基于計算思維的思想與方法（第4版）-習題及答案 ch07

第七章問題求解的算法基礎選擇題1-5ABCDA6-10BCDAB問答題1.什么是算法?算法(Algorithm)是一種求解問題的思維方式，是對事物本質的數(shù)學抽象。具體說，算法是由基本運算規(guī)則和運算順序構成的、完整的解題方法和步驟，是程序設計的核心。2.算法有哪些特征?(1)確定性(Certainty)(2)有效性(Effectiveness)(3)有窮性(Finiteness)(4)有零個或多個輸入(Input)(5)有一個或多個輸出(Output)3.算法的復雜性是指什么?1.時間復雜度(TimeComplexity)算法的時間復雜度是指度量時間的復雜性，即算法的時間效率的指標。換言之，時間復雜度是與求解問題的規(guī)模、算法輸入數(shù)據(jù)相關的函數(shù)，該函數(shù)表示算法運行所花費的時間。2.空間復雜度(SpaceComplexity)算法的空間復雜度是指算法運行的存儲空間，是實現(xiàn)算法所需的內存空間的大小。4.在問題求解過程中，算法的描述方法由哪幾種?算法是對解題過程的精確描述，描述算法的方法很多，常用的描述方法有自然語言、圖形描述(流程圖、N-S結構圖、PAD結構圖)、偽代碼、程序設計語言等。5.窮舉算法的基本思想是什么?(1)確定范圍：按照問題要求確定問題解的大致范圍一一列舉，遍歷所有可能的組合值。.(2)條件約束：判斷題解是否符合正解條件，避免解題結果錯誤。(3)循環(huán)運算：使可能解的范圍降至最小，以便提高解題效益。6.迭代算法的基本思想是什么?所謂迭代，就是為了逼近所需目標或結果而重復反饋，每次迭代的結果作為下次迭代的初始值。迭代與遞推的區(qū)別源于問題的性質，在實際問題中可能遇到以下兩種情況。.(1)可以表示成數(shù)學上明確的遞推公式。(2)無法直接寫出顯式遞推公式：只能通過“迭代”，并且可分為精確迭代和近似迭代。7.遞歸算法的基本思想是什么?遞歸是一種強有力的數(shù)學工具，它可使問題的描述和求解變得簡潔和清晰，它有兩種形式。(1)直接遞歸：重復一個或一組操作，如累加、累減、累乘、累除等運算就是直接遞歸，程序設計中的賦值語句“a=a+1；"是累加，把a+1的值賦給a是遞歸計算，而不是表達式計算。(2)間接遞歸：是指從1到n之間所有自然數(shù)相乘的結果，階乘計算就是典型的間接遞歸，程序用到它自身的前一步或前幾步。8.遞歸算法和遞推算法有何區(qū)別?本質上，遞歸和遞推都是同一種解決問題的思路，都是把問題進行分解，但遞推是由小到大的推導，而遞歸則是由大到小的推導。9.分治算法的基本思想是什么?由分治算法產生的子問題往往是原問題的較小模式，最終使子問題縮小到容易直接求解，自然導致遞歸過程的產生，也為使用遞歸技術提供了方便。分治算法一般按照以下步驟求解：(1)分解：將要解決的問題劃分成若干規(guī)模較小的同類問題(子問題)；(2)求解：當待解決的問題劃分得足夠小后，用簡單的方法求得結果；(3)合并：按照原問題的要求，將子問題的解逐層合并構成原問題的整體解。10.動態(tài)規(guī)劃的基本思想什么?為了解決某一多階段決策過程的優(yōu)化問題，而依次做出n個決策D1，D2，...Dn；如果這個決策序列是最優(yōu)的，不論前面決策是怎樣的，以后的最優(yōu)決策取決于由前面決策所確定的當前狀態(tài)。動態(tài)規(guī)劃一般按照以下步驟求解。(1)劃分：將待求解的問題劃分為若干個階段，即若干互相聯(lián)系的子問題。(2)推導：按照自底向上的順序，推導出原問題的解。(3)記錄：記錄子問題的解，避免求解過程中重復多次求解同一子問題，提高算法求解效率。11.數(shù)據(jù)結構、數(shù)據(jù)查找與數(shù)據(jù)排序有何區(qū)別?對于非數(shù)值數(shù)據(jù)，它不是求問題的數(shù)值解，只能采用數(shù)據(jù)結構的方式來實現(xiàn)對數(shù)據(jù)的處理；數(shù)據(jù)查找和排序實際上是對數(shù)組中的數(shù)據(jù)元素進行處理。談論題1.你認為，研究數(shù)值數(shù)據(jù)算法、數(shù)據(jù)查找與排序、數(shù)據(jù)結構的意義在哪里?數(shù)據(jù)元素操作通常是對數(shù)組中的元素進行查找與排序，是介于數(shù)值數(shù)據(jù)處