華北電力大學（北京）

華北電力大學2021年碩士生入學考試初試科目考試大綱

科目代碼：842

科目名稱：數據結構與操作系統

本門課程由數據結構和操作系統兩門課程組成，兩門課程各占75分，具體要求如下：

第一部分：數據結構

一、考試的總體要求與目標

掌握數據結構的基本概念、基本原理和方法。掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本時間復雜度和空間復雜度分析。能夠運用數據結構基本原理和方法進行問題的分析與求解，具備采用C語言設計與實現算法的能力。

二、考試的內容

1. 基本概念和術語

2. 線性表

線性表的定義;線性表的邏輯結構;線性表的存儲結構(順序存儲、鏈式存儲);不同存儲方式下操作的實現;線性表的應用。

3. 棧與隊列

棧：棧的定義和基本概念;棧的邏輯結構;棧的存儲結構(順序存儲，鏈式存儲);不同存儲方式下操作的實現;棧的應用。

隊列：隊列的定義和基本概念;隊列的邏輯結構;隊列的存儲結構(順序，鏈式);不同存儲方式下操作的實現;隊列的應用。

4. 樹和二叉樹

二叉樹：二叉樹的概念;二叉樹的基本性質;二叉樹的邏輯結構;二叉樹的存儲結構(順序、鏈式);各存儲結構上的操作實現;二叉樹的遍歷及應用;線索二叉樹的基本概念和構造。

樹和森林：樹(森林)的基本概念;樹(森林)的邏輯結構;樹(森林)的存儲結構(雙親表示法，孩子鏈表表示法，孩子兄弟鏈表表示法);樹(森林)的基本操作實現;樹(森林)與二叉樹之間的相互轉換;樹(森林)的應用。

哈夫曼樹(最優二叉樹)和哈夫曼編碼。

5. 圖

圖的定義與基本概念;圖的邏輯結構;圖的存儲結構(鄰接矩陣、鄰接表、鄰接多重表、十字鏈表);不同存儲結構上的基本操作實現;圖的遍歷(深度優先遍歷，廣度優先遍歷);圖的應用。

6. 查找

查找的基本概念與術語;靜態查找表(順序查找、折半查找、分塊查找);動態查找表(二叉排序樹、二叉平衡樹和B-樹);哈希表(哈希表的概念、常用的哈希函數、解決沖突的方法);查找性能分析;查找算法的分析及應用。

7. 排序

排序的基本概念;插入類排序(直接插入排序、折半插入排序、希爾排序)、交換類排序(冒泡排序、快速排序)、選擇類排序(簡單選擇排序、堆排序)、歸并類排序(二路歸并排序)、基數排序;各種內部排序算法的穩定性和時間性能分析;排序算法的應用。

8.綜合應用：根據實際問題，設計有效的數據結構和算法，并進行時間復雜度分析。

三、考試的題型

選擇題、填空題、判斷題、簡答題、綜合應用題、算法設計題

四、參考書目

1. 林碧英，石敏，焦潤海. 新編數據結構與算法教程.清華大學出版社.

第二部分：操作系統

一、考試的總體要求

要求考生熟練掌握計算機操作系統中的基本概念、基本原理; 從資源管理角度掌握計算機操作系統的主要功能及設計思想;了解和掌握現代計算機系統對其各種軟硬資源的管理方法及實現技術;了解當代計算機操作系統的新技術與發展趨勢。

二、考試的內容

1.掌握與操作系統相關的基本概念。

2.操作系統概述：

包括操作系統的概念;操作系統的發展過程;操作系統的分類;操作系統的特征;操作系統的功能;操作系統接口;常用操作系統的結構特點。

3. 進程管理：

包括進程的概念;進程控制(進程的狀態機轉換);進程同步;經典的進程同步互斥問題;進程通信;線程的定義及實現。

4.處理機調度與死鎖：

包括處理機調度的概念;調度方式及算法;死鎖的概念;死鎖產生的原因;死鎖的處理策略。

5.存儲器管理：

包括程序的裝入和鏈接;連續分配存儲管理方式;覆蓋與交換;分頁存儲管理方式;分段存儲管理方式。虛擬存儲器的概念;局部性原理;缺頁中斷;請求分頁存儲管理方式;頁面置換算法;請求分段存儲管理方式;邏輯地址到物理地址的轉換。

6.設備管理：

包括I/O系統的組成;I/O控制方式;I/O軟件層次結構;設備獨立性;緩沖管理;假脫機技術(SPOOLing技術);設備分配;設備處理(驅動)。

7.磁盤管理：

包括磁盤調度;磁盤空閑存儲空間的管理;磁盤陣列。

8.文件管理：

包括文件和文件系統的概念;文件邏輯結構;外存分配方法(文件物理結構);文件控制塊FCB;目錄管理;索引節點;FAT表;文件保護。

三、考試的題型

選擇題、填空題、綜合應用題。

四、參考書目

1.鄒鵬，操作系統原理與實踐，北京：高等教育出版社，2008.

2.湯小丹等，計算機操作系統，第四版.西安：西安電子科技大學出版社，2014.