全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)VisualFoxpro公共基礎(chǔ)知識(shí)講義(周末培訓(xùn)班)

1、全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí) vfvf 公共基礎(chǔ)知識(shí)公共基礎(chǔ)知識(shí)考試主要是在筆試出現(xiàn)，上機(jī)沒有。考試主要是在筆試出現(xiàn)，上機(jī)沒有。筆試分?jǐn)?shù)分布：筆試分?jǐn)?shù)分布：選擇題：有選擇題：有 1010 個(gè)小題，共計(jì)個(gè)小題，共計(jì) 2020 分，每個(gè)小題分，每個(gè)小題 2 2 分分填空題：有填空題：有 5 5 個(gè)小題，共計(jì)個(gè)小題，共計(jì) 1010 分，每個(gè)小題分，每個(gè)小題 2 2 分分公共基礎(chǔ)知識(shí)總計(jì)公共基礎(chǔ)知識(shí)總計(jì) 3030 分在筆試。分在筆試。第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法1.11.1 算法算法考點(diǎn)考點(diǎn) 1 1：算法的基本概念：算法的基本概念算法概念：所謂算法是指解題方案的準(zhǔn)確而完整

2、的描述。算法概念：所謂算法是指解題方案的準(zhǔn)確而完整的描述。程序設(shè)計(jì)中的算法概念：程序設(shè)計(jì)中的算法概念：算法是指解決某一個(gè)問題的方法和步驟。算法是指解決某一個(gè)問題的方法和步驟。1 1、算法的基本特征、算法的基本特征（1 1）可行性：是指問題可以在現(xiàn)有的條件下解決）可行性：是指問題可以在現(xiàn)有的條件下解決（2 2）確定性：是指問題是確定的，不是模棱兩可的）確定性：是指問題是確定的，不是模棱兩可的（3 3）有窮性：是指有限的步驟，是指在有限的時(shí)間之內(nèi)）有窮性：是指有限的步驟，是指在有限的時(shí)間之內(nèi)（4 4）擁有足夠的情報(bào)：處理該問題的所必須的數(shù)據(jù)）擁有足夠的情報(bào)：處理該問題的所必須的數(shù)據(jù)（5 5）輸入：

3、）輸入：0 0 個(gè)以上的輸入個(gè)以上的輸入（6 6）輸出：至少有一個(gè)輸出）輸出：至少有一個(gè)輸出考點(diǎn)考點(diǎn) 2 2：算法的復(fù)雜度：算法的復(fù)雜度衡量算法的復(fù)雜程度，可以使用時(shí)間復(fù)雜度和空間復(fù)雜度來衡量衡量算法的復(fù)雜程度，可以使用時(shí)間復(fù)雜度和空間復(fù)雜度來衡量有關(guān)算法的復(fù)雜度主要掌握：有關(guān)算法的復(fù)雜度主要掌握：（1 1）算法的時(shí)間復(fù)雜度）算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的概念：時(shí)間復(fù)雜度的概念：是指執(zhí)行該算法所需要的計(jì)算工作量是指執(zhí)行該算法所需要的計(jì)算工作量時(shí)間復(fù)雜度的概念分析：時(shí)間復(fù)雜度的概念分析：時(shí)間復(fù)雜度其實(shí)就是指執(zhí)行該算法的循環(huán)次數(shù)的一個(gè)量值時(shí)間復(fù)雜度其實(shí)就是指執(zhí)行該算法的循環(huán)次數(shù)的一個(gè)量值我們一般衡量

4、算法的時(shí)間復(fù)雜度的時(shí)候，有這么三種情況：我們一般衡量算法的時(shí)間復(fù)雜度的時(shí)候，有這么三種情況：第一種：是指最好的情況下第一種：是指最好的情況下第二種：是指最壞的情況下第二種：是指最壞的情況下第三種：是指最糟糕的情況下第三種：是指最糟糕的情況下注意：注意：時(shí)間復(fù)雜度不是使用時(shí)間來衡量時(shí)間復(fù)雜度不是使用時(shí)間來衡量（2 2）算法的空間復(fù)雜度）算法的空間復(fù)雜度空間復(fù)雜度的概念：空間復(fù)雜度的概念：是指在執(zhí)行該算法是所占用的內(nèi)存空間。是指在執(zhí)行該算法是所占用的內(nèi)存空間?？臻g復(fù)雜度的概念分析：空間復(fù)雜度的概念分析：空間復(fù)雜度主要是衡量算法在執(zhí)行的過程中，所占有的內(nèi)存空間大小，并不是空間復(fù)雜度主要是衡量算法在執(zhí)

5、行的過程中，所占有的內(nèi)存空間大小，并不是其他所占內(nèi)存空間大小。其他所占內(nèi)存空間大小。例如：例如：算法在沒有執(zhí)行的情況下，占有的內(nèi)存，不是空間復(fù)雜度。一定要注意是在執(zhí)算法在沒有執(zhí)行的情況下，占有的內(nèi)存，不是空間復(fù)雜度。一定要注意是在執(zhí)行的過程中，所占有的內(nèi)存空間大小。行的過程中，所占有的內(nèi)存空間大小。注意：注意：算法的時(shí)間復(fù)雜度大，其空間復(fù)雜度不一定大算法的時(shí)間復(fù)雜度大，其空間復(fù)雜度不一定大算法的時(shí)間復(fù)雜度小，其空間復(fù)雜度不一定小算法的時(shí)間復(fù)雜度小，其空間復(fù)雜度不一定小總結(jié)：總結(jié)：算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒有直接聯(lián)系，但是有間接的聯(lián)系算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒有直接聯(lián)系，但是有間接的聯(lián)系

6、注意：注意：時(shí)間復(fù)雜度與空間復(fù)雜度的前提條件是在執(zhí)行的情況下分析時(shí)間復(fù)雜度與空間復(fù)雜度的前提條件是在執(zhí)行的情況下分析1.21.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念考點(diǎn)考點(diǎn) 3 3：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)1 1、數(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)常用的邏輯結(jié)構(gòu)：順序、鏈接、索引等結(jié)構(gòu)。常用的邏輯結(jié)構(gòu)：順序、鏈接、索引等結(jié)構(gòu)。注意：注意：結(jié)構(gòu)的概念：是指數(shù)據(jù)元素之間前后件的關(guān)系。結(jié)構(gòu)的概念：是指數(shù)據(jù)元素之間前后件的關(guān)系。注意：注意：前后件概念：是指該元素，前一個(gè)離他最近的元素或后一個(gè)

7、離他最近的元素前后件概念：是指該元素，前一個(gè)離他最近的元素或后一個(gè)離他最近的元素比如：比如：1,2,3,4,51,2,3,4,5春、夏、秋、冬春、夏、秋、冬2 2、數(shù)據(jù)的物理結(jié)構(gòu)、數(shù)據(jù)的物理結(jié)構(gòu)( (存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)) )概念：是指數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）在計(jì)算機(jī)存儲(chǔ)空間中的存放形式也可概念：是指數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）在計(jì)算機(jī)存儲(chǔ)空間中的存放形式也可以稱之為：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以稱之為：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或者，數(shù)據(jù)的物理結(jié)構(gòu)就是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的具體表示或者，數(shù)據(jù)的物理結(jié)構(gòu)就是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的具體表示注意：數(shù)據(jù)結(jié)構(gòu)中主要有三種結(jié)構(gòu)：邏輯結(jié)構(gòu)、物理結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)注意：數(shù)據(jù)結(jié)構(gòu)中主要有三種結(jié)構(gòu)

