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