數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納筆記(參考版)
2025-04-20 01:00本頁(yè)面
【正文】 但是，由于作者本人水平有限，可能有很多考點(diǎn)沒有規(guī)納出來(lái)，也可能有些考點(diǎn)規(guī)納有誤，在此，作者本人誠(chéng)懇希望諸位朋友直面提出.________________________________________________________________________________________________________ 易考網(wǎng)，優(yōu)秀的考試資源整合提供商！ 第 頁(yè)。此外，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點(diǎn)?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列?；鶖?shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問題等。所以，在歸并排序中，關(guān)注最多的就是2路歸并。樹選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請(qǐng)大家注意。簡(jiǎn)單選擇，是通過簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù)；樹選擇，是通過“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（小）者，最終選出最小（大）數(shù)；而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。具體來(lái)說(shuō)，它可以分為：簡(jiǎn)單選擇、樹選擇、堆排。快速排序，在處理的“問題規(guī)模”這個(gè)概念上，與希爾有點(diǎn)相反，快速排序，是先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序。直接插入是依次尋找，折半插入是折半尋找。其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。我們將從以下幾個(gè)側(cè)面來(lái)對(duì)排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。但是，歸結(jié)到一點(diǎn)，就是考查你對(duì)書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)（時(shí)間復(fù)雜度）能否了如指掌?；诠１淼目疾辄c(diǎn)有：哈希函數(shù)的設(shè)計(jì)，沖突解決方法的選擇及沖突處理過程的描述。：哈希一詞，是外來(lái)詞，譯自“hash”一詞，意為：散列或雜湊的意思。鍵樹也稱字符樹，特別適用于查找英文單詞的場(chǎng)合。因?yàn)檫@兩種算法涉及到B樹結(jié)點(diǎn)的分裂和合并，是一個(gè)難點(diǎn)。B樹是二叉排序樹的進(jìn)一步改進(jìn)，也可以把B樹理解為三叉、四叉....排序樹。對(duì)于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。二叉排序樹，簡(jiǎn)言之，就是“左小右大”，它的中序遍歷結(jié)果是一個(gè)遞增的有序序列。其中，尤以前兩種結(jié)構(gòu)為重，也有部分名校偏愛考B樹的。本節(jié)內(nèi)容與樹一章的內(nèi)容有聯(lián)系，但也有很多不同，應(yīng)注意規(guī)納。：這是本章的重點(diǎn)和難點(diǎn)?？忌枰⒁膺@三種表下的ASL值以及三種算法的實(shí)現(xiàn)。對(duì)于及有序順序表我們采用二分查找法。下面詳細(xì)介紹其考查知識(shí)點(diǎn)及考查方式：：主要分為三種線性結(jié)構(gòu)：順序表，有序順序表，索引順序表。在復(fù)習(xí)這一章的知識(shí)時(shí)，你需要先弄清楚以下幾個(gè)概念：關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找與動(dòng)態(tài)查找的含義及區(qū)別；平均查找長(zhǎng)度ASL的概念及在各種查找算法中的計(jì)算方法和計(jì)算結(jié)果，特別是一些典型結(jié)構(gòu)的ASL值，應(yīng)該記住。應(yīng)該說(shuō)，查找和排序兩章是前面我們所學(xué)的知識(shí)的綜合運(yùn)用，用到了樹、也用到了鏈表等知識(shí)，對(duì)這些數(shù)據(jù)結(jié)構(gòu)某一方面的運(yùn)用就構(gòu)成了查找和排序。注意區(qū)分。這個(gè)問題也具有非常實(shí)用的背景特色，一個(gè)典型的應(yīng)該就是旅游景點(diǎn)及旅游路線的選擇問題。概念理解是比較容易的，關(guān)鍵是算法的理解。關(guān)鍵路徑問題是工程進(jìn)度控制的重要方法，具有很強(qiáng)的實(shí)用性。這個(gè)問題拿來(lái)直接考算法源碼的不多，一般是要求按照書上的算法描述求解的過程和步驟。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面：一是何謂關(guān)鍵路徑，二是最早時(shí)間是什么意思、如何求，三是最晚時(shí)間是什么意思、如何求。當(dāng)然，后一種排序出來(lái)的結(jié)果是“逆拓?fù)溆行颉钡?。：拓?fù)渑判蛴袃煞N方法，一是無(wú)前趨的頂點(diǎn)優(yōu)先算法，二是無(wú)后繼的頂點(diǎn)優(yōu)先算法。、最小生成樹的概念以及最小生成樹的構(gòu)造：PRIM算法和KRUSKAL算法。：深
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1