遼寧科技大學課程教學大綱

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦遼寧科技大學課程教學大綱遼寧科技高校課程教學大綱

課程名稱：數(shù)據(jù)結構

英文名稱：DataStructure

課程編號：X2050876

學時數(shù)：64

其中試驗（實訓）學時數(shù)：20課外學時數(shù)：0

學分數(shù)：4.0

適用專業(yè)：軟件工程(升本)

一、課程的性質和任務

數(shù)據(jù)結構是軟件工程專業(yè)的核心專業(yè)基礎課。也是計算機及相關專業(yè)的碩士討論生入學考試的專業(yè)課程之一。通過學習，使同學能夠分析數(shù)據(jù)對象特征，按照問題的需要，確定規(guī)律結構并挑選合適的存儲結構，實現(xiàn)典型算法設計及性能分析。要求同學把握典型算法及其程序實現(xiàn)，進而培養(yǎng)和提高同學算法分析與設計能力，建立數(shù)據(jù)結構的概念，為后續(xù)課程的學習及軟件開發(fā)打好基礎。

二、課程教學內(nèi)容的基本要求、重點和難點

1、緒論

把握數(shù)據(jù)元素、規(guī)律結構、存儲結構等基本概念；理解算法的定義、描述辦法及算法分析辦法；

了解《數(shù)據(jù)結構》的課程體系。

重點：數(shù)據(jù)結構的概念及算法描述辦法。

難點：算法的效率度量。

2、線性結構

理解線性表的定義及思想；理解線性表的挨次，鏈式存儲實現(xiàn)；嫻熟把握線性表的插入、刪除、查找等基本操作；把握線性表的逆置、分解、合并等典型算法；理解棧和隊列的定義及動態(tài)思想；把握棧、隊列的存儲實現(xiàn)和基本操作；理解棧與遞歸的關系，把握棧、隊列的應用問題：遞歸算法的設計原則及如何利用棧實現(xiàn)非遞歸算法的設計、表達式求值等問題；了解串的定義及存儲實現(xiàn)，把握串的模式匹配算法；了解數(shù)組的定義，把握特別矩陣（對稱矩陣、三角矩陣）的壓縮存儲實現(xiàn)。

重點：線性表的基本算法及典型算法，棧、隊列的基本算法（操作）。

難點：棧與遞歸的關系。

3、樹

了解樹、二叉樹的概念、性質；把握二叉樹的存儲實現(xiàn)；嫻熟把握二叉樹的遍歷辦法及算法實現(xiàn)；

理解二叉樹的遞歸算法的設計原則，把握二叉樹的應用算法（求葉子，高度等）；了解樹的遍歷及存儲；理解樹與二叉樹的轉換關系；把握哈夫曼樹的概念、構造算法及編碼。

重點：二叉樹的遍歷及算法

難點：二叉樹遞歸算法的理解及如何利用棧實現(xiàn)非遞歸算法

4、圖

了解圖的定義及相關術語；把握圖的鄰接矩陣、鄰接表的存儲實現(xiàn)；把握圖的遍歷算法的思想及其實現(xiàn)，并能夠基于存儲結構寫出遍歷序列；理解圖的連通性概念及算法；理解最小生成樹、拓撲排序、最短路徑的概念及算法；了解關鍵路徑的概念及算法思想。

重點：圖的存儲及遍歷算法，圖的典型算法實現(xiàn)

難點：遍歷及應用算法的實現(xiàn)

5、排序和查找

了解排序的相關概念；把握直接插入、容易挑選、冒泡、迅速排序和堆排序的算法思想及實現(xiàn)；理解希爾、歸并、基數(shù)排序的算法思想；理解各種算法的適用條件及其效率；了解線性表、樹表和散列表查找的相關概念；嫻熟把握挨次、折半查找算法，理解查找算法效率度量的辦法，會計算查找算法的ASL值；把握二叉排序樹的構造和查找算法；了解散列函數(shù)的選取原則和常見辦法，能夠按照散列函數(shù)和矛盾處理辦法構造散列表并把握散列表的查找算法；了解B+、B-樹的概念。

重點：把握幾種常見排序算法及特點；常見查找辦法的算法及適用條件。

難點：迅速排序的非遞歸實現(xiàn)

三、教學方式及學時分配

四、課程其他教學環(huán)節(jié)要求

（二）數(shù)據(jù)結構課程設計

要求：同學自立完成課程設計的任務，查閱相關資料、編寫程序并寫出說明書。

（三）作業(yè)

為提高課堂教學質量，催促同學聽課，任課老師可舉行適當?shù)碾S堂小測試；每章講授結束后，各留2-3道綜合題（應用題）、有試驗的章節(jié)留2-3道典型算法設計題作為作業(yè)，批改后做集中講評，講解作業(yè)中浮現(xiàn)的問題。作業(yè)的題型以算法設計為主。

（四）課外

首先完成老師布置的作業(yè)，預備試驗程