1、全國(guó)計(jì)算機(jī)等級(jí)考試,National Computer Rank Examination,+,全國(guó)計(jì)算機(jī)等級(jí)考試,National Computer Rank Examination,第一部分 公共基礎(chǔ)知識(shí),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),3,二級(jí)公共基礎(chǔ)知識(shí)考試內(nèi)容,數(shù)據(jù)結(jié)構(gòu)和算法 程序設(shè)計(jì)基礎(chǔ) 軟件工程 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),4,1、二級(jí)公共基礎(chǔ)知識(shí)不單獨(dú)考試，與其他二級(jí)科目組合在一起，作為二級(jí)科目考核內(nèi)容的一部分。公共基礎(chǔ)部分占全卷的20分。 2、公共基礎(chǔ)知識(shí)考查方式為選擇題共20道。,二級(jí)公共基礎(chǔ)知識(shí)考試方式,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),

2、5,理解基本概念 多做練習(xí) 適當(dāng)記憶一些名詞 與所學(xué)程序設(shè)計(jì)語(yǔ)言結(jié)合起來(lái)理解,二級(jí)公共基礎(chǔ)知識(shí)學(xué)習(xí)方法,第一章 數(shù)據(jù)結(jié)構(gòu)和算法,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),7,本章知識(shí)要點(diǎn),算法,算法的定義,算法的特征,算法復(fù)雜度,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的定義,邏輯結(jié)構(gòu) 和 物理結(jié)構(gòu),線性結(jié)構(gòu) 和 非線性結(jié)構(gòu),順序表、鏈表、堆棧 隊(duì)列、循環(huán)隊(duì)列、樹(shù),算法的基本要素,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),8,算法是解決方案的準(zhǔn)確而完整性描述。,一、算法,算法的特性： （1）有窮性：算法必須在有限的次數(shù)內(nèi)完成。 （2）確定性：算法的每一步必須是明確的。 （3）可行性：算法的每一步必須是可以實(shí)現(xiàn)的。 （4）擁

3、有足夠的情報(bào)：算法必須有一定的輸入和輸出。,算法不等于程序，也不等于計(jì)算方法。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),9,算法的基本要素： （1）對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作： A .算術(shù)運(yùn)算 B .邏輯運(yùn)算 C .關(guān)系運(yùn)算 D .數(shù)據(jù)傳輸 （2）算法的控制結(jié)構(gòu)： A .順序結(jié)構(gòu) B .選擇結(jié)構(gòu) C .循環(huán)結(jié)構(gòu),一、算法,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),10,算法的復(fù)雜度：衡量算法優(yōu)劣的量。 （1）時(shí)間復(fù)雜度：算法的時(shí)間耗費(fèi)。 A .算法中基本操作重復(fù)執(zhí)行次數(shù)和算法執(zhí)行時(shí)間 同步增長(zhǎng)，稱作算法的時(shí)間復(fù)雜度。 B .算法中基本操作重復(fù)執(zhí)行次數(shù)和問(wèn)題規(guī)模有關(guān)， 是問(wèn)題規(guī)模的函數(shù)。 C .算法的時(shí)間

4、復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工 作量。 （2）空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間。,一、算法,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),11,例題 1、算法的基本特征是可行性、確定性、 和擁有足夠的情報(bào)。 2、算法具有4個(gè)特性，以下選項(xiàng)中不屬于算法特性的是（ ） A) 有窮性B) 簡(jiǎn)潔性C) 可行性D) 確定性3、算法的時(shí)間復(fù)雜度是指（ ） A) 執(zhí)行算法程序所需要的時(shí)間 B) 算法程序的長(zhǎng)度 C) 算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D) 算法程序中的指令條數(shù) 4、算法的空間復(fù)雜度是指（ ） A) 算法程序的長(zhǎng)度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲(chǔ)空間 D) 執(zhí)行過(guò)程中所需

5、要的存儲(chǔ)空間,一、算法,有窮性,B,C,D,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),12,5、在計(jì)算機(jī)中，算法是指（ ） A) 加工方法B) 解題方案的準(zhǔn)確而完整的描述 C) 排序方法D) 查詢方法 6、下列敘述中正確的是（ ） A) 算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)。 B) 算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。 C) 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的。 D) 算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)。,一、算法,B,B,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),13,二、數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)主要研究?jī)煞矫娴膯?wèn)題： （1）數(shù)據(jù)本身。 （2）數(shù)據(jù)之間的前后件關(guān)系。,數(shù)據(jù)結(jié)

6、構(gòu)表示為：DS=D，S 例：D=春，夏，秋，冬 S=(春,夏)，(夏,秋)，(秋,冬)，(冬,春),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),14,數(shù)據(jù)的結(jié)構(gòu)分為： （1）物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)介質(zhì)中真正存儲(chǔ)的結(jié)構(gòu)， 也被稱為“存儲(chǔ)結(jié)構(gòu)” （2）邏輯結(jié)構(gòu)：人們所理解的數(shù)據(jù)之間的結(jié)構(gòu)，可以用圖示 的方法繪畫(huà)出來(lái)的數(shù)據(jù)之間的結(jié)構(gòu)。,例：一個(gè)班由35名同學(xué)，他們的座位牌號(hào)就是物理結(jié)構(gòu)， 一次考試的排名是邏輯結(jié)構(gòu)。,注意：邏輯結(jié)構(gòu)和物理結(jié)構(gòu)沒(méi)有必然的聯(lián)系，也不一定是 一一對(duì)應(yīng)的。,二、數(shù)據(jù)結(jié)構(gòu),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),15,數(shù)據(jù)的結(jié)構(gòu)分為： （1）線性結(jié)構(gòu)： 非空數(shù)據(jù)結(jié)構(gòu)同時(shí)滿足以下兩個(gè)

