上海理工大學碩士研究生入學

《數據結構及操作系統》考試大綱

第一部分：數據結構

一、參考書目

數據結構（第二版），嚴蔚敏主編，2006，清華大學出版社。

二、 考試內容要求

1、了解數據結構及其分類、數據結構與算法的密切關系。

　　2、熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構。

　　3、掌握設計算法的步驟和算法分析方法。

　　4、掌握數據結構在排序和查找等常用算法中的應用。

5、初步掌握文件組織方法和索引技術。

三、考試內容

1、 數據結構基本概念及簡單的算法分析 

　　1)什么是數據結構

　　2) 抽象數據類型及面向對象概念：數據類型；數據抽象與抽象數據類型；面向對象的概念；用于描述數據結構的語言

　　3) 數據結構的抽象層次

　　4) 算法定義

　　5) 性能分析與度量：算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復雜.

2、 數組

　　1)作為抽象數據類型的數組：數組的定義和初始化；作為抽象數據類型的數組；數組的順序存儲方式

　　2)順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例

　　3) 字符串：字符串的抽象數據類型；字符串操作的實現；字符串的模式匹配

3、鏈表 

　　1) 單鏈表：單鏈表的結構；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結點的單鏈表；用模板定義的單鏈表類；單鏈表的游標類；靜態鏈表

　　2) 循環鏈表：循環鏈表的類定義；用循環鏈表解約瑟夫問題；多項式及其相加：多項式的類定義；多項式的加法

　　3) 雙向鏈表

4、棧和隊列 

　　1) 棧：棧的抽象數據類型；棧的順序存儲表示；棧的鏈接存儲表示

　　2) 隊列 ：隊列的抽象數據類型；隊列的順序存儲表示；隊列的鏈接存儲表示；3) 隊列的應用舉例

　　4) 優先級隊列：優先級隊列的定義；優先級隊列的存儲表示

5、遞歸 

　　1) 遞歸的概念

　　2) 迷宮問題

　　3) 遞歸過程與遞歸工作棧

　　4) 利用棧實現的迷宮問題非遞歸解法

　　5) 廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲結構的實現；廣6) 義表的訪問算法；廣義表的遞歸算法

6、樹與森林

　　www.xuecan.net

　　1) 樹和森林的概念：樹的定義；樹的術語；樹的抽象數據類型

　　2) 二叉樹：二叉樹的定義；二叉樹的性質；二叉樹的抽象數據類型

　　3) 二叉樹的表示：數組表示；鏈表存儲表示

　　4) 二叉樹遍歷：中序遍歷；前序遍歷；后序遍歷；應用二叉樹遍歷的事例；二 叉樹遍歷的游標類；不用棧的二叉樹中序遍歷算法

　　5) 線索化二叉樹：線索；中序線索化二叉樹；前序與后序的線索化

　　6) 堆：堆的定義；堆的建立；堆的插入與刪除

　　7) 樹與森林：樹的存儲表示；森林與二叉樹的轉換；樹的遍歷；森林的遍歷

　　二叉樹的計數

　　8) 霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼編碼

7、集合與搜索  www.xuecan.net

　　1) 集合及其表示：集合基本概念；以集合為基礎的抽象數據類型；用位向量實現集合抽象據類型；用有序鏈表實現集合的抽象數據類型

　　2) 等價類：等價關系與等價類；確定等價類的鏈表方法；并查集

　　3) 簡單的搜索結構：搜索的概念；靜態搜索結構；順序搜索；基于有序順序表的對分搜索

　　4) 二叉搜索樹：定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除；與二叉搜索樹相關的中序游標類

　　5) AVI樹：AVI樹的定義；平衡化旋轉；AVI樹的插入和刪除；AVI樹的高度

8、 圖 

　　1) 圖的基本概念：圖的基本概念；圖的抽象數據類型

　　2) 圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表

　　3) 圖的遍歷與連通性：深度優先搜索；廣度優先搜索；連通分量；重連通分量

　　4) 最小生成樹：克魯斯卡爾算法；普里姆算法

　　5) 活動網絡：用頂點表示活動的網絡；用邊表示活動的網絡

9、排序 

　　1) 插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序

　　2) 交換排序：起泡排序；快速排序

　　3) 選擇排序：直接選擇排序；錦標賽排序；堆排序

　　4) 歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序

　　5) 基數排序：多關鍵碼排序；鏈式基數排序

　　6) 外排序：外排序的基本過程；k路平衡歸并；初始歸并段的生成；最佳歸并樹

10、索引與散列結構

　　1) 靜態索引結構：線性索引；倒排表；m路靜態查找樹

　　2) 動態索引結構：動態的m路查找樹；b_樹；b_樹的插入；b_樹的刪除；b+樹

　　3) 散列：詞典的抽象數據類型；散列表與散列方法；散列函數；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析 

第二部分：操作系統

一、參考書目

湯小丹等，《計算機操作系統》（第三版），西安電子科技大學出版社，2007年

二、考試內容范圍

要求考生重點掌握操作系統設計方法與實現技術，能夠運用所學的操作系統原理、方法與技術分析問題和解決問題。

1、操作系統引論

操作系統的目標與作用；操作系統的發展與分類； 操作系統的基本特性與主要功能。

2、進程管理

進程的基本概念； 進程控制；進程同步（進程同步的基本概念、 實現臨界區互斥的基本方法、 信號量、經典同步問題）；進程通信（共享存儲系統、消息傳遞系統、管道通信）；線程概念；線程的實現。

3、處理機調度

調度的基本概念；調度的基本準則；典型調度算法（先來先服務調度算法、短作業（短進程、短線程）優先調度算法、時間片輪轉調度算法、優先級調度算法、高響應比優先調度算法、多級反饋隊列調度算法） 。 

4、死鎖

死鎖的基本概念；死鎖預防；死鎖避免（系統安全狀態、銀行家算法）；死鎖檢測與解除。

5、存儲器管理 

程序裝入與鏈接；連續分配管理方式； 非連續分配管理方式（基本分頁存儲管理方式、基本分段存儲管理方式；段頁式存儲管理方式）； 虛擬存儲器的基本概念；請求分頁存儲管理方式；請求分段存儲管理方式；頁面置換算法（最佳置換算法（OPT）、最近最久未少使用置換算法（LRU）、時鐘置換算法（CLOCK））。 

6、設備管理www.xuecan.net

 I/O系統；I/O 控制方式；緩沖管理；I/O軟件；設備分配；磁盤存儲器的管理（磁盤性能、磁盤調度、磁盤高速緩存）。

7、文件管理

文件與文件系統的基本概念；文件的邏輯結構（順序文件；索引文件；索引順序文件）；外存分配方式（連續分配、鏈接分配、索引分配）；文件控制塊和索引節點；目錄結構；文件存儲空間的管理方法；文件共享；文件保護。 

三、試卷結構

基本知識測試占50%，綜合應用測試占50%。

命題著重考察考生對基本概念、基本知識和基本理論的掌握情況，以及對基本方法的運用能力。