2013《805軟件基礎與技術綜合》考試大綱

《軟件基礎與技術綜合》考試大綱一、考試內容數據結構70分+數據庫40分+軟件工程40分數據結構部分數據結構基本概念數據結構的基本概念：數據、數據元素、數據結構、數據的邏輯結構、物理結構、算法等。算法時間復雜度和空間復雜度的分析方法。線性表線性表的定義。線性表的順序存儲結構和主要算法實現(xiàn)，如查找、插入和刪除算法。線性表的鏈式存儲結構和主要算法實現(xiàn)，如查找、插入和刪除算法。循環(huán)鏈表、雙向鏈表的特點。從時間和空間復雜度的角度比較兩種存儲結構的不同特點及其適用場合。線性表的應用，如線性表的合并算法。棧和隊列棧的定義及特點，棧的順序存儲和鏈接存儲結構，進棧出棧算法，順序棧棧滿和?？盏臈l件。棧的應用，如表達式求值算法，借助棧深入理解遞歸算法。隊列的定義及特點，隊列的順序存儲(循環(huán)隊)和鏈接存儲結構，進隊出隊算法，循環(huán)隊列中隊滿及隊空的條件。串和數組串的定義。串的古典模式匹配算法。數組地址的計算方法。特殊矩陣的壓縮存儲方法。樹和二叉樹二叉樹的定義和性質。二叉樹的兩種存儲結構：順序存儲和鏈式存儲。二叉樹的創(chuàng)建和三種不同遍歷算法，利用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結點個數、葉子結點個數、二叉樹的高度等算法。線索二叉樹的特性及構造方法。樹和森林的定義、存儲結構與二叉樹的轉換方法。樹的應用，哈夫曼樹及哈夫曼編碼的構造算法、帶權路徑長度的計算。圖圖的定義和性質。圖的兩種存儲結構：鄰接矩陣和鄰接表。圖的兩種遍歷策略：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。圖的基本應用，包括拓撲排序算法、求解最短路徑的迪杰斯特拉算法、構造最小生成樹的兩種算法(普里姆算法和克魯斯卡爾算法)。查找線性表的查找：順序查找和折半查找算法。樹表的查找：二叉排序樹的定義，二叉排序樹的創(chuàng)建、插入、刪除和查找算法。散列表的查找：兩種處理沖突的方法包括開放地址法(線性探測法、二次探測法)和鏈地址法。上述三種不同查找算法的分析，平均查找長度ASL的計算方法及時間復雜度分析，不同查找算法的適用場合。排序排序的基本概念。插入排序：直接插入排序、折半插入排序和希爾排序。交換排序：冒泡排序和快速排序。選擇排序：簡單選擇排序和堆排序。歸并排序：2-路歸并排序。上述各種排序方法的特點和排序過程，時間和空間復雜度的分析，排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。排序算法的實現(xiàn)及適用場合。數據庫部分數據庫系統(tǒng)概述數據庫系統(tǒng)概論：數據，數據庫，數據庫管理系統(tǒng)，數據庫系統(tǒng)，數據管理技術的產生和發(fā)展，數據庫系統(tǒng)的特點。數據模型：數據模型的組成要素，概念模型，層次模型，網狀模型，關系模型，對象模型。數據庫系統(tǒng)結構：數據庫系統(tǒng)模式的概念，數據庫系統(tǒng)的三級模式結構，數據庫的二級映像功能與數據獨立性，數據庫系統(tǒng)的組成。數據庫技術的研究領域。關系數據庫關系模型概述。關系數據結構及形式化定義：關系，關系模式，關系數據庫。關系的完整性：實體完整性，參照完整性，用戶自定義完整性。關系代數：集合運算，關系運算。關系數據庫標準語言——SQLSQL概述。SQL數據定義。SQL查詢：單表查詢，連接查詢，嵌套查詢，集合查詢。SQL數據更新：插入數據，修改數據，刪除數據。視圖：SQL創(chuàng)建視圖，查詢視圖，更新視圖，視圖意義。數據控制：SQL授權，收回授權。嵌入式SQL。關系數據庫理論關系模式的冗余和異常問題。規(guī)范化：函數依賴，碼，范式，2NF，3NF，BCNF，多值依賴，4NF。模式的分解。數據庫安全保護數據庫安全性控制。數據庫完整性控制。數據庫并發(fā)控制。數據恢復。數據庫設計數據庫設計的概述。需求分析。概念結構設計。邏輯結構設計。數據庫物理設計。數據庫實施。數據庫運行維護。SQLServer2000數據庫管理系統(tǒng)Transact-SQL程序設計：變量，流程控制命令，其他命令，常用函數。存儲過程和觸發(fā)器。備份和還原。軟件工程部分軟件工程基本概念軟件概念軟件工程概念軟件生命周期軟件工程標準與規(guī)范軟件工程過程軟件過程模型軟件開發(fā)工具和環(huán)境軟件工程知識領域軟件項目管理軟件度量軟件項目估算軟件質量度量進度計劃軟件開發(fā)過程管理需求工程軟件需求的基本概念軟件需求工程的過程需求獲取技術用例驅動的需求描述軟件需求規(guī)格說明結構化軟件開發(fā)方法結構化軟件開發(fā)方法概述結構化軟件開發(fā)過程結構化分析與建模結構化軟件結構設計模塊結構的改進及優(yōu)化結構化算法設計面向對象分析與UML建模面向對象分析的基本過程建立功能模型建立對象模型建立動態(tài)模型定義服務面向對象設計面向對象設計原則面向對象設計方法軟件體系結構的設計設計模式用戶界面設計軟件設計復用軟件構建編程語言的特點及選擇軟件編碼規(guī)范代碼重用代碼審查單元測試軟件測試軟件測試的基本概念軟件測試過程和模型集成測試和策略確認測試、系統(tǒng)測試白盒測試技術黑盒測試技術面向對象測試技術軟件自動化測試軟件可靠性軟件架構計算機軟件系統(tǒng)體系結構C/S系統(tǒng)體系結構B/S系統(tǒng)體系結構分布式系統(tǒng)體系結構基于服務的軟件架構二