全國計算機(jī)二級公共基礎(chǔ)知識(要點)課件

1、全國計算機(jī)二級公共基礎(chǔ)知識(要點)1全國計算機(jī)等級考試二級二級公共公共基礎(chǔ)基礎(chǔ)知識知識全國計算機(jī)二級公共基礎(chǔ)知識(要點)2公共基礎(chǔ)知識公共基礎(chǔ)知識內(nèi)容：內(nèi)容： 考試大綱考試大綱 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 軟件工程基礎(chǔ)軟件工程基礎(chǔ) 數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)全國計算機(jī)二級公共基礎(chǔ)知識(要點)3考試大綱考試大綱基本要求基本要求1、掌握算法的基本概念。、掌握算法的基本概念。2、掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。、掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3、掌握基本排序和查找算法。、掌握基本排序和查找算法。4、掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。、掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。5、掌握軟件

2、工程的基本方法，具有初步應(yīng)用、掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6、掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫、掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。的設(shè)計。全國計算機(jī)二級公共基礎(chǔ)知識(要點)4考試大綱考試大綱考試內(nèi)容考試內(nèi)容一、基本數(shù)據(jù)結(jié)構(gòu)與算法一、基本數(shù)據(jù)結(jié)構(gòu)與算法1、算法的基本概念；算法復(fù)雜度的概念和意義、算法的基本概念；算法復(fù)雜度的概念和意義(空間復(fù)雜度與空間復(fù)雜度與時間復(fù)雜度時間復(fù)雜度)。2、數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的

3、概念。的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3、線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入刪除運算。、線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入刪除運算。4、棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。、棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。5、線性單鏈表，雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。、線性單鏈表，雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。6、樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前、樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。序、中序和后序遍歷。7、順序查找與二分查找算法；基本排序算法、順序查找與二分查找算法；基本排序算法(交

4、換類排序、選交換類排序、選擇類排序、插入類排序擇類排序、插入類排序)。全國計算機(jī)二級公共基礎(chǔ)知識(要點)5考試大綱考試大綱考試內(nèi)容考試內(nèi)容二、程序設(shè)計基礎(chǔ)二、程序設(shè)計基礎(chǔ)1、程序設(shè)計方法與風(fēng)格。、程序設(shè)計方法與風(fēng)格。2、結(jié)構(gòu)化程序設(shè)計。、結(jié)構(gòu)化程序設(shè)計。3、面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多、面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。態(tài)性。全國計算機(jī)二級公共基礎(chǔ)知識(要點)6考試大綱考試大綱考試內(nèi)容考試內(nèi)容三、軟件工程基礎(chǔ)三、軟件工程基礎(chǔ)1、軟件工程的基本概念；軟件生命周期概念；軟件工具與軟、軟件工程的基本概念；軟件生命周期概念；軟件工具與軟件開發(fā)環(huán)境。件開發(fā)環(huán)境

5、。2、結(jié)構(gòu)化分析方法；數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說、結(jié)構(gòu)化分析方法；數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。明書。3、結(jié)構(gòu)化設(shè)計方法；、結(jié)構(gòu)化設(shè)計方法； 總體設(shè)計，詳細(xì)設(shè)計。總體設(shè)計，詳細(xì)設(shè)計。4、軟件測試的方法；白盒測試，黑盒測試，測試用例設(shè)計；、軟件測試的方法；白盒測試，黑盒測試，測試用例設(shè)計；軟件測試的實施；單元測試，集成測試，系統(tǒng)測試。軟件測試的實施；單元測試，集成測試，系統(tǒng)測試。5、程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。、程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。全國計算機(jī)二級公共基礎(chǔ)知識(要點)7考試大綱考試大綱考試內(nèi)容考試內(nèi)容四、數(shù)據(jù)庫設(shè)計基礎(chǔ)四、數(shù)據(jù)庫設(shè)計基礎(chǔ)1、數(shù)據(jù)庫的基本概念；數(shù)據(jù)庫

6、，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系、數(shù)據(jù)庫的基本概念；數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。統(tǒng)。2、數(shù)據(jù)模型；實體聯(lián)系模型及、數(shù)據(jù)模型；實體聯(lián)系模型及E-R圖，從圖，從E-R圖導(dǎo)出關(guān)系數(shù)圖導(dǎo)出關(guān)系數(shù)據(jù)模型。據(jù)模型。3、關(guān)系代數(shù)運算，包括集合運算及選擇、投影、連接運算；、關(guān)系代數(shù)運算，包括集合運算及選擇、投影、連接運算；數(shù)據(jù)庫規(guī)范化理論。數(shù)據(jù)庫規(guī)范化理論。4、數(shù)據(jù)庫設(shè)計方法和步驟；需求分析、概念設(shè)計、邏輯設(shè)計、數(shù)據(jù)庫設(shè)計方法和步驟；需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。和物理設(shè)計的相關(guān)策略。全國計算機(jī)二級公共基礎(chǔ)知識(要點)8考試大綱考試大綱考試題型考試題型選擇題選擇題10 題題每題每題 2

7、分分共共 20 分分填空題填空題5 題題每題每題 2 分分共共 10 分分合計合計 30 分分全國計算機(jī)二級公共基礎(chǔ)知識(要點)9數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法關(guān)鍵考點關(guān)鍵考點 算法基本概念及算法復(fù)雜度算法基本概念及算法復(fù)雜度 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 棧和隊列棧和隊列 線性鏈表線性鏈表 二叉樹基本概念及其特性二叉樹基本概念及其特性 查找技術(shù)查找技術(shù)全國計算機(jī)二級公共基礎(chǔ)知識(要點)10數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念算法的基本概念1、算法、算法算法是指解題方案的準(zhǔn)確而完整的描述算法是指解題方案的準(zhǔn)確而完整的描述。注意：算法與數(shù)學(xué)上的計算方法不是同一個概念。算法要考慮計算機(jī)的注意：

8、算法與數(shù)學(xué)上的計算方法不是同一個概念。算法要考慮計算機(jī)的特點，要考慮計算方法的可行性。特點，要考慮計算方法的可行性。算法也不等于程序。算法不考慮具體的機(jī)器及編程語言。解決問題算法也不等于程序。算法不考慮具體的機(jī)器及編程語言。解決問題時，總是先設(shè)計算法，然后進(jìn)行編程。時，總是先設(shè)計算法，然后進(jìn)行編程。2、算法的基本特征、算法的基本特征可行性可行性確定性確定性有窮性有窮性擁有足夠的情報擁有足夠的情報算法是一個動態(tài)概念，強調(diào)實際的執(zhí)行過程。算法是一個動態(tài)概念，強調(diào)實際的執(zhí)行過程。數(shù)學(xué)上的計算方法是一個靜態(tài)概念，注重理論上的正確性。數(shù)學(xué)上的計算方法是一個靜態(tài)概念，注重理論上的正確性。數(shù)學(xué)上的計算方法是

9、設(shè)計算法的基礎(chǔ)。數(shù)學(xué)上的計算方法是設(shè)計算法的基礎(chǔ)。全國計算機(jī)二級公共基礎(chǔ)知識(要點)11數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念算法的基本概念3、算法的基本要素、算法的基本要素算法中對數(shù)據(jù)的運算和操作算法中對數(shù)據(jù)的運算和操作基本的運算和操作有：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸?；镜倪\算和操作有：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu)算法的控制結(jié)構(gòu)控制結(jié)構(gòu)決定操作的執(zhí)行順序。要求符合結(jié)構(gòu)化原則，強調(diào)易讀性?？刂平Y(jié)構(gòu)決定操作的執(zhí)行順序。要求符合結(jié)構(gòu)化原則，強調(diào)易讀性。4、算法設(shè)計基本方法、算法設(shè)計基本方法列舉法列舉法 列舉所有可能情況，檢測其中符合條件的結(jié)果。列舉所有可能

