《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫 復(fù)習(xí)PPT課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫 復(fù)習(xí)PPT課件（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、數(shù)據(jù)結(jié)構(gòu) 70分參考題型： 填空,選擇,判斷： 解答題： 算法題：第1頁/共30頁對算法的要求：根據(jù)教學(xué)知識點的難易和重要性，將相關(guān)的算法理解和應(yīng)用分三個層次進行要求：層次1) 能閱讀和理解算法，能結(jié)合具體數(shù)據(jù)給出算法執(zhí)行結(jié)果；層次2) 能寫出算法的偽代碼；層次3) 能靈活運用算法，對實際問題進行算法設(shè)計。第2頁/共30頁第一章 序論數(shù)據(jù)結(jié)構(gòu)的知識點：1.數(shù)據(jù)的邏輯結(jié)構(gòu)2.數(shù)據(jù)的存儲結(jié)構(gòu)3.對數(shù)據(jù)的運算（運算的定義和運算的實現(xiàn)）4.抽象數(shù)據(jù)類型的概念和表示方法第3頁/共30頁第一章 序論算法的知識點： 算法的定義 算法的特性 算法的時間分析和空間分析方法第4頁/共30頁第二章 線性表5個主要知
2、識點：1.線性表的定義2.線性表的存儲表示-順序表，鏈表3.線性表的運算在不同存儲結(jié)構(gòu)上的實現(xiàn)4.有序表的操作5.線性表的應(yīng)用第5頁/共30頁第二章 線性表線性表順序存儲結(jié)構(gòu)的特點：1.邏輯上相鄰的元素在物理上也相鄰；2.不需要為表示元素之間的邏輯相鄰關(guān)系開辟附加空間；3.可以隨機訪問數(shù)據(jù)元素；4.插入和刪除元素時需要大量移動元素。第6頁/共30頁第二章 線性表線性表鏈式存儲結(jié)構(gòu)的特點：1.邏輯上相鄰的元素在物理上不一定相鄰；2.需要為表示元素之間的邏輯相鄰關(guān)系開辟附加空間：指針域；3.無法隨機訪問數(shù)據(jù)元素；4.插入和刪除元素時不需要大量移動元素，只要修改相關(guān)結(jié)點的指針值即可。第7頁/共30頁
3、第二章 線性表幾種常用的線性鏈表:1.單鏈表2.循環(huán)單鏈表(既可以用頭指針引導(dǎo),又可以用尾指針引導(dǎo))3.雙向鏈表4.雙向循環(huán)鏈表第8頁/共30頁第二章 線性表 帶頭結(jié)點的鏈表和不帶頭結(jié)點的鏈表在操作上有差別.判表空條件:第9頁/共30頁第三章 棧和隊列棧和隊列都是插入和刪除操作受到限制的特殊線性表；棧的特點： 后進先出（LIFO）隊列的特點：先進先出（FIFO）第10頁/共30頁第三章 棧和隊列棧的操作：順序棧：順序表操作的特例鏈棧：單鏈表操作的特例第11頁/共30頁第三章 棧和隊列隊列的操作：鏈隊列：帶頭結(jié)點、頭指針和尾指針的單鏈表，入隊端在表尾，出隊端在表頭。循環(huán)鏈隊列：可以只用一個尾指針
4、用定長數(shù)組作為隊列的存儲結(jié)構(gòu)時，一般采用循環(huán)隊列的形式-循環(huán)隊列。第12頁/共30頁第三章 棧和隊列隊列的操作：鏈隊列：帶頭結(jié)點、頭指針和尾指針的單鏈表，入隊端在表尾，出隊端在表頭。循環(huán)鏈隊列：可以只用一個尾指針用定長數(shù)組作為隊列的存儲結(jié)構(gòu)時，一般采用循環(huán)隊列的形式第13頁/共30頁第三章 棧和隊列循環(huán)隊列：數(shù)組：Q1.maxsize-1front指向?qū)︻^元素rear指向隊尾元素的下一個隊列的最大容量：maxsize-106543217frontreara5a1a2a3a4第14頁/共30頁第三章 棧和隊列循環(huán)隊列的計算公式Q0.maxsize-1：入隊： rear = ( rear+1 )
5、mod maxsize出隊： front = ( front +1 ) mod maxsize隊空條件： front = rear隊滿條件： front = (rear+1) mod maxsize隊列長度： (rear front + maxsize) mod maxsize第15頁/共30頁第三章 棧和隊列循環(huán)隊列的計算公式Q1.maxsize：入隊： rear = rear mod maxsize+1出隊： front = front mod maxsize +1隊空條件： front = rear隊滿條件： front = rear mod maxsize+1隊列長度： (rear f
6、ront + maxsize) mod maxsize第16頁/共30頁第4章 數(shù)組數(shù)組知識點：多維數(shù)組行優(yōu)先和列優(yōu)先的存儲方式；數(shù)組元素地址的計算方法；特殊矩陣的壓縮存儲方法以及下標變換算公式的推導(dǎo)；稀疏矩陣的壓縮存儲技術(shù)-三元組表、十字鏈表。第17頁/共30頁第6章 樹和二叉樹知識點(1)：樹和二叉樹的定義二叉樹的（5個）性質(zhì)完全二叉樹的特點二叉樹的存儲結(jié)構(gòu)，主要掌握二叉鏈表二叉樹的遍歷算法以及二叉樹常用運算第18頁/共30頁第6章 樹和二叉樹知識點（2）：表達式的二叉樹表示樹的存儲結(jié)構(gòu)樹、森林與二叉樹的相互轉(zhuǎn)換樹和森林的遍歷哈夫曼樹的定義和構(gòu)造，哈夫曼編碼方法第19頁/共30頁第7章 圖
7、知識點(1)：圖的概念：有向圖，無向圖路徑，回路（環(huán)），簡單路徑，簡單環(huán)無向連通圖、連通分量有向強連通圖、強連通分量完全圖第20頁/共30頁第7章 圖知識點（2）：生成樹、生成森林熟練掌握圖的存儲結(jié)構(gòu)鄰接矩陣和鄰接表，他們的特點和操作熟練掌握圖的DFS遍歷和BFS遍歷的概念和實現(xiàn)算法第21頁/共30頁第7章 圖知識點（3）：最小生成樹的概念和prim、Kluscla算法思想拓撲序列的概念和拓撲排序算法最短路徑的概念和Dijkstra算法關(guān)鍵路徑的概念和關(guān)鍵路徑的算法思想第22頁/共30頁第8章 查找知識點(1)：平均查找長度ASL的定義和計算方法順序查找的特點、算法和ASL（等概情況下查找成功
8、的ASL（n+1)/2）折半查找的特點、算法和ASL（折半查找判定樹的定義和使用）第23頁/共30頁第8章 查找知識點(2)：索引順序查找的特點、查找方法和ASL二叉排序樹的定義、查找、插入、刪除哈希表的概念、哈希函數(shù)的構(gòu)造、裝填因子對查找效率的影響、解決沖突的方法（線性探測、二次探測和拉鏈法）、沖突和堆積的不同、哈希表的構(gòu)造和ASL計算第24頁/共30頁第9章 排序知識點：直接插入排序希爾排序冒泡排序快速排序簡單選擇排序堆排序歸并排序第25頁/共30頁數(shù)據(jù)庫系統(tǒng)基本概念：DB，DBS，DBMS，概念模型，數(shù)據(jù)模型，實體，聯(lián)系（1:1，1:n，n:m)，數(shù)據(jù)獨立性，ER圖，數(shù)據(jù)模型的三要素關(guān)鍵
9、字：候選碼，主碼，外部碼，主屬性數(shù)據(jù)庫系統(tǒng)模式結(jié)構(gòu)（三級模式，兩級映射）用數(shù)據(jù)庫系統(tǒng)來管理數(shù)據(jù)的特點第26頁/共30頁數(shù)據(jù)庫系統(tǒng)關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)關(guān)系的定義、關(guān)系的性質(zhì)關(guān)系的完整性規(guī)則關(guān)系模式的概念關(guān)系代數(shù)運算（9種，其中原子運算有5種）靈活運用關(guān)系代數(shù)運算實現(xiàn)復(fù)雜的查詢第27頁/共30頁數(shù)據(jù)庫系統(tǒng)函數(shù)依賴的概念完全函數(shù)依賴、部分函數(shù)依賴、傳遞函數(shù)依賴1NF、2NF、3NF定義會通過分解關(guān)系模式達到高級范式會將E-R圖轉(zhuǎn)換成關(guān)系模式數(shù)據(jù)庫的設(shè)計（四個步驟）第28頁/共30頁數(shù)據(jù)庫系統(tǒng)會用SQL的Select語句實現(xiàn)查詢單表查詢、多表連接查詢、嵌套查詢、用集函數(shù)查詢、分組查詢、結(jié)果排序會Create，Delete，Insert，Update第29頁/共30頁感謝您的觀看。第30頁/共30頁
數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫 復(fù)習(xí)PPT課件
