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