遼寧科技大學(xué)課程教學(xué)大綱

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

課程名稱：數(shù)據(jù)結(jié)構(gòu)

英文名稱：DataStructure

課程編號：X2050876

學(xué)時數(shù)：64

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

學(xué)分?jǐn)?shù)：4.0

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

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

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

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

1、緒論

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

了解《數(shù)據(jù)結(jié)構(gòu)》的課程體系。

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

難點：算法的效率度量。

2、線性結(jié)構(gòu)

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

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

難點：棧與遞歸的關(guān)系。

3、樹

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

理解二叉樹的遞歸算法的設(shè)計原則，把握二叉樹的應(yīng)用算法（求葉子，高度等）；了解樹的遍歷及存儲；理解樹與二叉樹的轉(zhuǎn)換關(guān)系；把握哈夫曼樹的概念、構(gòu)造算法及編碼。

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

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

4、圖

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

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

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

5、排序和查找

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

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

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

三、教學(xué)方式及學(xué)時分配

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

（二）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

要求：同學(xué)自立完成課程設(shè)計的任務(wù)，查閱相關(guān)資料、編寫程序并寫出說明書。

（三）作業(yè)

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

（四）課外

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