7、條件就是線性結(jié)構(gòu)： A .有且僅有一個(gè)根結(jié)點(diǎn)； B .除頭結(jié)點(diǎn)和尾結(jié)點(diǎn)外，任何結(jié)點(diǎn)有且僅有一個(gè)前件 和一個(gè)后件。 （2）非線性結(jié)構(gòu)：除了線性結(jié)構(gòu)都是非線性結(jié)構(gòu)。,二、數(shù)據(jù)結(jié)構(gòu),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),16,全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)要求掌握的數(shù)據(jù)結(jié)構(gòu)共有以下六種：,線性表 堆棧 隊(duì)列 循環(huán)隊(duì)列 線性鏈表 樹(shù)和二叉樹(shù),線 性 結(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)和邏輯結(jié)構(gòu)不相同,非線性結(jié)構(gòu),二、數(shù)據(jù)結(jié)構(gòu),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),17,10,20,30,40,5

8、0,60,70,80,三、順序表：順序表就是數(shù)組,1、順序表也叫做線性表，屬于線性結(jié)構(gòu)。 線性表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相同。 2、特點(diǎn)： （1）有且僅有一個(gè)頭結(jié)點(diǎn)（根節(jié)點(diǎn)）和尾結(jié)點(diǎn)。 （2）任意其他結(jié)點(diǎn)至多有一個(gè)前件，一個(gè)后件。 （3）頭結(jié)點(diǎn)沒(méi)有前件，尾結(jié)點(diǎn)沒(méi)有后件。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),18,四、堆棧,1、定義：只允許在棧頂位置插 入數(shù)據(jù)和刪除數(shù)據(jù)的線性結(jié) 構(gòu)是堆棧，簡(jiǎn)稱為“?！?。 2、堆棧屬于線性結(jié)構(gòu)。 3、堆棧的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 相同。 4、特點(diǎn)：先進(jìn)后出，后進(jìn)先出 所以堆棧也叫做先進(jìn)后出表 （FILO） 5、堆棧具備存儲(chǔ)功能：函數(shù)的 遞歸調(diào)用和表達(dá)式求解都用 到了堆棧

9、。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),19,入棧順序：a、b、c、d、e、f,?？?a,b,a,c,b,a,b,a,d,b,a,.,入a,入b,入c,出c,入d,模擬堆棧的數(shù)據(jù)出入過(guò)程：,四、堆棧,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),20,【典型題型】 假設(shè)一個(gè)堆棧，入棧順序?yàn)閍bcde，認(rèn)為在任何時(shí)刻均允許出棧，下列選項(xiàng)中不可能的出棧順序?yàn)椋?） A）abcde（可能） B）edcba（可能） C）cdeba（可能） D）cdeab（不可能）,如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是（ ） A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e

10、1,e2D) 任意順序,棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是（ ） A) ABCED B) DCBEA C) DBCEA D) CDABE,四、堆棧,D,B,B,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),21,五、隊(duì)列,1、隊(duì)列屬于線性結(jié)構(gòu)。 2、隊(duì)列的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相同。 3、定義：入隊(duì)操作發(fā)生在隊(duì)尾，出隊(duì)操作發(fā)生在隊(duì)頭。 4、特點(diǎn)：先進(jìn)先出，后進(jìn)后出，所以隊(duì)列也叫做先進(jìn)先 出表（FIFO）。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),22,1、棧和隊(duì)列的共同特點(diǎn)是（ ） A)都是先進(jìn)先出 B) 都是先進(jìn)后出 C) 只允許在端點(diǎn)處插入和刪

11、除元素 D) 沒(méi)有共同點(diǎn) 2、一些重要的程序語(yǔ)言(如C語(yǔ)言和Pascal語(yǔ)言) 允許過(guò)程的遞歸調(diào)用。而 實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用（ ） A) 棧 B) 堆 C) 數(shù)組 D) 鏈表 3、下列關(guān)于棧的敘述中正確的是（ ） A)在棧中只能插入數(shù)據(jù) B)在棧中只能刪除數(shù)據(jù) C)棧是先進(jìn)先出的線性表 D)棧是后進(jìn)先出的線性表 4、下列關(guān)于隊(duì)列的敘述中正確的是（ ） A)在隊(duì)列中只能插入數(shù)據(jù) B)在隊(duì)列中只能刪除數(shù)據(jù) C)隊(duì)列是先進(jìn)先出的線性表 D)隊(duì)列是后進(jìn)先出的線性表,五、隊(duì)列,C,A,D,C,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),23,六、循環(huán)隊(duì)列,rear,front,全國(guó)計(jì)算機(jī)等級(jí)考試,二

12、級(jí)公共基礎(chǔ)知識(shí),24,入隊(duì)順序：a、b、c、d、e、f,模擬循環(huán)隊(duì)列的數(shù)據(jù)出入過(guò)程：,循環(huán)隊(duì)列空 front=rear,rear,front,a,front,rear,數(shù)據(jù)a入隊(duì),a,front,rear,b,數(shù)據(jù)b入隊(duì),front,rear,b,數(shù)據(jù)a出隊(duì),入隊(duì)運(yùn)算是往隊(duì)列隊(duì)尾插入一個(gè)數(shù)據(jù)元素；退隊(duì)運(yùn)算是從隊(duì)列的隊(duì)頭刪除一個(gè)數(shù)據(jù)元素。,六、循環(huán)隊(duì)列,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),25,七、線性鏈表,1、鏈表屬于線性結(jié)構(gòu)。 2、鏈表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)不相同。 3、線性鏈表由結(jié)點(diǎn)組成： 每個(gè)結(jié)點(diǎn)有兩個(gè)區(qū)域：數(shù)據(jù)域，指針域。 A .數(shù)據(jù)域，用來(lái)存儲(chǔ)數(shù)據(jù)。 B .指針域，用來(lái)指向下一個(gè)結(jié)點(diǎn)

13、的位置。 3、繪畫(huà)一個(gè)由5個(gè)節(jié)點(diǎn)組成的線性鏈表，數(shù)據(jù)為1、2、3、4、5。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),26,鏈表的種類：?jiǎn)捂湵?、循環(huán)鏈表、雙向鏈表。,1,2,3,4,5,1,2,3,4,5,循環(huán)鏈表,雙向鏈表,1,2,3,4,5,七、線性鏈表,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),27,1、鏈表不具有的特點(diǎn)是（ ） A) 不必事先估計(jì)存儲(chǔ)空間 B) 可隨機(jī)訪問(wèn)任一元素 C) 插入刪除不需要移動(dòng)元素 D) 所需空間與線性表長(zhǎng)度成正比 2、數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于 。 3、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ） A) 存儲(chǔ)結(jié)構(gòu)B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu)

