2019年上海理工大學(xué)考研869《數(shù)據(jù)結(jié)構(gòu)及軟件工程》考試大綱

1、上海理工大學(xué)考研輔導(dǎo)：17600666009（同微信）上海理工大學(xué)碩士研究生入學(xué)《數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)結(jié)構(gòu)及軟件工程》考試大綱第一部分：數(shù)據(jù)結(jié)構(gòu)第一部分：數(shù)據(jù)結(jié)構(gòu)一、參考書目一、參考書目《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏等主編，清華大學(xué)出版社，2012年二、二、考試內(nèi)容要求考試內(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

2、、掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用。5、初步掌握文件組織方法和索引技術(shù)。三、考試內(nèi)容三、考試內(nèi)容1、數(shù)據(jù)結(jié)構(gòu)基本概念及簡(jiǎn)單的算法分析數(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)的語言3)數(shù)據(jù)結(jié)構(gòu)的抽象層次4)算法定義5)性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的后期測(cè)試；算法的事前估計(jì)；空間復(fù)雜度度量；時(shí)間復(fù)雜度度量；時(shí)間復(fù)雜度

3、的漸進(jìn)表示法；漸進(jìn)的空間復(fù)雜.2、數(shù)組數(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)循

4、環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題；多項(xiàng)式及其相加：多項(xiàng)式的類定義；多項(xiàng)式的加法3)雙向鏈表上海理工大學(xué)考研輔導(dǎo)：17600666009（同微信）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ì)分插入排序；鏈表插入排序

5、；希爾排序2)交換排序：起泡排序；快速排序3)選擇排序：直接選擇排序；錦標(biāo)賽排序；堆排序4)歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序5)基數(shù)排序：多關(guān)鍵碼排序；鏈?zhǔn)交鶖?shù)排序6)外排序：外排序的基本過程；k路平衡歸并；初始?xì)w并段的生成；最佳歸并樹1010、索引與散列結(jié)構(gòu)、索引與散列結(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)散列：詞典的抽

6、象數(shù)據(jù)類型；散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析第二部分：軟件工程第二部分：軟件工程一、參考書目一、參考書目張海藩，牟永敏著，《軟件工程導(dǎo)論》（第6版），清華大學(xué)出版社，2013年二、考試內(nèi)容范圍二、考試內(nèi)容范圍掌握軟件工程的基本概念、基本原理和基本方法；掌握可行性研究、需求分析、軟件設(shè)計(jì)、軟件測(cè)試、維護(hù)和演化、軟件過程和管理等方面的基礎(chǔ)知識(shí)，建立軟件開發(fā)的系統(tǒng)化和工程化的概念和質(zhì)量意識(shí)，能