《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫 復(fù)習(xí)PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫 復(fù)習(xí)PPT課件（30頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu) 70分參考題型： 填空,選擇,判斷： 解答題： 算法題：第1頁/共30頁對(duì)算法的要求：根據(jù)教學(xué)知識(shí)點(diǎn)的難易和重要性，將相關(guān)的算法理解和應(yīng)用分三個(gè)層次進(jìn)行要求：層次1) 能閱讀和理解算法，能結(jié)合具體數(shù)據(jù)給出算法執(zhí)行結(jié)果；層次2) 能寫出算法的偽代碼；層次3) 能靈活運(yùn)用算法，對(duì)實(shí)際問題進(jìn)行算法設(shè)計(jì)。第2頁/共30頁第一章 序論數(shù)據(jù)結(jié)構(gòu)的知識(shí)點(diǎn)：1.數(shù)據(jù)的邏輯結(jié)構(gòu)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3.對(duì)數(shù)據(jù)的運(yùn)算（運(yùn)算的定義和運(yùn)算的實(shí)現(xiàn)）4.抽象數(shù)據(jù)類型的概念和表示方法第3頁/共30頁第一章 序論算法的知識(shí)點(diǎn)： 算法的定義 算法的特性 算法的時(shí)間分析和空間分析方法第4頁/共30頁第二章 線性表5個(gè)主要知

2、識(shí)點(diǎn)：1.線性表的定義2.線性表的存儲(chǔ)表示-順序表，鏈表3.線性表的運(yùn)算在不同存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)4.有序表的操作5.線性表的應(yīng)用第5頁/共30頁第二章 線性表線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：1.邏輯上相鄰的元素在物理上也相鄰；2.不需要為表示元素之間的邏輯相鄰關(guān)系開辟附加空間；3.可以隨機(jī)訪問數(shù)據(jù)元素；4.插入和刪除元素時(shí)需要大量移動(dòng)元素。第6頁/共30頁第二章 線性表線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：1.邏輯上相鄰的元素在物理上不一定相鄰；2.需要為表示元素之間的邏輯相鄰關(guān)系開辟附加空間：指針域；3.無法隨機(jī)訪問數(shù)據(jù)元素；4.插入和刪除元素時(shí)不需要大量移動(dòng)元素，只要修改相關(guān)結(jié)點(diǎn)的指針值即可。第7頁/共30頁

3、第二章 線性表幾種常用的線性鏈表:1.單鏈表2.循環(huán)單鏈表(既可以用頭指針引導(dǎo),又可以用尾指針引導(dǎo))3.雙向鏈表4.雙向循環(huán)鏈表第8頁/共30頁第二章 線性表 帶頭結(jié)點(diǎn)的鏈表和不帶頭結(jié)點(diǎn)的鏈表在操作上有差別.判表空條件:第9頁/共30頁第三章 棧和隊(duì)列棧和隊(duì)列都是插入和刪除操作受到限制的特殊線性表；棧的特點(diǎn)： 后進(jìn)先出（LIFO）隊(duì)列的特點(diǎn)：先進(jìn)先出（FIFO）第10頁/共30頁第三章 棧和隊(duì)列棧的操作：順序棧：順序表操作的特例鏈棧：單鏈表操作的特例第11頁/共30頁第三章 棧和隊(duì)列隊(duì)列的操作：鏈隊(duì)列：帶頭結(jié)點(diǎn)、頭指針和尾指針的單鏈表，入隊(duì)端在表尾，出隊(duì)端在表頭。循環(huán)鏈隊(duì)列：可以只用一個(gè)尾指針

4、用定長數(shù)組作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)時(shí)，一般采用循環(huán)隊(duì)列的形式-循環(huán)隊(duì)列。第12頁/共30頁第三章 棧和隊(duì)列隊(duì)列的操作：鏈隊(duì)列：帶頭結(jié)點(diǎn)、頭指針和尾指針的單鏈表，入隊(duì)端在表尾，出隊(duì)端在表頭。循環(huán)鏈隊(duì)列：可以只用一個(gè)尾指針用定長數(shù)組作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)時(shí)，一般采用循環(huán)隊(duì)列的形式第13頁/共30頁第三章 棧和隊(duì)列循環(huán)隊(duì)列：數(shù)組：Q1.maxsize-1front指向?qū)︻^元素rear指向隊(duì)尾元素的下一個(gè)隊(duì)列的最大容量：maxsize-106543217frontreara5a1a2a3a4第14頁/共30頁第三章 棧和隊(duì)列循環(huán)隊(duì)列的計(jì)算公式Q0.maxsize-1：入隊(duì)： rear = ( rear+1 )