10、情況，檢測其中符合條件的結(jié)果。歸納法歸納法 列舉若干特殊情況，分析歸納出一般規(guī)律。列舉若干特殊情況，分析歸納出一般規(guī)律。遞推遞推 從已知初始條件出發(fā)，逐步推導(dǎo)出中間及最后結(jié)果。從已知初始條件出發(fā)，逐步推導(dǎo)出中間及最后結(jié)果。遞歸遞歸 將復(fù)雜問題歸結(jié)為簡單問題，在歸結(jié)為更簡單問題，將復(fù)雜問題歸結(jié)為簡單問題，在歸結(jié)為更簡單問題， 。減半遞推技術(shù)減半遞推技術(shù) 將問題規(guī)模將問題規(guī)?！皽p半減半”，并重復(fù)該，并重復(fù)該“減半減半” 的過程。的過程?；厮莘ɑ厮莘?分析問題，找出某些線索，沿線索逐步試探。若試探成功，則分析問題，找出某些線索，沿線索逐步試探。若試探成功，則繼續(xù)，若試探失敗，則回退。直至問題解決。繼

11、續(xù)，若試探失敗，則回退。直至問題解決。全國計算機(jī)二級公共基礎(chǔ)知識(要點)12數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念算法的基本概念5、算法的時間復(fù)雜度、算法的時間復(fù)雜度指執(zhí)行算法所需要的計算工作量指執(zhí)行算法所需要的計算工作量算法工作量的度量應(yīng)與計算機(jī)、編程語言、編程細(xì)節(jié)等無關(guān)。算法工作量的度量應(yīng)與計算機(jī)、編程語言、編程細(xì)節(jié)等無關(guān)。算法的工作量用算法的工作量用算法所執(zhí)行的基本運算次數(shù)算法所執(zhí)行的基本運算次數(shù)衡量。衡量。算法工作量是問題規(guī)模的函數(shù)：算法工作量是問題規(guī)模的函數(shù)：算法的工作量算法的工作量= f (n)度量方法有：度量方法有：平均性態(tài)分析平均性態(tài)分析 計算其加權(quán)平均值計算其加權(quán)平均值最

12、壞情況分析最壞情況分析 計算其基本運算的最大次數(shù)計算其基本運算的最大次數(shù)6、算法的空間復(fù)雜度、算法的空間復(fù)雜度指執(zhí)行算法所需要的存儲空間指執(zhí)行算法所需要的存儲空間包括：算法程序所占據(jù)的存儲空間包括：算法程序所占據(jù)的存儲空間待處理數(shù)據(jù)所占據(jù)的存儲空間待處理數(shù)據(jù)所占據(jù)的存儲空間算法程序執(zhí)行中所需要的額外存儲空間算法程序執(zhí)行中所需要的額外存儲空間如果額外存儲空間大小不隨問題規(guī)模變化，則稱之為如果額外存儲空間大小不隨問題規(guī)模變化，則稱之為算法原地工作算法原地工作。降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲空間和額外空間入手。降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲空間和額外空間入手。全國計算機(jī)二級公共基礎(chǔ)知識(

13、要點)13數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。結(jié)構(gòu)結(jié)構(gòu) 通常指前后件關(guān)系。通常指前后件關(guān)系。主要研究：數(shù)據(jù)元素間的固有邏輯關(guān)系主要研究：數(shù)據(jù)元素間的固有邏輯關(guān)系 數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系 對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算2、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)前后件前后件(直接前驅(qū)和

14、直接后繼直接前驅(qū)和直接后繼)關(guān)系就是指邏輯關(guān)系關(guān)系就是指邏輯關(guān)系3、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲形式數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲形式存儲結(jié)構(gòu)也稱為物理結(jié)構(gòu)存儲結(jié)構(gòu)也稱為物理結(jié)構(gòu)同一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)同一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)常用的有：順序、鏈接、索引等形式常用的有：順序、鏈接、索引等形式全國計算機(jī)二級公共基礎(chǔ)知識(要點)14數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念4、數(shù)據(jù)結(jié)構(gòu)的表示、數(shù)據(jù)結(jié)構(gòu)的表示二元關(guān)系表示：二元關(guān)系表示：兩個要素：數(shù)據(jù)元素的集合兩個要素：數(shù)據(jù)元素的集合D，該集合上的關(guān)系，該集合上的關(guān)系R。即：即：

15、B=(D,R)如：如：D=春春,夏夏,秋秋,冬冬 R=(春春,夏夏),(夏夏,秋秋),(秋秋,冬冬)圖形表示：圖形表示：標(biāo)有元素值的方框表示結(jié)點，有向線段表示邏輯關(guān)系。標(biāo)有元素值的方框表示結(jié)點，有向線段表示邏輯關(guān)系。春春 夏夏 秋秋 冬冬5、線性結(jié)構(gòu)和非線性結(jié)構(gòu)、線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)：線性結(jié)構(gòu)：一個非空的線性結(jié)構(gòu)有且只有一個根結(jié)點，每一個非空的線性結(jié)構(gòu)有且只有一個根結(jié)點，每個結(jié)點最多只有一個直接前驅(qū)、最多只有一個直接后繼。個結(jié)點最多只有一個直接前驅(qū)、最多只有一個直接后繼。非線性結(jié)構(gòu)：非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。全國計算機(jī)二級公共基礎(chǔ)知識(要點)15數(shù)據(jù)結(jié)

16、構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表及其順序存儲結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)1、線性表、線性表線性表是由線性表是由 n (n0)個元素組成的有限序列：個元素組成的有限序列：(a1,a2,ai,an)有且只有一個根結(jié)點，它無直接前驅(qū)。有且只有一個根結(jié)點，它無直接前驅(qū)。有且只有一個終端結(jié)點，它無直接后繼。有且只有一個終端結(jié)點，它無直接后繼。除根結(jié)點和終端結(jié)點外，其他所有結(jié)點都有且只有一個直接前驅(qū)和直接后繼。除根結(jié)點和終端結(jié)點外，其他所有結(jié)點都有且只有一個直接前驅(qū)和直接后繼。結(jié)點個數(shù)結(jié)點個數(shù)n稱為線性表的長度。稱為線性表的長度。n=0時，稱為空表。時，稱為空表。2、線性表的順序存儲、線性表的順序存儲順序存儲也

17、稱為順序分配順序存儲也稱為順序分配線性表中所有元素所占的存儲空間是連續(xù)的線性表中所有元素所占的存儲空間是連續(xù)的線性表中各元素在存儲空間中按照邏輯順序依次存儲線性表中各元素在存儲空間中按照邏輯順序依次存儲3、順序表的運算、順序表的運算線性表的順序存儲結(jié)構(gòu)通常稱為線性表的順序存儲結(jié)構(gòu)通常稱為順序表順序表包括：插入、刪除、查找、分解、合并、復(fù)制、逆轉(zhuǎn)等。包括：插入、刪除、查找、分解、合并、復(fù)制、逆轉(zhuǎn)等。在高級語言中，順序表對應(yīng)一維數(shù)組。在高級語言中，順序表對應(yīng)一維數(shù)組。順序表的查找方便，插入和刪除較麻煩。順序表的查找方便，插入和刪除較麻煩。全國計算機(jī)二級公共基礎(chǔ)知識(要點)16數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)

