HEAD
在二叉樹(shù)的第K層上最多有2的K-1次方個(gè)結(jié)點(diǎn)
深度為M的二叉樹(shù)最多有2的M次方-1個(gè)結(jié)點(diǎn)
具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log2N]+1，其中對(duì)數(shù)部分取整數(shù)
滿二叉樹(shù)與完全二叉樹(shù)
二叉樹(shù)的遍歷；前序，中序，后序遍歷
遍歷方法：可先按要求逐個(gè)遍歷個(gè)子樹(shù)，然后進(jìn)行排序
順序查找最壞需比較N次
二分法查找最壞需比較log2N次
冒泡排序法最壞需比較N（N-1）/2次
簡(jiǎn)單插入排序法最壞需比較N（N-1）/2次
希爾排序法最壞需比較O（N的1.5次方）次
簡(jiǎn)單選擇排序法最壞需比較N（N-1）/2次
堆排序法最壞需比較O（Nlog2N）次
二 程序設(shè)計(jì)基礎(chǔ)
程序設(shè)計(jì)方法主要經(jīng)過(guò)了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段
注釋分為序言性注釋和功能性注釋
結(jié) 程序的質(zhì)量與GOTO語(yǔ)句的數(shù)量成反比
構(gòu)
程 順序結(jié)構(gòu)
化 三種基本結(jié)構(gòu) 選擇結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu)----先判斷后執(zhí)行
序 重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）
設(shè) 直到型循環(huán)結(jié)構(gòu)----先執(zhí)行后判斷
計(jì)
選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口
面向?qū)ο蟮姆椒ê图夹g(shù)以對(duì)象（類(lèi)）為核心
面 1 創(chuàng)建該類(lèi)的實(shí)例，從而直接使用
向
對(duì) 兩種方法可以重復(fù)是用一個(gè)對(duì)象類(lèi) 2 從它派生出一個(gè)滿足當(dāng)前需要的新類(lèi)
象 對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性、分類(lèi)性、多態(tài)性、封裝性，模塊獨(dú)立性好
的 對(duì)象是類(lèi)的實(shí)例，消息是實(shí)例之間傳遞的信息
程 消息構(gòu)成：接收消息的對(duì)象的名稱(chēng)，消息名，零個(gè)或多個(gè)參數(shù)
序 （例如：MyCircle.show(GREEN)） MyCircle是接收對(duì)象名稱(chēng)show是消息名GREEN是參數(shù)
設(shè)計(jì) 繼承具有傳遞性，繼承分單繼承和多重繼承
三 軟件工程基礎(chǔ)
計(jì)算機(jī)軟件是包括程序，數(shù)據(jù)及相關(guān)文檔的完整集合
計(jì)算機(jī)軟件定義：與計(jì)算機(jī)系統(tǒng)的操作相關(guān)的計(jì)算機(jī)程序，規(guī)程，規(guī)則以及可能有的文件文檔及數(shù)據(jù)
軟件按功能可以分為；應(yīng)用軟件，系統(tǒng)軟件，支撐軟件（工具軟件）
軟件工程的三個(gè)要素：方法，工具，過(guò)程
軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程
軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開(kāi)發(fā)技術(shù)和軟件技術(shù)管理
軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性
軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合
結(jié)構(gòu)化分析方法：
軟件開(kāi)發(fā)方法包括：分析方法，設(shè)計(jì)方法，程序設(shè)計(jì)方法
需求分析將創(chuàng)建所需的數(shù)據(jù)模型，功能模型，控制模型
需求分析階段的工作：需求獲取，需求分析，編寫(xiě)需求規(guī)格說(shuō)明書(shū)，需求評(píng)審
需求分析方法：結(jié)構(gòu)化分析方法（包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法、面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法、面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法），面向?qū)ο蟮姆治龇椒?BR> 結(jié)構(gòu)化方法包括；結(jié)構(gòu)化分析方法，結(jié)構(gòu)化設(shè)計(jì)方法，結(jié)構(gòu)化編程方法
結(jié)構(gòu)化分析方法常用工具：數(shù)據(jù)流圖（圖符：加工，數(shù)據(jù)流，存儲(chǔ)文件，源或潭），數(shù)據(jù)字典，判定樹(shù)，判定表
數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心
數(shù)據(jù)字典的作用是對(duì)DFD中出現(xiàn)的被命名的圖形元素的確切解釋
判定表或判定樹(shù)是以圖形的形式描述數(shù)據(jù)流圖的加工邏輯
結(jié)構(gòu)化設(shè)計(jì)方法：
•軟件設(shè)計(jì)是確定系統(tǒng)的物理模型
•軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)，數(shù)據(jù)設(shè)計(jì)，接口設(shè)計(jì)，過(guò)程設(shè)計(jì)
•軟件設(shè)計(jì)分兩步：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)
•衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)
•內(nèi)聚性是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量
•耦合性是模塊間相互連接的緊密程度的度量
1.概要設(shè)計(jì)
•常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖（圖符：一般模塊，數(shù)據(jù)信息，控制信息）
•經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類(lèi)型：傳入模塊，傳出模塊，變換模塊，協(xié)調(diào)模塊
•數(shù)據(jù)流類(lèi)型：變換型，事務(wù)型
•變換型系統(tǒng)結(jié)構(gòu)圖由輸入，中心變換，輸出三部分組成
2.詳細(xì)設(shè)計(jì)
•常見(jiàn)的過(guò)程設(shè)計(jì)工具有 圖形類(lèi)：程序流程圖（圖符：控制流，加工步驟，邏輯條件）
N-S圖
PAD圖
語(yǔ)言類(lèi)：PDL
•型：順序型，選擇型，先判斷重復(fù)型，后判斷重復(fù)型，多分支選擇型
在二叉樹(shù)的第K層上最多有2的K-1次方個(gè)結(jié)點(diǎn)
深度為M的二叉樹(shù)最多有2的M次方-1個(gè)結(jié)點(diǎn)
具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log2N]+1，其中對(duì)數(shù)部分取整數(shù)
滿二叉樹(shù)與完全二叉樹(shù)
二叉樹(shù)的遍歷；前序，中序，后序遍歷
遍歷方法：可先按要求逐個(gè)遍歷個(gè)子樹(shù)，然后進(jìn)行排序
順序查找最壞需比較N次
二分法查找最壞需比較log2N次
冒泡排序法最壞需比較N（N-1）/2次
簡(jiǎn)單插入排序法最壞需比較N（N-1）/2次
希爾排序法最壞需比較O（N的1.5次方）次
簡(jiǎn)單選擇排序法最壞需比較N（N-1）/2次
堆排序法最壞需比較O（Nlog2N）次
二 程序設(shè)計(jì)基礎(chǔ)
程序設(shè)計(jì)方法主要經(jīng)過(guò)了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段
注釋分為序言性注釋和功能性注釋
結(jié) 程序的質(zhì)量與GOTO語(yǔ)句的數(shù)量成反比
構(gòu)
程 順序結(jié)構(gòu)
化 三種基本結(jié)構(gòu) 選擇結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu)----先判斷后執(zhí)行
序 重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）
設(shè) 直到型循環(huán)結(jié)構(gòu)----先執(zhí)行后判斷
計(jì)
選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口
面向?qū)ο蟮姆椒ê图夹g(shù)以對(duì)象（類(lèi)）為核心
面 1 創(chuàng)建該類(lèi)的實(shí)例，從而直接使用
向
對(duì) 兩種方法可以重復(fù)是用一個(gè)對(duì)象類(lèi) 2 從它派生出一個(gè)滿足當(dāng)前需要的新類(lèi)
象 對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性、分類(lèi)性、多態(tài)性、封裝性，模塊獨(dú)立性好
的 對(duì)象是類(lèi)的實(shí)例，消息是實(shí)例之間傳遞的信息
程 消息構(gòu)成：接收消息的對(duì)象的名稱(chēng)，消息名，零個(gè)或多個(gè)參數(shù)
序 （例如：MyCircle.show(GREEN)） MyCircle是接收對(duì)象名稱(chēng)show是消息名GREEN是參數(shù)
設(shè)計(jì) 繼承具有傳遞性，繼承分單繼承和多重繼承
三 軟件工程基礎(chǔ)
計(jì)算機(jī)軟件是包括程序，數(shù)據(jù)及相關(guān)文檔的完整集合
計(jì)算機(jī)軟件定義：與計(jì)算機(jī)系統(tǒng)的操作相關(guān)的計(jì)算機(jī)程序，規(guī)程，規(guī)則以及可能有的文件文檔及數(shù)據(jù)
軟件按功能可以分為；應(yīng)用軟件，系統(tǒng)軟件，支撐軟件（工具軟件）
軟件工程的三個(gè)要素：方法，工具，過(guò)程
軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程
軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開(kāi)發(fā)技術(shù)和軟件技術(shù)管理
軟件工程的原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可驗(yàn)證性
軟件開(kāi)發(fā)環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合
結(jié)構(gòu)化分析方法：
軟件開(kāi)發(fā)方法包括：分析方法，設(shè)計(jì)方法，程序設(shè)計(jì)方法
需求分析將創(chuàng)建所需的數(shù)據(jù)模型，功能模型，控制模型
需求分析階段的工作：需求獲取，需求分析，編寫(xiě)需求規(guī)格說(shuō)明書(shū)，需求評(píng)審
需求分析方法：結(jié)構(gòu)化分析方法（包括面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法、面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法、面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法），面向?qū)ο蟮姆治龇椒?BR> 結(jié)構(gòu)化方法包括；結(jié)構(gòu)化分析方法，結(jié)構(gòu)化設(shè)計(jì)方法，結(jié)構(gòu)化編程方法
結(jié)構(gòu)化分析方法常用工具：數(shù)據(jù)流圖（圖符：加工，數(shù)據(jù)流，存儲(chǔ)文件，源或潭），數(shù)據(jù)字典，判定樹(shù)，判定表
數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心
數(shù)據(jù)字典的作用是對(duì)DFD中出現(xiàn)的被命名的圖形元素的確切解釋
判定表或判定樹(shù)是以圖形的形式描述數(shù)據(jù)流圖的加工邏輯
結(jié)構(gòu)化設(shè)計(jì)方法：
•軟件設(shè)計(jì)是確定系統(tǒng)的物理模型
•軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)，數(shù)據(jù)設(shè)計(jì)，接口設(shè)計(jì)，過(guò)程設(shè)計(jì)
•軟件設(shè)計(jì)分兩步：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)
•衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)
•內(nèi)聚性是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量
•耦合性是模塊間相互連接的緊密程度的度量
1.概要設(shè)計(jì)
•常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖（圖符：一般模塊，數(shù)據(jù)信息，控制信息）
•經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類(lèi)型：傳入模塊，傳出模塊，變換模塊，協(xié)調(diào)模塊
•數(shù)據(jù)流類(lèi)型：變換型，事務(wù)型
•變換型系統(tǒng)結(jié)構(gòu)圖由輸入，中心變換，輸出三部分組成
2.詳細(xì)設(shè)計(jì)
•常見(jiàn)的過(guò)程設(shè)計(jì)工具有 圖形類(lèi)：程序流程圖（圖符：控制流，加工步驟，邏輯條件）
N-S圖
PAD圖
語(yǔ)言類(lèi)：PDL
•型：順序型，選擇型，先判斷重復(fù)型，后判斷重復(fù)型，多分支選擇型