超碰人人揉人人捏人人添-97人人超碰国产精品-成人激情欧美国产第一页-亚洲欧美日韩中文字幕第一区

《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱

一、課程的性質(zhì)、目的與任務(wù)

《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門(mén)必修的專業(yè)基礎(chǔ)課。這門(mén)課程的主要特點(diǎn)是實(shí)踐性很強(qiáng),不僅要學(xué)習(xí)基本理論知識(shí),更要注重上機(jī)實(shí)踐,通過(guò)上機(jī)實(shí)踐驗(yàn)證算法的正確性,掌握和鞏固所學(xué)理論知識(shí)。設(shè)立本門(mén)課程的目的是通過(guò)學(xué)習(xí)，使學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步了解對(duì)算法的時(shí)間分析和空間分析技術(shù)。另一方面，通過(guò)對(duì)本課程算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能力，為后續(xù)課程，特別是軟件課程打下堅(jiān)實(shí)的知識(shí)基礎(chǔ)。要求學(xué)生掌握各種常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及有關(guān)操作的算法。

二、課程教學(xué)基本內(nèi)容與要求

第一章、緒論

（一）基本教學(xué)內(nèi)容：

1.1 什么是數(shù)據(jù)結(jié)構(gòu)

1.2 基本概念與術(shù)語(yǔ)

1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

1.4 算法與算法分析

（二）基本要求

教學(xué)目的：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，了解抽象數(shù)據(jù)類型，了解算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析，了解算法的描述方法。

重點(diǎn)：據(jù)結(jié)構(gòu)的基本概念、算法描述、算法分析

難點(diǎn)：算法描述、算法分析

第二章、線性表

（一）基本教學(xué)內(nèi)容：

2.1 線性表的類型定義

2.2 線性表的順序表示與實(shí)現(xiàn)

2.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)

（二）基本要求

教學(xué)目的：理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說(shuō)明；掌握在順序表和鏈表上實(shí)現(xiàn)的插入、刪除和按值查找的算法；了解循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。

重點(diǎn)：線性表的定義及其運(yùn)算、組織形式、結(jié)構(gòu)特征和類型說(shuō)明、順序表和鏈表上實(shí)現(xiàn)的插入、刪除和按值查找的算法、循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作

難點(diǎn)：線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)相關(guān)算法、循環(huán)鏈表、雙(循環(huán))鏈表的插入、刪除等操作

第三章、棧和隊(duì)列

（一）基本教學(xué)內(nèi)容：

3.1 棧

3.2 棧的應(yīng)用舉例

3.3 棧與遞歸的實(shí)現(xiàn)

3.4 隊(duì)列

（二）基本要求

教學(xué)目的：理解棧的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)算的實(shí)現(xiàn)；理解隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。

重點(diǎn)：棧的存儲(chǔ)結(jié)構(gòu)、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、棧與隊(duì)列的應(yīng)用

難點(diǎn)：隊(duì)列的存儲(chǔ)結(jié)構(gòu)、棧與隊(duì)列的應(yīng)用

第四章、串

（一）基本教學(xué)內(nèi)容：

4.1 串類型的定義

4.2 串的表示與實(shí)現(xiàn)

4.3 串的模式匹配算法

4.4 串的操作應(yīng)用舉例

（二）基本要求

教學(xué)目的：了解串的邏輯定義；掌握用順序存儲(chǔ)串及堆存儲(chǔ)串時(shí)的特點(diǎn)及在這兩種存儲(chǔ)方式下基本操作的實(shí)現(xiàn)；了解改進(jìn)的模式匹配算法；

重點(diǎn)：串的存儲(chǔ)結(jié)構(gòu)、串的模式匹配

難點(diǎn)：串的存儲(chǔ)結(jié)構(gòu)、串的模式匹配

第五章、數(shù)組和廣義表

（一）基本教學(xué)內(nèi)容：

5.1 數(shù)組的定義

5.2 數(shù)組的順序表示與實(shí)現(xiàn)

5.3 矩陣的壓縮存儲(chǔ)

5.4 廣義表的定義

（二）基本要求

教學(xué)目的：掌握數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及特殊矩陣的存儲(chǔ)方式；了解稀疏矩陣的壓縮存儲(chǔ)方式—三元組表。

重點(diǎn)：數(shù)組的順序存儲(chǔ)結(jié)構(gòu)、.特殊矩陣的壓縮存儲(chǔ)方法

難點(diǎn)：.特殊矩陣的壓縮存儲(chǔ)方法

第六章、樹(shù)和二叉樹(shù)

（一）基本教學(xué)內(nèi)容：

6.1 樹(shù)的定義和基本術(shù)語(yǔ)

6.2 二叉樹(shù)

6.3 遍歷二叉樹(shù)和線索二叉樹(shù)

6.4 樹(shù)和森林

6.6赫夫曼樹(shù)及應(yīng)用

（二）基本要求

教學(xué)目的：深刻理解二叉樹(shù)的定義、性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹(shù)的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹(shù)的三種遍歷算法；掌握二叉樹(shù)的線索化方法；靈活運(yùn)用二叉樹(shù)的遍歷方法解決相關(guān)的應(yīng)用問(wèn)題。

