2021上海理工大學(xué)869數(shù)據(jù)結(jié)構(gòu)及軟件工程研究生考試大綱 正文

上海理工大學(xué)碩士研究生入學(xué)
《數(shù)據(jù)結(jié)構(gòu)及軟件工程》考試大綱
第一部分：數(shù)據(jù)結(jié)構(gòu)
一、參考書目
《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版），嚴(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í)際問(wèn)題要求來(lái)選擇數(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)基本概念及簡(jiǎn)單的算法分析
　　1)什么是數(shù)據(jù)結(jié)構(gòu)
　　2) 抽象數(shù)據(jù)類型及面向?qū)ο蟾拍睿簲?shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍睿挥糜诿枋鰯?shù)據(jù)結(jié)構(gòu)的語(yǔ)言
　　3) 數(shù)據(jù)結(jié)構(gòu)的抽象層次
　　4) 算法定義
　　5) 性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的后期測(cè)試；算法的事前估計(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ǎn)捂湵淼慕Y(jié)構(gòu)；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結(jié)點(diǎn)的單鏈表；用模板定義的單鏈表類；單鏈表的游標(biāo)類；靜態(tài)鏈表
　　2) 循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問(wè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) 迷宮問(wèn)題
　　3) 遞歸過(guò)程與遞歸工作棧
　　4) 利用棧實(shí)現(xiàn)的迷宮問(wèn)題非遞歸解法
　　5) 廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)；廣6) 義表的訪問(wèn)算法；廣義表的遞歸算法
　　
6、樹(shù)與森林
　　
　　1) 樹(shù)和森林的概念：樹(shù)的定義；樹(shù)的術(shù)語(yǔ)；樹(shù)的抽象數(shù)據(jù)類型
　　2) 二叉樹(shù)：二叉樹(shù)的定義；二叉樹(shù)的性質(zhì)；二叉樹(shù)的抽象數(shù)據(jù)類型
　　3) 二叉樹(shù)的表示：數(shù)組表示；鏈表存儲(chǔ)表示
　　4) 二叉樹(shù)遍歷：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹(shù)遍歷的事例；二 叉樹(shù)遍歷的游標(biāo)類；不用棧的二叉樹(shù)中序遍歷算法
　　5) 線索化二叉樹(shù)：線索；中序線索化二叉樹(shù)；前序與后序的線索化
　　6) 堆：堆的定義；堆的建立；堆的插入與刪除
　　7) 樹(shù)與森林：樹(shù)的存儲(chǔ)表示；森林與二叉樹(shù)的轉(zhuǎn)換；樹(shù)的遍歷；森林的遍歷
　　二叉樹(shù)的計(jì)數(shù)
　　8) 霍夫曼樹(shù)：路徑長(zhǎng)度；霍夫曼樹(shù)；霍夫曼編碼
　　
7、集合與搜索
　　
　　1) 集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實(shí)現(xiàn)集合抽象據(jù)類型；用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型
　　2) 等價(jià)類：等價(jià)關(guān)系與等價(jià)類；確定等價(jià)類的鏈表方法；并查集
　　3) 簡(jiǎn)單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的對(duì)分搜索
　　4) 二叉搜索樹(shù)：定義；二叉搜索樹(shù)上的搜索；二叉搜索樹(shù)的插入；二叉搜索樹(shù)的刪除；與二叉搜索樹(shù)相關(guān)的中序游標(biāo)類
　　5) AVI樹(shù)：AVI樹(shù)的定義；平衡化旋轉(zhuǎn)；AVI樹(shù)的插入和刪除；AVI樹(shù)的高度
　
8、 圖
　　
　　1) 圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型
　　2) 圖的存儲(chǔ)表示：鄰接矩陣；鄰接表；鄰接多重表
　　3) 圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；重連通分量
　　4) 最小生成樹(shù)：克魯斯卡爾算法；普里姆算法
　　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) 外排序：外排序的基本過(guò)程；k路平衡歸并；初始?xì)w并段的生成；最佳歸并樹(shù)
　　
10、索引與散列結(jié)構(gòu)
　　
　　1) 靜態(tài)索引結(jié)構(gòu)：線性索引；倒排表；m路靜態(tài)查找樹(shù)
　　2) 動(dòng)態(tài)索引結(jié)構(gòu)：動(dòng)態(tài)的m路查找樹(shù)；b_樹(shù)；b_樹(shù)的插入；b_樹(shù)的刪除；b+樹(shù)
　　3) 散列：詞典的抽象數(shù)據(jù)類型；散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開(kāi)散列方法；散列表分析 
　　
第二部分：軟件工程
一、參考書目
張海藩，牟永敏 著，《軟件工程導(dǎo)論》（第6版），清華大學(xué)出版社，2013年
 
