北大计算机系2007级数据结构考研提纲

北大计算机系2007级数据结构考研提纲
发信站: 北大未名站 (2006年08月29日23:12:13 星期二), 转信

http://db.pku.edu.cn/mzhang/ds/account/a10_kydg.html

北京大学计算机系

2007级硕士研究生入学考试

数据结构复习提要

2006年8月  张铭  编写

（本课程考研总分为80分）

1. 主要参考书：

(1) 许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社，2004年
7月。ISBN 7-04-014616-9。

（网上购书：http://www.landraco.com.cn/book/bookdetail.asp?plucode=14616-00）

    *

      第1、2、3章（第1-84页）由许卓群主笔
    *

      第4、5、6章（第85-202页）由杨冬青主笔
    *

      第8、10章（第254-293页，第333-358页）由唐世渭主笔
    *

      第7章内排序、第9章检索、第11章高级线性结构、第12章高级树结构（第203-253
页，第294-332页，第359-468页，）由张铭主笔

    教材勘误表（下载）（Acrobat reader）

　

(2) 张铭、赵海燕、王腾蛟，《数据结构与算法－－学习指导与习题解析》，高等教育出
版社，2005年 10月。ISBN 7-04-017829-X。

（网上购书：http://www.landraco.com.cn/book/bookdetail.asp?plucode=17829-00）

    *

      第7、9、10、12、13、14章（第162-215、244-279、280-303、324-503页）由张铭
教授主笔
    *

      第1、2、3、11章（第1-47、304-323页）由赵海燕副教授主笔
    *

      第4、5、6、8章（第48-161、226-243页）由王腾蛟副教授主笔

   内容简介：主教材各章知识点、习题和上机题解答，ACM竞赛和上机实习报告示例，
2004秋季学期北大信科院期中期末“数据结构与算法”试题详解，1999-2005年北大计算
机专业“数据结构”考研题详解。

   学习指导书勘误表（下载）

　

   北大教材科、王府井图书大厦、西单图书大厦有售。某些新华书店也可能有售。

   高教社购书热线：010-58581118，58581117，58581116。

    高教社网上订购URL：http://www.landraco.com.cn

　

(3) 张铭，刘晓丹译。《数据结构与算法分析》（C++两版、Java版）。电子工业出版社
2002年6月C++第二版。译自：Clifford A.Shaffer, A practical Introduction to
Data Structures and Algorithm Analysis,  Prentice Hall.

　

2. 课程网站（课程讲义、算法源代码等）：http://www.db.pku.edu.cn/mzhang/DS/

                                   或者 http://db.cs.pku.edu.cn/mzhang/DS/

　

3. 关于算法：

  （1）算法语言无所谓，只要能看懂。考试用 C++出题，但答题随意(可以用C/C++、
Java、Pascal、自然语言等等，看得懂就可以) 。

  （2）如果要求自己独立地写算法（而不是填空），请注意写算法思想，并加上足够的
注释

  （3）对于算法中直接使用的类和 函数（例如栈、队列的函数），应该 先写ADT，并说
明函数功能、入口参数、出口参数

　

4. 关于答疑和讨论

   张铭不回答关于考研的 mail。

   关于教材内容问题和数据结构技术性问题，欢迎到http://db.cs.pku.edu.cn/mzhang/
DS/bbs/index.asp

论坛“读者交流”板块讨论。

    关于考研技巧问题，请到BBS考研版（http://bbs.pku.edu.cn/cgi-bin/bbstop?boar
d=Kaoyan，似乎北大校外不能访问）去询问。

     常见问题解答

　

5.  考试范围和重点

不考11.3存储管理，不考12.3空间树结构，不考12.4.1决策树、12.4.2博弈树。

各章节以下面的内容为复习重点，尤其是绿颜色文字、红色文字或★标出部分为重中之重
。其中红色部分为根据新教材本届考试增加的内容。考试时如果涉及到本大纲没有列出的
内容，那么试卷中会给出足够的定义和性质。

第1章 概论 （教材中本章作者为许卓群）

一. 重要概念

    1. 数据类型 2. 抽象数据结构 3. 数据结构 4. 存储结构 5. 算法 6. 算法度量(时
间代价、空间代价)

    7.  数据结构的选择和评价

二. 方法

     1. 根据二元组画出图示逻辑结构(注意边的方向)

     2. 根据要求设计数据结构

     3. 算法度量的大O表示法的简化法则（不要求掌握大Ω、大Θ表示法）

　

第2章 线性表（教材中本章作者为许卓群）

一. 概念

     1. 线性表 2. 单链表 3. 双链表 4. 循环表 5. 栈 6. 队列 7. 循环队列

二. 方法

    1. 线性表的运算(指针操作的正确性)

    2. 循环队列队列的实现

   ★3. 表达式求值(前中后缀各种表达式互相转化、表达式树与各种表达式互相转换、
前缀后缀表达式求值)

    4. 栈的性质，用栈来生成序列

　

第3章 字符串（教材中本章作者为许卓群）

一. 概念

   1. 串   2. 模式匹配

二. 方法

   1. 串的基本操作

   2. 串的存储

★ 3. 串的KMP快速模式匹配算法(next数组)，求特征next数组（N数组）和利用next数组
完成匹配的方法

   4. 相关串运算和处理算法

　

第4章 二叉树（教材中本章作者为杨冬青）

