數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納一(適于清華嚴(yán)版教材)_跨考網(wǎng)
一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點(diǎn)構(gòu)成
數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為:概論,線性表,棧和隊(duì)列,串,多維數(shù)組和廣義表,樹和二叉樹,圖,查找,內(nèi)排,外排,文件,動(dòng)態(tài)存儲(chǔ)分配。
對(duì)于絕大多數(shù)的學(xué)校而言,“外排,文件,動(dòng)態(tài)存儲(chǔ)分配”三章基本上是不考的,在大多數(shù)高校的計(jì)算機(jī)本科教學(xué)過程中,這三章也是基本上不作講授的。所以,大家在這三章上可以不必花費(fèi)過多的精力,只要知道基本的概念即可。但是,對(duì)于報(bào)考名校特別是該校又有在試卷中對(duì)這三章進(jìn)行過考核的歷史,那么這部分朋友就要留意這三章了。
按照以上我們給出的章節(jié)以及對(duì)后三章的介紹,數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為:
概論:內(nèi)容很少,概念簡(jiǎn)單,分?jǐn)?shù)大多只有幾分,有的學(xué)校甚至不考。
線性表:基礎(chǔ)章節(jié),必考內(nèi)容之一??碱}多數(shù)為基本概念題,名??碱}中,鮮有大型算法設(shè)計(jì)題。如果有,也是與其它章節(jié)內(nèi)容相結(jié)合。
棧和隊(duì)列:基礎(chǔ)章節(jié),容易出基本概念題,必考內(nèi)容之一。而棧常與其它章節(jié)配合考查,也常與遞歸等概念相聯(lián)系進(jìn)行考查。
串 :基礎(chǔ)章節(jié),概念較為簡(jiǎn)單。專門針對(duì)于此章的大型算法設(shè)計(jì)題很少,較常見的是根據(jù)KMP進(jìn)行算法分析。
多維數(shù)組及廣義表 :基礎(chǔ)章節(jié),基于數(shù)組的算法題也是常見的,分?jǐn)?shù)比例波動(dòng)較大,是出題的“可選單元”或“侯補(bǔ)單元”。一般如果要出題,多數(shù)不會(huì)作為大題出。數(shù)組常與“查找,排序”等章節(jié)結(jié)合來作為大題考查。
樹和二叉樹 :重點(diǎn)難點(diǎn)章節(jié),各校必考章節(jié)。各校在此章出題的不同之處在于,是否在本章中出一到兩道大的算法設(shè)計(jì)題。通過對(duì)多所學(xué)校的試卷分析,絕大多數(shù)學(xué)校在本章都曾有過出大型算法設(shè)計(jì)題的歷史。
圖 :重點(diǎn)難點(diǎn)章節(jié),名校尤愛考。如果作為重點(diǎn)來考,則多出現(xiàn)于分析與設(shè)計(jì)題型當(dāng)中,可與樹一章共同構(gòu)成算法設(shè)計(jì)大題的題型設(shè)計(jì)。
查找 :重點(diǎn)難點(diǎn)章節(jié),概念較多,聯(lián)系較為緊密,容易混淆。出題時(shí)可以作為分析型題目給出,在基本概念型題目中也較為常見。算法設(shè)計(jì)型題中可以數(shù)組結(jié)合來考查,也可以與樹一章結(jié)合來考查。
排序 :與查找一章類似,本章同屬于重點(diǎn)難點(diǎn)章節(jié),且概念更多,聯(lián)系更為緊密,概念之間更容易混淆。在基本概念的考查中,尤愛考各種排序算法的優(yōu)劣比較此類的題。算法設(shè)計(jì)大題中,如果作為出題,那么常與數(shù)組結(jié)合來考查。
二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點(diǎn)勾劃:
概述
本章主要起到總領(lǐng)作用,為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。大家主要注意以下幾點(diǎn):數(shù)據(jù)結(jié)構(gòu)的基本概念,時(shí)間和空間復(fù)雜度的概念及度量方法,算法設(shè)計(jì)時(shí)的注意事項(xiàng)。本章考點(diǎn)不多,只要稍加注意理解即可。
第一章 線性表
作為線性結(jié)構(gòu)的開篇章節(jié),線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中,其作用都是不可低估的。在這一章,第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯?chǔ)的概念,鏈?zhǔn)酱鎯?chǔ)概念將是整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重,無論哪一章都涉及到了這個(gè)概念。
總體來說,線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面:
1.線性表的相關(guān)基本概念,如:前驅(qū)、后繼、表長(zhǎng)、空表、首元結(jié)點(diǎn),頭結(jié)點(diǎn),頭指針等概念。
2.線性表的結(jié)構(gòu)特點(diǎn),主要是指:除第一及最后一個(gè)元素外,每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。
3.線性表的順序存儲(chǔ)方式及其在具體語言環(huán)境下的兩種不同實(shí)現(xiàn):表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。
4.線性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算:?jiǎn)捂湵?、循環(huán)鏈表,雙向鏈表,雙向循環(huán)鏈表。其中,單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。此外,近年來在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出(可能是順序也可能是倒序)的問題。
在鏈表的小題型中,經(jīng)??嫉揭恍┲T如:判表空的題。在不同的鏈表中,其判表空的方式是不一樣的,請(qǐng)大家注意。
5.線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下,其不同的優(yōu)缺點(diǎn)比較,即其各自適用的場(chǎng)合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。
第二章 棧與隊(duì)列
棧與隊(duì)列,是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎,很多人從這一章開始坐暈車,一直暈到現(xiàn)在。所以,理解棧與隊(duì)列,是走向DS高手的一條必由之路,。
學(xué)習(xí)此章前,你可以問一下自己是不是已經(jīng)知道了以下幾點(diǎn):
1.棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念,包括:順序棧,鏈棧,共享?xiàng)#h(huán)隊(duì)列,鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)(請(qǐng)注意包括:存和取兩部分)的特點(diǎn)。
2.遞歸算法。棧與遞歸的關(guān)系,以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法:n!階乘問題,fib數(shù)列問題,hanoi問題,背包問題,二叉樹的遞歸和非遞歸遍歷問題,圖的深度遍歷與棧的關(guān)系等。其中,涉及到樹與圖的問題,多半會(huì)在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。
3.棧的應(yīng)用:數(shù)值表達(dá)式的求解,括號(hào)的配對(duì)等的原理,只作原理性了解,具體要求考查此為題目的算法設(shè)計(jì)題不多。
4.循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件,循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。
如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌,棧與隊(duì)列一章可以不看書了。注意,我說的是可以不看書,并不是可以不作題哦。
2022考研初復(fù)試已經(jīng)接近尾聲,考研學(xué)子全面進(jìn)入2023屆備考,跨考為23考研的考生準(zhǔn)備了10大課包全程準(zhǔn)備、全年復(fù)習(xí)備考計(jì)劃、目標(biāo)院校專業(yè)輔導(dǎo)、全真復(fù)試模擬練習(xí)和全程針對(duì)性指導(dǎo);2023考研的小伙伴針也已經(jīng)開始擇校和復(fù)習(xí)了,跨考考研暢學(xué)5.0版本全新升級(jí),無論你在校在家都可以更自如的完成你的考研復(fù)習(xí),暑假集訓(xùn)營(yíng)帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識(shí)點(diǎn)入門;個(gè)性化制定備考方案,助你贏在起跑線,早出發(fā)一點(diǎn)離成功就更近一點(diǎn)!
考研院校專業(yè)選擇和考研復(fù)習(xí)計(jì)劃 | |||
2023備考學(xué)習(xí) | 2023線上線下隨時(shí)學(xué)習(xí) | 34所自劃線院??佳袕?fù)試分?jǐn)?shù)線匯總 | |
2022考研復(fù)試最全信息整理 | 全國(guó)各招生院校考研復(fù)試分?jǐn)?shù)線匯總 | ||
2023全日制封閉訓(xùn)練 | 全國(guó)各招生院??佳姓{(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分?jǐn)?shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學(xué)科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時(shí)間 | 高定班 | 標(biāo)準(zhǔn)班 | 課程介紹 | 咨詢 |
秋季集訓(xùn) | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對(duì)1+專業(yè)課定向輔導(dǎo)+協(xié)議加強(qiáng)課程(高定班)+專屬規(guī)劃答疑(高定班)+精細(xì)化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班) | |
2023集訓(xùn)暢學(xué) | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強(qiáng)化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對(duì)性一對(duì)一課程+班主任全程督學(xué)服務(wù)+全程規(guī)劃體系+全程測(cè)試體系+全程精細(xì)化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強(qiáng)課+初試專屬服務(wù)+復(fù)試全科標(biāo)準(zhǔn)班服務(wù) |