二、考試內(nèi)容范圍
掌握軟件工程的基本概念、基本原理和基本方法；掌握可行性研究、需求分析、軟件設(shè)計(jì)、軟件測(cè)試、維護(hù)和演化、軟件過(guò)程和管理等方面的基礎(chǔ)知識(shí)，建立軟件開(kāi)發(fā)的系統(tǒng)化和工程化的概念和質(zhì)量意識(shí)，能夠綜合利用軟件工程的方法與技術(shù)。
 
 1、軟件工程概述
1）軟件的本質(zhì)特征和軟件開(kāi)發(fā)的本質(zhì)困難
2）軟件危機(jī)的產(chǎn)生及軟件工程的起源
3）軟件工程的定義
4）軟件工程學(xué)科的重要地位
 
2、軟件生命周期
 1）需求：需求的定義和類型、需求工程過(guò)程、需求規(guī)格說(shuō)明、需求評(píng)審
設(shè)計(jì)：高層設(shè)計(jì)和詳細(xì)設(shè)計(jì)
2）測(cè)試：驗(yàn)證與確認(rèn)、單元測(cè)試、集成測(cè)試、系統(tǒng)測(cè)試和驗(yàn)收測(cè)試、回歸測(cè)試和部署
3）維護(hù)和演化：演化的基本概念、演化和維護(hù)活動(dòng)、程序理解和逆向工程、系統(tǒng)和過(guò)程的再工程過(guò)程
4）項(xiàng)目管理：人員組織和管理、項(xiàng)目計(jì)劃和跟蹤、軟件估算、風(fēng)險(xiǎn)控制、配置管理     
 
3、 軟件過(guò)程模型（一）
1）瀑布模型
2）演化模型及增量和迭代方法的本質(zhì)特征
3）螺旋模型  
 
4、軟件過(guò)程模型（二）
 1）統(tǒng)一軟件開(kāi)發(fā)過(guò)程模型
2）敏捷過(guò)程模型
 
5、 可行性分析
1）可行性研究的目標(biāo)
2）可行性研究的過(guò)程和預(yù)期結(jié)果
3）經(jīng)濟(jì)可行性的基本概念和評(píng)估方法
4）技術(shù)可行性的基本概念
5）合規(guī)可行性的基本概念
 
6、需求工程概述
1）軟件需求的根本挑戰(zhàn)
2）軟件需求的制品
3）需求工程過(guò)程——需求獲取、分析、規(guī)約和驗(yàn)證
4）需求管理——需求跟蹤、優(yōu)先級(jí)和需求變更
5）領(lǐng)域模型和數(shù)據(jù)字典
 
7、結(jié)構(gòu)化需求分析
1）建模基礎(chǔ)：模型和視圖
2）系統(tǒng)流程圖
3）數(shù)據(jù)流圖
4）實(shí)體-聯(lián)系圖
5）狀態(tài)轉(zhuǎn)換圖 、IPO圖
 
