【正文】 每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：完全二叉樹還具有如下兩個(gè)特性：性質(zhì)5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為 。性質(zhì)6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1，2，…，n）的結(jié)點(diǎn)有以下結(jié)論：①若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。③若2k+1≤n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。二叉樹的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(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ǔ)地址，稱為右指針域。二叉樹的遍歷可以分為以下三種：（1）前序遍歷（DLR）：若二叉樹為空，則結(jié)束返回。（2）中序遍歷（LDR）：若二叉樹為空，則結(jié)束返回。（3）后序遍歷（LRD）：若二叉樹為空，則結(jié)束返回。 查找技術(shù)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。）平均查找長(zhǎng)度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。否則就是表中沒有要找的元素，查找不成功。順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O（n）。2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。的值等于x，則說明已查到；2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。最壞的情況下，需要比較log2n次。對(duì)于無序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。 排序技術(shù)排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。插入類排序法（方法：簡(jiǎn)單插入排序，希爾排序）?？偨Y(jié)：各種排序法比較：本章應(yīng)考點(diǎn)撥：本章內(nèi)容在筆試中會(huì)出現(xiàn)56個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約10分。1）符號(hào)名的命名。2）程序的注釋。序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡(jiǎn)歷、程序設(shè)計(jì)者、復(fù)審者、復(fù)審日期及修改日期等。3）視覺組織。（2）數(shù)據(jù)說明。（3）語句的結(jié)構(gòu)。即指在設(shè)計(jì)和確定模塊時(shí)，使得一個(gè)模塊內(nèi)包含的信息（過程或數(shù)據(jù)），對(duì)于不需要這些信息的其它模塊來說，是不能訪問的。（4）輸入和輸出。 結(jié)構(gòu)化程序設(shè)計(jì)（面向過程的程序設(shè)計(jì)方法）結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語句。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。（2）逐步求精。（3）模塊化。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。一種簡(jiǎn)單的程序設(shè)計(jì)，即按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段。 面向?qū)ο蟮某绦蛟O(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：（1）與人類習(xí)慣的思維方法一致；（2）穩(wěn)定性好；（3）可重用軟件的重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似軟件的過程。*：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來改變。*：操作是對(duì)象的動(dòng)態(tài)屬性。對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類性，多態(tài)性，封裝性，模塊獨(dú)立性好。指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。指可以將具有相同屬性的操作的對(duì)象抽象成類。指同一個(gè)操作可以是不同對(duì)象的行為。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。從外面不能直接使用對(duì)象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。 （5）模塊獨(dú)立性好。從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。消息的組成包括：（1）接收消息的對(duì)象的名稱；（2）消息標(biāo)識(shí)符，也稱消息名；（3）零個(gè)或多個(gè)參數(shù)。繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。單繼承指一個(gè)類只允許有一個(gè)父類，多重繼承指一個(gè)類允許有多個(gè)父類。多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。本章內(nèi)容比較少，也很簡(jiǎn)單，掌握住基本的概念就可以輕松應(yīng)對(duì)考試了，所以在這部分丟分，比較可惜。軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性軟件的這個(gè)特點(diǎn)使它與其它工程對(duì)象有著明顯的差異。；2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；3）軟件在運(yùn)行、使用期間不存在磨損、老化問題；4）軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會(huì)因素許多軟件的開發(fā)和運(yùn)行涉及軟件用戶的機(jī)構(gòu)設(shè)置，體制問題以及管理方式等，甚至涉及到人們的觀念和心理，軟件知識(shí)產(chǎn)權(quán)及法律等問題。軟件危機(jī)與軟件工程軟件工程概念的出現(xiàn)源自軟件危機(jī)。具體的說，在軟件開發(fā)和維護(hù)過程中，軟件危機(jī)主要表現(xiàn)在：1）軟件需求的增長(zhǎng)得不到滿足。2）軟件開發(fā)成本和進(jìn)度無法控制。3）軟件質(zhì)量難以保證。5）軟件的成本不斷提高?？傊梢詫④浖C(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。軟件工程的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)：1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過程，它包括3個(gè)要素：方法、工具和過程。軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：1）軟件定義階段：包括制定計(jì)劃和需求分析。需求分析：對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪改。軟件工程的目標(biāo)與原則（1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。（3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來，使模塊接口盡量簡(jiǎn)單。模塊的大小要適中，模塊過大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。5）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)是確定、無歧義且規(guī)范的。7）完備性：軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。軟件開發(fā)工具與軟件開發(fā)環(huán)境(1)軟件開發(fā)工具軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高質(zhì)量。同時(shí)，軟件開發(fā)方法的有效應(yīng)用也必須得到相應(yīng)工具的支持，否則方法將難以有效的實(shí)施。計(jì)算機(jī)輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開發(fā)機(jī)器和一個(gè)存放開發(fā)過程信息的中心數(shù)據(jù)庫(kù)組合起來，形成軟件工程環(huán)境。 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。*：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題。結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹；4）判定表。下圖是數(shù)據(jù)流圖的基本圖形元素：加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。存儲(chǔ)文件（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。*：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。軟件需求規(guī)格說明書（SRS）軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。 結(jié)構(gòu)化設(shè)計(jì)方法軟件設(shè)計(jì)的基礎(chǔ)*：需求分析主要解決“做什么”的問題，而軟件設(shè)計(jì)主要解決“怎么做”的問題。結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系。接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。從工程角度來看，軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。詳細(xì)設(shè)計(jì)：確定每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。1）抽象。2）模塊化。3）信息隱蔽。4）模塊獨(dú)立性。*：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。在結(jié)構(gòu)化程序設(shè)計(jì)中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。*：按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。*：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。總體設(shè)計(jì)（概要設(shè)計(jì)）和詳細(xì)設(shè)計(jì)（1）總體設(shè)計(jì)（概要設(shè)計(jì)）軟件概要設(shè)計(jì)的基本任務(wù)是：1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；3）編寫概要設(shè)計(jì)文檔；4）概要設(shè)計(jì)文檔評(píng)審。程序結(jié)構(gòu)圖的基本圖符：模塊用一個(gè)矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信息。其表示形式如下圖：它們的含義分別是：傳入模塊：從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級(jí)模塊。變換模塊：從上級(jí)模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級(jí)模塊。程序結(jié)構(gòu)圖的有關(guān)術(shù)語列舉如下：深度：表示控制的層數(shù)。寬度：整體控制跨度（最大模塊數(shù)的層）的表示。扇出：一個(gè)模塊直接調(diào)用的其他模塊數(shù)。下圖是一個(gè)程序結(jié)構(gòu)圖的示例：面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。A、變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。B、事