📄 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 + -