考綱分析與應(yīng)試策略 一、考試簡介 001 二、考試方式 001 三、考試大綱解讀 002 四、應(yīng)試經(jīng)驗(yàn)與答題技巧 003 五、復(fù)習(xí)策略 004 第 一章　緒論 第 一節(jié)　數(shù)據(jù)結(jié)構(gòu)與算法的基本概念 006 考點(diǎn)1　數(shù)據(jù)結(jié)構(gòu)的基本概念 006 考點(diǎn)2　算法的基本概念 007 第二節(jié)　算法的時(shí)間復(fù)雜度與空間復(fù)雜度 008 考點(diǎn)3　時(shí)間復(fù)雜度 008 考點(diǎn)4　空間復(fù)雜度 010 過關(guān)練習(xí) 010 單項(xiàng)選擇題 010 答案與解析 012 第二章　線性表 第 一節(jié)　線性表的順序表示 015 考點(diǎn)1　線性表的定義和性質(zhì) 015 考點(diǎn)2　順序表的性質(zhì)和操作 016 第二節(jié)　線性表的鏈?zhǔn)奖硎?016 考點(diǎn)3　單鏈表的性質(zhì)和操作 016 考點(diǎn)4　雙向鏈表的性質(zhì)和操作 018 考點(diǎn)5　循環(huán)鏈表與靜態(tài)鏈表 019 考點(diǎn)6　順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)的比較 020 過關(guān)練習(xí) 020 單項(xiàng)選擇題 020 綜合應(yīng)用題 022 答案與解析 027 第三章　棧、隊(duì)列和數(shù)組 第 一節(jié)　棧 048 考點(diǎn)1　棧的基本概念 048 考點(diǎn)2　棧的順序存儲(chǔ) 051 考點(diǎn)3　棧的鏈?zhǔn)酱鎯?chǔ) 052 考點(diǎn)4　棧的應(yīng)用 052 第二節(jié)　隊(duì)列 054 考點(diǎn)5　隊(duì)列的基本概念 054 考點(diǎn)6　隊(duì)列的順序存儲(chǔ) 055 考點(diǎn)7　隊(duì)列的鏈?zhǔn)酱鎯?chǔ) 058 考點(diǎn)8　隊(duì)列的應(yīng)用 058 第三節(jié)　數(shù)組 059 考點(diǎn)9　多維數(shù)組的存儲(chǔ) 059 考點(diǎn)10　特殊矩陣的壓縮存儲(chǔ) 060 過關(guān)練習(xí) 061 單項(xiàng)選擇題 061 綜合應(yīng)用題 065 答案與解析 066 第四章　樹形結(jié)構(gòu) 第 一節(jié)　樹 077 考點(diǎn)1　樹的基本概念和性質(zhì) 077 考點(diǎn)2　樹的存儲(chǔ)結(jié)構(gòu) 079 第二節(jié)　二叉樹 079 考點(diǎn)3　二叉樹的定義和性質(zhì) 079 考點(diǎn)4　特殊的二叉樹 081 第三節(jié)　二叉樹的存儲(chǔ)與遍歷 083 考點(diǎn)5　二叉樹的鏈?zhǔn)酱鎯?chǔ) 083 考點(diǎn)6　二叉樹的順序存儲(chǔ) 083 考點(diǎn)7　二叉樹的遍歷 084 考點(diǎn)8　線索二叉樹 086 第四節(jié)　森林 088 考點(diǎn)9　樹、森林與二叉樹的轉(zhuǎn)換 088 考點(diǎn)10　樹與森林的遍歷 090 第五節(jié)　樹形結(jié)構(gòu)的應(yīng)用 091 考點(diǎn)11　哈夫曼樹與哈夫曼編碼 091 考點(diǎn)12　并查集 093 過關(guān)練習(xí) 093 單項(xiàng)選擇題 093 綜合應(yīng)用題 100 答案與解析 104 第五章　圖 第 一節(jié)　圖的基本概念與圖的存儲(chǔ) 126 考點(diǎn)1　圖的基本概念 126 考點(diǎn)2　鄰接矩陣 127 考點(diǎn)3　鄰接表 128 考點(diǎn)4　其他存儲(chǔ)方式 129 第二節(jié)　圖的遍歷 129 考點(diǎn)5　深度優(yōu)先搜索 129 考點(diǎn)6　廣度優(yōu)先搜索 131 第三節(jié)　最小生成樹 133 考點(diǎn)7　最小生成樹的概念 133 考點(diǎn)8　Kruskal算法與Prim算法 135 第四節(jié)　最短路徑 136 考點(diǎn)9　最短路徑的概念 136 考點(diǎn)10　Dijkstra算法與Floyd算法 137 第五節(jié)　拓?fù)渑判?138 考點(diǎn)11　AOV網(wǎng)與拓?fù)渑判虻母拍?138 考點(diǎn)12　拓?fù)渑判虻那蠼?138 第六節(jié)　 關(guān)鍵路徑 139 考點(diǎn)13　AOE網(wǎng)與關(guān)鍵路徑的概念 139 考點(diǎn)14　關(guān)鍵路徑的求解 140 過關(guān)練習(xí) 141 單項(xiàng)選擇題 141 綜合應(yīng)用題 148 答案與解析 152 第六章　查找 第 一節(jié)　線性查找 167 考點(diǎn)1　順序查找 167 考點(diǎn)2　折半查找 168 考點(diǎn)3　分塊查找 169 第二節(jié)　樹形查找 170 考點(diǎn)4　二叉排序樹 170 考點(diǎn)5　平衡二叉樹 170 考點(diǎn)6　B樹與B+樹 172 考點(diǎn)7　紅黑樹 174 第三節(jié)　散列查找 175 考點(diǎn)8　散列表的基本概念 175 考點(diǎn)9　散列函數(shù)設(shè)計(jì)與沖突處理 176 考點(diǎn)10　散列表的性能分析 178 第四節(jié)　串的匹配 178 考點(diǎn)11　暴力匹配算法 178 考點(diǎn)12　KMP算法 179 過關(guān)練習(xí) 180 單項(xiàng)選擇題 180 綜合應(yīng)用題 184 答案與解析 186 第七章　排序 第 一節(jié)　插入類排序 197 考點(diǎn)1　直接插入排序 197 考點(diǎn)2　折半插入排序 198 考點(diǎn)3　希爾排序 198 第二節(jié)　交換類排序 200 考點(diǎn)4　冒泡排序 200 考點(diǎn)5　快速排序 200 第三節(jié)　選擇類排序 201 考點(diǎn)6　簡單選擇排序 201 考點(diǎn)7　堆排序 202 第四節(jié)　歸并排序與基數(shù)排序 203 考點(diǎn)8　歸并排序 203 考點(diǎn)9　基數(shù)排序 204 第五節(jié)　排序總結(jié) 204 考點(diǎn)10　內(nèi)部排序的對(duì)比 204 考點(diǎn)11　排序的應(yīng)用 206 第六節(jié)　外部排序 206 考點(diǎn)12　外部排序算法 206 考點(diǎn)13　最佳歸并樹 207 過關(guān)練習(xí) 207 單項(xiàng)選擇題 207 綜合應(yīng)用題 213 答案與解析 214 全真模擬題及答案解析 全真模擬題 226 全真模擬題參考答案及解析 228