2023年天津理工大學(xué)計算機科學(xué)與技術(shù)考研808考試大綱

考試大綱的內(nèi)容一般包括當(dāng)年全國研究生入學(xué)考試相應(yīng)科目的考試范圍、考試要求、考試形式、試卷結(jié)構(gòu)等信息，對考生備考至關(guān)重要。希賽網(wǎng)整理了2023年天津理工大學(xué)計算機科學(xué)與技術(shù)（081200）考研808數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考試大綱信息，希望對考生備考有所幫助。

相關(guān)閱讀推薦>>>2021-2022年全國考研復(fù)試線丨2023年全國考試科目匯總丨2023年全國研究方向匯總

（注：以下信息來自學(xué)院官網(wǎng)，僅供參考，具體內(nèi)容以院校發(fā)布為準(zhǔn)）

808 數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)一初試考試大綱

一、考試方式

考試采用筆試形式，考試時間為180分鐘，試卷滿分為150分。

二、 試卷結(jié)構(gòu)與分數(shù)比重

數(shù)據(jù)結(jié)構(gòu)占80分，題型及分配比例：選擇題(25%)、綜合應(yīng)用題(75%)。

操作系統(tǒng)占70分，題型及分配比例：填空題(20%)、選擇題(20%)、簡述題(20%)、算法實現(xiàn)與綜合分析習(xí)題(40%)。

三、考查的知識范圍

《數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》入學(xué)考試總分150分，包括兩部分內(nèi)容：其中數(shù)據(jù)結(jié)構(gòu)考試主要涉及線性結(jié)構(gòu)、樹、圖、查找和排序中的典型數(shù)據(jù)結(jié)構(gòu)和算法，要能夠針對具體問題進行分析，選擇正確的邏輯結(jié)構(gòu)、設(shè)計合理的存儲結(jié)構(gòu)、提出解決問題的方法或算法，并能對所選方法和算法的正確性、復(fù)雜性進行分析，占80分;操作系統(tǒng)考試主要涉及基本概念、原理和功能，理解操作系統(tǒng)的整體運行過程， 掌握操作系統(tǒng)進程、內(nèi)存、文件和I/O管理的策略、算法、機制以及相互關(guān)系，能夠運用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題，并能利用C語言描述相關(guān)算法，占70分。

數(shù)據(jù)結(jié)構(gòu)部分

一、緒論

1. 數(shù)據(jù)結(jié)構(gòu)相關(guān)基本概念

2. 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

3. 算法效率的度量(O-表示法)

二、線性表、棧和隊列(以下各點要求掌握算法的程序?qū)崿F(xiàn))

1. 順序表的表示和基本操作的實現(xiàn)算法

2. 單鏈表、循環(huán)鏈表、雙向鏈表的表示和基本操作的實現(xiàn)算法

3. 棧的表示和基本操作的實現(xiàn)算法

4. 循環(huán)隊列、鏈隊列的表示和基本操作的實現(xiàn)算法

三、數(shù)組、遞歸

1. 數(shù)組的存儲方式

2. 特殊矩陣的壓縮存儲

3. 遞歸思想的特點

4. 遞歸算法和遞歸函數(shù)

四、樹和二叉樹

1. 樹的定義和基本術(shù)語

2. 二叉樹的定義、性質(zhì)，二叉鏈表存儲結(jié)構(gòu)

3. 完全二叉樹的性質(zhì)

4. 二叉樹的深度優(yōu)先(先序、中序、后序)和廣度優(yōu)先(層序)遍歷算法和程序?qū)崿F(xiàn)

5. 樹的存儲結(jié)構(gòu)

6. 樹、森林與二叉樹的轉(zhuǎn)換

7. 哈夫曼樹的定義、性質(zhì)、構(gòu)造方法、哈夫曼樹的應(yīng)用

五、圖

1. 圖的定義和術(shù)語

2. 圖的鄰接矩陣、鄰接表存儲結(jié)構(gòu)

3. 圖的深度優(yōu)先搜索、廣度優(yōu)先搜索及其算法實現(xiàn)

4. 生成樹的定義，圖的最小生成樹定義與構(gòu)造方法(不要求算法實現(xiàn))

5. 拓撲排序

6. 單源最短路徑問題的求解

六、查找

1. 平均搜索長度(ASL)的定義

2. 順序表的查找算法、程序?qū)崿F(xiàn)和ASL分析

3. 二分查找法的算法描述、程序?qū)崿F(xiàn)和ASL分析

4. 索引順序表的查找(分塊查找)方法和和ASL分析

5. 二叉排序樹的定義、插入、刪除操作

6. 平衡二叉樹的定義、構(gòu)造(掌握4種旋轉(zhuǎn)方法)，計算等概率下查找成功的ASL和查找不成功的ASL

7. B-樹的定義、插入與刪除操作

8. 散列表的概念，幾種常用散列函數(shù)的構(gòu)造方法

9. 散列表處理沖突的方法(線性探查法、二次探查法、再散列法、鏈地址法)，計算等概率下查找成功的ASL和查找不成功的ASL

10.散列表負載因子(裝填因子)α的定義

七、排序(以下每種排序算法要求掌握排序過程和程序?qū)崿F(xiàn))

1. 直接插入排序、希爾排序

2. 冒泡排序、快速排序