14、D) 物理和存儲(chǔ)結(jié)構(gòu) 4、數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 兩大類。,七、線性鏈表,B,A,存儲(chǔ)結(jié)構(gòu),非線性結(jié)構(gòu),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),28,八、樹(shù)與二叉樹(shù),1、樹(shù)的基本概念,樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，是n個(gè)結(jié)點(diǎn)的有限集合。,一般的樹(shù),從邏輯結(jié)構(gòu)看：1）樹(shù)中只有根結(jié)點(diǎn)沒(méi)有前趨；2）除根外，其余結(jié)點(diǎn)都有且僅有一個(gè)前趨； 3）樹(shù)的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后繼；4）除根外的其他結(jié)點(diǎn)，都存在唯一一條從根到該結(jié)點(diǎn)的路徑； 5）樹(shù)是一種分支結(jié)構(gòu),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),29,注意: (1)樹(shù)結(jié)構(gòu)具有明顯的層次關(guān)系，即樹(shù)是一種層次結(jié)構(gòu)。因此具有層次關(guān)系的數(shù)據(jù)都可以用樹(shù)這種數(shù)據(jù)結(jié)構(gòu)來(lái)描述

15、。 (2)在樹(shù)結(jié)構(gòu)中分層的原則是：根節(jié)點(diǎn)在第1層，同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層。 (3)在樹(shù)中，葉子結(jié)點(diǎn)沒(méi)有子樹(shù)。,八、樹(shù)與二叉樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),30,（1）根節(jié)點(diǎn)：在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)。 （2）子節(jié)點(diǎn)：在數(shù)據(jù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 （3）度：在數(shù)據(jù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。在樹(shù)中，所有結(jié)點(diǎn)中的最大的度稱為該樹(shù)的度。 （4）樹(shù)的深度：樹(shù)的最大層次稱為樹(shù)的深度。,八、樹(shù)與二叉樹(shù),2、樹(shù)的基本術(shù)語(yǔ),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),31,3

16、、二叉樹(shù),八、樹(shù)與二叉樹(shù),二叉樹(shù)也是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)最多分兩叉的有序樹(shù)。,二叉樹(shù)具有以下兩個(gè)特點(diǎn)： (1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； (2)每一個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。,D,D,D,D,D,D,D,D,D,(a)只有根結(jié)點(diǎn)的二叉樹(shù),(b)深度為4的二叉樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),32,4、有序樹(shù)與無(wú)序樹(shù)：,八、樹(shù)與二叉樹(shù),二叉樹(shù)和度為二的樹(shù)的區(qū)別： A .二叉樹(shù)是有序樹(shù)，度為二的樹(shù)是普通樹(shù)，屬于無(wú)序樹(shù)。 B .二叉樹(shù)允許為空，度為二的樹(shù)至少有三個(gè)結(jié)點(diǎn)。 【普通樹(shù)不允許為空，至少有一個(gè)結(jié)點(diǎn)】,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),33,5、二

17、叉樹(shù)的五種基本結(jié)構(gòu),八、樹(shù)與二叉樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),34,八、樹(shù)與二叉樹(shù),6、二叉樹(shù)的基本性質(zhì),性質(zhì)1 在二叉樹(shù)的第k層上，最多有 (k1) 個(gè)結(jié)點(diǎn)。 根據(jù)二叉樹(shù)的特點(diǎn)，這個(gè)性質(zhì)是顯然的。 性質(zhì)2 深度為 m 的二叉樹(shù)最多有個(gè) 個(gè)結(jié)點(diǎn)。 根據(jù)性質(zhì)1，只要將第1層到 m 層上的最大樹(shù)的結(jié)點(diǎn)相加就可以得到整個(gè)二叉樹(shù)中結(jié)點(diǎn)的最大值，即 + + = 性質(zhì)3 在任意一棵二叉樹(shù)中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。 = +1 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為 n+1 ，其中 n表示取 n 的整數(shù)部分。 性質(zhì)5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 n+1。,全

18、國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),35,7、滿二叉樹(shù)和完全二叉樹(shù)：,(1)滿二叉樹(shù)：二叉樹(shù)的每一層均具備該層最大結(jié)點(diǎn)個(gè)數(shù)。 （即：不具備度為1的結(jié)點(diǎn)） (2)完全二叉樹(shù)：滿二叉樹(shù)是一個(gè)特殊的完全二叉樹(shù)。將所有結(jié)點(diǎn) 自上向下、自左向右編號(hào)，結(jié)點(diǎn)編號(hào)連續(xù)而不缺失。,滿二叉樹(shù),完全二叉樹(shù),1,2,3,4,5,6,八、樹(shù)與二叉樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),36,填空題： 設(shè)一棵完全二叉樹(shù)共有700個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn),二叉樹(shù)的結(jié)點(diǎn)共有三種：度為0的葉子結(jié)點(diǎn)、度為1的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)。 設(shè)度為0的葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則： n

19、0+n1+n2=700（1） 根據(jù)二叉樹(shù)性質(zhì)：葉子結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)個(gè)數(shù)多1，即： n0=n2+1 （2） 將（2）式帶入（1）式，所以： n0+n1+n0-1=700 2n0=701-n1 完全二叉樹(shù)總結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，則度為1的結(jié)點(diǎn)個(gè)數(shù)為1；完全二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)，則度為1的結(jié)點(diǎn)個(gè)數(shù)為0。 所以：2n0=701-1，即 n0=350。,經(jīng)典例題,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),37,6、二叉樹(shù)的遍歷：,二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。 二叉樹(shù)由根、左子樹(shù)、右子樹(shù)三部分組成 二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷左子樹(shù)和遍歷右子樹(shù),令：L：遍歷左子樹(shù) D：訪問(wèn)根結(jié)

