數(shù)據(jù)結(jié)構(gòu)的知識點分布

1.數(shù)據(jù)結(jié)構(gòu)課程理論教學(xué)的知識點分布及學(xué)時安排數(shù)據(jù)結(jié)構(gòu)(課程編碼：T1040060),總學(xué)時為60學(xué)時，其中講課學(xué)時為38學(xué)時、習(xí)題學(xué)時為2學(xué)時、實驗學(xué)時為20學(xué)時。各知識點內(nèi)容及相應(yīng)學(xué)時如下詳示：第1章緒論(1學(xué)時)(1)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用范疇，數(shù)據(jù)結(jié)構(gòu)在軟件體系中的地位和作用；(2)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語；(3)抽象數(shù)據(jù)類型(ADT)的概念；(4)算法的時間復(fù)雜性和空間復(fù)雜性分析方法。第2章線性表(4學(xué)時)(1)線性表的邏輯結(jié)構(gòu)特性和線性表的抽象數(shù)據(jù)類型(ADT)的設(shè)計；(2)線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)方法；(3)順序存儲實現(xiàn)中的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法；(4)鏈?zhǔn)酱鎯崿F(xiàn)中單鏈表的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法；(5)雙向鏈表的插入和刪除等基本操作及相關(guān)算法；(6)循環(huán)鏈表的特點及創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法。(7)一元多項式的表示方法及相加算法。第3章棧與隊列(3學(xué)時)(1)棧與隊列的定義、特點和性質(zhì)；(2)棧、隊列的設(shè)計和實現(xiàn)以及基本操作及相關(guān)算法。(3)棧和隊列在表達式求值、括號匹配、數(shù)制轉(zhuǎn)換、迷宮求解中的應(yīng)用。第4章串(2學(xué)時)(1)串的定義、性質(zhì)和特點；(2)串的設(shè)計、實現(xiàn)方法和基本操作；(3)串的樸素模式匹配算法，KMP算法。第5章數(shù)組和廣義表(2學(xué)時)(1)數(shù)組的存儲表示方法；(2)數(shù)組在存儲結(jié)構(gòu)中的地址計算方法；(3)特殊矩陣壓縮存儲時的下標(biāo)變換公式；(4)稀疏矩陣的兩種壓縮存儲方法；(5)以三元組表示稀疏矩陣時進行矩陣運算采用的算法；(6)廣義表的定義、特點和性質(zhì)。第6章樹和二叉樹(8學(xué)時)(1)二叉樹的定義、結(jié)構(gòu)特點和性質(zhì)；(2)二叉樹的設(shè)計和實現(xiàn)，二叉樹存儲結(jié)構(gòu)的特點，三種遍歷方式的遞歸和非遞歸算法。(3)二叉樹的線索化過程和算法；(4)樹的設(shè)計和實現(xiàn)、樹的各種表示方法及基本術(shù)語，樹和森林與二叉樹的轉(zhuǎn)換方法；(5)最優(yōu)二叉樹的特性及建立最優(yōu)二叉樹和哈夫曼編碼的方法。第7章圖(8學(xué)時)(1)圖的定義、術(shù)語和性質(zhì)；(2)圖的設(shè)計和實現(xiàn)；(3)圖的鄰接矩陣、鄰接表的存儲結(jié)構(gòu)及其構(gòu)造方法；(4)圖的兩種遍歷方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；(5)最小生成樹的算法、拓?fù)渑判虻乃惴ǎ?6)關(guān)鍵路徑的算法，構(gòu)造最短路徑的Dijkstra算法和Floyd算法。第8章查找(4學(xué)時)(1)順序表和有序表的查找方法；(2)二叉排序樹的構(gòu)造方法和查找方法；(3)二叉排序樹結(jié)點的刪除算法；(4)二叉平衡樹的構(gòu)造方法；(5)哈希表的構(gòu)造方法；(6)各種查找方法的前提要求、各種查找算法的優(yōu)缺點、各種查找算法的時間復(fù)雜性。第9章排序(6學(xué)時)(1)簡單插入排序、希爾排序、快速排序、選擇排序、堆排序、歸并排序、基數(shù)排序算法；(2)各種排序算法的特點、時間復(fù)雜性、空間復(fù)雜性和“穩(wěn)定性”分析。習(xí)題課（2學(xué)時）線性結(jié)構(gòu)（包括線性表、棧和隊列、串、數(shù)組和廣義表）教學(xué)完成后安排1學(xué)時習(xí)題課，整個教學(xué)完成后安排1學(xué)時習(xí)題課?！稊?shù)據(jù)結(jié)構(gòu)》全課程的整體拓?fù)鋱D如圖4-1所示。排序知識點：簡單插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數(shù)排序的排序知識點：簡單插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數(shù)排序的存儲結(jié)構(gòu)特點和實現(xiàn)算法，以上排序算法的優(yōu)缺點以及它們的時間復(fù)雜性、空間復(fù)雜性和穩(wěn)定性分析。知識點:線性表的邏輯結(jié)構(gòu)特點、順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、創(chuàng)建、查找、插入和刪除算法。線性表數(shù)據(jù)結(jié)構(gòu)拓?fù)鋱D概念、術(shù)語、算法線性結(jié)構(gòu)非線性結(jié)構(gòu)應(yīng)用知識點:數(shù)據(jù)結(jié)構(gòu)的應(yīng)用范疇、在軟件體系中的地位和作用、抽象數(shù)據(jù)類型、算法的時間復(fù)雜性和空間復(fù)雜性分析方法。數(shù)組和廣義表棧和隊列串知識點：棧和隊列的定義、性質(zhì)、特點、存儲結(jié)構(gòu)和基本操作的實現(xiàn)、棧和隊列的應(yīng)用。知識點：串的定義、性質(zhì)和特點，存儲結(jié)構(gòu)和基本操作的實現(xiàn)，串的模式匹配算法。知識點：數(shù)組的存儲結(jié)構(gòu)，三角矩陣、稀疏矩陣的壓縮存儲方法，廣義表的定義、性質(zhì)、特點和存儲結(jié)構(gòu)。圖形結(jié)構(gòu)樹形結(jié)構(gòu)知識點：樹和二叉樹的定義、特點、性質(zhì)，存儲結(jié)構(gòu)和實現(xiàn)方法，二叉樹的前序、中序和后序遍歷的遞歸和非遞歸算法，線索二叉樹的特點、性質(zhì)和實現(xiàn)算法，樹和森林與二叉樹的轉(zhuǎn)換算法，最優(yōu)二叉樹的特性及實現(xiàn)算法，Huffman編碼的特點和實現(xiàn)算法。知識點：圖的定義、術(shù)語、性質(zhì)和特點，圖的鄰接矩陣和鄰接表的存儲實現(xiàn)和特點，圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法，連通圖的最小生成樹算法，有向無環(huán)圖的拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法，圖的最短路徑算法中的Dijkstra算法和Floye