數(shù)據(jù)結(jié)構(gòu)課程標(biāo)準(zhǔn)精品精編資料

1、數(shù)據(jù)結(jié)構(gòu)課程標(biāo)準(zhǔn)（?？疲┮?、課程的性質(zhì)：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門必修專業(yè)基礎(chǔ)課，它是一門理論性強(qiáng)，但有一定的實(shí)踐性和較強(qiáng)實(shí)用性的基礎(chǔ)課程。二、課程的教學(xué)目的與任務(wù)：本課程的任務(wù)是討論數(shù)據(jù)的各種邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及有關(guān)操作的算法。目的是使學(xué)生掌握分析研究計(jì)算機(jī)加工的數(shù)據(jù)對象的特性，以便對所要處理的數(shù)據(jù)對象選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，并在此基礎(chǔ)上掌握對這些數(shù)據(jù)的操作（查找、插入、刪除和修改等）。同時(shí)培養(yǎng)學(xué)生運(yùn)用C語言編寫結(jié)構(gòu)清晰、正確易讀的算法，并具備初步評價(jià)算法的能力，為學(xué)生今后繼續(xù)學(xué)習(xí)和研究打下堅(jiān)實(shí)的基礎(chǔ)。三、課程的教學(xué)手段和方法：本課程理論講授采用教材與多媒體相配合的教學(xué)手段。本課程包

2、括課堂教學(xué)與實(shí)踐教學(xué)兩大部分。 課堂教學(xué)在方法上， 采用課堂講授、 課后自學(xué)、 課堂討論、課外作業(yè) 、平時(shí)測驗(yàn)等教學(xué)形式。實(shí)踐教學(xué)部分主要是實(shí)驗(yàn)。四、課程內(nèi)容及學(xué)時(shí)分配（共 72 學(xué)時(shí) , 其中講課60 學(xué)時(shí) , 實(shí)驗(yàn) 12 學(xué)時(shí)）：第一部分講授內(nèi)容（ 60 學(xué)時(shí)）第一章緒論（共4 學(xué)時(shí)）第一節(jié)有關(guān)概念和術(shù)語（2 學(xué)時(shí)）一、基本要求：掌握數(shù)據(jù)結(jié)構(gòu)的一些基本概念，了解抽象數(shù)據(jù)類型的定義和使用。二、 教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系。教學(xué)難點(diǎn)是什么是數(shù)據(jù)的邏輯結(jié)構(gòu)及物理結(jié)構(gòu)？三、講授內(nèi)容：（一）數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)

3、邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)類型、算法等。（二）抽象數(shù)據(jù)類型。四、思考題：舉出一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、結(jié)構(gòu)上的操作內(nèi)容。第二節(jié)算法及算法分析（2 學(xué)時(shí)）一、基本要求：掌握算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法，了解算法的描述方法。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是算法的各種描述方法和算法分析（時(shí)間復(fù)雜度及空間復(fù)雜度）。教學(xué)難點(diǎn)是對一個(gè)算法時(shí)間復(fù)雜度的分析。三、講授內(nèi)容：（一）描述算法所用的C 語言中的一些有關(guān)問題。（二）算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。四、思考題：編寫算法，求一元多項(xiàng)式 Pn(x)=a 0+a1x+a2x2+a3x3+anxn 的值 Pn(x 0) ，要求時(shí)

4、間復(fù)雜度盡可能小。第二章 線性表（ 12 學(xué)時(shí)）第一節(jié)線性表的順序存儲結(jié)構(gòu)（學(xué)時(shí)）一、基本要求：理解線性表的定義和基本操作；掌握數(shù)組的存儲（例如：數(shù)組元素在內(nèi)存位置的計(jì)算方法）和在順序存儲結(jié)構(gòu)上的基本操作（如插入、刪除、合并、劃分和比較等）的實(shí)現(xiàn)。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是線性表的邏輯結(jié)構(gòu)、線性表的順序存儲存構(gòu)C 語言描述、基本操作實(shí)現(xiàn)方法和簡單應(yīng)用。教學(xué)難點(diǎn)是用C 語言實(shí)現(xiàn)基本操作和如何通過順序存儲結(jié)構(gòu)解決實(shí)際問題。三、講授內(nèi)容：（一）線性表的定義和基本操作；（二）線性表的順序存儲結(jié)構(gòu)；（三）定義在順序存儲結(jié)構(gòu)上的基本操作的實(shí)現(xiàn)；（四）應(yīng)用舉例及分析。四、思考題：設(shè)有兩個(gè)按元素值遞增有序

