新疆農(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)理論問(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ù)渑判颍P(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）排序算法的分類，重要指標(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)度算法（先來(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è)備的分類，通道，設(shè)備無(wú)關(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è)備無(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ū)的種類；虛擬設(shè)備的概念和SPOOLING系統(tǒng)的組成和實(shí)現(xiàn)；磁盤(pán)調(diào)度算法。

    （3）難點(diǎn)：設(shè)備無(wú)關(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）通過(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é)出版社

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