數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納-免費(fèi)閱讀
【正文】 基數(shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個有序序列。簡單選擇，是通過簡單的數(shù)組遍歷方案確定最小數(shù)；樹選擇，是通過“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（小）者，最終選出最?。ù螅?shù)；而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。直接插入是依次尋找，折半插入是折半尋找。基于哈希表的考查點(diǎn)有：哈希函數(shù)的設(shè)計，沖突解決方法的選擇及沖突處理過程的描述。B樹是二叉排序樹的進(jìn)一步改進(jìn)，也可以把B樹理解為三叉、四叉....排序樹。本節(jié)內(nèi)容與樹一章的內(nèi)容有聯(lián)系，但也有很多不同，應(yīng)注意規(guī)納。下面詳細(xì)介紹其考查知識點(diǎn)及考查方式：1. 線性表上的查找：主要分為三種線性結(jié)構(gòu)：順序表，有序順序表，索引順序表。這個問題也具有非常實(shí)用的背景特色，一個典型的應(yīng)該就是旅游景點(diǎn)及旅游路線的選擇問題。理解關(guān)鍵路徑的關(guān)鍵有三個方面：一是何謂關(guān)鍵路徑，二是最早時間是什么意思、如何求，三是最晚時間是什么意思、如何求。3. 考查圖的兩種遍歷算法：深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，其中深度遍歷相當(dāng)于二叉樹中的先序遍歷,“先序、中序、后序遍歷”對于二叉樹一章的重要性。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送分題。由于二叉樹一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來（比如：求葉子個數(shù)），所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹葉子個數(shù)”這樣的題目就下筆如有神了。所以，樹這一章的重要性，已經(jīng)不說自明了。這一點(diǎn)，是理解整個廣義表一節(jié)算法的基礎(chǔ)。本章的考查重點(diǎn)有：1. 多維數(shù)組中某數(shù)組元素的position求解。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)之外。第三章 串經(jīng)歷了棧一章的痛苦煎熬后，終于迎來了串一章的柳暗花明。棧與隊列存取數(shù)據(jù)（請注意包括：存和取兩部分）的特點(diǎn)。此外，近年來在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問題。第一章 線性表作為線性結(jié)構(gòu)的開篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。一般如果要出題，多數(shù)不會作為大題出。線性表：基礎(chǔ)章節(jié)，必考內(nèi)容之一。所以，大家在這三章上可以不必花費(fèi)過多的精力，只要知道基本的概念即可。串：基礎(chǔ)章節(jié)，概念較為簡單。圖：重點(diǎn)難點(diǎn)章節(jié)，名校尤愛考。二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點(diǎn)勾劃第0章概述本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。靜態(tài)鏈表與順序表的相似及不同之處。第二章 棧與隊列棧與隊列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。4. 循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊算法。3. 順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實(shí)現(xiàn)方式。但作為考研課程來說，本章的考查重點(diǎn)可能與大學(xué)里的程序語言所關(guān)注的不太一樣，下面會作介紹。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。比如：求表深度，復(fù)制廣義表等。二叉樹的遍歷算法有三種：先序，中序和后序。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。與這些概念相聯(lián)系的相關(guān)計算題也應(yīng)該掌握。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。7. 最短路徑問題：與關(guān)鍵路徑問題并稱為圖一章的兩只攔路虎。現(xiàn)實(shí)生活中，search幾乎無處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時代，萬事離不開search，小到文檔內(nèi)文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大部分時間。其中，二分查找還要特別注意適
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1