《數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)》考試大綱

學習頻道    來源: 上海理工大學      2024-07-20         

本站非官方網(wǎng)站,信息完全免費,僅供參考,不收取任何費用,請以官網(wǎng)公布為準!

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

《數(shù)據(jù)結(jié)構(gòu)及操作系統(tǒng)》考試大綱

第一部分:數(shù)據(jù)結(jié)構(gòu)

一、參考書目

數(shù)據(jù)結(jié)構(gòu)(第二版),嚴蔚敏主編,2006,清華大學出版社。

二、 考試內(nèi)容要求

1、了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系。

  2、熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作,學會根據(jù)實際問題要求來選擇數(shù)據(jù)結(jié)構(gòu)。

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

  4、掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應用。

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) 性能分析與度量:算法的性能標準;算法的后期測試;算法的事前估計;空間復雜度度量;時間復雜度度量;時間復雜度的漸進表示法;漸進的空間復雜.

2、 數(shù)組

  1)作為抽象數(shù)據(jù)類型的數(shù)組:數(shù)組的定義和初始化;作為抽象數(shù)據(jù)類型的數(shù)組;數(shù)組的順序存儲方式

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

  3) 字符串:字符串的抽象數(shù)據(jù)類型;字符串操作的實現(xiàn);字符串的模式匹配

  

3、鏈表 

  

  1) 單鏈表:單鏈表的結(jié)構(gòu);單鏈表的類定義;單鏈表中的插入與刪除;帶表頭結(jié)點的單鏈表;用模板定義的單鏈表類;單鏈表的游標類;靜態(tài)鏈表

  2) 循環(huán)鏈表:循環(huán)鏈表的類定義;用循環(huán)鏈表解約瑟夫問題;多項式及其相加:多項式的類定義;多項式的加法

  3) 雙向鏈表

  

4、棧和隊列 

  1) 棧:棧的抽象數(shù)據(jù)類型;棧的順序存儲表示;棧的鏈接存儲表示

  2) 隊列 :隊列的抽象數(shù)據(jù)類型;隊列的順序存儲表示;隊列的鏈接存儲表示;3) 隊列的應用舉例

  4) 優(yōu)先級隊列:優(yōu)先級隊列的定義;優(yōu)先級隊列的存儲表示

  

5、遞歸 

  

  1) 遞歸的概念

  2) 迷宮問題

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

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

  5) 廣義表:廣義表的概念;廣義表的表示及操作;廣義表存儲結(jié)構(gòu)的實現(xiàn);廣6) 義表的訪問算法;廣義表的遞歸算法

  

6、樹與森林

  www.xuecan.net

  1) 樹和森林的概念:樹的定義;樹的術(shù)語;樹的抽象數(shù)據(jù)類型

  2) 二叉樹:二叉樹的定義;二叉樹的性質(zhì);二叉樹的抽象數(shù)據(jù)類型

  3) 二叉樹的表示:數(shù)組表示;鏈表存儲表示

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

  5) 線索化二叉樹:線索;中序線索化二叉樹;前序與后序的線索化

  6) 堆:堆的定義;堆的建立;堆的插入與刪除

  7) 樹與森林:樹的存儲表示;森林與二叉樹的轉(zhuǎn)換;樹的遍歷;森林的遍歷

  二叉樹的計數(shù)

  8) 霍夫曼樹:路徑長度;霍夫曼樹;霍夫曼編碼

  

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

  

  1) 集合及其表示:集合基本概念;以集合為基礎的抽象數(shù)據(jù)類型;用位向量實現(xiàn)集合抽象據(jù)類型;用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型

  2) 等價類:等價關(guān)系與等價類;確定等價類的鏈表方法;并查集

  3) 簡單的搜索結(jié)構(gòu):搜索的概念;靜態(tài)搜索結(jié)構(gòu);順序搜索;基于有序順序表的對分搜索

  4) 二叉搜索樹:定義;二叉搜索樹上的搜索;二叉搜索樹的插入;二叉搜索樹的刪除;與二叉搜索樹相關(guān)的中序游標類

  5) AVI樹:AVI樹的定義;平衡化旋轉(zhuǎn);AVI樹的插入和刪除;AVI樹的高度

 

