📄 2006级硕士研究生入学考试“数据结构”复习提要.htm
字号:
<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>Shell</FONT><FONT face=宋体
size=3>排序、</FONT><FONT face=宋体 color=#008000>★快速排序、基数排序、归并排序</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 size=3>1</FONT><FONT
face=宋体 size=3>）基于</FONT><FONT face=宋体 color=#008000>比较次数</FONT><FONT face=宋体
size=3>和</FONT><FONT face=宋体 color=#008000>移位次数</FONT><FONT face=宋体
size=3>（一个移位就是一次纪录赋值操作，例如一次 swap 交换是3次移位），分析</FONT><FONT face=宋体
color=#008000>最好</FONT><FONT face=宋体 size=3>、</FONT><FONT face=宋体
color=#008000>最坏</FONT><FONT face=宋体 size=3>的时间、空间</P></FONT><FONT size=3>
<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></P>
<P align=justify> 3. </FONT><FONT face=宋体
size=3>各种排序方法的</FONT><FONT face=宋体 color=#008000>局部修改</FONT><FONT face=宋体
size=3>和</FONT><FONT face=宋体 color=#008000>混合应用</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>8</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>概念</P></FONT>
<P align=justify><FONT face=宋体 color=#000000 size=3> 1.
顺序文件 2. 散列文件 3. 倒排文件</FONT></P><FONT face=宋体 color=#008080 size=4>
<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></P>
<P align=justify><FONT face=宋体 color=#ff0000> 2.
赢者树、败者树</FONT></P>
<P align=justify><FONT face=宋体 color=#ff0000> 3.
多路归并 </FONT><FONT face=宋体 size=3></P>
<P align=justify> </P></FONT><FONT face=宋体 color=#000080 size=5>
<P align=justify>第</FONT><FONT color=#000080 size=5>9</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> </FONT><FONT face=宋体 size=3></P>
<P align=justify></FONT><FONT face=宋体 color=#008040 size=4> ★</FONT><FONT
color=#008040 size=4>3. </FONT><FONT face=宋体 color=#008040
size=4>散列表、同义词、碰撞、堆积</FONT><FONT face=宋体 size=5></P>
<P align=justify></FONT><FONT face=宋体 color=#008080 size=4>二</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></P>
<P align=justify> 2. </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> 2)
</FONT><FONT face=宋体 size=3>冲突处理方法</FONT><FONT size=3>(</FONT><FONT face=宋体
size=3>分离同义词子表、线性探测、双散列函数</FONT><FONT size=3>)</FONT></P>
<P align=justify><FONT size=3> 3. <FONT
color=#ff0000>递归分治、回溯</FONT></FONT></P>
<P align=justify><FONT face=宋体 color=#000080 size=5> </P>
<P align=justify>第</FONT><FONT color=#000080 size=5>10</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> </FONT><FONT face=宋体
size=3>动态索引结构</FONT><FONT size=3>(B</FONT><FONT face=宋体 size=3>树</FONT><FONT
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. B</FONT><FONT
face=宋体 color=#008000>树、</FONT><FONT color=#008000>B+</FONT><FONT face=宋体
color=#008000>树的插入与删除</FONT><FONT size=3>(</FONT><FONT face=宋体
size=3>注意保持性质，特别是等高；以及子女和关键码个数的上下限制</FONT><FONT size=3>)</P>
<P align=justify> B</FONT><FONT
face=宋体 size=3>树中关键码没有重复，父结点中的关键码是其子结点的分界；</FONT><FONT size=3>B+</FONT><FONT
face=宋体 size=3>中最底层是关键码的一个全集，往根的方向一层层复写。</FONT><FONT size=3></P>
<P align=justify> B</FONT><FONT
face=宋体 size=3>树插入</FONT><FONT size=3> : </FONT><FONT face=宋体
size=3>插入</FONT><FONT size=3> <FONT face=宋体>--------</FONT> </FONT><FONT face=宋体
size=3>分裂</FONT><FONT size=3></P>
<P align=justify> B</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> </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> </FONT><FONT face=宋体 size=3>--------</FONT><FONT size=3> </FONT><FONT
face=宋体 size=3>合并</FONT><FONT size=3></P>
<P align=justify> B+</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> </FONT><FONT face=宋体 size=3>分裂</FONT><FONT size=3></P>
<P align=justify> B+</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> </FONT><FONT face=宋体 size=3>借关键码</FONT><FONT size=3> </FONT><FONT
face=宋体 size=3>--------</FONT><FONT size=3> </FONT><FONT face=宋体 size=3>合并 </P>
<P align=justify> </P></FONT><FONT face=宋体 color=#000080 size=5>
<P align=justify>第</FONT><FONT color=#000080 size=5>11</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 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 size=3></P>
<P align=justify> 1. </FONT><FONT face=宋体
size=3>数组的行优先、列优先顺序存储地址计算</FONT><FONT size=3></P>
<P align=justify> 2. </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
size=3></P>
<P align=justify> 4. </FONT><FONT face=宋体
size=3>广义表的表头、表尾、长度、深度</P>
<P align=justify> </P></FONT><FONT face=宋体 color=#000080 size=5>
<P align=justify>第</FONT><FONT color=#000080 size=5>12</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></P><FONT size=3>
<P align=justify> 1. <FONT face=宋体
size=3>字符树(</FONT>trie<FONT face=宋体 size=3>树、<FONT
color=#ff0000>PATRICIA树</FONT></FONT></FONT>) <FONT face=宋体><FONT
size=3>2. <FONT
color=#ff0000>最佳BST</FONT></FONT></FONT>
<FONT size=3>3. 平衡二叉树(AVL树)</FONT> <FONT size=3>4.
<FONT color=#ff0000>伸展树（半伸展树）</FONT></FONT></P><FONT face=宋体 color=#008080
size=4>
<P align=justify>二</FONT><FONT color=#008080 size=4>. </FONT><FONT face=宋体
color=#008080 size=4>方法</FONT></P><FONT face=宋体 color=#008000>
<P align=justify><FONT size=3> </FONT><FONT face=宋体 color=#ff0000>
</FONT></FONT><FONT face=宋体 size=3>1. 字符树的画法</FONT></P>
<P align=justify><FONT face=宋体 color=#ff0000> 2. </FONT><FONT
face=宋体 color=#008000><FONT face=宋体 color=#ff0000>最佳BST以及动态规划方法</FONT></P>
<P align=justify> ★</FONT><FONT color=#008000>3.
AVL</FONT><FONT face=宋体 color=#008000>树的插入</FONT><FONT size=3>(LL</FONT><FONT
face=宋体 size=3>，</FONT><FONT size=3>LR</FONT><FONT face=宋体 size=3>，</FONT><FONT
size=3>RR</FONT><FONT face=宋体 size=3>，</FONT><FONT size=3>RL</FONT><FONT face=宋体
size=3>四种旋转</FONT>，<FONT size=3>不考删除</FONT><FONT size=3>)</FONT><FONT face=宋体
size=3>，严格按照算法来完成</FONT></P>
<P align=justify><FONT color=#ff0000 size=3> 3.
伸展树（半伸展树）的插入操作</FONT></P>
<P align=justify> </P><FONT face=宋体 color=#000080 size=5>
<P align=justify>祝大家顺心如意！</FONT></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -