暨南大學(xué)碩士研究生入學(xué)考試自命題科目

暨南大學(xué)碩士研究生入學(xué)考試自命題科目848《計算機基礎(chǔ)綜合》考試大綱Ⅰ考試形式一、試卷滿分及考試時間本試卷滿分為150分，考試時間為180分鐘二、答題方式答題方式為閉卷、筆試三、試卷內(nèi)容結(jié)構(gòu)7575Ⅱ考查內(nèi)容數(shù)據(jù)結(jié)構(gòu)【考查目標】理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。一、基本概念和術(shù)語（一）數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型等概念（二）算法設(shè)計的基本要求（三）語句的頻度和估算時間復(fù)雜度二、線性表（一）線性表的定義和基本操作（二）線性表的實現(xiàn)1．順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)三、棧、隊列和數(shù)組（一）棧和隊列的基本概念（二）棧和隊列的順序存儲結(jié)構(gòu)（三）棧和隊列的鏈式存儲結(jié)構(gòu)（四）棧和隊列的應(yīng)用（五）特殊矩陣的壓縮存儲四、樹與二叉樹棧（一）樹的概念（二）二叉樹二叉樹的定義及其主要特征二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)二叉樹的遍歷線索二叉樹的基本概念和構(gòu)造二叉排序樹平衡二叉樹（三）樹、森林樹的存儲結(jié)構(gòu)森林與二叉樹的轉(zhuǎn)換樹和森林的遍歷（四）樹的應(yīng)用12．哈夫曼(Huffman)樹和哈夫曼編碼五、圖（一）圖的概念（二）圖的存儲結(jié)構(gòu)及基本操作鄰接矩陣鄰接表（三）圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索（四）圖的基本應(yīng)用最?。ù鷥r）生成樹拓撲排序關(guān)鍵路徑最短路徑六、查找（一）查找的基本概念（二）順序查找法（三）折半查找法（四）B-樹（五）散列(Hash)表及其查找（六）查找算法的分析及應(yīng)用七、內(nèi)部排序（一）排序的基本概念（二）插入排序直接插入排序折半插入排序（三）氣泡排序（bubblesort）（四）簡單選擇排序（五）希爾排序（shellsort）（六）快速排序（七）堆排序（八）二路歸并排序(mergesort)（九）基數(shù)排序（十）各種內(nèi)部排序算法的比較（十一）內(nèi)部排序算法的應(yīng)用操作系統(tǒng)【考查目標】掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)的整體運行過程。I/OC一、操作系統(tǒng)概述(一)操作系統(tǒng)的概念、特征、功能和提供的服務(wù)(二)操作系統(tǒng)的發(fā)展與分類(三)操作系統(tǒng)的運行環(huán)境內(nèi)核態(tài)與用戶態(tài)中斷、異常系統(tǒng)調(diào)用(四)操作系統(tǒng)體系結(jié)構(gòu)二、進程管理(一)進程與線程進程概念進程的狀態(tài)與轉(zhuǎn)換進程控制進程組織進程通信共享存儲系統(tǒng)，消息傳遞系統(tǒng)，管道通信。調(diào)度的基本概念3調(diào)度方式典型調(diào)度算法先來先服務(wù)調(diào)度算法，短作業(yè)(短進程、短線程)優(yōu)先調(diào)度算法，時間片輪轉(zhuǎn)調(diào)度算法，優(yōu)先級調(diào)度算法，高響應(yīng)比優(yōu)先調(diào)度算法，多級反饋隊列調(diào)度算法。進程同步的基本概念實現(xiàn)臨界區(qū)互斥的基本方法軟件實現(xiàn)方法，硬件實現(xiàn)方法。信號量管程經(jīng)典同步問題生產(chǎn)者-消費者問題，讀者-寫者問題，哲學(xué)家進餐問題。(四)死鎖死鎖的概念死鎖處理策略死鎖預(yù)防死鎖避免系統(tǒng)安全狀態(tài)，銀行家算法。三、內(nèi)存管理(一)內(nèi)存管理基礎(chǔ)內(nèi)存管理概念程序裝入與鏈接，邏輯地址與物理地址空間，內(nèi)存保護。交換與覆蓋連續(xù)分配管理方式非連續(xù)分配管理方式分頁管理方式，分段管理方式，段頁式管理方式。虛擬內(nèi)存基本概念請求分頁管理方式頁面置換算法(OT(FIO)(LU)，時鐘置換算法(CLOCK頁面分配策略工作集(一)文件系統(tǒng)基礎(chǔ)文件概念文件的邏輯結(jié)構(gòu)順序文件，索引文件，索引順序文件。目錄結(jié)構(gòu)文件控制塊和索引節(jié)點，單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)，樹形目錄結(jié)構(gòu)，圖形目錄結(jié)構(gòu)。文件共享文件保護訪問類型，訪問控制。(二)文件系統(tǒng)實現(xiàn)文件系統(tǒng)層次結(jié)構(gòu)目錄實現(xiàn)文件實現(xiàn)(三)磁盤組織與管理磁盤的結(jié)構(gòu)磁盤調(diào)度算法磁盤的管理五