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

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

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

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

數據結構部分
一、緒論
1． 數據結構相關基本概念
2． 邏輯結構和物理結構
3． 算法效率的度量（O－表示法）
二、線性表、棧和隊列（以下各點要求掌握算法的程序實現）
1． 順序表的表示和基本操作的實現算法
2． 單鏈表、循環鏈表、雙向鏈表的表示和基本操作的實現算法
3． 棧的表示和基本操作的實現算法
4． 循環隊列、鏈隊列的表示和基本操作的實現算法
三、數組、遞歸
1． 數組的存儲方式
2． 特殊矩陣的壓縮存儲
3． 遞歸思想的特點
4． 遞歸算法和遞歸函數
四、樹和二叉樹
1． 樹的定義和基本術語
2． 二叉樹的定義、性質，二叉鏈表存儲結構
3． 完全二叉樹的性質
4． 二叉樹的深度優先（先序、中序、后序）和廣度優先（層序）遍歷算法和程序實現
5． 樹的存儲結構
6． 樹、森林與二叉樹的轉換
7． 哈夫曼樹的定義、性質、構造方法、哈夫曼樹的應用
五、圖
1． 圖的定義和術語
2． 圖的鄰接矩陣、鄰接表存儲結構
3． 圖的深度優先搜索、廣度優先搜索及其算法實現
4． 生成樹的定義，圖的最小生成樹定義與構造方法（不要求算法實現）
5． 拓撲排序
6． 單源最短路徑問題的求解
六、查找
1． 平均搜索長度（ASL）的定義
2． 順序表的查找算法、程序實現和ASL分析
3． 二分查找法的算法描述、程序實現和ASL分析
4． 索引順序表的查找（分塊查找）方法和和ASL分析
5． 二叉排序樹的定義、插入、刪除操作
6． 平衡二叉樹的定義、構造（掌握4種旋轉方法），計算等概率下查找成功的ASL和查找不成功的ASL
7． B-樹的定義、插入與刪除操作
8． 散列表的概念，幾種常用散列函數的構造方法
9． 散列表處理沖突的方法（線性探查法、二次探查法、再散列法、鏈地址法），計算等概率下查找成功的ASL和查找不成功的ASL
10．散列表負載因子（裝填因子）α的定義
七、排序（以下每種排序算法要求掌握排序過程和程序實現）
1． 直接插入排序、希爾排序
2． 冒泡排序、快速排序
3． 簡單選擇排序、堆排序
4． 歸并排序
5． 基數排序（箱排序）
6． 以上各種排序算法的時間復雜度分析，各自的特征及其比較

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

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

天津理工大學

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