8、面向?qū)ο笮枨蠓治觯ㄒ唬?/strong>
1）UML建?；A(chǔ)
2）用例和用例圖
3）用例圖的基本符號(hào)與用例關(guān)系
4）用例描述
 
 
9、面向?qū)ο笮枨蠓治觯ǘ?/strong>
1）用活動(dòng)圖、順序圖和通信圖描述用戶需求
2）領(lǐng)域的概念類與類圖
3）類之間的關(guān)系
4）概念模型的創(chuàng)建步驟與建模舉例
   
10、軟件設(shè)計(jì)基礎(chǔ)
1）總體設(shè)計(jì)和詳細(xì)設(shè)計(jì)的概念
2）軟件設(shè)計(jì)過(guò)程
3）軟件設(shè)計(jì)的基本原理
4）軟件設(shè)計(jì)的啟發(fā)式規(guī)則
5）非功能性需求和軟件設(shè)計(jì)
 
11、人機(jī)界面設(shè)計(jì)
     1）一般的人機(jī)界面設(shè)計(jì)原則
2）人機(jī)交互方式和界面風(fēng)格
3）人機(jī)界面分析與建模
4）界面設(shè)計(jì)活動(dòng)和設(shè)計(jì)原則
5）界面設(shè)計(jì)的實(shí)現(xiàn)工具
6）可用性和人機(jī)交互評(píng)價(jià)
 
12、軟件體系結(jié)構(gòu)基礎(chǔ)
1）軟件體系結(jié)構(gòu)視圖
2）軟件體系結(jié)構(gòu)模式初步
3）基于構(gòu)件的軟件開(kāi)發(fā)和UML構(gòu)件圖
4）使用UML部署圖描述部署模型
   
13、 結(jié)構(gòu)化軟件設(shè)計(jì)
1）層次圖、HIPO圖和結(jié)構(gòu)圖
2）程序流程圖、盒圖
3）判定表和判定樹(shù)
4）面向數(shù)據(jù)流的設(shè)計(jì)方法
   
14、面向?qū)ο筌浖O(shè)計(jì)
1）需求分析的精化-實(shí)體類、邊界類和控制類
2）類圖和對(duì)象圖
3）CRC技術(shù)
4）類之間的關(guān)系
5）從分析類到射擊類
6）使用狀態(tài)機(jī)圖進(jìn)行設(shè)計(jì)建模
7）使用活動(dòng)圖、順序圖和通信圖進(jìn)行設(shè)計(jì)建模
 
15、程序設(shè)計(jì)語(yǔ)言和編碼
1）程序設(shè)計(jì)語(yǔ)言
2）編程規(guī)范和程序設(shè)計(jì)風(fēng)格
3）軟件設(shè)計(jì)質(zhì)量度量
4）McCabe復(fù)雜度分析
    
16、 軟件測(cè)試、 軟件維護(hù)和演化
1）軟件測(cè)試的目的
2）軟件測(cè)試策略和模型
3）白盒測(cè)試
4）黑盒測(cè)試
5）軟件測(cè)試完成標(biāo)準(zhǔn)
6）軟件維護(hù)的概念
7）軟件維護(hù)過(guò)程
8）軟件演化和再工程技術(shù)
 
   
 

上海理工大學(xué)

添加上海理工大學(xué)學(xué)姐微信，或微信搜索公眾號(hào)“考研派小站”，關(guān)注[考研派小站]微信公眾號(hào)，在考研派小站微信號(hào)輸入[上海理工大學(xué)考研分?jǐn)?shù)線、上海理工大學(xué)報(bào)錄比、上海理工大學(xué)考研群、上海理工大學(xué)學(xué)姐微信、上海理工大學(xué)考研真題、上海理工大學(xué)專業(yè)目錄、上海理工大學(xué)排名、上海理工大學(xué)保研、上海理工大學(xué)公眾號(hào)、上海理工大學(xué)研究生招生）]即可在手機(jī)上查看相對(duì)應(yīng)上海理工大學(xué)考研信息或資源。

本文來(lái)源：http://m.zhangjiajieline.cn/shanghailigongdaxue/cankaoshumu_387411.html