數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納筆記-資料下載頁(yè)
2025-04-17 01:00本頁(yè)面
【正文】 后的中序遍歷結(jié)果相同。B樹是二叉排序樹的進(jìn)一步改進(jìn)，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找算法外，應(yīng)該特別注意一下B樹的插入和刪除算法。因?yàn)檫@兩種算法涉及到B樹結(jié)點(diǎn)的分裂和合并，是一個(gè)難點(diǎn)。B樹是報(bào)考名校的同學(xué)應(yīng)該關(guān)注的焦點(diǎn)之一。鍵樹也稱字符樹，特別適用于查找英文單詞的場(chǎng)合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹及描述其大致查找過(guò)程。：哈希一詞，是外來(lái)詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據(jù)當(dāng)前待查找數(shù)據(jù)的特征，以記錄關(guān)鍵字為自變量，設(shè)計(jì)一個(gè)function，該函數(shù)對(duì)關(guān)鍵字進(jìn)行轉(zhuǎn)換后，其解釋結(jié)果為待查的地址?；诠１淼目疾辄c(diǎn)有：哈希函數(shù)的設(shè)計(jì)，沖突解決方法的選擇及沖突處理過(guò)程的描述。第八章 內(nèi)部排序內(nèi)排是DS課程中最后一個(gè)重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點(diǎn)，就是考查你對(duì)書本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)（時(shí)間復(fù)雜度）能否了如指掌。這一章，我們對(duì)重點(diǎn)的規(guī)納將跟以上各章不同。我們將從以下幾個(gè)側(cè)面來(lái)對(duì)排序一章進(jìn)行不同的規(guī)納，以期能更全面的理解排序一章的總體結(jié)構(gòu)及各種算法。從排序算法的種類來(lái)分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說(shuō)到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過(guò)控制每次參與排序的數(shù)的總范圍“由小到大”的增量來(lái)實(shí)現(xiàn)排序效率提高的目的。交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷耄徽Z(yǔ)以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二。快速排序，在處理的“問題規(guī)?！边@個(gè)概念上，與希爾有點(diǎn)相反，快速排序，是先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。選擇排序，相對(duì)于前面幾種排序算法來(lái)說(shuō)，難度大一點(diǎn)。具體來(lái)說(shuō)，它可以分為：簡(jiǎn)單選擇、樹選擇、堆排。這三種方法的不同點(diǎn)是，根據(jù)什么規(guī)則選取最小的數(shù)。簡(jiǎn)單選擇，是通過(guò)簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù)；樹選擇，是通過(guò)“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（小）者，最終選出最小（大）數(shù)；而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過(guò)堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。樹選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請(qǐng)大家注意。歸并排序，故名思義，是通過(guò)“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實(shí)現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單，有一點(diǎn)，要銘記在心：歸并排序是穩(wěn)定排序。基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問題等?；鶖?shù)排序，又分為兩種：多關(guān)鍵字的排序（撲克牌排序），鏈?zhǔn)脚判颍ㄕ麛?shù)排序）?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問題規(guī)模規(guī)范、變小，并且，在排序的過(guò)程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列。本章各種排序算法的思想以及偽代碼實(shí)現(xiàn)，及其時(shí)間復(fù)雜度都是必須掌握的，學(xué)習(xí)時(shí)要多注意規(guī)納、總結(jié)、對(duì)比。此外，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點(diǎn)。至此，數(shù)據(jù)結(jié)構(gòu)所有章節(jié)的章節(jié)重點(diǎn)問題，我們已經(jīng)規(guī)納完畢，使用清華嚴(yán)版教材的同學(xué)，在復(fù)習(xí)的同時(shí)，可以參照本貼給出的重點(diǎn)進(jìn)行復(fù)習(xí)。但是，由于作者本人水平有限，可能有很多考點(diǎn)沒有規(guī)納出來(lái)，也可能有些考點(diǎn)規(guī)納有誤，在此，作者本人誠(chéng)懇希望諸位朋友直面提出.________________________________________________________________________________________________________ 易考網(wǎng)，優(yōu)秀的考試資源整合提供商！ 第 頁(yè)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1