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