新疆農(nóng)業(yè)大學全日制碩士研究生入學考試

    《數(shù)據(jù)結構及操作系統(tǒng)》考試大綱

    命題方式招生單位自命題科目類別初試

    滿分150

    考試性質(zhì)

    《數(shù)據(jù)結構及操作系統(tǒng)》課程主要包含數(shù)據(jù)結構和操作系統(tǒng)兩塊內(nèi)容。該課程的考試是為招收工學類碩士研究生而設置的選拔考試。它的主要目的是測試考生對該課程的把握程度，包括對課程中的概念、基本原理和方法的理解和掌握，及能夠運用所學的原理和方法分析、判斷及解決有關理論問題和實際問題。

    考試方式和考試時間

    考試采用閉卷筆試形式，試卷滿分為150分（數(shù)據(jù)結構和操作系統(tǒng)各占75分），考試時間為3小時。

    考試內(nèi)容和考試要求

    一、數(shù)據(jù)結構

    （一）數(shù)據(jù)結構概論

    考試內(nèi)容：

    1．概念：數(shù)據(jù)結構，數(shù)據(jù)元素，數(shù)據(jù)項，數(shù)據(jù)的四種經(jīng)典邏輯結構，數(shù)據(jù)的物理存儲結構，數(shù)據(jù)結構研究的三個方向，算法，算法的時間復雜度、空間復雜度

    2．理解和應用：

    （1）數(shù)據(jù)的四種經(jīng)典邏輯結構之間的區(qū)別和聯(lián)系

    （2）算法的特性和設計的要求

    （3）時間復雜度和空間復雜度的關系

    考試要求

    （1）掌握基本概念

    （2）能計算出給定程序的時間復雜度

    （二）線性結構

    考試內(nèi)容：

    1.概念：線性結構的特點，線性表，線性表的順序存儲特點，順序表中元素存儲位置之間的關系，線性鏈表，循環(huán)鏈表，雙向鏈表，棧，隊列，循環(huán)隊列，串，子串，模式匹配算法

    2.理解與應用：

    （1）線性表、棧、隊列與線性結構的關系

    （2）線性表的順序存儲結構表示

    （3）順序表中的插入、刪除、合并操作算法的思想及實現(xiàn)方法

    （4）線性表的鏈式存儲結構表示

    （5）單鏈表的創(chuàng)建、查找、插入、刪除、合并算法的思想及實現(xiàn)方法

    （6）雙向鏈表的插入和刪除算法的思想及實現(xiàn)

    （7）棧中棧頂、棧底的含義，棧中元素操作的特點

    （8）棧頂指針的作用及意義

    （9）棧的進棧、出棧算法的思想及實現(xiàn)方法

    （10）棧的應用

    （11）隊列中隊頭、隊尾的含義，隊列的基本特點

    （12）循環(huán)隊列的設計思路及實現(xiàn)方法

    （13）隊列的入隊列、出隊列算法的思想及實現(xiàn)方法

    （14）子串的位置及模式匹配

    （15）子串的定位算法及KMP算法

    考試要求：

    （1）掌握基本概念

    （2）對算法的思想能進行文字描述

    （3）了解棧與隊列的操作特點

    （三）樹

    考試內(nèi)容：

    1.概念：樹，子樹，二叉樹，結點的度，分支結點，雙親、兄弟、堂兄、祖先、子孫結點，樹的深度，無序樹，有序樹，森林，滿二叉樹，完全二叉樹，線索二叉樹，最優(yōu)二叉樹，樹的帶權路徑長度

    2.理解與應用

    （1）二叉樹的性質(zhì)

    （2）滿二叉樹與完全二叉樹的區(qū)別與聯(lián)系

    （3）二叉樹的存儲結構及實現(xiàn)

    （4）二叉樹的三種遍歷算法的思想及實現(xiàn)方法

    （5）二叉樹的線索過程

    （6）樹的存儲結構及表示

    （7）樹、二叉樹、森林間的相互轉(zhuǎn)換

    （8）樹、森林的遍歷與二叉樹的遍歷之間的聯(lián)系

    （9）線索二叉樹的存儲結構

    （10）二叉樹的線索化算法

    （11）赫夫曼樹的構造算法及實現(xiàn)方法

    考試要求：

    （1）掌握基本概念

    （2）掌握算法的思想，能對算法代碼實現(xiàn)

    （3）了解樹、二叉樹、森林的存儲結構、遍歷關系

    （四）圖

    考試內(nèi)容：

    1.概念：圖，頂點，弧，有向圖，無向圖，完全圖，子圖，頂點的度，路徑，簡單路徑，回路，連通圖，連通分量，強連通圖，強連通分量，生成樹，生成森林，有向無環(huán)圖，拓撲排序，關鍵路徑，AOV網(wǎng)，AOE網(wǎng)，最短路徑

    2.理解與應用：

    （1）圖的特點

    （2）圖的存儲結構及實現(xiàn)

    （3）圖的遍歷算法思想及實現(xiàn)方法

    （4）圖的最小生成樹構造算法思想及實現(xiàn)方法

    （5）拓撲排序算法的思想及實現(xiàn)方法

    （6）最短路徑的構造算法

    考試要求：

    （1）掌握基本概念

    （2）掌握算法的思想，能對算法代碼實現(xiàn)

    （3）了解各種算法的應用范圍和解決的實際問題

    （五）查找

    考試內(nèi)容：

    1.概念：查找表，關鍵字，靜態(tài)查找，動態(tài)查找，平均查找長度，二叉排序樹，平衡因子，平衡二叉樹，B-樹，B+樹，鍵樹，TRIE樹，哈希表，

    2.理解與應用：

    （1）理解靜態(tài)查找和動態(tài)查找的區(qū)別

    （2）靜態(tài)查找的三種方法及實現(xiàn)，三種方法的特點及適用范圍

    （3）二叉排序樹的構造和插入算法的思想及實現(xiàn)方法

    （4）二叉排序樹構造過程中的平衡處理算法的思想

    （5）各種查找方法的ASL計算

    （6）B-樹上的查找、插入、刪除算法的思想

    （7）哈希函數(shù)的構造方法

    （8）哈希構造中處理沖突的方法

    考試要求：

    （1）掌握基本概念

    （2）掌握算法的思想，能對算法代碼實現(xiàn)

    （3）掌握哈希表的構造方法

    （4）了解各種算法的應用范圍和解決的實際問題

    （六）排序

    1.概念：排序，穩(wěn)定，內(nèi)排序，外排序

    2.理解與應用：

    （1）排序算法的分類，重要指標

    （2）各種排序算法的思想及實現(xiàn)方法

    （3）各種算法的穩(wěn)定性、時間復雜度、空間復雜度

    （4）各種排序算法的特點和適用范圍

    考試要求：

    （1）掌握基本概念

    （2）掌握各種排序算法的思想，能對算法代碼實現(xiàn)

    （3）理解各種排序方法的優(yōu)缺點和適用范圍

    （4）了解穩(wěn)定性、時間復雜度和空間復雜度對排序的影響

    二、操作系統(tǒng)原理

    （一）操作系統(tǒng)概論

    考試內(nèi)容：

    1．概念：操作系統(tǒng)的定義、功能和地位，操作系統(tǒng)的發(fā)展，操作系統(tǒng)基本特征

    2．理解和應用：

    （1）批處理多道系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)三個基本操作系統(tǒng)的工作原理及特征

    （2）分時系統(tǒng)與實時系統(tǒng)的區(qū)別

    （3）基本操作系統(tǒng)的特征

    考試要求

    （1）掌握基本概念

    （2）理解操作系統(tǒng)在計算機系統(tǒng)中的地位和三個基本特征

    （二）進程管理

    考試內(nèi)容：

    1．概念：前趨圖，進程的定義、特征、三種基本狀態(tài)（就緒、阻塞和運行），進程控制塊，臨界資源，臨界區(qū)，同步機制應遵循的原則，管程的定義，條件變量，進程通信的類型，線程，線程的屬性，處理機的三級調(diào)度，進程的兩種調(diào)度方式，周轉(zhuǎn)時間，帶權周轉(zhuǎn)時間，常用的幾種調(diào)度算法（先來先服務、短作業(yè)（進程）優(yōu)先、高優(yōu)先權優(yōu)先、高響應比優(yōu)先、時間片輪轉(zhuǎn)法、多級反饋隊列調(diào)度），優(yōu)先權，響應比，死鎖，產(chǎn)生死鎖的原因、必要條件及處理死鎖的基本方法，死鎖定理

    2．理解與應用：

    （1）進程與程序的區(qū)別

    （2）進程三個基本狀態(tài)之間的轉(zhuǎn)換及引起轉(zhuǎn)換的原因

    （3）進程的兩種制約關系，并能進行辨別

    （4）能夠辨別臨界資源

    （5）常用的幾種信號量機制及每種機制的原理

    （6）利用信號量實現(xiàn)進程的互斥、同步和前趨關系

    （7）理解經(jīng)典的進程同步問題（生產(chǎn)者-消費者問題；讀者-寫者問題；哲學家進餐問題）

    （8）利用管理解決生產(chǎn)者和消費者問題

    （9）消息傳遞通信的實現(xiàn)方法

    （10）消息緩沖隊列通信的實現(xiàn)方法

    （11）理解什么是內(nèi)核支持線程和用戶級線程

    （12）進程與線程的區(qū)別

    （13）進程調(diào)度方式中搶占式的搶占原則

    （14）理解每種調(diào)度算法的算法思想、優(yōu)缺點，并能根據(jù)算法思想完成相應計算

    （15）預防死鎖的各種方法

    （16）銀行家算法的思想

    （17）能夠根據(jù)銀行家算法和安全性檢測算法判斷系統(tǒng)的安全狀態(tài)及決定是否分配資源

    （18）死鎖檢測的方法

    （19）死鎖解除的方法

    考試要求：

    （1）掌握基本概念及基本原理

    （2）重點：進程的概念和進程的并發(fā)特征；進程與程序的區(qū)別；進程狀態(tài)及轉(zhuǎn)換；相關臨界區(qū)問題和臨界資源；用信號量解決進程的同步與互斥問題；進程調(diào)度算法；死鎖的概念與解決死鎖的方法。

    （3）難點：進程的相互制約；相關臨界區(qū)的概念；進程通信；用信號量解決進程的互斥與同步；

    （三）存儲管理

    考試內(nèi)容：

    1.概念：相對地址，絕對地址，重定位，靜態(tài)重定位，動態(tài)重定位，碎片，拼接，頁表，快表，段表，虛擬存儲器的概念及特征，抖動（顛簸）

    2.理解與應用

    （1）固定分區(qū)的內(nèi)存分配原理

    （2）動態(tài)（可變）分區(qū)的內(nèi)存分配原理，及常用數(shù)據(jù)結構

    （3）動態(tài)（可變）分區(qū)常用的三種分配算法（首次適應算法、循環(huán)首次適應算法、最佳適應算法）

    （4）引入分頁和分段的原因

    （5）基本分頁的實現(xiàn)原理及和機制

    （6）基本分段的實現(xiàn)原理及和機制

    （7）分頁與分段的主要區(qū)別

    （8）請求分頁管理的實現(xiàn)原理和機制

    （9）缺頁中斷的處理過程及缺頁中斷與一般中斷的區(qū)別

    （10）掌握常用的頁面置換算法（最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）），并能根據(jù)算法思想完成相應計算

    （11）請求分段管理的實現(xiàn)原理和機制

    考試要求：

    （1）掌握基本概念和原理

    （2）重點：虛擬存儲器的概念；靜態(tài)與動態(tài)重定位及其區(qū)別；可變分區(qū)的管理算法；分頁管理的實現(xiàn)原理和機制；基本分段的實現(xiàn)原理和機制；典型的頁面替換算法；分頁與分段的區(qū)別。

    （3）難點：虛擬存儲器的概念；頁面替換算法；分頁與分段的區(qū)別。

    （四）設備管理

    考試內(nèi)容：

    1.概念：I/O設備的分類，通道，設備無關性，虛擬設備，SPOOLing技術，尋道時間，旋轉(zhuǎn)延遲時間

    2.理解與應用：

    （1）設備管理的功能

    （2）設備控制器的功能

    （3）通道的分類

    （4）I/O的幾種控制方式（程序I/O方式、中斷控制方式、DMA方式、通道控制方式）的工作原理及特點

    （5）緩沖技術的引入目的和緩沖區(qū)的分類

    （6）設備無關性；

    （7）設備分配中常用的數(shù)據(jù)結構

    （8）獨占設備的分配與釋放。

    （9）SPOOLing系統(tǒng)的組成及實現(xiàn)

    （10）磁盤調(diào)度常用的幾種調(diào)度算法（先來先服務、最短尋道優(yōu)先、掃描算法、循環(huán)掃描算法），并能根據(jù)算法思想完成相應計算

    考試要求：

    （１）掌握基本概念和原理

    （２）重點：I/O控制方式；緩沖技術的引入目的和緩沖區(qū)的種類；虛擬設備的概念和SPOOLING系統(tǒng)的組成和實現(xiàn)；磁盤調(diào)度算法。

    （3）難點：設備無關性；虛擬設備；I/O控制方式。

    （五）文件管理

    考試內(nèi)容：

    1.概念：文件、文件的分類，文件邏輯結構，文件物理結構，目錄，文件控制塊，按名存取，位示圖

    2.理解與應用：

    （１）文件和文件系統(tǒng)的概念；

    （２）文件的基本操作

    （3）文件邏輯結構中的順序文件、索引文件和索引順序文件的形式和特點

    （4）文件物理結構中涉及的連續(xù)分配、鏈接分配和索引分配如何實現(xiàn)一個文件在外存上的存放及每種分配方式的特點

    （5）二級和多級文件目錄的形式及特點

    （6）管理文件存儲空間的常用方法

    （7）通過位示圖如何實現(xiàn)盤塊的分配和回收

    考試要求：

    （１）掌握基本概念和原理

    （２）重點：文件的邏輯結構和物理結構；二級和多級文件目錄；管理文件存儲空間的方法。

    （3）難點：文件的邏輯結構；文件的物理結構。

    主要參考書目

    《數(shù)據(jù)結構C語言版》，嚴蔚敏著，清華大學出版社

    《計算機操作系統(tǒng)（第三版）》湯小丹著，西安電子科技大學出版社

添加新疆農(nóng)業(yè)大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[新疆農(nóng)業(yè)大學考研分數(shù)線、新疆農(nóng)業(yè)大學報錄比、新疆農(nóng)業(yè)大學考研群、新疆農(nóng)業(yè)大學學姐微信、新疆農(nóng)業(yè)大學考研真題、新疆農(nóng)業(yè)大學專業(yè)目錄、新疆農(nóng)業(yè)大學排名、新疆農(nóng)業(yè)大學保研、新疆農(nóng)業(yè)大學公眾號、新疆農(nóng)業(yè)大學研究生招生）]即可在手機上查看相對應新疆農(nóng)業(yè)大學考研信息或資源。