8、：邏輯結(jié)構(gòu)、物理結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)考點(diǎn)考點(diǎn) 4 4：線性結(jié)構(gòu)與非線性結(jié)構(gòu)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)重點(diǎn)掌握線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念重點(diǎn)掌握線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念在數(shù)據(jù)結(jié)構(gòu)中，將數(shù)據(jù)分為兩種結(jié)構(gòu)：在數(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)：滿足以下兩個(gè)條件，第一：有且只有一個(gè)根節(jié)點(diǎn)；第二：每一個(gè)節(jié)線性結(jié)構(gòu)：滿足以下兩個(gè)條件，第一：有且只有一個(gè)根節(jié)點(diǎn)；第二：每一個(gè)節(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。概念解釋：概念解釋：前件（前驅(qū)）前件（前驅(qū)） ：是指某一個(gè)元素，離這個(gè)元素最近的前一個(gè)元素：是指某一個(gè)元素，離這個(gè)元素最近的前

9、一個(gè)元素后件（后驅(qū)）后件（后驅(qū)） ：是指某一個(gè)元素，離這個(gè)元素最近的后一個(gè)元素：是指某一個(gè)元素，離這個(gè)元素最近的后一個(gè)元素前件，有的書本上面稱之為前驅(qū)前件，有的書本上面稱之為前驅(qū)后件，有的書本上面稱之為后驅(qū)后件，有的書本上面稱之為后驅(qū)非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)的就是非線性結(jié)構(gòu)非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)的就是非線性結(jié)構(gòu)非線性結(jié)構(gòu)主要有：樹結(jié)構(gòu)、圖結(jié)構(gòu)等等。非線性結(jié)構(gòu)主要有：樹結(jié)構(gòu)、圖結(jié)構(gòu)等等。1.31.3 線性表、棧和隊(duì)列線性表、棧和隊(duì)列考點(diǎn)考點(diǎn) 5 5：線性表和棧：線性表和棧1 1、線性表的基本概念、線性表的基本概念線性表是線性表是 n(n=0)n(n=0)個(gè)元素個(gè)元素 a1,a2,a3,a1,a

10、2,a3,an,an 組成的一個(gè)有限序列，表中除了第一組成的一個(gè)有限序列，表中除了第一個(gè)以外的每一個(gè)元素，有且只有一個(gè)前件；除最后一個(gè)元素外每一個(gè)元素，有個(gè)以外的每一個(gè)元素，有且只有一個(gè)前件；除最后一個(gè)元素外每一個(gè)元素，有且只有一個(gè)后件。且只有一個(gè)后件。也可以表示為：也可以表示為：（a1,a2,a3,a1,a2,a3,an,an）2 2、線性表的順序存儲(chǔ)結(jié)構(gòu)、線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)具有的特點(diǎn)：線性表的順序存儲(chǔ)結(jié)構(gòu)具有的特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存儲(chǔ)的線性表中各數(shù)據(jù)元素在存儲(chǔ)空

11、間中是按邏輯順序依次存儲(chǔ)的線性表的存儲(chǔ)有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)線性表的存儲(chǔ)有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)注意：一般情況下，線性存儲(chǔ)所占用的空間要小于鏈?zhǔn)酱鎯?chǔ)所占用的空間。注意：一般情況下，線性存儲(chǔ)所占用的空間要小于鏈?zhǔn)酱鎯?chǔ)所占用的空間。3 3、棧的定義、棧的定義棧是一種特殊的線性結(jié)構(gòu)棧是一種特殊的線性結(jié)構(gòu)棧的概念：棧是一種先進(jìn)后出或后進(jìn)先出的線性結(jié)構(gòu)棧的概念：棧是一種先進(jìn)后出或后進(jìn)先出的線性結(jié)構(gòu)棧的概念分析：棧的概念分析：棧其實(shí)就是一個(gè)死胡同棧其實(shí)就是一個(gè)死胡同4 4、棧的順序存儲(chǔ)及運(yùn)算、棧的順序存儲(chǔ)及運(yùn)算棧有三個(gè)基本的運(yùn)算：入棧、讀棧、退棧棧有三個(gè)基本的運(yùn)算：入棧、讀棧、退?？偨Y(jié)：總結(jié)：棧中指

12、向棧底的指針是用棧中指向棧底的指針是用 bottombottom 來表示來表示棧中指向棧頂?shù)闹羔樖怯脳Ｖ兄赶驐ｍ數(shù)闹羔樖怯?toptop 來表示來表示棧頂指針是可以來回移動(dòng)的，棧底指針不能移動(dòng)棧頂指針是可以來回移動(dòng)的，棧底指針不能移動(dòng)棧可以順序存儲(chǔ)，也可以鏈?zhǔn)酱鎯?chǔ)?？梢皂樞虼鎯?chǔ)，也可以鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)都是屬于線性結(jié)構(gòu)順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)都是屬于線性結(jié)構(gòu)考點(diǎn)考點(diǎn) 6 6：隊(duì)列及其基本運(yùn)算：隊(duì)列及其基本運(yùn)算1 1、隊(duì)列的定義、隊(duì)列的定義隊(duì)列的概念：是指允許在一端進(jìn)行插入而另一端進(jìn)行刪除的線性表。隊(duì)列的概念：是指允許在一端進(jìn)行插入而另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常使用指針

13、允許插入的一端稱為隊(duì)尾，通常使用指針rearrear 表示。尾指針總是指向最后插入表示。尾指針總是指向最后插入的元素；允許刪除的一端稱為排頭，通常使用指針的元素；允許刪除的一端稱為排頭，通常使用指針 frontfront 表示，排頭指針指向表示，排頭指針指向排頭元素的前一個(gè)位置。排頭元素的前一個(gè)位置。隊(duì)列的概念就是先進(jìn)先出或后進(jìn)后出隊(duì)列的概念就是先進(jìn)先出或后進(jìn)后出2 2、循環(huán)隊(duì)列及其運(yùn)算、循環(huán)隊(duì)列及其運(yùn)算1.41.4 線性鏈表線性鏈表考點(diǎn)考點(diǎn) 7 7：線性鏈表的基本概念：線性鏈表的基本概念重點(diǎn)掌握概念重點(diǎn)掌握概念在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

14、中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式既可以用于表示線性結(jié)構(gòu)，也可以表示非線性指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式既可以用于表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。結(jié)構(gòu)?？偨Y(jié)：總結(jié)：鏈?zhǔn)酱鎯?chǔ)所占有的空間一般情況是比順序存儲(chǔ)所占的空間要大鏈?zhǔn)酱鎯?chǔ)所占有的空間一般情況是比順序存儲(chǔ)所占的空間要大1.51.5 樹與二叉樹樹與二叉樹考點(diǎn)考點(diǎn) 8 8：樹與二叉樹：樹與二叉樹1 1、樹的基本概念、樹的基本概念需要掌握以下樹的基本概念：需要掌握

