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

2、序存儲(chǔ)結(jié)構(gòu)及其插入刪除運(yùn)算。4、棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5、線性單鏈表，雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6、樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7、順序查找與二分查找算法；基本排序算法(交換類排序、選擇類排序、插入類排序)。4考試大綱考試內(nèi)容三、軟件工程基礎(chǔ)1、軟件工程的基本概念；軟件生命周期概念；軟件工具與軟件開發(fā)環(huán)境。2、結(jié)構(gòu)化分析方法；數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3、結(jié)構(gòu)化設(shè)計(jì)方法； 總體設(shè)計(jì)，詳細(xì)設(shè)計(jì)。4、軟件測試的方法；白盒測試，黑盒測試，測試用例設(shè)計(jì)；軟件測試的實(shí)施；單元測試，集成測試，系統(tǒng)測試。5、程

3、序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。6考試大綱考試內(nèi)容四、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)1、數(shù)據(jù)庫的基本概念；數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2、數(shù)據(jù)模型；實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3、關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算；數(shù)據(jù)庫規(guī)范化理論。4、數(shù)據(jù)庫設(shè)計(jì)方法和步驟；需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。7數(shù)據(jù)結(jié)構(gòu)與算法關(guān)鍵考點(diǎn)算法基本概念及算法復(fù)雜度數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)棧和隊(duì)列線性鏈表二叉樹基本概念及其特性查找技術(shù)9數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念1、算法算法是指解題方案的準(zhǔn)確而完整的描述。注意：算法與數(shù)學(xué)上的計(jì)算方法不是同一個(gè)概念。算法要考慮計(jì)算機(jī)的特點(diǎn)，要考慮計(jì)算方

4、法的可行性。算法也不等于程序。算法不考慮具體的機(jī)器及編程語言。解決問題時(shí)，總是先設(shè)計(jì)算法，然后進(jìn)行編程。2、算法的基本特征可行性確定性有窮性擁有足夠的情報(bào)算法是一個(gè)動(dòng)態(tài)概念，強(qiáng)調(diào)實(shí)際的執(zhí)行過程。數(shù)學(xué)上的計(jì)算方法是一個(gè)靜態(tài)概念，注重理論上的正確性。數(shù)學(xué)上的計(jì)算方法是設(shè)計(jì)算法的基礎(chǔ)。10數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念3、算法的基本要素算法中對(duì)數(shù)據(jù)的運(yùn)算和操作基本的運(yùn)算和操作有：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu)控制結(jié)構(gòu)決定操作的執(zhí)行順序。要求符合結(jié)構(gòu)化原則，強(qiáng)調(diào)易讀性。4、算法設(shè)計(jì)基本方法列舉法 列舉所有可能情況，檢測其中符合條件的結(jié)果。歸納法 列舉若干特殊情況，分析歸納出一般規(guī)

5、律。遞推 從已知初始條件出發(fā)，逐步推導(dǎo)出中間及最后結(jié)果。遞歸 將復(fù)雜問題歸結(jié)為簡單問題，在歸結(jié)為更簡單問題， 。減半遞推技術(shù) 將問題規(guī)?！皽p半”，并重復(fù)該“減半” 的過程?；厮莘?分析問題，找出某些線索，沿線索逐步試探。若試探成功，則繼續(xù)，若試探失敗，則回退。直至問題解決。11數(shù)據(jù)結(jié)構(gòu)與算法算法的基本概念5、算法的時(shí)間復(fù)雜度指執(zhí)行算法所需要的計(jì)算工作量算法工作量的度量應(yīng)與計(jì)算機(jī)、編程語言、編程細(xì)節(jié)等無關(guān)。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)衡量。算法工作量是問題規(guī)模的函數(shù)：算法的工作量= f (n)度量方法有：平均性態(tài)分析 計(jì)算其加權(quán)平均值最壞情況分析 計(jì)算其基本運(yùn)算的最大次數(shù)6、算法的空間

