MS二級(jí)考試必備筆記(棧,二叉樹(shù)等)

1、第一課 數(shù)據(jù)結(jié)構(gòu)和算法 數(shù)據(jù)結(jié)構(gòu)由數(shù)據(jù)和結(jié)構(gòu)構(gòu)成數(shù)據(jù)由一堆元素構(gòu)成。結(jié)構(gòu)就是關(guān)系，集合中各個(gè)數(shù)據(jù)元素之間存在的關(guān)系（聯(lián)系）。數(shù)據(jù)元素之間的關(guān)系用前件后件/直接前驅(qū)和直接后繼數(shù)據(jù)元素之間的關(guān)系：邏輯關(guān)系表示前后件關(guān)系：存儲(chǔ)關(guān)系跟邏輯關(guān)系不一定一致。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 1 順序存儲(chǔ)結(jié)構(gòu)：邏輯相鄰的數(shù)據(jù)元素存儲(chǔ)在物理相鄰存儲(chǔ)單位里 2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：第二課：棧及其基本運(yùn)算子彈匣就是一個(gè)形象的棧。 棧的特點(diǎn)：1 先進(jìn)后出，2 棧有記憶作用， 3 順序結(jié)構(gòu)下，棧的插入與刪除不需要一棟表中其他數(shù)據(jù)元素；4 棧頂指針top動(dòng)態(tài)反應(yīng)了棧中元素的變化情況。棧也稱先進(jìn)后出表（FILO） 或者后進(jìn)先出表（LIFO）棧的基

2、本運(yùn)算棧的存儲(chǔ)第三課 二叉樹(shù)及其基本性質(zhì) 定義：與一般樹(shù)結(jié)構(gòu)比較，二叉樹(shù)在結(jié)構(gòu)上具有規(guī)范性和確定性的特點(diǎn)。 二叉樹(shù)的基本性質(zhì)：性質(zhì)5和6是完全二叉樹(shù)和滿二叉樹(shù)特有的性質(zhì)：例子：二叉樹(shù)遍歷 二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，再遍歷右子樹(shù)。在先左后右的原則下，根據(jù)訪問(wèn)根節(jié)點(diǎn)的次序不同。 前序遍歷（DLR） 中序遍歷（LDR） 后序遍歷（LRD） 程序設(shè)計(jì)結(jié)構(gòu) 面向?qū)ο蠓椒ǖ幕靖拍睿宏P(guān)于面向?qū)ο蠓椒ǎ瑢?duì)其概念有許多不同的看法和定義，但是都涵蓋對(duì)象及對(duì)象屬性與方法、類(lèi)、繼承、多態(tài)性幾個(gè)基本要素。 1對(duì)象 是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。?duì)象可以用來(lái)

3、表示客觀世界中的任何實(shí)體，它既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界和意義的東西。 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中設(shè)計(jì)的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由一組靜態(tài)特征和它可執(zhí)行的一組操作組成。 客觀世界中的實(shí)體通常都既具有靜態(tài)的屬性，又具有動(dòng)態(tài)的行為，因此面向?qū)ο蠓椒ㄖ械膶?duì)象是由該對(duì)象屬性的數(shù)據(jù)以及可以對(duì)這些數(shù)據(jù)施加的所有操作封裝在一起構(gòu)成的統(tǒng)一體。屬性 是對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過(guò)執(zhí)行對(duì)象的操作來(lái)改變。 不同對(duì)象的同意屬性可以具有不同的屬性值。 一個(gè)對(duì)象能夠接受不同形式、不同內(nèi)容的多個(gè)消息，相同形式的消息可以

4、送往不同的對(duì)象，不同的對(duì)象對(duì)于形式相同的消息可以有不同的解釋?zhuān)軌蜃龀霾煌姆磻?yīng)。一個(gè)對(duì)象可以同時(shí)往多個(gè)對(duì)象傳遞消息，兩個(gè)對(duì)象也可以同時(shí)向某一個(gè)對(duì)象傳遞消息。軟件工程基本概念 軟件的定義 軟件特點(diǎn)： 軟件工程過(guò)程 軟件的維護(hù)階段，不包括大規(guī)模的修改。結(jié)構(gòu)化設(shè)計(jì)方法 軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，也就是說(shuō)軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。 軟件設(shè)計(jì)是開(kāi)發(fā)階段最重要的步驟。 概要設(shè)計(jì)：將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)及接口、全局?jǐn)?shù)據(jù)或結(jié)構(gòu)庫(kù)模式。詳細(xì)設(shè)計(jì)：確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。軟件設(shè)計(jì)的基礎(chǔ)：概要設(shè)計(jì)（總體設(shè)計(jì)）軟件概要設(shè)計(jì)的基本任務(wù)如下： 基本形式：順序形式，選擇形式，重復(fù)形式。詳細(xì)設(shè)計(jì) 程序流程圖（PFD）軟件的測(cè)試和調(diào)試軟件測(cè)試的目的： 但是暴露錯(cuò)誤并不是軟件測(cè)試的最終目的，測(cè)試的根本目的是盡可能多地發(fā)現(xiàn)并排除軟件中隱藏的錯(cuò)誤。 軟件測(cè)試