（北大计算机）考研经验贴

kuddy

上面的提纲是陈老师去年给的，大家可以看看，去年考试的题目97%都在里面了，可惜不能显示颜色，想要看看重点的同学发email给我：katyush@163.com

kuddy

北京大学计算机系

2005级硕士研究生入学考试

数据结构复习提要

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


--------------------------------------------------------------------------------

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

教材第1、2、3章由许卓群主笔，第4、5、6章由杨冬青主笔，第8、10章由唐世渭主笔，第7、9、11、12章由张铭主笔。
　

2. 关于算法：

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

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

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

3. 关于答疑

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

　

4.  考试范围和重点

不考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章 二叉树（教材中本章作者为杨冬青）

一. 概念

      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章 内排序（教材中本章作者为张铭）

二. 方法

     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. 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四种旋转，不考删除)，严格按照算法来完成

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

　

　

xiongoo

谢谢先  对小弟太有帮助了

望塔

请问你的Email是多少啊？
我是外校跨专业考北大计算机的，但我现在还不清楚到底考哪个方向更适合我，我很迷茫，在北大也没有熟人。看了你的帖子，颇有收获，我想向您问一些问题，又不知道怎么跟你联系。

kuddy

我的email:katyush@163.com
我也是外系外校的，还是上海**大学的，我初试数学132，数据结构+操作系统109，英语和数学60+，复试网络89/100。我也不比他们学计算机的差多少啊。
成功=信心+毅力+冒险精神。
一般的email我都回的。

mrhanyu

"另外，
我希望大家在任何选择作出时，都要把兴趣而不是别的任何东西放在第一位。"
-------------------------------------------------------------

太对了!忍不住回一贴!

kuddy

确立目标后的专一、坚持 、信心
好，现在经过深思和与学长的探讨之后，你打定了主意，那这个时候最重要的事情就是一
定要坚持和相信自己——不管你现在的基础有多么差。大四上学期是考研的关键时期，也
是一个多事之秋。薄弱的基础和巨大的差距，考研过程中种种高昂的机会成本，周边同学
提早过上的幸福生活都会使你的心理产生微妙的变化。我们的目标就是让这种变化限制到
最小范围。arcane和我，都是放弃了本系唾手可得的保研机会，而选择这条不确定的道路
的，我想，考北大cs的同学,很多都会面临这种抉择，我的建议是，一旦选择做出之后，
一定要相信自己的选择是最好的。在选择之前，是我喜欢所以我选择，在选择之后，必须
是我选择所以我喜欢。如果说用两个字来概括考研成功的最重要的因素，那就是“坚持”
，考研复习是个逐渐获得加速度的过程，越到最后，你的态度和激情就越有价值，因为这
个时候你从中获得的前进速度是初期不可能想象的到的。
（未完待续）
转自未名

kuddy