6、復(fù)雜度指執(zhí)行算法所需要的存儲(chǔ)空間包括：算法程序所占據(jù)的存儲(chǔ)空間待處理數(shù)據(jù)所占據(jù)的存儲(chǔ)空間算法程序執(zhí)行中所需要的額外存儲(chǔ)空間如果額外存儲(chǔ)空間大小不隨問題規(guī)模變化，則稱之為算法原地工作。降低算法的空間復(fù)雜度，應(yīng)從數(shù)據(jù)的存儲(chǔ)空間和額外空間入手。12算法定義特征復(fù)雜度（時(shí)間/空間）數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)的邏輯結(jié)構(gòu)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3.數(shù)據(jù)的運(yùn)算線性線性表?xiàng)?、?duì)列非線性樹形結(jié)構(gòu)二叉樹（滿二叉樹、完全二叉數(shù)）順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)查找（順序、二分）修改排序（交換、插入、選擇）插入刪除修改13數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素

7、的集合。結(jié)構(gòu) 通常指前后件關(guān)系。主要研究：數(shù)據(jù)元素間的固有邏輯關(guān)系 數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算2、數(shù)據(jù)的邏輯結(jié)構(gòu)指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)前后件(直接前驅(qū)和直接后繼)關(guān)系就是指邏輯關(guān)系3、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式存儲(chǔ)結(jié)構(gòu)也稱為物理結(jié)構(gòu)同一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)常用的有：順序、鏈接、索引等形式14數(shù)據(jù)結(jié)構(gòu)與算法線性表及其順序存儲(chǔ)結(jié)構(gòu)1、線性表線性表是由 n (n0)個(gè)元素組成的有限序列：(a1,a2,ai,an)有且只有一個(gè)根結(jié)點(diǎn)，它無直接前驅(qū)。有且只有一個(gè)終端結(jié)點(diǎn)，它無直接后繼。除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)都有且只有一

8、個(gè)直接前驅(qū)和直接后繼。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長度。n=0時(shí)，稱為空表。2、線性表的順序存儲(chǔ)順序存儲(chǔ)也稱為順序分配線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的線性表中各元素在存儲(chǔ)空間中按照邏輯順序依次存儲(chǔ)3、順序表的運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)通常稱為順序表包括：插入、刪除、查找、分解、合并、復(fù)制、逆轉(zhuǎn)等。在高級(jí)語言中，順序表對(duì)應(yīng)一維數(shù)組。順序表的查找方便，插入和刪除較麻煩。16數(shù)據(jù)結(jié)構(gòu)與算法線性表及其順序存儲(chǔ)結(jié)構(gòu)注意： 線性表屬于線性結(jié)構(gòu)。 線性表的順序存儲(chǔ)結(jié)構(gòu)通常稱為順序表。 在順序表中，所有元素按照其邏輯順序連續(xù)存儲(chǔ)，前后件元素緊鄰，前件元素一定存儲(chǔ)在后件元素的前面。邏輯上相鄰的數(shù)據(jù)元素物理上也相鄰

9、 在程序設(shè)計(jì)語言中，線性表的順序存儲(chǔ)結(jié)構(gòu)對(duì)應(yīng)了一維數(shù)組。因?yàn)樵诔绦蛟O(shè)計(jì)語言中，一維數(shù)組與計(jì)算機(jī)中實(shí)際的存儲(chǔ)空間結(jié)構(gòu)是一致的。 在順序表中，如果要在第 i 個(gè)位置插入一個(gè)新元素，則原第 i 個(gè)元素以及之后的所有元素都要依次后移一個(gè)位置。在平均情況下，在順序表中插入一個(gè)新元素，需要移動(dòng) n/2 個(gè)元素。 在順序表中，如果要?jiǎng)h除第 i 個(gè)位置的元素，則原第 i 個(gè)元素之后的所有元素都要依次前移一個(gè)位置。在平均情況下，在順序表中刪除一個(gè)元素，需要移動(dòng) n/2 個(gè)元素。17數(shù)據(jù)結(jié)構(gòu)與算法隊(duì)列及其基本運(yùn)算1、隊(duì)列隊(duì)列(queue)是限定在一端進(jìn)行插入另一端進(jìn)行刪除的線性表允許進(jìn)行插入的一端稱為隊(duì)尾。允許進(jìn)