5、順序表A 和 B，編一程序?qū) 表和 B 表歸并成一個(gè)新的遞增有序的順序表C（值相同的元素均保留在C 表中）。第二節(jié)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（學(xué)時(shí)）一、基本要求：掌握單鏈表的基本結(jié)構(gòu)及基本操作（如建立、查找、插入和刪除等）；掌握循環(huán)鏈表和雙向鏈表；能用單鏈表解決一些實(shí)際問題。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是順序存儲結(jié)構(gòu)及鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)，如何用 C 語言實(shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)，單鏈表上基本操作的實(shí)現(xiàn)，各種鏈表的結(jié)構(gòu)：循環(huán)鏈表，雙向鏈表和單鏈表的一些簡單應(yīng)用。教學(xué)難點(diǎn)是單鏈表上基本操作的實(shí)現(xiàn)和建立在鏈表上的一些應(yīng)用。三、講教內(nèi)容：（一）鏈?zhǔn)酱鎯Y(jié)構(gòu)的實(shí)現(xiàn)方法；（二）單鏈表的基本操作；（三）循環(huán)鏈表及雙向

6、鏈表的實(shí)現(xiàn)；（四）應(yīng)用舉例。四、思考題：分析單鏈表、循環(huán)鏈表和雙向鏈表的相同點(diǎn)、不同點(diǎn)及各自的特點(diǎn)。第三章 棧和隊(duì)列（ 8 學(xué)時(shí)）第一節(jié)棧（ 4 學(xué)時(shí)）一、基本要求：掌握棧的定義，掌握順序和鏈?zhǔn)酱鎯Φ臈５幕静僮鲗?shí)現(xiàn)。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是棧的邏輯結(jié)構(gòu)定義，用C 語言實(shí)現(xiàn)棧的兩種方式：順序存儲結(jié)構(gòu)及鏈?zhǔn)酱鎯Y(jié)構(gòu)，棧的基本操作的實(shí)現(xiàn)。教學(xué)難點(diǎn)是棧的基本操作的實(shí)現(xiàn)和一些具體應(yīng)用。三、講授內(nèi)容：（一）棧的定義及基本運(yùn)算；（二）棧的順序存儲和鏈接存儲的表示；（三）在棧的順序存儲和鏈接存儲上進(jìn)行各種棧操作的算法；（四）棧的應(yīng)用舉例。四、思考題：求 2 階 Fibonacci 數(shù)列的遞歸算法。第二

7、節(jié) 對（ 4 學(xué)時(shí)）一、基本要求：掌握隊(duì)列的定義、順序存儲及鏈接存儲時(shí)的操作，掌握順序存儲下循環(huán)隊(duì)列的插入、刪除運(yùn)算算法。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是隊(duì)列的邏輯定義，用 C 語言實(shí)現(xiàn)隊(duì)列的兩種方式：順序存儲結(jié)構(gòu)及鏈?zhǔn)酱鎯Y(jié)構(gòu)，隊(duì)列的基本操作實(shí)現(xiàn)和循環(huán)隊(duì)列的實(shí)現(xiàn)。教學(xué)難點(diǎn)是隊(duì)列的基本操作的實(shí)現(xiàn)和循環(huán)隊(duì)列的實(shí)現(xiàn)方式。三、講授內(nèi)容：（一） 隊(duì)列的類型定義；（二）隊(duì)列的順序存儲 ( 循環(huán)隊(duì) ) 表示及各種操作的實(shí)現(xiàn)算法；（三）隊(duì)列的鏈接存儲表示及各種操作的實(shí)現(xiàn)算法。四、思考題：隊(duì)列管理的模擬算法（隊(duì)列采用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)）。第四章串和數(shù)組（ 4 學(xué)時(shí)）第一節(jié)串（ 2 學(xué)時(shí)）一、基本要求：理解串的定

