數(shù)據(jù)結構復習重點歸納筆記-免費閱讀
【正文】 本章各種排序算法的思想以及偽代碼實現(xiàn)，及其時間復雜度都是必須掌握的，學習時要多注意規(guī)納、總結、對比。堆排序中的堆建立、堆調整是重要考點。希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。第八章 內(nèi)部排序內(nèi)排是DS課程中最后一個重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。除B樹的查找算法外，應該特別注意一下B樹的插入和刪除算法。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。對于第一種，我們采用傳統(tǒng)查找方法，逐個比較。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法。簡單地說，最早時間是通過“從前向后”的方法求的，而最晚時間是通過“從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經(jīng)求出來之后才能進行。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。樹一章，處處是重點，道道是考題，大家務必個個過關。：二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個最重要的特殊之處是在于：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認為是不相同的兩棵二叉樹。我會在另一篇系列文章（）里給出三種遍歷的遞歸和非遞歸算法的背記版，到時請大家一定熟記?？傮w來說，樹一章的知識點包括：二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎上實現(xiàn)二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，樹與森林和二叉樹的轉換。近來，在一些學校中，出現(xiàn)了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。其中，理解算法是核心，會求數(shù)組是得分點。第三章 串經(jīng)歷了棧一章的痛苦煎熬后，終于迎來了串一章的柳暗花明。棧與隊列存取數(shù)據(jù)（請注意包括：存和取兩部分）的特點。此外，近年來在不少學校中還多次出現(xiàn)要求用遞歸算法實現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問題。第一章 線性表作為線性結構的開篇章節(jié)，線性表一章在線性結構的學習乃至整個數(shù)據(jù)結構學科的學習中，其作用都是不可低估的。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。一般如果要出題，多數(shù)不會作為大題出。線性表：基礎章節(jié)，必考內(nèi)容之一。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。串 ：基礎章節(jié)，概念較為簡單。圖 ：重點難點章節(jié)，名校尤愛考。二、數(shù)據(jù)結構各章節(jié)重點勾劃：第0章 概述本章主要起到總領作用，為讀者進行數(shù)據(jù)結構的學習進行了一些先期鋪墊。靜態(tài)鏈表與順序表的相似及不同之處。第二章 棧與隊列棧與隊列，是很多學習DS的同學遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。、隊滿條件，循環(huán)隊列中入隊與出隊算法。廣義表的概念，是數(shù)據(jù)結構里第一次出現(xiàn)的。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。其劃分的依據(jù)是視其每個算法中對根結點數(shù)據(jù)的訪問順序而定。對于線索二叉樹，應該掌握：線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類常考題）。這一點成為很多學校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然后回答這個問題。：圖的存儲形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。當然，后
教學教案相關推薦
鄂ICP備17016276號-1