暨南大學(xué)848計算機基礎(chǔ)綜合研究生考研大綱及參考書目 正文

暨南大學(xué)碩士研究生入學(xué)考試自命題科目848《計算機基礎(chǔ)綜合》考試大綱
　　　
Ⅰ考試形式
一、試卷滿分及考試時間
本試卷滿分為 150 分，考試時間為 180 分鐘二、答題方式
答題方式為閉卷、筆試三、試卷內(nèi)容結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu) 75 分
操作系統(tǒng) 75 分

Ⅱ考查內(nèi)容
數(shù)據(jù)結(jié)構(gòu)【考查目標(biāo)】
1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。
2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計與分析。
3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。一、基本概念和術(shù)語
（一）數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型等概念
（二）算法設(shè)計的基本要求
（三）語句的頻度和估算時間復(fù)雜度二、線性表
（一）線性表的定義和基本操作
（二）線性表的實現(xiàn)1．順序存儲結(jié)構(gòu)
2.鏈?zhǔn)酱鎯Y(jié)構(gòu)
3.線性表的應(yīng)用三、棧、隊列和數(shù)組
（一）棧和隊列的基本概念
（二）棧和隊列的順序存儲結(jié)構(gòu)
（三）棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)
（四）棧和隊列的應(yīng)用
（五）特殊矩陣的壓縮存儲四、樹與二叉樹棧
（一）樹的概念
（二）二叉樹
1.二叉樹的定義及其主要特征
2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

3.二叉樹的遍歷
4.線索二叉樹的基本概念和構(gòu)造
5.二叉排序樹
6.平衡二叉樹
（三）樹、森林
1.樹的存儲結(jié)構(gòu)
2.森林與二叉樹的轉(zhuǎn)換
3.樹和森林的遍歷
（四）樹的應(yīng)用 1．特價類問題
2．哈夫曼(Huffman)樹和哈夫曼編碼
五、圖
（一）圖的概念
（二）圖的存儲結(jié)構(gòu)及基本操作
1.鄰接矩陣
2.鄰接表
（三）圖的遍歷
1.深度優(yōu)先搜索
2.廣度優(yōu)先搜索
（四）圖的基本應(yīng)用
1.最?。ù鷥r）生成樹
2.拓?fù)渑判?br /> 3.關(guān)鍵路徑
4.最短路徑
六、查找
（一）查找的基本概念
（二）順序查找法
（三）折半查找法
（四）B-樹
（五）散列(Hash)表及其查找
（六）查找算法的分析及應(yīng)用七、內(nèi)部排序
（一）排序的基本概念
（二）插入排序
1.直接插入排序
2.折半插入排序
（三）氣泡排序（bubble sort）
（四）簡單選擇排序

（五）希爾排序（shell sort）
（六）快速排序
（七）堆排序
（八）二路歸并排序(merge sort)
（九）基數(shù)排序
（十）各種內(nèi)部排序算法的比較
（十一）內(nèi)部排序算法的應(yīng)用

操作系統(tǒng)【考查目標(biāo)】
1.掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)的整體運行過程。
2.掌握操作系統(tǒng)進(jìn)程、內(nèi)存、文件和 I/O 管理的策略、算法、機制以及相互關(guān)系。
3.能夠運用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題，并能利用 C 語言描述相關(guān)算法。
一、操作系統(tǒng)概述
(一) 操作系統(tǒng)的概念、特征、功能和提供的服務(wù)(二) 操作系統(tǒng)的發(fā)展與分類
(三) 操作系統(tǒng)的運行環(huán)境
1.內(nèi)核態(tài)與用戶態(tài)
2.中斷、異常
3.系統(tǒng)調(diào)用
(四)操作系統(tǒng)體系結(jié)構(gòu)二、進(jìn)程管理
(一) 進(jìn)程與線程
1.進(jìn)程概念
2.進(jìn)程的狀態(tài)與轉(zhuǎn)換
3.進(jìn)程控制
4.進(jìn)程組織
5.進(jìn)程通信
共享存儲系統(tǒng)，消息傳遞系統(tǒng)，管道通信。
6.線程概念與多線程模型(二) 處理機調(diào)度
1.調(diào)度的基本概念
2.調(diào)度時機、切換與過程3 調(diào)度的基本準(zhǔn)則
4.調(diào)度方式
5.典型調(diào)度算法
先來先服務(wù)調(diào)度算法，短作業(yè) (短進(jìn)程、短線程 )優(yōu)先調(diào)度算法，時間片輪轉(zhuǎn)

