數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用c++語言描述習(xí)題參考答案doc

1、第1章概論1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的含義分別是什么？數(shù)據(jù)：數(shù)據(jù)：對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素：數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個整體考慮。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系運(yùn)算，是以數(shù)據(jù)為成員的結(jié)構(gòu)，是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，數(shù)據(jù)元素之間存在著一種或多種特定的關(guān)系。數(shù)據(jù)類型：數(shù)據(jù)類型：數(shù)據(jù)類型是用來區(qū)分不同的數(shù)據(jù)；由于數(shù)據(jù)在存儲時

2、所需要的容量各不相同，不同的數(shù)據(jù)就必須要分配不同大小的內(nèi)存空間來存儲，所有就要將數(shù)據(jù)劃分成不同的數(shù)據(jù)類型。數(shù)據(jù)類型包含取值范圍和基本運(yùn)算等概念。2.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是數(shù)據(jù)的物理結(jié)構(gòu)？數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)定義了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的相互邏輯關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)包含下面兩個方面的信息：①數(shù)據(jù)元素的信息；②各數(shù)據(jù)元素之間的關(guān)系。物理結(jié)構(gòu)：物理結(jié)構(gòu)：也叫儲存結(jié)構(gòu)，是指邏輯結(jié)構(gòu)

3、的存儲表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式，包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲表示。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的，一個操作算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采與的存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時，針對不同問題，選擇合理的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)非常重要。3.數(shù)據(jù)結(jié)構(gòu)的主要操作包括哪些？對于各種數(shù)據(jù)結(jié)構(gòu)而言，他們在基本操作上是相似的，最常用的操作有：?創(chuàng)建：建

4、立一個數(shù)據(jù)結(jié)構(gòu)；?清除：清除一個數(shù)據(jù)結(jié)構(gòu)；?插入：在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點(diǎn)；?刪除：把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中刪除；?訪問：對數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)進(jìn)行訪問；?更新：改變指定結(jié)點(diǎn)的值或改變指定的某些結(jié)點(diǎn)之間的關(guān)系；?查找：在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的結(jié)點(diǎn)；?排序：對數(shù)據(jù)結(jié)構(gòu)中各個結(jié)點(diǎn)按指定數(shù)據(jù)項(xiàng)的值，以升序或降序重新排列。4.什么是抽象數(shù)據(jù)類型？如何定義抽象數(shù)據(jù)類型？抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指一個數(shù)學(xué)模型以

5、及定義在此數(shù)學(xué)模型上的一組操作。ADT是與具體的物理存儲無關(guān)的數(shù)據(jù)類型，因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)據(jù)結(jié)構(gòu)的特性不變，都不影響其外部使用。對抽象數(shù)據(jù)類型的描述一般用（DRP)三元組表示，抽象數(shù)據(jù)類型的定義格式為：ADT數(shù)據(jù)對象D：數(shù)據(jù)關(guān)系R：解。因此，程序可以從i=0或i=1出發(fā)，由已知i1規(guī)模的解，通過遞推，獲得問題規(guī)模為i的解，直至得到問題規(guī)模為n的解。遞歸法：遞歸法：遞歸策略是利用函數(shù)直接或間接地調(diào)用自身來完成某個

6、計(jì)算過程。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出更大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出較大規(guī)模問題的解。窮舉法：窮舉法：窮舉搜索法也稱窮舉法或搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找出那些符合要求的候選解作為問題的解。迭代法：數(shù)值分析中通過從一個初始估

7、計(jì)出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。9.算法設(shè)計(jì)中的分治策略、貪心策略、動態(tài)規(guī)劃策略、回溯策略以及分支定界策略的基本思想是什么？分治策略分治策略的基本思想是把一個規(guī)模為n的問題劃分為若干個規(guī)模較小、且與原問題相似的子問題，然后分別求解這些子問題，最后把各子結(jié)果合并得到整個問題的解。分解的子問題通常與原問題相似，所以可以遞歸地使用分治策略來求解。貪心策略貪心策略的基本思

8、想是把一個整體最優(yōu)問題分解為一系列的最優(yōu)選擇問題，決策一旦做出，就不能再更改。它是通過若干次的貪心選擇而得出最優(yōu)解（或較優(yōu)解）的一種解題策略。動態(tài)規(guī)劃策略動態(tài)規(guī)劃策略與貪心策略類似，將一個問題劃分為重復(fù)的子問題，通過對相同子問題的求解來解決較大問題，即將一個問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪心策略中，每采用一次貪心準(zhǔn)則便做出一個不可撤回的決策，可能得不到問題的最優(yōu)解。而在動態(tài)規(guī)劃中，處理要按照某種規(guī)則進(jìn)行選擇，還要考察每