《數(shù)據(jù)結(jié)構(gòu)與算法(三)》課程教學(xué)大綱

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

一、課程基本口心、

數(shù)據(jù)結(jié)構(gòu)與算法

課程名稱

DataStructuresandAlgorithms

課程編碼OSI221511030開課院部海洋與空間信息學(xué)院課程團(tuán)隊(duì)智能應(yīng)用組

學(xué)分3.0課內(nèi)學(xué)時(shí)52講授40實(shí)驗(yàn)0上機(jī)12實(shí)踐0課外學(xué)時(shí)52

適用專業(yè)通信工程授課語(yǔ)言中文

先修課程程序設(shè)計(jì)（C/C++）

《數(shù)據(jù)結(jié)構(gòu)與算法》是一門綜合性的、重要的專業(yè)基礎(chǔ)課，是通信工程等專業(yè)的核心專業(yè)基礎(chǔ)課程。這些專業(yè)的任務(wù)是研究信息表示

和信息處理，即如何有效地表示和加工處理信息。一方面是發(fā)展硬件技術(shù)，另一方面是研究問題本身的特性，在計(jì)算機(jī)處理問題時(shí)能利用

這些特性來(lái)達(dá)到更有效處理的目的，后者就是數(shù)據(jù)結(jié)構(gòu)課程的研究?jī)?nèi)容。本課程的目標(biāo)是在學(xué)習(xí)高級(jí)語(yǔ)言程序設(shè)計(jì)等課程的基礎(chǔ)上，掌握

利用計(jì)算機(jī)解決問題的一般性方法（抽象數(shù)據(jù)類型定義、表示和實(shí)現(xiàn)）和常用算法，能培養(yǎng)學(xué)生的計(jì)算機(jī)思維（邏輯思維和抽象思維）能

力以及形式化思維方法，進(jìn)一步訓(xùn)練和強(qiáng)化學(xué)生的編程能力，逐步提升程序規(guī)模和運(yùn)行效率，為軟件開發(fā)奠定堅(jiān)實(shí)的基礎(chǔ)。

"DataStructureandAlgorithm'^isacomprehensiveandimportantmajorcourse,whichisforthemajorsofcommunicationengineering.Thetask

課程簡(jiǎn)介

ofthesemajorsistostudytherepresentationandprocessofinformation,thatistosay,howtorepresentandprocessinformationeffectively.Oneside

（必修）

istodevelopthehardwaretechnology;ontheothersideistostudythecharacteristicsoftheproblemitself,andthenthesecharacteristicscanbeused

toprocessinformationmoreefficient.Thus,thelatteristheresearchcontentofthiscourse.Thegoalofthiscourseistomasterthegeneralmethodsto

solveproblems(abstractdatatypedefinition,representationandImplementation)usingcomputerandsomecommonalgorithmsafterlearningthe

advancedprogramminglanguage,cultivatestudents'ComputationalThinking(logicalthinkingandabstractthinkingability)andformalthinking

method,andfurthertrainandstrengthenthestudentsprogrammingability,andgraduallyimprovetheprogramscaleandefficiency,tolayasolid

foundationforsoftwaredevelopment.

負(fù)責(zé)人大綱執(zhí)筆人審核人

二、課程目標(biāo)

畢業(yè)要求指標(biāo)點(diǎn)

序號(hào)代號(hào)課程目標(biāo)OBE

任務(wù)自選

1Ml深刻領(lǐng)會(huì)數(shù)據(jù)的不同存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)，全面理解不同數(shù)據(jù)結(jié)構(gòu)的基本概念，及常用算法的設(shè)計(jì)是2.1

思想和實(shí)現(xiàn)方法，比較識(shí)別不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)和應(yīng)用場(chǎng)景。

掌握利用計(jì)算機(jī)軟件解決問題的思維方式及方法，對(duì)問題進(jìn)行建模，培養(yǎng)學(xué)生的計(jì)算機(jī)抽象思維能

2M2是2.2

力，進(jìn)一步訓(xùn)練和強(qiáng)化學(xué)生的建模能力，為軟件開發(fā)奠定堅(jiān)實(shí)的基礎(chǔ)。

3M3培養(yǎng)學(xué)生檢索先進(jìn)算法相關(guān)的文獻(xiàn)能力，并能借助文獻(xiàn)研究，提出解決復(fù)雜問題的算法。是2.3

培育學(xué)生分析問題和解決問題的能力，能運(yùn)用數(shù)據(jù)結(jié)構(gòu)，論證解決方案有效性，綜合得到解決通信

4M4是2.4

領(lǐng)域復(fù)雜工程問題的解決方案。

三、課程內(nèi)容

支撐課課內(nèi)課外

序號(hào)章節(jié)號(hào)標(biāo)題課程內(nèi)容/重難點(diǎn)教學(xué)方式課外環(huán)節(jié)

程目標(biāo)學(xué)時(shí)學(xué)時(shí)

本章重點(diǎn)難點(diǎn)：算法的時(shí)間復(fù)雜度、抽象數(shù)據(jù)類型。1.1數(shù)據(jù)

結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)舉例、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理

1第一章第一章緒論結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容。L2數(shù)據(jù)結(jié)構(gòu)的抽象形式數(shù)據(jù)Ml,M34講授4作業(yè)

類型、抽象數(shù)據(jù)類型。L3算法性能分析算法的性能分析、

算法的時(shí)間復(fù)雜度。

本章重點(diǎn)難點(diǎn)：線性表在順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)下的實(shí)現(xiàn)。2.1

線性表線性表的概念。2.2順序表順序表的概念、類定義。

2第二章第二章線性表2.3單鏈表單鏈表的概念、類定義。2.4線性鏈表的其他變形Ml,M28講授/上機(jī)8作業(yè)/上機(jī)

