|
|
|
|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
825 計算機專業基礎 B 研究生入學考試大綱-南京理工大學
數據結構部分：
一、課程的地位與作用
《數據結構》課程是計算機專業的核心課程之一，是一門綜合性的專業基礎課，它介于數
學，計算機硬件，計算機軟件之間。是高級程序設計語言，編譯原理，操作系統，數據庫，人
工智能等課程的基礎。同時，數據結構的技術也廣泛應用于信息科學、系統工程，應用數學，
以及各種工程技術領域。
二、課程的教學目標與基本要求
課程目的是使學生了解計算機應用中數據對象的特性，學會在應用中, 根據現實世界中的
問題選擇適當的數據邏輯結構和存儲結構以及相應算法, 并且培養基本的、良好的程序設計技
能。
三、課程內容（重點△，難點★）
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
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
總 計 40 8 48
五、課程說明
課程英文名稱 Data Structure
主要先修課程 C++程序設計
適用專業類別 計算機科學與技術
主要教材（作者、教材
名稱、出版社）
“數據結構與算法分析” 張琨 張宏 朱保平 人民郵電出版
社,2016
考核方式 考試
課程簡介 各種類型的數據結構和查找，排序的各種方法
必 開
實 驗
項 目
序號 項 目 名 稱 學時
1 線性表鏈式存儲結構的應用 3
2 二叉樹 2
3 Hash 表應用 2
4
5
6
7
8
操作系統部分：
1 緒論
1.1 操作系統的目標和作用
1.2 操作系統的發展過程
1.3 操作系統的基本特征
1.4 操作系統的主要功能
1.5 操作系統結構設計
1.6 硬件保護
2 進程管理
2.1 進程概念
2.1.1 進程的定義
2.1.2 程序的并發執行及其特征
2.1.3 進程的特征與狀態
2.1.4 進程控制塊
2.2 進程控制
2.2.1 進程的創建
2.2.2 進程的終止
2.2.3 進程的阻塞與喚醒
2.2.4 進程的掛起與激活
2.3 進程同步
2.3.1 進程同步的基本概念
2.3.2 硬件和軟件解決進程互斥
2.3.3 信號量機制
2.4 經典進程同步問題
2.5 進程通信
2.5.1 進程通信類型
2.5.2 消息傳遞通信的實現方法
2.6 線程
2.6.1 線程的基本概念
2.6.2 線程的實現方式
3 處理機調度與死鎖
3.1 處理機調度的層次
3.1.1 高級調度
3.1.2 低級調度
3.1.3 中級調度
3.2 調度隊列模型和調度準則
3.2.1 調度隊列模型
3.2.2 選擇調度方式和調度算法的若干準則
3.3 調度算法
3.3.1 先來先服務和短作業優先
3.3.2 優先權調度算法
3.3.3 時間片輪轉的調度算法
3.3.4 高響應比優先的調度算法
3.3.5 多級反饋隊列調度算法
3.4 產生死鎖的原因和必要條件
3.4.1 產生死鎖的原因
3.4.2 產生死鎖的必要條件
3.4.3 處理死鎖的基本方法
3.5 預防死鎖的方法
3.5.1 預防死鎖
3.5.2 系統安全狀態
3.5.3 銀行家算法
3.6 死鎖的檢測與解除
4 存儲器管理
4.1 程序的裝入和鏈接
4.1.1 程序的裝入
4.1.2 程序的鏈接
4.2 連續分配方式
4.2..1 單一連續分配
4.2..2 固定分區分配
4.2..3 動態分區分配
4.2..4 伙伴系統
4.2..5 可重定位分區分配
4.3 基本分頁存儲管理
4.3.1 頁面與頁表
4.3.2 地址變換機構
4.3.3 兩級和多級頁表
4.4 基本分段存儲管理
4.5.1 分段存儲管理方式的引入
4.5.2 分段系統的基本原理
4.5.3 信息共享
4.5.4 段頁式存儲管理
4.5 虛擬存儲器的基本概念
4.5.1 虛擬存儲器的引入
4.5.2 虛擬存儲器的實現方法
4.5.3 虛擬存儲器的特征
4.6 請求分頁存儲管理
4.6.1 請求分頁中的硬件支持
4.6.2 內存分配策略和分配算法
4.6.3 調頁策略
4.7 頁面置換算法
4.7.1 最佳置換算法和先進先出置換算法
4.7.2 LRU 置換算法
4.7.3 CLOCK 置換算法
4.7.4 其他置換算法
4.8 請求分段存儲管理
4.8.1 請求分段中的硬件支持
4.8.2 分段的共享和保護
5 設備管理
5.1 緩沖管理
5.1.1 緩沖的引入
5.1.2 單緩沖和雙緩沖
5.1.3 循環緩沖
5.1.4 緩沖池
5.2 I/O 軟件
5.2.1 I/O 軟件的設計目標和原則
5.2.2 中斷處理程序
5.2.3 設備驅動程序
5.2.4 設備獨立性軟件
5.2.5 用戶層的 I/O 軟件
5.3 設備分配
5.3.1 設備分配中的數據結構
5.3.2 設備分配時應考慮的因素
5.3.3 獨占設備的分配程序
5.3.4 SPOOLing 技術
5.4 磁盤存儲器的管理
5.4.1 磁盤調度
5.4.2 磁盤高速緩存
5.4.3 提高磁盤 I/O 速度的其它方法
6 文件管理
6.1 文件和文件系統
6.1.1 文件、記錄和數據項
6.1.2 文件類型和文件系統模型
6.1.3 文件操作
6.2 文件的邏輯結構
6.2.1 文件邏輯結構的類型
6.2.2 順序文件
6.2.3 索引文件
6.2.4 索引順序文件
6.3 外存分配方式
6.3.1 連續分配
6.3.2 鏈接分配
6.3.3 FAT 和 NTFS 技術
6.3.4 索引分配
6.4 目錄管理
6.4.1 文件控制塊和索引結點
6.4.2 目錄結構
6.4.3 目錄查詢技術
6.5 文件存儲空間的管理
6.5.1 空閑表法和空閑鏈表法
6.5.2 位示圖法
6.5.3 成組鏈接法
6.6 文件共享與文件保護
6.6.1 基于索引結點的共享方式
6.6.2 利用符號鏈實現文件共享
參考書籍 1) 《計算機操作系統（第三版）》西安電子科技大學出版社
湯小丹等
2) 《操作系統概念 (中譯版) (第七版)》 高等教育出版社
Abraham Silberschatz 等
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
|
|
上一篇文章： 2018年南京理工大學計算機專業基礎（A）考研大綱
下一篇文章： 2018年南京理工大學計算機專業基礎（C）考研大綱
|
|
|
|
|
|
文章搜索
您現在的位置： 
