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