8、 圖 

  

  1) 圖的基本概念:圖的基本概念;圖的抽象數(shù)據(jù)類型

  2) 圖的存儲表示:鄰接矩陣;鄰接表;鄰接多重表

  3) 圖的遍歷與連通性:深度優(yōu)先搜索;廣度優(yōu)先搜索;連通分量;重連通分量

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

  5) 活動網(wǎng)絡:用頂點表示活動的網(wǎng)絡;用邊表示活動的網(wǎng)絡

9、排序 

  1) 插入排序:直接插入排序;對分插入排序;鏈表插入排序;希爾排序

  2) 交換排序:起泡排序;快速排序

  3) 選擇排序:直接選擇排序;錦標賽排序;堆排序

  4) 歸并排序:歸并;迭代的歸并排序算法;遞歸的表歸并排序

  5) 基數(shù)排序:多關(guān)鍵碼排序;鏈式基數(shù)排序

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

10、索引與散列結(jié)構(gòu)

  

  1) 靜態(tài)索引結(jié)構(gòu):線性索引;倒排表;m路靜態(tài)查找樹

  2) 動態(tài)索引結(jié)構(gòu):動態(tài)的m路查找樹;b_樹;b_樹的插入;b_樹的刪除;b+樹

  3) 散列:詞典的抽象數(shù)據(jù)類型;散列表與散列方法;散列函數(shù);處理溢出的閉散列方法;處理溢出的開散列方法;散列表分析 

  

第二部分:操作系統(tǒng)

一、參考書目

湯小丹等,《計算機操作系統(tǒng)》(第三版),西安電子科技大學出版社,2007年


二、考試內(nèi)容范圍

要求考生重點掌握操作系統(tǒng)設計方法與實現(xiàn)技術(shù),能夠運用所學的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題。


1、操作系統(tǒng)引論

操作系統(tǒng)的目標與作用;操作系統(tǒng)的發(fā)展與分類; 操作系統(tǒng)的基本特性與主要功能。

2、進程管理

進程的基本概念; 進程控制;進程同步(進程同步的基本概念、 實現(xiàn)臨界區(qū)互斥的基本方法、 信號量、經(jīng)典同步問題);進程通信(共享存儲系統(tǒng)、消息傳遞系統(tǒng)、管道通信);線程概念;線程的實現(xiàn)。

3、處理機調(diào)度

調(diào)度的基本概念;調(diào)度的基本準則;典型調(diào)度算法(先來先服務調(diào)度算法、短作業(yè)(短進程、短線程)優(yōu)先調(diào)度算法、時間片輪轉(zhuǎn)調(diào)度算法、優(yōu)先級調(diào)度算法、高響應比優(yōu)先調(diào)度算法、多級反饋隊列調(diào)度算法) 。 

4、死鎖

死鎖的基本概念;死鎖預防;死鎖避免(系統(tǒng)安全狀態(tài)、銀行家算法);死鎖檢測與解除。

5、存儲器管理 

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

6、設備管理www.xuecan.net

 I/O系統(tǒng);I/O 控制方式;緩沖管理;I/O軟件;設備分配;磁盤存儲器的管理(磁盤性能、磁盤調(diào)度、磁盤高速緩存)。

7、文件管理

文件與文件系統(tǒng)的基本概念;文件的邏輯結(jié)構(gòu)(順序文件;索引文件;索引順序文件);外存分配方式(連續(xù)分配、鏈接分配、索引分配);文件控制塊和索引節(jié)點;目錄結(jié)構(gòu);文件存儲空間的管理方法;文件共享;文件保護。 

三、試卷結(jié)構(gòu)

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

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

陽光文庫  http://m.e-deep.com.cn/wenku/
陽光考試網(wǎng)    考試資訊分享    m.yggk.net             [責任編輯:陽光學習網(wǎng)]
陽光考試網(wǎng)手機版 |   學習頻道 |   學習專欄 |   大學排行榜 |   高考查分系統(tǒng) |   高考志愿填報 |   專題列表 |   教務管理系統(tǒng) |   高考錄取查詢

  陽光文庫   免費學習門戶 備案號:閩ICP備11025842號-3 網(wǎng)站地圖

本站所有資料完全免費,不收取任何費用,僅供學習和研究使用,版權(quán)和著作權(quán)歸原作者所有

Copyright 2025 陽光學習網(wǎng), All Rights Reserved.