下面我們看一下圖這一章的主要考點以及這些考點的考查方式
考查有關圖的基本概念問題
這些概念是進行圖一章學習的基礎這一章的概念包括圖的定義和特點無向圖有向圖入度出度完全圖生成子圖路徑長度回路(強)連通圖(強)連通分量等概念與這些概念相聯系的相關計算題也應該掌握
考查圖的幾種存儲形式
圖的存儲形式包括鄰接矩陣(逆)鄰接表十字鏈表及鄰接多重表在考查時有的學校是給出一種存儲形式要求考生用算法或手寫出與給定的結構相對應的該圖的另一種存儲形式
考查圖的兩種遍歷算法深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法這兩個算法對圖一章的重要性等同於先序中序後序遍歷對於二叉樹一章的重要性在考查時圖一章的算法設計題常常是基於這兩種基本的遍歷算法而設計的比如求最長的最短路徑問題和判斷兩頂點間是否存在長為K的簡單路徑問題就分別用到了廣度遍歷和深度遍歷算法
生成樹最小生成樹的概念以及最小生成樹的構造PRIM算法和KRUSKAL算法
考查時一般不要求寫出算法源碼而是要求根據這兩種最小生成樹的算法思想寫出其構造過程及最終生成的最小生成樹
拓撲排序問題
拓撲排序有兩種方法一是無前趨的頂點優先算法二是無後繼的頂點優先算法換句話說一種是從前向後的排序一種是從後向前排當然後一種排序出來的結果是逆拓撲有序的
關鍵路徑問題
這個問題是圖一章的難點問題理解關鍵路徑的關鍵有三個方面一是何謂關鍵路徑二是最早時間是什麼意思如何求三是最晚時間是什麼意思如何求簡單地說最早時間是通過從前向後的方法求的而最晚時間是通過從後向前的方法求解的並且要想求最晚時間必須是在所有的最早時間都已經求出來之後才能進行這個問題拿來直接考算法源碼的不多一般是要求按照書上的算法描述求解的過程和步驟
在實際設計關鍵路徑的算法時還應該注意以下這一點采用鄰接表的存儲結構求最早時間和最晚時間要采用不同的處理方法即在算法初始時應該首先將所有頂點的最早時間全部置為關鍵路徑問題是工程進度控制的重要方法具有很強的實用性
最短路徑問題
與關鍵路徑問題並稱為圖一章的兩只攔路虎概念理解是比較容易的關鍵是算法的理解最短路徑問題分為兩種一是求從某一點出發到其余各點的最短路徑;二是求圖中每一對頂點之間的最短路徑這個問題也具有非常實用的背景特色一個典型的應該就是旅游景點及旅游路線的選擇問題解決第一個問題用DIJSKTRA算法解決第二個問題用FLOYD算法注意區分
第七章 查找
在不少數據結構的教材中是把查找與排序放入高級數據結構中的應該說查找和排序兩章是前面我們所學的知識的綜合運用用到了樹也用到了鏈表等知識對這些數據結構某一方面的運用就構成了查找和排序
現實生活中search幾乎無處不在特別是現在的網絡時代萬事離不開search小到文檔內文字的搜索大到INTERNET上的搜索search占據了我們上網的大部分時間
在復習這一章的知識時你需要先弄清楚以下幾個概念
關鍵字主關鍵字次關鍵字的含義;靜態查找與動態查找的含義及區別;平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果特別是一些典型結構的ASL值應該記住
在DS的教材中一般將search分為三類st在順序表上的查找;nd在樹表上的查找;rd在哈希表上的查找下面詳細介紹其考查知識點及考查方式
線性表上的查找
主要分為三種線性結構順序表有序順序表索引順序表對於第一種我們采用傳統查找方法逐個比較對於及有序順序表我們采用二分查找法對於第三種索引結構我們采用索引查找算法考生需要注意這三種表下的ASL值以及三種算法的實現其中二分查找還要特別注意適用條件以及其遞歸實現方法
樹表上的查找
這是本章的重點和難點由於這一節介紹的內容是使用樹表進行的查找所以很容易與樹一間的某些概念相混淆本節內容與樹一章的內容有聯系但也有很多不同應注意規納樹表主要分為以下幾種二叉排序樹平衡二叉樹B樹鍵樹其中尤以前兩種結構為重也有部分名校偏愛考B樹的由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹所以與二叉樹的聯系就更為緊密二叉樹一章學好了這裡也就不難了
二叉排序樹簡言之就是左小右大它的中序遍歷結果是一個遞增的有序序列平衡二叉樹是二叉排序樹的優化其本質也是一種二叉排序樹只不過平衡二叉樹對左右子樹的深度有了限定深度之差的絕對值不得大於對於二叉排序樹判斷某棵二叉樹是否二叉排序樹這一算法經常被考到可用遞歸也可以用非遞歸平衡二叉樹的建立也是一個常考點但該知識點歸根結底還是關注的平衡二叉樹的四種調整算法所以應該掌握平衡二叉樹的四種調整算法調整的一個參照是調整前後的中序遍歷結果相同
B樹是二叉排序樹的進一步改進也可以把B樹理解為三叉四叉排序樹除B樹的查找算法外應該特別注意一下B樹的插入和刪除算法因為這兩種算法涉及到B樹結點的分裂和合並是一個難點B樹是報考名校的同學應該關注的焦點之一
鍵樹也稱字符樹特別適用於查找英文單詞的場合一般不要求能完整描述算法源碼多是根據算法思想建立鍵樹及描述其大致查找過程
基本哈希表的查找算法
哈希一詞是外來詞譯自hash一詞意為散列或雜湊的意思哈希表查找的基本思想是根據當前待查找數據的特征以記錄關鍵字為自變量設計一個function該函數對關鍵字進行轉換後其解釋結果為待查的地址基於哈希表的考查點有哈希函數的設計沖突解決方法的選擇及沖突處理過程的描述
第八章 內部排序
內排是DS課程中最後一個重要的章節建立在此章之上的考題可以有多種類型填空選擇判斷乃至大型算法題但是歸結到一點就是考查你對書本上的各種排序算法及其思想以及其優缺點和性能指標(時間復雜度)能否了如指掌
這一章我們對重點的規納將跟以上各章不同我們將從以下幾個側面來對排序一章進行不同的規納以期能更全面的理解排序一章的總體結構及各種算法
從排序算法的種類來分本章主要闡述了以下幾種排序方法插入選擇交換歸並計數等五種排序方法
其中在插入排序中又可分為直接插入折半插入路插入希爾排序這幾種插入排序算法的最根本的不同點說到底就是根據什麼規則尋找新元素的插入點直接插入是依次尋找折半插入是折半尋找希爾排序是通過控制每次參與排序的數的總范圍由小到大的增量來實現排序效率提高的目的
交換排序又稱冒泡排序在交換排序的基礎上改進又可以得到快速排序快速排序的思想一語以敝之用中間數將待排數據組一分為二快速排序在處理的問題規模這個概念上與希爾有點相反快速排序是先處理一個較大規模然後逐漸把處理的規模降低最終達到排序的目的
選擇排序相對於前面幾種排序算法來說難度大一點具體來說它可以分為簡單選擇樹選擇堆排這三種方法的不同點是根據什麼規則選取最小的數簡單選擇是通過簡單的數組遍歷方案確定最小數;樹選擇是通過錦標賽類似的思想讓兩數相比不斷淘汰較大(小)者最終選出最小(大)數;而堆排序是利用堆這種數據結構的性質通過堆元素的刪除調整等一系列操作將最小數選出放在堆頂堆排序中的堆建立堆調整是重要考點樹選擇排序也曾經在一些學校中的大型算法題中出現請大家注意
歸並排序故名思義是通過歸並這種操作完成排序的目的既然是歸並就必須是兩者以上的數據集合才可能實現歸並所以在歸並排序中關注最多的就是路歸並算法思想比較簡單有一點要銘記在心歸並排序是穩定排序
基數排序是一種很特別的排序方法也正是由於它的特殊所以基數排序就比較適合於一些特別的場合比如撲克牌排序問題等基數排序又分為兩種多關鍵字的排序(撲克牌排序)鏈式排序(整數排序)基數排序的核心思想也是利用基數空間這個概念將問題規模規范變小並且在排序的過程中只要按照基排的思想是不用進行關鍵字比較的這樣得出的最終序列就是一個有序序列
本章各種排序算法的思想以及偽代碼實現及其時間復雜度都是必須掌握的學習時要多注意規納總結對比此外對於教材中的節要求必須熟記在理解的基礎上記憶這一節幾乎成為很多學校每年的必考點
[] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23998.html
