• 2025考研復(fù)試伴學(xué)班
• 2025考研復(fù)試標(biāo)準(zhǔn)班
• 2026考研英語全程班
• 26考研全科上岸規(guī)劃營(yíng)「擇校▪規(guī)劃▪備考」
• 華北電力大學(xué)（北京）2025考研專業(yè)課復(fù)習(xí)資料「真題▪筆記▪講義▪題庫(kù)」

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

科目代碼：842

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

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

第一部分：數(shù)據(jù)結(jié)構(gòu)

一、考試的總體要求

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

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

1、概述

數(shù)據(jù)結(jié)構(gòu)的基本概念與理解；相關(guān)術(shù)語包括:數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項(xiàng),數(shù)據(jù)對(duì)象,邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu),抽象數(shù)據(jù)類型；四種基本的邏輯結(jié)構(gòu)；兩種基本的存儲(chǔ)結(jié)構(gòu)。

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

2、線性表

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

3、棧與隊(duì)列

棧的定義；棧的邏輯結(jié)構(gòu)；棧的存儲(chǔ)結(jié)構(gòu)（順序棧，鏈棧）；不同存儲(chǔ)方式下基本操作的實(shí)現(xiàn)，包括：初始化、入棧、出棧、取得棧頂元素、判�？�、判棧滿、遍歷等；棧的簡(jiǎn)單應(yīng)用。

隊(duì)列的定義；隊(duì)列的邏輯結(jié)構(gòu)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)（順序，鏈?zhǔn)剑�；不同存�?chǔ)方式下基本操作的實(shí)現(xiàn)：初始化、入隊(duì)、出隊(duì)、隊(duì)空、隊(duì)滿的判定條件、求隊(duì)列長(zhǎng)度、遍歷等；隊(duì)列的簡(jiǎn)單應(yīng)用。

4、樹和二叉樹

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

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

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

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

4、圖

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

圖的典型應(yīng)用，包括：判斷回路、最小生成樹（prim算法、kruscal算法）、最短路徑（迪杰斯特拉算法、floyd算法）、拓?fù)渑判�、關(guān)鍵路徑；基于遍歷的其他簡(jiǎn)單應(yīng)用。

5、查找

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

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

樹表查找，包括：二叉排序樹的構(gòu)造、查找、刪除與查找性能分析（平均查找長(zhǎng)度）；平衡二叉樹的構(gòu)造、查找、刪除與查找性能分析（平均查找長(zhǎng)度）；

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

6、排序

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

7．綜合應(yīng)用，包括：簡(jiǎn)單問題的數(shù)據(jù)分析，選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)高效的算法，并進(jìn)行時(shí)間復(fù)雜度和空間復(fù)雜度的分析。

三、考試的題型

單向選擇題、填空題、簡(jiǎn)答題、應(yīng)用題、算法設(shè)計(jì)題

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

一、考試的總體要求

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

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

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

包括操作系統(tǒng)的定義；操作系統(tǒng)的發(fā)展過程；操作系統(tǒng)的分類；操作系統(tǒng)的特征和服務(wù)；操作系統(tǒng)的功能；常用操作系統(tǒng)的結(jié)構(gòu)特點(diǎn)。

2．進(jìn)程管理：

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

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

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

4．存儲(chǔ)器管理：

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

5．設(shè)備管理：

包括I/O系統(tǒng)的組成；I/O控制方式；I/O軟件層次結(jié)構(gòu)；設(shè)備獨(dú)立性；緩沖管理；假脫機(jī)技術(shù);設(shè)備分配；設(shè)備處理。

6．文件管理：

包括文件和文件系統(tǒng)；文件邏輯結(jié)構(gòu)；目錄管理；文件共享；文件保護(hù)。

7．磁盤管理：

包括磁盤I/O；外存分配方法；空閑存儲(chǔ)空間的管理；磁盤容錯(cuò)技術(shù)。

三、考試的題型

單向選擇題、填空題、應(yīng)用題