數(shù)據結構熊回香習題答案(全)

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

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

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

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

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

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

7、em,(L.listsize+L.incrementsize)*sizeof(ElemType)); if(!L.elem) return false; // 存儲分配失敗 L.listsize+=L.incrementsize; // 當前存儲容量增加 } 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