【正文】 位； 第 2步：修改設(shè)計(jì)和代碼，以排除錯(cuò)誤； 第 3步：進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。 （ 4）軟件測(cè)試的實(shí)施 程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，它與軟件測(cè)試不同，軟件測(cè)試是盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤。 ：靠經(jīng)驗(yàn)和直覺推測(cè)程序中可能存在的各種錯(cuò)誤，從而有針對(duì)性地編寫檢查這些錯(cuò)誤的例子的方法。 黑盒測(cè)試 ：將程序的所有可能的輸入數(shù)據(jù)劃分成若干部分（及若干等價(jià)類），然后從每個(gè)等價(jià)類中選取數(shù)據(jù)作為測(cè)試用例。 ：基本路徑測(cè)試的思想和步驟是，根據(jù)軟件過程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測(cè)試用例對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測(cè)試。 白盒測(cè)試的基本原則： ：邏輯覆蓋是泛指一系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測(cè)試用例設(shè)計(jì)技術(shù)。 （ 3）軟件測(cè)試技術(shù)與方法綜述 白盒測(cè)試又稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試，是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢測(cè)內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)范要求。 （ 2）軟件測(cè)試的準(zhǔn)則 ① 軟件測(cè)試從是否要執(zhí)行被測(cè)試軟件的角度可以分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。 軟件測(cè)試 四、軟件測(cè)試及程序的調(diào)試 軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程： ?一個(gè)好的測(cè)試用例是指很可能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的用例； ?一個(gè)成功的測(cè)試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。 （ 2）詳細(xì)設(shè)計(jì) ?常見的過程設(shè)計(jì)工具有： ， NS（方框圖）， PAD（問題分析圖）； ：判定表； ： PDL（過程設(shè)計(jì)語言）。 軟件設(shè)計(jì)的準(zhǔn)則 ?詳細(xì)設(shè)計(jì)的任務(wù)：為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法的局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。結(jié)構(gòu)圖是描述軟件結(jié)構(gòu)的圖形工具。 ?概要設(shè)計(jì)的基本任務(wù)：設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)、確定數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)、編寫概要設(shè)計(jì)文檔、進(jìn)行概要設(shè)計(jì)文檔評(píng)審。 軟件設(shè)計(jì)的內(nèi)容 ?結(jié)構(gòu)化設(shè)計(jì)方法的基本思想：將軟件設(shè)計(jì)成相對(duì)獨(dú)立、單一功能的模塊組成的結(jié)構(gòu)。 ?接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。 ?結(jié)構(gòu)設(shè)計(jì)是定義軟件系統(tǒng)各主要部件之間的關(guān)系。 ?軟件設(shè)計(jì)的基礎(chǔ)目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，即軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。 3. 結(jié)構(gòu)化分析的常用工具 軟件需求規(guī)格說明書（ SRS）是需求分析階段的最后結(jié)果，是軟件開發(fā)中的重要文檔之一。 ②數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。 其中最重要的工具是數(shù)據(jù)流圖 。 需求分析與需求分析方法 ?需求分析的定義 ?需求分析階段的工作 ?需求分析方法 ?結(jié)構(gòu)化分析方法 ?面向?qū)ο蟮姆治龇椒? 二、結(jié)構(gòu)化分析方法 2. 關(guān)于結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。 軟件開發(fā)工具與軟件開發(fā)環(huán)境 （ 2）軟件開發(fā)環(huán)境 軟件開發(fā)環(huán)境或稱軟件工程環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。 ?軟件定義階段的任務(wù)包括可行性研究與計(jì)劃制定、需求分析； ?軟件開發(fā)階段的任務(wù)包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件測(cè)試； ?軟件維護(hù)階段的任務(wù)包括軟件的運(yùn)行、維護(hù)和退役。軟件工程的三個(gè)要素：方法、工具和過程。 ?軟件的三個(gè)要素： ①程序 ②數(shù)據(jù) ③文檔 （ 2）軟件分類：軟件按功能可分為三大類： ①應(yīng)用軟件 ②系統(tǒng)軟件 ③支撐軟件（或工具軟件） （ 3）軟件危機(jī)的定義： 軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題。 ?程序調(diào)試 、 靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試 。 ?結(jié)構(gòu)化設(shè)計(jì)方法 、 總體設(shè)計(jì)與詳細(xì)設(shè)計(jì) 。 答案： A 第三章 軟件工程基礎(chǔ) 【 本章考試要點(diǎn) 】 ?軟件工程基本概念；軟件生命周期概念；軟件工具與軟件開發(fā)環(huán)境。 答案： 順序結(jié)構(gòu) 例：下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)原則的 是（ ）。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的。 答案： A 例：下列敘述中正確的是 。 答案： A 例：在面向?qū)ο蠓椒ㄖ?，不屬于“?duì)象”基本特點(diǎn)的 是 。 A. 程序的效率第一，清晰第二 B. 程序的可讀性好 C. 程序中要有必要的注釋 D. 輸入數(shù)據(jù)前要有提示信息 軟件在編碼階段，力求程序語句簡(jiǎn)單、直接，不能只為了追求效率而使語句復(fù)雜化。因此對(duì)象的信息隱蔽是依靠對(duì)象的封裝來實(shí)現(xiàn)的。） 答案： C 例：在面向?qū)ο蠓椒ㄖ?，?shí)現(xiàn)信息隱蔽是依靠 _____。 A．各模塊應(yīng)包括盡量多的功能 B．各模塊的規(guī)模應(yīng)盡量大 C．各模塊之間的聯(lián)系應(yīng)盡量緊密 D．模塊內(nèi)有高內(nèi)聚度，模塊間有低耦合度 答案： D 例：下面選項(xiàng)中不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)的是 ____。 面向?qū)ο蟪绦蛟O(shè)計(jì)中 ， 對(duì)象具有以下特征： ?繼承性 ?抽象性 ?封裝性 ?多態(tài)性 例：下列選項(xiàng)中不符合良好程序設(shè)計(jì)風(fēng)格的是 。 ?多態(tài)性是指子類對(duì)象可以像父類對(duì)象那樣使用 ， 同樣的消息既可以發(fā)送給父類對(duì)象 ， 也可以發(fā)送給子類對(duì)象 。 ?繼承是指能夠直接獲得已有的性質(zhì)和特征 ， 而不必重復(fù)定義它們 。 繼承 ?繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù) 。 ?類的對(duì)象的抽象 ， 它描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)；而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例 。 ?操作過程對(duì)外是封閉的 ， 用戶只能看到這一操作實(shí)施后的結(jié)果 。 ?一般只能通過執(zhí)行對(duì)象的操作來改變 。 ?對(duì)象具有：標(biāo)識(shí)惟一性 、 分類性 、 多態(tài)性 、 封裝性和模塊獨(dú)立性 。 ?用來表示客觀世界中的任何實(shí)體 。 注意： 面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn) ①與人類習(xí)慣的思維方法一致； ②穩(wěn)定性好； ③可重用性好； ④易于開發(fā)大型軟件產(chǎn)品； ⑤可維護(hù)性好 。 ?當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格是著名的：“清晰第一，效率第二”。 ?面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 ， 掌握并理解對(duì)象 、 方法 、屬性 ， 以及繼承與多態(tài)性的概念 。 答案：線性結(jié)構(gòu) 第二章 程序設(shè)計(jì)基礎(chǔ) 【 本章考試要點(diǎn) 】 ?程序設(shè)計(jì)方法與風(fēng)格。 A 快速排序 B 冒泡排序 C 直接插入排序 D 堆排序 答案： D 例：按“先進(jìn)后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 。 例：冒泡排序在最壞的情況下的比較次數(shù)是 。 （ 2） 堆排序法 ?長(zhǎng)度為 n的序列 ， 在最壞的情況下 ， 堆排序的比較次數(shù)為 O ( nlog2n )。 ?長(zhǎng)度為 n的線性表 ， 在最壞的情況下 ， 希爾排序所需要的比較次數(shù)為： O ( ) （二）插入類排序 （三）選擇類排序 （ 1） 簡(jiǎn)單選擇排序 ?掃描整個(gè)線性表 ， 從選出最小的元素 ， 將它交換到最前面；對(duì)剩下的子表采用同樣的方法 ， 直到子表為空 。 ?長(zhǎng)度為 n的線性表 ， 在最壞的情況下 ， 簡(jiǎn)單插入排序需要經(jīng)過 n ( n – 1 ) / 2次的比較 。 （ 2）快速排序法 快速排序過程中，隨著對(duì)各子表不斷地進(jìn)行分割，劃分出的子表會(huì)越來越多，但一次又只能對(duì)一個(gè)子表進(jìn)行再分割處理，需要將暫時(shí)不分割的子表記憶起來，這就要用一個(gè)棧來實(shí)現(xiàn)。 答案： C 十、排序技術(shù) （一）交換類排序 交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。 A） O(n) B） O(n2) C） O(log2n) D） O(nlog2n) 二分查找的效率要比順序查找高得多。 答案： 升序 例：在長(zhǎng)度為 64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為 。 ?對(duì)于長(zhǎng)度為 n的有序線性表，在最壞情況下，二分查找只需要比較 log2n次，而順序查找需要比較 n次。 （二）二分法查找 ?二分法查找只適用于順序查找的有序表。 ?在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中的一半元素進(jìn)行比較。 350 分析： 根據(jù)完全二叉樹的性質(zhì) 6（ P36）可知： （ 1）編號(hào) 700的葉子結(jié)點(diǎn)（即最后一個(gè)葉子結(jié)點(diǎn)），其父結(jié)點(diǎn)編號(hào)為： INT( 700 / 2 ) =350 （ 2）編號(hào)為 350的結(jié)點(diǎn)為最后一個(gè)樹結(jié)點(diǎn)，即：編號(hào) 1至 350均為父結(jié)點(diǎn)，計(jì) 350個(gè)；編號(hào) 351至 700均為葉子結(jié)點(diǎn)。 則這棵樹中的葉子結(jié)點(diǎn)有 _____ 。 A. 219 B. 221 C. 229 D. 231 二叉樹性質(zhì) 3：度為 0的結(jié)點(diǎn)比度為 2的結(jié)點(diǎn)多一個(gè)。故深度為 2的結(jié)點(diǎn)個(gè)數(shù)為： n2=271 2(71) =63 分析： 根據(jù)二叉樹性質(zhì) 1，滿二叉第 7層的葉子結(jié)點(diǎn)數(shù)為 271個(gè)，即 64個(gè)。 答案： 63 分析：根據(jù)二叉樹性質(zhì) 1，該深度為 7的滿二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)為 2(71)個(gè)。 答案： A 例：一棵二叉樹有 10個(gè)度為 1的結(jié)點(diǎn)， 7個(gè)度為 2的結(jié)點(diǎn)，則該二叉樹共有 個(gè)結(jié)點(diǎn)。 答案： 16 例：某二叉樹有 n個(gè)度為 2的結(jié)點(diǎn)，則該二叉樹的葉子結(jié)點(diǎn)為 個(gè)。 根據(jù)二叉樹的性質(zhì)：二叉樹第 i（ i1）層上至多有 2i1個(gè)結(jié)點(diǎn)。 則其后序遍歷的結(jié)果為 _________ _________ _________ _________ 。 則其前序遍歷的結(jié)果為 ________________ 。 則其后序遍歷的結(jié)果為 ______________________ 。 A. DYBEAFCZX B. DEBFZXCA C. ABDYECFXZ D. ABCDEFXYZ 答案： C 例：對(duì)下列二叉樹進(jìn)行中序遍歷的結(jié)果 。 完全二叉樹的兩個(gè)性質(zhì) （ 4）二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。 ② 若 2k≤n， 則編號(hào)為 k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn) （ 顯然也無右子結(jié)點(diǎn) ） 。 ?設(shè)完全二叉樹共有 n個(gè)結(jié)點(diǎn) 。 ?完全二叉樹 除最后一層外，其它各層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，最后一層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊。 （ 3）滿二叉樹和完全二叉樹 ?滿二叉樹 除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。如果葉子結(jié)點(diǎn) n0，度為 2的結(jié)點(diǎn)數(shù)為 n2，則 n0＝ n2＋ 1。 性質(zhì) 2：深度為 m的二叉樹最多有 2m1個(gè)結(jié)點(diǎn)。 ?用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)： ? 一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域； ? 另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。 ?樹的最大層次稱為樹的深度。 ?沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 ?沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。 A）各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致 B）各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù) C）進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素 D）以上三種說法都不對(duì) 答案： C 八、樹 ?樹 是一種簡(jiǎn)單的非線性結(jié)構(gòu)，是層次結(jié)構(gòu)。 ?線性鏈表的刪除 為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。 ?線性鏈表的插入 為了在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè)新節(jié)點(diǎn)，它可以從可利用棧中取得。 ?在線性鏈表中查找指定元素 在非空線性鏈表中尋找包括指定元素 x的前一個(gè)結(jié)點(diǎn) p的基本方法如下： ? 從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)?x為止。 A）循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu) B）在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況 C）在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況 D）循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定 答案： D 七、線性鏈表 ?線性