2016年華北電力大學數(shù)據(jù)結構與操作系統(tǒng)考研初試大綱

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

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

科目代碼：842

科目名稱：數(shù)據(jù)結構與操作系統(tǒng)

本門課程由數(shù)據(jù)結構和操作系統(tǒng)兩門課程組成，兩門課程各占75分，具體要求如下：

第一部分：數(shù)據(jù)結構

一、考試的總體要求

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

二、考試的內(nèi)容

1、概述

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

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

2、線性表

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

3、棧與隊列

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

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

4、樹和二叉樹

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

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

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

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

4、圖

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

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

5、查找

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

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

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

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

6、排序

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

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

三、考試的題型

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

第二部分：操作系統(tǒng)

一、考試的總體要求

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

二、考試的內(nèi)容

1．操作系統(tǒng)概述：

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

2．進程管理：

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

3．處理機調(diào)度與死鎖：

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

4．存儲器管理：

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

5．設備管理：

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

6．文件管理：

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

7．磁盤管理：

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

三、考試的題型

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