15、以下樹的基本概念：根節(jié)點(diǎn)：沒有前件的節(jié)點(diǎn)，稱為根節(jié)點(diǎn)根節(jié)點(diǎn)：沒有前件的節(jié)點(diǎn)，稱為根節(jié)點(diǎn)兄弟節(jié)點(diǎn)：擁有同一個(gè)前件的節(jié)點(diǎn)，稱為兄弟節(jié)點(diǎn)兄弟節(jié)點(diǎn)：擁有同一個(gè)前件的節(jié)點(diǎn)，稱為兄弟節(jié)點(diǎn)葉子節(jié)點(diǎn)：沒有后件的節(jié)點(diǎn)，稱為葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)：沒有后件的節(jié)點(diǎn)，稱為葉子節(jié)點(diǎn)節(jié)點(diǎn)的度：該節(jié)點(diǎn)所擁有的后件的個(gè)數(shù)，或某一個(gè)節(jié)點(diǎn)所擁有子節(jié)點(diǎn)的個(gè)數(shù)。節(jié)點(diǎn)的度：該節(jié)點(diǎn)所擁有的后件的個(gè)數(shù)，或某一個(gè)節(jié)點(diǎn)所擁有子節(jié)點(diǎn)的個(gè)數(shù)。樹的度：在一個(gè)樹結(jié)構(gòu)中，該節(jié)點(diǎn)擁有的最大子節(jié)點(diǎn)個(gè)數(shù)，稱為該樹的度。樹的度：在一個(gè)樹結(jié)構(gòu)中，該節(jié)點(diǎn)擁有的最大子節(jié)點(diǎn)個(gè)數(shù)，稱為該樹的度。樹的深度：樹的最深層次數(shù)，就稱之為樹的深度樹的深度：樹的最深層次數(shù)，就稱之為樹的深

16、度2 2、什么是二叉樹、什么是二叉樹二叉樹的概念：該樹中的最大節(jié)點(diǎn)的度為二叉樹的概念：該樹中的最大節(jié)點(diǎn)的度為 2 2二叉樹中有：度為二叉樹中有：度為 0 0 的節(jié)點(diǎn)的節(jié)點(diǎn)( (葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)) )、度為、度為 1 1 的節(jié)點(diǎn)、度為的節(jié)點(diǎn)、度為 2 2 的節(jié)點(diǎn)的節(jié)點(diǎn)二叉樹的特點(diǎn)：二叉樹的特點(diǎn)：非空的二叉樹只有一個(gè)根節(jié)點(diǎn)非空的二叉樹只有一個(gè)根節(jié)點(diǎn)每一個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹，且分別稱為該節(jié)點(diǎn)的左子樹和右子樹每一個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹，且分別稱為該節(jié)點(diǎn)的左子樹和右子樹3 3、二叉樹的性質(zhì)、二叉樹的性質(zhì)（1 1）在二叉樹的第）在二叉樹的第 k k 層上，最多有層上，最多有 2 2k-1k-1（k=1k=1

17、）個(gè)節(jié)點(diǎn)）個(gè)節(jié)點(diǎn)分析：第分析：第 k k 層，最多擁有層，最多擁有 2 2k-1k-1（k=1k=1）個(gè)節(jié)點(diǎn)是指該層處于滿節(jié)點(diǎn)情況。每一層）個(gè)節(jié)點(diǎn)是指該層處于滿節(jié)點(diǎn)情況。每一層能夠容納的最大節(jié)點(diǎn)個(gè)數(shù)。能夠容納的最大節(jié)點(diǎn)個(gè)數(shù)。（2 2）深度為）深度為 m m 的二叉樹最多有的二叉樹最多有 2 2m m-1-1 個(gè)節(jié)點(diǎn)。深度為個(gè)節(jié)點(diǎn)。深度為 m m 是指二叉樹有是指二叉樹有 m m 層。層。分析：分析： 深度為深度為 m m 的二叉樹最多有的二叉樹最多有 2 2m m-1-1 個(gè)節(jié)點(diǎn)，個(gè)節(jié)點(diǎn)， 是指該二叉樹是滿二叉樹的情況。是指該二叉樹是滿二叉樹的情況。（3 3）在任意一顆二叉樹中，度為）在任意一

18、顆二叉樹中，度為0 0 的節(jié)點(diǎn)（葉子節(jié)點(diǎn)）總是比度為的節(jié)點(diǎn)（葉子節(jié)點(diǎn)）總是比度為2 2 的節(jié)點(diǎn)多的節(jié)點(diǎn)多1 1 個(gè)。個(gè)。4 4、滿二叉樹與完全二叉樹、滿二叉樹與完全二叉樹（1 1）滿二叉樹）滿二叉樹概念：滿二叉樹是指該樹每一層節(jié)點(diǎn)數(shù)都滿足性質(zhì)概念：滿二叉樹是指該樹每一層節(jié)點(diǎn)數(shù)都滿足性質(zhì) 1 1說明：滿二叉樹是指每一層的節(jié)點(diǎn)數(shù)都滿足最大節(jié)點(diǎn)數(shù)說明：滿二叉樹是指每一層的節(jié)點(diǎn)數(shù)都滿足最大節(jié)點(diǎn)數(shù)（2 2）完全二叉樹）完全二叉樹概念：完全二叉樹是指該樹的最后一層從右邊開始缺少葉子節(jié)點(diǎn)，其他層的節(jié)概念：完全二叉樹是指該樹的最后一層從右邊開始缺少葉子節(jié)點(diǎn)，其他層的節(jié)點(diǎn)數(shù)滿足性質(zhì)點(diǎn)數(shù)滿足性質(zhì) 1 1說明：說明

19、：完全二叉樹除了最后一層不滿足性質(zhì)完全二叉樹除了最后一層不滿足性質(zhì) 1 1，其他都滿足，其他都滿足，并且最后一層從右并且最后一層從右邊開始缺少葉子節(jié)點(diǎn)。邊開始缺少葉子節(jié)點(diǎn)。總結(jié)：總結(jié)：計(jì)算二叉樹中節(jié)點(diǎn)總數(shù)的公式：計(jì)算二叉樹中節(jié)點(diǎn)總數(shù)的公式：節(jié)點(diǎn)總數(shù)節(jié)點(diǎn)總數(shù) = = 度為度為 0 0 的節(jié)點(diǎn)數(shù)的節(jié)點(diǎn)數(shù) + + 度為度為 1 1 的節(jié)點(diǎn)數(shù)的節(jié)點(diǎn)數(shù) + + 度為度為 2 2 的節(jié)點(diǎn)數(shù)的節(jié)點(diǎn)數(shù)計(jì)算二叉樹中葉子節(jié)點(diǎn)總數(shù)的公式：計(jì)算二叉樹中葉子節(jié)點(diǎn)總數(shù)的公式：度為度為 0 0 的節(jié)點(diǎn)總數(shù)的節(jié)點(diǎn)總數(shù) = = 度為度為 2 2 的節(jié)點(diǎn)總數(shù)的節(jié)點(diǎn)總數(shù) + 1 + 1計(jì)算二叉樹中度為計(jì)算二叉樹中度為 2 2 的節(jié)