3 具体课程复习方略
大概就是在去年这个时候，我开始关注cs考研，而那个时候的我，是一个基本上不知道什
么是C,什么是C++的典型的文科生（我高中学的是文科，现在的专业也是一个只学过半年
“大学文科基础数学”的纯文科专业，幸而我修过经济学的双学位）记得当时我在康博斯
请教了这里的前任版主vito一些问题，vito学长很热情的向我介绍了相关情况并给了我不
少鼓励，也是在去年这个时候，我认识了我考研过程中认识的第一位也是最亲密的一位研
友——arcane.
现在回想起来，大三下的后半期和整个暑假乃至到十一左右，我的复习效率其实都很低，
基本上是“一杯茶，一包烟，一本离散看半天”的状态（那个时候学会了吸烟，现在已经
戒掉了，建议大家不管考不考研都要把自己的身体放在第一位）。整个近半年的时间，我
就在像读故事书一样反反复复在看那本大本的离散，而令别人难以置信的是，我竟然没有
动手做过一道题。直到有一天，当我上网发现网上已经有网友把离散所有的题都做完了之
后，我才在骤然间感到了压力。至于专业课，我基本上在这个时段把C,C++的基本语法搞
明白了，但真正要考的ds和os基本上处于一窍不通的状态。当时之所以这样，一是听过来
人讲专业课并不难，应该主要把精力放在离散上。二是当时把学习的希望基本上寄托在了
大四上的跟班听课上了，现在想来，虽然这些做法总体上很冒险，不值得大家借鉴，但我
觉得可能有些歪打正着，对大家的启示还是有的：1 虽然没做什么题，但我对离散的兴趣
被完完全全的调动起来了，到后期，我真的能像读金庸小说似的，饶有兴趣的读上半天，
有时候兴之所至，还要加上些批注。这让我在十月份之后全面作离散课后题时，并没有觉
得很枯燥，而且效率还可以。2 对跨专业而言，自学cs的专业课效率会很低，不如冒险放
一放，等大四上专业课开课时，系统的旁听一下专业课。（当然基本编程语言的使用要熟
练）这样，能把有限的时间利用的最好。当然也有教训：１ 从０５年的卷面分数分配来
看，高数这个时候其实应该也多看看　，至少把指定参考资料的课后习题应该做一遍（我
想我数学基础的分应该绝大部分都丢在高数上了）2 公共课这个时候也应该做一些题，以
免后期时间紧迫，压力太大。
十月中旬开始，才是我复习的黄金时期，这个时候的基本安排是：每天和arcane一起上课
，在４５甲自习，坚持旁听os和ds课，课下以幻灯片为最重要的资料复习巩固，同时ds选
择一定量的课后题来做，（我感觉ds的课后题没必要全做）；同时开始大规模，地毯式的
作离散课后题，基本上以２－３天做一章。这个时候压力开始慢慢有了，时间抓的也比较
紧，基本上取消了各种娱乐活动：）高数由于历年考得较简单，我们又都没想到会出到７
０分，所以只是断断续续的作了一些课后题。
从１２月中旬开始，是我考研的最关键时期，这个时候另一位研友ｃｊ，也加入到了我们
在四十五甲的复习队伍，他的加入，大大活跃了我们的讨论气氛，我这时一方面把从９０
年开始到０４年的数学和专业课真题作了一遍，另一方面开始全面的看政治，并作了一些
模拟题。ｃｊ、我和arcane在最后的时候又对我们认为特别重要的离散、ｏｓ、高数的知
识点作了一遍讨论和归纳，总之，这最后的一个月我感觉自己受益匪浅。

kuddy

以上谈的是我的大体经历，下面我再扼要谈一下各科复习：
１公共课，由于我是文科生，所以在这两科上基本没投入什么精力，个人感觉英语应该把
历年真题做一遍，这里我推荐曹其军的真题，因为他里面分析的非常详细（事实上我英语
基本上只看了这一本书），政治０５年的题大家都看到了，很基础，根本没必要上辅导班
和作大量模拟题（当然肯定要做一些），举个例子，我们宿舍一个考经院的同学，没上辅
导班，只是看了红宝书，做了做人大的1800,就考了88分。我个人推荐大家一定要看好红
宝书和小本的考试分析，然后找一个“辅导专家”的题系统来做就行了。
2 计算机数学基础
离散的重要性不用说大家也都明白，尽管05年由于题出的简单，情况有些特殊，但就04年
以前的情况来看，基本上是得离散者得天下，个人认为：离散的所有课后题是一定得做的
，历年的真题也是一定得做的，至于别的参考资料，个人认为都可以不看，还有时间的话
就做第二遍和推导课本中的定理吧。
我今年吃了高数的大亏，可怜我不定积分那两道题就有一道一点都没写，主要是考前太轻
视了，希望０６的csers一定要弄清分值分配，把高数看好，实事求是来讲，今年的高数
很简单，比数一的难度要低，做完课后大家如果还不放心的话，就把陈文灯的理工版复习
指导看一下吧。
3 计算机专业基础
数学的课听不听无所谓，专业课则最好要听一下，没有辅导班的时候听课就更重要了。作
为一个北大土著，其实说这话我有点矛盾，因为有时候旁听的人太多，会给pku的本科生
确实带来诸多不便，ds课件上的算法最好要达到大家自己能独立推导和默写的境界。
os的陈老师出题不偏不倚，大家把书和课件看好，再花时间把pv琢磨一下就OK了。当然对
跨系考的同学，最好再找一些其他参考资料来做，题目无所谓，主要是熟悉一下术语的意
涵和不同的表达方式，加强对课本的理解。
(未完待续）

[ Last edited by kuddy on 2005-4-25 at 10:53 ]

lylykitty

谢谢楼主给我们分享了这么多的经验~~~`
不过，听说面试的时候，是要自己有过一些项目做
或者能编大量的程序，这样才好进哦~~~~
是不是这样的呢？
我还打算现在找点兼职做做呢
赫赫~~~