📄 2006级硕士研究生入学考试“数据结构”复习提要.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://db.pku.edu.cn/mzhang/DS/DSgradreview.HTM -->
<!-- saved from url=(0022)http://internet.e-mail --><HTML><HEAD><TITLE>2006级硕士研究生入学考试“数据结构”复习提要</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.2668" name=GENERATOR>
<STYLE>.style1 {
FONT-SIZE: 18px
}
</STYLE>
</HEAD>
<BODY>
<P align=center><FONT face=楷体_GB2312
color=#000040><BIG><BIG><BIG>北京大学计算机系</BIG></BIG></BIG></FONT></P>
<P align=center><FONT face=楷体_GB2312
color=#004080><BIG><BIG><BIG>2006级硕士研究生入学考试</BIG></BIG></BIG></FONT></P>
<P align=center><BIG><BIG><BIG><FONT face=楷体_GB2312
color=#008000>数据结构</FONT><FONT face=楷体_GB2312
color=#004080>复习提要</FONT></BIG></BIG></BIG></P>
<P align=center><FONT style="FONT-SIZE: larger" face=楷体_GB2312
color=#004080>2005年7月 张铭 编写</FONT></P>
<P align=center><FONT face=宋体 color=#000080 size=5>（本课程考研总分为80分）</FONT></P>
<HR>
<P><FONT size=4>1. 主要参考书：</FONT></P>
<P><FONT size=4>(1) 许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年 7月。ISBN
7-04-014616-9。</FONT></P>
<UL>
<LI><FONT size=4>第1、2、3章（第1-84页）由许卓群主笔</FONT>
<LI><FONT size=4>第4、5、6章（第85-202页）由杨冬青主笔</FONT>
<LI><FONT size=4>第8、10章（第254-293页，第333-358页）由唐世渭主笔</FONT>
<LI><FONT
size=4>第7章内排序、第9章检索、第11章高级线性结构、第12章高级树结构（第203-253页，第294-332页，第359-468页，）由张铭主笔</FONT>
</LI></UL>
<P> 教材勘误表（<A
href="http://db.cs.pku.edu.cn/mzhang/DS/zhinan/errata.pdf">下载</A>）（<A
href="http://db.pku.edu.cn/mzhang/DS/zhinan/Acrobat5.01简体中文完整版.rar">Acrobat
reader</A>） </P>
<P>(2) <FONT size=4>张铭、赵海燕、王腾蛟，《数据结构与算法－－学习指导与习题解析》，高等教育出版社，2005年 9月。ISBN
7-04-017829-X。</FONT></P>
<P><FONT size=4>
内容简介：主教材各章知识点、习题和上机题解答，ACM竞赛和上机实习报告示例，2004秋季学期北大信科院期中期末“数据结构与算法”试题详解，1999-2005年北大计算机专业“数据结构”考研题详解。</FONT></P>
<P><FONT size=4>(3)
张铭，刘晓丹译。《数据结构与算法分析》（C++两版、Java版）。电子工业出版社2002年6月C++第二版。译自：Clifford A.Shaffer, A
practical Introduction to Data Structures and Algorithm Analysis, Prentice
Hall. </FONT></P>
<P> </P>
<P><FONT size=4>2. 课程网站（课程讲义、算法源代码等）：</FONT><A
href="http://www.db.pku.edu.cn/mzhang/DS/"><FONT
size=4>http://www.db.pku.edu.cn/mzhang/DS/</FONT></A></P>
<P><FONT
size=4>
或者 <A
href="http://db.cs.pku.edu.cn/mzhang/DS/">http://db.cs.pku.edu.cn/mzhang/DS/</A></FONT></P>
<P class=MsoNormal style="MARGIN-LEFT: 18pt; TEXT-INDENT: -18pt"><FONT
size=4><SPAN style="FONT-FAMILY: 宋体">3</SPAN><SPAN lang=EN-US
style="FONT-WEIGHT: normal; FONT-FAMILY: 宋体">.</SPAN><SPAN lang=EN-US
style="FONT-WEIGHT: normal; FONT-STYLE: normal; FONT-FAMILY: 宋体; FONT-VARIANT: normal"> </SPAN><SPAN
style="FONT-WEIGHT: normal; FONT-FAMILY: 宋体">关于算法：</SPAN></FONT></P>
<P class=MsoNormal style="MARGIN-LEFT: 18pt; TEXT-INDENT: -18pt"><SPAN
style="FONT-FAMILY: 宋体"><FONT size=4> （1）算法</FONT></SPAN><FONT
size=4><SPAN style="FONT-WEIGHT: normal; FONT-FAMILY: 宋体">语言无所谓，只要能看懂。考试用<SPAN
lang=EN-US>C++出题，但答题随意</SPAN>(可以用C/C++、Java、Pascal、自然语言等等，看得懂就可以)<SPAN
lang=EN-US>。</SPAN></SPAN></FONT></P>
<P class=MsoNormal style="MARGIN-LEFT: 18pt; TEXT-INDENT: -18pt"><SPAN
style="FONT-FAMILY: 宋体"><FONT size=4> （2）如果要求自己独立地</FONT></SPAN><FONT
size=4><SPAN lang=EN-US>写算法</SPAN>（而不是填空），请注意写算法思想，并加上足够的<SPAN
lang=EN-US>注释</SPAN></FONT></P>
<P class=MsoNormal style="MARGIN-LEFT: 18pt; TEXT-INDENT: -18pt"><FONT
size=4> （3）对于<SPAN lang=EN-US>算法中直接使用的</SPAN>类和<SPAN
lang=EN-US>函数</SPAN>（例如栈、队列的函数），应该<SPAN
lang=EN-US>先写ADT，并说明函数功能、入口参数、出口参数</SPAN></FONT></P>
<P> </P>
<P><FONT size=4><SPAN style="FONT-FAMILY: 宋体">4</SPAN><SPAN
style="COLOR: black; FONT-FAMILY: 宋体">. 关于答疑和讨论</SPAN></FONT></P>
<P><FONT size=4><SPAN style="COLOR: black; FONT-FAMILY: 宋体">
张铭</SPAN><SPAN style="COLOR: black; FONT-FAMILY: 宋体">不回答关于考研的<SPAN
lang=EN-US>mail。</SPAN></SPAN></FONT></P>
<P><FONT size=4><SPAN lang=EN-US
style="COLOR: black; FONT-FAMILY: 宋体">
关于教材内容问题和数据结构技术性问题，欢迎到</SPAN><A
href="http://db.cs.pku.edu.cn/mzhang/DS/bbs/index.asp">http://db.cs.pku.edu.cn/mzhang/DS/bbs/index.asp</A></FONT></P>
<P><FONT
size=4>论坛讨论。不过，由于有人擅自在论坛上张贴广告，我们暂时封锁论坛为只读状态。大约在2005年9月本科生开始上《数据结构与算法A》课程之后，将解除锁定状态，欢迎讨论交流。</FONT></P>
<P><FONT size=4> 关于考研技巧问题，请到<SPAN
style="COLOR: black; FONT-FAMILY: 宋体"><SPAN
lang=EN-US>到BBS考研版（</SPAN></SPAN><SPAN
style="COLOR: black; FONT-FAMILY: 宋体; TEXT-DECORATION: none"><FONT
color=#000080><A
href="http://bbs.pku.edu.cn/cgi-bin/bbstop?board=Kaoyan"><U>http://bbs.pku.edu.cn/cgi-bin/bbstop?board=Kaoyan</U></A></FONT></SPAN><SPAN
lang=EN-US
style="COLOR: black; FONT-FAMILY: 宋体">，似乎北大校外不能访问）去询问。</SPAN></FONT></P>
<P> <A
href="http://db.cs.pku.edu.cn/mzhang/DS/zhinan/FAQ.pdf">常见问题解答</A> </P>
<P> </P>
<P><FONT size=4>5. 考试范围和重点</FONT></P>
<P align=justify><FONT size=4>不考<FONT face=宋体 color=#ff00ff
size=5>11.3存储管理</FONT>，不考<FONT face=宋体 color=#ff00ff
size=5>12.3空间树结构</FONT>，不考<FONT face=宋体 color=#ff00ff
size=5>12.4.1决策树、12.4.2博弈树</FONT>。</FONT></P>
<P align=justify><FONT size=4>各章节以下面的内容为<FONT face=宋体 color=#ff00ff
size=5>复习重点，</FONT>尤其是<FONT face=宋体 color=#008000 size=5>绿颜色文字</FONT><FONT
face=宋体 size=5>、</FONT><FONT face=宋体 color=#ff0000 size=5>红色文字</FONT>或<FONT
face=宋体 color=#008000 size=5>★</FONT>标出部分为<FONT face=宋体 color=#ff00ff
size=5>重中之重</FONT>。其中<FONT
color=#ff0000>红色部分</FONT>为根据新教材本届考试增加的内容。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质。</FONT></P>
<HR>
<P align=justify><A style="TEXT-DECORATION: none"
href="http://db.pku.edu.cn/mzhang/DS/Dsintro.htm"><FONT face=宋体 color=#000080
size=5>第1章 概论 </FONT></A><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 color=#008000></P>
<P align=justify> 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></P><FONT face=宋体
color=#ff0000> 7. 数据结构的选择和评价</FONT><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><FONT size=3>(</FONT><FONT face=宋体
size=3>注意边的方向</FONT><FONT size=3>) </FONT></P>
<P align=justify><FONT size=3> </FONT><FONT face=宋体
color=#008000> </FONT><FONT face=宋体 color=#ff0000> 2.
根据要求设计数据结构</FONT></P><FONT size=3>
<P align=justify> 3. </FONT><FONT face=宋体
size=3>算法度量的大</FONT><FONT size=3>O</FONT><FONT face=宋体
size=3>表示法的简化法则（不要求掌握大Ω、大Θ表示法）</FONT></P>
<P align=justify> </P><FONT face=宋体 color=#000080 size=5>
<P align=justify>第</FONT><FONT color=#000080 size=5>2</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> 5. </FONT><FONT face=宋体
size=3>栈</FONT><FONT size=3> 6. </FONT><FONT face=宋体 size=3>队列</FONT><FONT
size=3> 7. </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 size=3></P>
<P align=justify> 1. </FONT><FONT face=宋体
size=3>线性表的运算</FONT><FONT size=3>(</FONT><FONT face=宋体
size=3>指针操作的正确性</FONT><FONT size=3>) </FONT></P>
<P align=justify><FONT color=#ff0000><FONT size=3> </FONT> 2.
循环队列队列的实现</FONT><FONT size=3></P>
<P align=justify> <FONT face=宋体 color=#008000>★</FONT>3. <FONT
face=宋体 color=#008000>表达式求值(中缀表达式转后缀表达式的算法、后缀表达式求值算法)</FONT></FONT></P><FONT
face=宋体 color=#008000>
<P align=justify> </FONT><FONT face=宋体 size=3> 4.
栈的性质，用栈来生成序列</FONT></P>
<P align=justify> </P><FONT face=宋体 size=3><FONT face=宋体 color=#000080 size=5>
<P align=justify>第3章</FONT><FONT color=#000080 size=5> </FONT></FONT><FONT
face=宋体 color=#000080 size=5>字符串</FONT><FONT face=宋体 size=3><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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -