2022年天津理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生考試科目數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)大綱 正文

一、考試方式
考試采用筆試形式，考試時(shí)間為180分鐘，試卷滿分為150分。

二、試卷結(jié)構(gòu)與分?jǐn)?shù)比重
數(shù)據(jù)結(jié)構(gòu)占80分，題型及分配比例：選擇題（25%）、綜合應(yīng)用題（75%）。
操作系統(tǒng)占70分，題型及分配比例：填空題（20%）、選擇題（20%）、簡述題（20%）、算法實(shí)現(xiàn)與綜合分析習(xí)題（40%）。

 三、考查的知識(shí)范圍
《數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)》入學(xué)考試總分150分，包括兩部分內(nèi)容：其中數(shù)據(jù)結(jié)構(gòu)考試主要涉及線性結(jié)構(gòu)、樹、圖、查找和排序中的典型數(shù)據(jù)結(jié)構(gòu)和算法，要能夠針對(duì)具體問題進(jìn)行分析，選擇正確的邏輯結(jié)構(gòu)、設(shè)計(jì)合理的存儲(chǔ)結(jié)構(gòu)、提出解決問題的方法或算法，并能對(duì)所選方法和算法的正確性、復(fù)雜性進(jìn)行分析，占80分；操作系統(tǒng)考試主要涉及基本概念、原理和功能，理解操作系統(tǒng)的整體運(yùn)行過程， 掌握操作系統(tǒng)進(jìn)程、內(nèi)存、文件和I/O管理的策略、算法、機(jī)制以及相互關(guān)系，能夠運(yù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－表示法）
二、線性表、棧和隊(duì)列（以下各點(diǎn)要求掌握算法的程序?qū)崿F(xiàn)）
1． 順序表的表示和基本操作的實(shí)現(xiàn)算法
2． 單鏈表、循環(huán)鏈表、雙向鏈表的表示和基本操作的實(shí)現(xiàn)算法
3． 棧的表示和基本操作的實(shí)現(xiàn)算法
4． 循環(huán)隊(duì)列、鏈隊(duì)列的表示和基本操作的實(shí)現(xiàn)算法
三、數(shù)組、遞歸
1． 數(shù)組的存儲(chǔ)方式
2． 特殊矩陣的壓縮存儲(chǔ)
3． 遞歸思想的特點(diǎn)
4． 遞歸算法和遞歸函數(shù)
四、樹和二叉樹
1． 樹的定義和基本術(shù)語
2． 二叉樹的定義、性質(zhì)，二叉鏈表存儲(chǔ)結(jié)構(gòu)
3． 完全二叉樹的性質(zhì)
4． 二叉樹的深度優(yōu)先（先序、中序、后序）和廣度優(yōu)先（層序）遍歷算法和程序?qū)崿F(xiàn)
5． 樹的存儲(chǔ)結(jié)構(gòu)
6． 樹、森林與二叉樹的轉(zhuǎn)換
7． 哈夫曼樹的定義、性質(zhì)、構(gòu)造方法、哈夫曼樹的應(yīng)用
五、圖
1． 圖的定義和術(shù)語
2． 圖的鄰接矩陣、鄰接表存儲(chǔ)結(jié)構(gòu)
3． 圖的深度優(yōu)先搜索、廣度優(yōu)先搜索及其算法實(shí)現(xiàn)
4． 生成樹的定義，圖的最小生成樹定義與構(gòu)造方法（不要求算法實(shí)現(xiàn)）
5． 拓?fù)渑判?br /> 6． 單源最短路徑問題的求解
六、查找
1． 平均搜索長度（ASL）的定義
2． 順序表的查找算法、程序?qū)崿F(xiàn)和ASL分析
3． 二分查找法的算法描述、程序?qū)崿F(xiàn)和ASL分析
4． 索引順序表的查找（分塊查找）方法和和ASL分析
5． 二叉排序樹的定義、插入、刪除操作
6． 平衡二叉樹的定義、構(gòu)造（掌握4種旋轉(zhuǎn)方法），計(jì)算等概率下查找成功的ASL和查找不成功的ASL
7． B-樹的定義、插入與刪除操作
8． 散列表的概念，幾種常用散列函數(shù)的構(gòu)造方法
9． 散列表處理沖突的方法（線性探查法、二次探查法、再散列法、鏈地址法），計(jì)算等概率下查找成功的ASL和查找不成功的ASL
10．散列表負(fù)載因子（裝填因子）α的定義
七、排序（以下每種排序算法要求掌握排序過程和程序?qū)崿F(xiàn)）
1． 直接插入排序、希爾排序
2． 冒泡排序、快速排序
3． 簡單選擇排序、堆排序
4． 歸并排序
5． 基數(shù)排序（箱排序）
6． 以上各種排序算法的時(shí)間復(fù)雜度分析，各自的特征及其比較

