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

1、第1章概論1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的含義分別是什么？數(shù)據(jù)：數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素：數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮。數(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ù)類型是用來(lái)區(qū)分不同的數(shù)據(jù)；由于數(shù)據(jù)在存儲(chǔ)時(shí)

2、所需要的容量各不相同，不同的數(shù)據(jù)就必須要分配不同大小的內(nèi)存空間來(lái)存儲(chǔ)，所有就要將數(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)包含下面兩個(gè)方面的信息：①數(shù)據(jù)元素的信息；②各數(shù)據(jù)元素之間的關(guān)系。物理結(jié)構(gòu)：物理結(jié)構(gòu)：也叫儲(chǔ)存結(jié)構(gòu)，是指邏輯結(jié)構(gòu)

3、的存儲(chǔ)表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式，包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲(chǔ)表示。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的，一個(gè)操作算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采與的存儲(chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，針對(duì)不同問(wèn)題，選擇合理的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)非常重要。3.數(shù)據(jù)結(jié)構(gòu)的主要操作包括哪些？對(duì)于各種數(shù)據(jù)結(jié)構(gòu)而言，他們?cè)诨静僮魃鲜窍嗨频模畛Ｓ玫牟僮饔校?創(chuàng)建：建

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

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

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

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

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