一. 概念

      1. 二叉树 2.二叉树的前序、中序、后序周游 3. 二叉排序树 4. 穿线树(中序、
前序、后序) 5. Huffman树、Huffman编码 6. 堆、堆排序

二. 方法

      1．二叉树的链式存储

         （1）二叉链表

         （2）带父指针的三重链表

      2. 二叉树的顺序存储

           完全二叉树的顺序存储

    ★3. 使用栈(前、中、后序)周游二叉树(注意，不要使用带GOTO语句的机械消除递归
的方法)、使用队列层次地周游二叉树，在周游过程中寻找某个结点或进行某种操作 (结
合应用，例如穿线树，或把快速排序转换成非递归形式)

       4. 二叉检索树的插入与删除

       5. 构造Huffman树，利用Huffman树进行编码、解码

       6. 堆排序的建堆过程

　

第5章 树（教材中本章作者为杨冬青）

一. 概念

       1. 树、森林  2. 树、森林的先根周游、后根周游、层次周游

二. 方法

      1. 树林与二叉树相互转换

      2．森林的链式存储

          (1) 转换为相应的二叉树，用二叉链表表示

          (2) 父指针表示法

          (3) 子结点表表示法

       3. 森林的顺序存储

      不必死记各种顺序存储方法，要了解原理。其本质是按照周游的性质，把顺序存储
的森林信息反构造成森林（在内存中往往用二叉树来表示）

       4. 二叉树和森林的层次周游(用队列)，可能结合应用

　

第6章 图（教材中本章作者为杨冬青）

一. 概念

     1. 图的深度周游 2. 图的宽度周游 3. 图的生成树、生成树林、最小生成树 （不
要求掌握关键路径）

二. 方法

   ★1. 图的存储方法

       （1） 相邻矩阵 （2） 邻接表(结点表 -- 边表)

     2. 图的周游

       （1） 深度优先 （2） 宽度优先

     3. 图的生成树与最小生成树

       （1） 从某一点出发，按深度优先或宽度优先周游的生成树

       （2） 最小生成树 ① Prim算法 ② Kruskal算法(避圈法)

     4. 拓扑排序 : 对于给定图，找出若干个或所有拓扑序列

        任何无环的有向图，都可以拓扑排序。

     5. 最短路径

        Dijkstra算法、Floyd算法(这两个算法都属于贪心法，也属于动态规划法) ★
两个算法的关键都在求Min的部分

     6. 贪心法

     7. 图的相关算法

　

★第7章 内排序（教材中本章作者为张铭）

二. 方法

     1. 重点排序算法：直接插入法、Shell排序、★快速排序、基数排序、归并排序

     2. 算法分析

       （1）基于比较次数和移位次数（一个移位就是一次纪录赋值操作，例如一次
swap 交换是3次移位），分析最好、最坏的时间、空间

       （2） 记住各种排序方法的平均时间

      3. 各种排序方法的局部修改和混合应用

　

第8章 文件管理和外排序（教材中本章作者为唐世渭）

一. 概念

     1. 顺序文件 2. 散列文件 3. 倒排文件

二. 方法

     1. 置换选择排序

     2. 赢者树、败者树

     3. 多路归并

　

第9章 检索（教材中本章作者为张铭）

一. 概念

     1. 平均检索长度

     2. 二分法检索

   ★3. 散列表、同义词、碰撞、堆积（聚积）、二次聚集

二. 方法

     1. 二分法检索的判定树、查找某个结点的比较次数

     2. 散列表: 1) 散列函数的选择(除余法、折叠法)

               2) 冲突处理方法(分离同义词子表、线性探测、双散列函数)

     3. 递归分治、回溯

　

第10章 索引技术（教材中本章作者为唐世渭）

一. 概念

        动态索引结构(B树)

二. 方法

     1. 索引结构设计以及索引效率分析

    ★2. B树、B+树的插入与删除(注意保持性质，特别是等高；以及子女和关键码个数
的上下限制)

         B树中关键码没有重复，父结点中的关键码是其子结点的分界；B+中最底层是关
键码的一个全集，往根的方向一层层复写。

         B树插入 : 插入 -------- 分裂

         B树删除 : 交换 -------- 删除 -------- 借关键码 -------- 合并

         B+树插入 : 插入 -------- 分裂

         B+树删除 : 删除 -------- 借关键码 -------- 合并　

　

第11章 数组与广义表（教材中本章作者为张铭）

一. 概念

     1. 多维数组 2. 稀疏矩阵 3. 广义表(递归表、再入表)

二. 方法

     1. 数组的行优先、列优先顺序存储地址计算

     2. 稀疏矩阵的三元组及十字链表存储

   ★3. 广义表的带表头的单链形式存储(递归表、再入表)

     4. 广义表的表头、表尾、长度、深度

　

第12章 高级树结构（教材中本章作者为张铭）

一. 概念

     1. 字符树(trie树、PATRICIA树)   2. 最佳BST       3. 平衡二叉树(AVL树
)      4. 伸展树（半伸展树）

二. 方法

    1. 字符树的画法

    2. 最佳BST以及动态规划方法

    ★3. AVL树的插入(LL，LR，RR，RL四种旋转，不考删除)，严格按照算法来完成

    4. 伸展树（半伸展树）的插入操作

[s:2] [s:2] [s:2]

[s:2] [s:2] [s:2]