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

1、《數(shù)據(jù)結(jié)構(gòu)及計(jì)算機(jī)組成原理數(shù)據(jù)結(jié)構(gòu)及計(jì)算機(jī)組成原理》考試大綱和參考書(shū)目考試大綱和參考書(shū)目第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)參考教材參考教材：《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版），嚴(yán)蔚敏等主編，清華大學(xué)出版社，2012年第一章緒論明確數(shù)據(jù)結(jié)構(gòu)的定義、研究的內(nèi)容，掌握算法及算法分析的概念，了解抽象數(shù)據(jù)類(lèi)型的概念。第二章線性表掌握線性表的概念，兩種存儲(chǔ)結(jié)構(gòu)順序表和鏈表的表示和實(shí)現(xiàn)、掌握鏈表（單鏈表、單循環(huán)鏈表和雙向鏈表）上的查找、插入、刪除基本操作及能編寫(xiě)鏈表上的綜合操作

2、程序。第三章棧和隊(duì)列掌握棧的概念，掌握順序棧、鏈棧的進(jìn)棧、出棧操作程序。能利用棧寫(xiě)出表達(dá)式求值過(guò)程，能用棧讀寫(xiě)遞歸程序。掌握隊(duì)列的概念，掌握循環(huán)隊(duì)列、循環(huán)鏈隊(duì)列的入隊(duì)、出隊(duì)操作程序。第四章串掌握串的基本運(yùn)算的含義，掌握求子串位置的定位函數(shù)，理解KMP模式匹配算法和時(shí)間復(fù)雜度。第五章多維數(shù)組和廣義表掌握多維數(shù)組及特殊矩陣的地址公式，廣義表的運(yùn)算和存儲(chǔ)。了解廣義表的遞歸算法。第六章樹(shù)和二叉樹(shù)。掌握樹(shù)、二叉樹(shù)的定義、術(shù)語(yǔ)，二叉樹(shù)的性質(zhì)，掌握二

3、叉樹(shù)的遞歸和非遞歸遍歷算法，掌握中序線索二叉樹(shù)的概念和遍歷算法，掌握Haffman樹(shù)及其應(yīng)用，了解樹(shù)與二叉樹(shù)的關(guān)系，了解回溯法與樹(shù)的遍歷。第七章圖掌握?qǐng)D的定義、術(shù)語(yǔ)，掌握?qǐng)D的存儲(chǔ)，圖的遍歷算法，掌握最小生成樹(shù)、拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑概念，了解其算法。第九章查找掌握有序表的查找算法和查找的時(shí)間復(fù)雜度，掌握二叉排序樹(shù)的查找、插入和刪除算法，掌握平衡二叉樹(shù)和B樹(shù)的插入、刪除概念。掌握哈希表構(gòu)造、解決沖突的方法及哈希表的查找。第十章內(nèi)部排

4、序掌握直接插入排序、冒泡排序、簡(jiǎn)單選擇排序、快速排序、堆排序、歸并排序和希爾排序算法和時(shí)間復(fù)雜度，了解基數(shù)排序的概念。廣義表的概念廣義表的存儲(chǔ)廣義表的應(yīng)用舉例樹(shù)和二叉樹(shù)樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)：二叉樹(shù)的定義二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷線索二叉樹(shù)樹(shù)和森林：樹(shù)的存儲(chǔ)結(jié)構(gòu)靜態(tài)鏈表樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換樹(shù)的遍歷樹(shù)的應(yīng)用舉例：哈夫曼樹(shù)哈夫曼編碼回溯法與樹(shù)的遍歷圖圖的定義和基本術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣鄰接表十字鏈表鄰接多重表圖的遍歷：