目 錄
第一篇　習(xí)題與實(shí)驗(yàn)
第一章　緒論 3
1.1　學(xué)習(xí)指導(dǎo) 3
1.1.1　基本概念 3
1.1.2　抽象數(shù)據(jù)類型 5
1.1.3　算法及其分析 6
1.2　習(xí)題 9
1.2.1　單項(xiàng)選擇題 9
1.2.2 填空題 10
1.2.3 判斷題 11
1.2.4 簡答題 11
第二章　線性表 12
2.1 學(xué)習(xí)指導(dǎo) 12
2.1.1　線性表的定義及抽象數(shù)據(jù)類型 12
2.1.2　順序表的實(shí)現(xiàn) 13
2.1.3　線性鏈表的實(shí)現(xiàn) 15
2.1.4　分析討論 18
2.1.5　線性表的應(yīng)用 18
2.2 習(xí)題 18
2.2.1 單項(xiàng)選擇題 18
2.2.2 填空題 21
2.2.3 判斷題 22
2.2.4 簡答題 23
2.2.5 算法設(shè)計(jì)題 23
2.3 實(shí)驗(yàn) 24
2.3.1 線性表（驗(yàn)證性實(shí)驗(yàn)） 24
2.3.2 線性表（設(shè)計(jì)性實(shí)驗(yàn)） 30
第三章　棧與隊(duì)列 37
3.1 學(xué)習(xí)指導(dǎo) 37
3.1.1　棧的類型定義 37
3.1.2　順序棧的實(shí)現(xiàn) 38
3.1.3　棧的應(yīng)用 39
3.1.4 隊(duì)列 39
3.2 習(xí)題 41
3.2.1 單項(xiàng)選擇題 41
3.2.2 填空題 43
3.2.3 判斷題 43
3.2.4 簡答題 44
3.2.5 算法設(shè)計(jì)題 44
3.3 實(shí)驗(yàn) 44
3.3.1 棧和隊(duì)列的應(yīng)用（驗(yàn)證性實(shí)驗(yàn)） 44
3.3.2 棧和隊(duì)列（設(shè)計(jì)性實(shí)驗(yàn)） 50
第四章　串 54
4.1 學(xué)習(xí)指導(dǎo) 54
4.1.1　串的定義 54
4.1.2　串的表示和實(shí)現(xiàn) 55
4.2 習(xí)題 59
4.2.1　單項(xiàng)選擇題 59
4.2.2 填空題 59
4.2.3 判斷題 59
4.2.4　算法設(shè)計(jì)題 60
4.3 實(shí)驗(yàn) 60
4.3.1 串的基本運(yùn)算（驗(yàn)證性實(shí)驗(yàn)） 60
4.3.2 串的應(yīng)用（設(shè)計(jì)性實(shí)驗(yàn)） 63
第五章　數(shù)組和廣義表 65
5.1 學(xué)習(xí)指導(dǎo) 65
5.1.1　數(shù)組的定義 65
5.1.2　數(shù)組順序存儲的表示和實(shí)現(xiàn) 66
5.1.3　稀疏矩陣的壓縮存儲 67
5.1.4　廣義表 69
5.2 習(xí)題 71
5.2.1 單項(xiàng)選擇題 71
5.2.2 填空題 72
5.3 實(shí)驗(yàn) 73
數(shù)組的存儲表示和實(shí)現(xiàn)方法（驗(yàn)證性實(shí)驗(yàn)） 73
第六章　樹和二叉樹 77
6.1 學(xué)習(xí)指導(dǎo) 77
6.1.1　樹的概念 77
6.1.2　二叉樹 78
6.1.3　遍歷二叉樹和線索二叉樹 80
6.1.4　樹和森林 84
6.1.5　哈夫曼樹 85
6.2　習(xí)題 86
6.2.1 單項(xiàng)選擇題 86
6.2.2 填空題 88
6.2.3 簡答題 90
6.3 實(shí)驗(yàn) 90
6.3.1 二叉樹的建立及遍歷（驗(yàn)證性實(shí)驗(yàn)） 90
6.3.2 哈夫曼樹（設(shè)計(jì)性實(shí)驗(yàn)） 94
第七章　圖 96
7.1 學(xué)習(xí)指導(dǎo) 96
7.1.1 圖的基本概念 96
7.1.2 圖的存儲結(jié)構(gòu) 98
7.1.3 圖的遍歷 99
7.1.4　圖的連通性 100
7.1.5 有向無環(huán)圖及其應(yīng)用 101
7.1.6 最短路徑 102
7.2 習(xí)題 102
7.2.1 單項(xiàng)選擇題 102
7.2.2 填空題 106
7.2.3 判斷題 106
7.2.4 簡答題 107
7.2.5 算法設(shè)計(jì)題 108
7.3 實(shí)驗(yàn) 108
7.3.1　圖的遍歷（驗(yàn)證性實(shí)驗(yàn)） 108
7.3.2　最小生成樹問題（設(shè)計(jì)性實(shí)驗(yàn)） 113
第八章　查找 116
8.1 學(xué)習(xí)指導(dǎo) 116
8.1.1 查找的基本概念 116
8.1.2 靜態(tài)查找表 117
8.1.3 動(dòng)態(tài)查找表 119
8.1.4 哈希表 124
8.2 習(xí)題 127
8.2.1　單項(xiàng)選擇題 127
8.2.2　填空題 130
8.2.3　判斷題 131
8.2.4　簡答題 131
8.2.5　算法設(shè)計(jì)題 132
8.3 實(shí)驗(yàn) 133
8.3.1　線性表的查找（驗(yàn)證性實(shí)驗(yàn)） 133
8.3.2　散列查找（設(shè)計(jì)性實(shí)驗(yàn)） 137
第九章　排序 140
9.1 學(xué)習(xí)指導(dǎo) 140
9.1.1 排序的基本概念 140
9.1.2 插入排序 141
9.1.3 交換排序 144
9.1.4 選擇排序 147
9.1.5 歸并排序 149
9.1.6 各種排序方法的綜合比較 149
9.2 習(xí)題 150
9.2.1 單項(xiàng)選擇題 150
9.2.2 填空題 153
9.2.3 判斷題 154
9.2.4 簡答題 154
9.2.5 算法設(shè)計(jì)題 155
9.3 實(shí)驗(yàn) 155
9.3.1 簡單排序的應(yīng)用（驗(yàn)證性實(shí)驗(yàn)） 155
9.3.2 復(fù)雜排序的應(yīng)用（設(shè)計(jì)性實(shí)驗(yàn)） 159
第二篇　實(shí)訓(xùn)案例
實(shí)訓(xùn)案例一　通信錄查找系統(tǒng) 165
實(shí)訓(xùn)案例二　雙向約瑟夫環(huán) 169
實(shí)訓(xùn)案例三　算術(shù)表達(dá)式求值程序 173
實(shí)訓(xùn)案例四　校園導(dǎo)游咨詢系統(tǒng) 178
實(shí)訓(xùn)案例五　實(shí)現(xiàn)閉散列表的建立和查找 185
實(shí)訓(xùn)案例六　排序 187
實(shí)訓(xùn)案例七　運(yùn)動(dòng)會成績統(tǒng)計(jì)系統(tǒng) 194
實(shí)訓(xùn)案例八　地圖染色問題 199
實(shí)訓(xùn)案例九　哈夫曼樹的構(gòu)建與展示 204
實(shí)訓(xùn)案例十　圖的深度和廣度優(yōu)先搜索遍歷 211
實(shí)訓(xùn)案例十一　餐館消費(fèi)問題 217
實(shí)訓(xùn)案例十二　二叉樹的基本操作管理系統(tǒng) 221
附錄A　數(shù)據(jù)結(jié)構(gòu)模擬試卷
數(shù)據(jù)結(jié)構(gòu)模擬試卷（一） 229
數(shù)據(jù)結(jié)構(gòu)模擬試卷（二） 233
數(shù)據(jù)結(jié)構(gòu)模擬試卷（三） 236
數(shù)據(jù)結(jié)構(gòu)模擬試卷（四） 239
數(shù)據(jù)結(jié)構(gòu)模擬試卷（五） 242
數(shù)據(jù)結(jié)構(gòu)模擬試卷（六） 245
數(shù)據(jù)結(jié)構(gòu)模擬試卷（七） 248
數(shù)據(jù)結(jié)構(gòu)模擬試卷（八） 251
數(shù)據(jù)結(jié)構(gòu)模擬試卷（九） 254
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十） 257
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十一） 260
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十二） 264
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十三） 268
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十四） 271
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十五） 275
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十六） 279
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十七） 283
數(shù)據(jù)結(jié)構(gòu)模擬試卷（一）參考答案 287
數(shù)據(jù)結(jié)構(gòu)模擬試卷（二）參考答案 289
數(shù)據(jù)結(jié)構(gòu)模擬試卷（三）參考答案 291
數(shù)據(jù)結(jié)構(gòu)模擬試卷（四）參考答案 293
數(shù)據(jù)結(jié)構(gòu)模擬試卷（五）參考答案 295
數(shù)據(jù)結(jié)構(gòu)模擬試卷（六）參考答案 296
數(shù)據(jù)結(jié)構(gòu)模擬試卷（七）參考答案 298
數(shù)據(jù)結(jié)構(gòu)模擬試卷（八）參考答案 300
數(shù)據(jù)結(jié)構(gòu)模擬試卷（九）參考答案 301
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十）參考答案 302
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十一）參考答案 304
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十二）參考答案 306
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十三）參考答案 308
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十四）參考答案 311
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十五）參考答案 314
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十六）參考答案 316
數(shù)據(jù)結(jié)構(gòu)模擬試卷（十七）參考答案 318