|
|
|
|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
824 計算機專業基礎 A 研究生入學考試大綱-南京理工大學
離散數學部分：
1 命題演算基礎
1．1 命題與聯結詞
①命題 ②聯結詞 ③合式公式 ④命題的符號化
1.2 真假性
①解釋 ②等價公式 ③聯結詞的完備集 ④對偶式和內否式。
1.3 范式及其應用
①范式 ②主范式
2 命題演算的推理理論
2.1 命題演算的公理系統
①公理系統的組成部分 ②公理系統的推理過程
2.2 命題演算的假設推理系統
①假設推理系統的組成 ②假設推理系統的推理過程
2.3 命題演算的歸結推理法
①歸結證明過程②歸結證明方法
3 謂詞演算基礎
3.1 謂詞和個體
①個體 ②謂詞 ③語句的符號化
3.2 函數和量詞
①函數項 ②量詞
3.4 永真性和可滿足性
①真假性 ②同真假性 ③永真性和可滿足性 ④范式
4 謂詞演算的推理理論
4.1 謂詞演算的永真公理系統
①公理系統的組成部分 ②公理系統的推理過程
4.2 謂詞演算的假設推理系統
①假設推理系統的組成及證明方法 ②定理的推導過程
4.3 謂詞演算的歸結系統
①置換 ②歸結反演系統 ③霍恩子句邏輯程序
5 遞歸函數論
5.1 數論函數和數論謂詞
5.2 函數的構造
6 集合
6．1 集合的基本概念
①集合；②子集合；③空集合；④集合的相等。
6．2 集合的基本運算
①集合的運算；②集合的交；③集合的并；④集合的差；⑤集合的對稱差；⑥集合的廣義交；
⑦集合的廣義并；⑧冪集合。
6．3 全集和集合的補
①全集；②集合的補；③德·摩根定律。
6．4 自然數與自然數集
①自然數；②自然數集；③數學歸納法；④集合的歸納定義。
6．5 包含與排斥原理
①有限集；②包含與排斥原理。
7 關系
7．1 集合的笛卡爾積集
①有序對；②集合的笛卡爾積集；③有序 n(n? 2)元組；④n 重(n? 2)笛卡爾積集。
7．2 二元關系的基本概念
①二元關系；②二元關系的表示；③二元關系的圖形表示；④二元關系的矩表示；⑤二元關
系的運算；⑥二元關系的復合運算；⑦二元關系的逆關系。
7．3 二元關系的性質
①二元關系的性質；②自反的二元關系；③反自反的二元關系 ；④對稱的二元關系；⑤反
對稱的二元關系；⑥傳遞的二元關系。
7．4 二元關系的閉包運算
①二元關系的閉包運算；②自反閉包；③對稱閉包；④傳遞閉包。
7．5 等價關系與集合的劃分
①等價關系；②等價類；③集合的劃分；④商集合。
7．6 偏序關系和格
①偏序關系；②偏序集；③極大元；④極小元；⑤最大元；⑥最小元； ⑦最小上界；⑧最
大下界；⑨可比；⑩覆蓋；⑾有序集；⑿良序集；⒀格。
8 函數與集合的勢
8．1 函數的基本概念
①函數（映射）；②定義域；③陪域；④值域；⑤象集；⑥原象集；⑦單射函數；⑧滿射函
數；⑨雙射函數。
8．2 函數的復合與可逆函數
①函數的復合；②左可逆函數；③右可逆函數；④可逆函數。
8．3 無限集
①集合的勢；②無限集；③集合的勢相等；④可數無限集；⑤不可數無限集； ⑥集合勢大
小的比較。
9 圖論
9．1 圖的基本概念
①有向圖；②無向圖；③頂點集；④邊集；⑤自環；⑥孤立點；⑦多重邊；⑧簡單圖；⑨完
全圖；⑩關聯；⑾鄰接；⑿圖的同構；⒀子圖；⒁生成子圖；⒂補圖；⒃圖的頂點度數（次
數）；⒄圖的頂點度數和與邊數關系。
9．2 圖中的通路、圖的連通性與圖的矩陣表示
①圖中的通路；②簡單通路；③初等通路；④回路；⑤簡單回路；⑥初等回路（圈）；⑦連
通圖；⑧有向連通圖；⑨有向單側連通圖；⑩有向強連通圖；⑾ 圖的鄰接矩陣；⑿圖的關
聯矩陣；⒀圖的可達矩陣。
9．3 帶權圖與帶權圖中最短通路
①帶權圖；②帶權圖的最短通路；③狄克斯瑞（Dijkstra）算法。
9．4 歐拉圖
①歐拉圖；②歐拉通路；③歐拉回路；④歐拉定理。
9．5 哈密爾頓圖與貨郎擔問題
①哈密爾頓通路；②哈密爾頓回路（圈）；③哈密爾頓圖；④哈密爾頓圖的必要條件；⑤哈
密爾頓圖的充分條件；⑥貨郎擔問題；⑦最鄰近算法。
9．6 二部圖
①二部圖（偶圖）；②二部圖的充要條件；③二部圖的匹配；④二部圖的極大匹配；⑤二部
圖的完美匹配。
9．7 平面圖
①平面圖；②平面圖的歐拉定理；③平面圖的必要條件；④平面圖的區域著色。
10 樹
10．1 樹的基本概念
①樹；②樹中頂點與邊關系公式；③樹的等價定義。
10．2 連通圖的生成樹與帶權圖的最小生成樹
①連通圖的生成樹；②割集；③割集與生成樹的關系；④帶權圖最小生成樹的算法。
10．3 有序樹
①有向樹；②根樹；③有序樹；④有序 n (n? 2)分樹；⑤正則有序 n (n? 2) 分樹。
10．4 前綴碼和最優二分樹
①前綴碼；②帶權圖的最優二分樹；③霍夫曼（Huffman）算法。
11 群和環
11．1 代數運算的基本概念
①二元運算；②封閉的二元運算；③可結合的二元運算；④可交換的二元運算；⑤n 元運算
11．2 代數系統和半群
①代數系統；②左么元；③右么元；④么元；⑤半群；⑥含么半群（獨異點）；⑦半群的同
態；⑧子半群；⑨子含么半群。
11．3 群的基本概念
①左逆元；②右逆元；③逆元；④群；⑤有限群；⑥交換群；⑦群同態；⑧群同構；⑨群中
元素的階。
11．4 變換群和置換群
①變換含么半群；②變換群；③置換群；④n 個文字對稱群。
11．5 循環群
①循環群。
11．6 子群、群的子集生成的群
①子群。
11．7 子群的陪集
①子群的陪集；②子群在群中的指數；③群中拉格朗日定理。
11．8 正規子群、商群、群同態
①正規子群；②商群；③群的同態基本定理。
主要參考教材：朱保平,葉有培,張琨.離散數學(第 2 版).北京：北京理
工大學出版社，2014
數據結構部分：
一、課程的地位與作用
《數據結構》課程是計算機專業的核心課程之一，是一門綜合性的專業基礎課，它介于數
學，計算機硬件，計算機軟件之間。是高級程序設計語言，編譯原理，操作系統，數據庫，人
工智能等課程的基礎。同時，數據結構的技術也廣泛應用于信息科學、系統工程，應用數學，
以及各種工程技術領域。
二、課程的教學目標與基本要求
課程目的是使學生了解計算機應用中數據對象的特性，學會在應用中, 根據現實世界中的
問題選擇適當的數據邏輯結構和存儲結構以及相應算法, 并且培養基本的、良好的程序設計技
能。
三、課程內容（重點△，難點★）
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年南京理工大學基礎英語考研大綱
下一篇文章： 2018年南京理工大學計算機專業基礎（B）考研大綱
|
|
|
|
|
|
文章搜索
您現在的位置： 
