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