5、mod maxsize出隊(duì)： front = ( front +1 ) mod maxsize隊(duì)空條件： front = rear隊(duì)滿條件： front = (rear+1) mod maxsize隊(duì)列長度： (rear front + maxsize) mod maxsize第15頁/共30頁第三章 棧和隊(duì)列循環(huán)隊(duì)列的計(jì)算公式Q1.maxsize：入隊(duì)： rear = rear mod maxsize+1出隊(duì)： front = front mod maxsize +1隊(duì)空條件： front = rear隊(duì)滿條件： front = rear mod maxsize+1隊(duì)列長度： (rear f

6、ront + maxsize) mod maxsize第16頁/共30頁第4章 數(shù)組數(shù)組知識(shí)點(diǎn)：多維數(shù)組行優(yōu)先和列優(yōu)先的存儲(chǔ)方式；數(shù)組元素地址的計(jì)算方法；特殊矩陣的壓縮存儲(chǔ)方法以及下標(biāo)變換算公式的推導(dǎo)；稀疏矩陣的壓縮存儲(chǔ)技術(shù)-三元組表、十字鏈表。第17頁/共30頁第6章 樹和二叉樹知識(shí)點(diǎn)(1)：樹和二叉樹的定義二叉樹的（5個(gè)）性質(zhì)完全二叉樹的特點(diǎn)二叉樹的存儲(chǔ)結(jié)構(gòu)，主要掌握二叉鏈表二叉樹的遍歷算法以及二叉樹常用運(yùn)算第18頁/共30頁第6章 樹和二叉樹知識(shí)點(diǎn)（2）：表達(dá)式的二叉樹表示樹的存儲(chǔ)結(jié)構(gòu)樹、森林與二叉樹的相互轉(zhuǎn)換樹和森林的遍歷哈夫曼樹的定義和構(gòu)造，哈夫曼編碼方法第19頁/共30頁第7章 圖

7、知識(shí)點(diǎn)(1)：圖的概念：有向圖，無向圖路徑，回路（環(huán)），簡單路徑，簡單環(huán)無向連通圖、連通分量有向強(qiáng)連通圖、強(qiáng)連通分量完全圖第20頁/共30頁第7章 圖知識(shí)點(diǎn)（2）：生成樹、生成森林熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)鄰接矩陣和鄰接表，他們的特點(diǎn)和操作熟練掌握?qǐng)D的DFS遍歷和BFS遍歷的概念和實(shí)現(xiàn)算法第21頁/共30頁第7章 圖知識(shí)點(diǎn)（3）：最小生成樹的概念和prim、Kluscla算法思想拓?fù)湫蛄械母拍詈屯負(fù)渑判蛩惴ㄗ疃搪窂降母拍詈虳ijkstra算法關(guān)鍵路徑的概念和關(guān)鍵路徑的算法思想第22頁/共30頁第8章 查找知識(shí)點(diǎn)(1)：平均查找長度ASL的定義和計(jì)算方法順序查找的特點(diǎn)、算法和ASL（等概情況下查找成功

8、的ASL（n+1)/2）折半查找的特點(diǎn)、算法和ASL（折半查找判定樹的定義和使用）第23頁/共30頁第8章 查找知識(shí)點(diǎn)(2)：索引順序查找的特點(diǎn)、查找方法和ASL二叉排序樹的定義、查找、插入、刪除哈希表的概念、哈希函數(shù)的構(gòu)造、裝填因子對(duì)查找效率的影響、解決沖突的方法（線性探測、二次探測和拉鏈法）、沖突和堆積的不同、哈希表的構(gòu)造和ASL計(jì)算第24頁/共30頁第9章 排序知識(shí)點(diǎn)：直接插入排序希爾排序冒泡排序快速排序簡單選擇排序堆排序歸并排序第25頁/共30頁數(shù)據(jù)庫系統(tǒng)基本概念：DB，DBS，DBMS，概念模型，數(shù)據(jù)模型，實(shí)體，聯(lián)系（1:1，1:n，n:m)，數(shù)據(jù)獨(dú)立性，ER圖，數(shù)據(jù)模型的三要素關(guān)鍵

9、字：候選碼，主碼，外部碼，主屬性數(shù)據(jù)庫系統(tǒng)模式結(jié)構(gòu)（三級(jí)模式，兩級(jí)映射）用數(shù)據(jù)庫系統(tǒng)來管理數(shù)據(jù)的特點(diǎn)第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ù)運(yùn)算（9種，其中原子運(yùn)算有5種）靈活運(yùn)用關(guān)系代數(shù)運(yùn)算實(shí)現(xiàn)復(fù)雜的查詢第27頁/共30頁數(shù)據(jù)庫系統(tǒng)函數(shù)依賴的概念完全函數(shù)依賴、部分函數(shù)依賴、傳遞函數(shù)依賴1NF、2NF、3NF定義會(huì)通過分解關(guān)系模式達(dá)到高級(jí)范式會(huì)將E-R圖轉(zhuǎn)換成關(guān)系模式數(shù)據(jù)庫的設(shè)計(jì)（四個(gè)步驟）第28頁/共30頁數(shù)據(jù)庫系統(tǒng)會(huì)用SQL的Select語句實(shí)現(xiàn)查詢單表查詢、多表連接查詢、嵌套查詢、用集函數(shù)查詢、分組查詢、結(jié)果排序會(huì)Create，Delete，Insert，Update第29頁/共30頁感謝您的觀看。第30頁/共30頁