操作系統(tǒng)部分
一、操作系統(tǒng)概述
1.操作系統(tǒng)的概念、特征、功能和作用
2.操作系統(tǒng)的發(fā)展與分類
3.操作系統(tǒng)體系結(jié)構(gòu)
二、進(jìn)程管理
1.進(jìn)程與線程
(1)進(jìn)程概念
(2)進(jìn)程的狀態(tài)與轉(zhuǎn)換
(3)進(jìn)程控制
(4)進(jìn)程同步
(5)進(jìn)程通信
共享存儲(chǔ)系統(tǒng)；消息傳遞系統(tǒng)；管道通信。
(6)線程概念與線程實(shí)現(xiàn)方式
2.處理機(jī)調(diào)度
(1)調(diào)度的基本概念
(2)調(diào)度時(shí)機(jī)、切換與過程
(3)調(diào)度的基本準(zhǔn)則
(4)調(diào)度方式
(5)典型調(diào)度算法
先來先服務(wù)調(diào)度算法；短作業(yè)(短進(jìn)程、短線程)優(yōu)先調(diào)度算法；時(shí)間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級(jí)調(diào)度算法；
高響應(yīng)比優(yōu)先調(diào)度算法；多級(jí)反饋隊(duì)列調(diào)度算法。
3.同步與互斥
(1)進(jìn)程同步的基本概念
(2)實(shí)現(xiàn)臨界區(qū)互斥的基本方法
軟件實(shí)現(xiàn)方法；硬件實(shí)現(xiàn)方法。
(3)信號(hào)量機(jī)制
(4)管程機(jī)制
(5)經(jīng)典同步問題
生產(chǎn)者-消費(fèi)者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題；睡眠理發(fā)師問題。
4.死鎖
(1)死鎖的概念
(2)死鎖處理策略
(3)死鎖預(yù)防
(4)死鎖避免
系統(tǒng)安全狀態(tài)；銀行家算法。
(5)死鎖檢測和解除
三、存儲(chǔ)器管理
1.存儲(chǔ)器管理概念
(1)存儲(chǔ)器的層次結(jié)構(gòu)
(2)程序的裝入和鏈接
絕對(duì)裝入方式；可重定位裝入方式；動(dòng)態(tài)運(yùn)行時(shí)裝入方式。
靜態(tài)鏈接方式；裝入時(shí)動(dòng)態(tài)鏈接方式；運(yùn)行時(shí)動(dòng)態(tài)鏈接方式。
(3)交換技術(shù)
(4)連續(xù)分配存儲(chǔ)管理方式
單一連續(xù)分配；固定分區(qū)分配；動(dòng)態(tài)分區(qū)分配(基于順序搜索的動(dòng)態(tài)分區(qū)分配算法、基于索引的動(dòng)態(tài)分區(qū)分配算法)；動(dòng)態(tài)可重定位分區(qū)分配。
(5)非連續(xù)分配管理方式
分頁管理方式；分段管理方式；段頁式管理方式。
  2.虛擬內(nèi)存管理
(1)虛擬存儲(chǔ)器基本概念
(2)請(qǐng)求分頁存儲(chǔ)管理方式
(3)頁面置換算法
最佳置換算法OPT；先進(jìn)先出置換算法FIFO；最近最久未使用置換算法LRU；最少使用置換算法LFU；時(shí)鐘置換算法CLOCK；頁面緩沖算法PBA。
(4)頁面分配策略
(5)抖動(dòng)與工作集
(6)請(qǐng)求分段存儲(chǔ)管理方式
四、輸入輸出(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ū)動(dòng)程序
(7)設(shè)備無關(guān)性
2.I/O核心子系統(tǒng)
(1)緩沖區(qū)管理
(2)設(shè)備分配與回收
(3)假脫機(jī)技術(shù)(SPOOLing)
3.磁盤存儲(chǔ)器的性能和調(diào)度
(1)磁盤性能與結(jié)構(gòu)
(2)磁盤調(diào)度算法
先來先付服務(wù)FCFSl；最短尋道時(shí)間優(yōu)先DDTF；掃描算法SCAN (電梯調(diào)度算法)；循環(huán)掃描算法CSCAN；NStepSCAN和FSCAN調(diào)度算法。
五、文件管理
1.文件系統(tǒng)基礎(chǔ)
(1)文件概念
(2)文件的邏輯結(jié)構(gòu)（順序文件、索引文件、索引順序文件）
(3)文件目錄
文件控制塊和索引節(jié)點(diǎn)；單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)。
(4)文件共享
(5)文件保護(hù)
2.磁盤存儲(chǔ)器的管理
(1)外存組織方式
連續(xù)組織方式；鏈接組織方式（FAT技術(shù)、NTFS技術(shù)）；索引組織方式。
(2)文件存儲(chǔ)空間的管理
空閑表法；空閑鏈表法；位示圖法；成組鏈接法。
(3)提高磁盤I/O速度的方法
(4)磁盤可靠性技術(shù)
(5)數(shù)據(jù)一致性控制

四、參考書目
 《數(shù)據(jù)結(jié)構(gòu)》 機(jī)械工業(yè)出版社 2008年     戴敏
《計(jì)算機(jī)操作系統(tǒng)》(第四版)，湯小丹等編著, 西安電子科技大學(xué)出版社。

天津理工大學(xué)

本文來源：http://m.zgxindalu.cn/tianjinligongdaxue/cankaoshumu_461230.html