10、行刪除的另一端稱為隊(duì)頭。其特點(diǎn)為“先入先出”(FIFO)或“后入后出”(LILO)。(先來先服務(wù))通常設(shè)置指針rear指向隊(duì)尾，指針front指向隊(duì)頭。2、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的各個(gè)數(shù)據(jù)元素按其邏輯順序依次連續(xù)存儲(chǔ)。由于插入刪除操作只能在隊(duì)列的兩端進(jìn)行，所以不需要移動(dòng)數(shù)據(jù)元素。3、隊(duì)列的基本運(yùn)算在實(shí)際應(yīng)用中常常使用循環(huán)隊(duì)列。入隊(duì)：在隊(duì)尾位置插入新元素。 出隊(duì)：取出隊(duì)頭位置的元素。 “上溢”：入隊(duì)時(shí)隊(duì)列已滿?！跋乱纭保撼鲫?duì)時(shí)隊(duì)列已空。19數(shù)據(jù)結(jié)構(gòu)與算法線性鏈表1、鏈?zhǔn)酱鎯?chǔ)方式 結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域(存儲(chǔ)數(shù)據(jù))、指針域(指向其前件或后件)。 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，存儲(chǔ)順序與邏輯關(guān)系可

11、以不一致。 鏈?zhǔn)酱鎯?chǔ)方式既可以用來表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。2、線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。(棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列)常用的線性鏈表有：單鏈表 (一個(gè)指針域，指向直接后繼)雙向鏈表 (兩個(gè)指針域，指向直接后繼及后繼) 循環(huán)鏈表 (所有結(jié)點(diǎn)的指針構(gòu)成循環(huán)鏈)3、線性鏈表的基本運(yùn)算查找：在線性鏈表中查找指定元素。插入：在線性鏈表中插入新結(jié)點(diǎn)。刪除：在線性鏈表中刪除指定結(jié)點(diǎn)。20單鏈表 (Singly Linked List) 每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。 邏輯上相鄰的元素物理上不需要相鄰；不可隨機(jī)存取，順序存?。徊迦?、刪除時(shí)不需要

12、移動(dòng)大量元素表頭指針datanext21 (插入前) (插入后) 鏈表插入 newnodenext = pnext; pnext = newnode；newnodepnewnodep22鏈表刪除 pnext = q next 23數(shù)據(jù)結(jié)構(gòu)與算法樹的基本概念1、樹樹是一種簡單的非線性結(jié)構(gòu)。元素間的關(guān)系具有明顯的層次結(jié)構(gòu)。2、相關(guān)的術(shù)語根結(jié)點(diǎn)葉節(jié)點(diǎn)父結(jié)點(diǎn)子結(jié)點(diǎn)子樹結(jié)點(diǎn)的度樹的度樹的深度24數(shù)據(jù)結(jié)構(gòu)與算法查找技術(shù)1、順序查找從線性表的第一個(gè)元素開始，依次與指定數(shù)據(jù)比較，若相等則查找成功，若比較的所有元素都不相等，則查找失敗。最壞情況的比較次數(shù)為表長n，平均情況為n/2。無序順序表的查找只能采用順序查

13、找的方法。線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)也只能采用順序查找的方法。2、二分法查找在順序存儲(chǔ)的線性表為有序的情況下，可以使用二分法查找。方法為：將待查數(shù)據(jù)與線性表的中間項(xiàng)比較：若相等，則查找成功；若小于，則在線性表的前半部分進(jìn)行二分法查找；若大于，則在線性表的后半部分進(jìn)行二分法查找；反復(fù)進(jìn)行直到相等(查找成功)或子表長度為0(查找失敗)。26數(shù)據(jù)結(jié)構(gòu)與算法排序技術(shù)1、交換類排序起泡排序最壞情況下的比較次數(shù)為 n(n-1)/2 。 快速排序最壞情況下的比較次數(shù)為 n(n-1)/2 。 2、插入類排序簡單插入排序最壞情況下的比較次數(shù)為 n(n-1)/2 。 希爾排序最壞情況下的比較次數(shù)為 O( n 1.5) 。

14、3、選擇類排序簡單選擇排序最壞情況下的比較次數(shù)為 n(n-1)/2 。堆排序最壞情況下的比較次數(shù)為 O( n log2n) 。27數(shù)據(jù)結(jié)構(gòu)與算法本章重點(diǎn)8、滿二叉樹是二叉樹的特殊形態(tài)，滿二叉樹的各層結(jié)點(diǎn)都達(dá)到最大值，葉結(jié)點(diǎn)只出現(xiàn)在最后一層。9、完全二叉樹是二叉樹的特殊形態(tài)，完全二叉樹除最后一層外，各層結(jié)點(diǎn)都達(dá)到最大值，葉結(jié)點(diǎn)只出現(xiàn)在最后兩層。滿二叉樹屬于完全二叉樹。10、根據(jù)掃描根結(jié)點(diǎn)的順序，按照先左后右的原則，遍歷二叉樹有三種方法：前序遍歷、中序遍歷、后序遍歷。11、在長度為 n 的線性表中進(jìn)行順序查找，最壞情況需要比較 n 次。12、在長度為 n 的線性表中進(jìn)行對(duì)分查找，最壞情況需要比較

