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

DataStructure

課程代碼：19410016

學(xué)分：2

學(xué)時(shí)：48（其中：課堂教學(xué)學(xué)時(shí)：16實(shí)驗(yàn)學(xué)時(shí)：上機(jī)學(xué)時(shí):32課程實(shí)踐學(xué)時(shí)：）

先修課程：計(jì)算機(jī)基礎(chǔ)

適用專業(yè)：教育技術(shù)

教材：數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版，嚴(yán)蔚敏，吳偉民，清華大學(xué)出版社，2013年4月

一、課程性質(zhì)與課程目標(biāo)

（-）課程性質(zhì)

用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題時(shí)，涉及到數(shù)據(jù)表示及數(shù)據(jù)處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正

是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過(guò)這兩方面的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課

程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)

用中具有舉足輕重的作用。

（-）課程目標(biāo)

課程目標(biāo)1:掌握線性表的定義、兩種存儲(chǔ)結(jié)構(gòu)及在不同的存儲(chǔ)結(jié)構(gòu)下基本

算法的實(shí)現(xiàn)。

課程目標(biāo)2：掌握棧、隊(duì)列的定義、特點(diǎn)、兩種存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn);

了解棧、隊(duì)列的應(yīng)用。

課程目標(biāo)3：深刻理解二叉樹的定義、性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉

樹的三種遍歷算法；掌握二叉樹的線索化方法。

課程目標(biāo)4：掌握在順序表、有序表、索引表、散列表等上的查找算法；理

解二叉排序樹、平衡二叉樹、B-樹的各種算法。

課程目標(biāo)5：掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、

歸并排序和基數(shù)排序的基本思想、步驟及算法；了解其算法分析。

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

第一章數(shù)據(jù)結(jié)構(gòu)基本概念

（-）課程內(nèi)容

①數(shù)據(jù)結(jié)構(gòu)的概念（重點(diǎn)）

②抽象數(shù)據(jù)類型（難點(diǎn)）

③算法和算法分析（重點(diǎn)，難點(diǎn)）

（二）教學(xué)要求

了解：數(shù)據(jù)結(jié)構(gòu)以及算法的作用

理解：數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系；數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)

結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)；抽象數(shù)據(jù)類型的概念

掌握：算法分析的方法

（三）重點(diǎn)與難點(diǎn)

①數(shù)據(jù)結(jié)構(gòu)的概念（重點(diǎn)）

②抽象數(shù)據(jù)類型（難點(diǎn)）

③算法和算法分析（重點(diǎn)，難點(diǎn)）

第二章線性表

（-）課程內(nèi)容

①線性表邏輯結(jié)構(gòu)

②線性表的順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn)（重點(diǎn)）

③線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)（重點(diǎn)，難點(diǎn)）

（二）教學(xué)要求

了解：循環(huán)鏈表、雙（循環(huán)）鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作

理解：線性表的定義及其運(yùn)算：順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說(shuō)明

掌握：這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法

熟練掌握：利用順序表和鏈表進(jìn)行算法設(shè)計(jì)

（三）重點(diǎn)與難點(diǎn)

①線性表的順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn)（重點(diǎn)）

②線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)（重點(diǎn)，難點(diǎn)）

第三章棧和隊(duì)列

（-）課程內(nèi)容

①串及其基本運(yùn)算

②串的定長(zhǎng)順序存儲(chǔ)及基本運(yùn)算（重點(diǎn)）

③串的堆存儲(chǔ)結(jié)構(gòu)計(jì)

（二）教學(xué)要求

了解：串的定義

理解：串的存儲(chǔ)方式

掌握：常用的串運(yùn)算

熟練掌握：串的算法設(shè)

（三）重點(diǎn)與難點(diǎn)

1.重點(diǎn)是串的定長(zhǎng)順序存儲(chǔ)及基本運(yùn)算（重點(diǎn)）

第四章二叉樹

（-）課程內(nèi)容

①定義與性質(zhì)

②存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn)（重點(diǎn)）

③二叉樹的遍歷（重點(diǎn)，難點(diǎn)）

④線索二叉樹（難點(diǎn)）