20、點(diǎn) R：遍歷右子樹(shù) 有六種遍歷方法： DLR，LDR，LRD， DRL，RDL，RLD,約定先左后右,有三種遍歷方法： DLR，LDR，LRD，分別稱為先序遍歷（先根遍歷）、中序遍歷（中根遍歷）、后序遍歷（后根遍歷）,八、樹(shù)與二叉樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),38,(1)先序遍歷（ DLR ） 若二叉樹(shù)非空 訪問(wèn)根結(jié)點(diǎn)； 先序遍歷左子樹(shù)； 先序遍歷右子樹(shù)；,先序遍歷序列結(jié)果：A,B,D,E,G,C,F,八、樹(shù)與二叉樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),39,八、樹(shù)與二叉樹(shù),(2)中序遍歷（LDR ） 若二叉樹(shù)非空中序遍歷左子樹(shù);訪問(wèn)根結(jié)點(diǎn); 中序遍歷右子樹(shù);,中序遍歷序列： D

21、,B,G,E,A,C,F,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),40,八、樹(shù)與二叉樹(shù),(3)后序遍歷（ LRD ） 若二叉樹(shù)非空后序遍歷左子樹(shù)后序遍歷右子樹(shù) 訪問(wèn)根結(jié)點(diǎn),后序遍歷序列： D,G,E,B,F,C,A,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),41,1、下列二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為（ ） A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ 2、某二叉樹(shù)中有n個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為（ ） A）n+1 B）n-1 C）2n D）n/2 3、一棵二叉樹(shù)中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為（ ） A

22、）219 B）221 C）229 D）231,C,A,A,經(jīng)典例題講解,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),42,4、已知一棵二叉樹(shù)的前序遍歷結(jié)果和中序遍歷結(jié)果分別為ABDEGCFH和DBGEACHF，則該二叉樹(shù)的后序遍歷結(jié)果為 ，層次遍歷結(jié)果為 。,DGEBHFCA,ABCDEFGH,經(jīng)典例題講解,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),43,解答：若二叉樹(shù)的任意兩個(gè)節(jié)點(diǎn)的值都不相同，則二叉樹(shù)的前序序列和中序序列可唯一確定一棵二叉樹(shù)，確定方法如下： （1）根據(jù)前序遍歷的定義：前序序列的第一個(gè)元素必為二叉樹(shù)的根節(jié)點(diǎn)； 根據(jù)中序遍歷的定義：中序序列的根節(jié)點(diǎn)恰為左右子樹(shù)的中序序列的分界點(diǎn)；根節(jié)點(diǎn)前

23、的子序列為左子樹(shù)的中序序列；根節(jié)點(diǎn)后的子序列為右子樹(shù)的中序序列； （2）根據(jù)左子樹(shù)的中序序列的節(jié)點(diǎn)個(gè)數(shù)，在前序序列中找出左子樹(shù)的前序序列，剩下的即為右子樹(shù)的前序序列； （3）然后用相同的辦法分別找出左、右子樹(shù)的根及其左右子樹(shù)的前序序列和中序序列； （4）依此類推，直至待構(gòu)造的二叉樹(shù)的前序序列僅剩一個(gè)字母為止。,經(jīng)典例題講解,第二章 程序設(shè)計(jì)基礎(chǔ),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),45,本章知識(shí)要點(diǎn),面向過(guò)程的程序設(shè)計(jì),結(jié)構(gòu)化程序設(shè)計(jì),模塊化程序設(shè)計(jì),面向?qū)ο蟮某绦蛟O(shè)計(jì),對(duì)象的定義,對(duì)象的屬性和方法,類和實(shí)例的派生與繼承,消息與多態(tài)性,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),46,一、程序設(shè)計(jì)

24、方法,1、面向過(guò)程的程序設(shè)計(jì)：C語(yǔ)言、BASIC語(yǔ)言等。 （1）結(jié)構(gòu)化程序設(shè)計(jì)：順序、選擇、循環(huán)。 三大結(jié)構(gòu)（順序、選擇、循環(huán)）可以解決所有的問(wèn)題，和 問(wèn)題的規(guī)模沒(méi)有關(guān)系。 （2）模塊化程序設(shè)計(jì)：利用將程序分解的方法，將復(fù)雜的問(wèn)題 簡(jiǎn)單化，將單一的問(wèn)題分成多個(gè)模塊獨(dú)立解決。 C語(yǔ)言：模塊就是函數(shù)。 VB語(yǔ)言：模塊就是模塊、子例程、子程序。 VFP數(shù)據(jù)庫(kù)：模塊就是子程序。 Access數(shù)據(jù)庫(kù)：模塊就是宏、事件代碼。 2、面向?qū)ο蟮某绦蛟O(shè)計(jì)：VB、VFP、Java、Delphi等。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),47,二、程序設(shè)計(jì)風(fēng)格,1.源程序文檔化 選擇標(biāo)示符的名字 注釋（序言性和功能

25、性注釋） 程序的視覺(jué)組織 2.數(shù)據(jù)說(shuō)明的方法 顯示地說(shuō)明一切變量 數(shù)據(jù)說(shuō)明的次序應(yīng)該規(guī)范化 說(shuō)明語(yǔ)句中變量安排有序化 對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說(shuō)明,3.語(yǔ)句的結(jié)構(gòu) 每條語(yǔ)句簡(jiǎn)單明了 盡量不用或少用GOTO語(yǔ)句 盡量只采用3種基本控制結(jié)構(gòu)編程 4.輸入和輸出 對(duì)輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查 輸入輸出格式保持一致 設(shè)計(jì)良好的輸出報(bào)表,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),48,三、結(jié)構(gòu)化程序設(shè)計(jì),20世紀(jì)70年代提出了結(jié)構(gòu)化程序設(shè)計(jì)（Structured Programming）,結(jié)構(gòu)化程序設(shè)計(jì)的原則： （1）自頂向下。 （2）逐步求精。 （3）模塊化。 （4）限制使用goto語(yǔ)句。,結(jié)構(gòu)化程序設(shè)計(jì)的

