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

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

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

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

數(shù)據(jù)結構部分
一、緒論
1． 數(shù)據(jù)結構相關基本概念
2． 邏輯結構和物理結構
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． 樹的定義和基本術語
2． 二叉樹的定義、性質(zhì)，二叉鏈表存儲結構
3． 完全二叉樹的性質(zhì)
4． 二叉樹的深度優(yōu)先（先序、中序、后序）和廣度優(yōu)先（層序）遍歷算法和程序?qū)崿F(xiàn)
5． 樹的存儲結構
6． 樹、森林與二叉樹的轉(zhuǎn)換
7． 哈夫曼樹的定義、性質(zhì)、構造方法、哈夫曼樹的應用
五、圖
1． 圖的定義和術語
2． 圖的鄰接矩陣、鄰接表存儲結構
3． 圖的深度優(yōu)先搜索、廣度優(yōu)先搜索及其算法實現(xiàn)
4． 生成樹的定義，圖的最小生成樹定義與構造方法（不要求算法實現(xiàn)）
5． 拓撲排序
6． 單源最短路徑問題的求解
六、查找
1． 平均搜索長度（ASL）的定義
2． 順序表的查找算法、程序?qū)崿F(xiàn)和ASL分析
3． 二分查找法的算法描述、程序?qū)崿F(xiàn)和ASL分析
4． 索引順序表的查找（分塊查找）方法和和ASL分析
5． 二叉排序樹的定義、插入、刪除操作
6． 平衡二叉樹的定義、構造（掌握4種旋轉(zhuǎn)方法），計算等概率下查找成功的ASL和查找不成功的ASL
7． B-樹的定義、插入與刪除操作
8． 散列表的概念，幾種常用散列函數(shù)的構造方法
9． 散列表處理沖突的方法（線性探查法、二次探查法、再散列法、鏈地址法），計算等概率下查找成功的ASL和查找不成功的ASL
10．散列表負載因子（裝填因子）α的定義
七、排序（以下每種排序算法要求掌握排序過程和程序?qū)崿F(xiàn)）
1． 直接插入排序、希爾排序
2． 冒泡排序、快速排序
3． 簡單選擇排序、堆排序
4． 歸并排序
5． 基數(shù)排序（箱排序）
6． 以上各種排序算法的時間復雜度分析，各自的特征及其比較

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

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

天津理工大學

本文來源：http://www.lyhuahuisp.com/tianjinligongdaxue/cankaoshumu_461230.html