二級新增知識點

1、公共基礎(chǔ)知識（二級） 公共基礎(chǔ)知識總復(fù)習(xí) 主講人：高艷霞主講人：高艷霞第一章 數(shù)據(jù)結(jié)構(gòu)與算法n1、算法 基本特征、時間復(fù)雜度（會計算簡單算法的）、空間復(fù)雜度2、基本概念 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容、目的、定義、邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)n3、線性結(jié)構(gòu)幾個特例（線性表、棧、隊列）的特征與操作比較： 順序表不需要指針、棧和隊列都有兩個指針、指向位置的區(qū)別、滿與空的判別n4、順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別、操作的異同，各有什么優(yōu)缺點，注意同樣存在鏈棧、鏈隊，頭指針與頭結(jié)點的區(qū)別。鏈表的頭指針與頭結(jié)點圖n頭指針：指向第一個結(jié)點；n頭結(jié)點：鏈表中為方便運算而設(shè)置的結(jié)點。a2a1anHead510270地址：5頭結(jié)點頭指針總結(jié)

2、：順序表的優(yōu)缺點n順序表的優(yōu)點：n1）無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間。n2）可以方便地隨機(jī)存取表中的任一結(jié)點。n順序表的缺點：n1）插入和刪除運算不方便。須移動大量結(jié)點，效率較低。n2）存取空間要預(yù)先分配，動態(tài)擴(kuò)充和分配都不方便。總結(jié)：鏈表的優(yōu)缺點n鏈表的優(yōu)點：n1）插入和刪除很方便。n2）不需要實現(xiàn)估計“容量”，擴(kuò)充和動態(tài)分配空間很容易。n鏈表的缺點：n1）為表示結(jié)點間的邏輯關(guān)系需要增加額外的空間。n2）不能實現(xiàn)隨機(jī)訪問。n5、樹與二叉樹 1）根、葉子、度、深度的概念 2）二叉樹的五條性質(zhì)：總個數(shù)、葉子數(shù)、高度的計算。 完全二叉樹中，由總結(jié)點個數(shù)求葉子與非葉子結(jié)點的簡單做法。

3、 3）三種遍歷方法：由其中兩種求另一種遍歷的序列一定要知道。n6、查找技術(shù)n順序查找適合于任何線性表，最壞情況需要比較n次n二分查找只適應(yīng)于順序存儲的有序表，二分查找的結(jié)束直到查找成功或子表長度為0才停止，要會計算它的次數(shù)；最壞情況需要比較log2n二分查找舉例n設(shè)有有序表（5，16，23，42，58，67，79，81）使用二分法查找元素23。元素地址123456789值51623354258677981第一次第二次第三次Low=1High=9Mid=5High=4Mid=2Low=3Mid=3Mid=(Low+High)/2n7、排序技術(shù) 排序的目的、分類、各種排序的思想與時間復(fù)雜度，冒泡、

4、簡單插入、簡單選擇的比較次數(shù)要會計算。各種排序方法的性能比較排序方法最好情況/時間最壞情況/時間空間復(fù)雜度冒泡排序n-1n(n-1)/2O(1)快速排序nlog2nn(n-1)/2O(log2n)簡單插入n-1n(n-1)/2O(1)希爾排序O(n1.5)特定增量序列O(1)簡單選擇n(n-1)/2n(n-1)/2O(1)堆排序O(nlog2n)O(nlog2n)O(1)二、程序設(shè)計方法與風(fēng)格n程序設(shè)計發(fā)展的兩個階段、風(fēng)格的定義、主導(dǎo)風(fēng)格是什么？n結(jié)構(gòu)化程序設(shè)計的主要原則、GOTO語句的使用問題n面向?qū)ο蟪绦蛟O(shè)計 1）著名的面向?qū)ο笳Z言有哪些：Simula、SmallTalk、c+、java

5、n2）面向?qū)ο蠓椒ê图夹g(shù)以對象為核心。設(shè)計原理是模擬現(xiàn)實世界。主要優(yōu)點是可重用性、可維護(hù)性、易擴(kuò)展，這是符合軟件工程要求的。n3）基本概念 對象及其組成、特點。類及其與對象關(guān)系。注意：對象沒有繼承性，類沒有多態(tài)性。 4）消息 作用及組成、類的繼承性和對象的多態(tài)性實現(xiàn)了軟件的可重用性和可擴(kuò)充性。三 軟件工程n3.1.1、軟件危機(jī)的表現(xiàn)與軟件工程的定義及三要素n3.1.2 軟件工程過程與PDCA、軟件生命周期n3.1.3 軟件工程研究內(nèi)容3.2 結(jié)構(gòu)化分析方法n1）需求分析的任務(wù)、目的（三大模型）、工作內(nèi)容、方法n2）常用工具：四種（圖字樹表）兔子鼠標(biāo)兔子鼠標(biāo)n3）分析成果3.3 結(jié)構(gòu)化設(shè)計n1）

6、概要設(shè)計與詳細(xì)設(shè)計的任務(wù)劃分n2）設(shè)計原則：抽象、模塊化、信息隱蔽、 模塊獨立性（內(nèi)聚與耦合） 3） 概要設(shè)計方法：采用結(jié)構(gòu)圖，面向數(shù)據(jù)流 4） 詳細(xì)設(shè)計工具：三圖一碼3.4 測試與調(diào)試n測試涵蓋整個軟件過程、測試六準(zhǔn)則、靜態(tài)測試、動態(tài)測試需要測試用例、白盒測試與黑盒測試的區(qū)別、測試實施步驟（單集驗系）n調(diào)試與測試的區(qū)別、方法、靜態(tài)調(diào)試是主要的調(diào)試手段四 數(shù)據(jù)庫設(shè)計基礎(chǔ)n1、基本概念 DB、DBMS、DBS、DBAS的聯(lián)系與區(qū)別 常見的DBMS:Oracle、PB、DB2、 SQLServer、VF（非嚴(yán)格） 數(shù)據(jù)一致性、物理獨立性、邏輯獨立性、三級模式與兩級映射、存儲結(jié)構(gòu)屬于內(nèi)模式的范疇2、數(shù)據(jù)模型nE-R模型屬于概念模型、層次、網(wǎng)狀、關(guān)系模型屬于邏輯模型及兩類模型的表示、候選鍵、主鍵、關(guān)系與關(guān)系模式的區(qū)別、三類完整性約束的理解。n3、關(guān)系代數(shù)與關(guān)系演算是數(shù)據(jù)庫的理論基礎(chǔ)n4、數(shù)據(jù)庫的設(shè)計 概要設(shè)計與邏輯設(shè)計應(yīng)該都?xì)w于軟件工程的概要設(shè)計、視圖集成時應(yīng)注意解決四類沖突、物理設(shè)計的內(nèi)容二級考