二級公共基礎第一章.ppt

二級公共基礎知識,,目 錄,第1章 數(shù)據(jù)結構與算法,1.1 算法,考點1：算法的基本概念 算法：是指對解題方案的準確而完整的描述 1. 算法的基本特征 （1）可行性 （2）確定性 （3）有窮性 （4）擁有足夠的情報,1.1 算法,2. 算法的基本要素 （1）對數(shù)據(jù)對象的基本操作 算術運算、邏輯運算、關系運算、數(shù)據(jù)傳輸 （2）算法的控制結構,1.1 算法,考點2：算法的復雜度 1.算法的時間復雜度 即指執(zhí)行算法所需要的計算工作量。 （1）平均性態(tài) 即指用各種特定輸入條件下的基本運算次數(shù)的加權平均值來度量算法的工作量。,1.1 算法,1.算法的時間復雜度 即指執(zhí)行算法所需要的計算工作量。 （1）平均性態(tài) 即指用各種特定輸入條件下的基本運算次數(shù)的加權平均值來度量算法的工作量。 計算公式：A(n)=,1.1 算法,（2）最壞情況復雜性 即指在規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)。 計算公式：W(n)=maxt(x) W(n) 比A(n) 好計算 2.算法的空間復雜度 指執(zhí)行這個算法所需要的內(nèi)存空間。,1.2 數(shù)據(jù)結構的基本概念,考點3：數(shù)據(jù)的邏輯結構與存儲結構 簡單地說，數(shù)據(jù)結構是指相互關聯(lián)的數(shù)據(jù)元素的集合，即數(shù)據(jù)組織形式。所謂結構，就是指數(shù)據(jù)元素之間的前后件關系。 1.數(shù)據(jù)的邏輯結構 指反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結構。 2.數(shù)據(jù)的存儲結構 數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結構。,1.2 數(shù)據(jù)結構的基本概念,考點4：線性結構與非線性結構 如果一個非空的數(shù)據(jù)結構滿足下列兩個條件：第一，有且只有一個根結點；第二，每一個結點最多有一個前件，也最多有一個后件，則稱該數(shù)據(jù)結構為線性結構。 如果一個數(shù)據(jù)結構不是線性結構，則稱之為非線性結構。,1.3 線性表、棧和隊列,考點5：線性表和棧 1. 線性表的基本概念 2. 線性表的順序存儲結構 3. 棧的定義 棧是限定在一端進行插入與刪除的線性表 4. 棧的順序存儲及運算 (1) 入棧運算 (2) 出棧運算 (3) 讀棧頂運算,1.3 線性表、棧和隊列,考點6：隊列及其基本運算 1. 隊列的定義 2. 循環(huán)隊列及其運算 3. 棧的定義 棧是限定在一端進行插入與刪除的線性表 4. 棧的順序存儲及運算 (1) 入棧運算 (2) 出棧運算 (3) 讀棧頂運算,1.4 線性鏈表,*考點7：線性鏈表的基本概念 線性表的鏈式存儲結構稱為線性鏈表。,1.5 樹與二叉樹,考點8：樹與二叉樹 1. 樹的基本概念 2. 什么是二叉樹 3. 二叉樹的的基本性質(zhì) 4. 滿二叉樹與完全二叉樹,1.5 樹與二叉樹,*考點9：二叉樹的遍歷 1. 前序遍歷（DLR） 2. 中序遍歷（LDR） 3. 后序遍歷（LRD）,Diagram,Guild Design is one of aligned company with Microsoft Ltd, and we develop and provide the design templates for Office 97, 2000, and XP.,ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.,Title Add your text,Cycle Diagram,Text,Text,Text,Text,Text,Cycle name,Add Your Text,Diagram,Text,Text,Text,Add Your Title Text Text 1 Text 2 Text 3 Text 4 Text 5,Add Your Title Text Text 1 Text 2 Text 3 Text 4 Text 5,Text,Text,Diagram,Concept,Add Your Text,Text,Text,Text,Text,Text,Text,Diagram,Diagram,Add Your Text,Add Your Text,Add Your Text,Add Your Title,Diagram,Add Your Text,Add Your Text,Add Your Text,Text,Text,Text,Diagram,Text,Text,Text,Text,Add Your Title,Diagram,Title,Add Your Text,Add Your Text,Add Your Text,Add Your Text,Add Your Text,Add Your Text,Diagram,1,ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.,2,ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.,3,ThemeGallery is a Design Digital Content & Contents mall developed by Guild Design Inc.,Diagram,Your Text,Your Text,Your Text,Your Text,Your Text,Your Text,Your Text,Your Text,2001,2002,2003,2004,Progress Diagram,Phas