棧一端開口（棧頂），一端封閉（棧底）棧頂top先進后出（相反）棧滿：top=n；?？眨簍op=0計算棧中數(shù)據(jù)個數(shù)：初始棧滿n-當(dāng)前；當(dāng)前-初始棧空0方法：大數(shù)-小數(shù)隊列兩端均開放循環(huán)隊列人數(shù)的計算1.隊尾>隊頭:隊尾-隊頭2.隊尾<隊頭:總數(shù)-(隊頭-隊尾)先進先出二叉樹葉子結(jié)點就是度為0的點。在任意一顆二叉樹中,度為0的點（葉子結(jié)點）總比度為2的點多1個。度為0/1/2三種可能性。根葉子結(jié)點算法兩個指標（判斷標準）1.時間復(fù)雜度:計算工作量2.空間復(fù)雜度:內(nèi)存空間量二者無關(guān)算法與運行環(huán)境無關(guān)算法具有通用性算法形式多樣數(shù)據(jù)結(jié)構(gòu)分類:邏輯結(jié)構(gòu)（頭腦中）和存儲結(jié)構(gòu)（電腦中）邏輯結(jié)構(gòu)分類:線性結(jié)構(gòu)（一對一）和非線性結(jié)構(gòu)（一對多）棧和隊列屬于線性二叉樹屬于非線性線性結(jié)構(gòu)：必須有根結(jié)點，每一個結(jié)點最多有一個前件也最多有一個后件存儲結(jié)構(gòu)分類:順序結(jié)構(gòu)（不改變順序）和鏈式結(jié)構(gòu)（改變順序）鏈式結(jié)構(gòu)空間大于順序結(jié)構(gòu)空間鏈式結(jié)構(gòu)的前后順序是任意的二叉樹的遍歷前序，中序，后序三種順序關(guān)鍵在于根的位置前序：根左右中序：左根右后序：左右根設(shè)某二叉樹的中序序列為BDCA,后序序列為DCBA,則前序序列為()

A)DCBA

B)BDCA

C)ABCD（前序根在第一個）

D)BADC根左右AB左C右D左查找查找分類:順序查找和二分法查找順序查找最大比較次數(shù)為n次在n個數(shù)找最大/最小比較次數(shù)為n-1次二分法查找最大比較次數(shù)為log2n次規(guī)律：順序存儲的有序表排序堆排序希爾排序速度：堆排序>希爾排序>其余四種選擇排序（2種）插入排序（2種）交換排序（2種）最壞比較次數(shù)為n(n-1)/2程序設(shè)計方法分類:面向結(jié)構(gòu)化程序設(shè)計面向?qū)ο蟪绦蛟O(shè)計設(shè)計要求:清晰第一,效率第二面向結(jié)構(gòu)化程序設(shè)計三種基本結(jié)構(gòu)順序、選擇、循環(huán)主要特點:自上而下逐步求精模塊化避免使用goto語句面向?qū)ο蟪绦蛟O(shè)計對象:屬性和操作的封裝體。類:具有相似屬性與操作的一組對象。實例對象的屬性:標識唯一性,封裝性,分類性,多態(tài)性類的屬性:繼承性軟件組成:程序,數(shù)據(jù)和文檔。軟件分類:系統(tǒng)軟件,工具軟件（通用性）和應(yīng)用軟件（非通用性）。軟件工程三要素:方法,工具和過程。軟件生命周期:定義階段,開發(fā)階段和維護階段。開發(fā)階段4步驟:需求分析,設(shè)計,編碼,測試。軟件危機:周期,質(zhì)量,價格。模塊獨立性內(nèi)聚性:模塊內(nèi)部耦合性:模塊之間高內(nèi)聚低耦合流程圖數(shù)據(jù)流程圖(DFD):用于結(jié)構(gòu)化分析數(shù)據(jù)字典：流程圖的核心（解釋作用）程序流程圖(PFD):用于結(jié)構(gòu)化設(shè)計測試和調(diào)試軟件測試:發(fā)現(xiàn)錯誤軟件調(diào)試:發(fā)現(xiàn)并改正錯誤測試方法:黑盒測試和白盒測試白盒：覆蓋法，基本路徑測試軟件測試4步驟:單元測試,集成測試,驗收測試,系統(tǒng)測試E-R圖三要素:實體:矩形屬性:橢圓聯(lián)系:菱形聯(lián)系分類:一對一,一對多,多對多數(shù)據(jù)庫數(shù)據(jù)庫核心:DBMS(數(shù)據(jù)庫管理系統(tǒng))數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫管理系統(tǒng)和數(shù)據(jù)庫關(guān)系。數(shù)據(jù)庫設(shè)計4階段:需求分析,概念設(shè)計,邏輯設(shè)計,物理設(shè)計。數(shù)據(jù)庫語言:定義語言,操縱語言,控制語言。操縱語言：增加，修改，刪除，查詢數(shù)據(jù)庫模式:內(nèi)模式（1個）,概念模式,外模式（n個）。數(shù)據(jù)庫中數(shù)據(jù)的特點：獨立性，集成性，高共享性，低冗余性。二維表二維表(關(guān)系)組成:二維表的行:元組二維表的列:屬性；主關(guān)鍵字和外關(guān)鍵字主關(guān)鍵字：號關(guān)系運算兩張表(結(jié)構(gòu)相同)公共部分：交,內(nèi)容集合