【文章內容簡介】 。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密，二叉樹一章學好了，這里也就不難了。二叉排序樹，簡言之，就是“左小右大”，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優(yōu)化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，“判斷某棵二叉樹是否二叉排序樹”這一算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法，所以應該掌握平衡二叉樹的四種調整算法，調整的一個參照是：調整前后的中序遍歷結果相同。B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找算法外，應該特別注意一下B樹的插入和刪除算法。因為這兩種算法涉及到B樹結點的分裂和合并，是一個難點。B樹是報考名校的同學應該關注的焦點之一。鍵樹也稱字符樹，特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據算法思想建立鍵樹及描述其大致查找過程。3. 基本哈希表的查找算法：哈希一詞，是外來詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據當前待查找數據的特征，以記錄關鍵字為自變量，設計一個function，該函數對關鍵字進行轉換后，其解釋結果為待查的地址?；诠１淼目疾辄c有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。第八章　內部排序內排是DS課程中最后一個重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結到一點，就是考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標（時間復雜度）能否了如指掌。這一章，我們對重點的規(guī)納將跟以上各章不同。我們將從以下幾個側面來對排序一章進行不同的規(guī)納，以期能更全面的理解排序一章的總體結構及各種算法。從排序算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計數等五種排序方法。其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點，說到底就是根據什么規(guī)則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數的總范圍“由小到大”的增量來實現排序效率提高的目的。交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序?？焖倥判虻乃枷?，一語以敝之：用中間數將待排數據組一分為二?？焖倥判?，在處理的“問題規(guī)?！边@個概念上，與希爾有點相反，快速排序，是先處理一個較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達到排序的目的。選擇排序，相對于前面幾種排序算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據什么規(guī)則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數；樹選擇，是通過“錦標賽”類似的思想，讓兩數相比，不斷淘汰較大（?。┱?，最終選出最小（大）數；而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。樹選擇排序，也曾經在一些學校中的大型算法題中出現，請大家注意。歸并排序，故名思義，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數據集合才可能實現歸并。所以，在歸并排序中，關注最多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心：歸并排序是穩(wěn)定排序?；鶖蹬判?，是一種很特別的排序方法，也正是由于它的特殊，所以，基數排序就比較適合于一些特別的場合，比如撲克牌排序問題等?；鶖蹬判颍址譃閮煞N：多關鍵字的排序（撲克牌排序），鏈式排序（整數排序）。基數排序的核心思想也是利用“基數空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。本章各種排序算法的思想以及偽代碼實現，及其時間復雜度都是必須掌握的，學習時要多注意規(guī)納、總結、對比。此外，要求必須熟記，在理解的基礎上記憶，這一節(jié)幾乎成為很多學校每年的必考點。數據結構復習重點歸納數據結構大學教程The Complete Data Structure Training Course第一章 數據結構及其基本概念Chapter 1 Data Structure and It’s Basic Concepts1. 1什么是數據結構(What is Data Structure)如果你問一個木匠學徒：你工作的工具要用什么，他可能會回答你：“我只要一把錘子和一個鋸”。但是如果你去問一個老木工或者是大師級的建筑師，他會告訴你“我需要一些精確的工具”。由于計算機所解決的問題都是從生活中抽象出來的問題，其復雜性不言而喻，所以我們需要這樣精確有效的工具去解決現實生活中的復雜問題。算法、數據結構、程序設計語言都是這樣的工具。數據結構是信息的組織方式。對于相同的算法，用不同的數據結構表示其中的抽象數據類型會造成不同的執(zhí)行效率。這就有必要研究各種抽象數據類型用不同的數據結構表示的效率差異，以及其適用場合。[一]何謂數據結構（What is Data Structure）數據結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數據的內部構成，即一個數據由哪些成分數據構成，以什么方式構成，呈什么結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，而物理上的數據結構反映成分數據在計算機內部的存儲安排。數據結構是信息的一種組織方式，好的數據結構可以提高算法的效率，它通常與一組算法的集合相對應，通過這組算法集合可以對數據結構中的數據進行某種操作。從學科角度來講，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。[二]數據結構學科的研究對象 (The Object of Data Structure Research)數據結構作為一門學科，主要研究數據的各種邏輯結構和存儲結構，以及對數據的各種操作。因此，主要有三個方面的內容：數據的邏輯結構；數據的物理存儲結構；對數據的