820計算機專業(yè)基礎考綱

1、考試科目820計算機專業(yè)基礎考試形式筆試(閉卷)考試時間180分鐘考試總分150分本科目包括數(shù)據(jù)結構和計算機操作系統(tǒng)兩門課程，總分150分，兩門課程各占 75分數(shù)據(jù)結構一、總體要求數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，是計算機科學與技術學科的核心課程。要求：1. 理解數(shù)據(jù)結構的基本概念； 掌握數(shù)據(jù)的邏輯結構、 存儲結構及其差異，以及各種基本操作的實現(xiàn)。2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎上，能夠分析算法的時間復雜度與空間復雜度。3. 能夠選擇合適的數(shù)據(jù)結構和算法策略進行問題求解，具備采用 C或C+或 JAVA語言設計與實現(xiàn)算法的能力。二、內(nèi)容1. 數(shù)據(jù)結構及算法的相關概念和術語(1)

2、 數(shù)據(jù)結構及算法的概念；(2) 數(shù)據(jù)的邏輯結構和存儲結構；(3) 算法的定義及特性；(4) 算法時間復雜度和空間復雜度的分析方法。2. 線性表(1) 線性表的定義(2) 線性表的基本操作及在順序存儲及鏈式存儲上的實現(xiàn)；(3) 各種變形鏈表(循環(huán)鏈表、雙向鏈表、帶頭結點的鏈表等)的表示和基本操作的實現(xiàn)；(4) 遞歸過程的特點及實現(xiàn)方法；(5) 棧和隊列的基本概念；棧和隊列的順序存儲結構、鏈式儲存結構及其存儲特點；(6)棧和隊 列的應用(7) 循環(huán)隊列的判滿、判空方法；(8) 特殊矩陣的壓縮儲存；3. 廣義表的基本概念、存儲結構和基本操作4. 樹和二叉樹(1) 樹與森林的基本概念(2) 樹與森林的

3、存儲結構及遍歷(3) 二叉樹的定義及 6大性質(zhì)(4) 二叉樹的順序儲存與鏈式儲存結構(5) 二叉樹的先序、中序、后序三種遍歷方式的關系以及實現(xiàn)；層序遍歷的實現(xiàn)(6) 線索二叉樹的基本概念與構造方法(7) 樹與二叉樹的應用：二叉排序樹；二叉平衡樹；哈夫曼樹與哈夫曼編碼5. 圖(1) 圖的基本概念和術語；(2) 圖的存儲結構：鄰接矩陣、鄰接表、逆鄰接表；(3) 遍歷算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法；(4) 應用：最小生成樹；最短路徑，拓撲排序和關鍵路徑。6. 查找(1) 查找的基本概念；靜態(tài)查找與動態(tài)查找；(2) 順序查找、折半查找、索引查找(3) 哈希查找哈希函數(shù)的基本構造方法，解決地址

4、沖突的基本策略；(4) 各種查找算法的時間復雜度和空間復雜度。7 排序(1) 排序的基本概念(2) 插入排序(3) 簡單選擇排序(4) 希爾排序(5) 快速排序(6) 堆排序(7) 歸并排序(8) 基數(shù)排序(9) 排序算法的比較。三、題型及分值比例1. 填空題(10分)2. 單選題(20分)3. 簡答題(30分)4. 算法題(15分)其中算法題分為閱讀、修改和編寫算法三類：(1) 閱讀算法：閱讀指定算法，回答使用的數(shù)據(jù)結構、算法實現(xiàn)的功能或執(zhí)行的結果；(2) 修改算法：閱讀指定算法，指出算法的錯誤并修正；指出算法的不足并改進；按給定功能填寫 算法空缺部分；(3) 編寫算法：根據(jù)算法功能要求，選

5、擇或者設計合適的數(shù)據(jù)結構，用程序設計語言編寫算法，實 現(xiàn)指定功能。以上皆可分析給定或者設計的算法時空復雜度。操作系統(tǒng)部分一、總體要求主要考察學生對操作系統(tǒng)基本概念、原理的理解程度，重點考察操作系統(tǒng)的設計方法與實現(xiàn)技術, 同時能夠具備運用所學的操作系統(tǒng)原理、方法與技術分析問題和解決問題的能力。二、內(nèi)容及比例1. 操作系統(tǒng)的基本概念1) 批處理與多道程序設計2) 分時系統(tǒng)與實時系統(tǒng)3) 操作系統(tǒng)的基本類型與特征4) 并發(fā)與并行的概念5）操作系統(tǒng)的層次結構與功能模塊6）程序的并發(fā)執(zhí)行與順序執(zhí)行2. 處理機管理1）進程：進程控制塊、進程的幾種基本狀態(tài)與狀態(tài)轉換（進程的創(chuàng)建、進程的終止、進程的 阻塞與喚

6、醒、進程的掛起與激活等）2）進程的同步與互斥：臨界資源、臨界區(qū)、進程同步與互斥問題、信號量機制以及P、V操作、管程機制。3）進程間通信：進程通信的類型（直接通信和間接通信方式）、消息傳遞系統(tǒng)中的幾個問題、 消息緩沖隊列通信機制。4）線程與進程的調(diào)度：線程與進程的基本概念，調(diào)度的類型、調(diào)度隊列模型、調(diào)度方式、進 程調(diào)度算法（先來先服務、短進程優(yōu)先、時間片輪轉、基于優(yōu)先級的調(diào)度算法等）。5）死鎖:死鎖的基本概念，死鎖定理、死鎖預防、死鎖避免與處理死鎖的基本方法、銀行家 算法。6）綜合應用：生產(chǎn)者消費者問題、讀者和寫者問題、哲學家進餐問題等。3. 內(nèi)存管理1）內(nèi)存管理的需求：重定位、內(nèi)存保護、內(nèi)存共

7、享2）程序的裝入和鏈接：靜態(tài)裝入和可重定位裝入、靜態(tài)鏈接、動態(tài)鏈接、運行時動態(tài)鏈接。3）分區(qū)存儲管理：分區(qū)方式（單一連續(xù)分區(qū)、固定分區(qū)、可變式分區(qū)）、分區(qū)分配算法（首 次適應算法、循環(huán)首次適應算法、最佳適應法、最壞適應法等）。4）段式管理與頁式管理：段、頁、碎片等基本概念、段式管理與頁式管理機制5）虛擬內(nèi)存：局部性原理、虛擬內(nèi)存概念、請求分段與請求分頁、段頁式管理、段頁式地址結構與地址轉換、頁面置換算法（先進先出、LRU Clock置換）、抖動4. 設備管理1）I/O系統(tǒng)的：基本概念、I/O控制方式（程序I/O、中斷、DMA通道）、相關數(shù)據(jù)結構、 緩沖管理（單緩沖、雙緩沖、循環(huán)緩沖、緩沖池）2）磁盤管理與磁盤調(diào)度算法：SSTF算法，SCAN算法，CSCAN算法，N-STEP-SCAN算法，F(xiàn)SCAN算法3）設備分配、設備處理、虛擬設備，Spooli ng系統(tǒng)5. 文件系統(tǒng)1）基本概念：文件和文件系統(tǒng)、目錄、文件結構的物理結構和邏輯結構（順序文件、索引順 序文件、索引文件、H