計(jì)算機(jī)科學(xué)導(dǎo)論-基于計(jì)算思維的思想與方法（第4版）-習(xí)題及答案 ch07

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