二級(jí)公共基礎(chǔ)第一章.ppt

二級(jí)公共基礎(chǔ)知識(shí),,目 錄,第1章 數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法,考點(diǎn)1：算法的基本概念 算法：是指對(duì)解題方案的準(zhǔn)確而完整的描述 1. 算法的基本特征 （1）可行性 （2）確定性 （3）有窮性 （4）擁有足夠的情報(bào),1.1 算法,2. 算法的基本要素 （1）對(duì)數(shù)據(jù)對(duì)象的基本操作 算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸 （2）算法的控制結(jié)構(gòu),1.1 算法,考點(diǎn)2：算法的復(fù)雜度 1.算法的時(shí)間復(fù)雜度 即指執(zhí)行算法所需要的計(jì)算工作量。 （1）平均性態(tài) 即指用各種特定輸入條件下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。,1.1 算法,1.算法的時(shí)間復(fù)雜度 即指執(zhí)行算法所需要的計(jì)算工作量。 （1）平均性態(tài) 即指用各種特定輸入條件下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。 計(jì)算公式：A(n)=,1.1 算法,（2）最壞情況復(fù)雜性 即指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。 計(jì)算公式：W(n)=maxt(x) W(n) 比A(n) 好計(jì)算 2.算法的空間復(fù)雜度 指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,考點(diǎn)3：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu) 簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合，即數(shù)據(jù)組織形式。所謂結(jié)構(gòu)，就是指數(shù)據(jù)元素之間的前后件關(guān)系。 1.數(shù)據(jù)的邏輯結(jié)構(gòu) 指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,考點(diǎn)4：線性結(jié)構(gòu)與非線性結(jié)構(gòu) 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：第一，有且只有一個(gè)根結(jié)點(diǎn)；第二，每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件，則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。,1.3 線性表、棧和隊(duì)列,考點(diǎn)5：線性表和棧 1. 線性表的基本概念 2. 線性表的順序存儲(chǔ)結(jié)構(gòu) 3. 棧的定義 棧是限定在一端進(jìn)行插入與刪除的線性表 4. 棧的順序存儲(chǔ)及運(yùn)算 (1) 入棧運(yùn)算 (2) 出棧運(yùn)算 (3) 讀棧頂運(yùn)算,1.3 線性表、棧和隊(duì)列,考點(diǎn)6：隊(duì)列及其基本運(yùn)算 1. 隊(duì)列的定義 2. 循環(huán)隊(duì)列及其運(yùn)算 3. 棧的定義 棧是限定在一端進(jìn)行插入與刪除的線性表 4. 棧的順序存儲(chǔ)及運(yùn)算 (1) 入棧運(yùn)算 (2) 出棧運(yùn)算 (3) 讀棧頂運(yùn)算,1.4 線性鏈表,*考點(diǎn)7：線性鏈表的基本概念 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。,1.5 樹與二叉樹,考點(diǎn)8：樹與二叉樹 1. 樹的基本概念 2. 什么是二叉樹 3. 二叉樹的的基本性質(zhì) 4. 滿二叉樹與完全二叉樹,1.5 樹與二叉樹,*考點(diǎn)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