|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
《數據結構》研究生入學考試學習大綱
|
一、課程的地位與作用
《數據結構》課程是計算機專業的核心課程之一，是一門綜合性的專業基礎課，它介于數學，計算機硬件，計算機軟件之間。是高級程序設計語言，編譯原理，操作系統，數據庫，人工智能等課程的基礎。同時，數據結構的技術也廣泛應用于信息科學、系統工程，應用數學，以及各種工程技術領域。
|
|
|
二、課程的教學目標與基本要求
課程目的是使學生了解計算機應用中數據對象的特性，學會在應用中， 根據現實世界中的問題選擇適當的數據邏輯結構和存儲結構以及相應算法， 并且培養基本的、良好的程序設計技能。
三、課程內容（重點△，難點★）
1 緒論
1.1 數據結構的有關概念
1.2 數據結構發展概況
1.3△關于算法及算法的分析
1.3.1算法
1.3.2 算法設計要求
1.3.3 ★時間復雜度
2線性表
2. 1 線性表的邏輯結構
2. 2 △線性表的順序存儲結構及運算實現
2. 3 △線性表的鏈式存儲結構及運算
2. 3. 1 線性鏈表
2. 3. 2 循環鏈表
2. 3. 3 雙向鏈表
2. 3. 4 靜態鏈表
2. 4 ★一元多項式的表示及相加
3 棧和隊列
3.1 棧的定義及運算
3.2 △棧的存儲結構及運算實現
3.3棧應用舉例
3.4 隊的定義及運算
3.5 △隊的存儲結構及運算實現
3.5.1 隊的鏈式存儲和運算
3.5.2 循環隊---隊的順序存儲和運算
4 數組
4.1 數組的定義
4.2 ★稀疏矩陣的三元組表示及有關算法
4.3 稀疏矩陣的十字鏈表表示及相加
5 樹和二叉樹
5.1 樹的定義及有關術語
5.2 △二叉樹
5.2.1 二叉樹的定義
5.2.2 二叉樹的性質
5.2.3 二叉樹的存儲結構
5.3 △二叉樹的遍歷算法及線索二叉樹
5.3.1 二叉樹的遍歷
5.3.2 ★線索二叉樹
5.4 樹和森林
5.4.1 樹的存儲結構
5.4.2森林與二叉樹的轉換
5.4.3樹和森林的遍歷
5.5 哈夫曼樹及其應用
5.5.1 哈夫曼樹
5.5.2 哈夫曼編碼
6 圖
6.1 圖的定義及邏輯結構、存儲方法
6.2 △圖的遍歷算法
6.2.1 圖的深度優先搜索
6.2.2 圖的廣度優先搜索
6.3 △無向圖的連通性
6.3.1 無向圖的連通分量
6.3.2 無向圖的生成樹
6.3.3 ★最小生成樹
6.4 △有向無環圖及其應用
6.4.1 拓撲排序；
6.4.2 ★關鍵路徑
6.5 △★單源點最短路徑
7 查找
7.1 △靜態查找表
7.1.1 順序表的查找
7.1.2 有序表的折半查找
7.1.3 索引順序表的查找
7.2 △動態查找表
7.2.1 二叉排序樹
7.2.2 ★平衡二叉樹
7.2.3 ★B-樹
7.3 △哈希表
7. 3. 1 哈希表的定義
7. 3. 2 哈希函數
7. 3. 3 沖突處理方法
7. 3. 4 哈希表的查找
8 △內部排序
8.1 排序的概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 插入排序
8.2.3 希爾排序
8.3 快速排序
8.4 選擇排序
8.4.1 簡單選擇排序
8.4.2 堆排序
8.5各種內部排序方法的比較
|
|
|
|
四、時間分配
|
|
|
課程分
段標識
|
序號
|
教 學 內 容
|
教學環節（學時）
|
|
|
講
課
|
習
題
|
實
驗
|
上
機
|
課
外
|
小
計
|
|
|
|
1
|
緒論
|
2
|
|
|
|
|
2
|
|
|
2
|
線性表
|
5
|
|
|
3
|
|
7
|
|
|
3
|
棧和隊列
|
4
|
|
|
|
|
7
|
|
|
4
|
數組
|
4
|
|
|
|
|
4
|
|
|
5
|
樹和二叉樹
|
7
|
|
|
3
|
|
10
|
|
|
6
|
圖
|
7
|
|
|
|
|
7
|
|
|
7
|
查找
|
7
|
|
|
2
|
|
7
|
|
|
8
|
內部排序
|
4
|
|
|
|
|
4
|
|
|
總 計
|
40
|
|
|
8
|
|
48
|
|
|
五、課程說明
|
|
|
課程英文名稱
|
Data Structure
|
|
|
主要先修課程
|
C++程序設計
|
|
|
適用專業類別
|
計算機科學與技術
|
|
|
主要教材（作者、教材名稱、出版社）
|
“數據結構” 嚴蔚敏、吳偉民 清華大學出版社
|
|
|
考核方式
|
考試
|
|
|
課程簡介
|
各種類型的數據結構和查找，排序的各種方法
|
|
|
必 開
實 驗
項 目
|
序號
|
項 目 名 稱
|
學時
|
|
|
1
|
線性表鏈式存儲結構的應用
|
3
|
|
|
2
|
二叉樹
|
2
|
|
|
3
|
Hash表應用
|
2
|
|
|
4
|
|
|
|
|
5
|
|
|
|
|
6
|
|
|
|
|
7
|
|
|
|
|
8
|
|
|
操作系統
1 操作系統引論
操作系統的目標、作用和類型
操作系統的發展與分類
操作系統的功能與組成
市場上常用的操作系統的介紹
進程的描述與控制
進程的描述
進程的定義
進程的狀態
進程的控制
2.2.1 原語
2.2.2 進程控制的幾個基本原語
進程的同步與通信
進程同步的基本概念
3.1.1臨界資源
臨界區
硬件和軟件解決進程互斥
信號量機制
3.2.1 整型信號量
記錄型信號量
經典進程同步問題
進程通信
3.3.1 進程通信類型
直接通信和間接通信
消息通信機制
3.3 線程的基本概念
調度與死鎖
調度的類型和模型
4.1.1 調度類型
調度隊列模型
調度方式選擇的準則
常用的進程調度算法
死鎖的基本概念
4.3.1 死鎖的原因
產生死鎖的必要條件
處理死鎖的基本方法
死鎖的預防和避免
4.4.1 死鎖的預防
4.4.2 系統的安全狀態
4.4.3銀行家算法
存儲器管理
程序的裝入和連接
連續分配存儲管理方式
5.2.1 單一連續分配
固定分區分配
動態分區分配
動態重定位
對換
多道程序環境的對換
對換空間管理
進程的換入與換出
分頁存儲管理
分頁存儲管理的基本方法
地址變換機構
兩級和多級頁表
分段存儲管理
分段存儲管理的引入與原理
段頁式存儲管理
虛擬存儲器
虛擬存儲的基本概念
請求分頁存儲管理
請求分頁硬件支持
頁面分配
頁面調入策略
頁面置換
最佳和先進先出算法
LRU算法
Clock算法
其它置換算法
請求分頁系統的性能問題
6.4.1 工作集
6.4.2 抖動及其預防
請求分段存儲管理
設備管理
I/O系統的組成
I/O 系統的結構
I/O設備
I/O設備控制器
I/O通道
I/O控制方式
程序I/O
中斷驅動I/O
DMA
I/O通道方式
緩沖區的作用與管理
設備分配
數據結構
分配考慮因素
設備獨立性
獨占設備的分配
SPOOLing技術
設備處理
設備驅動程序的功能和特點
設備驅動和中斷處理程序的處理過程
文件系統
文件和文件系統
文件的分類
文件的基本操作
文件的邏輯結構
8.2.1文件邏輯結構的類型
8.2.2 常見的幾種邏輯結構（順序，索引，索引順序）
目錄管理
8.3.1文件控制塊和索引結點
8.3.2 單級和兩級目錄結構
8.3.3 樹型目錄
8.3.4目錄查詢技術
文件共享
文件共享的必要性
常用的共享方式
文件保護
文件保護的重要性
文件保護的幾種方案
磁盤存儲器管理
9.1磁盤I/O1 操作系統引論
1.1 操作系統的目標、作用和類型
1.2 操作系統的發展與分類
1.3 操作系統的功能與組成
1.4 市場上常用的操作系統的介紹
2 進程的描述與控制
2.1 進程的描述
2.1.1 進程的定義
2.1.2 進程的狀態
2.2 進程的控制
2.2.1 原語
2.2.2 進程控制的幾個基本原語
3 進程的同步與通信
3.1 進程同步的基本概念
3.1.1臨界資源
3.1.2 臨界區
3.1.3 硬件和軟件解決進程互斥
3.2 信號量機制
3.2.1 整型信號量
3.2.2 記錄型信號量
3.2.3 經典進程同步問題
3.3 進程通信
3.3.1 進程通信類型
3.3.2 直接通信和間接通信
3.3.3 消息通信機制
3.3 線程的基本概念
4 調度與死鎖
4.1 調度的類型和模型
4.1.1 調度類型
4.1.2 調度隊列模型
4.1.3 調度方式選擇的準則
4.2 常用的進程調度算法
4.3 死鎖的基本概念
4.3.1 死鎖的原因
4.3.2 產生死鎖的必要條件
4.3.3 處理死鎖的基本方法
4.4 死鎖的預防和避免
4.4.1 死鎖的預防
4.4.2 系統的安全狀態
4.4.3銀行家算法
5 存儲器管理
5.1 程序的裝入和連接
5.2 連續分配存儲管理方式
5.2.1 單一連續分配
5.2.2 固定分區分配
5.2.3 動態分區分配
5.2.4 動態重定位
5.3 對換
5.3.1 多道程序環境的對換
5.3.2 對換空間管理
5.3.3 進程的換入與換出
5.2 分頁存儲管理
5.4.1 分頁存儲管理的基本方法
5.4.2 地址變換機構
5.4.3 兩級和多級頁表
5.3 分段存儲管理
5.5.1 分段存儲管理的引入與原理
5.5.2 段頁式存儲管理
6 虛擬存儲器
6.1 虛擬存儲的基本概念
6.2 請求分頁存儲管理
6.2.1 請求分頁硬件支持
6.2.2 頁面分配
6.2.3 頁面調入策略
6.3 頁面置換
6.3.1 最佳和先進先出算法
6.3.2 LRU算法
6.3.3 Clock算法
6.3.4 其它置換算法
6.4 請求分頁系統的性能問題
6.4.1 工作集
6.4.2 抖動及其預防
6.5 請求分段存儲管理
7 設備管理
7.1 I/O系統的組成
7.1.1 I/O 系統的結構
7.1.2 I/O設備
7.1.3 I/O設備控制器
7.1.4 I/O通道
7.2 I/O控制方式
7.2.1 程序I/O
7.2.2 中斷驅動I/O
7.2.3 DMA
7.2.4 I/O通道方式
7.3 緩沖區的作用與管理
7.4 設備分配
7.4.1 數據結構
7.4.2 分配考慮因素
7.4.3 設備獨立性
7.4.4 獨占設備的分配
7.4.5 SPOOLing技術
7.5 設備處理
7.5.1 設備驅動程序的功能和特點
7.5.2 設備驅動和中斷處理程序的處理過程
8 文件系統
8.1 文件和文件系統
8.1.1 文件的分類
8.1.2 文件的基本操作
8.2 文件的邏輯結構
8.2.1文件邏輯結構的類型
8.2.2 常見的幾種邏輯結構（順序，索引，索引順序）
8.3 目錄管理
8.3.1文件控制塊和索引結點
8.3.2 單級和兩級目錄結構
8.3.3 樹型目錄
8.3.4目錄查詢技術
8.4 文件共享
8.4.1 文件共享的必要性
8.4.2 常用的共享方式
8.5 文件保護
8.5.1 文件保護的重要性
8.5.2 文件保護的幾種方案
9 磁盤存儲器管理
9.1磁盤I/O
9.1.1 磁盤調度算法
9.1.2 各種掃描算法
9.2外存分配
9.3 空閑存儲空間的管理
10 UNIX操作系統分析
10. 1 UNIX綜述
10.2 UNIX進程控制子系統
10.3 UNIX文件系統子系統
參考書籍 1） 《計算機操作系統（第三版）》西安電子科技大學出版社
湯子贏
2） 操作系統概念（中譯版） （六版） 高等教育出版社
Peter Baer Galvin
9.1.1 磁盤調度算法
9.1.2 各種掃描算法
9.2外存分配
9.3 空閑存儲空間的管理
UNIX操作系統分析
10. 1 UNIX綜述
UNIX進程控制子系統
UNIX文件系統子系統
參考書籍 1） 《計算機操作系統（第三版）》西安電子科技大學出版社
湯子贏
2） 操作系統概念（中譯版） （六版） 高等教育出版社
Peter Baer Galvin
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
