?? midtermreview.htm
字號:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>復習大綱 </title><meta name="GENERATOR" content="Microsoft FrontPage 4.0"></head><body><p><font FACE="宋體" COLOR="#000080" size="7"> </p><p ALIGN="JUSTIFY"></font><font FACE="宋體" COLOR="#ff00ff" size="7"> </p><p ALIGN="JUSTIFY">不考第</font><font COLOR="#ff00ff" size="7">2</font><fontFACE="宋體" COLOR="#ff00ff" size="7">章。其他各章節以下面的內容為復習重點。尤其是</font><fontFACE="宋體" COLOR="#008000" size="7">綠顏色文字</font><font FACE="宋體"COLOR="#ff00ff" size="7">或</font><font FACE="宋體" COLOR="#008000" size="7">★</font><fontFACE="宋體" COLOR="#ff00ff" size="7">標出部分為重中之重</font><fontFACE="宋體" color="#FF00FF" size="7">。</font><font FACE="宋體" COLOR="#000080"size="7"></p><p ALIGN="JUSTIFY"> </p><p ALIGN="JUSTIFY">第</font><font COLOR="#000080" size="7">1</font><fontFACE="宋體" COLOR="#000080" size="7">章</font><font COLOR="#000080" size="7"> </font><fontFACE="宋體" COLOR="#000080" size="7">及</font><font COLOR="#000080" size="7"> </font><fontFACE="宋體" COLOR="#000080" size="7">第</font><font COLOR="#000080" size="7">3</font><fontFACE="宋體" COLOR="#000080" size="7">章</font><fontFACE="宋體" COLOR="#008080" size="7"></p><p ALIGN="JUSTIFY">一</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">重要概念</font><font COLOR="#008000"></p> <p ALIGN="JUSTIFY"><big><big><big> 1. </font><font FACE="宋體" COLOR="#008000">數據類型</font><font COLOR="#008000"> 2. </font><font FACE="宋體" COLOR="#008000">抽象數據結構</font><font COLOR="#008000"> 3. </font><font FACE="宋體" COLOR="#008000">數據結構</font><font COLOR="#008000"> 4. </font><font FACE="宋體" COLOR="#008000">存儲結構</font><font COLOR="#008000"> 5. </font><font FACE="宋體" COLOR="#008000">算法</font><font COLOR="#008000"> 6. </font><font FACE="宋體" COLOR="#008000">算法度量</font><font COLOR="#008000">(</font><font FACE="宋體" COLOR="#008000">時間代價、空間代價</font><font COLOR="#008000">)</font></big></big></big><font FACE="宋體" COLOR="#008080" size="7"></p> <p ALIGN="JUSTIFY">二</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">方法</font><font size="6"></p> <p ALIGN="JUSTIFY"> 1. <font FACE="宋體">根據二元組畫出圖示邏輯結構</font>(<font FACE="宋體">注意邊的方向</font>)</p> <p ALIGN="JUSTIFY"> 2. <font FACE="宋體">算法度量的大</font>O<font FACE="宋體">表示法的簡化法則（不要求掌握大Ω、大Θ表示法）</p> <p ALIGN="JUSTIFY"></font></font><font FACE="宋體" COLOR="#000080" size="7"> </p><p ALIGN="JUSTIFY">第</font><font COLOR="#000080" size="7">4</font><font FACE="宋體"COLOR="#000080" size="7">章</font><font COLOR="#000080" size="7"> </font><fontFACE="宋體" COLOR="#000080" size="7">線性表</font><font FACE="宋體" COLOR="#008080"size="7"></p><p ALIGN="JUSTIFY">一</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">概念</font><font size="6"></p> <p ALIGN="JUSTIFY"> 1. <font FACE="宋體">線性表</font> 2. <font FACE="宋體">單鏈表</font> 3. <font FACE="宋體">雙鏈表</font> 4. <font FACE="宋體">循環表</font> 5. <font FACE="宋體">棧</font> 6. <font FACE="宋體">隊列</font> 7. <font FACE="宋體">循環隊列</font></font><font FACE="宋體" COLOR="#008080" size="7"></p> <p ALIGN="JUSTIFY">二</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">方法</font><font size="6"></p> <p ALIGN="JUSTIFY"> 1. <font FACE="宋體">線性表的運算</font>(<font FACE="宋體">指針操作的正確性</font>)</p> <p ALIGN="JUSTIFY"> 2. <font FACE="宋體">表達式求值</font>(<font FACE="宋體">表達式二叉樹、后綴表達式</font>)</font><font FACE="宋體" COLOR="#008000"></p> <p ALIGN="JUSTIFY"><big><big><big> ★</font><font COLOR="#008000"> 3. </font><font FACE="宋體" COLOR="#008000">棧的性質，用棧來生成序列</font></big></big></big><font FACE="宋體" size="6"></p> <p ALIGN="JUSTIFY"></font><font FACE="宋體" COLOR="#000080" size="7"> </p><p ALIGN="JUSTIFY">第</font><font COLOR="#000080" size="7">5</font><font FACE="宋體"COLOR="#000080" size="7">章</font><font COLOR="#000080" size="7"> </font><fontFACE="宋體" COLOR="#000080" size="7">二叉樹</font><font FACE="宋體" COLOR="#008080"size="7"></p><p ALIGN="JUSTIFY">一</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">概念</font><font size="6"></p> <p ALIGN="JUSTIFY"> 1. <font FACE="宋體">二叉樹</font> 2.<font FACE="宋體">二叉樹的前序、中序、后序周游</font> 3. <font FACE="宋體">二叉排序樹</font> 4. <font FACE="宋體">穿線樹</font>(<font FACE="宋體">中序、前序、后序</font>) 5. Huffman<font FACE="宋體">樹、</font>Huffman<font FACE="宋體">編碼</font> 6. <font FACE="宋體">堆、堆排序</p> <p ALIGN="JUSTIFY">二</font>. <font FACE="宋體">方法</font></p> <p ALIGN="JUSTIFY"> 1<font FACE="宋體">．二叉樹的鏈式存儲</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> （</font>1<font FACE="宋體">）二叉鏈表</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> （</font>2<font FACE="宋體">）帶父指針的三重鏈表</font></p> <p ALIGN="JUSTIFY"> 2. <font FACE="宋體">二叉樹的順序存儲</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> 完全二叉樹的順序存儲</font></font><font FACE="宋體" COLOR="#008000"></p> <p ALIGN="JUSTIFY"><big><big><big> ★</font><font COLOR="#008000">3. </font><font FACE="宋體" COLOR="#008000">使用棧</font><font COLOR="#008000">(</font><font FACE="宋體" COLOR="#008000">前、中、后序</font><font COLOR="#008000">)</font><font FACE="宋體" COLOR="#008000">周游二叉樹(注意，不要使用帶GOTO語句的機械消除遞歸的方法)、使用隊列層次地周游二叉樹，在周游過程中尋找某個結點或進行某種操作</font><font COLOR="#008000"> </font></big></big></big><font size="6">(<font FACE="宋體">結合應用</font>，例如穿線樹，或把遞歸轉換成非遞歸形式)</p> </font><font COLOR="#008000"> <p ALIGN="JUSTIFY"><big><big><big> 4. </font><font FACE="宋體" COLOR="#008000">二叉檢索樹的插入與刪除</font></big></big></big><font size="6"></p> <p ALIGN="JUSTIFY"> 5. <font FACE="宋體">構造</font>Huffman<font FACE="宋體">樹，利用</font>Huffman<font FACE="宋體">樹進行編碼、解碼</font></p> <p ALIGN="JUSTIFY"> 6. <font FACE="宋體">堆排序的建堆過程，</p> <p ALIGN="JUSTIFY"></font></font><font FACE="宋體" COLOR="#000080" size="7"> </p><p ALIGN="JUSTIFY">第</font><font COLOR="#000080" size="7">6</font><font FACE="宋體"COLOR="#000080" size="7">章</font><font COLOR="#000080" size="7"> </font><fontFACE="宋體" COLOR="#000080" size="7">樹</font><font FACE="宋體" COLOR="#008080"size="7"></p><p ALIGN="JUSTIFY">一</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">概念</font><font size="6"></p> <p ALIGN="JUSTIFY"> 1. <font FACE="宋體">樹、森林</font> 2. <font FACE="宋體">樹的先根周游、后根周游、層次周游</font></font><font FACE="宋體" COLOR="#008080" size="7"></p> <p ALIGN="JUSTIFY">二</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">方法</font><font size="6"></p> <p ALIGN="JUSTIFY"></font><font color="#008000" size="6"> </font><font size="7" color="#008000"> 1. </font><font FACE="宋體" color="#008000" size="7">樹林與二叉樹相互轉換</font><font size="6"></p> <p ALIGN="JUSTIFY"> 2<font FACE="宋體">．森林的鏈式存儲</font></p> <p ALIGN="JUSTIFY"></font><font size="7" color="#008000"> </font><font color="#008000"><font size="7"> </font><font face="宋體" size="6">(1) 轉換為相應的二叉樹，用二叉鏈表表示</font></font><font size="7"></p> <p ALIGN="JUSTIFY"></font><font size="6"> (2) <font FACE="宋體">父指針表示法</font></p> <p ALIGN="JUSTIFY"> (3) <font FACE="宋體">子結點表表示法</font></p> <p ALIGN="JUSTIFY"> 3. <font FACE="宋體">森林的順序存儲</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> 不必死記各種順序存儲方法，要了解原理。其本質是按照周游的性質，把順序存儲的森林信息反構造成森林（在內存中往往用二叉樹來表示）</font></p> <p ALIGN="JUSTIFY"> 4. <font FACE="宋體">二叉樹和森林的層次周游</font>(<font FACE="宋體">用隊列</font>)<font FACE="宋體">，可能結合應用</font></p> <p ALIGN="JUSTIFY"></font><font FACE="宋體" COLOR="#000080" size="7"> </p><p ALIGN="JUSTIFY">第</font><font COLOR="#000080" size="7">7</font><font FACE="宋體"COLOR="#000080" size="7">章</font><font COLOR="#000080" size="7"> </font><fontFACE="宋體" COLOR="#000080" size="7">圖</font><font FACE="宋體" COLOR="#008080"size="7"></p><p ALIGN="JUSTIFY">一</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">概念</font><font size="6"></p> <p ALIGN="JUSTIFY"> 1. <font FACE="宋體">圖的深度周游</font> 2. <font FACE="宋體">圖的寬度周游</font> 3. <font FACE="宋體">圖的生成樹、生成樹林、最小生成樹</font> <font FACE="宋體">（不要求掌握關鍵路徑）</font></font><font FACE="宋體" COLOR="#008080" size="7"></p> <p ALIGN="JUSTIFY">二</font><font COLOR="#008080" size="7">. </font><font FACE="宋體" COLOR="#008080" size="7">方法</font><font FACE="宋體" COLOR="#008000"></p> <p ALIGN="JUSTIFY"><big><big><big> ★</font><font COLOR="#008000">1. </font><font FACE="宋體" COLOR="#008000">圖的存儲方法</font></big></big></big><font COLOR="#008000"></p> <p ALIGN="JUSTIFY"></font><big><big><big><font FACE="宋體" COLOR="#008000"> （</font><font COLOR="#008000">1</font><font FACE="宋體" COLOR="#008000">）</font><font COLOR="#008000"> </font><font FACE="宋體" COLOR="#008000">相鄰矩陣</font><font COLOR="#008000"> </font><font FACE="宋體" COLOR="#008000">（</font><font COLOR="#008000">2</font><font FACE="宋體" COLOR="#008000">）</font><font COLOR="#008000"> </font><font FACE="宋體" COLOR="#008000">鄰接表</font><font COLOR="#008000">(</font><font FACE="宋體" COLOR="#008000">結點表</font><font COLOR="#008000"> -- </font><font FACE="宋體" COLOR="#008000">邊表</font><font COLOR="#008000">)</font></big></big></big><font size="6"> </p> <p ALIGN="JUSTIFY"> 2. <font FACE="宋體">圖的周游</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> （</font>1<font FACE="宋體">）</font> <font FACE="宋體">深度優先</font> <font FACE="宋體">（</font>2<font FACE="宋體">）</font> <font FACE="宋體">寬度優先</font></p> <p ALIGN="JUSTIFY"> 3. <font FACE="宋體">圖的生成樹與最小生成樹</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> （</font>1<font FACE="宋體">）</font> <font FACE="宋體">從某一點出發，按深度優先或寬度優先周游的生成樹</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> （</font>2<font FACE="宋體">）</font> <font FACE="宋體">最小生成樹</font> <font FACE="宋體">①</font> Prim<font FACE="宋體">算法</font> <font FACE="宋體">②</font> Kruskal<font FACE="宋體">算法</font>(<font FACE="宋體">避圈法</font>)</p> <p ALIGN="JUSTIFY"> 4. <font FACE="宋體">拓撲排序</font> : <font FACE="宋體">對于給定圖，找出若干個或所有拓撲序列</font></p> <p ALIGN="JUSTIFY"><font FACE="宋體"> 任何無環的有向圖，都可以拓撲排序。</font> </p> <p ALIGN="JUSTIFY"> 5. <font FACE="宋體">最短路徑</font></p> <p ALIGN="JUSTIFY"> Dijkstra<font FACE="宋體">算法、</font>Floyd<font FACE="宋體">算法</font>(<font FACE="宋體">屬于動態規劃法</font>) <font FACE="宋體">★</font> <font FACE="宋體">兩個算法的關鍵都在求</font>Min<font FACE="宋體">的部分 </font></p> </font> </body> </html> ?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -