2021上海理工大學869數據結構及軟件工程研究生考試大綱 正文

上海理工大學碩士研究生入學
《數據結構及軟件工程》考試大綱
第一部分：數據結構
一、參考書目
《數據結構》（C語言版），嚴蔚敏等主編，清華大學出版社，2012年
二、 考試內容要求
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) 散列：詞典的抽象數據類型；散列表與散列方法；散列函數；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析 
　　
第二部分：軟件工程
一、參考書目
張海藩，牟永敏 著，《軟件工程導論》（第6版），清華大學出版社，2013年
 
二、考試內容范圍
掌握軟件工程的基本概念、基本原理和基本方法；掌握可行性研究、需求分析、軟件設計、軟件測試、維護和演化、軟件過程和管理等方面的基礎知識，建立軟件開發(fā)的系統(tǒng)化和工程化的概念和質量意識，能夠綜合利用軟件工程的方法與技術。
 
 1、軟件工程概述
1）軟件的本質特征和軟件開發(fā)的本質困難
2）軟件危機的產生及軟件工程的起源
3）軟件工程的定義
4）軟件工程學科的重要地位
 
2、軟件生命周期
 1）需求：需求的定義和類型、需求工程過程、需求規(guī)格說明、需求評審
設計：高層設計和詳細設計
2）測試：驗證與確認、單元測試、集成測試、系統(tǒng)測試和驗收測試、回歸測試和部署
3）維護和演化：演化的基本概念、演化和維護活動、程序理解和逆向工程、系統(tǒng)和過程的再工程過程
4）項目管理：人員組織和管理、項目計劃和跟蹤、軟件估算、風險控制、配置管理     
 
3、 軟件過程模型（一）
1）瀑布模型
2）演化模型及增量和迭代方法的本質特征
3）螺旋模型  
 
4、軟件過程模型（二）
 1）統(tǒng)一軟件開發(fā)過程模型
2）敏捷過程模型
 
5、 可行性分析
1）可行性研究的目標
2）可行性研究的過程和預期結果
3）經濟可行性的基本概念和評估方法
4）技術可行性的基本概念
5）合規(guī)可行性的基本概念
 
6、需求工程概述
1）軟件需求的根本挑戰(zhàn)
2）軟件需求的制品
3）需求工程過程——需求獲取、分析、規(guī)約和驗證
4）需求管理——需求跟蹤、優(yōu)先級和需求變更
5）領域模型和數據字典
 
7、結構化需求分析
1）建?；A：模型和視圖
2）系統(tǒng)流程圖
3）數據流圖
4）實體-聯(lián)系圖
5）狀態(tài)轉換圖 、IPO圖
 
8、面向對象需求分析（一）
1）UML建?；A
2）用例和用例圖
3）用例圖的基本符號與用例關系
4）用例描述
 
 
9、面向對象需求分析（二）
1）用活動圖、順序圖和通信圖描述用戶需求
2）領域的概念類與類圖
3）類之間的關系
4）概念模型的創(chuàng)建步驟與建模舉例
   
10、軟件設計基礎
1）總體設計和詳細設計的概念
2）軟件設計過程
3）軟件設計的基本原理
4）軟件設計的啟發(fā)式規(guī)則
5）非功能性需求和軟件設計
 
11、人機界面設計
     1）一般的人機界面設計原則
2）人機交互方式和界面風格
3）人機界面分析與建模
4）界面設計活動和設計原則
5）界面設計的實現工具
6）可用性和人機交互評價
 
12、軟件體系結構基礎
1）軟件體系結構視圖
2）軟件體系結構模式初步
3）基于構件的軟件開發(fā)和UML構件圖
4）使用UML部署圖描述部署模型
   
13、 結構化軟件設計
1）層次圖、HIPO圖和結構圖
2）程序流程圖、盒圖
3）判定表和判定樹
4）面向數據流的設計方法
   
14、面向對象軟件設計
1）需求分析的精化-實體類、邊界類和控制類
2）類圖和對象圖
3）CRC技術
4）類之間的關系
5）從分析類到射擊類
6）使用狀態(tài)機圖進行設計建模
7）使用活動圖、順序圖和通信圖進行設計建模
 
15、程序設計語言和編碼
1）程序設計語言
2）編程規(guī)范和程序設計風格
3）軟件設計質量度量
4）McCabe復雜度分析
    
16、 軟件測試、 軟件維護和演化
1）軟件測試的目的
2）軟件測試策略和模型
3）白盒測試
4）黑盒測試
5）軟件測試完成標準
6）軟件維護的概念
7）軟件維護過程
8）軟件演化和再工程技術
 
   
 

上海理工大學

本文來源：http://www.zhongzhouzhikong.com/shanghailigongdaxue/cankaoshumu_387411.html