新疆農(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è)置的選拔考試。它的主要目的是測試考生對該課程的把握程度，包括對課程中的概念、基本原理和方法的理解和掌握，及能夠運(yùn)用所學(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)（就緒、阻塞和運(yùn)行），進(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)者-消費(fèi)者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題） （8）利用管理解決生產(chǎn)者和消費(fèi)者問題 （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）獨(dú)占設(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é)出版社 |
||||
原文鏈接：http://yjsc.xjau.edu.cn/2020/0925/c2153a71742/page.htm
以上就是“2021考研大綱：新疆農(nóng)業(yè)大學(xué)856數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)2021年碩士研究生入學(xué)考試初試自命題考試大綱及參考書目”的全部內(nèi)容，更多考研大綱信息，請多多關(guān)注！