20、點(diǎn)的總數(shù)的公式：的節(jié)點(diǎn)的總數(shù)的公式：度為度為 2 2 的節(jié)點(diǎn)總數(shù)的節(jié)點(diǎn)總數(shù) = = 度為度為 0 0 的節(jié)點(diǎn)總數(shù)的節(jié)點(diǎn)總數(shù) 1 1考點(diǎn)考點(diǎn) 9 9：二叉樹的遍歷：二叉樹的遍歷二叉樹的遍歷有三種：前序遍歷、中序遍歷、后序遍歷二叉樹的遍歷有三種：前序遍歷、中序遍歷、后序遍歷（1 1）前序遍歷）前序遍歷先根，后左先根，后左( (左子樹左子樹) )，再右，再右( (右子樹右子樹) )（2 2）中序遍歷）中序遍歷先左先左( (左子樹左子樹) )，后根，再右，后根，再右( (右子樹右子樹) )（3 3）后序遍歷）后序遍歷先左先左( (左子樹左子樹) )，后右，后右( (右子樹右子樹) )，再根，再根1.6

21、1.6 查找技術(shù)查找技術(shù)重點(diǎn)掌握時(shí)間復(fù)雜度重點(diǎn)掌握時(shí)間復(fù)雜度考點(diǎn)考點(diǎn) 1010：順序查找：順序查找順序查找的時(shí)間復(fù)雜度：順序查找的時(shí)間復(fù)雜度：如果順序的線性表長(zhǎng)度為如果順序的線性表長(zhǎng)度為 n n，那么，查找其中滿足條件的元素，那么，查找其中滿足條件的元素，最好的情況下，時(shí)間復(fù)雜度為：最好的情況下，時(shí)間復(fù)雜度為：1 1最壞的情況下，時(shí)間復(fù)雜度為：最壞的情況下，時(shí)間復(fù)雜度為：n n沒有找到的時(shí)間復(fù)雜度：沒有找到的時(shí)間復(fù)雜度：n n考點(diǎn)考點(diǎn) 1111：二分查找：二分查找二分查找的時(shí)間復(fù)雜度：二分查找的時(shí)間復(fù)雜度：最壞的情況下的時(shí)間復(fù)雜度為：最壞的情況下的時(shí)間復(fù)雜度為：loglog2 2n n注意：注

22、意：時(shí)間復(fù)雜度也可以表示為數(shù)學(xué)的函數(shù)形式：時(shí)間復(fù)雜度也可以表示為數(shù)學(xué)的函數(shù)形式：二分查找的時(shí)間復(fù)雜度為：二分查找的時(shí)間復(fù)雜度為：loglog2 2n n或或 o(log o(log2 2n)n)1.71.7 排序技術(shù)排序技術(shù)考點(diǎn)考點(diǎn) 1212：各種排序方法：各種排序方法1 1、冒泡排序法、冒泡排序法時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：最壞情況下：最壞情況下：n(n-1)/2n(n-1)/2或或 on(n-1)/2 on(n-1)/22 2、快速排序法、快速排序法時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：最壞的情況下：最壞的情況下：cmax = n(n-1)/2cmax = n(n-1)/2或或 on(n-1)/2 on(n

23、-1)/2其中其中 cmaxcmax 是指比較次數(shù)達(dá)到最大次數(shù)是指比較次數(shù)達(dá)到最大次數(shù)3 3、簡(jiǎn)單插入排序法、簡(jiǎn)單插入排序法時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：最壞的情況下：最壞的情況下：n(n-1)/2n(n-1)/2或或 on(n-1)/2 on(n-1)/24 4、希爾排序、希爾排序時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：最壞的情況下：最壞的情況下：n n1.51.5或或 o(n o(n1.51.5) )5 5、簡(jiǎn)單選擇排序法、簡(jiǎn)單選擇排序法時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：最壞的情況下：最壞的情況下：n(n-1)/2n(n-1)/2或或 on(n-1)/2 on(n-1)/26 6、堆排序法、堆排序法時(shí)間復(fù)雜度：時(shí)間復(fù)雜度

24、：nlognlog2 2n n或或 o(nlog o(nlog2 2n)n)時(shí)間復(fù)雜度總結(jié)：時(shí)間復(fù)雜度總結(jié)：堆排序：堆排序： o(nlogo(nlog2 2n)n)、 希爾排序：希爾排序： o(no(n1.51.5) )、 二分法查找：二分法查找： o(logo(log2 2n)n)， 其他都是其他都是 n(n-1)/2n(n-1)/2必考點(diǎn)：必考點(diǎn)：算法的概念、時(shí)間復(fù)雜度、空間復(fù)雜度、線性結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、棧、算法的概念、時(shí)間復(fù)雜度、空間復(fù)雜度、線性結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、棧、隊(duì)列、二叉樹隊(duì)列、二叉樹第二章第二章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)2.12.1 程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)風(fēng)格考點(diǎn)考

25、點(diǎn) 1 1：程序設(shè)計(jì)風(fēng)格：程序設(shè)計(jì)風(fēng)格1 1、源程序文檔化、源程序文檔化需要考慮的情況有：需要考慮的情況有：（1 1）符號(hào)名的命名符號(hào)名的命名: :符號(hào)名最好是有意義的名稱符號(hào)名最好是有意義的名稱（2 2）程序注釋：程序中最好添加注釋程序注釋：程序中最好添加注釋程序的注釋分為兩種：程序的注釋分為兩種：功能性注釋功能性注釋序言性注釋序言性注釋（3 3）視覺組織）視覺組織2 2、數(shù)據(jù)說明的方法、數(shù)據(jù)說明的方法3 3、語句的結(jié)構(gòu)：三大基本結(jié)構(gòu)（順序結(jié)構(gòu)、判斷結(jié)構(gòu)、重復(fù)結(jié)構(gòu)）、語句的結(jié)構(gòu)：三大基本結(jié)構(gòu)（順序結(jié)構(gòu)、判斷結(jié)構(gòu)、重復(fù)結(jié)構(gòu)）重點(diǎn)掌握：清晰第一、效率第二重點(diǎn)掌握：清晰第一、效率第二4 4、輸入和

26、輸出、輸入和輸出注意：掌握，程序必須要符合高內(nèi)聚，底耦合注意：掌握，程序必須要符合高內(nèi)聚，底耦合2.22.2 結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)考點(diǎn)考點(diǎn) 2 2：結(jié)構(gòu)化程序設(shè)計(jì)的原則：結(jié)構(gòu)化程序設(shè)計(jì)的原則主要的原則有四點(diǎn)：主要的原則有四點(diǎn)：（1 1）自頂向下自頂向下（2 2）逐步求精逐步求精（3 3）模塊化模塊化（4 4）限制使用限制使用 gotogoto 語句語句考點(diǎn)考點(diǎn) 3 3：結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)：結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)程序設(shè)計(jì)中有三大基本結(jié)構(gòu)：程序設(shè)計(jì)中有三大基本結(jié)構(gòu)：（1 1）順序結(jié)構(gòu)順序結(jié)構(gòu)（2 2）選擇結(jié)構(gòu)選擇結(jié)構(gòu)（3 3）重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）考點(diǎn)考點(diǎn) 4

