數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)提要 - 廣西廣播電視大學(xué)

1、數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)提要數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)提要1數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)提要中央電大理工部計算機(jī)教研室數(shù)據(jù)結(jié)構(gòu)是99級計算機(jī)應(yīng)用專業(yè)一門統(tǒng)設(shè)必修課和專業(yè)基礎(chǔ)課，它主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)，在計算機(jī)中的存儲結(jié)構(gòu)，對數(shù)據(jù)進(jìn)行的插入、查找、刪除、排序、遍歷等運(yùn)算和不同方法，這些運(yùn)算在存儲結(jié)構(gòu)上具體實(shí)現(xiàn)的算法。學(xué)習(xí)好該課程將為學(xué)好整個計算機(jī)專業(yè)打下堅實(shí)的基礎(chǔ)。第一部分第一部分各章復(fù)習(xí)要求各章復(fù)習(xí)要求下面按照主教材中各章次序給出每章的具體復(fù)習(xí)要求，以便指導(dǎo)同

2、學(xué)們更好地進(jìn)行期末復(fù)習(xí)。第一章緒論重點(diǎn)掌握的內(nèi)容：1.數(shù)據(jù)結(jié)構(gòu)的二元組表示，對應(yīng)的圖形表示，序偶和邊之間的對應(yīng)關(guān)系。2.集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)的特點(diǎn)。3.抽象數(shù)據(jù)類型的定義和表示方法。4.一維和二維數(shù)組中元素的按下標(biāo)和按地址的訪問方式以及相互轉(zhuǎn)換，元素地址和數(shù)組地址的計算，元素占用存儲空間大小和數(shù)組占用存儲空間大小的計算。5.普通函數(shù)重載和操作符函數(shù)重載的含義，定義格式和調(diào)用格式。6.函數(shù)定義中值參數(shù)和引用參數(shù)的說明格式及作

3、用，函數(shù)被調(diào)用執(zhí)行時對傳送來的實(shí)際參數(shù)的影響。7.算法的時間復(fù)雜度和空間復(fù)雜度的概念，計算方法，數(shù)量級表示。8.一個簡單算法的最好、最差和平均這三種情況的時間復(fù)雜度的計算。對于本章的其余內(nèi)容均作一般掌握。第二章線性表重點(diǎn)掌握的內(nèi)容：1.線性表的定義和抽象數(shù)據(jù)類型的描述，線性表中每一種操作的功能，對應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個參數(shù)的作用。2.線性表的順序存儲結(jié)構(gòu)的類型定義，即List類型的定義和每個域的定義及作用。3.線性表的每一

4、種運(yùn)算在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)的算法，及相應(yīng)的時間復(fù)雜度。4.鏈接存儲的概念，線性表的單鏈接和雙鏈接存儲的結(jié)構(gòu)，向單鏈表中一個結(jié)點(diǎn)之后插入新結(jié)點(diǎn)或從單鏈表中刪除一個結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針鏈接過程。5.單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)，每個域的定義及作用，即LNode類型的定義及結(jié)構(gòu)。6.帶表頭附加結(jié)點(diǎn)的鏈表、循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點(diǎn)。7.線性表的每一種運(yùn)算在單鏈表上實(shí)現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。8.在順序存儲或鏈接存儲的線性表上實(shí)現(xiàn)指定功能的算法的分析

5、和設(shè)計。對于本章的其余內(nèi)容均作一般掌握。第三章稀疏矩陣和廣義表重點(diǎn)掌握的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)提要數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)提要3對于本章的其余內(nèi)容均作一般掌握。第六章二叉樹的應(yīng)用重點(diǎn)掌握的內(nèi)容：1.二叉搜索樹的定義和性質(zhì)。2.二叉搜索樹查找的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，查找一個元素的查找長度，即從樹根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)數(shù)。3.二叉搜索樹插入的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，根據(jù)一組數(shù)據(jù)生成一棵二叉搜索樹的過程。4.堆

6、的定義和順序存儲結(jié)構(gòu)，小根堆和大根堆的異同。5.向堆中插入元素的過程、算法描述及時間復(fù)雜度。6.從堆中刪除元素的過程、算法描述及時間復(fù)雜度。7.哈夫曼樹的定義，樹的帶權(quán)路徑長度的計算，根據(jù)若干個葉子結(jié)點(diǎn)的權(quán)構(gòu)造哈夫曼樹的過程。對本章的其余內(nèi)容均作一般了解。第七章圖重點(diǎn)掌握的內(nèi)容：1.圖的頂點(diǎn)集和邊集的表示。2.圖的一些概念的含義，如頂點(diǎn)、邊、度、完全圖、子圖、路徑、路徑長度、連通圖、權(quán)、網(wǎng)等。3.圖的鄰接矩陣、鄰接表和邊集數(shù)組三種存儲結(jié)

7、構(gòu)及相應(yīng)的空間復(fù)雜度。4.存儲圖使用的vexlistadjmatrixadjlistedgenodeedgesetedge等類型的定義及用途。5.圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過程。6.對分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行深度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時間復(fù)雜度。7.對分別用鄰接矩陣和用鄰接表表示的圖進(jìn)行廣度優(yōu)先搜索遍歷的過程、算法描述以及相應(yīng)的時間復(fù)雜度。8.圖的生成樹、生成樹的權(quán)、最小生成樹等的定義。9.根據(jù)普里姆算

8、法求圖的最小生成樹的過程和算法描述。10根據(jù)克魯斯卡爾算法求圖的最小生成樹的過程和算法描述。11.圖的拓?fù)湫蛄泻屯負(fù)渑判虻母拍?，求圖的拓?fù)湫蛄械姆椒?，對用鄰接表表示的圖進(jìn)行拓?fù)渑判虻倪^程和算法。對本章的其余內(nèi)容均作一般掌握。它包括建立圖的鄰接矩陣、鄰接表、邊集數(shù)組算法，建立圖的逆鄰接表和十字鄰接表等內(nèi)容。第八章查找重點(diǎn)掌握的內(nèi)容：1.在一維數(shù)組上進(jìn)行順序查找的過程、算法、平均查找長度和時間復(fù)雜度。2.在一維數(shù)組上進(jìn)行二分查找的過程、遞歸