目 錄
第一篇　習(xí)題與實(shí)驗(yàn)
第一章　緒論 3
1.1　學(xué)習(xí)指導(dǎo) 3
1.1.1　基本概念 3
1.1.2　抽象數(shù)據(jù)類(lèi)型 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 簡(jiǎn)答題 11
第二章　線性表 12
2.1 學(xué)習(xí)指導(dǎo) 12
2.1.1　線性表的定義及抽象數(shù)據(jù)類(lèi)型 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 簡(jiǎn)答題 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　棧的類(lèi)型定義 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 簡(jiǎn)答題 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ù)組順序存儲(chǔ)的表示和實(shí)現(xiàn) 66
5.1.3　稀疏矩陣的壓縮存儲(chǔ) 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ù)組的存儲(chǔ)表示和實(shí)現(xiàn)方法（驗(yàn)證性實(shí)驗(yàn)） 73
第六章　樹(shù)和二叉樹(shù) 77
6.1 學(xué)習(xí)指導(dǎo) 77
6.1.1　樹(shù)的概念 77
6.1.2　二叉樹(shù) 78
6.1.3　遍歷二叉樹(shù)和線索二叉樹(shù) 80
6.1.4　樹(shù)和森林 84
6.1.5　哈夫曼樹(shù) 85
6.2　習(xí)題 86
6.2.1 單項(xiàng)選擇題 86
6.2.2 填空題 88
6.2.3 簡(jiǎn)答題 90
6.3 實(shí)驗(yàn) 90
6.3.1 二叉樹(shù)的建立及遍歷（驗(yàn)證性實(shí)驗(yàn)） 90
6.3.2 哈夫曼樹(shù)（設(shè)計(jì)性實(shí)驗(yàn)） 94
第七章　圖 96
7.1 學(xué)習(xí)指導(dǎo) 96
7.1.1 圖的基本概念 96
7.1.2 圖的存儲(chǔ)結(jié)構(gòu) 98
7.1.3 圖的遍歷 99
7.1.4　圖的連通性 100
7.1.5 有向無(wú)環(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 簡(jiǎn)答題 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ù)問(wèn)題（設(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　簡(jiǎn)答題 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 簡(jiǎn)答題 154
9.2.5 算法設(shè)計(jì)題 155
9.3 實(shí)驗(yàn) 155
9.3.1 簡(jiǎn)單排序的應(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)會(huì)成績(jī)統(tǒng)計(jì)系統(tǒng) 194
實(shí)訓(xùn)案例八　地圖染色問(wèn)題 199
實(shí)訓(xùn)案例九　哈夫曼樹(shù)的構(gòu)建與展示 204
實(shí)訓(xùn)案例十　圖的深度和廣度優(yōu)先搜索遍歷 211
實(shí)訓(xùn)案例十一　餐館消費(fèi)問(wèn)題 217
實(shí)訓(xùn)案例十二　二叉樹(shù)的基本操作管理系統(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