《數據結構與算法分析》理論教學大綱

（供四年制本科信息與計算科學（醫學信息學）、醫學信息工程專業使用）

I前言

數據結構與算法分析是信息與計算科學（醫學信息學）專業及醫學信息工程專業學生的一門

重要專業課程。隨著計算機技術的迅猛發展，計算機已深入到人類社會的各個領域，計算機的應

用已不再局限于科學計算，而是更多地應用于控制、管理及數據處理等非數值計算的處理工作。

與此相應，計算機加工處理的對象由純粹的數值發展到字符、表格和圖像等各種具有一定結構的

數據。因此分析待處理對象的特性以及各處理對象之間存在的關系，是編制高質量的程序、開發

各種應用軟件和系統軟件、搞好計算機應用中必須解決的重要問題。數據結構這門課程的開設正

是為此目的服務的。學習數據結構旨在使學生了解各種數據對象的特性，學會數據組織的方法和

把現實世界中的問題在計算機內部的表示方法，以培養學生基本的、良好的算法設計能力和程序

設計技能。

本大綱適合信息與計算科學（醫學信息學）、醫學信息工程專業使用，現將大綱使用中的有關

問題說明如下：

-為了使教師和學生更好地掌握教材，大綱每一章節均由教學目的、教學要求和教學內容三

部分組成。教學目的注明教學目標，教學要求分掌握、熟悉和了解三個級別，教學內容與

教學要求級別相對應，并統一標示（核心內容即知識點以下劃實線，重點內容以下劃虛線，

一般內容不標示）便于學生重點學習。

二教師在保證大綱核心內容的前提下，可根據不同教學手段，講授重點內容和介紹一般內

容，有的內容可留給學生自學。

三總教學參考時數72學時，其中理論60學時，實驗12學時，理論/實驗為5:1。

四教材：《數據結構》，清華大學出版社，嚴蔚敏，1版，1997年。

n正文

第一章緒論

一教學目的

通過本章的教學，使學生了解學習數據結構的必要性，掌握數據結構的定義，使學生深刻認

識該課程的重要地位；使學生了解算法分析的方法。

二教學要求

（一）了解學習數據結構的必要性，掌握數據結構的定義。

（二）了解算法分析的方法。

（三）掌握時間和空間權衡的意義。

三教學內容

（-）數據結構的原則和地位。

（-）抽象數據類型和數據結構。

（三）問題、算法和程序。

（四）算法的效率，最佳、最差和平均情況。

（五）漸近分析和程序運行時間的計算。

（六）時間和空間權衡。

第二章線性表

一教學目的

本章的目的是使學生掌握線性表的實現方式與應用。

二教學要求

（一）掌握線性表的順序存儲結構的特點及描述方法和各種操作的基本思路、步驟及實現算法。

（二）掌握線性表的各種鏈式存儲結構的特點、描述及各種鏈表的建立和各種操作的基本思路、

步驟及實現算法。

三教學內容

（一）順序表

1順序表的插入。

2順序表的刪除。

（-）鏈表

1鏈表的插入。

2鏈表的刪除。

第三章棧和隊列

一教學目的

本章的目的是使學生掌握棧和隊列及其實現方式與應用。

二教學要求

（一）熟悉棧的定義、特征及在其上所定義的基本運算。

（-）掌握在兩種存儲結構上對棧所施加的基本運算的實現。

（三）熟悉隊列的定義、特征及在其上所定義的基本運算。

（四）掌握在兩種存儲結構上對隊列所施加的基本運算的實現。

三教學內容

（-）堆棧

1堆棧的定義。

2推棧的在能結構.與寒現.。…

3堆棧的應用。

（二）隊列

1隊列的定義。

2隊列的存儲結構與實現。

3隊列的應用。

第四章數組和廣義表

一教學目的

使學生熟悉數組和廣義表的概念及值的順序存貯及鏈式存貯；掌握數組和廣義表的基本運

算。

二教學要求

（-）了解數組的定義。

（-）熟悉和領會數組的存儲方式。

（三）掌握常用的數組運算。

三教學內容

（一）數組的概念。

（-）數組的順序存貯。

（三）數組的算法

1二元組數組。

2數組的轉置。

