數(shù)據(jù)結(jié)構(gòu)搶分攻略 真題分類(lèi)分級(jí)詳解

考綱分析與應(yīng)試策略

一、考試簡(jiǎn)介 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ò)關(guān)練習(xí) 010
單項(xiàng)選擇題 010
答案與解析 012


第二章　線(xiàn)性表

第 一節(jié)　線(xiàn)性表的順序表示 015
考點(diǎn)1　線(xiàn)性表的定義和性質(zhì) 015
考點(diǎn)2　順序表的性質(zhì)和操作 016
第二節(jié)　線(xiàn)性表的鏈?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ò)關(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ò)關(guān)練習(xí) 061
單項(xiàng)選擇題 061
綜合應(yīng)用題 065
答案與解析 066


第四章　樹(shù)形結(jié)構(gòu)

第 一節(jié)　樹(shù) 077
考點(diǎn)1　樹(shù)的基本概念和性質(zhì) 077
考點(diǎn)2　樹(shù)的存儲(chǔ)結(jié)構(gòu) 079
第二節(jié)　二叉樹(shù) 079
考點(diǎn)3　二叉樹(shù)的定義和性質(zhì) 079
考點(diǎn)4　特殊的二叉樹(shù) 081
第三節(jié)　二叉樹(shù)的存儲(chǔ)與遍歷 083
考點(diǎn)5　二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ) 083
考點(diǎn)6　二叉樹(shù)的順序存儲(chǔ) 083
考點(diǎn)7　二叉樹(shù)的遍歷 084
考點(diǎn)8　線(xiàn)索二叉樹(shù) 086
第四節(jié)　森林 088
考點(diǎn)9　樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 088
考點(diǎn)10　樹(shù)與森林的遍歷 090
第五節(jié)　樹(shù)形結(jié)構(gòu)的應(yīng)用 091
考點(diǎn)11　哈夫曼樹(shù)與哈夫曼編碼 091
考點(diǎn)12　并查集 093
過(guò)關(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é)　最小生成樹(shù) 133
考點(diǎn)7　最小生成樹(shù)的概念 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ò)關(guān)練習(xí) 141
單項(xiàng)選擇題 141
綜合應(yīng)用題 148
答案與解析 152


第六章　查找

第 一節(jié)　線(xiàn)性查找 167
考點(diǎn)1　順序查找 167
考點(diǎn)2　折半查找 168
考點(diǎn)3　分塊查找 169
第二節(jié)　樹(shù)形查找 170
考點(diǎn)4　二叉排序樹(shù) 170
考點(diǎn)5　平衡二叉樹(shù) 170
考點(diǎn)6　B樹(shù)與B+樹(shù) 172
考點(diǎn)7　紅黑樹(shù) 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ò)關(guān)練習(xí) 180
單項(xiàng)選擇題 180
綜合應(yīng)用題 184
答案與解析 186


第七章　排序

第 一節(jié)　插入類(lèi)排序 197
考點(diǎn)1　直接插入排序 197
考點(diǎn)2　折半插入排序 198
考點(diǎn)3　希爾排序 198
第二節(jié)　交換類(lèi)排序 200
考點(diǎn)4　冒泡排序 200
考點(diǎn)5　快速排序 200
第三節(jié)　選擇類(lèi)排序 201
考點(diǎn)6　簡(jiǎn)單選擇排序 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　最佳歸并樹(shù) 207
過(guò)關(guān)練習(xí) 207
單項(xiàng)選擇題 207
綜合應(yīng)用題 213
答案與解析 214


全真模擬題及答案解析

全真模擬題 226
全真模擬題參考答案及解析 228