26、基本結(jié)構(gòu)： （1）順序結(jié)構(gòu)。 （2）選擇結(jié)構(gòu)。 （3）重復(fù)結(jié)構(gòu)。,結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)程序的易讀性。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),49,利用圖示表示順序結(jié)構(gòu),程序流程圖,N-S圖,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),50,利用圖示表示選擇結(jié)構(gòu),程序流程圖,N-S圖,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),51,利用圖示表示重復(fù)結(jié)構(gòu)(1),程序流程圖當(dāng)型循環(huán),程序流程圖直到型循環(huán),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),52,利用圖示表示重復(fù)結(jié)構(gòu)(2),S,UNTIL 條件,N-S圖當(dāng)型循環(huán),N-S圖直到型循環(huán),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),53,三、面向?qū)ο蟮某绦蛟O(shè)計(jì),面向?qū)?/p>

27、象(Object Oriented)的程序設(shè)計(jì)方法已經(jīng)發(fā)展成為主流的軟件開(kāi)發(fā)方法，起源于對(duì)面向?qū)ο笳Z(yǔ)言的研究。20世紀(jì)60年代后期首次被提出，80年代開(kāi)始走向?qū)嵱谩?面向?qū)ο蟮某绦蛟O(shè)計(jì)的術(shù)語(yǔ)： 對(duì)象、屬性、方法、封裝性、事件、類、父類、子類、實(shí)例、派生、繼承、消息、多態(tài)性。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),54,面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)： （1）與人類習(xí)慣的思維方法一致。 （2）穩(wěn)定性好。 （3）可重用性好。 （4）易于開(kāi)發(fā)大型軟件產(chǎn)品。 （5）可維護(hù)性好。,三、面向?qū)ο蟮某绦蛟O(shè)計(jì),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),55,1、對(duì)象的定義,對(duì)象：現(xiàn)實(shí)生活中存在的可以相互區(qū)分的物體。 是屬

28、性和方法的封裝。,對(duì)象的基本特點(diǎn)： （1）標(biāo)識(shí)唯一性。 （2）分類型。 （3）多態(tài)性。 （4）封裝性。 （5）模塊獨(dú)立型好。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),56,2、對(duì)象的屬性和方法,屬性（Property）：用來(lái)描述對(duì)象的狀態(tài)，是對(duì)象的靜態(tài)特性。 包括屬性名和屬性值兩方面。 例如：“顯示器”作為對(duì)象，具備“顏色”屬性，取值為“銀白色”。 方法（Method）：用來(lái)描述對(duì)象的行為，是對(duì)象的動(dòng)態(tài)特性。 方法具備方法名。 方法必須利用事件來(lái)激活。 例如:“顯示器”作為對(duì)象，具備“關(guān)閉”的方法，必須用“斷電”事件來(lái)激活。,屬性名,屬性值,方法名,事件,封裝性：(Encapsulation)

29、對(duì)象依靠對(duì)象名將自身的屬性和方法封裝。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),57,3、類和實(shí)例的派生與繼承,（1）類（Class）：具有相同屬性和方法的 對(duì)象的集合，是對(duì)對(duì)象屬性和方法的抽 象。 （2）實(shí)例（Instances）：類的子類派生出 的對(duì)象就是該類的一個(gè)實(shí)例。 類展現(xiàn)對(duì)象的共性；實(shí)例展現(xiàn)對(duì)象的個(gè)性。 （3）派生過(guò)程中將發(fā)生屬性和方法的繼承 （Inheritance） 父類將自身的所有屬性和方法傳遞 給子類，子類繼承父類傳遞的所有屬性 和方法，并產(chǎn)生自身特有的屬性和方 法，再將這些屬性和方法的總和傳遞給 下一級(jí)子類。,人,好人,壞人,中國(guó)人,外國(guó)人,張三,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公

30、共基礎(chǔ)知識(shí),58,4、消息與多態(tài)性,（1）消息（Message）：進(jìn)行對(duì)象之間的信息傳遞。 （2）多態(tài)性（Polymorphism）：同樣的消息傳遞給不同的對(duì)象，導(dǎo)致 完全不同的行動(dòng)。,消息的組成： A .接收消息的對(duì)象名稱。 B .消息標(biāo)識(shí)符，也叫做“消息名”。 C .零個(gè)或多個(gè)參數(shù)。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),59,1、結(jié)構(gòu)化程序設(shè)計(jì)的三種結(jié)構(gòu)是（ ） A) 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu) B) 分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu) C) 多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(jié)構(gòu) D) 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 2、在設(shè)計(jì)程序時(shí)，應(yīng)采納的原則之一是（ ） A) 不限制goto語(yǔ)句的使用 B)

31、減少或取消注解行 C) 程序越短越好 D) 程序結(jié)構(gòu)應(yīng)有助于讀者理解 3、程序設(shè)計(jì)語(yǔ)言的基本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和（ ） A) 對(duì)象成分 B) 變量成分 C) 語(yǔ)句成分 D) 傳輸成分 4、結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是（ ） A) 程序的規(guī)模 B) 程序的效率 C) 程序設(shè)計(jì)語(yǔ)言的先進(jìn)性 D) 程序易讀性,練習(xí)題,D,D,D,D,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),60,5、以下不屬于對(duì)象的基本特點(diǎn)的是（ ） A) 分類性 B) 多態(tài)性 C) 繼承性D) 封裝性 6、對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是（ ） A) 程序應(yīng)簡(jiǎn)單、清晰、可讀性好 B) 符號(hào)名的命名只要符合語(yǔ)法

32、 C) 充分考慮程序的執(zhí)行效率 D) 程序的注釋可有可無(wú) 7、在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的（ ） A) 安全性 B) 一致性 C) 可理解性 D) 合理性 8、程序的3種基本控制結(jié)構(gòu)是（ ） A) 過(guò)程、子過(guò)程和分程序B) 順序、選擇和重復(fù) C) 遞歸、堆棧和隊(duì)列 D) 調(diào)用、返回和轉(zhuǎn)移 9、下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則的是（ ） A) 自頂向下 B) 由底向上 C) 模塊化 D) 限制使用goto語(yǔ)句,練習(xí)題,A,A,C,B,B,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),61,10、對(duì)象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)

