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

考綱分析與應試策略

一、考試簡介 001
二、考試方式 001
三、考試大綱解讀 002
四、應試經(jīng)驗與答題技巧 003
五、復習策略 004


第 一章　緒論

第 一節(jié)　數(shù)據(jù)結(jié)構(gòu)與算法的基本概念 006
考點1　數(shù)據(jù)結(jié)構(gòu)的基本概念 006
考點2　算法的基本概念 007
第二節(jié)　算法的時間復雜度與空間復雜度 008
考點3　時間復雜度 008
考點4　空間復雜度 010
過關練習 010
單項選擇題 010
答案與解析 012


第二章　線性表

第 一節(jié)　線性表的順序表示 015
考點1　線性表的定義和性質(zhì) 015
考點2　順序表的性質(zhì)和操作 016
第二節(jié)　線性表的鏈式表示 016
考點3　單鏈表的性質(zhì)和操作 016
考點4　雙向鏈表的性質(zhì)和操作 018
考點5　循環(huán)鏈表與靜態(tài)鏈表 019
考點6　順序結(jié)構(gòu)與鏈式結(jié)構(gòu)的比較 020
過關練習 020
單項選擇題 020
綜合應用題 022
答案與解析 027

第三章　棧、隊列和數(shù)組

第 一節(jié)　棧 048
考點1　棧的基本概念 048
考點2　棧的順序存儲 051
考點3　棧的鏈式存儲 052
考點4　棧的應用 052
第二節(jié)　隊列 054
考點5　隊列的基本概念 054
考點6　隊列的順序存儲 055
考點7　隊列的鏈式存儲 058
考點8　隊列的應用 058
第三節(jié)　數(shù)組 059
考點9　多維數(shù)組的存儲 059
考點10　特殊矩陣的壓縮存儲 060
過關練習 061
單項選擇題 061
綜合應用題 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　二叉樹的鏈式存儲 083
考點6　二叉樹的順序存儲 083
考點7　二叉樹的遍歷 084
考點8　線索二叉樹 086
第四節(jié)　森林 088
考點9　樹、森林與二叉樹的轉(zhuǎn)換 088
考點10　樹與森林的遍歷 090
第五節(jié)　樹形結(jié)構(gòu)的應用 091
考點11　哈夫曼樹與哈夫曼編碼 091
考點12　并查集 093
過關練習 093
單項選擇題 093
綜合應用題 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é)　拓撲排序 138
考點11　AOV網(wǎng)與拓撲排序的概念 138
考點12　拓撲排序的求解 138
第六節(jié)　 關鍵路徑 139
考點13　AOE網(wǎng)與關鍵路徑的概念 139
考點14　關鍵路徑的求解 140
過關練習 141
單項選擇題 141
綜合應用題 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ù)設計與沖突處理 176
考點10　散列表的性能分析 178
第四節(jié)　串的匹配 178
考點11　暴力匹配算法 178
考點12　KMP算法 179
過關練習 180
單項選擇題 180
綜合應用題 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　排序的應用 206
第六節(jié)　外部排序 206
考點12　外部排序算法 206
考點13　最佳歸并樹 207
過關練習 207
單項選擇題 207
綜合應用題 213
答案與解析 214


全真模擬題及答案解析

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