2020年814計算機基礎綜合考試大綱

考試科目：數據結構、計算機組成原理、操作系統

考試形式和試卷結構

一、試卷滿分及考試時間

試卷滿分為150分，考試時間為180分鐘。

二、試卷內容結構

數據結構                         1/3

計算機組成原理                   1/3

操作系統                         1/3

三、試卷題型結構

選擇題                           10-20分

填空題                           15-30分

簡答題                           30-50分

解答題（包括證明題）             95-50分

數據結構

1、考試范圍

算法復雜度分析、線性結構、棧與隊列、樹形結構、圖形結構、查找算法、排序算法。

2、考試要點

（1）算法復雜度分析的基本概念、漸進表示方法；

（2）線性表基本概念、線性表的順序存儲、鏈式存儲及其基本操作與應用；

（3）棧和隊列的概念、順序存儲、鏈式存儲及其基本操作與應用；

（4）二叉樹的概念、存儲結構、遍歷算法，以及二叉查找樹、平衡二叉樹、堆與優先隊列等應用；

（5）樹與森林的概念、存儲結構、遍歷算法，樹和森林與二叉樹的轉換；

（6）圖的概念、圖形存儲結構、圖的遍歷算法，以及拓撲排序、最短路徑、最小生成樹等應用；

（7）基本的查找算法和排序算法及其算法復雜度。

3、參考書

趙仲孟，張選平，等編著. 數據結構與算法（第一版）. 北京：高等教育出版社，2016年11月

操作系統

1、考試范圍

操作系統引論，進程管理，死鎖，存儲管理，文件管理，設備管理。

2、考試要點

（1）操作系統引論：操作系統定義、地位與作用、功能與特征，操作系統的類型及特點（多道批處理系統、分時系統、實時系統、網絡操作系統、分布式操作系統），操作系統性能（吞吐量，響應時間），操作系統用戶接口，系統調用。

（2）處理機調度：作業、進程和線程的基本概念、狀態轉換及控制方法，調度的策略和算法，互斥、同步問題及使用P、V原語解決此類問題，死鎖的概念、產生的必要條件及解決死鎖的方法，進程間通信，用戶接口及其使用方式。

（3）存儲管理：存儲體系，存儲管理的功能，地址轉換，虛擬存儲器，分區、分頁、分段、段頁式管理的實現原理、存儲分配算法，內存保護、共享，覆蓋、交換及請求式分頁技術等內存擴充技術，頁面淘汰算法，局部性原理及工作集概念。

（4）文件管理：文件、文件系統，文件系統的功能，文件的邏輯結構、物理結構、目錄結構，文件存取與操作，存儲空間的管理，磁盤調度算法，文件共享和保護，文件的主要操作。

（5）設備管理：設備管理的功能和任務，設備分類，I/O控制方式，通道，緩沖技術，設備無關性，虛擬設備技術，設備分配技術。

3、參考書

湯小丹，梁紅兵，等著. 計算機操作系統（第四版）. 西安：西安電子科技大學出版社，2014年5月

計算機組成原理

1、考試范圍

計算機指令系統、計算機存儲器、計算機總線與輸入輸出系統、計算機運算方法、計算機數據通路設計與控制器設計方法。

2、考試要點

（1）理解計算機系統的基本概念；理解指令系統的功能及設計原則，掌握指令格式及尋址方式；

（2）理解存儲器的組成及存儲系統的工作原理；掌握存儲器、系統總線及輸入輸出接口的原理及相關設計方法; 

（3）理解并掌握計算機的運算方法和運算器；理解CPU的組成和功能，掌握數據通路的設計思想和方法，掌握控制單元的設計思想和方法。

3、參考書

王換招，陳妍，趙青蘋. 計算機組成與設計（第一版）. 北京：清華大學出版社，2013年8月