📄 2006级硕士研究生入学考试“数据结构”复习提要.htm
字号:
<P class=MsoNormal
style="MARGIN-RIGHT: -2.65pt; mso-pagination: widow-orphan"><SPAN
lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>1. 串<SPAN
style="mso-spacerun: yes"> </SPAN>2. 模式匹配</SPAN></P></FONT>
<P align=justify><FONT face=宋体 color=#008080 size=4>二. 方法</FONT></P><FONT
face=宋体 size=3>
<P class=MsoNormal
style="MARGIN-RIGHT: -2.65pt; mso-pagination: widow-orphan"><SPAN
lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>1.
串的基本操作</SPAN></P>
<P class=MsoNormal
style="MARGIN-RIGHT: -2.65pt; mso-pagination: widow-orphan"><SPAN
lang=EN-US><SPAN style="mso-spacerun: yes"> </SPAN>2.
串的存储</SPAN></P>
<P class=MsoNormal
style="MARGIN-RIGHT: -2.65pt; mso-pagination: widow-orphan"><FONT
color=#008000>★ 3.
串的KMP快速模式匹配算法(next数组)，求特征next数组（N数组）和利用next数组完成匹配的方法</FONT></P>
<P class=MsoNormal
style="MARGIN-RIGHT: -2.65pt; mso-pagination: widow-orphan"> </P></FONT><FONT
face=宋体 color=#000080 size=5>
<P align=justify>第</FONT><FONT color=#000080 size=5>4</FONT><FONT face=宋体
color=#000080 size=5>章</FONT><FONT color=#000080 size=5> </FONT><FONT face=宋体
color=#000080 size=5>二叉树</FONT><FONT face=宋体 color=#008080
size=4>（教材中本章作者为</FONT><FONT face=宋体 color=#000080 size=5>杨冬青</FONT><FONT
face=宋体 color=#008080 size=4>）</P>
<P align=justify>一</FONT><FONT color=#008080 size=4>. </FONT><FONT face=宋体
color=#008080 size=4>概念</FONT><FONT size=3></P>
<P align=justify> 1. </FONT><FONT face=宋体
size=3>二叉树</FONT><FONT size=3> 2.</FONT><FONT face=宋体
size=3>二叉树的前序、中序、后序周游</FONT><FONT size=3> 3. </FONT><FONT face=宋体
size=3>二叉排序树</FONT><FONT size=3> 4. </FONT><FONT face=宋体 size=3>穿线树</FONT><FONT
size=3>(</FONT><FONT face=宋体 size=3>中序、前序、后序</FONT><FONT size=3>) 5.
Huffman</FONT><FONT face=宋体 size=3>树、</FONT><FONT size=3>Huffman</FONT><FONT
face=宋体 size=3>编码</FONT><FONT size=3> 6. </FONT><FONT face=宋体 size=3>堆、堆排序</P>
<P align=justify>二</FONT><FONT size=3>. </FONT><FONT face=宋体
size=3>方法</FONT><FONT size=3></P>
<P align=justify> 1</FONT><FONT
face=宋体 size=3>．二叉树的链式存储</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3> （</FONT><FONT
size=3>1</FONT><FONT face=宋体 size=3>）二叉链表</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3> （</FONT><FONT
size=3>2</FONT><FONT face=宋体 size=3>）带父指针的三重链表</FONT><FONT size=3></P>
<P align=justify> 2. </FONT><FONT
face=宋体 size=3>二叉树的顺序存储</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3>
完全二叉树的顺序存储</FONT><FONT face=宋体 color=#008000></P>
<P align=justify> ★</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><FONT size=3>(</FONT><FONT face=宋体 size=3>结合应用</FONT><FONT
size=3>，例如穿线树，或把快速排序转换成非递归形式)</P></FONT><FONT color=#008000>
<P align=justify> 4. </FONT><FONT
face=宋体 color=#008000>二叉检索树的插入与删除</FONT><FONT size=3></P>
<P align=justify> 5. </FONT><FONT
face=宋体 size=3>构造</FONT><FONT size=3>Huffman</FONT><FONT face=宋体
size=3>树，利用</FONT><FONT size=3>Huffman</FONT><FONT face=宋体
size=3>树进行编码、解码</FONT><FONT size=3></P>
<P align=justify> 6. </FONT><FONT
face=宋体 size=3>堆排序的建堆过程</FONT></P>
<P align=justify><FONT face=宋体 color=#000080 size=5> </P>
<P align=justify>第</FONT><FONT color=#000080 size=5>5</FONT><FONT face=宋体
color=#000080 size=5>章</FONT><FONT color=#000080 size=5> </FONT><FONT face=宋体
color=#000080 size=5>树</FONT><FONT face=宋体 color=#008080
size=4>（教材中本章作者为</FONT><FONT face=宋体 color=#000080 size=5>杨冬青</FONT><FONT
face=宋体 color=#008080 size=4>）</P>
<P align=justify>一</FONT><FONT color=#008080 size=4>. </FONT><FONT face=宋体
color=#008080 size=4>概念</FONT><FONT size=3></P>
<P align=justify> 1. </FONT><FONT
face=宋体 size=3>树、森林</FONT><FONT size=3> </FONT><FONT face=宋体 color=#008000
size=4>2. 树、森林的先根周游、后根周游、层次周游</FONT><FONT face=宋体 color=#008080 size=4></P>
<P align=justify>二</FONT><FONT color=#008080 size=4>. </FONT><FONT face=宋体
color=#008080 size=4>方法</FONT><FONT size=3></P>
<P align=justify></FONT><FONT color=#008000 size=3> </FONT><FONT
color=#008000><FONT size=4> 1. </FONT><FONT face=宋体
size=4>树林与二叉树相互转换</FONT></FONT><FONT size=3></P>
<P align=justify> 2</FONT><FONT face=宋体
size=3>．森林的链式存储</FONT><FONT size=3></P>
<P align=justify></FONT><FONT color=#008000><FONT
size=4> (1)
</FONT><FONT face=宋体 size=4>转换为相应的二叉树，用二叉链表表示</FONT></FONT><FONT size=4></P>
<P align=justify></FONT><FONT size=3>
(2) </FONT><FONT face=宋体
size=3>父指针表示法</FONT><FONT size=3></P>
<P align=justify>
(3) </FONT><FONT face=宋体
size=3>子结点表表示法</FONT></P><FONT size=3>
<P align=justify> </FONT><FONT
color=#008000>3. 森林的顺序存储</FONT></P>
<P align=justify><FONT face=宋体
size=3> 不必死记各种顺序存储方法，要了解原理。其本质是按照周游的性质，把顺序存储的森林信息反构造成森林（在内存中往往用二叉树来表示）</FONT><FONT
size=3></P>
<P align=justify> 4. </FONT><FONT face=宋体
size=3>二叉树和森林的层次周游</FONT><FONT size=3>(</FONT><FONT face=宋体
size=3>用队列</FONT><FONT size=3>)</FONT><FONT face=宋体 size=3>，可能结合应用</FONT></P>
<P align=justify><FONT face=宋体 color=#000080 size=5> </P>
<P align=justify>第</FONT><FONT color=#000080 size=5>6</FONT><FONT face=宋体
color=#000080 size=5>章</FONT><FONT color=#000080 size=5> </FONT><FONT face=宋体
color=#000080 size=5>图</FONT><FONT face=宋体 color=#008080
size=4>（教材中本章作者为</FONT><FONT face=宋体 color=#000080 size=5>杨冬青</FONT><FONT
face=宋体 color=#008080 size=4>）</P>
<P align=justify>一</FONT><FONT color=#008080 size=4>. </FONT><FONT face=宋体
color=#008080 size=4>概念</FONT><FONT size=3></P>
<P align=justify> 1. </FONT><FONT face=宋体
size=3>图的深度周游</FONT><FONT size=3> 2. </FONT><FONT face=宋体
size=3>图的宽度周游</FONT><FONT size=3> 3. </FONT><FONT face=宋体
size=3>图的生成树、生成树林、最小生成树</FONT><FONT size=3> </FONT><FONT face=宋体
size=3>（不要求掌握关键路径）</FONT><FONT face=宋体 color=#008080 size=4></P>
<P align=justify>二</FONT><FONT color=#008080 size=4>. </FONT><FONT face=宋体
color=#008080 size=4>方法</FONT><FONT face=宋体 color=#008000></P>
<P align=justify> ★</FONT><FONT color=#008000>1. </FONT><FONT
face=宋体 color=#008000>图的存储方法</FONT><FONT color=#008000></P>
<P align=justify></FONT><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><FONT size=3> </P>
<P align=justify> 2. </FONT><FONT face=宋体
color=#008000>图的周游</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3> （</FONT><FONT size=3>1</FONT><FONT
face=宋体 size=3>）</FONT><FONT size=3> </FONT><FONT face=宋体
size=3>深度优先</FONT><FONT size=3> </FONT><FONT face=宋体 size=3>（</FONT><FONT
size=3>2</FONT><FONT face=宋体 size=3>）</FONT><FONT size=3> </FONT><FONT face=宋体
size=3>宽度优先</FONT><FONT size=3></P>
<P align=justify> 3. </FONT><FONT face=宋体
size=3>图的生成树与最小生成树</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3> （</FONT><FONT size=3>1</FONT><FONT
face=宋体 size=3>）</FONT><FONT size=3> </FONT><FONT face=宋体
size=3>从某一点出发，按深度优先或宽度优先周游的生成树</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3> （</FONT><FONT size=3>2</FONT><FONT
face=宋体 size=3>）</FONT><FONT size=3> </FONT><FONT face=宋体
size=3>最小生成树</FONT><FONT size=3> </FONT><FONT face=宋体 size=3>①</FONT><FONT
size=3> Prim</FONT><FONT face=宋体 size=3>算法</FONT><FONT size=3> </FONT><FONT
face=宋体 size=3>②</FONT><FONT size=3> Kruskal</FONT><FONT face=宋体
size=3>算法</FONT><FONT size=3>(</FONT><FONT face=宋体 size=3>避圈法</FONT><FONT
size=3>)</P>
<P align=justify> 4. </FONT><FONT face=宋体
size=3>拓扑排序</FONT><FONT size=3> : </FONT><FONT face=宋体
size=3>对于给定图，找出若干个或所有拓扑序列</FONT><FONT size=3></P>
<P align=justify></FONT><FONT face=宋体
size=3> 任何无环的有向图，都可以拓扑排序。</FONT><FONT
size=3> </P>
<P align=justify> 5. </FONT><FONT face=宋体
size=3>最短路径</FONT><FONT size=3></P>
<P align=justify> Dijkstra</FONT><FONT
face=宋体 size=3>算法、</FONT><FONT size=3>Floyd</FONT><FONT face=宋体
size=3>算法</FONT><FONT size=3>(</FONT><FONT face=宋体
size=3>这两个算法都属于贪心法，也属于动态规划法</FONT><FONT size=3>) </FONT><FONT face=宋体
color=#008000>★ 两个算法的关键都在求Min的部分</FONT></P>
<P align=justify><FONT face=宋体 color=#008000> </FONT><FONT face=宋体
size=3> 6. </FONT><FONT color=#ff0000
size=3>贪心法</FONT></P><FONT face=宋体 size=3>
<P align=justify> </P></FONT><FONT face=宋体 color=#000080 size=5>
<P align=justify>★第</FONT><FONT color=#000080 size=5>7</FONT><FONT face=宋体
color=#000080 size=5>章</FONT><FONT color=#000080 size=5> </FONT><FONT face=宋体
color=#000080 size=5>内排序</FONT><FONT face=宋体 color=#008080
size=4>（教材中本章作者为</FONT><FONT face=宋体 color=#000080 size=5>张铭</FONT><FONT face=宋体
color=#008080 size=4>）</P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -