本站
非官方網(wǎng)站，信息完全免費，僅供參考，不收取任何費用，具體請以官網(wǎng)公布為準！
華北電力大學2017年碩士生入學考試初試科目考試大綱
科目代碼：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)的基本概念和術語；掌握線性表、棧、隊列、二叉樹、樹和圖的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及常用操作；掌握查找和內(nèi)排序的各種方法；設計具有較高時空性能的算法。
二、 考試的內(nèi)容
1、概述
數(shù)據(jù)結(jié)構(gòu)的基本概念與理解；相關術語包括:數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項,數(shù)據(jù)對象,邏輯結(jié)構(gòu),存儲結(jié)構(gòu),抽象數(shù)據(jù)類型；四種基本的邏輯結(jié)構(gòu)；兩種基本的存儲結(jié)構(gòu)。
算法相關內(nèi)容，包括：算法定義；算法的5大特性；算法設計要求；時間復雜度；空間復雜度；語句頻度。
2、線性表
線性表的定義；線性表的邏輯結(jié)構(gòu)；線性表的順序存儲（順序表）；線性表的鏈式存儲（單鏈表，循環(huán)鏈表，雙向鏈表）；不同存儲方式下基本操作的實現(xiàn)，包括：初始化、創(chuàng)建、插入、刪除、查找、修改、求表長、遍歷、輸出等；基于各基本操作的簡單應用。
3、棧與隊列
棧的定義；棧的邏輯結(jié)構(gòu)；棧的存儲結(jié)構(gòu)（順序棧，鏈棧）；不同存儲方式下基本操作的實現(xiàn)，包括：初始化、入棧、出棧、取得棧頂元素、判棧空、判棧滿、遍歷等；棧的簡單應用。
隊列的定義；隊列的邏輯結(jié)構(gòu)；隊列的存儲結(jié)構(gòu)（順序，鏈式）；不同存儲方式下基本操作的實現(xiàn)：初始化、入隊、出隊、隊空、隊滿的判定條件、求隊列長度、遍歷等；隊列的簡單應用。
4、樹和二叉樹
二叉樹的基本概念與術語；二叉樹的5個基本性質(zhì)；二叉樹的邏輯結(jié)構(gòu)；二叉樹的存儲結(jié)構(gòu)（順序、鏈式）；各存儲結(jié)構(gòu)上的基本操作，包括：創(chuàng)建、前序（中序、后序）三種遍歷、層次遍歷、求結(jié)點個數(shù)、求葉子個數(shù)、求深度；基于遍歷的簡單應用。
樹（森林）的基本概念與術語；樹（森林）的邏輯結(jié)構(gòu)；樹（森林）的存儲結(jié)構(gòu)（雙親表示法，孩子鏈表表示法，孩子兄弟鏈表表示法）；樹（森林）的基本操作，包括：創(chuàng)建、查找、插入、刪除、求深度、先根（先序）遍歷和后根（中序）遍歷；基于樹（或者森林）的遍歷的簡單應用。
二叉樹和樹（森林）的典型應用，包括：由兩種遍歷序列確定一棵二叉樹；由兩種遍歷序列確定一棵樹（或森林）；樹（森林）與二叉樹之間的相互轉(zhuǎn)換；
哈夫曼樹（最優(yōu)二叉樹），包括：哈夫曼樹的定義及術語、哈夫曼樹的邏輯結(jié)構(gòu)、哈夫曼樹的存儲結(jié)構(gòu)、哈夫曼編碼、WPL、構(gòu)造哈夫曼樹（邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)的變化過程）。
4、圖
圖的定義與基本術語；圖的邏輯結(jié)構(gòu)；圖的鄰接矩陣存儲結(jié)構(gòu)；圖的鄰接表及逆鄰接表存儲結(jié)構(gòu)；兩種存儲上基本操作，包括：創(chuàng)建、深度遍歷、廣度遍歷。
圖的典型應用，包括：判斷回路、最小生成樹（prim算法、kruscal算法）、最短路徑（迪杰斯特拉算法、floyd算法）、拓撲排序、關鍵路徑；基于遍歷的其他簡單應用。
5、查找
查找相關的基本概念與術語；幾類常用的查找，包括：線性表查找、樹表查找、哈希表等。
線性表查找，包括：順序查找、折半查找、分塊查找；以上幾種線性表查找的算法及性能分析（查找成功與不成功時的平均查找長度）。
樹表查找，包括：二叉排序樹的構(gòu)造、查找、刪除與查找性能分析（平均查找長度）；平衡二叉樹的構(gòu)造、查找、刪除與查找性能分析（平均查找長度）；
哈希表，包括：哈希表的概念、常用的哈希函數(shù)、解決沖突的方法、哈希表的查找與性能分析等。
6、排序
排序的基本概念；插入類排序（直接插入、折半插入、希爾排序）；交換類排序（冒泡排序、快速排序）；選擇類排序（簡單選擇排序、堆排序）；各種排序方法的基本思想、基本算法、一趟排序結(jié)果；各種排序方法的穩(wěn)定性。
7．綜合應用，包括：簡單問題的數(shù)據(jù)分析，選擇合適的數(shù)據(jù)結(jié)構(gòu)，設計高效的算法，并進行時間復雜度和空間復雜度的分析。
三、 考試的題型
單向選擇題、填空題、簡答題、應用題、算法設計題
第二部分：操作系統(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)的結(jié)構(gòu)特點。
2．進程管理：
包括進程的基本概念；進程控制(進程的狀態(tài)機轉(zhuǎn)換)；進程同步；經(jīng)典的進程同步互斥問題；進程通信；線程的定義及實現(xiàn)。
3．處理機調(diào)度與死鎖：
包括處理機調(diào)度的基本概念；調(diào)度方式及算法；死鎖的基本概念；死鎖的概念; 死鎖的處理策略。
4．存儲器管理：yz.xuecan.net
包括程序的裝入和鏈接；連續(xù)分配存儲管理方式；覆蓋與交換；分頁存儲管理方式；分段存儲管理方式。虛擬存儲器的基本概念；請求分頁存儲管理方式；頁面置換算法；請求分段存儲管理方式。
5．設備管理：
包括I/O系統(tǒng)的組成；I/O控制方式；I/O軟件層次結(jié)構(gòu)；設備獨立性；緩沖管理；假脫機技術;設備分配；設備處理。
6．文件管理：
包括文件和文件系統(tǒng)；文件邏輯結(jié)構(gòu)；目錄管理；文件共享；文件保護。
7．磁盤管理：
包括磁盤I/O；外存分配方法；空閑存儲空間的管理；磁盤容錯技術。
三、 考試的題型
單向選擇題、填空題、 應用題
高考報名系統(tǒng) http://xjuit.com/dagang/