27、 4：結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用：結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用結(jié)構(gòu)化程序設(shè)計(jì)的原則主要把握以下內(nèi)容：結(jié)構(gòu)化程序設(shè)計(jì)的原則主要把握以下內(nèi)容：（1 1）盡量使用順序結(jié)構(gòu)、選擇結(jié)構(gòu)、重復(fù)結(jié)構(gòu)來表示程序）盡量使用順序結(jié)構(gòu)、選擇結(jié)構(gòu)、重復(fù)結(jié)構(gòu)來表示程序（2 2）選用的控制結(jié)構(gòu)只允許有一個(gè)入口和一個(gè)出口）選用的控制結(jié)構(gòu)只允許有一個(gè)入口和一個(gè)出口（3 3）程序語句組成容易識(shí)別的模塊，每一個(gè)模塊只有一個(gè)入口和一個(gè)出口）程序語句組成容易識(shí)別的模塊，每一個(gè)模塊只有一個(gè)入口和一個(gè)出口（4 4）復(fù)雜的結(jié)構(gòu)應(yīng)該使用三大基本來嵌套）復(fù)雜的結(jié)構(gòu)應(yīng)該使用三大基本來嵌套（5 5）語句中沒有的控制語句，則前后一致進(jìn)行模擬）

28、語句中沒有的控制語句，則前后一致進(jìn)行模擬（6 6）嚴(yán)格控制）嚴(yán)格控制 gotogoto 語句語句2.32.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)注意：到目前為止，程序設(shè)計(jì)主要分為兩種：注意：到目前為止，程序設(shè)計(jì)主要分為兩種：第一種：結(jié)構(gòu)化程序設(shè)計(jì)第一種：結(jié)構(gòu)化程序設(shè)計(jì)第二種：面向?qū)ο蟮某绦蛟O(shè)計(jì)第二種：面向?qū)ο蟮某绦蛟O(shè)計(jì)考點(diǎn)考點(diǎn) 5 5：面向?qū)ο蠓椒ǖ幕靖拍睿好嫦驅(qū)ο蠓椒ǖ幕靖拍? 1、對(duì)象、對(duì)象(object)(object)（1 1）標(biāo)識(shí)唯一性）標(biāo)識(shí)唯一性（2 2）分類性）分類性（3 3）多態(tài)性：相同的消息對(duì)不同的對(duì)象有不同的動(dòng)作）多態(tài)性：相同的消息對(duì)不同的對(duì)象有不同的動(dòng)作（4 4）封

29、裝性：）封裝性：這里需要注意：這里需要注意：封裝性與隱藏性的不同封裝性與隱藏性的不同（5 5）模塊獨(dú)立性較好）模塊獨(dú)立性較好注意：模塊與其他不同模塊聯(lián)系越少，就說明獨(dú)立性越好注意：模塊與其他不同模塊聯(lián)系越少，就說明獨(dú)立性越好2 2、類、類將屬性、操作將屬性、操作( (方法方法) )相似的對(duì)象歸為一類相似的對(duì)象歸為一類3 3、消息、消息概念：面向?qū)ο蟮氖澜缡峭ㄟ^對(duì)象與對(duì)象彼此的合作來推動(dòng)的，對(duì)象之間的這概念：面向?qū)ο蟮氖澜缡峭ㄟ^對(duì)象與對(duì)象彼此的合作來推動(dòng)的，對(duì)象之間的這種相互合作需要一個(gè)機(jī)制來協(xié)助進(jìn)行，這種機(jī)制就稱之為“消息”種相互合作需要一個(gè)機(jī)制來協(xié)助進(jìn)行，這種機(jī)制就稱之為“消息”4 4、繼承

30、、繼承相似生物學(xué)中的遺傳相似生物學(xué)中的遺傳繼承是指子類承接了父類的某一些特性和方法繼承是指子類承接了父類的某一些特性和方法也就是說，子類具有一些父類共同的特征也就是說，子類具有一些父類共同的特征5 5、多態(tài)性、多態(tài)性概念：對(duì)象根據(jù)所接收的消息而做出的動(dòng)作概念：對(duì)象根據(jù)所接收的消息而做出的動(dòng)作第三章第三章 軟件工程基礎(chǔ)軟件工程基礎(chǔ)3.13.1 軟件工程的基本概念軟件工程的基本概念考點(diǎn)考點(diǎn) 1 1：軟件的定義與分類：軟件的定義與分類軟件的分類：軟件的分類：按功能分類：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件按功能分類：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件( (工具工具) )軟件工程的概念：是應(yīng)用于計(jì)算機(jī)軟件的定義、開

31、發(fā)和維護(hù)的一整套的方法、軟件工程的概念：是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套的方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序軟件危機(jī)：軟件危機(jī)：主要是指軟件的開發(fā)過程當(dāng)中，軟件的質(zhì)量不好控制、預(yù)算經(jīng)常超支、軟件開主要是指軟件的開發(fā)過程當(dāng)中，軟件的質(zhì)量不好控制、預(yù)算經(jīng)常超支、軟件開發(fā)不規(guī)范、軟件開發(fā)的效率比較低下。發(fā)不規(guī)范、軟件開發(fā)的效率比較低下。軟件工程有三要素：軟件工程有三要素：方法、工具方法、工具和過程和過程在第三章中，在第三章中，重點(diǎn)掌握方法和工具重點(diǎn)掌握方法和工具軟件的分類：軟件的分類：系統(tǒng)軟件：主要是指操作系統(tǒng)系統(tǒng)軟件：主要是指操作系統(tǒng)應(yīng)用軟件：我們?cè)诓僮飨到y(tǒng)中一

32、般使用的軟件大多都屬于應(yīng)用軟件應(yīng)用軟件：我們?cè)诓僮飨到y(tǒng)中一般使用的軟件大多都屬于應(yīng)用軟件支撐軟件：一般是對(duì)某一種應(yīng)用或服務(wù)的支持，這類軟件稱之為支持軟件，例支撐軟件：一般是對(duì)某一種應(yīng)用或服務(wù)的支持，這類軟件稱之為支持軟件，例如：手機(jī)或固定電話的收費(fèi)系統(tǒng)如：手機(jī)或固定電話的收費(fèi)系統(tǒng)在第三章中，重點(diǎn)掌握，軟件工程的執(zhí)行過程當(dāng)中的，每一個(gè)階段的方法和工在第三章中，重點(diǎn)掌握，軟件工程的執(zhí)行過程當(dāng)中的，每一個(gè)階段的方法和工具，也就是在每一個(gè)階段使用的什么方法、使用了什么工具，這里是需要重點(diǎn)具，也就是在每一個(gè)階段使用的什么方法、使用了什么工具，這里是需要重點(diǎn)掌握的。掌握的?？键c(diǎn)考點(diǎn) 2 2：軟件的生命周期

33、：軟件的生命周期軟件開發(fā)的周期主要包括三大階段：軟件開發(fā)的周期主要包括三大階段：（1 1）定義階段）定義階段可行性分析、需求分析可行性分析、需求分析（2 2）開發(fā)階段）開發(fā)階段概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)( (編碼寫程序編碼寫程序) )、調(diào)試、調(diào)試（3 3）維護(hù)階段）維護(hù)階段使用、維護(hù)、退役使用、維護(hù)、退役3.23.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法考點(diǎn)考點(diǎn) 3 3：關(guān)于結(jié)構(gòu)化分析的常用工具：關(guān)于結(jié)構(gòu)化分析的常用工具重點(diǎn)掌握重點(diǎn)掌握數(shù)據(jù)流圖數(shù)據(jù)流圖和和數(shù)據(jù)字典數(shù)據(jù)字典結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求階段的運(yùn)用，是使用數(shù)據(jù)流結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需

