復(fù)習(xí)考試王位春

1、復(fù)習(xí)考試王位春wangwchpku目標(biāo)：4.0！優(yōu)異成績 良好心態(tài) (扎實的基礎(chǔ)知識 +良好的學(xué)習(xí)復(fù)習(xí)方法 +考場上的正常發(fā)揮)知識點（圖）一. 概念二. 方法及算法 1. 圖的存儲方法：（1） 相鄰矩陣（2） 鄰接表(結(jié)點表 - 邊表) 2. 圖的周游：（1） 深度優(yōu)先（2） 寬度優(yōu)先 3. 圖的生成樹與最小生成樹（1） 從某一點出發(fā)，按深度優(yōu)先或?qū)挾葍?yōu)先周游的生成樹（2） 最小生成樹 Prim算法 Kruskal算法(避圈法) 4. 拓撲排序 : 對于給定圖，找出若干個或所有拓撲序列 任何無環(huán)的有向圖，都可以拓撲排序。 5. 最短路徑 Dijkstra算法、Floyd算法(屬于動態(tài)規(guī)劃法)

2、 兩個算法的關(guān)鍵都在求Min的部分知識點（內(nèi)排序）二. 方法及算法 1. 重點排序算法：直接插入法、Shell排序、快速排序、基數(shù)排序、歸并排序 2. 算法分析 （1）基于比較次數(shù)和移位次數(shù)分析最好、最壞的時間、空間 直接插入法、二分法插入排序、起泡排序、直接選擇、快速排序、基數(shù)排序、歸并排序 （2） 記住各種排序方法的平均時間 3. 各種排序方法的局部修改和混合應(yīng)用知識點（文件管理和外排序、檢索）方法及算法 1. 置換選擇排序 2. 多路歸并 (敗者樹，最佳歸并樹，多路歸并的讀盤和寫盤次數(shù)) （不考第8章8.2.2節(jié)關(guān)于讀盤時間的計算）一. 概念 1. 平均檢索長度 2. 二分檢索 3. 散

3、列表、同義詞、碰撞、堆積二. 方法 1. 二分法檢索的判定樹、查找某個結(jié)點的比較次數(shù) 2. 散列表: 1) 散列函數(shù)的選擇(除余法、平方取中法、折疊法)2) 沖突處理方法(分離同義詞子表、線性探測、雙散列函數(shù)) 三. 散列算法（查找、插入、刪除，對墓碑的處理）不考9.2集合知識點（索引技術(shù)）一. 概念 1. 順序文件 2. 散列文件 3. 倒排文件 4. 靜態(tài)索引結(jié)構(gòu) 5.動態(tài)索引結(jié)構(gòu)(B樹)二. 方法（不考算法） 1. B樹、B+樹的插入與刪除(注意保持性質(zhì)，特別是等高；以及子 結(jié)點和關(guān)鍵碼個數(shù)的上下限制) 2. B樹/B+樹的讀盤和寫盤次數(shù)分析 3. B樹/B+樹的效率分析B樹中關(guān)鍵碼沒有重復(fù)，父結(jié)點中的關(guān)鍵碼是其子結(jié)點的分界；B+中最底層是關(guān)鍵碼的一個全集，往根的方向一層層復(fù)寫。 不考10.2.1多分樹，不考10.2.2ISAM和10.4.3VSAM。復(fù)習(xí)根據(jù)考試提綱制定計劃教材？講義？作業(yè)以前的試題？理解與記憶（關(guān)系到考試時解題的時間）我的方法：把自己覺得看過但不好記的知識點記到一張紙上，每次復(fù)習(xí)前都過一遍，考試前多看幾次動筆去寫代碼跟同學(xué)討論考試心態(tài)：我能！從以往的考試特別是期中考試得到了什么？考試時間分配解題順序