一數據結構的章節結構及重點構成
數據結構學科的章節劃分基本上為概論線性表棧和隊列串多維數組和廣義表樹和二叉樹圖查找內排外排文件動態存儲分配
對於絕大多數的學校而言外排文件動態存儲分配三章基本上是不考的在大多數高校的計算機本科教學過程中這三章也是基本上不作講授的所以大家在這三章上可以不必花費過多的精力只要知道基本的概念即可但是對於報考名校特別是該校又有在試卷中對這三章進行過考核的歷史那麼這部分朋友就要留意這三章了
按照以上我們給出的章節以及對後三章的介紹數據結構的章節比重大致為
概論內容很少概念簡單分數大多只有幾分有的學校甚至不考
線性表基礎章節必考內容之一考題多數為基本概念題名校考題中鮮有大型算法設計題如果有也是與其它章節內容相結合
棧和隊列基礎章節容易出基本概念題必考內容之一而棧常與其它章節配合考查也常與遞歸等概念相聯系進行考查
串 基礎章節概念較為簡單專門針對於此章的大型算法設計題很少較常見的是根據KMP進行算法分析
多維數組及廣義表 基礎章節基於數組的算法題也是常見的分數比例波動較大是出題的可選單元或侯補單元一般如果要出題多數不會作為大題出數組常與查找排序等章節結合來作為大題考查
樹和二叉樹 重點難點章節各校必考章節各校在此章出題的不同之處在於是否在本章中出一到兩道大的算法設計題通過對多所學校的試卷分析絕大多數學校在本章都曾有過出大型算法設計題的歷史
圖 重點難點章節名校尤愛考如果作為重點來考則多出現於分析與設計題型當中可與樹一章共同構成算法設計大題的題型設計
查找 重點難點章節概念較多聯系較為緊密容易混淆出題時可以作為分析型題目給出在基本概念型題目中也較為常見算法設計型題中可以數組結合來考查也可以與樹一章結合來考查
排序 與查找一章類似本章同屬於重點難點章節且概念更多聯系更為緊密概念之間更容易混淆在基本概念的考查中尤愛考各種排序算法的優劣比較此類的題算法設計大題中如果作為出題那麼常與數組結合來考查
二數據結構各章節重點勾劃
第章 概述
本章主要起到總領作用為讀者進行數據結構的學習進行了一些先期鋪墊大家主要注意以下幾點數據結構的基本概念時間和空間復雜度的概念及度量方法算法設計時的注意事項本章考點不多只要稍加注意理解即可
第一章 線性表
作為線性結構的開篇章節線性表一章在線性結構的學習乃至整個數據結構學科的學習中其作用都是不可低估的在這一章第一次系統性地引入鏈式存儲的概念鏈式存儲概念將是整個數據結構學科的重中之重無論哪一章都涉及到了這個概念
總體來說線性表一章可供考查的重要考點有以下幾個方面
線性表的相關基本概念如前驅後繼表長空表首元結點頭結點頭指針等概念
線性表的結構特點主要是指除第一及最後一個元素外每個結點都只有一個前趨和只有一個後繼
線性表的順序存儲方式及其在具體語言環境下的兩種不同實現表空間的靜態分配和動態分配靜態鏈表與順序表的相似及不同之處
線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算單鏈表循環鏈表雙向鏈表雙向循環鏈表其中單鏈表的歸並算法循環鏈表的歸並算法雙向鏈表及雙向循環鏈表的插入和刪除算法等都是較為常見的考查方式此外近年來在不少學校中還多次出現要求用遞歸算法實現單鏈表輸出(可能是順序也可能是倒序)的問題
在鏈表的小題型中經常考到一些諸如判表空的題在不同的鏈表中其判表空的方式是不一樣的請大家注意
線性表的順序存儲及鏈式存儲情況下其不同的優缺點比較即其各自適用的場合單鏈表中設置頭指針循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處
第二章 棧與隊列
棧與隊列是很多學習DS的同學遇到第一只攔路虎很多人從這一章開始坐暈車一直暈到現在所以理解棧與隊列是走向DS高手的一條必由之路
學習此章前你可以問一下自己是不是已經知道了以下幾點
棧隊列的定義及其相關數據結構的概念包括順序棧鏈棧共享棧循環隊列鏈隊等棧與隊列存取數據(請注意包括存和取兩部分)的特點
遞歸算法棧與遞歸的關系以及借助棧將遞歸轉向於非遞歸的經典算法n!階乘問題fib數列問題hanoi問題背包問題二叉樹的遞歸和非遞歸遍歷問題圖的深度遍歷與棧的關系等其中涉及到樹與圖的問題多半會在樹與圖的相關章節中進行考查
棧的應用數值表達式的求解括號的配對等的原理只作原理性了解具體要求考查此為題目的算法設計題不多
循環隊列中判隊空隊滿條件循環隊列中入隊與出隊算法
如果你已經對上面的幾點了如指掌棧與隊列一章可以不看書了注意我說的是可以不看書並不是可以不作題哦
第三章 串
經歷了棧一章的痛苦煎熬後終於迎來了串一章的柳暗花明
串在概念上是比較少的一個章節也是最容易自學的章節之一但正如每個過來人所了解的KMP算法是這一章的重要關隘突破此關隘後走過去又是一馬平川的大好DS山河了呵呵
串一章需要攻破的主要堡壘有
串的基本概念串與線性表的關系(串是其元素均為字符型數據的特殊線性表)空串與空格串的區別串相等的條件
串的基本操作以及這些基本函數的使用包括取子串串連接串替換求串長等等運用串的基本操作去完成特定的算法是很多學校在基本操作上的考查重點
順序串與鏈串及塊鏈串的區別和聯系實現方式
KMP算法思想KMP中next數組以及nextval數組的求法明確傳統模式匹配算法的不足明確next數組需要改進之外其中理解算法是核心會求數組是得分點不用我多說這一節內容是本章的重中之重可能進行的考查方式是求next和nextval數組值根據求得的next或nextval數組值給出運用KMP算法進行匹配的匹配過程
第四章 數組與廣義表
學過程序語言的朋友數組的概念我們已經不是第一次見到了應該已經一回生二回熟了所以在概念上不會存在太大障礙但作為考研課程來說本章的考查重點可能與大學裡的程序語言所關注的不太一樣下面會作介紹
廣義表的概念是數據結構裡第一次出現的它是線性表或表元素的有限序列構成該結構的每個子表或元素也是線性結構的所以這一章也歸入線性結構中
本章的考查重點有
多維數組中某數組元素的position求解一般是給出數組元素的首元素地址和每個元素占用的地址空間並組給出多維數組的維數然後要求你求出該數組中的某個元素所在的位置
明確按行存儲和按列存儲的區別和聯系並能夠按照這兩種不同的存儲方式求解中類型的題
將特殊矩陣中的元素按相應的換算方式存入數組中這些矩陣包括對稱矩陣三角矩陣具有某種特點的稀疏矩陣等熟悉稀疏矩陣的三種不同存儲方式三元組帶輔助行向量的二元組十字鏈表存儲掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法
廣義表的概念特別應該明確表頭與表尾的定義這一點是理解整個廣義表一節算法的基礎近來在一些學校中出現了這樣一種題目類型給出對某個廣義表L若干個求了若干次的取頭和取尾操作後的串值要求求出原廣義表L大家要留意
與廣義表有關的遞歸算法由於廣義表的定義就是遞歸的所以與廣義表有關的算法也常是遞歸形式的比如求表深度復制廣義表等這種題目可以根據不同角度廣義表的表現形式運用兩種不同的方式解答一是把一個廣義表看作是表頭和表尾兩部分分別對表頭和表尾進行操作;二是把一個廣義表看作是若干個子表分別對每個子表進行操作
第五章 樹與二叉樹
從對線性結構的研究過度到對樹形結構的研究是數據結構課程學習的一次躍變此次躍變完成的好壞將直接關系到你到實際的考試中是否可以拿到高分而這所有的一切將最終影響你的專業課總分所以樹這一章的重要性已經不說自明了
總體來說樹一章的知識點包括
二叉樹的概念性質和存儲結構二叉樹遍歷的三種算法(遞歸與非遞歸)在三種基本遍歷算法的基礎上實現二叉樹的其它算法線索二叉樹的概念和線索化算法以及線索化後的查找算法最優二叉樹的概念構成和應用樹的概念和存儲形式樹與森林的遍歷算法及其與二叉樹遍歷算法的聯系樹與森林和二叉樹的轉換
[] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/24000.html