34、求階段的運(yùn)用，是使用數(shù)據(jù)流圖圖(dfd)(dfd)、數(shù)據(jù)字典（、數(shù)據(jù)字典（dddd） 、結(jié)構(gòu)化語言和判定樹、判定表等工具。、結(jié)構(gòu)化語言和判定樹、判定表等工具。1 1、數(shù)據(jù)流圖、數(shù)據(jù)流圖數(shù)據(jù)流圖（數(shù)據(jù)流圖（dfddfd） ：是描述數(shù)據(jù)處理工程的工具：是描述數(shù)據(jù)處理工程的工具重點(diǎn)掌握，數(shù)據(jù)流圖中的箭頭圖元。箭頭這個(gè)圖元是指數(shù)據(jù)流重點(diǎn)掌握，數(shù)據(jù)流圖中的箭頭圖元。箭頭這個(gè)圖元是指數(shù)據(jù)流2 2、數(shù)據(jù)字典、數(shù)據(jù)字典數(shù)據(jù)字典（數(shù)據(jù)字典（dddd） ：是結(jié)構(gòu)化分析方法的核心：是結(jié)構(gòu)化分析方法的核心概念：數(shù)據(jù)字典是對(duì)數(shù)據(jù)流圖中出現(xiàn)的所有元素的具體的命名概念：數(shù)據(jù)字典是對(duì)數(shù)據(jù)流圖中出現(xiàn)的所有元素的具體的命名總結(jié)：

35、總結(jié)：在軟件工程的定義階段，需求分析需要使用的工具：數(shù)據(jù)流圖、數(shù)據(jù)字典；使在軟件工程的定義階段，需求分析需要使用的工具：數(shù)據(jù)流圖、數(shù)據(jù)字典；使用的方法是結(jié)構(gòu)化分析方法用的方法是結(jié)構(gòu)化分析方法數(shù)據(jù)流圖中的所有定義的元素，在數(shù)據(jù)字典中解釋數(shù)據(jù)流圖中的所有定義的元素，在數(shù)據(jù)字典中解釋考點(diǎn)考點(diǎn) 4 4：軟件需求規(guī)格說明書：軟件需求規(guī)格說明書軟件需求規(guī)格說明書：是需求分析階段的最后成果，是軟件開發(fā)過程中的重要軟件需求規(guī)格說明書：是需求分析階段的最后成果，是軟件開發(fā)過程中的重要文檔之一。文檔之一。1 1、軟件需求規(guī)則說明書的作用、軟件需求規(guī)則說明書的作用（1 1）便于用戶、開發(fā)人員進(jìn)行理解和交流）便于用戶

36、、開發(fā)人員進(jìn)行理解和交流（2 2）反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)）反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)（3 3）作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)）作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)2 2、軟件需求規(guī)則說明書的內(nèi)容、軟件需求規(guī)則說明書的內(nèi)容( (了解了解) )3 3、軟件需求規(guī)則說明書的特點(diǎn)、軟件需求規(guī)則說明書的特點(diǎn)（1 1）正確性）正確性（2 2）無歧義性）無歧義性（3 3）完整性）完整性（4 4）可驗(yàn)證性）可驗(yàn)證性（5 5）一致性）一致性（6 6）可理解性）可理解性（7 7）可修改性）可修改性（8 8）可追蹤性）可追蹤性天要下雨留人不留天要下雨留人不留3.33.3 結(jié)

37、構(gòu)化設(shè)計(jì)方法結(jié)構(gòu)化設(shè)計(jì)方法考點(diǎn)考點(diǎn) 5 5：有關(guān)軟件設(shè)計(jì)的基本內(nèi)容：有關(guān)軟件設(shè)計(jì)的基本內(nèi)容1 1、軟件設(shè)計(jì)的基礎(chǔ)、軟件設(shè)計(jì)的基礎(chǔ)掌握此處的概念掌握此處的概念2 2、軟件設(shè)計(jì)的基本原理、軟件設(shè)計(jì)的基本原理（1 1）抽象：是指拋開表面現(xiàn)象，取得其本質(zhì)性的內(nèi)容，是一種分析方法）抽象：是指拋開表面現(xiàn)象，取得其本質(zhì)性的內(nèi)容，是一種分析方法（2 2）模塊化）模塊化（3 3）信息隱蔽）信息隱蔽內(nèi)聚性：是指一個(gè)模塊內(nèi)部結(jié)構(gòu)之間聯(lián)系的緊密程度內(nèi)聚性：是指一個(gè)模塊內(nèi)部結(jié)構(gòu)之間聯(lián)系的緊密程度耦合性：是指若干個(gè)模塊之間的聯(lián)系的緊密程度耦合性：是指若干個(gè)模塊之間的聯(lián)系的緊密程度軟件工程要求：高內(nèi)聚，低耦合軟件工程要求：

38、高內(nèi)聚，低耦合總結(jié)：總結(jié)：在軟件工程的過程當(dāng)中，軟件設(shè)計(jì)是指開發(fā)階段中的概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)在軟件工程的過程當(dāng)中，軟件設(shè)計(jì)是指開發(fā)階段中的概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)考點(diǎn)考點(diǎn) 6 6：結(jié)構(gòu)化設(shè)計(jì)方法的詳細(xì)設(shè)計(jì)：結(jié)構(gòu)化設(shè)計(jì)方法的詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)的過程中，我們所使用的工具：詳細(xì)設(shè)計(jì)的過程中，我們所使用的工具：圖形工具：程序流程圖、圖形工具：程序流程圖、n ns s 盒式圖、盒式圖、padpad、hipohipo表格工具：判斷表表格工具：判斷表語言工具：語言工具：pdlpdl（偽代碼、偽碼）（偽代碼、偽碼）（1 1）程序流程圖）程序流程圖重點(diǎn)掌握程序流程圖中的圖元：重點(diǎn)掌握程序流程圖中的圖元：箭頭：是指控制流箭

39、頭：是指控制流棱形：是指邏輯條件棱形：是指邏輯條件總結(jié)：總結(jié)：在數(shù)據(jù)流圖的工具中，箭頭是指數(shù)據(jù)流在數(shù)據(jù)流圖的工具中，箭頭是指數(shù)據(jù)流在程序流程圖的工具中，箭頭是指控制流在程序流程圖的工具中，箭頭是指控制流（2 2）n ns s 盒式圖盒式圖n ns s 盒式圖是對(duì)程序流程圖的改進(jìn)盒式圖是對(duì)程序流程圖的改進(jìn)（3 3）padpad 圖圖padpad 圖是問題分析圖圖是問題分析圖（4 4）pdlpdl過程設(shè)計(jì)語言，也稱為結(jié)構(gòu)化的英語和偽碼過程設(shè)計(jì)語言，也稱為結(jié)構(gòu)化的英語和偽碼補(bǔ)充：補(bǔ)充：在軟件工程中，軟件系統(tǒng)結(jié)構(gòu)圖的寬度、深度要求掌握在軟件工程中，軟件系統(tǒng)結(jié)構(gòu)圖的寬度、深度要求掌握寬度的概念：是指軟件

