數據結構(西北大學)精品課程

  • 名稱:數據結構(西北大學)精品課
  • 分類:數據庫  
  • 觀看人數:加載中
  • 時間:2019/11/12 13:56:28
收藏: 更多

“數據結構”是信息管理與信息系統專業一門重點專業基礎課程,也是學科專業核心專業基礎課程之一,屬于專業學位必修課程。本課程的教學任務是針對大量的信息處理對象,介紹對象信息與數據表示的各種抽象的、基本的邏輯結構及其上的基本運算操作。通過研究各種基本數據結構內在的邏輯關系和它們在計算機中的存儲表示方式,初步建立數據結構上基本運算操作的正確性概念,同時,結合各種典型問題討論其上的各種基本運算操作及其基本算法,講授各種數據結構的特點、適用范圍,以及對一些基本算法效率的定性和定量分析方法,為后續課程提供必要的數據結構基礎。

數據結構(西北大學)精品課程

《數據結構A》在計算機科學中是一門綜合性的專業基礎課,不僅是一般程序設計的基礎,而且是設計和實現操作系統、數據庫系統、編譯程序及其它系統程序和大型應用程序的重要基礎。

課程教學內容與基本要求

(一)緒論( 3 學時)

1.主要內容: (1)介紹什么是數據結構; (2)基本概念和術語 : 數據、數據元素、數據對象,以及數據結構的定義、邏輯結構、 物理結構(理解)數據類型、抽象數據類型; (3)抽象數據類型的表示與實現; (4)算法和算法分析 : 算法的概念、算法設計的要求以及算法效率的度量。 2.基本要求 (1)了解學習數據結構的重要性; (2)掌握數據結構的定義及相關概念和術語; (3)了解抽象數據類型的定義、表示與實現方法; (4)理解算法的概念、特點并掌握度量其效率的基本方法。 3.自學內容: 類 C語言的書寫規范。

(二)線性表( 6 學時)

1.主要內容: (1)線性表的抽象數據類型定義和相關概念:數據項、記錄、文件等; (2)線性表順序存儲表示和基本操作的實現; (3)線性表的鏈式存儲表示和基本操作的實現; (4)稀疏多項式的抽象數據類型定義、表示和加法的實現。

2.基本要求 (1)掌握線性表的定義和特點; (2)熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現算法; (3)熟練掌握單鏈表、循環鏈表、雙向鏈表三種鏈表的表示,以及單鏈表的查找、插 入、刪除、創建等實現算法。 3.自學內容: 靜態鏈表。

(三)棧和隊列( 5 學時)

1.主要內容: (1)棧和隊列的結構特性和抽象數據類型定義; (2)棧和隊列的順序存儲表示和實現; (3)棧和隊列的鏈式存儲表示和實現; (4)棧和隊列在程序設計中的應用。 2.基本要求 (1)掌握棧和隊列兩種抽象數據類型的特點; (2)掌握棧的兩種存儲表示和實現,特別注意棧滿棧空的條件; (3)掌握隊列的兩種存儲表示和實現,特別注意隊滿隊空的條件; (4)了解遞歸算法與棧的關系。 3.自學內容: 鏈棧,離散事件模擬

(四)串( 3 學時)

1.主要內容: (1)串的抽象數據類型定義; (2)串的表示和實現 : 定長順序存儲結構和堆分配存儲結構; (3)串的各種基本操作的實現及其應用; (4)串的模式匹配操作。 2.基本要求 (1)熟悉串的一些基本操作的定義,并能利用基本操作實現串的其它操作; (2)掌握串的定長順序存儲結構以及基本操作的實現; (3)掌握串的堆分配存儲結構以及基本操作的實現; (4)掌握串的簡單模式匹配算法,理解 KMP 算法。 3.自學內容: 串操作的應用實例。

(五)數組和廣義表( 4 學時)

1.主要內容: (1)數組的抽象數據類型定義及其順序表示和實現; (2)特殊矩陣和稀疏矩陣的壓縮存儲; (3)廣義表的抽象數據類型定義和存儲結構。 2.基本要求 (1)了解數組的兩種存儲表示方法,并掌握數組在以行為主的存儲結構中的地址計算 方法;

(2)掌握對特殊矩陣進行壓縮存儲時的下標變換公式; (3)熟悉稀疏矩陣的三元組順序表存儲結構下的一般轉置和快速轉置算法;了解十字 鏈表等存儲結構; (4)掌握廣義表的結構特點、取表頭表尾操作,及其存儲表示方法。 3.自學內容: 采用十字鏈表存儲結構創建稀疏矩陣。

(六)樹和二叉樹( 10 學時)

1.主要內容: (1)樹的抽象數據類型定義和基本術語; (2)二叉樹的抽象數據類型定義、性質和存儲結構; (3)二叉樹的遍歷; (4)線索二叉樹的定義、遍歷及線索化二叉樹; (5)樹的存儲結構、樹和森林的遍歷以及與二叉樹的轉換; (6)Huffman 樹及其應用。 2.基本要求 (1)掌握樹型結構的特點和基本術語; (2)熟練掌握二叉樹的性質,了解相應的證明方法; (3)了解二叉樹的順序存儲結構和鏈式存儲結構,熟練掌握二叉鏈表存儲結構; (4)熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法,能靈活運用遍歷算 法實現二叉樹的其他操作; (5)熟練掌握二叉樹的線索化過程,以及在中序線索二叉樹上找結點的前驅與后繼的 方法; (6)熟悉樹的各種存儲結構及其特點,掌握樹和森林與二叉樹的轉換方法; (7)了解 Huffman 樹的特性,掌握建立 Huffman 樹和 Huffman 編碼的方法。 3.自學內容: 先序、后序遍歷二叉樹非遞歸算法,層次遍歷二叉樹算法。

(七)圖( 9 學時)

1.主要內容: (1)圖的定義和術語; (2)圖的四種存儲結構:數組表示法(鄰接矩陣) 、鄰接表、十字鏈表和鄰接多重表; (3)圖的兩種遍歷策略:深度優先遍歷和廣度優先遍歷; (4)圖的連通性和最小生成樹; (5)有向無環圖及其應用:拓撲排序和關鍵路徑; (6)最短路徑問題。 2.基本要求 (1)熟悉圖的定義和術語; (2)了解圖的存儲結構,熟練掌握數組表示法(鄰接矩陣)和鄰接表存儲表示; (3)熟練掌握圖的深度優先遍歷和廣度優先遍歷算法; (4)掌握無向連通帶權圖的最小生成樹求解算法; (5)了解有向無環圖、 AOV網、 AOE網及其在實際中的應用,熟悉拓撲排序算法和關 鍵路徑算法; (6)熟悉兩種最短路徑問題求解算法。


河南福彩22选5基本走势图