一、考試性質
《計算機學科綜合(數據結構+ 操作系統)》是碩士研究生入學考試科目之一，是碩士研究生招生院校自行命題的選拔性考試。本考試大綱的制定力求反映招生類型 的特點，科學、公平、準確、規范地測評考生的相關基礎知識掌握水平，考生分析問 題和解決問題及綜合知識運用能力。應考人員應根據本大綱的內容和要求自行組織學 習內容和掌握有關知識。
本科目包含數據結構及操作系統兩門課程?？荚嚂r間共 180 分鐘。兩門課程各75 分。
數據結構主要包括三大常用數據結構的邏輯、物理表示與基本操作算法實現部分的知識，各種結構的經典應用和具體問題求解?？忌鷳莆崭鞣N數據結構及其操作，具備一定的算法設計與分析能力，能夠根據實際問題選擇合適的數據結構并設計算法實現。
操作系統主要包括其對各種計算機硬、軟件資源的管理方法的理論與應用學習?？忌鷳莆詹僮飨到y的基本概念、原理和基本功能，掌握操作系統中進程、內存、 文件和 I/O 管理的策略、算法、機制以及相互關系，并能夠運用所學的原理、方法 與技術分析和解決實際問題以及代碼實現。
二、考試主要內容
(一)數據結構
1、緒論
(1)基本概念和術語
基本要求：了解課程的研究內容，理解數據結構的相關概念。
考試范圍：掌握數據結構的研究內容、基本概念和相關術語;理解抽象數據類型的表示與實現。
(2)算法和算法分析
基本要求：理解算法的含義，熟悉算法描述語言，掌握算法的性能評價指標及評價方法,并能分析常用算法的時間復雜度。
考試范圍：算法的概念與特征;算法效率的度量指標;時間復雜度與空間復雜度的計算方法; 常見時間復雜度類型與性能優劣比較。
2、線性表
(1)線性表的類型定義
基本要求：掌握線性表的邏輯結構及相關概念;理解線性表的抽象數據類型?？荚嚪秶壕€性表的概念及文件、數據項及記錄的相關概念;線性表的抽象數據類型;用線性表表示集合合并的算法;合并有序線性表的算法。
(2)線性表的表示和實現
基本要求：掌握線性表的順序與鏈式兩種存儲結構及其各種基本運算的的實現過程;掌握兩 種存儲方式之間的差異及各自優缺點;能夠靈活運用順序表和鏈表解決實際問題。
考試范圍：順序存儲結構的概念及計算第 i 個元素存儲地址的公式;用類 C 描 述線性表的順序存儲結構;順序表的初始化、插入、刪除、定位和有序表合并算法;線性鏈表及相關概念;用 C 語言描述線性表的鏈式存儲結構;鏈表的訪問、插入、 刪除和有序合并算法;線性表的靜態鏈表表示基本定義;循環鏈表的定義以及與單鏈表的區別;雙向鏈表的定義和存儲表示;雙向鏈表的插入與刪除算法;一元多項式的表示及相加算法實現。
3、棧和隊列
(1)棧
基本要求：理解棧的定義、特性和運算;掌握棧的順序存儲實現及其性能分析;理解和掌握用棧實現表達式求解的過程;了解棧的鏈式存儲結構的實現。
考試范圍：棧的抽象數據類型定義;棧的先進后出特性;棧的存儲表示與基本操作實現;棧的應用。
(2)隊列
基本要求：理解隊列的定義、特性和運算;理解隊列的順序存儲實現及其性能分析;理解循環隊列的背景和實現方法;理解隊列的鏈式存儲結構的實現及其性能分析。
考試范圍：隊列的抽象數據類型定義;隊列的先進先出特性;隊列的存儲表示與基本操作實現。
4、串
基本要求：掌握串的相關概念、串的存儲結構(順序串和鏈式串)及基本運算的實現;掌握KMP 算法的基本思想及模式匹配過程;能靈活運用串的特點解決復雜的應用問題。
考試范圍：串類型的定義;串的定長順序存儲、堆分配存儲、塊鏈存儲表示和實現;串的模式匹配算法;串的應用。
5、數組和廣義表
基本要求：理解數組結構及其存儲，理解矩陣的壓縮存儲方式及其映射關系;理解廣義表以及子表、原子和長度等概念;理解廣義表的基本運算及其存儲。
考試范圍：數組的定義;二維數組的兩種存儲方式(以行序為主、以列序為主)及其數組元素存儲位置計算公式;特殊矩陣與稀疏矩陣的壓縮存儲方式;廣義表的定義和存儲結構。
