軟件技術基礎概論（簡體書）

本書是系統講述軟件技術基礎的基本理論、技術、方法和軟件開發工具等內容的教材。本書的特點是理論與實踐相結合，內容安排上由淺入深，循序漸進，對基本概念講解清楚。全書共分3篇11章，基礎篇主要內容是數據結構；技術篇主要內容有軟件工程技術、數據庫技術和統一建模語言UML；應用篇主要內容是Web網頁設計。本書提供大量的實例，並有配套的《軟件技術基礎概論習題解析與上機指導》教學輔導書。書中實例取材新穎，內容翔實，圖文並茂。本書中的全部算法都在Visual C++ 6.0環境下測試通過。
本書可作為高等學校工學專業和其他有關專業本科生、研究生教材，也可作為從事工程應用領域應用軟件開發的科研和工程技術人員的參考書。

《普通高等教育電氣信息類應用型規劃教材:軟件技術基礎概論》的理論與實踐相結合，內容安排上由淺入深，循序漸進，對基本概念講解清楚。《普通高等教育電氣信息類應用型規劃教材:軟件技術基礎概論》可作為高等學校工學專業和其他有關專業本科生、研究生教材，也可作為從事工程應用領域應用軟件開發的科研和工程技術人員的參考書。

第1篇 基礎篇
第1章 緒論
1.1 數據結構的概念
1.1.1 數據與數據元素
1.1.2 數據結構
1.2 邏輯結構與存儲結構
1.2.1 邏輯結構
1.2.2 存儲結構
1.3 算法與算法分析
1.3.1 算法的定義和描述
1.3.2 算法分析和復雜度計算
習題1
第2章 線性表
2.1 線性表及其邏輯結構
2.1.1 線性表的定義
2.1.2 線性表的基本操作
2.2 線性表的順序存儲結構及運算實現
2.2.1 線性表的順序存儲——順序表
2.2.2 順序表上基本運算的實現
2.3 線性表的鏈式存儲結構及運算實現
2.3.1 單鏈表
2.3.2 單鏈表上基本運算的實現
2.3.3 循環鏈表
2.3.4 單鏈表應用示例
習題2
第3章 棧和隊列
3.1 棧
3.1.1 棧的定義及基本運算
3.1.2 棧的存儲結構和運算實現
3.2 隊列
3.2.1 隊列的定義及基本運算
3.2.2 隊列的存儲結構和運算實現
習題3
第4章 樹與二叉樹
4.1 樹的基本概念
4.1.1 樹的概念與定義
4.1.2 樹的基本術語
4.2 二叉樹
4.2.1 二叉樹的定義
4.2.2 二叉樹的性質
4.2.3 二叉樹的存儲結構
4.3 二叉樹的遍歷
4.3.1 二叉樹的遍歷方法
4.3.2 遍歷二叉樹的遞歸算法及遍歷示例
4.3.3 二叉樹遍歷的應用
4.4 二叉排序樹
4.4.1 二叉排序樹的定義
4.4.2 二叉排序樹的插入操作和二叉排序樹的構造
4.5 哈夫曼樹
4.5.1 哈夫曼樹基本概念及構造方法
4.5.2 哈夫曼算法的實現
4.6 樹和森林
4.6.1 樹的定義與存儲結構
4.6.2 樹、森林與二叉樹之間的轉換
4.6.3 樹和森林的遍歷
習題4
第5章 圖
5.1 圖的基本概念
5.1.1 圖的定義
5.1.2 圖的基本術語
5.2 圖的存儲結構
5.2.1 鄰接矩陣
5.2.2 鄰接表
5.3 圖的遍歷
5.3.1 深度優先搜索
5.3.2 廣度優先搜索
5.3.3 圖的應用
習題5
第6章 查找
6.1 查找的基本概念
6.2 靜態查找表
6.2.1 順序查找
6.2.2 有序表的查找
6.3 動態查找表
6.3.1 二叉排序樹查找
6.3.2 哈希表構造與查找
習題6
第7章 排序
7.1 基本概念
7.2 插入排序
7.3 交換排序
7.3.1 冒泡排序
7.3.2 快速排序
7.4 選擇排序
7.5 歸并排序
習題7
第2篇 技術篇
第8章 軟件工程技術
8.1 軟件工程基本知識
8.1.1 概述
8.1.2 軟件和軟件危機
8.1.3 軟件工程的定義
8.2 軟件開發模型
8.2.1 瀑布模型
8.2.2 快速原型模型
8.2.3 增量模型
8.2.4 螺旋模型
8.2.5 噴泉模型
8.3 軟件生命周期
8.3.1 軟件定義
8.3.2 軟件設計
8.3.3 軟件編碼
8.3.4 軟件測試
8.3.5 軟件維護
8.4 軟件工程技術發展趨勢
習題8
第9章 數據庫技術
9.1 數據庫的基本知識
9.1.1 數據庫的基本概念
9.1.2 數據庫系統模型
9.2 關系模型及關系數據庫
9.2.1 關系模型
9.2.2 關系數據庫
9.3 數據庫系統結構
9.3.1 數據庫系統模式
9.3.2 數據庫系統的三級模式結構
9.4 數據庫設計
9.4.1 數據規范化
9.4.2 數據庫設計的一般步驟
9.4.3 數據庫概念結構設計
9.4.4 數據庫邏輯結構設計
9.4.5 數據庫物理結構設計
9.5 關系數據庫結構化查詢語言SQL
9.5.1 SQL的特點
9.5.2 SQL支持的關系數據模式
9.5.3 數據定義
9.5.4 查詢
9.5.5 數據更新
9.5.6 視圖
9.5.7 數據控制
9.6 動態SQL
9.6.1 靜態SQL語句
9.6.2 動態SQL
9.7 數據庫技術及SQL發展趨勢
習題9
第10 章統一建模語言UML
10.1 UML基本知識
10.1.1 UML發展歷史
10.1.2 UML基本概念
10.1.3 UML特點
10.2 面向對象分析技術與UML
10.2.1 面向對象分析技術
10.2.2 采用UML進行面向對象分析
……
第3篇 應用篇
第11章 Web網頁設計
參考文獻