循環(huán)鏈表、雙向鏈表。2.5單鏈表的應(yīng)用多項(xiàng)式及其運(yùn)算。

上機(jī)1:線性表的操作

本章重點(diǎn)難點(diǎn)：棧的特點(diǎn)、存儲(chǔ)、及其應(yīng)用，隊(duì)列的特點(diǎn)及其

存儲(chǔ)。3.1棧棧的概念、順序棧、鏈?zhǔn)綏?、括?hào)匹配、表達(dá)

3第三章第三章棧和隊(duì)列Ml,M28講授/上機(jī)8作業(yè)/上機(jī)

式的計(jì)算。3.2隊(duì)列隊(duì)列的概念、循環(huán)隊(duì)列、鏈?zhǔn)疥?duì)列、優(yōu)

先級(jí)隊(duì)列、雙端隊(duì)列。上機(jī)2：棧和隊(duì)列的應(yīng)用

本章重點(diǎn)難點(diǎn)：字符串模式匹配，特殊矩陣、稀疏矩陣的存儲(chǔ)

及操作。4.1多維數(shù)組的概念與存儲(chǔ)數(shù)組的數(shù)據(jù)結(jié)構(gòu)定義、

第四章字符串和

4第四章數(shù)組基于順序存儲(chǔ)的實(shí)現(xiàn)。4.2特殊矩陣對(duì)稱矩陣、三對(duì)角M1,M42講授/上機(jī)2作業(yè)/上機(jī)

數(shù)組

矩陣。4.3稀疏矩陣稀疏矩陣的類定義、稀疏矩陣的轉(zhuǎn)置。

4.4字符串字符串線性結(jié)構(gòu)的特點(diǎn)，模式匹配算法。上機(jī)3：

特殊矩陣的操作

本章重點(diǎn)難點(diǎn)：二叉樹的性質(zhì)、存儲(chǔ)及操作，線索二叉樹，

Huffman樹。5.1數(shù)和森林的概念樹的定義、樹的抽象數(shù)據(jù)類

型。5.2二叉樹二叉樹的定義、二叉樹的性質(zhì)、二叉樹的抽

象數(shù)據(jù)類型。5.3二叉樹的存儲(chǔ)二叉樹的順序存儲(chǔ)、二叉樹

5第五章第五章樹與森林的鏈?zhǔn)酱鎯?chǔ)。5.4二叉樹的遍歷中序遍歷、前序遍歷、后序M1,M410講授/上機(jī)10作業(yè)/上機(jī)

遍歷、非遞歸遍歷。5.5線索二叉樹線索、線索化二叉樹。

5.6樹與森林樹的存儲(chǔ)、森林與二叉樹的轉(zhuǎn)換、樹的遍歷、森

林的遍歷。5.7二叉樹的計(jì)數(shù)5.8哈夫曼樹路徑長(zhǎng)度、哈夫

曼樹、哈夫曼編碼。上機(jī)4：數(shù)的基本操作

本章重點(diǎn)難點(diǎn)：圖的存儲(chǔ)、遍歷、最小生成樹，最短路徑、關(guān)

鍵路徑。6.1圖的基本概念圖的基本概念、圖的抽象數(shù)據(jù)類

型。6.2圖的存儲(chǔ)鄰接矩陣、鄰接表。6.3圖的遍歷與連通

性深度優(yōu)先遍歷、廣度優(yōu)先遍歷、連通分量。6.4最小生成

6第六章第六章圖M1,M48講授/上機(jī)8作業(yè)/上機(jī)

樹克魯斯卡爾算法、普里姆算法。6.5最短路徑單源最短路

徑問題、所有頂點(diǎn)之間的最短路徑。6.6活動(dòng)網(wǎng)絡(luò)用頂點(diǎn)表

示活動(dòng)的網(wǎng)絡(luò)、用邊表示活動(dòng)的網(wǎng)絡(luò)、拓?fù)渑判?、關(guān)鍵路徑。

上機(jī)5：圖的基本操作

本章重點(diǎn)難點(diǎn)：順序查找、折半查找、平衡二叉樹、B樹、

HASH查找。7.1靜態(tài)表查找順序查找、折半查找。7.2動(dòng)

7第七章第七章查找M3,M46講授6作業(yè)

態(tài)查找表查找二叉搜索樹、平衡二叉樹、B樹。7.3HASH查

找HASH函數(shù)、解決沖突的方法。

本章重點(diǎn)難點(diǎn)：SHELL排序、冒泡排序、快速排序、堆排序、

歸并排序。8.1基于插入排序直接插入排序、折半插入排

8第八章第八章排序序、SHELL排序。8.2基于交換的排序冒泡排序、快速排M3,M46講授/上機(jī)6作業(yè)/上機(jī)

序。8.3基于選擇的排序簡(jiǎn)單選擇排序、堆排序。8.4基于

歸并的排序2-路歸并排序。上機(jī)6:查找排序算法的應(yīng)用

四、考核方式

序號(hào)考核環(huán)節(jié)操作細(xì)節(jié)總評(píng)占比

平時(shí)作業(yè)

1成績(jī)采用百分制，根據(jù)平時(shí)作業(yè)及實(shí)驗(yàn)完成情況評(píng)分。20%

及實(shí)驗(yàn)

2平時(shí)測(cè)驗(yàn)4次測(cè)驗(yàn)20%

3期末考試1.閉卷考試，成績(jī)采用百分制，卷面成績(jī)總分100分。60%

五、評(píng)分細(xì)則

序號(hào)課程目標(biāo)考核環(huán)節(jié)大致占比評(píng)分等級(jí)

平時(shí)作業(yè)

1