2016年華北電力大學數據結構與操作系統考研初試大綱

• 2025考研復試伴學班
• 2025考研復試標準班
• 2026考研英語全程班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 華北電力大學（北京）2025考研專業課復習資料「真題▪筆記▪講義▪題庫」

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

科目代碼：842

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

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

第一部分：數據結構

一、考試的總體要求

掌握數據結構的基本概念和術語；掌握線性表、棧、隊列、二叉樹、樹和圖的邏輯結構、存儲結構以及常用操作；掌握查找和內排序的各種方法；設計具有較高時空性能的算法。

二、考試的內容

1、概述

數據結構的基本概念與理解；相關術語包括:數據,數據元素,數據項,數據對象,邏輯結構,存儲結構,抽象數據類型；四種基本的邏輯結構；兩種基本的存儲結構。

算法相關內容，包括：算法定義；算法的5大特性；算法設計要求；時間復雜度；空間復雜度；語句頻度。

2、線性表

線性表的定義；線性表的邏輯結構；線性表的順序存儲（順序表）；線性表的鏈式存儲（單鏈表，循環鏈表，雙向鏈表）；不同存儲方式下基本操作的實現，包括：初始化、創建、插入、刪除、查找、修改、求表長、遍歷、輸出等；基于各基本操作的簡單應用。

3、棧與隊列

棧的定義；棧的邏輯結構；棧的存儲結構（順序棧，鏈棧）；不同存儲方式下基本操作的實現，包括：初始化、入棧、出棧、取得棧頂元素、判棧空、判棧滿、遍歷等；棧的簡單應用。

隊列的定義；隊列的邏輯結構；隊列的存儲結構（順序，鏈式）；不同存儲方式下基本操作的實現：初始化、入隊、出隊、隊空、隊滿的判定條件、求隊列長度、遍歷等；隊列的簡單應用。

4、樹和二叉樹

二叉樹的基本概念與術語；二叉樹的5個基本性質；二叉樹的邏輯結構；二叉樹的存儲結構（順序、鏈式）；各存儲結構上的基本操作，包括：創建、前序（中序、后序）三種遍歷、層次遍歷、求結點個數、求葉子個數、求深度；基于遍歷的簡單應用。

樹（森林）的基本概念與術語；樹（森林）的邏輯結構；樹（森林）的存儲結構（雙親表示法，孩子鏈表表示法，孩子兄弟鏈表表示法）；樹（森林）的基本操作，包括：創建、查找、插入、刪除、求深度、先根（先序）遍歷和后根（中序）遍歷；基于樹（或者森林）的遍歷的簡單應用。

二叉樹和樹（森林）的典型應用，包括：由兩種遍歷序列確定一棵二叉樹；由兩種遍歷序列確定一棵樹（或森林）；樹（森林）與二叉樹之間的相互轉換；

哈夫曼樹（最優二叉樹），包括：哈夫曼樹的定義及術語、哈夫曼樹的邏輯結構、哈夫曼樹的存儲結構、哈夫曼編碼、WPL、構造哈夫曼樹（邏輯結構及存儲結構的變化過程）。

4、圖

圖的定義與基本術語；圖的邏輯結構；圖的鄰接矩陣存儲結構；圖的鄰接表及逆鄰接表存儲結構；兩種存儲上基本操作，包括：創建、深度遍歷、廣度遍歷。

圖的典型應用，包括：判斷回路、最小生成樹（prim算法、kruscal算法）、最短路徑（迪杰斯特拉算法、floyd算法）、拓撲排序、關鍵路徑；基于遍歷的其他簡單應用。

5、查找

查找相關的基本概念與術語；幾類常用的查找，包括：線性表查找、樹表查找、哈希表等。

線性表查找，包括：順序查找、折半查找、分塊查找；以上幾種線性表查找的算法及性能分析（查找成功與不成功時的平均查找長度）。

樹表查找，包括：二叉排序樹的構造、查找、刪除與查找性能分析（平均查找長度）；平衡二叉樹的構造、查找、刪除與查找性能分析（平均查找長度）；

哈希表，包括：哈希表的概念、常用的哈希函數、解決沖突的方法、哈希表的查找與性能分析等。

6、排序

排序的基本概念；插入類排序（直接插入、折半插入、希爾排序）；交換類排序（冒泡排序、快速排序）；選擇類排序（簡單選擇排序、堆排序）；各種排序方法的基本思想、基本算法、一趟排序結果；各種排序方法的穩定性。

7．綜合應用，包括：簡單問題的數據分析，選擇合適的數據結構，設計高效的算法，并進行時間復雜度和空間復雜度的分析。

三、考試的題型

單向選擇題、填空題、簡答題、應用題、算法設計題

第二部分：操作系統

一、考試的總體要求

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

二、考試的內容

1．操作系統概述：

包括操作系統的定義；操作系統的發展過程；操作系統的分類；操作系統的特征和服務；操作系統的功能；常用操作系統的結構特點。

2．進程管理：

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

3．處理機調度與死鎖：

包括處理機調度的基本概念；調度方式及算法；死鎖的基本概念；死鎖的概念;死鎖的處理策略。

4．存儲器管理：

包括程序的裝入和鏈接；連續分配存儲管理方式；覆蓋與交換；分頁存儲管理方式；分段存儲管理方式。虛擬存儲器的基本概念；請求分頁存儲管理方式；頁面置換算法；請求分段存儲管理方式。

5．設備管理：

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

6．文件管理：

包括文件和文件系統；文件邏輯結構；目錄管理；文件共享；文件保護。

7．磁盤管理：

包括磁盤I/O；外存分配方法；空閑存儲空間的管理；磁盤容錯技術。

三、考試的題型

單向選擇題、填空題、應用題