15、log2n 次。但對(duì)分查找只適用于有序順序表。13、在冒泡排序、快速排序、簡單插入排序、選擇排序的方法中，最壞情況下需要比較的次數(shù)為 n(n-1)/2 。29程序設(shè)計(jì)基礎(chǔ)關(guān)鍵考點(diǎn)結(jié)構(gòu)化設(shè)計(jì)的原則面向?qū)ο蠓椒ǖ幕靖拍?0程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)方法與風(fēng)格1、程序設(shè)計(jì)方法就程序設(shè)計(jì)的方法和技術(shù)的發(fā)展而言主要經(jīng)歷了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)兩個(gè)階段2、程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出來的特點(diǎn)、習(xí)慣和邏輯思路。程序設(shè)計(jì)風(fēng)格會(huì)深刻影響軟件的質(zhì)量和可維護(hù)性，良好的程序設(shè)計(jì)風(fēng)格可以使程序的結(jié)構(gòu)清晰合理，使程序代碼便于維護(hù)。程序設(shè)計(jì)風(fēng)格的主導(dǎo)：“清晰第一，效率第二”。主要因素：源程序文檔化數(shù)

16、據(jù)說明的方法語句的結(jié)構(gòu)輸入和輸出31程序設(shè)計(jì)基礎(chǔ)結(jié)構(gòu)化程序設(shè)計(jì)1、結(jié)構(gòu)化程序設(shè)計(jì)要求把程序的結(jié)構(gòu)限制為順序、選擇和循環(huán)三種基本結(jié)構(gòu)。2、結(jié)構(gòu)化程序設(shè)計(jì)的原則自頂向下先總體后細(xì)節(jié)，先全局后局部。逐步求精對(duì)復(fù)雜問題設(shè)計(jì)子目標(biāo)過度，逐步細(xì)化。模塊化將復(fù)雜問題分解為若干簡單問題。限制使用GOTO語句防止造成程序邏輯結(jié)構(gòu)混亂。3、三種基本結(jié)構(gòu)順序結(jié)構(gòu) 選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)4、特點(diǎn)所有控制結(jié)構(gòu)由三種基本結(jié)構(gòu)組成各個(gè)模塊單入口單出口模塊的內(nèi)聚性強(qiáng) 模塊間的偶合性低32程序設(shè)計(jì)基礎(chǔ)面向?qū)ο蟮某绦蛟O(shè)計(jì)1、面向?qū)ο竺嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，是從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，用現(xiàn)實(shí)生活中常用的思維方法來描述客觀事物，是系

17、統(tǒng)中的對(duì)象及對(duì)象間的關(guān)系能如實(shí)反映事物及其關(guān)系。2、主要優(yōu)點(diǎn)與人類習(xí)慣的思維方法一致穩(wěn)定性好可重用性好易于開發(fā)大型軟件產(chǎn)品可維護(hù)性好3、基本概念對(duì)象類和實(shí)例消息繼承多態(tài)性33程序設(shè)計(jì)基礎(chǔ)本章重點(diǎn)1、程序設(shè)計(jì)并不等于編程，編程只是程序設(shè)計(jì)過程中的一小步。2、結(jié)構(gòu)化程序設(shè)計(jì)要求把程序的結(jié)構(gòu)限制為順序、選擇、循環(huán)三種基本結(jié)構(gòu)。3、模塊化設(shè)計(jì)是指把一個(gè)大程序按人們能理解的大小規(guī)模進(jìn)行分解。劃分模塊的基本原則是使每個(gè)模塊都易于理解。在按功能劃分模塊時(shí)，要求各模塊功能盡量單一，各模塊之間的聯(lián)系盡量的少。4、客觀世界是由實(shí)體及其聯(lián)系所組成的?？陀^世界中的實(shí)體稱為問題域的對(duì)象。5、類描述的是具有相似性質(zhì)一組對(duì)

