2011年上海理工大學(xué)數(shù)據(jù)結(jié)構(gòu)及計算機組成原理考研大綱_跨考網(wǎng)

《數(shù)據(jù)結(jié)構(gòu)及計算機組成原理》考試大綱和參考書目

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

　　第一章 緒論

　　明確數(shù)據(jù)結(jié)構(gòu)的定義、研究的內(nèi)容，掌握算法及算法分析的概念，了解抽象數(shù)據(jù)類型的概念。

　　第二章 線性表

　　掌握線性表的概念，兩種存儲結(jié)構(gòu)順序表和鏈表的表示和實現(xiàn)、掌握鏈表（單鏈表、單循環(huán)鏈表和雙向鏈表）上的查找、插入、刪除基本操作及能編寫鏈表上的綜合操作程序。

　　第三章 棧和隊列

　　掌握棧的概念，掌握順序棧、鏈棧的進棧、出棧操作程序。能利用棧寫出表達式求值過程，能用棧讀寫遞歸程序。

　　掌握隊列的概念，掌握循環(huán)隊列、循環(huán)鏈隊列的入隊、出隊操作程序。

　　第四章 串

　　掌握串的基本運算的含義，掌握求子串位置的定位函數(shù)，理解KMP模式匹配算法和時間復(fù)雜度。

　　第五章 多維數(shù)組和廣義表

　　掌握多維數(shù)組及特殊矩陣的地址公式，廣義表的運算和存儲。了解廣義表的遞歸算法。

　　第六章 樹和二叉樹。

　　掌握樹、二叉樹的定義、術(shù)語，二叉樹的性質(zhì)，掌握二叉樹的遞歸和非遞歸遍歷算法，掌握中序線索二叉樹的概念和遍歷算法，掌握Haffman樹及其應(yīng)用，了解樹與二叉樹的關(guān)系，了解回溯法與樹的遍歷。

　　第七章 圖

　　掌握圖的定義、術(shù)語，掌握圖的存儲，圖的遍歷算法，掌握最小生成樹、拓撲排序、關(guān)鍵路徑、最短路徑概念，了解其算法。

　　第九章 查找

　　掌握有序表的查找算法和查找的時間復(fù)雜度，掌握二叉排序樹的查找、插入和刪除算法，掌握平衡二叉樹和B-樹的插入、刪除概念。

　　掌握哈希表構(gòu)造、解決沖突的方法及哈希表的查找。

　　第十章 內(nèi)部排序

　　掌握直接插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序和希爾排序算法和時間復(fù)雜度，了解基數(shù)排序的概念。

　　專業(yè)課《數(shù)據(jù)結(jié)構(gòu)》考試大綱和參考書目

　　參考教材:《數(shù)據(jù)結(jié)構(gòu)·C語言版》 , 嚴蔚敏主編 , 清華大學(xué)出版社

　　參考用書:《數(shù)據(jù)結(jié)構(gòu)習(xí)題詳解》, 李春葆編著, 清華大學(xué)出版社

　　課程內(nèi)容（無標記章節(jié)一般了解、不考，打*號標記章節(jié)要求掌握，打**號標記章節(jié)要求重點掌握）

　　緒論

　　數(shù)據(jù)結(jié)構(gòu)定義

　　基本概念和術(shù)語

　　*算法描述和算法分析

　　抽象數(shù)據(jù)類型的表示和實現(xiàn)

　　線性表

　　線性表的基本概念

　　線性表順序表示和實現(xiàn)

　　線性表的鏈式表示和實現(xiàn)：

　　**線性鏈表

　　**循環(huán)鏈表

　　*雙向鏈表

　　順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)的比較

　　**線性表的應(yīng)用舉例

　　棧和隊列

　　*抽象數(shù)據(jù)類型棧的定義

　　*棧的表示和實現(xiàn)

　　棧的應(yīng)用舉例：

　　迷宮求解

　　**表達式求值

　　**棧與遞歸的實現(xiàn)

　　*抽象數(shù)據(jù)類型隊列的定義

　　*鏈隊列—隊列的鏈式表示和實現(xiàn)

　　**循環(huán)隊列—隊列的順序表示和實現(xiàn)

　　串

　　串類型的定義

　　串的表示和實現(xiàn)

　　**串的模式匹配算法

　　串的應(yīng)用舉例

　　數(shù)組和廣義表

　　數(shù)組的定義

　　*數(shù)組的順序表示和實現(xiàn)

　　*矩陣的壓縮存儲：

　　特殊矩陣

　　稀疏矩陣

　　*廣義表的概念

　　*廣義表的存儲

　　廣義表的應(yīng)用舉例

　　樹和二叉樹

　　樹的定義和基本術(shù)語

　　*二叉樹：

　　二叉樹的定義

　　二叉樹的性質(zhì)

　　二叉樹的存儲結(jié)構(gòu)

　　**二叉樹的遍歷

　　**線索二叉樹

　　樹和森林：

　　樹的存儲結(jié)構(gòu)

　　靜態(tài)鏈表

　　樹、森林和二叉樹的轉(zhuǎn)換

　　樹的遍歷

　　*樹的應(yīng)用舉例：

　　哈夫曼樹

　　哈夫曼編碼

　　回溯法與樹的遍歷

　　圖

　　*圖的定義和基本術(shù)語

　　圖的存儲結(jié)構(gòu)：

　　**鄰接矩陣

　　**鄰接表

　　十字鏈表

　　鄰接多重表

　　**圖的遍歷：

　　深度優(yōu)先搜索遍歷

　　廣度優(yōu)先搜索遍歷

　　*最小生成樹：

　　生成樹和最小生成樹

　　普里姆算法

　　克魯斯卡爾算法

　　有向無環(huán)圖及應(yīng)用：

　　*拓撲排序

　　關(guān)鍵路徑

　　最短路徑

　　查找

　　查找基本概念

　　順序表的查找：

　　順序查找

　　**有序表的查找

　　分塊查找