8、義和基本操作， 掌握用 C 語言如何實(shí)現(xiàn)物理存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)及堆結(jié)構(gòu)和串的合并、定位、比較算法。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是串的物理存儲結(jié)構(gòu)和串的基本操作的實(shí)現(xiàn)。教學(xué)難點(diǎn)是串的堆分配結(jié)構(gòu)。三、講授內(nèi)容：（一）串的類型定義；（二）串的存儲結(jié)構(gòu)；（三）串的基本操作的實(shí)現(xiàn)。四、思考題：設(shè) s 和 t 是表示成單鏈表的兩個(gè)串，試編寫一個(gè)找出s 中第 1 個(gè)不在 t 中出現(xiàn)的字符（假定每個(gè)結(jié)點(diǎn)只存放 1 個(gè)字符）的算法。第二節(jié)數(shù)組（ 2 學(xué)時(shí)）一、基本要求：掌握二維數(shù)組的存儲結(jié)構(gòu)和稀疏矩陣的壓縮存儲。了解稀疏矩陣的轉(zhuǎn)置算法。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是矩陣的向量存儲結(jié)構(gòu)和稀疏矩陣的壓縮存儲。

9、教學(xué)難點(diǎn)是稀疏矩陣的壓縮存儲。三、講授內(nèi)容：（一）二維數(shù)組的存儲結(jié)構(gòu)；（二）稀疏矩陣；（三）應(yīng)用舉例。四、思考題：稀疏矩陣轉(zhuǎn)置算法。第五章樹和二叉樹（10 學(xué)時(shí)）第一節(jié)二叉樹（ 6 學(xué)時(shí)）一、基本要求：掌握樹的定義，相關(guān)術(shù)語及基本操作；掌握二叉樹的定義，性質(zhì)，存儲結(jié)構(gòu)，基本操作和二叉樹的遍歷。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是樹的定義，二叉樹的定義、 性質(zhì)、存儲結(jié)構(gòu)、 基本操作和遍歷。教學(xué)難點(diǎn)是二叉樹的性質(zhì)。三、講授內(nèi)容：（一）樹的概念與基本操作；（二）二叉樹的定義、性質(zhì)；（三）二叉樹的存儲結(jié)構(gòu)；（四）二叉樹的遍歷；（五）二叉樹的舉例四、思考題：建立二叉樹并寫出其前序遍歷、中序遍歷的非遞歸算法。第

10、二節(jié)樹與森林（ 4 學(xué)時(shí)）一、基本要求：掌握樹的存儲結(jié)構(gòu)，樹、森林與二叉樹的轉(zhuǎn)化，樹和森林的遍歷；掌握哈夫曼樹和哈夫曼編碼。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是樹、森林與二叉樹的轉(zhuǎn)化，樹和森林的遍歷操作，哈夫曼樹。教學(xué)難點(diǎn)是樹的存儲結(jié)構(gòu)，樹、森林與二叉樹的轉(zhuǎn)化和哈夫曼樹。三、講授內(nèi)容：（一）樹的存儲結(jié)構(gòu)；（二）樹、森林與二叉樹的轉(zhuǎn)化；（三）樹和森林的遍歷；（四）哈夫曼樹的定義、構(gòu)造哈夫曼樹的方法；（五）哈夫曼編碼的方法。四、思考題：在以孩子兄第鏈表結(jié)構(gòu)存儲的樹中，寫出求樹中結(jié)點(diǎn)孩子的算法。第六章圖（ 8 學(xué)時(shí)）第一節(jié)圖的存儲和遍歷（4 學(xué)時(shí)）一、基本要求：掌握圖的定義和術(shù)語，圖的存儲表示和遍歷方式。

11、二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是圖的定義和術(shù)語，圖的存儲結(jié)構(gòu)，圖的遍歷。教學(xué)難點(diǎn)是圖的存儲結(jié)構(gòu)和圖的遍歷方式。三、講授內(nèi)容：（一）圖的定義和術(shù)語；（二）圖的鄰接矩陣和鄰接表表示；（三）圖的深度和廣度優(yōu)先查找。四、思考題：編寫算法：在無向圖的鄰接距陣結(jié)構(gòu)上，生成無向圖的鄰接鏈表結(jié)構(gòu)。第二節(jié)圖的應(yīng)用（ 4 學(xué)時(shí)）一、基本要求：掌握圖的生成樹及最小生成樹，求最短路徑，拓?fù)渑判颉６?、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是最小生成樹問題，最短路徑問題，拓?fù)渑判虻姆椒?。教學(xué)難點(diǎn)是最小生成樹問題和求最短路徑。三、講授內(nèi)容：（一）圖的生成樹和最小生成樹；（二）最短路徑；（三）拓?fù)渑判颉Ｋ?、思考題：對于一個(gè)具有n 個(gè)頂點(diǎn)和e

