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

考綱分析與應(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