數據結構、算法與應用c++語言描述習題參考答案doc

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

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

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

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

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

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

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

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