（15）散列表的平均查找長度（ ）。
A.與處理沖突的方法有關但與表的長度無關
B.與處理沖突的方法無關但與表的長度有關
C.與處理沖突的方法有關也與表的長度有關
D.與處理沖突的方法無關也與表的長度無關
（16）在采用線性探測法處理沖突所構成的閉散列表上進行查找可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的鍵值（ ）。
A.一定都是同義詞 B.一定都不是同義詞
C.都相同 D.不一定都是同義詞
2.多項選擇題。
（1）在構造哈希表的過程中，不可避免地會出現沖突，通常解決的辦法有（ ）。
A.平方取中法 B.開放地址法
C.隨機探測法 D.再哈希法
E.鏈地址法
（2）散列函數用來指定關鍵字與存儲地址之間的映射關系，常用的構造方法有（ ）。
A.直接定地法 B.折疊函數法
C.平方取中法 D.鏈接表法
E.除留余數法
3.填空題。
（1）順序查找含有n個元素的順序表，若查找成功，則比較關鍵字的次數最多為__次；當使用監視哨時，若查找失敗，則比較關鍵字的次數為____。
（2）在n個記錄的有序表中進行折半查找，則最大的比較次數是____。
（3）設順序表（a1，a2，…，a500）元素的值由小到大排列，對一個給定的k值用二分法查找順序表，在查找不成功時至多需要比較____次。
（4）用二分法查找一個線性表時，該線性表必須具有的特點是____；而分塊查找法要求將待查的表均勻地分成若干塊且塊中的元素可無序存放，但塊與塊之間__。
（5）分塊查找中，若索引表對各塊內均采用順序查找，則有900個元素的線性表分成__塊最好；若分成25塊，其平均查找長度為____。
（6）二叉排序樹的查找長度不僅與__有關，也與二叉排序樹的__有關。
（7）在二叉排序樹上插入新結點時不必移動其他結點，僅需使樹葉結點的指針由指向新結點即可。
（8）假定有k個關鍵字互為同義詞，若用線性探測再散列的方法把這k個關鍵字存入到散列表中，則至少需要進行____次探測。
4.判斷題。
（1）用數組或單鏈表存儲的有序表均可用折半查找方法來提高查找速度。