以下是泰安中公考研小編整理的2019年上海理工大學869《數據結構及軟件工程》考研大綱（下載版），以供各位考生參考。
一、參考書目
《數據結構》(C語言版)，嚴蔚敏等主編，清華大學出版社，2012年
二、 考試內容要求
1、瞭解數據結構及其分類、數據結構與算法的密切關係。
2、熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構。
3、掌握設計算法的步驟和算法分析方法。
4、掌握數據結構在排序和查找等常用算法中的應用。
5、初步掌握文件組織方法和索引技術。
三、考試內容
1、 數據結構基本概念及簡單的算法分析
1)什麼是數據結構
2) 抽象數據類型及面向對象概念：數據類型;數據抽象與抽象數據類型;面向對象的概念;用於描述數據結構的語言
3) 數據結構的抽象層次
4) 算法定義
5) 性能分析與度量：算法的性能標準;算法的後期測試;算法的事前估計;空間複雜度度量;時間複雜度度量;時間複雜度的漸進表示法;漸進的空間複雜.
2、 數組
1)作為抽象數據類型的數組：數組的定義和初始化;作為抽象數據類型的數組;數組的順序存儲方式
2)順序表：順序表的定義和特點;順序表的類定義;順序表的查找、插入和刪除;使用順序表的事例
3) 字符串：字符串的抽象數據類型;字符串操作的實現;字符串的模式匹配
3、鏈表
1) 單鏈表：單鏈表的結構;單鏈表的類定義;單鏈表中的插入與刪除;帶表頭結點的單鏈表;用模板定義的單鏈表類;單鏈表的遊標類;靜態鏈表
2) 循環鏈表：循環鏈表的類定義;用循環鏈表解約瑟夫問題;多項式及其相加：多項式的類定義;多項式的加法
3) 雙向鏈表
4、棧和隊列
1) 棧：棧的抽象數據類型;棧的順序存儲表示;棧的鏈接存儲表示
2) 隊列 ：隊列的抽象數據類型;隊列的順序存儲表示;隊列的鏈接存儲表示;3) 隊列的應用舉例
4) 優先級隊列：優先級隊列的定義;優先級隊列的存儲表示
5、遞歸
1) 遞歸的概念
2) 迷宮問題
3) 遞歸過程與遞歸工作棧
4) 利用棧實現的迷宮問題非遞歸解法
5) 廣義表：廣義表的概念;廣義表的表示及操作;廣義表存儲結構的實現;廣6) 義表的訪問算法;廣義表的遞歸算法
6、樹與森林
1) 樹和森林的概念：樹的定義;樹的術語;樹的抽象數據類型
2) 二叉樹：二叉樹的定義;二叉樹的性質;二叉樹的抽象數據類型
3) 二叉樹的表示：數組表示;鏈表存儲表示
4) 二叉樹遍歷：中序遍歷;前序遍歷;後序遍歷;應用二叉樹遍歷的事例;二 叉樹遍歷的遊標類;不用棧的二叉樹中序遍歷算法
5) 線索化二叉樹：線索;中序線索化二叉樹;前序與後序的線索化
6) 堆：堆的定義;堆的建立;堆的插入與刪除
7) 樹與森林：樹的存儲表示;森林與二叉樹的轉換;樹的遍歷;森林的遍歷
二叉樹的計數
8) 霍夫曼樹：路徑長度;霍夫曼樹;霍夫曼編碼
7、集合與搜索
1) 集合及其表示：集合基本概念;以集合為基礎的抽象數據類型;用位向量實現集合抽象據類型;用有序鏈表實現集合的抽象數據類型
2) 等價類：等價關係與等價類;確定等價類的鏈表方法;並查集
3) 簡單的搜索結構：搜索的概念;靜態搜索結構;順序搜索;基於有序順序表的對分搜索
4) 二叉搜索樹：定義;二叉搜索樹上的搜索;二叉搜索樹的插入;二叉搜索樹的刪除;與二叉搜索樹相關的中序遊標類
5) AVI樹：AVI樹的定義;平衡化旋轉;AVI樹的插入和刪除;AVI樹的高度
8、 圖
1) 圖的基本概念：圖的基本概念;圖的抽象數據類型
2) 圖的存儲表示：鄰接矩陣;鄰接表;鄰接多重表
閱讀更多 泰安中公考研 的文章
