2021華北電力大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)研究生考試大綱 正文

華北電力大學(xué)2021年碩士生入學(xué)考試初試科目考試大綱
科目代碼：842                
科目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)
本門(mén)課程由數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩門(mén)課程組成，兩門(mén)課程各占75分，具體要求如下：
第一部分：數(shù)據(jù)結(jié)構(gòu)
一、考試的總體要求與目標(biāo)
掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和方法。掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本時(shí)間復(fù)雜度和空間復(fù)雜度分析。能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問(wèn)題的分析與求解，具備采用C語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。
二、考試的內(nèi)容
    1. 基本概念和術(shù)語(yǔ)
    2. 線性表
線性表的定義；線性表的邏輯結(jié)構(gòu)；線性表的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）；不同存儲(chǔ)方式下操作的實(shí)現(xiàn)；線性表的應(yīng)用。
3. 棧與隊(duì)列
    棧：棧的定義和基本概念；棧的邏輯結(jié)構(gòu)；棧的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)）；不同存儲(chǔ)方式下操作的實(shí)現(xiàn)；棧的應(yīng)用。
 隊(duì)列：隊(duì)列的定義和基本概念；隊(duì)列的邏輯結(jié)構(gòu)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)（順序，鏈?zhǔn)剑?；不同存?chǔ)方式下操作的實(shí)現(xiàn)；隊(duì)列的應(yīng)用。
4. 樹(shù)和二叉樹(shù)
二叉樹(shù)：二叉樹(shù)的概念；二叉樹(shù)的基本性質(zhì)；二叉樹(shù)的邏輯結(jié)構(gòu)；二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（順序、鏈?zhǔn)剑?；各存?chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)；二叉樹(shù)的遍歷及應(yīng)用；線索二叉樹(shù)的基本概念和構(gòu)造。
樹(shù)和森林：樹(shù)（森林）的基本概念；樹(shù)（森林）的邏輯結(jié)構(gòu)；樹(shù)（森林）的存儲(chǔ)結(jié)構(gòu)（雙親表示法，孩子鏈表表示法，孩子兄弟鏈表表示法）；樹(shù)（森林）的基本操作實(shí)現(xiàn)；樹(shù)（森林）與二叉樹(shù)之間的相互轉(zhuǎn)換；樹(shù)（森林）的應(yīng)用。
哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）和哈夫曼編碼。
5. 圖
圖的定義與基本概念；圖的邏輯結(jié)構(gòu)；圖的存儲(chǔ)結(jié)構(gòu)（鄰接矩陣、鄰接表、鄰接多重表、十字鏈表）；不同存儲(chǔ)結(jié)構(gòu)上的基本操作實(shí)現(xiàn)；圖的遍歷（深度優(yōu)先遍歷，廣度優(yōu)先遍歷）；圖的應(yīng)用。
   6. 查找
查找的基本概念與術(shù)語(yǔ)；靜態(tài)查找表（順序查找、折半查找、分塊查找）；動(dòng)態(tài)查找表（二叉排序樹(shù)、二叉平衡樹(shù)和B-樹(shù)）；哈希表（哈希表的概念、常用的哈希函數(shù)、解決沖突的方法）；查找性能分析；查找算法的分析及應(yīng)用。
7. 排序
排序的基本概念；插入類(lèi)排序（直接插入排序、折半插入排序、希爾排序）、交換類(lèi)排序（冒泡排序、快速排序）、選擇類(lèi)排序（簡(jiǎn)單選擇排序、堆排序）、歸并類(lèi)排序（二路歸并排序）、基數(shù)排序；各種內(nèi)部排序算法的穩(wěn)定性和時(shí)間性能分析；排序算法的應(yīng)用。
8．綜合應(yīng)用：根據(jù)實(shí)際問(wèn)題，設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)和算法，并進(jìn)行時(shí)間復(fù)雜度分析。
三、考試的題型
選擇題、填空題、判斷題、簡(jiǎn)答題、綜合應(yīng)用題、算法設(shè)計(jì)題
四、參考書(shū)目
1． 林碧英，石敏，焦?jié)櫤? 新編數(shù)據(jù)結(jié)構(gòu)與算法教程.清華大學(xué)出版社.
 
第二部分：操作系統(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)相關(guān)的基本概念。 
2．操作系統(tǒng)概述：
包括操作系統(tǒng)的概念；操作系統(tǒng)的發(fā)展過(guò)程；操作系統(tǒng)的分類(lèi)；操作系統(tǒng)的特征；操作系統(tǒng)的功能；操作系統(tǒng)接口；常用操作系統(tǒng)的結(jié)構(gòu)特點(diǎn)。
3. 進(jìn)程管理：
包括進(jìn)程的概念；進(jìn)程控制(進(jìn)程的狀態(tài)機(jī)轉(zhuǎn)換)；進(jìn)程同步；經(jīng)典的進(jìn)程同步互斥問(wèn)題；進(jìn)程通信；線程的定義及實(shí)現(xiàn)。
4．處理機(jī)調(diào)度與死鎖：
包括處理機(jī)調(diào)度的概念；調(diào)度方式及算法；死鎖的概念；死鎖產(chǎn)生的原因；死鎖的處理策略。
5．存儲(chǔ)器管理：
包括程序的裝入和鏈接；連續(xù)分配存儲(chǔ)管理方式；覆蓋與交換；分頁(yè)存儲(chǔ)管理方式；分段存儲(chǔ)管理方式。虛擬存儲(chǔ)器的概念；局部性原理；缺頁(yè)中斷；請(qǐng)求分頁(yè)存儲(chǔ)管理方式；頁(yè)面置換算法；請(qǐng)求分段存儲(chǔ)管理方式；邏輯地址到物理地址的轉(zhuǎn)換。
6．設(shè)備管理：
包括I/O系統(tǒng)的組成；I/O控制方式；I/O軟件層次結(jié)構(gòu)；設(shè)備獨(dú)立性；緩沖管理；假脫機(jī)技術(shù)（SPOOLing技術(shù)）;設(shè)備分配；設(shè)備處理（驅(qū)動(dòng)）。
7．磁盤(pán)管理：
包括磁盤(pán)調(diào)度；磁盤(pán)空閑存儲(chǔ)空間的管理；磁盤(pán)陣列。
8．文件管理：
包括文件和文件系統(tǒng)的概念；文件邏輯結(jié)構(gòu)；外存分配方法（文件物理結(jié)構(gòu)）；文件控制塊FCB；目錄管理；索引節(jié)點(diǎn)；FAT表；文件保護(hù)。
三、考試的題型
選擇題、填空題、綜合應(yīng)用題。
四、參考書(shū)目
1．鄒鵬，操作系統(tǒng)原理與實(shí)踐，北京：高等教育出版社，2008.
2．湯小丹等，計(jì)算機(jī)操作系統(tǒng)，第四版.西安：西安電子科技大學(xué)出版社，2014.

華北電力大學(xué)(保定)

本文來(lái)源：http://talkofages.com/huabeidianlidaxue/cankaoshumu_409413.html