18、與算法線性表及其順序存儲結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)注意：注意： 線性表屬于線性結(jié)構(gòu)。線性表屬于線性結(jié)構(gòu)。 線性表的順序存儲結(jié)構(gòu)通常稱為順序表。線性表的順序存儲結(jié)構(gòu)通常稱為順序表。 在順序表中，所有元素按照其邏輯順序連續(xù)存儲，前后件元素緊鄰，在順序表中，所有元素按照其邏輯順序連續(xù)存儲，前后件元素緊鄰，前件元素一定存儲在后件元素的前面。前件元素一定存儲在后件元素的前面。 在程序設(shè)計語言中，線性表的順序存儲結(jié)構(gòu)對應(yīng)了一維數(shù)組。因為在程序設(shè)計語言中，線性表的順序存儲結(jié)構(gòu)對應(yīng)了一維數(shù)組。因為在程序設(shè)計語言中，一維數(shù)組與計算機(jī)中實際的存儲空間結(jié)構(gòu)是一致在程序設(shè)計語言中，一維數(shù)組與計算機(jī)中實際的存儲空間結(jié)構(gòu)

19、是一致的。的。 在順序表中，如果要在第在順序表中，如果要在第 i 個位置插入一個新元素，則原第個位置插入一個新元素，則原第 i 個元個元素以及之后的所有元素都要依次后移一個位置。在平均情況下，在順?biāo)匾约爸蟮乃性囟家来魏笠埔粋€位置。在平均情況下，在順序表中插入一個新元素，需要移動序表中插入一個新元素，需要移動 n/2 個元素。個元素。 在順序表中，如果要刪除第在順序表中，如果要刪除第 i 個位置的元素，則原第個位置的元素，則原第 i 個元素之后個元素之后的所有元素都要依次前移一個位置。在平均情況下，在順序表中刪除的所有元素都要依次前移一個位置。在平均情況下，在順序表中刪除一個元素，需要移

20、動一個元素，需要移動 n/2 個元素。個元素。 全國計算機(jī)二級公共基礎(chǔ)知識(要點)17數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法棧及其基本運算棧及其基本運算1、棧、棧棧棧(stack)是限定在一端進(jìn)行插入和刪除的線性表是限定在一端進(jìn)行插入和刪除的線性表允許進(jìn)行插入或刪除的一端稱為允許進(jìn)行插入或刪除的一端稱為棧頂棧頂。不允許進(jìn)行插入或刪除的另一端稱為不允許進(jìn)行插入或刪除的另一端稱為棧底棧底。其特點為其特點為“先入后出先入后出”(FILO)或或“后入先出后入先出”(LIFO)。(記憶作用記憶作用)通常設(shè)置指針通常設(shè)置指針top指向棧頂，指針指向棧頂，指針bottom指向棧底。指向棧底。2、棧的順序存儲結(jié)構(gòu)、棧的

21、順序存儲結(jié)構(gòu)棧的各個數(shù)據(jù)元素按其邏輯順序依次連續(xù)存儲。棧的各個數(shù)據(jù)元素按其邏輯順序依次連續(xù)存儲。由于插入刪除操作只能在棧頂一端進(jìn)行，所以由于插入刪除操作只能在棧頂一端進(jìn)行，所以不需要移動數(shù)據(jù)元素。不需要移動數(shù)據(jù)元素。3、棧的基本運算、棧的基本運算入棧入棧：在棧頂位置插入新元素。：在棧頂位置插入新元素。出棧出棧：取出棧頂位置的元素。：取出棧頂位置的元素。讀棧頂元素讀棧頂元素：讀出棧頂位置的元素。：讀出棧頂位置的元素?！吧弦缟弦纭保喝霔r堆棧已滿。：入棧時堆棧已滿。“下溢下溢”：出棧時堆棧：出棧時堆棧已空。已空。全國計算機(jī)二級公共基礎(chǔ)知識(要點)18數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法隊列及其基本運算隊列

22、及其基本運算1、隊列、隊列隊列隊列(queue)是限定在一端進(jìn)行插入另一端進(jìn)行刪除的線性表是限定在一端進(jìn)行插入另一端進(jìn)行刪除的線性表允許進(jìn)行插入的一端稱為允許進(jìn)行插入的一端稱為隊尾隊尾。允許進(jìn)行刪除的另一端稱為允許進(jìn)行刪除的另一端稱為隊頭隊頭。其特點為其特點為“先入先出先入先出”(FIFO)或或“后入后出后入后出”(LILO)。(先來先服務(wù)先來先服務(wù))通常設(shè)置指針通常設(shè)置指針rear指向隊尾，指針指向隊尾，指針front指向隊頭。指向隊頭。2、隊列的順序存儲結(jié)構(gòu)、隊列的順序存儲結(jié)構(gòu)隊列的各個數(shù)據(jù)元素按其邏輯順序依次連續(xù)存儲。隊列的各個數(shù)據(jù)元素按其邏輯順序依次連續(xù)存儲。由于插入刪除操作只能在隊列

23、的兩端進(jìn)行，所以由于插入刪除操作只能在隊列的兩端進(jìn)行，所以不需要移動數(shù)據(jù)元素。不需要移動數(shù)據(jù)元素。3、隊列的基本運算、隊列的基本運算在實際應(yīng)用中常常使用在實際應(yīng)用中常常使用循環(huán)隊列循環(huán)隊列。入隊入隊：在隊尾位置插入新元素。：在隊尾位置插入新元素。 出隊出隊：取出隊頭位置的元素。：取出隊頭位置的元素。 “上溢上溢”：入隊時隊列已滿。：入隊時隊列已滿?！跋乱缦乱纭保撼鲫爼r隊列已空。：出隊時隊列已空。全國計算機(jī)二級公共基礎(chǔ)知識(要點)19數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性鏈表線性鏈表1、鏈?zhǔn)酱鎯Ψ绞?、鏈?zhǔn)酱鎯Ψ绞?結(jié)點由兩部分組成：結(jié)點由兩部分組成：數(shù)據(jù)域數(shù)據(jù)域(存儲數(shù)據(jù)存儲數(shù)據(jù))、指針域指針域(指向

24、其前件或后件指向其前件或后件)。 數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，存儲順序與邏輯關(guān)系可以不一致。數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，存儲順序與邏輯關(guān)系可以不一致。 鏈?zhǔn)酱鎯Ψ绞郊瓤梢杂脕肀硎揪€性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。鏈?zhǔn)酱鎯Ψ绞郊瓤梢杂脕肀硎揪€性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。2、線性鏈表、線性鏈表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表線性鏈表。(棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列)常用的線性鏈表有：常用的線性鏈表有：單鏈表單鏈表 (一個指針域，指向直接后繼一個指針域，指向直接后繼)雙向鏈表雙向鏈表 (兩個指

25、針域，指向直接后繼及后繼兩個指針域，指向直接后繼及后繼) 循環(huán)鏈表循環(huán)鏈表 (所有結(jié)點的指針構(gòu)成循環(huán)鏈所有結(jié)點的指針構(gòu)成循環(huán)鏈)3、線性鏈表的基本運算、線性鏈表的基本運算查找查找：在線性鏈表中查找指定元素。：在線性鏈表中查找指定元素。插入插入：在線性鏈表中插入新結(jié)點。：在線性鏈表中插入新結(jié)點。刪除刪除：在線性鏈表中刪除指定結(jié)點。：在線性鏈表中刪除指定結(jié)點。全國計算機(jī)二級公共基礎(chǔ)知識(要點)20數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹的基本概念樹的基本概念1、樹、樹樹是一種簡單的非線性結(jié)構(gòu)。樹是一種簡單的非線性結(jié)構(gòu)。元素間的關(guān)系具有明顯的層次結(jié)構(gòu)。元素間的關(guān)系具有明顯的層次結(jié)構(gòu)。2、相關(guān)的術(shù)語、相關(guān)的術(shù)語

