初試-《計算機專業(yè)綜合》2019山東建筑大學考研專業(yè)課考試大綱

1、《計算機專業(yè)綜合》考試大綱山東建筑大學計算機科學與技術學院山東建筑大學研究生入學考試《計算機專業(yè)綜合》考試大綱一、數據結構（占75分）（一）緒論1.理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異；2.理解算法的概念、重要特性、設計要求，掌握算法的時間和空間復雜性分析。（二）線性表1.理解線性表的定義和基本操作；2.掌握線性表順序存儲及基本操作實現；3.掌握線性表鏈式存儲及基本操作實現，包括單鏈表、單向循環(huán)鏈表、雙向循環(huán)鏈表

2、的實現；4.了解靜態(tài)線性表的概念；5.了解順序存儲和鏈式存儲的優(yōu)缺點及適用場合；6.掌握線性表的應用，如集合的并、交、差運算的實現，一元多項式求和等。（三）棧和隊列1.理解棧和隊列的特性和它們之間的差異，掌握棧和隊列的適用場合；2.掌握順序棧和鏈棧定義及基本操作的實現；3.掌握循環(huán)隊列和鏈隊列定義及基本操作的實現；4.了解優(yōu)先隊列的概念和常用操作的實現；5.掌握棧和隊列的應用。（四）樹與二叉樹1.理解樹的基本概念；2.掌握二叉樹的定義及

3、主要特征；3.掌握二叉樹的順序存儲結構和鏈式存儲結構；4.掌握二叉樹的先序、中序、后序和層次遍歷及遍歷應用；5.理解樹的存儲結構；6.掌握樹和森林的遍歷、樹和森林與二叉樹的轉換；7.掌握哈夫曼（Huffman）樹和哈夫曼編碼。（五）圖1.理解圖的基本概念；2.掌握圖的鄰接矩陣和鄰接表存儲結構，掌握圖的基本操作在兩種存儲結構上的實現；3.了解圖的多重鄰接表和十字鏈表存儲結構；4.掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷；5.掌握圖的基本應用中的

4、最小生成樹（Prim和Kruskal）、最短路徑（Dijkstra和Floyd）、拓撲排序算法及復雜性分析。（六）查找1.理解查找的基本概念；2.掌握順序查找法和查找性能分析；3.掌握折半查找法和查找性能分析；4.掌握二叉排序樹的定義、構造、插入、刪除及查找性能分析；5.理解二叉平衡樹；了解B＋樹；6.掌握哈希（Hash）表的構造、查找及查找性能分析。（七）內部排序1.理解排序的基本概念；2.了解直接插入排序、折半插入排序、簡單選擇排序

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

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

7、：先來先服務、最短尋道、掃描算法、循環(huán)掃描等三、參考書目[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社[2]（美）薩尼（Sahni，S.）著，汪詩林等譯.數據結構、算法與應用（C語言描述）.北京：機械工業(yè)出版社.[3]劉小晶、杜選主編.數據結構——Java語言描述（第2版）.北京：清華大學出版社。[4]湯小丹，梁紅兵，湯子瀛等.計算機操作系統(tǒng)（第四版）[M].西安電子科技大學出版社.2014年5月第4版[5]湯小