《數(shù)據(jù)結(jié)構(gòu)與算法(徐鳳生)》習(xí)題答案

1、《數(shù)據(jù)結(jié)構(gòu)與算法》 《數(shù)據(jù)結(jié)構(gòu)與算法》習(xí)題答案 習(xí)題答案3習(xí)題 習(xí)題 11.解釋下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)。解：數(shù)據(jù)是用于描述客觀事物的數(shù)值、字符以及一切可以輸入到計算機(jī)中并由計算機(jī)程序加以處理的符號的集合，是計算機(jī)操作的對象的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它是數(shù)據(jù)中的一個“個體”。有時，一個數(shù)據(jù)元素可有若干數(shù)據(jù)項組成，。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)

2、結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的特性相同的數(shù)據(jù)元素的集合。2.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的？兩者有何異同？抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？解：數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱。例如，C 語言中的整型變量，其值為某個區(qū)間上的整數(shù)(依賴于機(jī)器)，定義在其上的操作為加、減、乘、除和取模等算術(shù)運算。抽象數(shù)據(jù)類型(Abstract Data Type，簡稱 ADT)是指一個數(shù)學(xué)模型以

3、及定義在此數(shù)學(xué)模型上的一組操作。例如，“整數(shù)”是一個抽象數(shù)據(jù)類型，其數(shù)學(xué)特性和具體的計算機(jī)或語言無關(guān)?！俺橄蟆钡囊饬x在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念，只是抽象數(shù)據(jù)類型的范圍更廣，除了已有的數(shù)據(jù)類型外，抽象數(shù)據(jù)類型還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。ADT 的定義取決于它的一組邏輯特性，與其在計算機(jī)內(nèi)的表示和實現(xiàn)無關(guān)。因此，不論 ADT 的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部的使

4、用。抽象數(shù)據(jù)類型的最重要的特點是抽象和信息隱蔽。抽象的本質(zhì)是抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細(xì)節(jié)，從而使所設(shè)計的數(shù)據(jù)結(jié)構(gòu)更具有一般性，可以解決一類問題。信息隱蔽就是對用戶隱蔽數(shù)據(jù)存儲和操作實現(xiàn)的細(xì)節(jié)，使用者僅需了解抽象操作，或界面服務(wù)，通過界面中的服務(wù)來訪問這些數(shù)據(jù)。一個含抽象數(shù)據(jù)類型的軟件模塊通常應(yīng)包含定義、表示和實現(xiàn)三部分。3.數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有幾種表示方法？各有什么特點？解：數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有四種不同的

5、表示方法：(1)順序存儲方法。數(shù)據(jù)元素順序存放，每個結(jié)點只含有一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作(如插入、刪除)效率較差。(2)鏈?zhǔn)酱鎯Ψ椒?。每個結(jié)點除包含數(shù)據(jù)元素信息外還包含一組指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種操作不要求存儲空間連續(xù)，便于進(jìn)行插入和刪除等操作，但存儲空間利用率較低。另外，由于邏輯上相鄰的數(shù)據(jù)元素在存儲空間上不一定相鄰，所以不能對其進(jìn)行隨機(jī)存取。(3)索引存儲方法。除數(shù)據(jù)元素存儲在