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

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

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

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