2019年山東建筑大學(xué)考研初試-《計(jì)算機(jī)專業(yè)綜合》考試大綱

1、《計(jì)算機(jī)專業(yè)綜合》考試大綱山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院山東建筑大學(xué)研究生入學(xué)考試《計(jì)算機(jī)專業(yè)綜合》考試大綱一、數(shù)據(jù)結(jié)構(gòu)（占75分）（一）緒論1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異；2.理解算法的概念、重要特性、設(shè)計(jì)要求，掌握算法的時(shí)間和空間復(fù)雜性分析。（二）線性表1.理解線性表的定義和基本操作；2.掌握線性表順序存儲(chǔ)及基本操作實(shí)現(xiàn)；3.掌握單向循環(huán)鏈表、雙向循環(huán)鏈表的實(shí)現(xiàn)；4.了解靜態(tài)線性表的概念；5.了解

2、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)及適用場(chǎng)合；6.掌握線性表的應(yīng)用，如集合的并、交、差運(yùn)算的實(shí)現(xiàn)，一元多項(xiàng)式求和等。（三）棧和隊(duì)列1.理解棧和隊(duì)列的特性和它們之間的差異，掌握棧和隊(duì)列的適用場(chǎng)合；2.掌握順序棧定義及基本操作的實(shí)現(xiàn)；3.掌握循環(huán)隊(duì)列定義及基本操作的實(shí)現(xiàn)；4.了解優(yōu)先隊(duì)列的概念和常用操作的實(shí)現(xiàn)；5.掌握棧和隊(duì)列的應(yīng)用。（四）樹(shù)與二叉樹(shù)1.理解樹(shù)的基本概念；2.掌握二叉樹(shù)的定義及主要特征；3.掌握二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；4

3、.掌握二叉樹(shù)的先序、中序、后序和層次遍歷及遍歷應(yīng)用；5.理解樹(shù)的存儲(chǔ)結(jié)構(gòu)；6.掌握樹(shù)和森林的遍歷、樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換；7.掌握哈夫曼（Huffman）樹(shù)和哈夫曼編碼。（五）圖1.理解圖的基本概念；2.掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)，掌握?qǐng)D的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；3.了解圖的多重鄰接表和十字鏈表存儲(chǔ)結(jié)構(gòu)；4.掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷；5.掌握?qǐng)D的基本應(yīng)用中的最小生成樹(shù)（Prim和Kruskal）、最短路徑（Dij

4、kstra和Floyd）、拓?fù)渑判蛩惴皬?fù)雜性分析。（六）查找1.理解查找的基本概念；2.掌握順序查找法和查找性能分析；3.掌握折半查找法和查找性能分析；4.掌握二叉排序樹(shù)的定義、構(gòu)造、插入、刪除及查找性能分析；5.理解二叉平衡樹(shù)；了解B＋樹(shù)；6.掌握哈希（Hash）表的構(gòu)造、查找及查找性能分析。（七）內(nèi)部排序1.理解排序的基本概念；2.了解直接插入排序、折半插入排序、簡(jiǎn)單選擇排序；3.掌握希爾排序、快速排序、堆排序、歸并排序、基數(shù)排序

5、《計(jì)算機(jī)專業(yè)綜合》考試大綱山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院使用置換算法（LRU）；時(shí)鐘置換算法（CLOCK）。4.頁(yè)面分配策略5.抖動(dòng)：抖動(dòng)現(xiàn)象；工作集。6.請(qǐng)求分段管理方式（四）輸入輸出（IO）管理（1）IO管理概述1.IO設(shè)備及設(shè)備控制器2.IO控制方式：程序IO、中斷驅(qū)動(dòng)IO、直接存儲(chǔ)器訪問(wèn)IO和通道IO3.IO軟件層次結(jié)構(gòu)：中斷處理程序、設(shè)備驅(qū)動(dòng)程序、設(shè)備獨(dú)立性軟件、用戶層IO軟件（2）設(shè)備分配1.分配中使用的數(shù)據(jù)結(jié)構(gòu)2.獨(dú)占設(shè)

6、備的分配過(guò)程3.假脫機(jī)技術(shù)（SPOOLing）（3）提高性能的高速緩存與緩沖區(qū)（五）文件管理（1）文件系統(tǒng)基礎(chǔ)1.文件概念2.文件邏輯結(jié)構(gòu)：順序文件；索引文件；索引順序文件。3.目錄結(jié)構(gòu)：文件控制塊和索引節(jié)點(diǎn)；單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)；樹(shù)形目錄結(jié)構(gòu)；目錄的查詢技術(shù)。4.文件共享及保護(hù)（2）磁盤組織與管理1.外存的組織方式文件的物理機(jī)構(gòu)：連續(xù)分配、鏈接分配、索引分配2.磁盤存儲(chǔ)空間管理：空閑表鏈法、位示圖法、成組鏈接法3.磁盤調(diào)度算法：

7、先來(lái)先服務(wù)、最短尋道、掃描算法、循環(huán)掃描等三、參考書(shū)目[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社[2](美)EllisHowitz，SartajSahni，DineshMehta著，張力等譯.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(C語(yǔ)言版)(第2版)[M].北京：清華大學(xué)出版社[3]湯子瀛.計(jì)算機(jī)操作系統(tǒng)(修訂版)[M].西安電子科技大學(xué)出版社，2005年1月[4]湯小丹等.計(jì)算機(jī)操作系統(tǒng)學(xué)習(xí)指導(dǎo)與題解[M].西安電子科技大學(xué)出版社