重點(diǎn)：二叉樹(shù)的定義，性質(zhì)，基本運(yùn)算和存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的遍歷和線索二叉樹(shù)、Huffman樹(shù)及應(yīng)用

難點(diǎn)：二叉樹(shù)的遍歷和線索二叉樹(shù)、Huffman樹(shù)及應(yīng)用

第七章、圖

（一）基本教學(xué)內(nèi)容：

7.1 圖的定義和術(shù)語(yǔ)

7.2 圖的存儲(chǔ)結(jié)構(gòu)

7.3 圖的遍歷

7.4 圖的連通性

7.5有向無(wú)環(huán)圖及其應(yīng)用

7.6最短路徑

（二）基本要求

教學(xué)目的：理解圖的基本概念及術(shù)語(yǔ)；掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)方法；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹(shù)的概念，能按Prim算法構(gòu)造最小生成樹(shù)；領(lǐng)會(huì)拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑的算法思想。

重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)、圖的遍歷、圖的連通性問(wèn)題

難點(diǎn)：有向無(wú)環(huán)圖及其應(yīng)用

第九章、查找

（一）基本教學(xué)內(nèi)容：

9.1 靜態(tài)查找表

9.2 動(dòng)態(tài)查表

9.3 哈希表

（二）基本要求

教學(xué)目的：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度；理解并掌握二叉排序樹(shù)的各種算法；

重點(diǎn)：.動(dòng)態(tài)查找表、哈希表

難點(diǎn)：動(dòng)態(tài)查找表、哈希表

十、內(nèi)部排序

（一）基本教學(xué)內(nèi)容：

10.1 概述

10.2 插入排序

10.3 快速排序

10.4 選擇排序

10.5 歸并排序

10.6 基數(shù)排序

10.7 各種內(nèi)部排序方法的比較討論

（二）基本要求

教學(xué)目的：領(lǐng)會(huì)排序的基本思想和基本概念；理解并掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟和時(shí)空效率分析；

三、課程各章節(jié)學(xué)時(shí)分配

四、本課程課外學(xué)習(xí)與修學(xué)指導(dǎo)

本課程強(qiáng)調(diào)理論和實(shí)踐的結(jié)合，突出對(duì)學(xué)生的動(dòng)手能力的培養(yǎng)。在對(duì)學(xué)生進(jìn)行基本數(shù)據(jù)結(jié)構(gòu)的技術(shù)、理論、設(shè)計(jì)等各種技能培養(yǎng)的同時(shí)，培養(yǎng)學(xué)生將實(shí)際問(wèn)題轉(zhuǎn)化為基本數(shù)據(jù)結(jié)構(gòu)的問(wèn)題的分析能力，鼓勵(lì)學(xué)生學(xué)以致用，將學(xué)到的知識(shí)用以解決實(shí)際問(wèn)題，從而提高學(xué)生算法設(shè)計(jì)能力和軟件開(kāi)發(fā)能力。

由于該課程涉及數(shù)據(jù)的各種組織方法，內(nèi)容復(fù)雜，難度較大，且具有很強(qiáng)的實(shí)踐性，所以要學(xué)好本課程，必須做到理論與實(shí)踐緊密結(jié)合，才能達(dá)到較好的學(xué)習(xí)效果。要求學(xué)生多參閱相關(guān)書(shū)籍，多做練習(xí)，多上機(jī)實(shí)驗(yàn)，掌握算法的基本原理及其實(shí)現(xiàn)過(guò)程。

五、本課程考核方式及成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)

考核方式：閉卷考試

成績(jī)?cè)u(píng)定方法：本課程的考核是平時(shí)成績(jī)、上機(jī)考試和期終考試成績(jī)相結(jié)合。具體比例為：平時(shí)（出勤、作業(yè)）20%，上機(jī)考試占20%，期末考試成績(jī)占60%。

其中期未考試總分100分，基礎(chǔ)題占50%，中等難度題占40%，較難題占10%?？荚囶}型主要有：選擇題、填空題、簡(jiǎn)單算法應(yīng)用題、算法填空題、算法設(shè)計(jì)等。

六、教學(xué)參考書(shū)

[1]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.北京：清華大學(xué)出版社.2006,4

[2]Sartaj Sahni. Data Structure, Algorithms, and Application in C++. The McGraw-Hill Company Inc.2006(數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用——C++語(yǔ)言描述.北京:機(jī)械工業(yè)出版社.2006)

[3]Willan Ford,Willian Topp. Data Structures with C++. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996(數(shù)據(jù)結(jié)構(gòu)——C++語(yǔ)言描述.北京:清華大學(xué)出版社，1997)

[4]徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C/C++描述）.北京:清華大學(xué)出版社.2010,12

[5]陳慧南.數(shù)據(jù)結(jié)構(gòu)（使用C++語(yǔ)言描述）.南京:東南大學(xué)出版社.2010,1

[6]殷人昆,陶永雷,謝若陽(yáng)等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）.北京:清華大學(xué)出版社.2002,7

大綱撰寫(xiě)人：朱素英

大綱審閱人：羅如為

教學(xué)副主任：易葉青

編寫(xiě)日期：2012.6