40、系統(tǒng)結(jié)構(gòu)圖中，某一層擁有最大的模塊數(shù)寬度的概念：是指軟件系統(tǒng)結(jié)構(gòu)圖中，某一層擁有最大的模塊數(shù)深度的概念：是指軟件系統(tǒng)結(jié)構(gòu)圖中，所擁有最大層次數(shù)深度的概念：是指軟件系統(tǒng)結(jié)構(gòu)圖中，所擁有最大層次數(shù)3.43.4 軟件測(cè)試軟件測(cè)試考點(diǎn)考點(diǎn) 7 7：軟件測(cè)試的目的：軟件測(cè)試的目的軟件測(cè)試的目的：使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的軟件測(cè)試的目的：使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清楚預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清楚預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。軟件測(cè)試的目的（簡(jiǎn)單的）軟件測(cè)試的目的（簡(jiǎn)單的） ：就是發(fā)

41、現(xiàn)錯(cuò)誤而執(zhí)行程序的過程：就是發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程考點(diǎn)考點(diǎn) 8 8：軟件測(cè)試的方法與技術(shù)：軟件測(cè)試的方法與技術(shù)1 1、靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試、靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試軟件測(cè)試從是否需要執(zhí)行被測(cè)試軟件的角度來分類，分為兩種：軟件測(cè)試從是否需要執(zhí)行被測(cè)試軟件的角度來分類，分為兩種：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試（1 1）靜態(tài)測(cè)試：使用人工的方式來靜態(tài)檢查軟件的代碼靜態(tài)測(cè)試：使用人工的方式來靜態(tài)檢查軟件的代碼（2 2）動(dòng)態(tài)測(cè)試：使用計(jì)算機(jī)來執(zhí)行測(cè)試軟件動(dòng)態(tài)測(cè)試：使用計(jì)算機(jī)來執(zhí)行測(cè)試軟件2 2、黑盒測(cè)試和白盒測(cè)試、黑盒測(cè)試和白盒測(cè)試白盒測(cè)試：主要是指在測(cè)試的過程中可以看到軟件內(nèi)部的代碼白盒測(cè)試：主要是指

42、在測(cè)試的過程中可以看到軟件內(nèi)部的代碼黑盒測(cè)試：主要是指在測(cè)試的過程中不可以看到軟件內(nèi)部的代碼黑盒測(cè)試：主要是指在測(cè)試的過程中不可以看到軟件內(nèi)部的代碼白盒測(cè)試的基本原則：白盒測(cè)試的基本原則：保證所測(cè)試的模塊中每一個(gè)獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)試模塊所有判斷保證所測(cè)試的模塊中每一個(gè)獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)試模塊所有判斷的每一個(gè)分支至少執(zhí)行一次；保證所測(cè)試模塊每一個(gè)循環(huán)都在邊界條件和一般的每一個(gè)分支至少執(zhí)行一次；保證所測(cè)試模塊每一個(gè)循環(huán)都在邊界條件和一般條件下至少執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。條件下至少執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。白盒測(cè)試的主要方法有：白盒測(cè)試的主要方法

43、有：（1 1）邏輯覆蓋測(cè)試邏輯覆蓋測(cè)試（2 2）基本路徑測(cè)試基本路徑測(cè)試3 3、黑盒測(cè)試、黑盒測(cè)試黑盒測(cè)試也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。黑盒測(cè)試也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。黑盒測(cè)試主要有：等價(jià)類劃分、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等。黑盒測(cè)試主要有：等價(jià)類劃分、邊界值分析法、錯(cuò)誤推測(cè)法、因果圖等。（1 1）等價(jià)類劃分法等價(jià)類劃分法（2 2）邊界值分析法邊界值分析法（3 3）錯(cuò)誤推測(cè)法錯(cuò)誤推測(cè)法考點(diǎn)考點(diǎn) 9 9：軟件測(cè)試的實(shí)施：軟件測(cè)試的實(shí)施軟件測(cè)試的一般過程按照軟件測(cè)試的一般過程按照 4 4 個(gè)步驟：個(gè)步驟：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試和系統(tǒng)測(cè)試單元測(cè)試、集成測(cè)試、驗(yàn)收測(cè)試和系統(tǒng)測(cè)試（1

44、1）單元測(cè)試）單元測(cè)試單元測(cè)試是指對(duì)軟件中的最小模塊進(jìn)行測(cè)試單元測(cè)試是指對(duì)軟件中的最小模塊進(jìn)行測(cè)試（2 2）集成測(cè)試）集成測(cè)試集成測(cè)試是指測(cè)試與組裝軟件的過程集成測(cè)試是指測(cè)試與組裝軟件的過程（3 3）驗(yàn)收測(cè)試）驗(yàn)收測(cè)試驗(yàn)收測(cè)試是指驗(yàn)證軟件的功能與性能驗(yàn)收測(cè)試是指驗(yàn)證軟件的功能與性能（4 4）系統(tǒng)測(cè)試）系統(tǒng)測(cè)試系統(tǒng)測(cè)試是指軟件在一定具體的環(huán)境下運(yùn)行的過程測(cè)試系統(tǒng)測(cè)試是指軟件在一定具體的環(huán)境下運(yùn)行的過程測(cè)試3.53.5 程序的調(diào)試程序的調(diào)試考點(diǎn)考點(diǎn) 1010：基本概念：基本概念重點(diǎn)掌握：重點(diǎn)掌握：調(diào)試的目的和任務(wù)調(diào)試的目的和任務(wù)調(diào)試的任務(wù)：就是診斷和修改程序中的錯(cuò)誤調(diào)試的任務(wù)：就是診斷和修改程序中

45、的錯(cuò)誤簡(jiǎn)單來說：改錯(cuò)誤簡(jiǎn)單來說：改錯(cuò)誤調(diào)試的目的：更正錯(cuò)誤調(diào)試的目的：更正錯(cuò)誤第四章第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4.14.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念數(shù)據(jù)庫(kù)系統(tǒng)的基本概念考點(diǎn)考點(diǎn) 1 1：數(shù)據(jù)庫(kù)與數(shù)據(jù)庫(kù)管理系統(tǒng)：數(shù)據(jù)庫(kù)與數(shù)據(jù)庫(kù)管理系統(tǒng)vfvf 是一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)，是一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)，dbmsdbms數(shù)據(jù)數(shù)據(jù)(data):(data):數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)(database):db(database):db數(shù)據(jù)定義語言數(shù)據(jù)定義語言(ddl)(ddl)：createcreate、dropdrop、alteralter數(shù)據(jù)操縱語言數(shù)據(jù)操縱語言(dml)(dml)：selectselect、inser

