考試大綱不僅能給你一個復(fù)習(xí)的方向，還能幫助你梳理整個知識脈絡(luò)，方便記憶。今天，小編為大家整理了“2021考研大綱：新疆農(nóng)業(yè)大學(xué)856數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)2021年碩士研究生入學(xué)考試初試自命題考試大綱及參考書目”的相關(guān)內(nèi)容，希望對大家有所幫助！
新疆農(nóng)業(yè)大學(xué)全日制碩士研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)》考試大綱
命題方式
招生單位自命題
科目類別
初試
滿分
150
考試性質(zhì)
《數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)》課程主要包含數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩塊內(nèi)容。該課程的考試是為招收工學(xué)類碩士研究生而設(shè)置的選拔考試。它的主要目的是測試考生對該課程的把握程度，包括對課程中的概念、基本原理和方法的理解和掌握，及能夠運用所學(xué)的原理和方法分析、判斷及解決有關(guān)理論問題和實際問題。
考試方式和考試時間
考試采用閉卷筆試形式，試卷滿分為150分（數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)各占75分），考試時間為3小時。
考試內(nèi)容和考試要求
一、數(shù)據(jù)結(jié)構(gòu)
（一）數(shù)據(jù)結(jié)構(gòu)概論
考試內(nèi)容：
1．概念：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)項，數(shù)據(jù)的四種經(jīng)典邏輯結(jié)構(gòu)，數(shù)據(jù)的物理存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)研究的三個方向，算法，算法的時間復(fù)雜度、空間復(fù)雜度
2．理解和應(yīng)用：
（1）數(shù)據(jù)的四種經(jīng)典邏輯結(jié)構(gòu)之間的區(qū)別和聯(lián)系
（2）算法的特性和設(shè)計的要求
（3）時間復(fù)雜度和空間復(fù)雜度的關(guān)系
考試要求
（1）掌握基本概念
（2）能計算出給定程序的時間復(fù)雜度
（二）線性結(jié)構(gòu)
考試內(nèi)容：
1.概念：線性結(jié)構(gòu)的特點，線性表，線性表的順序存儲特點，順序表中元素存儲位置之間的關(guān)系，線性鏈表，循環(huán)鏈表，雙向鏈表，棧，隊列，循環(huán)隊列，串，子串，模式匹配算法
2.理解與應(yīng)用：
（1）線性表、棧、隊列與線性結(jié)構(gòu)的關(guān)系
（2）線性表的順序存儲結(jié)構(gòu)表示
（3）順序表中的插入、刪除、合并操作算法的思想及實現(xiàn)方法
（4）線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)表示
（5）單鏈表的創(chuàng)建、查找、插入、刪除、合并算法的思想及實現(xiàn)方法
（6）雙向鏈表的插入和刪除算法的思想及實現(xiàn)
（7）棧中棧頂、棧底的含義，棧中元素操作的特點
（8）棧頂指針的作用及意義
（9）棧的進(jìn)棧、出棧算法的思想及實現(xiàn)方法
（10）棧的應(yīng)用
（11）隊列中隊頭、隊尾的含義，隊列的基本特點
（12）循環(huán)隊列的設(shè)計思路及實現(xiàn)方法
（13）隊列的入隊列、出隊列算法的思想及實現(xiàn)方法
（14）子串的位置及模式匹配
（15）子串的定位算法及KMP算法
考試要求：
（1）掌握基本概念
（2）對算法的思想能進(jìn)行文字描述
（3）了解棧與隊列的操作特點
（三）樹
考試內(nèi)容：
1.概念：樹，子樹，二叉樹，結(jié)點的度，分支結(jié)點，雙親、兄弟、堂兄、祖先、子孫結(jié)點，樹的深度，無序樹，有序樹，森林，滿二叉樹，完全二叉樹，線索二叉樹，最優(yōu)二叉樹，樹的帶權(quán)路徑長度
2.理解與應(yīng)用
（1）二叉樹的性質(zhì)
（2）滿二叉樹與完全二叉樹的區(qū)別與聯(lián)系
（3）二叉樹的存儲結(jié)構(gòu)及實現(xiàn)
（4）二叉樹的三種遍歷算法的思想及實現(xiàn)方法
（5）二叉樹的線索過程
（6）樹的存儲結(jié)構(gòu)及表示
（7）樹、二叉樹、森林間的相互轉(zhuǎn)換
（8）樹、森林的遍歷與二叉樹的遍歷之間的聯(lián)系
（9）線索二叉樹的存儲結(jié)構(gòu)
（10）二叉樹的線索化算法
（11）赫夫曼樹的構(gòu)造算法及實現(xiàn)方法
考試要求：
（1）掌握基本概念
（2）掌握算法的思想，能對算法代碼實現(xiàn)
（3）了解樹、二叉樹、森林的存儲結(jié)構(gòu)、遍歷關(guān)系
（四）圖
考試內(nèi)容：
1.概念：圖，頂點，弧，有向圖，無向圖，完全圖，子圖，頂點的度，路徑，簡單路徑，回路，連通圖，連通分量，強(qiáng)連通圖，強(qiáng)連通分量，生成樹，生成森林，有向無環(huán)圖，拓?fù)渑判颍P(guān)鍵路徑，AOV網(wǎng)，AOE網(wǎng)，最短路徑
2.理解與應(yīng)用：
（1）圖的特點
（2）圖的存儲結(jié)構(gòu)及實現(xiàn)
（3）圖的遍歷算法思想及實現(xiàn)方法
（4）圖的最小生成樹構(gòu)造算法思想及實現(xiàn)方法
（5）拓?fù)渑判蛩惴ǖ乃枷爰皩崿F(xiàn)方法
（6）最短路徑的構(gòu)造算法
考試要求：
（1）掌握基本概念
（2）掌握算法的思想，能對算法代碼實現(xiàn)
（3）了解各種算法的應(yīng)用范圍和解決的實際問題
（五）查找
考試內(nèi)容：
1.概念：查找表，關(guān)鍵字，靜態(tài)查找，動態(tài)查找，平均查找長度，二叉排序樹，平衡因子，平衡二叉樹，B-樹，B+樹，鍵樹，TRIE樹，哈希表，
2.理解與應(yīng)用：
（1）理解靜態(tài)查找和動態(tài)查找的區(qū)別
（2）靜態(tài)查找的三種方法及實現(xiàn)，三種方法的特點及適用范圍
（3）二叉排序樹的構(gòu)造和插入算法的思想及實現(xiàn)方法
（4）二叉排序樹構(gòu)造過程中的平衡處理算法的思想
（5）各種查找方法的ASL計算
（6）B-樹上的查找、插入、刪除算法的思想
（7）哈希函數(shù)的構(gòu)造方法
（8）哈希構(gòu)造中處理沖突的方法
考試要求：
（1）掌握基本概念
（2）掌握算法的思想，能對算法代碼實現(xiàn)
（3）掌握哈希表的構(gòu)造方法
（4）了解各種算法的應(yīng)用范圍和解決的實際問題
（六）排序
1.概念：排序，穩(wěn)定，內(nèi)排序，外排序
2.理解與應(yīng)用：
（1）排序算法的分類，重要指標(biāo)
（2）各種排序算法的思想及實現(xiàn)方法
（3）各種算法的穩(wěn)定性、時間復(fù)雜度、空間復(fù)雜度
（4）各種排序算法的特點和適用范圍
考試要求：
（1）掌握基本概念
（2）掌握各種排序算法的思想，能對算法代碼實現(xiàn)
（3）理解各種排序方法的優(yōu)缺點和適用范圍
（4）了解穩(wěn)定性、時間復(fù)雜度和空間復(fù)雜度對排序的影響
二、操作系統(tǒng)原理
（一）操作系統(tǒng)概論
考試內(nèi)容：
1．概念：操作系統(tǒng)的定義、功能和地位，操作系統(tǒng)的發(fā)展，操作系統(tǒng)基本特征
2．理解和應(yīng)用：
（1）批處理多道系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)三個基本操作系統(tǒng)的工作原理及特征
（2）分時系統(tǒng)與實時系統(tǒng)的區(qū)別
（3）基本操作系統(tǒng)的特征
考試要求
（1）掌握基本概念
（2）理解操作系統(tǒng)在計算機(jī)系統(tǒng)中的地位和三個基本特征
（二）進(jìn)程管理
考試內(nèi)容：
1．概念：前趨圖，進(jìn)程的定義、特征、三種基本狀態(tài)（就緒、阻塞和運行），進(jìn)程控制塊，臨界資源，臨界區(qū)，同步機(jī)制應(yīng)遵循的原則，管程的定義，條件變量，進(jìn)程通信的類型，線程，線程的屬性，處理機(jī)的三級調(diào)度，進(jìn)程的兩種調(diào)度方式，周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間，常用的幾種調(diào)度算法（先來先服務(wù)、短作業(yè)（進(jìn)程）優(yōu)先、高優(yōu)先權(quán)優(yōu)先、高響應(yīng)比優(yōu)先、時間片輪轉(zhuǎn)法、多級反饋隊列調(diào)度），優(yōu)先權(quán)，響應(yīng)比，死鎖，產(chǎn)生死鎖的原因、必要條件及處理死鎖的基本方法，死鎖定理
2．理解與應(yīng)用：
（1）進(jìn)程與程序的區(qū)別
（2）進(jìn)程三個基本狀態(tài)之間的轉(zhuǎn)換及引起轉(zhuǎn)換的原因
（3）進(jìn)程的兩種制約關(guān)系，并能進(jìn)行辨別
（4）能夠辨別臨界資源
（5）常用的幾種信號量機(jī)制及每種機(jī)制的原理
（6）利用信號量實現(xiàn)進(jìn)程的互斥、同步和前趨關(guān)系
（7）理解經(jīng)典的進(jìn)程同步問題（生產(chǎn)者-消費者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題）
（8）利用管理解決生產(chǎn)者和消費者問題
（9）消息傳遞通信的實現(xiàn)方法
（10）消息緩沖隊列通信的實現(xiàn)方法
（11）理解什么是內(nèi)核支持線程和用戶級線程
（12）進(jìn)程與線程的區(qū)別
（13）進(jìn)程調(diào)度方式中搶占式的搶占原則
（14）理解每種調(diào)度算法的算法思想、優(yōu)缺點，并能根據(jù)算法思想完成相應(yīng)計算
（15）預(yù)防死鎖的各種方法
（16）銀行家算法的思想
（17）能夠根據(jù)銀行家算法和安全性檢測算法判斷系統(tǒng)的安全狀態(tài)及決定是否分配資源
（18）死鎖檢測的方法
（19）死鎖解除的方法
考試要求：
（1）掌握基本概念及基本原理
（2）重點：進(jìn)程的概念和進(jìn)程的并發(fā)特征；進(jìn)程與程序的區(qū)別；進(jìn)程狀態(tài)及轉(zhuǎn)換；相關(guān)臨界區(qū)問題和臨界資源；用信號量解決進(jìn)程的同步與互斥問題；進(jìn)程調(diào)度算法；死鎖的概念與解決死鎖的方法。
（3）難點：進(jìn)程的相互制約；相關(guān)臨界區(qū)的概念；進(jìn)程通信；用信號量解決進(jìn)程的互斥與同步；
（三）存儲管理
考試內(nèi)容：
1.概念：相對地址，絕對地址，重定位，靜態(tài)重定位，動態(tài)重定位，碎片，拼接，頁表，快表，段表，虛擬存儲器的概念及特征，抖動（顛簸）
2.理解與應(yīng)用
（1）固定分區(qū)的內(nèi)存分配原理
（2）動態(tài)（可變）分區(qū)的內(nèi)存分配原理，及常用數(shù)據(jù)結(jié)構(gòu)
（3）動態(tài)（可變）分區(qū)常用的三種分配算法（首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法）
（4）引入分頁和分段的原因
（5）基本分頁的實現(xiàn)原理及和機(jī)制
（6）基本分段的實現(xiàn)原理及和機(jī)制
（7）分頁與分段的主要區(qū)別
（8）請求分頁管理的實現(xiàn)原理和機(jī)制
（9）缺頁中斷的處理過程及缺頁中斷與一般中斷的區(qū)別
（10）掌握常用的頁面置換算法（最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）），并能根據(jù)算法思想完成相應(yīng)計算
（11）請求分段管理的實現(xiàn)原理和機(jī)制
考試要求：
（1）掌握基本概念和原理
（2）重點：虛擬存儲器的概念；靜態(tài)與動態(tài)重定位及其區(qū)別；可變分區(qū)的管理算法；分頁管理的實現(xiàn)原理和機(jī)制；基本分段的實現(xiàn)原理和機(jī)制；典型的頁面替換算法；分頁與分段的區(qū)別。
（3）難點：虛擬存儲器的概念；頁面替換算法；分頁與分段的區(qū)別。
（四）設(shè)備管理
考試內(nèi)容：
1.概念：I/O設(shè)備的分類，通道，設(shè)備無關(guān)性，虛擬設(shè)備，SPOOLing技術(shù)，尋道時間，旋轉(zhuǎn)延遲時間
2.理解與應(yīng)用：
（1）設(shè)備管理的功能
（2）設(shè)備控制器的功能
（3）通道的分類
（4）I/O的幾種控制方式（程序I/O方式、中斷控制方式、DMA方式、通道控制方式）的工作原理及特點
（5）緩沖技術(shù)的引入目的和緩沖區(qū)的分類
（6）設(shè)備無關(guān)性；
（7）設(shè)備分配中常用的數(shù)據(jù)結(jié)構(gòu)
（8）獨占設(shè)備的分配與釋放。
（9）SPOOLing系統(tǒng)的組成及實現(xiàn)
（10）磁盤調(diào)度常用的幾種調(diào)度算法（先來先服務(wù)、最短尋道優(yōu)先、掃描算法、循環(huán)掃描算法），并能根據(jù)算法思想完成相應(yīng)計算
考試要求：
（１）掌握基本概念和原理
（２）重點：I/O控制方式；緩沖技術(shù)的引入目的和緩沖區(qū)的種類；虛擬設(shè)備的概念和SPOOLING系統(tǒng)的組成和實現(xiàn)；磁盤調(diào)度算法。
（3）難點：設(shè)備無關(guān)性；虛擬設(shè)備；I/O控制方式。
（五）文件管理
考試內(nèi)容：
1.概念：文件、文件的分類，文件邏輯結(jié)構(gòu)，文件物理結(jié)構(gòu)，目錄，文件控制塊，按名存取，位示圖
2.理解與應(yīng)用：
（１）文件和文件系統(tǒng)的概念；
（２）文件的基本操作
（3）文件邏輯結(jié)構(gòu)中的順序文件、索引文件和索引順序文件的形式和特點
（4）文件物理結(jié)構(gòu)中涉及的連續(xù)分配、鏈接分配和索引分配如何實現(xiàn)一個文件在外存上的存放及每種分配方式的特點
（5）二級和多級文件目錄的形式及特點
（6）管理文件存儲空間的常用方法
（7）通過位示圖如何實現(xiàn)盤塊的分配和回收
考試要求：
（１）掌握基本概念和原理
（２）重點：文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；二級和多級文件目錄；管理文件存儲空間的方法。
（3）難點：文件的邏輯結(jié)構(gòu)；文件的物理結(jié)構(gòu)。
主要參考書目
《數(shù)據(jù)結(jié)構(gòu)C語言版》，嚴(yán)蔚敏著，清華大學(xué)出版社
《計算機(jī)操作系統(tǒng)（第三版）》湯小丹著，西安電子科技大學(xué)出版社
原文標(biāo)題：紹興文理學(xué)院2021年研究生入學(xué)考試初試自命題科目考試大綱
原文鏈接：http://yzw.usx.edu.cn/info/1013/1562.htm
以上就是“2021考研大綱：新疆農(nóng)業(yè)大學(xué)856數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)2021年碩士研究生入學(xué)考試初試自命題考試大綱及參考書目”的全部內(nèi)容，更多考研大綱信息，請多多關(guān)注！