33、合，是指對(duì)數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行（ ） A) 結(jié)合 B) 隱藏 C) 封裝 D) 抽象 11、在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過(guò)發(fā) 送（ ） A）調(diào)用語(yǔ)句 B）命令 C）口令 D）消息 12、下列對(duì)象概念描述錯(cuò)誤的是（ ） A）任何對(duì)象都必須有繼承性 B）對(duì)象是屬性和方法的封裝體 C）對(duì)象間的通訊靠消息傳遞 D）操作是對(duì)象的動(dòng)態(tài)屬性,練習(xí)題,C,D,A,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),63,本章知識(shí)要點(diǎn),軟件危機(jī),軟件生命周期,需求分析,概要設(shè)計(jì),詳細(xì)設(shè)計(jì),測(cè)試,調(diào)試,軟件工程,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),64,一、軟件危機(jī),軟件危機(jī)主要表現(xiàn)在： （1）

34、軟件需求的增長(zhǎng)得不到滿足。 （2）軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。 （3）軟件質(zhì)量難以保證。 （4）軟件不可維護(hù)或可維護(hù)度非常低。 （5）軟件的成本不斷提高。 （6）軟件開(kāi)發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。,總之，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率問(wèn)題,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),65,二、軟件工程,軟件工程是為了擺脫軟件危機(jī)而誕生的，主要思想是在軟件開(kāi)發(fā)過(guò)程中應(yīng)用工程化原則。,軟件工程的三要素：方法、工具、工程。,軟件工程的主要內(nèi)容：軟件開(kāi)發(fā)技術(shù)、軟件工程管理。,軟件工程的原則： （1）抽象。 （2）信息隱蔽。 （3）模塊化。 （4）局部化。 （5）確定性。 （6）一

35、致性。 （7）完備性。 （8）可驗(yàn)證性。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),66,二、軟件生命周期,軟件生命周期（Software Life Cycle，SLC）：將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為“軟件生命周期”。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),67,二、軟件生命周期,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),68,三、需求分析,需求與需求分析,需求分析的方法,結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖與數(shù)據(jù)字典,判定樹(shù)與判定表,軟件需求規(guī)格說(shuō)明書(shū),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),69,1、需求與需求分析,需求：用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì) 約束等方面的期望。

36、,需求分析：發(fā)現(xiàn)用戶需求的過(guò)程,需求分析階段的工作： （1）需求獲取 （2）需求分析 （3）編寫(xiě)需求規(guī)格說(shuō)明書(shū) （4）需求評(píng)審,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),70,2、需求分析的方法,A .面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法 SA。 B .面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法 JSD。 C .面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法 DSSD。 D .面向?qū)ο蟮姆治龇椒?OOA。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),71,3、結(jié)構(gòu)化分析方法：數(shù)據(jù)流圖DFD,數(shù)據(jù)流圖DFD中的主要圖形元素：,加工/轉(zhuǎn)換,數(shù)據(jù)流,存儲(chǔ)文件/數(shù)據(jù)源,源,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),72,結(jié)構(gòu)化分析方法：數(shù)據(jù)字典

37、DD,數(shù)據(jù)字典DD是結(jié)構(gòu)化分析方法的核心。,數(shù)據(jù)字典的作用：對(duì)數(shù)據(jù)流圖DFD中出現(xiàn)的被命名圖形元素進(jìn) 行確切的解釋。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),73,結(jié)構(gòu)化分析方法：判定樹(shù)與判定表,判定樹(shù),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),74,判定表,結(jié)構(gòu)化分析方法：判定樹(shù)與判定表,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),75,結(jié)構(gòu)化分析方法：需求規(guī)格說(shuō)明書(shū),軟件需求規(guī)格說(shuō)明書(shū)（SRS）是需求分析階段的最后成果，將 在軟件工程的最后轉(zhuǎn)換為用戶手冊(cè)。,軟件需求規(guī)格說(shuō)明書(shū)的作用： （1）便于用戶、開(kāi)發(fā)人員進(jìn)行理解和交流。 （2）反映出用戶問(wèn)題的結(jié)構(gòu)，可作為軟件開(kāi)發(fā)工作的基礎(chǔ)和 依據(jù)。 （3）作為確

38、認(rèn)測(cè)試和驗(yàn)收的依據(jù)。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),76,四、概要設(shè)計(jì),軟件設(shè)計(jì)的基本原理： （1）抽象：把事物本質(zhì)的共同特性提取出來(lái)而不考慮細(xì)節(jié)。 （2）模塊化：把待開(kāi)發(fā)軟件分解成若干個(gè)小的簡(jiǎn)單部分。 （3）信息隱蔽：在一個(gè)模塊內(nèi)包含的信息，對(duì)于不需要這些 信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。 （4）模塊獨(dú)立性：評(píng)價(jià)設(shè)計(jì)好壞的重要度量指標(biāo)。,內(nèi)聚性和耦合性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)： A .內(nèi)聚性：一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度。 B .耦合性：模塊間互相連接的緊密程度。 一款優(yōu)秀的軟件設(shè)計(jì)，應(yīng)做到高內(nèi)聚，低耦合。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),77,概要設(shè)計(jì)的任務(wù)：

39、（1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)。 （2）確定軟件的每一個(gè)模塊 （3）確定模塊之間的調(diào)用關(guān)系 （4）評(píng)價(jià)模塊結(jié)構(gòu)質(zhì)量。,采用的方法：結(jié)構(gòu)化設(shè)計(jì)方法【SD】 使用的工具：軟件結(jié)構(gòu)圖SC。,四、概要設(shè)計(jì),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),78,五、詳細(xì)設(shè)計(jì),詳細(xì)設(shè)計(jì)的任務(wù)：為軟件結(jié)構(gòu)圖中每一個(gè)模塊確定實(shí)現(xiàn)的算法 和數(shù)據(jù)結(jié)構(gòu)。表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。,采用的方法：結(jié)構(gòu)化編程方法【SP】 使用的工具：程序流程圖、N-S圖、問(wèn)題分析圖PAD 判定表 過(guò)程設(shè)計(jì)語(yǔ)言/偽碼PDL,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),79,程序流程圖中的主要圖形元素：,加工步驟,控制流,邏輯條件,五、詳細(xì)設(shè)計(jì),全國(guó)計(jì)算機(jī)等級(jí)考試