3數組的快速轉置。

第六章樹和二叉樹

一教學目的

本章的目的是使學生掌握樹、二叉樹、線索二叉樹、Huffman編碼樹及其實現方式，并應用。

二教學要求

（一）掌握樹的定義，基本運算和存儲結構。

（二）掌握二叉樹的定義，性質，基本運算和存儲結構。

（三）掌握二叉樹的遍歷和線索二叉樹。

（四）熟悉樹，二叉樹與森林的轉換；樹與森林的遍歷。

（五）掌握二叉樹的應用（Huffman樹）。

三教學內容

（一）樹、二叉樹的概念及有關術語。

（―）二叉樹的性質。

（三）二叉樹存儲。

1順序存儲。

2鏈式存儲。

（四）二叉樹的遍歷

1前序遞歸遍歷。

2中序遞歸遍歷。

3后序遞歸遍歷。

4中序非遞歸遍歷。

5層次遍歷。

（五）線索二叉樹的概念、存儲表示、算法。

（六）樹轉換為二叉樹的方法。

（七）哈夫曼樹、哈夫曼編碼的概念、算法。

第七章圖

一教學目的

本章的目的是使學生掌握圖及其實現方式與相關算法，并應用。

二教學要求

（-）掌握圖的基本概念與術語。

（二）掌握圖的各種存貯方法（重點是鄰接矩陣和鄰接表）及其描述。

（三）掌握圖的深度優先、廣度優先遍歷算法。

（四）掌握生成樹與最小生成樹的概念，構造最小生成樹算法的思路、步驟及算法執行過程。

（五）領會拓撲排序、關鍵路徑、最短路徑的算法思想。

三教學內容

（-）圖的定義。

（二）圖的存儲結構。

1鄰接矩陛

2鄰接筵總..

（三）圖的遍歷。

1深度優先遍歷。

2匕度優先遍歷

（四）生成樹及最小生成樹。

1生成樹概念及算法。

2最小生成樹概念及算法。

（五）有向無環圖及其應用。

1拓撲排序。

2關鍵路經。

（六）最短路徑。

第九章查找

一教學目的

本章的目的是使學生了解各種查找算法，并應用。

二教學要求

（-）了解查找的基本思想及查找成功和不成功的概念。

（二）掌握在順序表、有序表、索引表上的查找方法和算法，并能求出相應的平均查找長度。

（三）熟悉并掌握二叉排序樹、平衡二叉樹的各種算法。

三教學內容

（一）查找、平均查找長度的概念。

（-）各種靜態查找表（順序表、有序表、索引順序表）的查找方法及實現算法。

（三）二叉排序樹的概念、查找算法及二叉查找樹的生成。

（四）平衡二叉樹的概念及構造平衡二叉樹時的四種旋轉技術。

第十章內部排序

一教學目的

本章的目的是使學生掌握各種內部排序算法。

二教學要求

（一）熟悉有關排序的概念。

（二）掌握各種排序方法的基本思路、實現步驟、算法。

（三）熟悉各種排序算法的特點、時間復雜度、穩定性。

三教學內容

（-）排序的術語與記號。

（二）插入排序。

1直摟麒排黑..

2Shell排序。

（三）交換排序

1快速排序。

2起泡排序。

（四）選擇排序。

1簡單選擇排序。

2堆排序。

（五）歸并排序。

（六）基數排序。

m教學組織與方法

一實施機構：由醫學信息工程系衛生信息工程教研室執行。

二組織內容：教案講義審核、多媒體課件（Flash）演示。

三教學方法：

1.理論教學：采用啟發式課堂教學方式，輔助現代教育技術和手段。核心內容以講授為主,

重點內容以介紹為主，一般內容以自學為主。

2.實驗教學：布置實驗內容，每位學生獨立完成。

3.輔導形式：輔導講義，課堂答疑，網絡查詢等。

四考核辦法：考試采用閉卷筆試，教學測量：理論考試占70%,實驗考核占30%。

IV教學時數分配表

講課內容教學手段時數實驗內容時數類型

緒論CAI4

線性表CAI8線性表的操作4驗證型

棧和隊列CAI8

數組和廣義表CAI4

樹和二叉樹CAI10樹的操作4