⑤二叉樹的應(yīng)用（重點(diǎn)，難點(diǎn)）

⑥樹的概念與表示

⑦基本操作與存儲(chǔ)

⑧樹、森林與二叉樹的轉(zhuǎn)換

⑨樹或森林的遍歷

⑩樹的應(yīng)用

（-）教學(xué)要求

了解：樹的簡(jiǎn)單應(yīng)用

理解：二叉樹的定義、性質(zhì)及其存儲(chǔ)方法；樹的定義、術(shù)語(yǔ)

掌握：二叉樹的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義；二叉樹的三種遍歷算法；

二叉樹的線索化方法；樹的各種存儲(chǔ)結(jié)構(gòu)；森林與二叉樹間的相互轉(zhuǎn)換；樹和森林的遍歷

熟練掌握：運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問(wèn)題

（三）重點(diǎn)與難點(diǎn)

②存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn)（重點(diǎn)）

③二叉樹的遍歷（重點(diǎn)，難點(diǎn)）

④線索二叉樹（難點(diǎn)）

⑤二叉樹的應(yīng)用（重點(diǎn)，難點(diǎn)）

第五章查找

（一）課程內(nèi)容

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

②靜態(tài)查找表（重點(diǎn)）

③動(dòng)態(tài)查找表（重點(diǎn)，難點(diǎn)）

④哈希表查找（雜湊法）（重點(diǎn)）

（二）教學(xué)要求

了解：查找的基本思想及查找成功和不成功的概念

理解：二叉排序樹、平衡二叉樹B-樹的各種算法

掌握：順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找

長(zhǎng)度

（三）重點(diǎn)與難點(diǎn)

靜態(tài)查找表（重點(diǎn)）

動(dòng)態(tài)查找表（重點(diǎn)，難點(diǎn)）

哈希表查找（雜湊法）（重點(diǎn)）

第六章排序

（-）課程內(nèi)容

①基本概念

②插入排序

③交換排序

④選擇排序

⑤二路歸并排序（難點(diǎn)）

⑥基數(shù)排序

⑦外排序（難點(diǎn)）

（二）教學(xué)要求

了解：外排序的定義和基本方法

理解：排序的基本思想和基本概念

掌握：插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基

本思想、步驟、算法及時(shí)空效率分析

（三）重點(diǎn)與難點(diǎn)

二路歸并排序（難點(diǎn)）

外排序（難點(diǎn)）

三、學(xué)時(shí)分配及教學(xué)方法

章

（按序填教學(xué)形式及學(xué)時(shí)分配

寫）

支撐的課程目

課主要教學(xué)方法

標(biāo)

課堂實(shí)上程小

教學(xué)驗(yàn)機(jī)實(shí)計(jì)

踐

課程目標(biāo)1

第一章224講授法

課程目標(biāo)1

第二章224講授法

課程目標(biāo)2

第三章246講授法、案例教學(xué)

課程目標(biāo)3

第四章4812講授法、案例教學(xué)

講授法、案例教學(xué)課程目標(biāo)4

第五章4812

講授法、案例教學(xué)課程目標(biāo)5

第六章4812

合計(jì)163248

五、課程考核

考核形式考核要求考核權(quán)重備注

點(diǎn)名

平時(shí)出勤10%

（10次）

完成作業(yè)次數(shù)與質(zhì)量

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

（10次）

管理系統(tǒng)設(shè)計(jì)要求

管理系統(tǒng)設(shè)計(jì)70%

（上機(jī)獨(dú)立完成）

注：1.分學(xué)期設(shè)置和考核的課程應(yīng)按學(xué)期分別填寫上表。

2.考核形式主要包括課堂表現(xiàn)、平時(shí)作業(yè)、階段測(cè)試、期中考試、期末考試、大作

業(yè)、小論文、項(xiàng)目設(shè)計(jì)和作品等。

3.考核要求包括作業(yè)次數(shù)、考試方式（開卷、閉卷）、項(xiàng)目設(shè)計(jì)要求等。

4.考核權(quán)重指該考核方式或途徑在總成績(jī)中