調(diào)度算法，優(yōu)先級調(diào)度算法，高響應(yīng)比優(yōu)先調(diào)度算法，多級反饋隊列調(diào)度算法。   (三) 同步與互斥
1.進(jìn)程同步的基本概念
2.實現(xiàn)臨界區(qū)互斥的基本方法
軟件實現(xiàn)方法，硬件實現(xiàn)方法。
3.信號量
4.管程
5.經(jīng)典同步問題
生產(chǎn)者-消費者問題，讀者 -寫者問題，哲學(xué)家進(jìn)餐問題。(四) 死鎖
1.死鎖的概念
2.死鎖處理策略
3.死鎖預(yù)防
4.死鎖避免
系統(tǒng)安全狀態(tài)，銀行家算法。
5.死鎖檢測和解除三、內(nèi)存管理
(一) 內(nèi)存管理基礎(chǔ)
1.內(nèi)存管理概念
程序裝入與鏈接，邏輯地址與物理地址空間，內(nèi)存保護(hù)。
2.交換與覆蓋
3.連續(xù)分配管理方式
4.非連續(xù)分配管理方式
分頁管理方式，分段管理方式，段頁式管理方式。  (二) 虛擬內(nèi)存管理
1.虛擬內(nèi)存基本概念
2.請求分頁管理方式
3.頁面置換算法
最佳置換算法 (OPT)，先進(jìn)先出置換算法 (FIFO)，最近最少使用置換算法 (LRU) ，時鐘置換算法 (CLOCK) 。
4.頁面分配策略
5.工作集
6.抖動四、文件管理
(一) 文件系統(tǒng)基礎(chǔ)
1.文件概念
2.文件的邏輯結(jié)構(gòu)
順序文件，索引文件，索引順序文件。

3.目錄結(jié)構(gòu)
文件控制塊和索引節(jié)點， 單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)， 樹形目錄結(jié)構(gòu)，圖形目
錄結(jié)構(gòu)。
4.文件共享
5.文件保護(hù)
訪問類型，訪問控制。(二) 文件系統(tǒng)實現(xiàn)
1.文件系統(tǒng)層次結(jié)構(gòu)
2.目錄實現(xiàn)
3.文件實現(xiàn)
(三) 磁盤組織與管理
1.磁盤的結(jié)構(gòu)
2.磁盤調(diào)度算法
3.磁盤的管理
五、輸入輸出 (I/O) 管理(一) I/O 管理概述
1.I/O 控制方式
2.I/O 軟件層次結(jié)構(gòu)(二) I/O 核心子系統(tǒng)
1.I/O 調(diào)度概念
2.高速緩存與緩沖區(qū)
3.設(shè)備分配與回收
4.假脫機技術(shù) (SPOOLing)

Ⅲ特別推薦
1.嚴(yán)蔚敏，吳偉民, 數(shù)據(jù)結(jié)構(gòu)（C 語言版）,清華大學(xué)出版社出版
2.嚴(yán)蔚敏, 吳偉民,《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析》,清華大學(xué)出版社出版
3.湯小丹，梁紅兵，《計算機操作系統(tǒng)》，西安電子科技大學(xué)出版社

暨南大學(xué)

本文來源：http://www.qiang-kai.com/jinandaxue/cankaoshu_457509.html