2014年848數據結構及操作系統(tǒng)考研大綱——上海理工大學光電學院
? 第一部分：數據結構
一、參考書目
數據結構(第二版)，嚴蔚敏主編，2006，清華大學出版社。
二、 考試內容要求
1、了解數據結構及其分類、數據結構與算法的密切關系。
2、熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構。
3、掌握設計算法的步驟和算法分析方法。
4、掌握數據結構在排序和查找等常用算法中的應用。
5、初步掌握文件組織方法和索引技術。
三、考試內容
1、 數據結構基本概念及簡單的算法分析
1)什么是數據結構
2) 抽象數據類型及面向對象概念：數據類型;數據抽象與抽象數據類型;面向對象的概念;用于描述數據結構的語言
3) 數據結構的抽象層次
4) 算法定義
5) 性能分析與度量：算法的性能標準;算法的后期測試;算法的事前估計;空間復雜度度量;時間復雜度度量;時間復雜度的漸進表示法;漸進的空間復雜.
2、 數組
1)作為抽象數據類型的數組：數組的定義和初始化;作為抽象數據類型的數組;數組的順序存儲方式
2)順序表：順序表的定義和特點;順序表的類定義;順序表的查找、插入和刪除;使用順序表的事例
3) 字符串：字符串的抽象數據類型;字符串操作的實現;字符串的模式匹配
3、鏈表
1) 單鏈表：單鏈表的結構;單鏈表的類定義;單鏈表中的插入與刪除;帶表頭結點的單鏈表;用模板定義的單鏈表類;單鏈表的游標類;靜態(tài)鏈表
2) 循環(huán)鏈表：循環(huán)鏈表的類定義;用循環(huán)鏈表解約瑟夫問題;多項式及其相加：多項式的類定義;多項式的加法
3) 雙向鏈表
4、棧和隊列
1) 棧：棧的抽象數據類型;棧的順序存儲表示;棧的鏈接存儲表示
2) 隊列 ：隊列的抽象數據類型;隊列的順序存儲表示;隊列的鏈接存儲表示;3) 隊列的應用舉例
4) 優(yōu)先級隊列：優(yōu)先級隊列的定義;優(yōu)先級隊列的存儲表示
5、遞歸
1) 遞歸的概念
2) 迷宮問題
3) 遞歸過程與遞歸工作棧
4) 利用棧實現的迷宮問題非遞歸解法
5) 廣義表：廣義表的概念;廣義表的表示及操作;廣義表存儲結構的實現;廣6) 義表的訪問算法;廣義表的遞歸算法
6、樹與森林
1) 樹和森林的概念：樹的定義;樹的術語;樹的抽象數據類型
2) 二叉樹：二叉樹的定義;二叉樹的性質;二叉樹的抽象數據類型
3) 二叉樹的表示：數組表示;鏈表存儲表示
4) 二叉樹遍歷：中序遍歷;前序遍歷;后序遍歷;應用二叉樹遍歷的事例;二 叉樹遍歷的游標類;不用棧的二叉樹中序遍歷算法
5) 線索化二叉樹：線索;中序線索化二叉樹;前序與后序的線索化
6) 堆：堆的定義;堆的建立;堆的插入與刪除
7) 樹與森林：樹的存儲表示;森林與二叉樹的轉換;樹的遍歷;森林的遍歷
二叉樹的計數
8) 霍夫曼樹：路徑長度;霍夫曼樹;霍夫曼編碼
7、集合與搜索
1) 集合及其表示：集合基本概念;以集合為基礎的抽象數據類型;用位向量實現集合抽象據類型;用有序鏈表實現集合的抽象數據類型
2) 等價類：等價關系與等價類;確定等價類的鏈表方法;并查集
3) 簡單的搜索結構：搜索的概念;靜態(tài)搜索結構;順序搜索;基于有序順序表的對分搜索
4) 二叉搜索樹：定義;二叉搜索樹上的搜索;二叉搜索樹的插入;二叉搜索樹的刪除;與二叉搜索樹相關的中序游標類
5) AVI樹：AVI樹的定義;平衡化旋轉;AVI樹的插入和刪除;AVI樹的高度
8、 圖
1) 圖的基本概念：圖的基本概念;圖的抽象數據類型
2) 圖的存儲表示：鄰接矩陣;鄰接表;鄰接多重表
3) 圖的遍歷與連通性：深度優(yōu)先搜索;廣度優(yōu)先搜索;連通分量;重連通分量
4) 最小生成樹：克魯斯卡爾算法;普里姆算法
5) 活動網絡：用頂點表示活動的網絡;用邊表示活動的網絡
9、排序
1) 插入排序：直接插入排序;對分插入排序;鏈表插入排序;希爾排序
2) 交換排序：起泡排序;快速排序
3) 選擇排序：直接選擇排序;錦標賽排序;堆排序
4) 歸并排序：歸并;迭代的歸并排序算法;遞歸的表歸并排序
5) 基數排序：多關鍵碼排序;鏈式基數排序
6) 外排序：外排序的基本過程;k路平衡歸并;初始歸并段的生成;最佳歸并樹
10、索引與散列結構
1) 靜態(tài)索引結構：線性索引;倒排表;m路靜態(tài)查找樹
2) 動態(tài)索引結構：動態(tài)的m路查找樹;b_樹;b_樹的插入;b_樹的刪除;b+樹
3) 散列：詞典的抽象數據類型;散列表與散列方法;散列函數;處理溢出的閉散列方法;處理溢出的開散列方法;散列表分析
第二部分：操作系統(tǒng)
一、參考書目
湯小丹等，《計算機操作系統(tǒng)》(第三版)，西安電子科技大學出版社，2007年
二、考試內容范圍
要求考生重點掌握操作系統(tǒng)設計方法與實現技術，能夠運用所學的操作系統(tǒng)原理、方法與技術分析問題和解決問題。
1、操作系統(tǒng)引論
操作系統(tǒng)的目標與作用;操作系統(tǒng)的發(fā)展與分類; 操作系統(tǒng)的基本特性與主要功能。
2、進程管理
進程的基本概念; 進程控制;進程同步(進程同步的基本概念、 實現臨界區(qū)互斥的基本方法、 信號量、經典同步問題);進程通信(共享存儲系統(tǒng)、消息傳遞系統(tǒng)、管道通信);線程概念;線程的實現。
3、處理機調度
調度的基本概念;調度的基本準則;典型調度算法(先來先服務調度算法、短作業(yè)(短進程、短線程)優(yōu)先調度算法、時間片輪轉調度算法、優(yōu)先級調度算法、高響應比優(yōu)先調度算法、多級反饋隊列調度算法) 。
4、死鎖
死鎖的基本概念;死鎖預防;死鎖避免(系統(tǒng)安全狀態(tài)、銀行家算法);死鎖檢測與解除。
5、存儲器管理
程序裝入與鏈接;連續(xù)分配管理方式; 非連續(xù)分配管理方式(基本分頁存儲管理方式、基本分段存儲管理方式;段頁式存儲管理方式); 虛擬存儲器的基本概念;請求分頁存儲管理方式;請求分段存儲管理方式;頁面置換算法(最佳置換算法(OPT)、最近最久未少使用置換算法(LRU)、時鐘置換算法(CLOCK))。
6、設備管理
I/O系統(tǒng);I/O 控制方式;緩沖管理;I/O軟件;設備分配;磁盤存儲器的管理(磁盤性能、磁盤調度、磁盤高速緩存)。
7、文件管理
文件與文件系統(tǒng)的基本概念;文件的邏輯結構(順序文件;索引文件;索引順序文件);外存分配方式(連續(xù)分配、鏈接分配、索引分配);文件控制塊和索引節(jié)點;目錄結構;文件存儲空間的管理方法;文件共享;文件保護。
三、試卷結構
基本知識測試占50%，綜合應用測試占50%。
命題著重考察考生對基本概念、基本知識和基本理論的掌握情況，以及對基本方法的運用能力。
相關推薦：?2014年上海理工大學光電信息與計算機工程學院考研大綱匯總
? ? ? ? ? ?2014年上海理工大學考研大綱匯總
? ? ? ? ? ?2014年招生簡章上海理工大學匯總
| 考研大綱匯總 | 考研英語大綱 | 考研政治大綱 | 考研數學大綱 | 考研專業(yè)課大綱 |