26、根結(jié)點根結(jié)點葉節(jié)點葉節(jié)點父結(jié)點父結(jié)點子結(jié)點子結(jié)點子樹子樹結(jié)點的度結(jié)點的度樹的度樹的度樹的深度樹的深度全國計算機(jī)二級公共基礎(chǔ)知識(要點)21數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法二叉樹二叉樹1、二叉樹的特點、二叉樹的特點非空二叉樹只有一個根結(jié)點。非空二叉樹只有一個根結(jié)點。每個結(jié)點最多有左右兩棵子樹。每個結(jié)點最多有左右兩棵子樹。2、二叉樹的基本性質(zhì)、二叉樹的基本性質(zhì)第第 k 層上最多有層上最多有 2 k-1個結(jié)點個結(jié)點深度為深度為 m 的二叉樹最多有的二叉樹最多有 2m-1個結(jié)點個結(jié)點任何二叉樹葉結(jié)點總比度為任何二叉樹葉結(jié)點總比度為 2 的節(jié)點多一個的節(jié)點多一個n 個節(jié)點的二叉樹的深度為個節(jié)點的二叉樹的深度

27、為 log2n+13、滿二叉樹、滿二叉樹4、完全二叉樹、完全二叉樹5、二叉樹的遍歷、二叉樹的遍歷先序遍歷先序遍歷 中序遍歷中序遍歷后序遍歷后序遍歷ABDEGCFHI DBGEACHFI DGEBHIFCA全國計算機(jī)二級公共基礎(chǔ)知識(要點)22數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法查找技術(shù)查找技術(shù)1、順序查找、順序查找從線性表的第一個元素開始，依次與指定數(shù)據(jù)比較，若相等則查找成功，從線性表的第一個元素開始，依次與指定數(shù)據(jù)比較，若相等則查找成功，若比較的所有元素都不相等，則查找失敗。若比較的所有元素都不相等，則查找失敗。最壞情況的比較次數(shù)為表長最壞情況的比較次數(shù)為表長n，平均情況為，平均情況為n/2。無序順

28、序表的查找只能采用順序查找的方法。無序順序表的查找只能采用順序查找的方法。線性表在鏈?zhǔn)酱鎯r也只能采用順序查找的方法。線性表在鏈?zhǔn)酱鎯r也只能采用順序查找的方法。2、二分法查找、二分法查找在順序存儲的線性表為有序的情況下，可以使用二分法查找。在順序存儲的線性表為有序的情況下，可以使用二分法查找。方法為：方法為：將待查數(shù)據(jù)與線性表的中間項比較：將待查數(shù)據(jù)與線性表的中間項比較：若相等，則查找成功；若相等，則查找成功；若小于，則在線性表的前半部分進(jìn)行二分法查找；若小于，則在線性表的前半部分進(jìn)行二分法查找；若大于，則在線性表的后半部分進(jìn)行二分法查找；若大于，則在線性表的后半部分進(jìn)行二分法查找；反復(fù)進(jìn)行

29、直到相等反復(fù)進(jìn)行直到相等(查找成功查找成功)或子表長度為或子表長度為0(查找失敗查找失敗)。全國計算機(jī)二級公共基礎(chǔ)知識(要點)23數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法排序技術(shù)排序技術(shù)1、交換類排序、交換類排序起泡排序起泡排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 快速排序快速排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 2、插入類排序、插入類排序簡單插入排序簡單插入排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。 希爾排序希爾排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 O( n 1.5) 。3、選擇類排序、選擇類排序簡單

30、選擇排序簡單選擇排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 n(n-1)/2 。堆排序堆排序最壞情況下的比較次數(shù)為最壞情況下的比較次數(shù)為 O( n log2n) 。全國計算機(jī)二級公共基礎(chǔ)知識(要點)24數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法本章重點本章重點1、算法是問題處理方案正確而完整的描述，算法的效率與數(shù)據(jù)的存儲結(jié)構(gòu)、算法是問題處理方案正確而完整的描述，算法的效率與數(shù)據(jù)的存儲結(jié)構(gòu)有密切的關(guān)系。有密切的關(guān)系。2、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示(存儲方式存儲方式)稱為數(shù)據(jù)的存儲結(jié)構(gòu)稱為數(shù)據(jù)的存儲結(jié)構(gòu)(物理物理結(jié)構(gòu)結(jié)構(gòu))。一種邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。一種邏輯結(jié)構(gòu)可

31、以有多種存儲結(jié)構(gòu)。3、在長度為、在長度為 n 的順序表中，插入或刪除一個元素平均需要移動一半元素。的順序表中，插入或刪除一個元素平均需要移動一半元素。4、棧是特殊的線性表，具有記憶作用。特點是、棧是特殊的線性表，具有記憶作用。特點是“先進(jìn)后出先進(jìn)后出(后進(jìn)先出后進(jìn)先出)”。棧。棧頂指針動態(tài)反映了棧中元素的變化情況。頂指針動態(tài)反映了棧中元素的變化情況。5、隊列是特殊的線性表。特點是、隊列是特殊的線性表。特點是“先進(jìn)先出先進(jìn)先出(后進(jìn)后出后進(jìn)后出)”。隊頭和隊尾指針。隊頭和隊尾指針動態(tài)地反映了隊列中元素的變化情況。動態(tài)地反映了隊列中元素的變化情況。6、線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。在線性鏈表中，

32、各元素節(jié)點的存儲、線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。在線性鏈表中，各元素節(jié)點的存儲空間可以不連續(xù)，存儲順序也可以與邏輯順序不一致。線性鏈表的插入空間可以不連續(xù)，存儲順序也可以與邏輯順序不一致。線性鏈表的插入刪除操作不需要移動數(shù)據(jù)元素。刪除操作不需要移動數(shù)據(jù)元素。7、二叉樹是一種非線性結(jié)構(gòu)。主要性質(zhì)有：、二叉樹是一種非線性結(jié)構(gòu)。主要性質(zhì)有：第第k層上最多有層上最多有 2 k-1 個結(jié)點個結(jié)點深度為深度為 m 時，最多有時，最多有2 m 1 個結(jié)點個結(jié)點度為度為0的結(jié)點比度為的結(jié)點比度為2的多一個的多一個深度至少為深度至少為 log2n +1全國計算機(jī)二級公共基礎(chǔ)知識(要點)25數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)

33、構(gòu)與算法本章重點本章重點8、滿二叉樹是二叉樹的特殊形態(tài)，滿二叉樹的各層結(jié)點都達(dá)到最大值，葉、滿二叉樹是二叉樹的特殊形態(tài)，滿二叉樹的各層結(jié)點都達(dá)到最大值，葉結(jié)點只出現(xiàn)在最后一層。結(jié)點只出現(xiàn)在最后一層。9、完全二叉樹是二叉樹的特殊形態(tài)，完全二叉樹除最后一層外，各層結(jié)點、完全二叉樹是二叉樹的特殊形態(tài)，完全二叉樹除最后一層外，各層結(jié)點都達(dá)到最大值，葉結(jié)點只出現(xiàn)在最后兩層。滿二叉樹屬于完全二叉樹。都達(dá)到最大值，葉結(jié)點只出現(xiàn)在最后兩層。滿二叉樹屬于完全二叉樹。10、根據(jù)掃描根結(jié)點的順序，按照先左后右的原則，遍歷二叉樹有三種、根據(jù)掃描根結(jié)點的順序，按照先左后右的原則，遍歷二叉樹有三種方法：前序遍歷、中序遍歷

