新疆農(nóng)業(yè)大學(xué)全日制碩士研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)》考試大綱
| 命題方式 | 招生單位自命題 | 科目類(lèi)別 | 初試 | |
| 滿分 | 150 | |||
| 考試性質(zhì) 《數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)》課程主要包含數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)兩塊內(nèi)容。該課程的考試是為招收工學(xué)類(lèi)碩士研究生而設(shè)置的選拔考試。它的主要目的是測(cè)試考生對(duì)該課程的把握程度，包括對(duì)課程中的概念、基本原理和方法的理解和掌握，及能夠運(yùn)用所學(xué)的原理和方法分析、判斷及解決有關(guān)理論問(wèn)題和實(shí)際問(wèn)題。 |
||||
| 考試方式和考試時(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) （三）樹(shù) 考試內(nèi)容： 1. 概念：樹(shù)，子樹(shù)，二叉樹(shù)，結(jié)點(diǎn)的度，分支結(jié)點(diǎn)，雙親、兄弟、堂兄、祖先、子孫結(jié)點(diǎn)，樹(shù)的深度，無(wú)序樹(shù)，有序樹(shù)，森林，滿二叉樹(shù)，完全二叉樹(shù)，線索二叉樹(shù)，最優(yōu)二叉樹(shù)，樹(shù)的帶權(quán)路徑長(zhǎng)度 2. 理解與應(yīng)用 （1）二叉樹(shù)的性質(zhì) （2）滿二叉樹(shù)與完全二叉樹(shù)的區(qū)別與聯(lián)系 （3）二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) （4）二叉樹(shù)的三種遍歷算法的思想及實(shí)現(xiàn)方法 （5）二叉樹(shù)的線索過(guò)程 （6）樹(shù)的存儲(chǔ)結(jié)構(gòu)及表示 （7）樹(shù)、二叉樹(shù)、森林間的相互轉(zhuǎn)換 （8）樹(shù)、森林的遍歷與二叉樹(shù)的遍歷之間的聯(lián)系 （9）線索二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) （10）二叉樹(shù)的線索化算法 （11）赫夫曼樹(shù)的構(gòu)造算法及實(shí)現(xiàn)方法 考試要求： （1）掌握基本概念 （2）掌握算法的思想，能對(duì)算法代碼實(shí)現(xiàn) （3）了解樹(shù)、二叉樹(shù)、森林的存儲(chǔ)結(jié)構(gòu)、遍歷關(guān)系 （四）圖 考試內(nèi)容： 1. 概念：圖，頂點(diǎn)，弧，有向圖，無(wú)向圖，完全圖，子圖，頂點(diǎn)的度，路徑，簡(jiǎn)單路徑，回路，連通圖，連通分量，強(qiáng)連通圖，強(qiáng)連通分量，生成樹(shù)，生成森林 ，有向無(wú)環(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）圖的最小生成樹(shù)構(gòu)造算法思想及實(shí)現(xiàn)方法 （5）拓?fù)渑判蛩惴ǖ乃枷爰皩?shí)現(xiàn)方法 （6）最短路徑的構(gòu)造算法 考試要求： （1）掌握基本概念 （2）掌握算法的思想，能對(duì)算法代碼實(shí)現(xiàn) （3）了解各種算法的應(yīng)用范圍和解決的實(shí)際問(wèn)題 （五）查找 考試內(nèi)容： 1. 概念：查找表，關(guān)鍵字，靜態(tài)查找，動(dòng)態(tài)查找，平均查找長(zhǎng)度，二叉排序樹(shù)，平衡因子，平衡二叉樹(shù)，B-樹(shù)，B+樹(shù)，鍵樹(shù)，TRIE樹(shù)，哈希表， 2. 理解與應(yīng)用： （1）理解靜態(tài)查找和動(dòng)態(tài)查找的區(qū)別 （2）靜態(tài)查找的三種方法及實(shí)現(xiàn)，三種方法的特點(diǎn)及適用范圍 （3）二叉排序樹(shù)的構(gòu)造和插入算法的思想及實(shí)現(xiàn)方法 （4）二叉排序樹(shù)構(gòu)造過(guò)程中的平衡處理算法的思想 （5）各種查找方法的ASL計(jì)算 （6）B-樹(shù)上的查找、插入、刪除算法的思想 （7）哈希函數(shù)的構(gòu)造方法 （8）哈希構(gòu)造中處理沖突的方法 考試要求： （1）掌握基本概念 （2）掌握算法的思想，能對(duì)算法代碼實(shí)現(xiàn) （3）掌握哈希表的構(gòu)造方法 （4）了解各種算法的應(yīng)用范圍和解決的實(shí)際問(wèn)題 （六）排序 1. 概念：排序，穩(wěn)定，內(nèi)排序，外排序 2. 理解與應(yīng)用： （1）排序算法的分類(lèi)，重要指標(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)程通信的類(lèi)型，線程，線程的屬性，處理機(jī)的三級(jí)調(diào)度，進(jìn)程的兩種調(diào)度方式，周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間，常用的幾種調(diào)度算法（先來(lái)先服務(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)程同步問(wèn)題（生產(chǎn)者-消費(fèi)者問(wèn)題；讀者-寫(xiě)者問(wèn)題；哲學(xué)家進(jìn)餐問(wèn)題） （8）利用管理解決生產(chǎn)者和消費(fèi)者問(wèn)題 （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ū)問(wèn)題和臨界資源；用信號(hào)量解決進(jìn)程的同步與互斥問(wè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)重定位，碎片，拼接，頁(yè)表，快表，段表，虛擬存儲(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）引入分頁(yè)和分段的原因 （5）基本分頁(yè)的實(shí)現(xiàn)原理及和機(jī)制 （6）基本分段的實(shí)現(xiàn)原理及和機(jī)制 （7）分頁(yè)與分段的主要區(qū)別 （8）請(qǐng)求分頁(yè)管理的實(shí)現(xiàn)原理和機(jī)制 （9）缺頁(yè)中斷的處理過(guò)程及缺頁(yè)中斷與一般中斷的區(qū)別 （10）掌握常用的頁(yè)面置換算法（最佳置換算法（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ū)的管理算法；分頁(yè)管理的實(shí)現(xiàn)原理和機(jī)制；基本分段的實(shí)現(xiàn)原理和機(jī)制；典型的頁(yè)面替換算法；分頁(yè)與分段的區(qū)別。 （3）難點(diǎn)：虛擬存儲(chǔ)器的概念；頁(yè)面替換算法；分頁(yè)與分段的區(qū)別。 （四）設(shè)備管理 考試內(nèi)容： 1. 概念：I/O設(shè)備的分類(lèi)，通道，設(shè)備無(wú)關(guān)性，虛擬設(shè)備，SPOOLing技術(shù)，尋道時(shí)間，旋轉(zhuǎn)延遲時(shí)間 2. 理解與應(yīng)用： （1）設(shè)備管理的功能 （2）設(shè)備控制器的功能 （3）通道的分類(lèi) （4）I/O的幾種控制方式（程序I/O方式、中斷控制方式、DMA方式、通道控制方式）的工作原理及特點(diǎn) （5）緩沖技術(shù)的引入目的和緩沖區(qū)的分類(lèi) （6）設(shè)備無(wú)關(guān)性； （7）設(shè)備分配中常用的數(shù)據(jù)結(jié)構(gòu) （8）獨(dú)占設(shè)備的分配與釋放。 （9）SPOOLing系統(tǒng)的組成及實(shí)現(xiàn) （10）磁盤(pán)調(diào)度常用的幾種調(diào)度算法（先來(lái)先服務(wù)、最短尋道優(yōu)先、掃描算法、循環(huán)掃描算法），并能根據(jù)算法思想完成相應(yīng)計(jì)算 考試要求： （１）掌握基本概念和原理 （２）重點(diǎn)：I/O控制方式；緩沖技術(shù)的引入目的和緩沖區(qū)的種類(lèi)；虛擬設(shè)備的概念和SPOOLING系統(tǒng)的組成和實(shí)現(xiàn)；磁盤(pán)調(diào)度算法。 （3）難點(diǎn)：設(shè)備無(wú)關(guān)性；虛擬設(shè)備；I/O控制方式。 （五）文件管理 考試內(nèi)容： 1. 概念：文件、文件的分類(lèi)，文件邏輯結(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）通過(guò)位示圖如何實(shí)現(xiàn)盤(pán)塊的分配和回收 考試要求： （１）掌握基本概念和原理 （２）重點(diǎn)：文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；二級(jí)和多級(jí)文件目錄；管理文件存儲(chǔ)空間的方法。 （3）難點(diǎn)：文件的邏輯結(jié)構(gòu)；文件的物理結(jié)構(gòu)。 |
||||
| 主要參考書(shū)目 《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》，嚴(yán)蔚敏著，清華大學(xué)出版社 《計(jì)算機(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é)考試初試自命題考試大綱及參考書(shū)目”的全部?jī)?nèi)容，更多考研大綱信息，請(qǐng)多多關(guān)注！
