數(shù)據(jù)結(jié)構(gòu)熊回香習(xí)題答案(全)

1、習(xí)題一 習(xí)題一 一、選擇題 一、選擇題 1．B 2．C 3．B 4．D 5．C 6．D 7．A 8．C 二、填空題 二、填空題 1．?dāng)?shù)據(jù)元素 數(shù)據(jù)元素間關(guān)系 2. 數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體 3．有窮性 確定性 可行性 4．算法的時(shí)間復(fù)雜度和空間復(fù)雜度 5．集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 三、簡述題 三、簡述題 1．解答：

2、 四種表示方法。 ⑴順序存儲方式。數(shù)據(jù)元素順序存放，每個(gè)存儲結(jié)點(diǎn)只含一個(gè)元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。 ⑵鏈?zhǔn)酱鎯Ψ绞?。每個(gè)存儲結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等） ，但存儲空間開銷大（用于指針） ，另外不能折半查找等。 ⑶索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外

3、，尚需建立一個(gè)索引表，索引表中索引指示存儲結(jié)點(diǎn)的存儲位置（下標(biāo)）或存儲區(qū)間端點(diǎn)（下標(biāo)） ，兼有靜態(tài)和動態(tài)特性。 ⑷散列存儲方式。 通過散列函數(shù)和解決沖突的方法， 將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)， 并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址， 這種存儲方式稱為散列存儲。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。 2．解答： 數(shù)據(jù)類型是程序設(shè)計(jì)語言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。如 C 語

4、言中的整型、實(shí)型、字符型等，如整數(shù)的取值范圍與具體機(jī)器和編譯系統(tǒng)有關(guān)，其操作有加、減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。 “抽象數(shù)據(jù)類型（ADT） ”指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。 “抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。 抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性， 而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。 無論其內(nèi)部結(jié)構(gòu)如何變化， 只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)

5、類型實(shí)質(zhì)上是一個(gè)概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型， 還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、 表示和實(shí)現(xiàn)三部分， 封裝在一起， 對用戶透明 （提供接口） ， 而不必了解實(shí)現(xiàn)細(xì)節(jié)。 抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計(jì)不再是 “藝術(shù)” ， 而是向 “科學(xué)”邁進(jìn)了一步。 3．解答： 評價(jià)好的算法有四個(gè)方面。 一是算法的正確性； 二是算法的易讀性； 三是算法的健壯

6、性；四是算法的時(shí)空效率（運(yùn)行） 。 三、算法設(shè)計(jì)題 說明：三、算法設(shè)計(jì)題 說明：以下解答中有關(guān)順序表的習(xí)題要包含頭文件：SqList.h，單鏈表的習(xí)題要包含頭文件：LinkList.h。 1．算法描述如下： bool SLOrderInsert(SqList if(L.length>=L.listsize) { // 當(dāng)前存儲空間已滿，增補(bǔ)空間 L.elem=(ElemType)realloc(L.el

7、em,(L.listsize+L.incrementsize)*sizeof(ElemType)); if(!L.elem) return false; // 存儲分配失敗 L.listsize+=L.incrementsize; // 當(dāng)前存儲容量增加 } for(i=L.length-1;i>=0i--) L.elem[i+1]=L.elem[i]; L.elem[i+1]=x;

8、L.length++; return true; } 2．算法描述如下： void Converse_Sq(SqList ElemType x; mid=L.length/2; for(i=0;i<mid;i++) { x=L.elem[i]; L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x; } } 3．算法描述如下： void Converse2_Sq(Elem