數(shù)據(jù)結(jié)構(gòu) 70分參考題型： 填空,選擇,判斷： 解答題： 算法題：第1頁(yè)/共30頁(yè)對(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頁(yè)/共30頁(yè)第一章 序論數(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頁(yè)/共30頁(yè)第一章 序論算法的知識(shí)點(diǎn)： 算法的定義 算法的特性 算法的時(shí)間分析和空間分析方法第4頁(yè)/共30頁(yè)第二章 線性表5個(gè)主要知識(shí)點(diǎn)：1.線性表的定義2.線性表的存儲(chǔ)表示-順序表，鏈表3.線性表的運(yùn)算在不同存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)4.有序表的操作5.線性表的應(yīng)用第5頁(yè)/共30頁(yè)第二章 線性表線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：1.邏輯上相鄰的元素在物理上也相鄰；2.不需要為表示元素之間的邏輯相鄰關(guān)系開辟附加空間；3.可以隨機(jī)訪問數(shù)據(jù)元素；4.插入和刪除元素時(shí)需要大量移動(dòng)元素。第6頁(yè)/共30頁(yè)第二章 線性表線性表鏈?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頁(yè)/共30頁(yè)第二章 線性表幾種常用的線性鏈表:1.單鏈表2.循環(huán)單鏈表(既可以用頭指針引導(dǎo),又可以用尾指針引導(dǎo))3.雙向鏈表4.雙向循環(huán)鏈表第8頁(yè)/共30頁(yè)第二章 線性表 帶頭結(jié)點(diǎn)的鏈表和不帶頭結(jié)點(diǎn)的鏈表在操作上有差別.判表空條件:第9頁(yè)/共30頁(yè)第三章 棧和隊(duì)列棧和隊(duì)列都是插入和刪除操作受到限制的特殊線性表；棧的特點(diǎn)： 后進(jìn)先出（LIFO）隊(duì)列的特點(diǎn)：先進(jìn)先出（FIFO）第10頁(yè)/共30頁(yè)第三章 棧和隊(duì)列棧的操作：順序棧：順序表操作的特例鏈棧：?jiǎn)捂湵聿僮鞯奶乩?1頁(yè)/共30頁(yè)第三章 棧和隊(duì)列隊(duì)列的操作：鏈隊(duì)列：帶頭結(jié)點(diǎn)、頭指針和尾指針的單鏈表，入隊(duì)端在表尾，出隊(duì)端在表頭。循環(huán)鏈隊(duì)列：可以只用一個(gè)尾指針用定長(zhǎng)數(shù)組作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)時(shí)，一般采用循環(huán)隊(duì)列的形式-循環(huán)隊(duì)列。第12頁(yè)/共30頁(yè)第三章 棧和隊(duì)列隊(duì)列的操作：鏈隊(duì)列：帶頭結(jié)點(diǎn)、頭指針和尾指針的單鏈表，入隊(duì)端在表尾，出隊(duì)端在表頭。循環(huán)鏈隊(duì)列：可以只用一個(gè)尾指針用定長(zhǎng)數(shù)組作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)時(shí)，一般采用循環(huán)隊(duì)列的形式第13頁(yè)/共30頁(yè)第三章 棧和隊(duì)列循環(huán)隊(duì)列：數(shù)組：Q1.maxsize-1front指向?qū)︻^元素rear指向隊(duì)尾元素的下一個(gè)隊(duì)列的最大容量：maxsize-106543217frontreara5a1a2a3a4第14頁(yè)/共30頁(yè)第三章 棧和隊(duì)列循環(huán)隊(duì)列的計(jì)算公式Q0.maxsize-1：入隊(duì)： rear = ( rear+1 ) mod maxsize出隊(duì)： front = ( front +1 ) mod maxsize隊(duì)空條件： front = rear隊(duì)滿條件： front = (rear+1) mod maxsize隊(duì)列長(zhǎng)度： (rear front + maxsize) mod maxsize第15頁(yè)/共30頁(yè)第三章 棧和隊(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ì)列長(zhǎng)度： (rear front + maxsize) mod maxsize第16頁(yè)/共30頁(yè)第4章 數(shù)組數(shù)組知識(shí)點(diǎn)：多維數(shù)組行優(yōu)先和列優(yōu)先的存儲(chǔ)方式；數(shù)組元素地址的計(jì)算方法；特殊矩陣的壓縮存儲(chǔ)方法以及下標(biāo)變換算公式的推導(dǎo)；稀疏矩陣的壓縮存儲(chǔ)技術(shù)-三元組表、十字鏈表。第17頁(yè)/共30頁(yè)第6章 樹和二叉樹知識(shí)點(diǎn)(1)：樹和二叉樹的定義二叉樹的（5個(gè)）性質(zhì)完全二叉樹的特點(diǎn)二叉樹的存儲(chǔ)結(jié)構(gòu)，主要掌握二叉鏈表二叉樹的遍歷算法以及二叉樹常用運(yùn)算第18頁(yè)/共30頁(yè)第6章 樹和二叉樹知識(shí)點(diǎn)（2）：表達(dá)式的二叉樹表示樹的存儲(chǔ)結(jié)構(gòu)樹、森林與二叉樹的相互轉(zhuǎn)換樹和森林的遍歷哈夫曼樹的定義和構(gòu)造，哈夫曼編碼方法第19頁(yè)/共30頁(yè)第7章 圖知識(shí)點(diǎn)(1)：圖的概念：有向圖，無向圖路徑，回路（環(huán)），簡(jiǎn)單路徑，簡(jiǎn)單環(huán)無向連通圖、連通分量有向強(qiáng)連通圖、強(qiáng)連通分量完全圖第20頁(yè)/共30頁(yè)第7章 圖知識(shí)點(diǎn)（2）：生成樹、生成森林熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)鄰接矩陣和鄰接表，他們的特點(diǎn)和操作熟練掌握?qǐng)D的DFS遍歷和BFS遍歷的概念和實(shí)現(xiàn)算法第21頁(yè)/共30頁(yè)第7章 圖知識(shí)點(diǎn)（3）：最小生成樹的概念和prim、Kluscla算法思想拓?fù)湫蛄械母拍詈屯負(fù)渑判蛩惴ㄗ疃搪窂降母拍詈虳ijkstra算法關(guān)鍵路徑的概念和關(guān)鍵路徑的算法思想第22頁(yè)/共30頁(yè)第8章 查找知識(shí)點(diǎn)(1)：平均查找長(zhǎng)度ASL的定義和計(jì)算方法順序查找的特點(diǎn)、算法和ASL（等概情況下查找成功的ASL（n+1)/2）折半查找的特點(diǎn)、算法和ASL（折半查找判定樹的定義和使用）第23頁(yè)/共30頁(yè)第8章 查找知識(shí)點(diǎn)(2)：索引順序查找的特點(diǎn)、查找方法和ASL二叉排序樹的定義、查找、插入、刪除哈希表的概念、哈希函數(shù)的構(gòu)造、裝填因子對(duì)查找效率的影響、解決沖突的方法（線性探測(cè)、二次探測(cè)和拉鏈法）、沖突和堆積的不同、哈希表的構(gòu)造和ASL計(jì)算第24頁(yè)/共30頁(yè)第9章 排序知識(shí)點(diǎn)：直接插入排序希爾排序冒泡排序快速排序簡(jiǎn)單選擇排序堆排序歸并排序第25頁(yè)/共30頁(yè)數(shù)據(jù)庫(kù)系統(tǒng)基本概念：DB，DBS，DBMS，概念模型，數(shù)據(jù)模型，實(shí)體，聯(lián)系（1:1，1:n，n:m)，數(shù)據(jù)獨(dú)立性，ER圖，數(shù)據(jù)模型的三要素關(guān)鍵字：候選碼，主碼，外部碼，主屬性數(shù)據(jù)庫(kù)系統(tǒng)模式結(jié)構(gòu)（三級(jí)模式，兩級(jí)映射）用數(shù)據(jù)庫(kù)系統(tǒng)來管理數(shù)據(jù)的特點(diǎn)第26頁(yè)/共30頁(yè)數(shù)據(jù)庫(kù)系統(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頁(yè)/共30頁(yè)數(shù)據(jù)庫(kù)系統(tǒng)函數(shù)依賴的概念完全函數(shù)依賴、部分函數(shù)依賴、傳遞函數(shù)依賴1NF、2NF、3NF定義會(huì)通過分解關(guān)系模式達(dá)到高級(jí)范式會(huì)將E-R圖轉(zhuǎn)換成關(guān)系模式數(shù)據(jù)庫(kù)的設(shè)計(jì)（四個(gè)步驟）第28頁(yè)/共30頁(yè)數(shù)據(jù)庫(kù)系統(tǒng)會(huì)用SQL的Select語(yǔ)句實(shí)現(xiàn)查詢單表查詢、多表連接查詢、嵌套查詢、用集函數(shù)查詢、分組查詢、結(jié)果排序會(huì)Create，Delete，Insert，Update第29頁(yè)/共30頁(yè)感謝您的觀看。第30頁(yè)/共30頁(yè)