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

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

一、課程基本口心、

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

課程名稱

DataStructuresandAlgorithms

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

學分3.0課內(nèi)學時52講授40實驗0上機12實踐0課外學時52

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

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

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

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

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

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

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

"DataStructureandAlgorithm'^isacomprehensiveandimportantmajorcourse,whichisforthemajorsofcommunicationengineering.Thetask

課程簡介

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.

負責人大綱執(zhí)筆人審核人

二、課程目標

畢業(yè)要求指標點

序號代號課程目標OBE

任務(wù)自選

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

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

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

2M2是2.2

力，進一步訓(xùn)練和強化學生的建模能力，為軟件開發(fā)奠定堅實的基礎(chǔ)。

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

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

4M4是2.4

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

三、課程內(nèi)容

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

序號章節(jié)號標題課程內(nèi)容/重難點教學方式課外環(huán)節(jié)

程目標學時學時

本章重點難點：算法的時間復(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算法性能分析算法的性能分析、

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

本章重點難點：線性表在順序存儲、鏈式存儲下的實現(xiàn)。2.1

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

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

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

上機1:線性表的操作

本章重點難點：棧的特點、存儲、及其應(yīng)用，隊列的特點及其

存儲。3.1棧棧的概念、順序棧、鏈式棧、括號匹配、表達

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

式的計算。3.2隊列隊列的概念、循環(huán)隊列、鏈式隊列、優(yōu)

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

本章重點難點：字符串模式匹配，特殊矩陣、稀疏矩陣的存儲

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

第四章字符串和

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

數(shù)組

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

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

特殊矩陣的操作

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

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

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

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

5第五章第五章樹與森林的鏈式存儲。5.4二叉樹的遍歷中序遍歷、前序遍歷、后序M1,M410講授/上機10作業(yè)/上機

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

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

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

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

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

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

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

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

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

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

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

示活動的網(wǎng)絡(luò)、用邊表示活動的網(wǎng)絡(luò)、拓撲排序、關(guān)鍵路徑。

上機5：圖的基本操作

本章重點難點：順序查找、折半查找、平衡二叉樹、B樹、

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

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

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

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

本章重點難點：SHELL排序、冒泡排序、快速排序、堆排序、

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

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

序。8.3基于選擇的排序簡單選擇排序、堆排序。8.4基于

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

四、考核方式

序號考核環(huán)節(jié)操作細節(jié)總評占比

平時作業(yè)

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

及實驗

2平時測驗4次測驗20%

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

五、評分細則

序號課程目標考核環(huán)節(jié)大致占比評分等級

平時作業(yè)

1