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

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

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

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

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

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