1、考試科目820計算機專業基礎考試形式筆試（閉卷）考試時間180分鐘考試總分150分本科目包括數據結構和計算機操作系統兩門課程，總分150分，兩門課程各占75分數據結構一、總體要求 數據結構是計算機程序設計的重要理論技術基礎，是計算機科學與技術學科的核心課程。要求學生通過數據結構課程的學習，能夠針對具體的應用和算法策略選擇和設計恰當的數據結構，并能編程實現。二、內容及比例數據結構部分主要考試內容（帶下劃線文字表示重點部分）：1. 數據結構及算法的相關概念和術語重點：數據結構及算法的概念；數據的邏輯結構和存儲結構；算法的定義及特性；算法時間復雜度和空間復雜度的分析方法。2線性表（包括棧、隊列和數組

2、）的存儲結構、基本運算及應用重點：線性表、棧和隊列的存儲結構及其存儲特點；線性表的基本操作在順序存儲及鏈式存儲上的實現；各種變形鏈表（循環鏈表、雙向鏈表、帶頭結點的鏈表等）的表示和基本操作的實現；遞歸過程的特點及實現方法；循環隊列的判滿、判空方法；稀疏矩陣的存儲方法（三元組、十字鏈表）和基本運算的實現（轉置、矩陣加法等）。3廣義表的存儲結構、基本運算及應用重點：廣義表的基本概念、基本操作及存儲結構。4樹和二叉樹的存儲結構、遍歷算法及應用重點：二叉樹和樹的遞歸定義、基本術語、基本性質；滿二叉樹和完全二叉樹的概念及特征；二叉樹、樹及森林的順序存儲及鏈式存儲，以及相互轉換算法；線索二叉樹、二叉排序樹

3、的構建；各種遍歷算法；哈夫曼樹和哈夫曼編碼的構建和應用。5圖的存儲結構、遍歷算法及應用重點：圖的基本概念和術語；圖的基本存儲方法：鄰接矩陣、關聯矩陣、鄰接表、逆鄰接表、十字鏈表；圖的遍歷算法：深度優先搜索算法和廣度優先搜索算法；圖的基本應用：最小生成樹、最短路徑，拓撲排序和關鍵路徑。6靜態查找表、動態查找表和哈希表（包括二叉排序樹、AVL樹）重點：靜態查找表、動態查找表和哈希表上的查找方法；哈希函數的基本構造方法，解決地址沖突的基本策略；理解各查找算法的時間復雜度和空間復雜度。7五類內部排序算法的算法思想、時間特性及穩定性重點：插入排序、交換排序、選擇排序、歸并排序和基數排序等五類排序算法的算

4、法思想和時間復雜度；五類排序算法的特性和適用情形。三、題型及分值單項選擇題：10 %填空題： 10 %簡答題：50 % 算法題：30 %分為閱讀、修改和編寫算法三類：閱讀算法：閱讀指定算法，回答使用的數據結構、算法實現的功能或執行的結果；修改算法：閱讀指定算法，指出算法的錯誤并修正；指出算法的不足并改進；按給定功能填寫算法空缺部分；編寫算法：根據算法功能要求和選定的數據結構，用程序設計語言（C和Pascal均可）編寫算法，實現指定功能。計算機操作系統一、 總體要求認識OS的學術和工程意義；理解和掌握OS的目標、總體結構及主要的設計思想，以及基本原理和原型實現技術；了解現代操作系統的一些重要前沿

5、技術和實現原理；使學生擁有能夠進一步學習、應用和研發實際操作系統的知識和工程技術基礎。二、內容及比例第一章 操作系統引論l理解：操作系統的目標和作用、理解用戶接口的意義和類型。l了解：傳統操作系統的結構設計、軟件工程的概念和微內核概念。l理解和掌握：操作系統中的基本概念：脫機輸入輸出技術、批處理技術、多道程序設計、什么是操作系統、操作系統的基本類型，各類型的基本概念和特點、操作系統的特征、理解操作系統的功能模塊。第二章進程的描述與控制l理解和掌握的概念有：前趨圖、程序順序執行、程序并發執行、進程的定義與特征、進程的基本狀態、進程的掛起狀態、進程控制塊、進程的創建、進程的終止、進程的阻塞與喚醒、

6、進程的掛起與激活。l理解和掌握：臨界資源、臨界區、利用軟件和硬件解決進程互斥問題、整型信號量機制、記錄型信號量機制、整型信號量機制、信號量集機制、生產者消費者問題、進程通信的類型、直接通信和間接通信方式、消息傳遞系統中的幾個問題、消息緩沖隊列通信機制。l了解：讀者和寫者問題、哲學家進餐問題、管程機制。l理解：線程的概念、線程間的同步和通信、用戶線程和內核支持線程的概念。第三章處理機調度與死鎖l理解和掌握：調度的類型、調度隊列模型、調度方式和各種調度算法、產生死鎖的原因和必要條件、處理死鎖的基本方法、死鎖的預防和避免、死鎖的檢查和解除。l理解：滿足實時系統要求時，應選擇適合實時系統中的調度算法。

7、l了解：多處理器系統的類型、進程的分配方式、進程（線程）的調度方式。第四章存儲器管理l理解和掌握：程序的裝入和鏈接、連續分配存儲管理方式、對換技術的應用、分頁存儲管理方式、分段存儲管理方式、段頁式存儲管理方式、虛擬存儲器的基本概念、請求分頁存儲管理方式、各種頁面置換算法、請求分段存儲管理方式、請求分頁系統的性能分析、頁式管理的其它置換算法。第五章 設備管理l理解:I/O系統中設備控制器基本功能和組成、通道的概念和分類，系統總線的概念。l理解和掌握：I/O控制方式中的循環測試方式、程序中斷方式、通道I/O方式的概念。l了解：緩沖管理的分類和應用。l理解和掌握：設備分配中的數據結構：設備控制表、控制器表、通道表、系統設備表的概念。設備分配時應考慮的因素有設備的固有屬性、分配算法、SPOOLing技術、設備分配的獨立性和分配時的安全性。l理解和掌握：磁盤存儲管理的調度策略：先來先服務（FIFO）、最短尋找時間優先服務（SSTE）、掃描法（SCAN）和循環掃描法（CSCAN）。l了解：提高磁盤性能的技術，例如磁盤高速緩存。第六章文件管理l理解和掌握：文件和文件系統、文件邏輯結構、外存分配方法、目錄管理、文件存儲空間的管理、文件共享與文件保護。l了解：磁盤容錯技術和數據一