北大计算机系2006级考研数据结构复习提要

《北大计算机系2006级考研数据结构复习提要》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北大计算机系2006级考研数据结构复习提要http://education.163.com　2005-09-0814:38:55　来源:北京大学作者：（本课程考研总分为80分）1.主要参考书：(1)许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年7月。ISBN7-04-014616-9。·第1、2、3章（第1-84页）由许卓群主笔·第4、5、6章（第85-202页）由杨冬青主笔·第8、10章（第254-293页，第333-358页）由唐世渭主笔·第7章内排序、第9章检索、第11章高级线性结构、第12章高级树结构（第203

2、-253页，第294-332页，第359-468页，）由张铭主笔   教材勘误表（下载）（Acrobatreader）(2)张铭、赵海燕、王腾蛟，《数据结构与算法－－学习指导与习题解析》，高等教育出版社，2005年9月。ISBN7-04-017829-X。  内容简介：主教材各章知识点、习题和上机题解答，ACM竞赛和上机实习报告示例，2004秋季学期北大信科院期中期末“数据结构与算法”试题详解，1999-2005年北大计算机专业“数据结构”考研题详解。(3)张铭，刘晓丹译。《数据结构与算法分析》（C++两版、Java版）。电子工业出版社2002年6

3、月C++第二版。译自：CliffordA.Shaffer,ApracticalIntroductiontoDataStructuresandAlgorithmAnalysis, PrenticeHall.　2.课程网站（课程讲义、算法源代码等）：http://www.db.pku.edu.cn/mzhang/DS/                                  或者http://db.cs.pku.edu.cn/mzhang/DS/3. 关于算法： （1）算法语言无所谓，只要能看懂。考试用C++出题，但答题随意(可以用C/C++

4、、Java、Pascal、自然语言等等，看得懂就可以)。 （2）如果要求自己独立地写算法（而不是填空），请注意写算法思想，并加上足够的注释  （3）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写ADT，并说明函数功能、入口参数、出口参数　4.关于答疑和讨论  张铭不回答关于考研的mail。  关于教材内容问题和数据结构技术性问题，欢迎到http://db.cs.pku..edu.cn/mzhang/DS/bbs/index.asp论坛讨论。不过，由于有人擅自在论坛上张贴广告，我们暂时封锁论坛为只读状态。大约在2005年9月本科生开始上

5、《数据结构与算法A》课程之后，将解除锁定状态，欢迎讨论交流。   关于考研技巧问题，请到到BBS考研版（http://bbs.pku.edu.cn/cgi-bin/bbstop?board=Kaoyan，似乎北大校外不能访问）去询问。    常见问题解答　5. 考试范围和重点不考11.3存储管理，不考12.3空间树结构，不考12.4.1决策树、12.4.2博弈树。各章节以下面的内容为复习重点，尤其是绿颜色文字、红色文字或★标出部分为重中之重。其中红色部分为根据新教材本届考试增加的内容。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义

6、和性质。第1章概论（教材中本章作者为许卓群）一.重要概念    1.数据类型2.抽象数据结构3.数据结构4.存储结构5.算法6.算法度量(时间代价、空间代价)    7. 数据结构的选择和评价二.方法     1.根据二元组画出图示逻辑结构(注意边的方向)    2.根据要求设计数据结构    3.算法度量的大O表示法的简化法则（不要求掌握大Ω、大Θ表示法）　第2章线性表（教材中本章作者为许卓群）一.概念     1.线性表2.单链表3.双链表4.循环表5.栈6.队列7.循环队列二.方法    1.线性表的运算(指针操作的正确性)   2.循环队列

7、队列的实现  ★3.表达式求值(中缀表达式转后缀表达式的算法、后缀表达式求值算法)   4.栈的性质，用栈来生成序列　第3章字符串（教材中本章作者为许卓群）一.概念1.串2.模式匹配二.方法1.串的基本操作2.串的存储★3.串的KMP快速模式匹配算法(next数组)，求特征next数组（N数组）和利用next数组完成匹配的方法　第4章二叉树（教材中本章作者为杨冬青）一.概念      1.二叉树2.二叉树的前序、中序、后序周游3.二叉排序树4.穿线树(中序、前序、后序)5.Huffman树、Huffman编码6.堆、堆排序二.方法       1．

8、二叉树的链式存储        （1）二叉链表        （2）带父指针的三重链表       2.二叉树的顺序存储