18、象。一個(gè)對(duì)象稱為類的實(shí)例。6、允許作用于某個(gè)對(duì)象上的各種操作稱為方法。7、消息是用來請(qǐng)求對(duì)象執(zhí)行某一處理或回答某些信息的要求。8、繼承是表示類之間的相似性的一種機(jī)制。9、封裝是一種信息隱蔽機(jī)制，目的是將對(duì)象的使用者與對(duì)象的設(shè)計(jì)者分開。用戶只需了解對(duì)象封裝界面上的信息，不必知道內(nèi)部的具體細(xì)節(jié)。34軟件工程基礎(chǔ)關(guān)鍵考點(diǎn)軟件定義與特點(diǎn)軟件開發(fā)過程的過程化原則結(jié)構(gòu)化分析方法結(jié)構(gòu)化設(shè)計(jì)方法軟件測試技術(shù)與方法程序調(diào)試基本概念35軟件工程基礎(chǔ)軟件工程基本概念1、軟件軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。2、軟件的特點(diǎn)抽象性可大量拷貝無磨損及老化問題受計(jì)算機(jī)系統(tǒng)限制(移植問題)復(fù)雜性高成本昂貴開發(fā)過程涉及

19、諸多社會(huì)因素3、軟件工程軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。三個(gè)要素方法：完成軟件工程項(xiàng)目的技術(shù)手段。工具：支持軟件的開發(fā)、管理、文檔生成。過程：支持軟件開發(fā)各個(gè)環(huán)節(jié)的管理、控制。目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可適應(yīng)性、可追蹤性、可互操作性滿足用戶要求的軟件產(chǎn)品。36軟件工程基礎(chǔ)軟件開發(fā)過程的過程化原則1、軟件工程過程 為獲得軟件產(chǎn)品，在軟件工具支持下的一系列軟件工程活動(dòng)。Plan軟件規(guī)格說明。Do軟件開發(fā)。Check軟件確認(rèn)。Action軟件演進(jìn)。 使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進(jìn)行的一組開發(fā)活動(dòng)，

20、在過程結(jié)束時(shí)將用戶要求轉(zhuǎn)化為軟件產(chǎn)品。軟件工程過程應(yīng)確定方法使用的順序、要求交付的文檔資料、為保證質(zhì)量與適應(yīng)變化所需要的管理、軟件開發(fā)各階段要完成的任務(wù)。2、軟件生命周期 定義階段可行性研究及項(xiàng)目計(jì)劃需求分析 開發(fā)階段概要設(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)測試 維護(hù)階段使用維護(hù)退役37軟件工程基礎(chǔ)結(jié)構(gòu)化分析方法在系統(tǒng)分析階段，結(jié)構(gòu)化分析方法用來對(duì)系統(tǒng)進(jìn)行邏輯設(shè)計(jì)。1、需求分析需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求。 常見的需求分析方法：結(jié)構(gòu)化分析方法 面向?qū)ο蟮姆治龇椒?、結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析就是使用數(shù)據(jù)流圖(DFD)、數(shù)據(jù)字典(DD)、結(jié)構(gòu)化英語、判定表和判定樹等工具，來建立一種被稱為結(jié)構(gòu)化規(guī)格

21、說明的目標(biāo)文檔。 結(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)據(jù)流的、自頂向下逐層分解的、建立系統(tǒng)的處理流程，它以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。3、 軟件需求規(guī)格說明書是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。軟件需求規(guī)格說明書把軟件計(jì)劃中確定的軟件范圍加以展開，制定出完整的信息描述、詳細(xì)的功能說明、恰當(dāng)?shù)臋z驗(yàn)標(biāo)準(zhǔn)、其他與要求有關(guān)的信息。38軟件工程基礎(chǔ)結(jié)構(gòu)化設(shè)計(jì)方法1、軟件設(shè)計(jì)軟件設(shè)計(jì)是把軟件需求轉(zhuǎn)換為軟件表示的過程。從技術(shù)角度：軟件設(shè)計(jì)包括結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。從工程角度：軟件設(shè)計(jì)包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)。軟件設(shè)計(jì)的基本原理包括：抽象、模塊化、信息隱蔽、模塊