34、、后序遍歷。方法：前序遍歷、中序遍歷、后序遍歷。11、在長度為、在長度為 n 的線性表中進(jìn)行順序查找，最壞情況需要比較的線性表中進(jìn)行順序查找，最壞情況需要比較 n 次。次。12、在長度為、在長度為 n 的線性表中進(jìn)行對分查找，最壞情況需要比較的線性表中進(jìn)行對分查找，最壞情況需要比較 log2n 次。但次。但對分查找只適用于有序順序表。對分查找只適用于有序順序表。13、在冒泡排序、快速排序、簡單插入排序、選擇排序的方法中，最壞情況、在冒泡排序、快速排序、簡單插入排序、選擇排序的方法中，最壞情況下需要比較的次數(shù)為下需要比較的次數(shù)為 n(n-1)/2 。全國計算機(jī)二級公共基礎(chǔ)知識(要點)26程序設(shè)計

35、基礎(chǔ)程序設(shè)計基礎(chǔ)關(guān)鍵考點關(guān)鍵考點 結(jié)構(gòu)化設(shè)計的原則結(jié)構(gòu)化設(shè)計的原則 面向?qū)ο蠓椒ǖ幕靖拍蠲嫦驅(qū)ο蠓椒ǖ幕靖拍钊珖嬎銠C(jī)二級公共基礎(chǔ)知識(要點)27程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)程序設(shè)計方法與風(fēng)格程序設(shè)計方法與風(fēng)格1、程序設(shè)計方法、程序設(shè)計方法就程序設(shè)計的方法和技術(shù)的發(fā)展而言就程序設(shè)計的方法和技術(shù)的發(fā)展而言主要經(jīng)歷了主要經(jīng)歷了結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計和和面向?qū)ο蟪绦蛟O(shè)計面向?qū)ο蟪绦蛟O(shè)計兩個階段兩個階段2、程序設(shè)計風(fēng)格、程序設(shè)計風(fēng)格程序設(shè)計風(fēng)格是指編寫程序時所表現(xiàn)出來的程序設(shè)計風(fēng)格是指編寫程序時所表現(xiàn)出來的特點特點、習(xí)慣習(xí)慣和和邏輯思路邏輯思路。程序設(shè)計風(fēng)格會深刻影響軟件的質(zhì)量和可維護(hù)性，良好的

36、程序設(shè)計風(fēng)格程序設(shè)計風(fēng)格會深刻影響軟件的質(zhì)量和可維護(hù)性，良好的程序設(shè)計風(fēng)格可以使程序的結(jié)構(gòu)清晰合理，使程序代碼便于維護(hù)。可以使程序的結(jié)構(gòu)清晰合理，使程序代碼便于維護(hù)。程序設(shè)計風(fēng)格的主導(dǎo)：程序設(shè)計風(fēng)格的主導(dǎo)：“清晰第一清晰第一，效率第二效率第二”。主要因素：主要因素：源程序文檔化源程序文檔化數(shù)據(jù)說明的方法數(shù)據(jù)說明的方法語句的結(jié)構(gòu)語句的結(jié)構(gòu)輸入和輸出輸入和輸出全國計算機(jī)二級公共基礎(chǔ)知識(要點)28程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計1、結(jié)構(gòu)化程序設(shè)計、結(jié)構(gòu)化程序設(shè)計要求把程序的結(jié)構(gòu)限制為順序、選擇和循環(huán)三種基本結(jié)構(gòu)。要求把程序的結(jié)構(gòu)限制為順序、選擇和循環(huán)三種基本結(jié)構(gòu)。2、結(jié)構(gòu)化程序

37、設(shè)計的原則、結(jié)構(gòu)化程序設(shè)計的原則自頂向下自頂向下先總體后細(xì)節(jié)，先全局后局部。先總體后細(xì)節(jié)，先全局后局部。逐步求精逐步求精對復(fù)雜問題設(shè)計子目標(biāo)過度，逐步細(xì)化。對復(fù)雜問題設(shè)計子目標(biāo)過度，逐步細(xì)化。模塊化模塊化將復(fù)雜問題分解為若干簡單問題。將復(fù)雜問題分解為若干簡單問題。限制使用限制使用GOTO語句語句防止造成程序邏輯結(jié)構(gòu)混亂。防止造成程序邏輯結(jié)構(gòu)混亂。3、三種基本結(jié)構(gòu)、三種基本結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu) 選擇結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)4、特點、特點所有控制結(jié)構(gòu)由三種基本結(jié)構(gòu)組成所有控制結(jié)構(gòu)由三種基本結(jié)構(gòu)組成各個模塊單入口單出口各個模塊單入口單出口模塊的內(nèi)聚性強模塊的內(nèi)聚性強 模塊間的偶合性低模塊間的偶合

38、性低全國計算機(jī)二級公共基礎(chǔ)知識(要點)29程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計1、面向?qū)ο?、面向?qū)ο竺嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，是從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，用現(xiàn)面向?qū)ο蠓椒ǖ谋举|(zhì)，是從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，用現(xiàn)實生活中常用的思維方法來描述客觀事物，是系統(tǒng)中的對象及對象間的實生活中常用的思維方法來描述客觀事物，是系統(tǒng)中的對象及對象間的關(guān)系能如實反映事物及其關(guān)系。關(guān)系能如實反映事物及其關(guān)系。2、主要優(yōu)點、主要優(yōu)點與人類習(xí)慣的思維方法一致與人類習(xí)慣的思維方法一致穩(wěn)定性好穩(wěn)定性好可重用性好可重用性好易于開發(fā)大型軟件產(chǎn)品易于開發(fā)大型軟件產(chǎn)品可維護(hù)性好可維護(hù)性好3、基

39、本概念、基本概念對象對象類和實例類和實例消息消息繼承繼承多態(tài)性多態(tài)性全國計算機(jī)二級公共基礎(chǔ)知識(要點)30程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)本章重點本章重點1、程序設(shè)計并不等于編程，編程只是程序設(shè)計過程中的一小步。、程序設(shè)計并不等于編程，編程只是程序設(shè)計過程中的一小步。2、結(jié)構(gòu)化程序設(shè)計要求把程序的結(jié)構(gòu)限制為順序、選擇、循環(huán)三種基本結(jié)、結(jié)構(gòu)化程序設(shè)計要求把程序的結(jié)構(gòu)限制為順序、選擇、循環(huán)三種基本結(jié)構(gòu)。構(gòu)。3、模塊化設(shè)計是指把一個大程序按人們能理解的大小規(guī)模進(jìn)行分解。劃分、模塊化設(shè)計是指把一個大程序按人們能理解的大小規(guī)模進(jìn)行分解。劃分模塊的基本原則是使每個模塊都易于理解。在按功能劃分模塊時，要求模塊的基本