40、,二級(jí)公共基礎(chǔ)知識(shí),80,六、軟件測(cè)試,軟件測(cè)試的目的：盡可能多的發(fā)現(xiàn)錯(cuò)誤。 （1）錯(cuò)誤理解：軟件測(cè)試為了發(fā)現(xiàn)錯(cuò)誤并改正。 （2）錯(cuò)誤理解：軟件測(cè)試為了證明軟件正確性。,軟件測(cè)試的準(zhǔn)則： （1）所有測(cè)試追溯到需求。 （2）嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試隨意性。 （3）充分注意測(cè)試中的群集現(xiàn)象：程序中存在錯(cuò)誤的概率與該程 序中已發(fā)現(xiàn)的錯(cuò)誤數(shù)量成正比。 （4）程序員避免檢測(cè)自己的程序。 （5）窮舉測(cè)試不可能。 （6）妥善保存測(cè)試文檔，為維護(hù)提供方便。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),81,軟件測(cè)試的方法： （1）靜態(tài)測(cè)試：由人工進(jìn)行，無(wú)需借助計(jì)算機(jī)。 （2）動(dòng)態(tài)測(cè)試：基于計(jì)算機(jī)，實(shí)際運(yùn)行軟件進(jìn)行

41、測(cè)試 A .白盒測(cè)試：邏輯覆蓋、基本路徑測(cè)試。 B .黑盒測(cè)試：等價(jià)類劃分、邊界值分析、錯(cuò)誤推測(cè)法、因果圖。,軟件測(cè)試的實(shí)施： 第1步：?jiǎn)卧獪y(cè)試（對(duì)每一個(gè)模塊進(jìn)行測(cè)試） 第2步：集成測(cè)試（將模塊組裝起來(lái)的同時(shí)進(jìn)行測(cè)試） 第3步：確認(rèn)測(cè)試（驗(yàn)證軟件的功能和性能是否滿足需求） 第4步：系統(tǒng)測(cè)試（評(píng)估系統(tǒng)環(huán)境下軟件的功能）,六、軟件測(cè)試,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),82,七、軟件調(diào)試（Debug）,軟件調(diào)試的目的：診斷和改正程序中的錯(cuò)誤。,軟件調(diào)試的基本步驟： 第1步：錯(cuò)誤定位?！菊紦?jù)了調(diào)試的絕大多數(shù)工作量】 第2步：修改設(shè)計(jì)和代碼，以排除錯(cuò)誤。 第3步：進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。,

42、全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),83,1、為了提高測(cè)試的效率，應(yīng)該（ ） A) 隨機(jī)選取測(cè)試數(shù)據(jù) B) 取一切可能的輸入數(shù)據(jù)作為測(cè)試數(shù)據(jù) C) 在完成編碼以后制定軟件的測(cè)試計(jì)劃 D) 集中對(duì)付那些錯(cuò)誤群集的程序 2、軟件生命周期中所花費(fèi)用最多的階段是（ ） A) 詳細(xì)設(shè)計(jì) B) 軟件編碼 C) 軟件測(cè)試 D) 軟件維護(hù) 3、下列敘述中，不屬于軟件需求規(guī)格說(shuō)明書(shū)的作用的是（ ） A) 便于用戶、開(kāi)發(fā)人員進(jìn)行理解和交流 B) 反映出用戶問(wèn)題的結(jié)構(gòu)，可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù) C) 作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù) D) 便于開(kāi)發(fā)人員進(jìn)行需求分析 4、下列不屬于軟件工程的3個(gè)要素的是（ ） )

43、工具) 過(guò)程 ) 方法 ) 環(huán)境,練習(xí)題,D,D,D,D,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),84,5、軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過(guò)程設(shè)計(jì)，其中軟件的過(guò)程設(shè)計(jì) 是指（ ） A) 模塊間的關(guān)系B) 系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述 C) 軟件層次結(jié)構(gòu)D) 軟件開(kāi)發(fā)過(guò)程 6、檢查軟件產(chǎn)品是否符合需求定義的過(guò)程稱為（ ） ) 確認(rèn)測(cè)試 ) 集成測(cè)試 ) 驗(yàn)證測(cè)試 ) 驗(yàn)收測(cè)試 7、數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖 符構(gòu)成。下列圖符名標(biāo)識(shí)的圖符不屬于數(shù)據(jù)流圖合法圖符的是（ ） ) 控制流 ) 加工 ) 數(shù)據(jù)存儲(chǔ) ) 源和流 8、開(kāi)發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之

44、間有著尖銳的矛盾，這種現(xiàn)象稱 作（ ） A) 軟件投機(jī) B) 軟件危機(jī) C) 軟件工程 D) 軟件產(chǎn)生 9、下面不屬于軟件設(shè)計(jì)原則的是（ ） ) 抽象 B) 模塊化 ) 自底向上 ) 信息隱蔽,練習(xí)題,B,B,B,B,B,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),85,10、開(kāi)發(fā)大型軟件時(shí)，產(chǎn)生困難的根本原因是（ ） A) 大系統(tǒng)的復(fù)雜性B 人員知識(shí)不足 C) 客觀世界千變?nèi)f化D) 時(shí)間緊、任務(wù)重 11、軟件工程的出現(xiàn)是由于（ ） A) 程序設(shè)計(jì)方法學(xué)的影響B(tài)) 軟件產(chǎn)業(yè)化的需要 C) 軟件危機(jī)的出現(xiàn)D) 計(jì)算機(jī)的發(fā)展 12、在數(shù)據(jù)流圖(DFD) 中，帶有名字的箭頭表示（ ） A) 模塊之間的調(diào)用

45、關(guān)系 B) 程序的組成成分 C) 控制程序的執(zhí)行順序D) 數(shù)據(jù)的流向 13、下列不屬于結(jié)構(gòu)化分析的常用工具的是（ ） A) 數(shù)據(jù)流圖 B) 數(shù)據(jù)字典 C) 判定樹(shù) D) PAD圖 14、在軟件生產(chǎn)過(guò)程中，需求信息的給出是（ ） A) 程序員 B) 項(xiàng)目管理者 C) 軟件分析設(shè)計(jì)人員D) 軟件用戶,練習(xí)題,A,C,D,D,D,第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ),全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),87,一、理解數(shù)據(jù)庫(kù)：,1、數(shù)據(jù)（Data）是描述事物的符號(hào)記錄。 2、為什么引入數(shù)據(jù)庫(kù)： （1）數(shù)據(jù)量大，數(shù)據(jù)多。 （2）方便查找。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),88,二、數(shù)據(jù)庫(kù)原理術(shù)語(yǔ)：,1、數(shù)據(jù)（