46、tinsert、updateupdate、deletedelete數(shù)據(jù)控制語言數(shù)據(jù)控制語言(dcl)(dcl)：考點(diǎn)考點(diǎn) 2 2：數(shù)據(jù)庫(kù)系統(tǒng)：數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)（簡(jiǎn)稱為數(shù)據(jù)庫(kù)系統(tǒng)（簡(jiǎn)稱為 dbsdbs） ：由以下部分組成：數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)：由以下部分組成：數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)、數(shù)據(jù)庫(kù)管理員、系統(tǒng)平臺(tái)庫(kù)管理員、系統(tǒng)平臺(tái)( (軟件平臺(tái)和硬件平臺(tái)軟件平臺(tái)和硬件平臺(tái)) )數(shù)據(jù)庫(kù)系統(tǒng)包含數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)包含數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)管理系統(tǒng)dbsdbs 包含包含 dbdb 和和 dbmsdbms考點(diǎn)考點(diǎn) 3 3：數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展：數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展階段主要有三種：數(shù)據(jù)庫(kù)

47、系統(tǒng)的發(fā)展階段主要有三種：人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫(kù)系統(tǒng)階段人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫(kù)系統(tǒng)階段考點(diǎn)考點(diǎn) 4 4：數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)：數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)1 1、數(shù)據(jù)的集成性、數(shù)據(jù)的集成性主要表現(xiàn)在三個(gè)方面主要表現(xiàn)在三個(gè)方面2 2、數(shù)據(jù)的高共享性和低冗余性、數(shù)據(jù)的高共享性和低冗余性3 3、數(shù)據(jù)獨(dú)立性、數(shù)據(jù)獨(dú)立性數(shù)據(jù)的獨(dú)立性的概念：是指數(shù)據(jù)與程序之間相互不依賴數(shù)據(jù)的獨(dú)立性的概念：是指數(shù)據(jù)與程序之間相互不依賴數(shù)據(jù)獨(dú)立性分為物理獨(dú)立性和邏輯獨(dú)立性數(shù)據(jù)獨(dú)立性分為物理獨(dú)立性和邏輯獨(dú)立性物理獨(dú)立性的概念：物理獨(dú)立性是指數(shù)據(jù)的物理結(jié)構(gòu)的改變，不影響數(shù)據(jù)庫(kù)物理獨(dú)立性的概念：物理獨(dú)立性是指數(shù)據(jù)的

48、物理結(jié)構(gòu)的改變，不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)。的邏輯結(jié)構(gòu)。邏輯獨(dú)立性的概念：數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，不需要相應(yīng)修改程序邏輯獨(dú)立性的概念：數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，不需要相應(yīng)修改程序4 4、數(shù)據(jù)的統(tǒng)一管理與控制、數(shù)據(jù)的統(tǒng)一管理與控制（1 1）數(shù)據(jù)的完整性檢查）數(shù)據(jù)的完整性檢查（2 2）數(shù)據(jù)的安全性保護(hù)）數(shù)據(jù)的安全性保護(hù)（3 3）并發(fā)控制）并發(fā)控制考點(diǎn)考點(diǎn) 5 5：數(shù)據(jù)模式：數(shù)據(jù)模式數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部具有三級(jí)模式和二級(jí)映射數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部具有三級(jí)模式和二級(jí)映射其中，三級(jí)模式是指概念模式、內(nèi)部模式和外部模式其中，三級(jí)模式是指概念模式、內(nèi)部模式和外部模式其中，二級(jí)映射是指概念模式到內(nèi)部模式的映射、外部模式到概念

49、模式的映射其中，二級(jí)映射是指概念模式到內(nèi)部模式的映射、外部模式到概念模式的映射（1 1）概念模式）概念模式概念模式是數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶的公共數(shù)據(jù)視概念模式是數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶的公共數(shù)據(jù)視圖圖（2 2）外模式）外模式外模式一般又稱之為“子模式”或“用戶模式”外模式一般又稱之為“子模式”或“用戶模式”數(shù)據(jù)庫(kù)的外模式，一般是指數(shù)據(jù)庫(kù)的操作界面數(shù)據(jù)庫(kù)的外模式，一般是指數(shù)據(jù)庫(kù)的操作界面（3 3）內(nèi)模式）內(nèi)模式內(nèi)模式又稱為物理模式，給出數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。內(nèi)模式又稱為物理模式，給出數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。4.24.2 數(shù)據(jù)模型

50、數(shù)據(jù)模型考點(diǎn)考點(diǎn) 6 6：e-re-r 模型模型( (實(shí)體聯(lián)系模型實(shí)體聯(lián)系模型) )1 1、e-re-r 模型的基本概念模型的基本概念（1 1）實(shí)體）實(shí)體（2 2）屬性）屬性（3 3）聯(lián)系）聯(lián)系在在 vfvf 中的聯(lián)系一共有三個(gè)：中的聯(lián)系一共有三個(gè)：一對(duì)一聯(lián)系：可以表示為一對(duì)一聯(lián)系：可以表示為 1:11:1一對(duì)多聯(lián)系：可以表示一對(duì)多聯(lián)系：可以表示 1 1：n n多對(duì)多聯(lián)系：可以表示多對(duì)多聯(lián)系：可以表示 m m：n n2 2、e-re-r 模型模型 3 3 個(gè)基本概念之間的連接關(guān)系個(gè)基本概念之間的連接關(guān)系e-re-r 圖就是由實(shí)體、聯(lián)系、屬性三種元素組成圖就是由實(shí)體、聯(lián)系、屬性三種元素組成3 3

51、、e-re-r 模型的圖示法模型的圖示法（1 1）實(shí)體集的表示）實(shí)體集的表示實(shí)體集是使用矩形來表示實(shí)體集是使用矩形來表示（2 2）屬性的表示）屬性的表示屬性是使用橢圓來表示屬性是使用橢圓來表示（3 3）聯(lián)系的表示）聯(lián)系的表示聯(lián)系是使用棱形表示聯(lián)系是使用棱形表示（4 4）實(shí)體集與屬性之間的連接關(guān)系）實(shí)體集與屬性之間的連接關(guān)系實(shí)體集與屬性之間是使用直線來連接的實(shí)體集與屬性之間是使用直線來連接的（5 5）實(shí)體集與聯(lián)系之間的連接關(guān)系）實(shí)體集與聯(lián)系之間的連接關(guān)系實(shí)體集與聯(lián)系是使用直線連接實(shí)體集與聯(lián)系是使用直線連接考點(diǎn)考點(diǎn) 7 7：層次模型：層次模型層次模型的概念：是指其基本結(jié)構(gòu)為樹形結(jié)構(gòu)層次模型的概念：

52、是指其基本結(jié)構(gòu)為樹形結(jié)構(gòu)比較典型的層次模型是族譜比較典型的層次模型是族譜考點(diǎn)考點(diǎn) 8 8：關(guān)系模型：關(guān)系模型1 1、關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)、關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)關(guān)系模型一般使用二維表，簡(jiǎn)稱為表關(guān)系模型一般使用二維表，簡(jiǎn)稱為表二維表一般滿足一下二維表一般滿足一下 7 7 個(gè)性質(zhì)個(gè)性質(zhì)（1 1）二維表中元組個(gè)數(shù)是有限的二維表中元組個(gè)數(shù)是有限的（2 2）二維表中的元組均不相同二維表中的元組均不相同（3 3）元組的次序可以任意交換元組的次序可以任意交換（4 4）元組的列不可分，元組的列是具有原子性元組的列不可分，元組的列是具有原子性（5 5）屬性名稱不能相同屬性名稱不能相同（6 6）屬性的次序可以任意交換屬