數據結構與算法（簡體書）

《21世紀高等教育計算機規劃教材．國家級雙語教學示範課程配套教材：數據結構與算法》是國家級雙語教學示範課程《數據結構》的配套教材，根據教育部高等學校計算機科學與技術教學指導委員會制定的《高等學校計算機科學與技術專業發展戰略研究報告暨專業規範》編寫。全書每章均以數據的邏輯結構、存儲結構和相應的算法實現為主線，並對算法的運算效率進行分析。全書分為8章，涵蓋了各種常見數據結構。第1章主要介紹數據結構和算法分析的基本概念，第2～6章主要介紹典型的線性結構、樹型結構和圖型結構，第7～8章分別介紹查找和排序操作。
另外，每章後面附有習題和上機實驗內容，上機實驗提供了完整的、可運行的程序上機實驗供讀者參考，以加深讀者對所學知識的理解和應用。
《21世紀高等教育計算機規劃教材．國家級雙語教學示範課程配套教材：數據結構與算法》既可作為高等院校計算機及相關專業數據結構課程的教學用書，也可作為從事計算機工程與應用的廣大讀者的參考書。．

《21世紀高等教育計算機規劃教材?國家級雙語教學示范課程配套教材:數據結構與算法》既可作為高等院校計算機及相關專業數據結構課程的教學用書，也可作為從事計算機工程與應用的廣大讀者的參考書。

第1章 緒論
1.1 數據及其邏輯結構
1.1.1 基本概念
1.1.2 邏輯結構
1.2 數據結構
1.2.1 什麼是數據結構
1.2.2 數據結構的二元組描述
1.2.3 數據結構和數據類型
1.3 存儲實現與運算實現
1.3.1 順序存儲結構
1.3.2 鏈式存儲結構
1.3.3 索引存儲結構
1.3.4 散列存儲結構
1.3.5 運算實現
1.3.6 進一步討論
1.4 算法描述和算法分析
1.4.1 什麼是算法
1.4.2 算法描述
1.4.3 算法分析
1.5 網絡教輔資源
1.6 小結
練習一

第2章 線性表
2.1 線性表的基本概念
2.2 線性表的順序表示和實現
2.3 線性表的鏈接表示和實現
2.3.1 線性表的鏈式存儲原理
2.3.2 線性表的鏈式存儲算法實現
2.3.3 算法效率分析
2.4 循環鏈表和雙鏈表
2.4.1 循環鏈表
2.4.2 雙向鏈表
2.5 線性表的應用舉例
2.5.1 問題的提出
2.5.2 分析問題
2.5.3 算法實現
2.5.4 程序
2.6 小結
練習二

第3章 棧和隊列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的基本運算
3.1.3 棧的順序存儲結構
3.1.4 棧的鏈式存儲結構
3.1.5 棧的應用
3.2 隊列
3.2.1 隊列的定義
3.2.2 隊列的基本運算
3.2.3 隊列的順序存儲結構
3.2.4 隊列的鏈式存儲結構
3.2.5 隊列的應用
3.3 小結
練習三

第4章 串和數組
4.1 串的基本概念
4.2 串的基本操作和串的存儲結構
4.2.1 串的基本操作
4.2.2 串的靜態順序存儲結構
4.2.3 串的動態順序存儲結構
4.2.4 串的鏈式存儲結構
4.3 數組的定義和運算
4.4 數組的順序存儲結構
4.5 特殊矩陣的壓縮存儲
4.5.1 特殊矩陣
4.5.2 稀疏矩陣
4.6 小結
練習四

第5章 樹和二叉樹
5.1 樹的概念與定義
5.1.1 樹的定義
5.1.2 樹的基本操作
5.2 二叉樹的性質和存儲結構
5.2.1 二叉樹的定義與基本操作
5.2.2 二叉樹的性質
5.2.3 二叉樹的存儲結構
5.3 二叉樹的遍歷與線索化
5.3.1 二叉樹的遍歷
5.3.2 二叉樹的非遞歸遍歷
5.3.3 樹的唯一性問題
5.3.4 二叉樹遍歷的應用
5.3.5 線索二叉樹
5.4 樹、森林和二叉樹的關係
5.4.1 樹的存儲結構
5.4.2 樹、森林與二叉樹的相互轉換
5.4.3 樹與森林的遍歷
5.5 哈夫曼樹及其應用
5.5.1 哈夫曼樹的定義
5.5.2 哈夫曼樹的構造
5.5.3 哈夫曼編碼
5.6 小結
練習五