40、原則是使每個模塊都易于理解。在按功能劃分模塊時，要求各模塊功能盡量單一，各模塊之間的聯(lián)系盡量的少。各模塊功能盡量單一，各模塊之間的聯(lián)系盡量的少。4、客觀世界是由實體及其聯(lián)系所組成的?？陀^世界中的實體稱為問題域的、客觀世界是由實體及其聯(lián)系所組成的。客觀世界中的實體稱為問題域的對象。對象。5、類描述的是具有相似性質(zhì)一組對象。一個對象稱為類的實例。、類描述的是具有相似性質(zhì)一組對象。一個對象稱為類的實例。6、允許作用于某個對象上的各種操作稱為方法。、允許作用于某個對象上的各種操作稱為方法。7、消息是用來請求對象執(zhí)行某一處理或回答某些信息的要求。、消息是用來請求對象執(zhí)行某一處理或回答某些信息的要求。8、

41、繼承是表示類之間的相似性的一種機(jī)制。、繼承是表示類之間的相似性的一種機(jī)制。9、封裝是一種信息隱蔽機(jī)制，目的是將對象的使用者與對象的設(shè)計者分開。、封裝是一種信息隱蔽機(jī)制，目的是將對象的使用者與對象的設(shè)計者分開。用戶只需了解對象封裝界面上的信息，不必知道內(nèi)部的具體細(xì)節(jié)。用戶只需了解對象封裝界面上的信息，不必知道內(nèi)部的具體細(xì)節(jié)。全國計算機(jī)二級公共基礎(chǔ)知識(要點)31軟件工程基礎(chǔ)軟件工程基礎(chǔ)關(guān)鍵考點關(guān)鍵考點 軟件定義與特點軟件定義與特點 軟件開發(fā)過程的過程化原則軟件開發(fā)過程的過程化原則 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法 結(jié)構(gòu)化設(shè)計方法結(jié)構(gòu)化設(shè)計方法 軟件測試技術(shù)與方法軟件測試技術(shù)與方法 程序調(diào)試基本概念程

42、序調(diào)試基本概念全國計算機(jī)二級公共基礎(chǔ)知識(要點)32軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件工程基本概念軟件工程基本概念1、軟件、軟件軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。2、軟件的特點、軟件的特點抽象性抽象性可大量拷貝可大量拷貝無磨損及老化問題無磨損及老化問題受計算機(jī)系統(tǒng)限制受計算機(jī)系統(tǒng)限制(移植問題移植問題)復(fù)雜性高成本昂貴復(fù)雜性高成本昂貴開發(fā)過程涉及諸多社會因素開發(fā)過程涉及諸多社會因素3、軟件工程、軟件工程軟件工程是應(yīng)用于計算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、軟件工程是應(yīng)用于計算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。

43、文檔、實踐標(biāo)準(zhǔn)和工序。三個要素三個要素方法：完成軟件工程項目的技術(shù)手段。方法：完成軟件工程項目的技術(shù)手段。工具：支持軟件的開發(fā)、管理、文檔生成。工具：支持軟件的開發(fā)、管理、文檔生成。過程：支持軟件開發(fā)各個環(huán)節(jié)的管理、控制。過程：支持軟件開發(fā)各個環(huán)節(jié)的管理、控制。目標(biāo)目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可適應(yīng)性、可追蹤性、可互操作性滿足用戶要求的軟件產(chǎn)品。可維護(hù)性、可適應(yīng)性、可追蹤性、可互操作性滿足用戶要求的軟件產(chǎn)品。全國計算機(jī)二級公共基礎(chǔ)知識(要點)33軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件開發(fā)過程的

44、過程化原則軟件開發(fā)過程的過程化原則1、軟件工程過程、軟件工程過程 為獲得軟件產(chǎn)品，在軟件工具支持下的一系列軟件工程活動。為獲得軟件產(chǎn)品，在軟件工具支持下的一系列軟件工程活動。Plan軟件規(guī)格說明。軟件規(guī)格說明。Do軟件開發(fā)。軟件開發(fā)。Check軟件確認(rèn)。軟件確認(rèn)。Action 軟件演進(jìn)。軟件演進(jìn)。 使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動，在過程結(jié)束時將使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動，在過程結(jié)束時將用戶要求轉(zhuǎn)化為軟件產(chǎn)品。用戶要求轉(zhuǎn)化為軟件產(chǎn)品。軟件工程過程應(yīng)確定軟件工程過程應(yīng)確定方法使用的順序方法使用的順序、要求交付的文檔資料要求交付的文檔資料、為保證質(zhì)為保證質(zhì)量與適應(yīng)變化

45、所需要的管理量與適應(yīng)變化所需要的管理、軟件開發(fā)各階段要完成的任務(wù)軟件開發(fā)各階段要完成的任務(wù)。2、軟件生命周期、軟件生命周期 定義階段定義階段可行性研究及項目計劃可行性研究及項目計劃需求分析需求分析 開發(fā)階段開發(fā)階段概要設(shè)計概要設(shè)計詳細(xì)設(shè)計詳細(xì)設(shè)計實現(xiàn)實現(xiàn)測試測試 維護(hù)階段維護(hù)階段使用使用維護(hù)維護(hù)退役退役全國計算機(jī)二級公共基礎(chǔ)知識(要點)34軟件工程基礎(chǔ)軟件工程基礎(chǔ)結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法在系統(tǒng)分析階段，結(jié)構(gòu)化分析方法用來對系統(tǒng)進(jìn)行邏輯設(shè)計。在系統(tǒng)分析階段，結(jié)構(gòu)化分析方法用來對系統(tǒng)進(jìn)行邏輯設(shè)計。1、需求分析、需求分析需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求。需求分析的任務(wù)是發(fā)現(xiàn)需求、求

46、精、建模和定義需求。 常見的需求分析方法：常見的需求分析方法：結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法 面向?qū)ο蟮姆治龇椒嫦驅(qū)ο蟮姆治龇椒?、結(jié)構(gòu)化分析方法、結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析就是使用結(jié)構(gòu)化分析就是使用數(shù)據(jù)流圖數(shù)據(jù)流圖(DFD)、數(shù)據(jù)字典數(shù)據(jù)字典(DD)、結(jié)構(gòu)化英語結(jié)構(gòu)化英語、判判定表定表和和判定樹判定樹等工具，來建立一種被稱為結(jié)構(gòu)化規(guī)格說明的目標(biāo)文檔。等工具，來建立一種被稱為結(jié)構(gòu)化規(guī)格說明的目標(biāo)文檔。 結(jié)構(gòu)化分析方法的實質(zhì)是著眼于數(shù)據(jù)流的、自頂向下逐層分解的、建立結(jié)構(gòu)化分析方法的實質(zhì)是著眼于數(shù)據(jù)流的、自頂向下逐層分解的、建立系統(tǒng)的處理流程，它以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏系統(tǒng)的處

47、理流程，它以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。輯模型。3、 軟件需求規(guī)格說明書軟件需求規(guī)格說明書是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。軟件需求規(guī)格說明書把軟件計劃中確定的軟件范圍加以展開，制定出完軟件需求規(guī)格說明書把軟件計劃中確定的軟件范圍加以展開，制定出完整的信息描述、詳細(xì)的功能說明、恰當(dāng)?shù)臋z驗標(biāo)準(zhǔn)、其他與要求有關(guān)的整的信息描述、詳細(xì)的功能說明、恰當(dāng)?shù)臋z驗標(biāo)準(zhǔn)、其他與要求有關(guān)的信息。信息。全國計算機(jī)二級公共基礎(chǔ)知識(要點)35軟件工程基礎(chǔ)軟件工程基礎(chǔ)結(jié)構(gòu)化設(shè)計方法結(jié)構(gòu)化設(shè)計方法1、軟件設(shè)計、軟件設(shè)計軟件設(shè)計是把