12、 條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為_和 _。關(guān)鍵路徑是什么？第七章查找（ 6 學(xué)時(shí)）第一節(jié)靜態(tài)查找和動態(tài)查找（3 學(xué)時(shí)）一、基本要求：掌握查找的基本方式；掌握靜態(tài)表上順序查找，有序表的折半查找和分塊查找；掌握動態(tài)查找：二叉排序樹的生成和插入，二叉排序樹上的查找。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是順序查找，有序表的折半查找，查找成功查找長度分析和二叉排序樹上的查找。教學(xué)難點(diǎn)是成功查找及不成功查找分析。三、講授內(nèi)容：（一）靜態(tài)查找：順序查找，有序表的折半查找和分塊查找；（二）動態(tài)查找：二叉排序樹上的查找。四、思考題：對長度為10的有序表進(jìn)行折半查找的判定樹，并求其等概時(shí)查找成功的平均查找長

13、度。第二節(jié)哈希表（ 3 學(xué)時(shí)）一、基本要求：掌握哈希表的查找方式, 常用哈希函數(shù)的構(gòu)造方法，解決沖突的主要方法，哈希表的查找及性能分析。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是哈希表的查找方式, 哈希函數(shù)的構(gòu)造，解決沖突的方法，哈希表的查找及性能分析。教學(xué)難點(diǎn)是哈希表的查找和如何解決沖突。三、講授內(nèi)容：（一）哈希表和哈希方法；（二）常用哈希函數(shù)的構(gòu)造方法；（三）處理沖突的方法；（四）哈希表的查找及性能分析。四、思考題：為什么說當(dāng)裝填因子非常接近1 時(shí)，線性探查類似于順序查找?為什么說當(dāng)裝填因子比較小( 比如 =0.7 左右 ) 時(shí)，散列查找的平均查找時(shí)間為O(1)?第七章排序（ 8 學(xué)時(shí)）一、基本要求：

14、掌握直接插入排序、冒泡排序、簡單選擇排序的方法及其實(shí)現(xiàn)；掌握快速排序、堆排序、二路歸并排序的方法；掌握各種排序方法的穩(wěn)定性、時(shí)間復(fù)雜度和空間復(fù)雜度。二、教學(xué)重點(diǎn)及難點(diǎn)：本節(jié)重點(diǎn)是各種排序（直接插入排序，冒泡排序，簡單選擇排序，快速排序，堆排序，歸并排序和基數(shù)排序）及時(shí)間復(fù)雜度分析。教學(xué)難點(diǎn)是各種排序方法的優(yōu)缺點(diǎn)及時(shí)間復(fù)雜度分析。三、講授內(nèi)容：（一）直接插入排序；（二）冒泡排序；（三）直接選擇排序；（四）快速排序；（五）堆排序；（六）歸并排序；（七）基數(shù)排序。四、思考題：試比較直接插入排序、簡單選擇排序、快速排序、堆排序、歸并排序、希爾排序和基數(shù)排序的時(shí)空性能、穩(wěn)定性和適用情況。第二部分 實(shí)驗(yàn)內(nèi)

15、容（ 12 學(xué)時(shí)）1.線性表操作插入、刪除、合并、查找（4 學(xué)時(shí)）2.樹和二叉樹的應(yīng)用建立二叉樹、遍歷二叉樹（2 學(xué)時(shí)）3.圖的應(yīng)用尋找兩頂點(diǎn)間邊數(shù)最少的一條路徑（2 學(xué)時(shí)）4.查找靜態(tài)、動態(tài)查找算法（2 學(xué)時(shí)）5.排序數(shù)組、鏈表排序算法（2 學(xué)時(shí)）五、開課時(shí)間（時(shí)長）、規(guī)定學(xué)時(shí)及成績考核、評定方式：本課程開課時(shí)長 : 一學(xué)期；規(guī)定學(xué)時(shí)： 72 學(xué)時(shí) , 其中講課 60 學(xué)時(shí) , 實(shí)驗(yàn) 12學(xué)時(shí)；本課程的考核以閉卷考試進(jìn)行，總成績：平時(shí)成績占30%，期末閉卷考試占70% 。六、使用教材及主要參考書、參考文獻(xiàn)：教材：數(shù)據(jù)結(jié)構(gòu)（C 語言版）鄧文華李益明編著電子工業(yè)出版社參考書：1數(shù)據(jù)結(jié)構(gòu) （ C語言版）嚴(yán)蔚敏吳偉民編著清華大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)題集 （ C語言版）嚴(yán)蔚敏吳偉民編著清華