數(shù)據(jù)結(jié)構復習指南與題解

第1章 概論
1.1 基本概念
1.1.1 數(shù)據(jù)的有關概念
1.1.2 數(shù)據(jù)結(jié)構的有關概念
1.1.3 算法的有關概念
1.2 基本理論
1.2.1 數(shù)據(jù)結(jié)構的研究目的和研究內(nèi)容
1.2.2 邏輯結(jié)構的4種基本形態(tài)及特點
1.2.3 引入抽象數(shù)據(jù)類型概念的好處
1.2.4 邏輯結(jié)構的特點及意義
1.2.5 算法的特征及設計要求
1.2.6 算法的計算量的含義及估算的方法
1.2.7 數(shù)據(jù)的存儲方式
1.2.8 算法的分類
1.2.9 數(shù)據(jù)結(jié)構的評價和選擇
1.3 典型例題
1.4 習題
第2章 線性表
2.1 基本概念
2.1.1 順序線性表的有關概念
2.1.2 鏈式線性表的有關概念
2.2 基本理論
2.2.1 線性結(jié)構的基本特征
2.2.2 線性表的特點
2.2.3 線性表典型的基本運算
2.2.4 順序表示法的基本思想和特點
2.2.5 單鏈表設置頭結(jié)點的作用
2.2.6 線性表的定位運算與算法
2.2.7 單鏈表插入運算的算法實現(xiàn)
2.2.8 單鏈表的數(shù)據(jù)域和指針域的作用
2.2.9 循環(huán)鏈表和雙鏈表的組織方法
2.2.10 線性表的插入運算與算法
2.2.11 線性表的刪除運算與算法
2.2.12 順序表的類C語言描述
2.2.13 單鏈表的類C語言描述
2.2.14 單鏈表定位運算的算法實現(xiàn)
2.2.15 單鏈表刪除運算的算法實現(xiàn)
2.2.16 鏈表的組織方法和特點
2.2.17 順序表的主要優(yōu)缺點
2.2.18 鏈表的豐要優(yōu)點和缺點
2.2.19 頭指針、頭結(jié)點、首結(jié)點的區(qū)別
2.2.20 線性表的索引存儲結(jié)構及其優(yōu)點
2.2.21 靜態(tài)鏈表的用途和構造方法
2.3 典型例題
2.4 習題
第3章 棧和隊列
3.1 基本概念
3.1.1 棧的有關概念
3.1.2 隊列的有關概念
3.2 基本理論
3.2.1 棧的基本運算
3.2.2 棧的基本特點
3.2.3 順序棧的組織方法
3.2.4 順序棧上初始化的算法
3.2.5 進棧和退棧運算在順序棧上的實現(xiàn)算法
3.2.6 鏈棧上實現(xiàn)進棧和退棧的算法
3.2.7 讀棧項元素的算法
3.2.8 判定棧是否為空的算法
3.2.9 取棧項元素的算法
3.2.10 數(shù)組及其基本運算
3.2.11 遞歸及其特點
3.2.12 鏈隊列的組織方法和語言描述
3.2.13 鏈隊列上入隊、出隊的算法
3.2.14 循環(huán)隊列上進行入隊、出隊的算法
3.2.15 循環(huán)隊列的隊滿、隊空條件
3.2.16 順序隊列上的"假溢出"及原因
3.2.17 循環(huán)隊列的組織方法
3.2.18 順序隊列的組織方法
3.2.19 隊列的特點及其基本運算
3.2.20 遞歸方法求解的條件
3.3 典型例題
3.4 習題
第4章 串
4.1 基本概念
4.2 基本理論
4.2.1 串的存儲方法
4.2.2 串的順序存儲結(jié)構
4.2.3 順序存儲串的基本運算
4.2.4 串的鏈式存儲的基本運算
4.3 典型例題
4.4 習題
第5章 數(shù)組與廣義表
5.1 基本概念
5.1.1 數(shù)組的有關概念
5.1.2 廣義表的有關概念
5.2 基本理論
5.2.1 數(shù)組的基本操作
5.2.2 數(shù)組的特點
5.2.3 數(shù)組的順序儲存表示
5.2.4 數(shù)組順序存儲的實現(xiàn)
5.2.5 二維數(shù)組的基本運算
5.2.6 二維數(shù)組的順序存儲方式
5.2.7 對稱矩陣的壓縮存儲
5.2.8 稀疏矩陣的基本操作
5.2.9 稀疏矩陣的壓縮存儲方式
5.2.10 廣義表的表示
5.2.11 廣義表的存儲結(jié)構和表示
5.2.12 廣義表存儲結(jié)構的特點
5.2.13 廣義表的基本算法
5.3 典型例題
5.4 習題
第6章 樹和二叉樹
6.1 基本概念
6.1.1 樹的基本術語
6.1.2 二叉樹的有關概念
6.2 基本理論
6.2.1 樹的含義
6.2.2 二叉樹的5種基本形態(tài)
6.2.3 二叉樹的基本運算
6.2.4 二叉樹的性質(zhì)
6.2.5 二叉樹順序存儲的基本思想
6.2.6 二叉樹遍歷方法
6.2.7 二叉樹的遍歷算法
6.2.8 樹的表示法
6.2.9 二叉樹的邏輯結(jié)構及特點
6.2.10 二叉鏈表中結(jié)點及根指針的作用
6.2.11 樹的存儲結(jié)構
6.2.12 樹的基本運算
6.2.13 二叉樹的線索化
6.2.14 哈夫曼樹的構造算法
6.2.15 樹的性質(zhì)
6.2.16 哈夫曼編碼
6.2.17 樹與二叉樹的關系
6.2.18 二叉樹的存儲結(jié)構
6.2.19 使用線索二叉樹的原因
6.2.20 線索二叉樹的方法
6.2.21 二叉樹的基本運算
6.2.22 樹、森林與二叉樹的轉(zhuǎn)換
6.3 典型例題
6.4 習題
第7章 圖
7.1 基本概念
7.2 基本理論
7.2.1 鄰接矩陣的表示方法
7.2.2 鄰接表的表示方法及特點
7.2.3 十字鄰接表存儲方法
7.2.4 非連通圖的遍歷方法
7.2.5 非連通圖中連通分量的求法
7.2.6 連通圖深度和廣度優(yōu)先搜索的基本思想
7.2.7 網(wǎng)的鄰接矩陣的建立方法
7.2.8 無向圖的鄰接表的建立方法
7.2.9 有向圖拓撲排序方法
7.2.10 拓撲排序的基本思想及算法
7.2.11 建立無向網(wǎng)絡的算法
7.2.12 prim算法的基本思想
7.2.13 最小生成樹的實際背景
7.2.14 鄰接表的形式及建鄰接表的算法
7.2.15 最小生成樹的性質(zhì)
7.2.16 求最小生成樹需考慮的問題
7.2.17 構造最小生成樹的方法
7.2.18 求從某個源點到其余各頂點的最短路徑
7.2.19 每對頂點之間的最短路徑
7.2.20 求關鍵路徑的計算過程
7.3 典型例題
7.4 習題
第8章 查找表
8.1 基本概念
8.2 基本理論
8.2.1 順序查找的基本思想
8.2.2 順序表查找的算法
8.2.3 折半查找的基本思想及特點
8.2.4 折半查找的算法
8.2.5 分塊查找的基本思想及特點
8.2.6 分塊查找的算法及時間與空間性能
8.2.7 二叉排序樹的基本思想及算法
8.2.8 在二叉排序樹上插入結(jié)點的算法
8.2.9 生成二叉排序樹的算法
8.2.10 從二叉排序樹上刪除結(jié)點
8.2.11 平衡二叉樹的方法
8.2.12 B-樹的含義
8.2.13 B-樹的查找
8.2.14 B-樹的插入和生成
8.2.15 B-樹的刪除
8.2.16 B-樹和B+樹的區(qū)別
8.2.17 B+樹查找、刪除特點
8.2.18 哈希表的含義及特點
8.2.19 常用的構造哈希函數(shù)的方法
8.2.20 解決沖突的方法
8.2.21 哈希表的查找及算法
8.2.22 鏈地址法的優(yōu)缺點
8.3 典型例題
8.4 習題
第9章 排序
9.1 基本概念
9.1.1 內(nèi)部排序的有關概念
9.1.2 外部排序的有關概念
9.2 基本理論
9.2.1 直接插入排序的基本思想及算法
9.2.2 直接插入排序的時空性能
9.2.3 希爾排序的基本思想及算法
9.2.4 冒泡排序的基本思想及算法
9.2.5 快速排序的基本思想及算法
9.2.6 直接選擇排序的基本思想及算法
9.2.7 堆排序的基本思想
9.2.8 堆排序的過程及算法
9.2.9 二路歸并排序的基本思想
9.2.10 基數(shù)排序的基本思想及算法
9.2.11 各種內(nèi)部排序方法的比較
9.2.12 外部排序的基本思想
9.2.13 歸并排序的基本方法
9.2.14 置換-選擇排序的基本思想
9.2.15 利用"敗者樹"實現(xiàn)置換選擇排序
9.2.16 最佳歸并樹的構造
9.3 典型例題
9.4 習題
第10章 文件
10.1 基本概念
10.2 基本理論
10.2.1 文件的結(jié)構
10.2.2 文件的組織形式
10.2.3 順序文件的組織形式及特點
10.2.4 文件的基本運算
10.2.5 散列文件的查找及特點
10.2.6 散列文件的結(jié)構和操作特點
10.2.7 多關鍵字文件的結(jié)構特點
10.2.8 順序文件的檢索方法
10.2.9 索引文件的組織特點
10.3 典型例題
10.4 習題
附錄 習題答案