3. 簡單選擇排序、堆排序

4. 歸并排序

5. 基數(shù)排序(箱排序)

6. 以上各種排序算法的時間復(fù)雜度分析，各自的特征及其比較

操作系統(tǒng)部分

一、操作系統(tǒng)概述

1.操作系統(tǒng)的概念、特征、功能和作用

2.操作系統(tǒng)的發(fā)展與分類

3.操作系統(tǒng)體系結(jié)構(gòu)

二、進程管理

1.進程與線程

(1)進程概念

(2)進程的狀態(tài)與轉(zhuǎn)換

(3)進程控制

(4)進程同步

(5)進程通信

共享存儲系統(tǒng);消息傳遞系統(tǒng);管道通信。

(6)線程概念與線程實現(xiàn)方式

2.處理機調(diào)度

(1)調(diào)度的基本概念

(2)調(diào)度時機、切換與過程

(3)調(diào)度的基本準(zhǔn)則

(4)調(diào)度方式

(5)典型調(diào)度算法

先來先服務(wù)調(diào)度算法;短作業(yè)(短進程、短線程)優(yōu)先調(diào)度算法;時間片輪轉(zhuǎn)調(diào)度算法;優(yōu)先級調(diào)度算法;高響應(yīng)比優(yōu)先調(diào)度算法;多級反饋隊列調(diào)度算法。

3.同步與互斥

(1)進程同步的基本概念

(2)實現(xiàn)臨界區(qū)互斥的基本方法

軟件實現(xiàn)方法;硬件實現(xiàn)方法。

(3)信號量機制

(4)管程機制

(5)經(jīng)典同步問題

生產(chǎn)者-消費者問題;讀者-寫者問題;哲學(xué)家進餐問題;睡眠理發(fā)師問題。

4.死鎖

(1)死鎖的概念

(2)死鎖處理策略

(3)死鎖預(yù)防

(4)死鎖避免

系統(tǒng)安全狀態(tài);銀行家算法。

(5)死鎖檢測和解除

三、存儲器管理

1.存儲器管理概念

(1)存儲器的層次結(jié)構(gòu)

(2)程序的裝入和鏈接

絕對裝入方式;可重定位裝入方式;動態(tài)運行時裝入方式。

靜態(tài)鏈接方式;裝入時動態(tài)鏈接方式;運行時動態(tài)鏈接方式。

(3)交換技術(shù)

(4)連續(xù)分配存儲管理方式

單一連續(xù)分配;固定分區(qū)分配;動態(tài)分區(qū)分配(基于順序搜索的動態(tài)分區(qū)分配算法、基于索引的動態(tài)分區(qū)分配算法);動態(tài)可重定位分區(qū)分配。

(5)非連續(xù)分配管理方式

分頁管理方式;分段管理方式;段頁式管理方式。

2.虛擬內(nèi)存管理

(1)虛擬存儲器基本概念

(2)請求分頁存儲管理方式

(3)頁面置換算法

最佳置換算法OPT;先進先出置換算法FIFO;最近最久未使用置換算法LRU;最少使用置換算法LFU;時鐘置換算法CLOCK;頁面緩沖算法PBA。

(4)頁面分配策略

(5)抖動與工作集

(6)請求分段存儲管理方式

四、輸入輸出(I/O)管理

1.I/O管理概述

(1)I/O系統(tǒng)的功能

(2)I/O軟件層次結(jié)構(gòu)

(3)I/O系統(tǒng)接口

(4)I/O控制方式

(5)設(shè)備控制器

(6)設(shè)備驅(qū)動程序

(7)設(shè)備無關(guān)性

2.I/O核心子系統(tǒng)

(1)緩沖區(qū)管理

(2)設(shè)備分配與回收

(3)假脫機技術(shù)(SPOOLing)

3.磁盤存儲器的性能和調(diào)度

(1)磁盤性能與結(jié)構(gòu)

(2)磁盤調(diào)度算法

先來先付服務(wù)FCFSl;最短尋道時間優(yōu)先DDTF;掃描算法SCAN (電梯調(diào)度算法);循環(huán)掃描算法CSCAN;NStepSCAN和FSCAN調(diào)度算法。

五、文件管理

1.文件系統(tǒng)基礎(chǔ)

(1)文件概念

(2)文件的邏輯結(jié)構(gòu)(順序文件、索引文件、索引順序文件)

(3)文件目錄

文件控制塊和索引節(jié)點;單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu);樹形目錄結(jié)構(gòu)。

(4)文件共享

(5)文件保護

2.磁盤存儲器的管理

(1)外存組織方式

連續(xù)組織方式;鏈接組織方式(FAT技術(shù)、NTFS技術(shù));索引組織方式。

(2)文件存儲空間的管理

空閑表法;空閑鏈表法;位示圖法;成組鏈接法。

(3)提高磁盤I/O速度的方法

(4)磁盤可靠性技術(shù)

(5)數(shù)據(jù)一致性控制

四、參考書目

《數(shù)據(jù)結(jié)構(gòu)》 機械工業(yè)出版社 2008年 戴敏

《計算機操作系統(tǒng)》(第四版)，湯小丹等編著, 西安電子科技大學(xué)出版社。

數(shù)據(jù)來源：天津理工大學(xué)2023考研初試自命題科目考試大綱