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