22、獨(dú)立性2、概要設(shè)計(jì)概要設(shè)計(jì)的基本任務(wù)：系統(tǒng)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)編寫設(shè)計(jì)文檔設(shè)計(jì)文檔評(píng)審結(jié)構(gòu)圖是軟件結(jié)構(gòu)設(shè)計(jì)的常用工具。3、詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)的任務(wù)，是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。常見的設(shè)計(jì)工具：圖形工具：流程圖、N - S、PAD、HIPO表格工具：判定表語言工具：PDL(偽碼)39軟件工程基礎(chǔ)軟件測試1、測試軟件測試的目標(biāo)是在精心控制的環(huán)境下執(zhí)行程序，以發(fā)現(xiàn)程序中的錯(cuò)誤，給出程序可靠性的鑒定。測試不是為了證明程序是正確的，目的是設(shè)法暴露程序中的錯(cuò)誤和缺陷。測試只能說明程序有錯(cuò)，不能證明程序無錯(cuò)。程序不能100%可靠。2、測試方法程

23、序的靜態(tài)分析程序的動(dòng)態(tài)分析自動(dòng)測試工具3、測試層次模塊測試(單元測試)整體測試(集成測試)又分為 功能測試 和 驗(yàn)收測試 兩種。4、白盒法根據(jù)對(duì)程序內(nèi)部邏輯結(jié)構(gòu)的分析來導(dǎo)出測試用例。5、黑盒法不考慮程序的內(nèi)部結(jié)構(gòu)特征，根據(jù)程序功能導(dǎo)出測試用例。40軟件工程基礎(chǔ)程序調(diào)試1、調(diào)試與測試 測試的目的是發(fā)現(xiàn)錯(cuò)誤，評(píng)價(jià)可靠性；調(diào)試的目的是發(fā)現(xiàn)錯(cuò)誤的位置，改正發(fā)現(xiàn)的錯(cuò)誤。 測試揭示設(shè)計(jì)人員的過失，由非設(shè)計(jì)人員承擔(dān)；調(diào)試幫助設(shè)計(jì)人員改正錯(cuò)誤，由設(shè)計(jì)人員自己承擔(dān)。 測試是機(jī)械的、強(qiáng)制的、嚴(yán)格的、可預(yù)測的；調(diào)試要求隨機(jī)應(yīng)變、聯(lián)想、經(jīng)驗(yàn)、智力，并要求自主地完成。 測試發(fā)現(xiàn)的錯(cuò)誤可立即進(jìn)行調(diào)試改正，然后還必須再進(jìn)行

24、測試。 調(diào)試用例與測試用例可以一致也可以不一致。2、調(diào)試方法 強(qiáng)行排錯(cuò)法 回溯法 原因排除法41軟件工程基礎(chǔ)本章重點(diǎn)1、軟件生命周期分為三個(gè)時(shí)期共八個(gè)階段：軟件定義期：問題定義、可行性研究、需求分析。軟件開發(fā)期：系統(tǒng)設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、測試。軟件維護(hù)期：運(yùn)行維護(hù)。2、在系統(tǒng)分析階段，結(jié)構(gòu)化分析方法用來對(duì)系統(tǒng)進(jìn)行邏輯設(shè)計(jì)，此時(shí)不考慮物理實(shí)現(xiàn)的問題，而只考慮“做什么”的問題，系統(tǒng)的物理設(shè)計(jì)(“如何做”)的問題留在系統(tǒng)設(shè)計(jì)階段用結(jié)構(gòu)化設(shè)計(jì)方法來完成。3、數(shù)據(jù)流圖有兩種典型的結(jié)構(gòu)形式：變換型、事務(wù)型。4、評(píng)價(jià)模塊的獨(dú)立性的標(biāo)準(zhǔn)有兩個(gè)：耦合性：表明兩個(gè)模塊間聯(lián)系的強(qiáng)弱。內(nèi)聚性：表明模塊內(nèi)部聯(lián)系是否緊密

25、。內(nèi)聚性要強(qiáng)，偶合性要弱。5、軟件測試是在精心控制的環(huán)境下執(zhí)行程序，發(fā)現(xiàn)程序中的錯(cuò)誤，給出程序可靠性的鑒定。6、測試是程序執(zhí)行的過程，目的在于發(fā)現(xiàn)錯(cuò)誤；一個(gè)好的測試在于能發(fā)現(xiàn)至今未能發(fā)現(xiàn)的錯(cuò)誤，一個(gè)成功的測試是發(fā)現(xiàn)了至今未發(fā)現(xiàn)的錯(cuò)誤。7、測試發(fā)現(xiàn)錯(cuò)誤后，可進(jìn)行調(diào)試；調(diào)試后的程序還應(yīng)再測試，以檢驗(yàn)調(diào)試效果。42數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)關(guān)鍵考點(diǎn)數(shù)據(jù)庫系統(tǒng)基本概念數(shù)據(jù)模型43數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫系統(tǒng)的基本概念1、數(shù)據(jù)庫 DB是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)中，是多種應(yīng)用數(shù)據(jù)的集成，可被各個(gè)應(yīng)用程序所共享。2、數(shù)據(jù)庫管理系統(tǒng) DBMS數(shù)據(jù)庫的管理機(jī)構(gòu)，系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)組織、操縱、維護(hù)、控