46、Data）是描述事物的符號(hào)記錄。 2、數(shù)據(jù)庫(kù)（DataBase，DB）數(shù)據(jù)的集合，是存放數(shù)據(jù)的倉(cāng)庫(kù)。 3、數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）負(fù)責(zé)數(shù)據(jù)的管理。 （1）DBMS屬于系統(tǒng)軟件。 （2）DBMS是數(shù)據(jù)庫(kù)系統(tǒng)的核心。 4、數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)（DBAS）利用DBMS開(kāi)發(fā)的應(yīng)用軟件。 5、數(shù)據(jù)庫(kù)系統(tǒng)（DBS）使用了數(shù)據(jù)庫(kù)技術(shù)的計(jì)算機(jī)，屬于硬件系統(tǒng)。 6、數(shù)據(jù)庫(kù)管理員（DBA）是數(shù)據(jù)庫(kù)系統(tǒng)的人的因素。負(fù)責(zé)管理、維 護(hù)、設(shè)計(jì)、監(jiān)視數(shù)據(jù)庫(kù)系統(tǒng)的運(yùn)行。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),89,計(jì)算機(jī)硬件,操作系統(tǒng),數(shù)據(jù)庫(kù)管理系統(tǒng),數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng),用戶,Windows XP / Vista / 7 / 200

47、3等。,Access / Visual FoxPro / SQL Server等。,二、數(shù)據(jù)庫(kù)原理術(shù)語(yǔ)：,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),90,三、數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式和兩級(jí)映射：,數(shù)據(jù)庫(kù)（DB）,內(nèi)模式 （物理模式）,概念模式,外模式/子模式,用戶模式,外模式,應(yīng)用,應(yīng)用,應(yīng)用,概念模式 內(nèi)模式映射,外模式 - 概念模式映射,全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述,局部數(shù)據(jù)邏輯結(jié)構(gòu)的描述,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),91,四、數(shù)據(jù)模型：,1、數(shù)據(jù)模型的三層分類： （1）概念數(shù)據(jù)模型/概念模型 （2）邏輯數(shù)據(jù)模型/數(shù)據(jù)模型 （3）物理數(shù)據(jù)模型/物理模型 2、典型的概念數(shù)據(jù)模型：E R模型（實(shí)體

48、 - 聯(lián)系模型） （1）實(shí)體：現(xiàn)實(shí)生活中的事物。 （2）屬性：表示實(shí)體的一些特征。 （3）聯(lián)系：實(shí)體之間的關(guān)聯(lián)。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),92,3、實(shí)體間聯(lián)系： （1）一對(duì)一（1:1） 學(xué)校 - 校長(zhǎng) 【計(jì)算機(jī)不予處理】 （2）一對(duì)多（1:m） 學(xué)生 班級(jí) 【計(jì)算機(jī)可以直接處理】 （3）多對(duì)多（m:n） 學(xué)生 課程 【轉(zhuǎn)換為兩個(gè)一對(duì)多聯(lián)系再處理】,歷史上出現(xiàn)過(guò)的數(shù)據(jù)模型：網(wǎng)狀模型、層次模型、關(guān)系模型,四、數(shù)據(jù)模型：,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),93,4、E-R模型的圖示表示法：,實(shí)體,聯(lián)系,實(shí)體的屬性,四、數(shù)據(jù)模型：,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),94,五、關(guān)系

49、模型：,關(guān)系的數(shù)據(jù)結(jié)構(gòu),例：學(xué)生關(guān)系,屬性,元組/記錄,主鍵,關(guān)系就是二維表。,1、元組是有限的。 2、元組不能重復(fù)。 3、屬性不能重復(fù)。 4、元素的順序是無(wú)關(guān)的。 5、屬性的順序是無(wú)關(guān)的。,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),95,關(guān)系的數(shù)據(jù)約束,A .實(shí)體完整性約束 主鍵取值不能為空，不能取重復(fù)值。 主鍵取值不同，就是兩個(gè)不同的元組。 B .參照完整性約束 不允許引用不存在的元組。 約束了關(guān)系之間相關(guān)聯(lián)的情況。 C .用戶自定義完整性約束,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),96,六、關(guān)系代數(shù)： 參與運(yùn)算的數(shù)據(jù)都是關(guān)系（二維表）。,1、基本關(guān)系代數(shù),（1）交：RS=t|tR且tS （2

50、）并：RS=t|tR或tS （3）差：R-S=t|tR且tS,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),97,R,A B C,1 2 5 1 4 9 2 8 4 5 6 0 9 2 4,S,A B C,1 2 5 3 4 9 2 6 4 5 6 0 3 3 3,結(jié)論：并交差三個(gè)操作都不能更改關(guān)系的屬性個(gè)數(shù)。,六、關(guān)系代數(shù)：,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),98,R,A B C,1 2 5,1 4 9,5 6 0,S,A B C,1 2 5,3 4 9,RS,R.A R.B R.C S.A S.B S.C,1 2 5 1 2 5,1 4 9 1 2 5 1 4 9 3 4 9 5 6 0 1 2 5 5 6 0 3 4 9,1 2 5 3 4 9,2、關(guān)系積（笛卡爾積）,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)公共基礎(chǔ)知識(shí),99,3、擴(kuò)展關(guān)系代數(shù)：,（1）選擇：AC(R) 【對(duì)關(guān)系的橫向分解】 （2）投影：A,C(R) 【對(duì)關(guān)系的縱向分解】,A,C(R),A C,1 5,1 9,2 4,5 0,9 4,R,A B C,1 2 5,1 4 9,2 8 4,5 6 0,9 2 4,全國(guó)計(jì)算機(jī)等級(jí)考試,二級(jí)