48、軟件需求轉(zhuǎn)換為軟件表示的過程。軟件設(shè)計是把軟件需求轉(zhuǎn)換為軟件表示的過程。從技術(shù)角度：軟件設(shè)計包括結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。從技術(shù)角度：軟件設(shè)計包括結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。從工程角度：軟件設(shè)計包括概要設(shè)計、詳細(xì)設(shè)計。從工程角度：軟件設(shè)計包括概要設(shè)計、詳細(xì)設(shè)計。軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱蔽、模塊獨立性軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱蔽、模塊獨立性2、概要設(shè)計、概要設(shè)計概要設(shè)計的基本任務(wù)：概要設(shè)計的基本任務(wù)：系統(tǒng)結(jié)構(gòu)設(shè)計系統(tǒng)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計編寫設(shè)計文檔編寫設(shè)計文檔設(shè)計文檔評審設(shè)計文檔評審結(jié)構(gòu)圖是軟件結(jié)構(gòu)設(shè)計的常用工具。結(jié)構(gòu)圖

49、是軟件結(jié)構(gòu)設(shè)計的常用工具。3、詳細(xì)設(shè)計、詳細(xì)設(shè)計詳細(xì)設(shè)計的任務(wù)，是為軟件結(jié)構(gòu)圖中的每一個模塊確定算法和局部數(shù)據(jù)詳細(xì)設(shè)計的任務(wù)，是為軟件結(jié)構(gòu)圖中的每一個模塊確定算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。結(jié)構(gòu)，用某種選定的工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。常見的設(shè)計工具：常見的設(shè)計工具：圖形工具：流程圖、圖形工具：流程圖、N - S、PAD、HIPO表格工具：判定表表格工具：判定表語言工具：語言工具：PDL(偽碼偽碼)全國計算機(jī)二級公共基礎(chǔ)知識(要點)36軟件工程基礎(chǔ)軟件工程基礎(chǔ)軟件測試軟件測試1、測試、測試軟件測試的目標(biāo)是在精心控制的環(huán)境下執(zhí)行程序，以發(fā)現(xiàn)程序中的錯誤，軟件測試的

50、目標(biāo)是在精心控制的環(huán)境下執(zhí)行程序，以發(fā)現(xiàn)程序中的錯誤，給出程序可靠性的鑒定。給出程序可靠性的鑒定。測試不是為了證明程序是正確的，目的是設(shè)法暴露程序中的錯誤和缺陷。測試不是為了證明程序是正確的，目的是設(shè)法暴露程序中的錯誤和缺陷。測試只能說明程序有錯，不能證明程序無錯。程序不能測試只能說明程序有錯，不能證明程序無錯。程序不能100%可靠?？煽俊?、測試方法、測試方法程序的靜態(tài)分析程序的靜態(tài)分析程序的動態(tài)分析程序的動態(tài)分析自動測試工具自動測試工具3、測試層次、測試層次模塊測試模塊測試(單元測試單元測試)整體測試整體測試(集成測試集成測試)又分為又分為 功能測試功能測試 和和 驗收測試驗收測試 兩種。

51、兩種。4、白盒法、白盒法根據(jù)對程序內(nèi)部邏輯結(jié)構(gòu)的分析來導(dǎo)出測試用例。根據(jù)對程序內(nèi)部邏輯結(jié)構(gòu)的分析來導(dǎo)出測試用例。5、黑盒法、黑盒法不考慮程序的內(nèi)部結(jié)構(gòu)特征，根據(jù)程序功能導(dǎo)出測試用例。不考慮程序的內(nèi)部結(jié)構(gòu)特征，根據(jù)程序功能導(dǎo)出測試用例。全國計算機(jī)二級公共基礎(chǔ)知識(要點)37軟件工程基礎(chǔ)軟件工程基礎(chǔ)程序調(diào)試程序調(diào)試1、調(diào)試與測試、調(diào)試與測試 測試的目的是發(fā)現(xiàn)錯誤，評價可靠性；調(diào)試的目的是發(fā)現(xiàn)錯誤的位置，測試的目的是發(fā)現(xiàn)錯誤，評價可靠性；調(diào)試的目的是發(fā)現(xiàn)錯誤的位置，改正發(fā)現(xiàn)的錯誤。改正發(fā)現(xiàn)的錯誤。 測試揭示設(shè)計人員的過失，由非設(shè)計人員承擔(dān)；調(diào)試幫助設(shè)計人員改正錯誤，測試揭示設(shè)計人員的過失，由非設(shè)計人

52、員承擔(dān)；調(diào)試幫助設(shè)計人員改正錯誤，由設(shè)計人員自己承擔(dān)。由設(shè)計人員自己承擔(dān)。 測試是機(jī)械的、強制的、嚴(yán)格的、可預(yù)測的；調(diào)試要求隨機(jī)應(yīng)變、聯(lián)想、經(jīng)測試是機(jī)械的、強制的、嚴(yán)格的、可預(yù)測的；調(diào)試要求隨機(jī)應(yīng)變、聯(lián)想、經(jīng)驗、智力，并要求自主地完成。驗、智力，并要求自主地完成。 測試發(fā)現(xiàn)的錯誤可立即進(jìn)行調(diào)試改正，然后還必須再進(jìn)行測試。測試發(fā)現(xiàn)的錯誤可立即進(jìn)行調(diào)試改正，然后還必須再進(jìn)行測試。 調(diào)試用例與測試用例可以一致也可以不一致。調(diào)試用例與測試用例可以一致也可以不一致。2、調(diào)試方法、調(diào)試方法 強行排錯法強行排錯法 回溯法回溯法 原因排除法原因排除法全國計算機(jī)二級公共基礎(chǔ)知識(要點)38軟件工程基礎(chǔ)軟件工程基

53、礎(chǔ)本章重點本章重點1、軟件生命周期分為三個時期共八個階段：、軟件生命周期分為三個時期共八個階段：軟件定義期：問題定義、可行性研究、需求分析。軟件定義期：問題定義、可行性研究、需求分析。軟件開發(fā)期：系統(tǒng)設(shè)計、詳細(xì)設(shè)計、編碼、測試。軟件開發(fā)期：系統(tǒng)設(shè)計、詳細(xì)設(shè)計、編碼、測試。軟件維護(hù)期：運行維護(hù)。軟件維護(hù)期：運行維護(hù)。2、在系統(tǒng)分析階段，結(jié)構(gòu)化分析方法用來對系統(tǒng)進(jìn)行邏輯設(shè)計，此時不考慮物理、在系統(tǒng)分析階段，結(jié)構(gòu)化分析方法用來對系統(tǒng)進(jìn)行邏輯設(shè)計，此時不考慮物理實現(xiàn)的問題，而只考慮實現(xiàn)的問題，而只考慮“做什么做什么”的問題，系統(tǒng)的物理設(shè)計的問題，系統(tǒng)的物理設(shè)計(“如何做如何做”)的問題的問題留在系統(tǒng)設(shè)