第6章 圖
6.1 圖的定義及理論
6.2 圖的存儲結構及算法實現
6.2.1 圖的基本運算的抽象
6.2.2 數組表示法
6.2.3 鄰接表表示
6.2.4 十字鏈表表示
6.3 圖的算法實現
6.3.1 圖的遍歷算法
6.3.2 圖的連通性
6.4 圖的應用
6.4.1 圖的最小生成樹
6.4.2 最短路徑
6.4.3 任意頂點最短路徑
6.5 小結
練習六

第7章 查找表
7.1 查找表的基本概念
7.2 靜態查找表
7.2.1 順序查找
7.2.2 折半查找
7.2.3 分塊查找
7.3 動態查找表
7.3.1 二叉排序樹
7.3.2 平衡二叉樹
7.4 哈希表
7.4.1 哈希表的基本概念
7.4.2 哈希函數的構造方法
7.4.3 處理哈希衝突的方法
7.5 小結
練習七

第8章 內部排序
8.1 排序的基本概念
8.1.1 排序
8.1.2 內部排序和外部排序
8.1.3 排序算法評價
8.1.4 排序算法的穩定性
8.1.5 待排序記錄序列的存儲結構
8.2 直接插入排序和希爾排序
8.2.1 直接插入排序
8.2.2 折半查找插入排序
8.2.3 希爾排序
8.3 選擇排序和堆排序
8.3.1 選擇排序
8.3.2 堆排序
8.4 冒泡排序和快速排序
8.4.1 冒泡排序
8.4.2 快速排序
8.5 歸併排序
8.6 基數排序
8.6.1 基本思想
8.6.2 基數排序過程與算法
8.7 各種內部排序方法的比較討論
8.8 外部排序
8.8.1 外部存儲系統
8.8.2 外部排序面臨的問題
8.8.3 外部排序的基本過程
8.9 小結
練習八
……．

8.有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占1個地址空間，則a85地址為（ ）。
A.13 B.33 C.18 D.40 1
9.設有二維數組A[501160]，其元素長度為1個字節，按列優先順序存儲，首元素A[0】[0】的地址為200，則元素A[101120]的存儲地址為（ ）。
A.820 8.720 C.1210 D.1410
10.一個5×5的對稱矩陣采用壓縮存儲，需要存儲（ ）個元素。
A5 8.10 C.15 D.20
11.數組All…5，1…6】的每個元素占5個單元，將其按行優先次序存儲在起始地址為l000的連續的內存單元中，則元素A[5，51的地址為（ ）。
A.1140 8.1145 C.1120 D.1125
12.對于基于三元組的稀疏矩陣轉置的處理方法以下說法正確的是（ ）。
A.按照矩陣A的列序來進行轉置，算法的時間復雜度為O（nu+tu）
B.按照A的三元組a.arra9的次序進行轉置，算法的時間復雜度為O（nu*tu）
C.按照矩陣A的列序來進行轉置的方法稱快速轉置
D.按照矩陣A的列序進行轉置，對于m
13.稀疏矩陣的壓縮存儲方法是只存儲（ ）。
A.非零元素 B.三元組（i，j，） C.alj D.i，j
14.基于三元組的稀疏矩陣，對每個非零元素a11可以用一個（ ）唯一確定。
A.非零元素 B.三元組（ij，aij） C.aii D.i，j
15.以下說法正確的是（ ）。
A.數組是同類型值的集合
B.數組是一組相繼的內存單元
C.數組是一種復雜的數據結構，數組元素之間的關系既不是線性的，也不是樹形的
D.使用三元組表表示稀疏矩陣的元素，有時并不能節省存儲空間
16.對稀疏矩陣進行壓縮存儲目的是（ ）。
A.便于進行矩陣運算 B.便于輸入和輸出
C.節省存儲空間 D.降低運算的時間復雜度。