|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
上海理工大學碩士研究生入學
《數據結構及操作系統》考試大綱
第一部分：數據結構
一、參考書目
《數據結構》（C 語言版），嚴蔚敏等主編，清華大學出版社，2012 年
二、 考試內容要求
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、樹與森林
1) 樹和森林的概念：樹的定義；樹的術語；樹的抽象數據類型
2) 二叉樹：二叉樹的定義；二叉樹的性質；二叉樹的抽象數據類型
3) 二叉樹的表示：數組表示；鏈表存儲表示
4) 二叉樹遍歷：中序遍歷；前序遍歷；后序遍歷；應用二叉樹遍歷的事例；
二 叉樹遍歷的游標類；不用棧的二叉樹中序遍歷算法
5) 線索化二叉樹：線索；中序線索化二叉樹；前序與后序的線索化
6) 堆：堆的定義；堆的建立；堆的插入與刪除
7) 樹與森林：樹的存儲表示；森林與二叉樹的轉換；樹的遍歷；森林的遍
歷
二叉樹的計數
8) 霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼編碼
7、集合與搜索
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) 散列：詞典的抽象數據類型；散列表與散列方法；散列函數；處理溢出
的閉散列方法；處理溢出的開散列方法；散列表分析
第二部分：操作系統
一、參考書目
湯小丹等，《計算機操作系統》（第四版），西安電子科技大學出版社，2014 年
二、考試內容范圍
要求考生重點掌握操作系統設計方法與實現技術，能夠運用所學的操作系統原
理、方法與技術分析問題和解決問題。
1、操作系統引論
操作系統的目標與作用；操作系統的發展與分類； 操作系統的基本特性與主要
功能。
2、進程管理
進程的基本概念； 進程控制；進程同步（進程同步的基本概念、 實現臨界區互
斥的基本方法、 信號量、經典同步問題）；進程通信（共享存儲系統、消息傳遞
系統、管道通信）；線程概念；線程的實現。
3、處理機調度
調度的基本概念；調度的基本準則；典型調度算法（先來先服務調度算法、短作
業（短進程、短線程）優先調度算法、時間片輪轉調度算法、優先級調度算法、
高響應比優先調度算法、多級反饋隊列調度算法） 。
4、死鎖
死鎖的基本概念；死鎖預防；死鎖避免（系統安全狀態、銀行家算法）；死鎖檢
測與解除。
5、存儲器管理
程序裝入與鏈接；連續分配管理方式； 非連續分配管理方式（基本分頁存儲管
理方式、基本分段存儲管理方式；段頁式存儲管理方式）； 虛擬存儲器的基本概
念；請求分頁存儲管理方式；請求分段存儲管理方式；頁面置換算法（最佳置換
算法（OPT）、最近最久未少使用置換算法（LRU）、時鐘置換算法（CLOCK））。
6、設備管理
I/O 系統；I/O 控制方式；緩沖管理；I/O 軟件；設備分配；磁盤存儲器的管理
（磁盤性能、磁盤調度、磁盤高速緩存）。
7、文件管理
文件與文件系統的基本概念；文件的邏輯結構（順序文件；索引文件；索引順序
文件）；外存分配方式（連續分配、鏈接分配、索引分配）；文件控制塊和索引節
點；目錄結構；文件存儲空間的管理方法；文件共享；文件保護。
三、試卷結構
基本知識測試占 50%，綜合應用測試占 50%。
命題著重考察考生對基本概念、基本知識和基本理論的掌握情況，以及對基本方
法的運用能力。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