26、制、保護(hù)等。為數(shù)據(jù)庫構(gòu)作模式為數(shù)據(jù)模式的實(shí)現(xiàn)提供方法和手段為用戶使用提供查詢、插入、修改、刪除等功能提供對(duì)數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能(復(fù)制、重組、檢測等)。3、DBMS提供的語言數(shù)據(jù)定義語言數(shù)據(jù)操縱語言數(shù)據(jù)控制語言44數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫系統(tǒng)的基本概念4、數(shù)據(jù)庫系統(tǒng) DBS由DB、DBMS、數(shù)據(jù)庫管理員(DBA)、硬件平臺(tái)、軟件平臺(tái)組成。5、數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)數(shù)據(jù)的集成性數(shù)據(jù)的高共享性低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)統(tǒng)一管理和控制6、數(shù)據(jù)庫系統(tǒng)的三級(jí)模式概念模式：數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)的邏輯描述，與具體的軟硬件環(huán)境無關(guān)。外模式：也叫用戶模式，是用戶的數(shù)據(jù)視圖。內(nèi)模式：也叫物理模式，描述數(shù)據(jù)庫中數(shù)據(jù)的存儲(chǔ)結(jié)

27、構(gòu)和存取方式。45數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)模型1、三種不同應(yīng)用層次的數(shù)據(jù)模型概念模型：概念數(shù)據(jù)模型，面向客觀世界、面向用戶，與具體的DBMS無關(guān)。數(shù)據(jù)模型：邏輯數(shù)據(jù)模型，面向DBS的模型，著重于數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)。物理模型：物理數(shù)據(jù)模型，面向計(jì)算機(jī)系統(tǒng)，是數(shù)據(jù)模型的物理表示。2、實(shí)體集之間的聯(lián)系一對(duì)一一對(duì)多或多對(duì)一多對(duì)多3、E - R模型的圖示法實(shí)體集表示法：在E - R圖中用矩形表示實(shí)體集，矩形內(nèi)注明實(shí)體集名稱。屬性表示法：在E - R圖中用橢圓，橢圓中注明屬性名稱。聯(lián)系表示法：在E - R圖中用菱形表示聯(lián)系，菱形中注明聯(lián)系名稱。實(shí)體集與屬性之間的連接關(guān)系：在E - R圖中用連接兩個(gè)圖形的無向線段表

28、示。46數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)模型4、層次模型 層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)。5、網(wǎng)狀模型網(wǎng)狀模型是一個(gè)不加任何條件限制的無向圖。6、關(guān)系模型關(guān)系模型用二維表表示關(guān)系。二維表有表框架(關(guān)系模式)和表元組組成。表框架由n個(gè)命名的屬性組成。屬性的取值范圍稱為值域。二維表中能夠唯一標(biāo)識(shí)元組的最小屬性集成為“鍵”(關(guān)鍵字)。二維表中可能有若干鍵，稱為侯選鍵(侯選關(guān)鍵字) 。侯選鍵中選擇作為用戶使用的稱為主鍵(主關(guān)鍵字) 。關(guān)系框架和關(guān)系元組構(gòu)成關(guān)系。47數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)關(guān)系代數(shù)1、關(guān)系模型的基本操作插入刪除修改查詢2、基本運(yùn)算并運(yùn)算(插入)差運(yùn)算(刪除)投影(查詢)選擇(查詢) 笛卡爾積(查詢)交運(yùn)算除運(yùn)算連接運(yùn)算(有條件的笛卡爾積) 自然連接運(yùn)算(公共域等值連接)48數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)與管理1、數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)的基本任務(wù)是根據(jù)用戶的信息需求、處理需求、軟硬件環(huán)境設(shè)計(jì)出數(shù)據(jù)模式。在數(shù)據(jù)庫設(shè)計(jì)中有兩種方法：面向數(shù)據(jù)的方法以信息需求為主兼顧處理需求。面向過程的方法以