54、計階段用結(jié)構(gòu)化設(shè)計方法來完成。留在系統(tǒng)設(shè)計階段用結(jié)構(gòu)化設(shè)計方法來完成。3、數(shù)據(jù)流圖有兩種典型的結(jié)構(gòu)形式：變換型、事務(wù)型。、數(shù)據(jù)流圖有兩種典型的結(jié)構(gòu)形式：變換型、事務(wù)型。4、評價模塊的獨立性的標(biāo)準(zhǔn)有兩個：、評價模塊的獨立性的標(biāo)準(zhǔn)有兩個：耦合性：表明兩個模塊間聯(lián)系的強弱。耦合性：表明兩個模塊間聯(lián)系的強弱。內(nèi)聚性：表明模塊內(nèi)部聯(lián)系是否緊密。內(nèi)聚性：表明模塊內(nèi)部聯(lián)系是否緊密。內(nèi)聚性要強，偶合性要弱。內(nèi)聚性要強，偶合性要弱。5、軟件測試是在精心控制的環(huán)境下執(zhí)行程序，發(fā)現(xiàn)程序中的錯誤，給出程序可靠、軟件測試是在精心控制的環(huán)境下執(zhí)行程序，發(fā)現(xiàn)程序中的錯誤，給出程序可靠性的鑒定。性的鑒定。6、測試是程序執(zhí)行的

55、過程，目的在于發(fā)現(xiàn)錯誤；一個好的測試在于能發(fā)現(xiàn)至今未、測試是程序執(zhí)行的過程，目的在于發(fā)現(xiàn)錯誤；一個好的測試在于能發(fā)現(xiàn)至今未能發(fā)現(xiàn)的錯誤，一個成功的測試是發(fā)現(xiàn)了至今未發(fā)現(xiàn)的錯誤。能發(fā)現(xiàn)的錯誤，一個成功的測試是發(fā)現(xiàn)了至今未發(fā)現(xiàn)的錯誤。7、測試發(fā)現(xiàn)錯誤后，可進(jìn)行調(diào)試；調(diào)試后的程序還應(yīng)再測試，以檢驗調(diào)試效果。、測試發(fā)現(xiàn)錯誤后，可進(jìn)行調(diào)試；調(diào)試后的程序還應(yīng)再測試，以檢驗調(diào)試效果。全國計算機(jī)二級公共基礎(chǔ)知識(要點)39數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)關(guān)鍵考點關(guān)鍵考點 數(shù)據(jù)庫系統(tǒng)基本概念數(shù)據(jù)庫系統(tǒng)基本概念 數(shù)據(jù)模型數(shù)據(jù)模型全國計算機(jī)二級公共基礎(chǔ)知識(要點)40數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)

56、庫系統(tǒng)的基本概念1、數(shù)據(jù)庫、數(shù)據(jù)庫 DB是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)中，是多是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)中，是多種應(yīng)用數(shù)據(jù)的集成，可被各個應(yīng)用程序所共享。種應(yīng)用數(shù)據(jù)的集成，可被各個應(yīng)用程序所共享。2、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng) DBMS數(shù)據(jù)庫的管理機(jī)構(gòu)，系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)組織、操縱、維護(hù)、控制、保數(shù)據(jù)庫的管理機(jī)構(gòu)，系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)組織、操縱、維護(hù)、控制、保護(hù)等。護(hù)等。為數(shù)據(jù)庫構(gòu)作模式為數(shù)據(jù)庫構(gòu)作模式為數(shù)據(jù)模式的實現(xiàn)提供方法和手段為數(shù)據(jù)模式的實現(xiàn)提供方法和手段為用戶使用提供查詢、插入、修改、刪除等功能為用戶使用提供查詢、插入、修改、刪除等

57、功能提供對數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能提供對數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能(復(fù)制、重組、檢測等復(fù)制、重組、檢測等)。3、DBMS提供的語言提供的語言數(shù)據(jù)定義語言數(shù)據(jù)定義語言數(shù)據(jù)操縱語言數(shù)據(jù)操縱語言數(shù)據(jù)控制語言數(shù)據(jù)控制語言全國計算機(jī)二級公共基礎(chǔ)知識(要點)41數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)庫系統(tǒng)的基本概念4、數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)庫系統(tǒng) DBS由由DB、DBMS、數(shù)據(jù)庫管理員、數(shù)據(jù)庫管理員(DBA)、硬件平臺、軟件平臺組成。、硬件平臺、軟件平臺組成。5、數(shù)據(jù)庫系統(tǒng)的基本特點、數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)的集成性數(shù)據(jù)的集成性數(shù)據(jù)的高共享性低冗余性數(shù)據(jù)的高共享性低冗余性數(shù)據(jù)的獨立性數(shù)據(jù)的獨立性

58、數(shù)據(jù)統(tǒng)一管理和控制數(shù)據(jù)統(tǒng)一管理和控制6、數(shù)據(jù)庫系統(tǒng)的三級模式、數(shù)據(jù)庫系統(tǒng)的三級模式概念模式概念模式：數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)的邏輯描述，與具體的軟硬件環(huán)境無關(guān)。數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)的邏輯描述，與具體的軟硬件環(huán)境無關(guān)。外模式外模式：也叫用戶模式，是用戶的數(shù)據(jù)視圖。也叫用戶模式，是用戶的數(shù)據(jù)視圖。內(nèi)模式內(nèi)模式：也叫物理模式，描述數(shù)據(jù)庫中數(shù)據(jù)的存儲結(jié)構(gòu)和存取方式。也叫物理模式，描述數(shù)據(jù)庫中數(shù)據(jù)的存儲結(jié)構(gòu)和存取方式。全國計算機(jī)二級公共基礎(chǔ)知識(要點)42數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)模型數(shù)據(jù)模型1、三種不同應(yīng)用層次的數(shù)據(jù)模型、三種不同應(yīng)用層次的數(shù)據(jù)模型概念模型概念模型：概念數(shù)據(jù)模型，面向客觀世界、面向用戶，與具

59、體的概念數(shù)據(jù)模型，面向客觀世界、面向用戶，與具體的DBMS無關(guān)。無關(guān)。數(shù)據(jù)模型數(shù)據(jù)模型：邏輯數(shù)據(jù)模型，面向邏輯數(shù)據(jù)模型，面向DBS的模型，著重于數(shù)據(jù)庫系統(tǒng)的實現(xiàn)。的模型，著重于數(shù)據(jù)庫系統(tǒng)的實現(xiàn)。物理模型物理模型：物理數(shù)據(jù)模型，面向計算機(jī)系統(tǒng)，是數(shù)據(jù)模型的物理表示。物理數(shù)據(jù)模型，面向計算機(jī)系統(tǒng)，是數(shù)據(jù)模型的物理表示。2、實體集之間的聯(lián)系、實體集之間的聯(lián)系一對一一對一一對多或多對一一對多或多對一多對多多對多3、E - R模型的圖示法模型的圖示法實體集表示法實體集表示法：在：在E - R圖中用矩形表示實體集，矩形內(nèi)注明實體集名稱。圖中用矩形表示實體集，矩形內(nèi)注明實體集名稱。屬性表示法屬性表示法：在：

60、在E - R圖中用橢圓，橢圓中注明屬性名稱。圖中用橢圓，橢圓中注明屬性名稱。聯(lián)系表示法聯(lián)系表示法：在：在E - R圖中用菱形表示聯(lián)系，菱形中注明聯(lián)系名稱。圖中用菱形表示聯(lián)系，菱形中注明聯(lián)系名稱。實體集與屬性之間的連接關(guān)系實體集與屬性之間的連接關(guān)系：在：在E - R圖中用連接兩個圖形的無向線段表示。圖中用連接兩個圖形的無向線段表示。全國計算機(jī)二級公共基礎(chǔ)知識(要點)43數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)模型數(shù)據(jù)模型4、層次模型、層次模型 層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)。層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)。5、網(wǎng)狀模型、網(wǎng)狀模型網(wǎng)狀模型是一個不加任何條件限制的無向圖。網(wǎng)狀模型是一個不加任何條件限制的無向圖。