2021上海理工大學(xué)848數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)研究生考試大綱 正文

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

上海理工大學(xué)

本文來源：http://www.scstrans.com/shanghailigongdaxue/cankaoshumu_387341.html