数据结构：关键点：教材，习题解析，视频，真题，多练。四类题：基础数据结构知识应用题（填空，解答，问答，画图等），算法填空题，算法改错题，算法设计题。
数据结构在考研的专业课卷中占80分，这门课我想着重来谈。
首先最重要的是把握住教材，一本教材一本习题解析已经非常足够，不行再添加严蔚敏老师的c语言版数据结构（非常经典的一本书），绝对足够。我同时还有张老师译的蓝皮DS教材，但几乎没看过。重视教材在上面也说了，这里还是想再次提出，希望大家能重视基础，“扎实＋灵活”是制胜之道。
张老师非常OPEN，在DS网站上几乎提供了一切北大本科生教学中用到的资料，比如ppt，资料索引，作业题（唯一的遗憾就是没有答案），甚至还有05年的完整DS教学视频，教学论坛也公开，这些大家一定要高度重视!最好都下载下来看看。比如教学视频吧，我去年是看了一遍半（后期时间宝贵就没看了），感觉张老师课讲得不错，看一遍过来巩固不少，并且从上课难度以及北大本科生上课的反应等方面也帮我增强了不少自信。
基础数据结构知识应用题（填空，解答，画图等）这一类题没用太多应对之策，因为每年考察的重点和题型都在变，较难把握，大家还是尽量掌握扎实基础知识，到时兵来将挡。
算法填空题要求在给定算法大体结构下写出空缺语句。这种题主要考察读程序能力，还是比较简单的。因为考察的空缺处多为程序的关键语句，而题目一开始会给出这一程序的功能，大家顺着已给的程序结构模拟程序执行过程（这一能力大家在复习中注意培养，不管是考试还是以后都是有用的^_^），再结合程序功能，去推断出填空处语句的作用，接下来填空来就比较容易了。这种题考的多为重要算法的应用题（甚至还考书上的原算法填空，印象很深的是考过置换选择排序的填空），所以基本功还是要好的。另外要注意边界条件，比如循环的起始处和终止条件等地方的设置，这是张老师喜欢考察的地方（借之考察大家写程序的完备性和健壮性）。
算法改错题出的相对较少，但今年考了。这一类题主要考察点有两个：逻辑错误和语法错误。多考察逻辑错误，比如边界条件不对，做的操作不对等，对语法错误考察较少，但今年的卷我好像改过其中的语法错误，具体是哪里不太记得了。这类题应对策略就针对考察点着手，一方面培养自己读程序调错误的能力，另一方面，C++/C语言的基本功也要扎实，简单的语法错误比如函数使用错误，变量声明不对等等要能一眼看出，要求高的还应能看出比如错误使用内存等问题。
算法设计题要求我们自己写代码，这一步大家千万别以为只要把程序写出来把问题解决了就OK了，对编程风格，程序结构等细节万不可轻视，从张铭老师的教学视频上可以看出张老师非常看重程序的可读性和健壮性，虽然说北大是在招研究生而不是程序员，但是老师肯定希望看到招进来的学生已经具有良好的编程基础和习惯，这一点就靠批改DS试卷的张老师来把关了。算法设计题建议的答题格式如下：
算法思想：……（一小段简单描述一下即可）
ADT（即程序中用到的数据结构，其实也就是个CLASS，并且成员变量可省去，主要写用到的函数，不用写函数实现，写函数声明（即“返回值类型 函数名 参数列表”）即可，最好在每个函数声明后面注释该函数功能）
int function(variable list)
{//简单描述参数的作用
（参数有效性的检验）
（程序主体）
（输出结果）
}
当然还要注意程序内要有充分的注释（不用每行都添加注释，但是关键语句后一定要有，并且注意言简意赅），程序风格也要注意，比如变量名尽量起的有意义，局部变量的定义与初始化最好在程序开始做完，程序内部尽量将功能相关的语句组织成小段落放在一起，必要时添加新函数来辅助实现功能，等等，都是程序正确性之外的考察点。推荐大家有时间去看一下林锐博士编的《高质量程序设计 c++/c语言》，里面有丰富的程序风格说明，看看对程序书写风格还是有较大帮助的，但其中部分内容要求有较高的C++语法基础且对数据结构的帮助不大，大家根据自身情况自己决定。
对于数据结构真题大家一定重视，比如里面的算法设计尽量都按照上面的格式来训练。真题里的名词解释题倒是可以不写（张老师说过她不考名词解释），但是看下名词解释考什么也能看出老师的考试重点。
数据结构还有一点是要多练，很多的ADT比如说栈，队列，二叉树（树），图等大家都可以去写具体程序，通过上机实践去掌握，这样加深记忆并且切实写过并且调试过之后对程序的理解会透彻不少。其实这一点讲给大三的学生听比较好，因为从数据结构课程的上机题入手就很不错。像我就有点得益于本科期间打下了不错的数据结构基础，后来看到北大教材中很多算法或者习题解法同我当时的做法很类似，要接受就比较简单了。大家在后面的复习中可以挑一些重点程序、算法，特别是自己掌握不牢固的，在复习看书疲惫的时候上机练一练，应该也会收获不错。
还有几点考试的经验：设计程序能递归则递归，省时省事，虽然递归程序运行稍慢一点让人不爽吧，但是写出递归程序拿到分数总比写不出非递归程序在那里吹胡子瞪眼让人爽的呵呵；做题大家能写一点就写一点，有步骤分，实在写不出来就写相关方面，能写多少就写多少（注意合理安排时间）。像我今年拿到题直接pass的红黑树（习题解析中介绍了，不过我没怎么看），跳到下一道发现居然是半伸展树又不会做（插一句，考前那晚我最后一次快速扫描DS书时，在高级树那章看了AVL树，看了伸展树，但就是没看课后上机题中介绍的半伸展树……），当时那叫一郁闷呀，我知道再给我多少时间我也想不起半伸展树的定义的，就直接拿伸展树的定义去做的半伸展树的题。不过张老师这题似乎至少给了我一半分，因为我红黑树空着，打印文件系统层次结构那题也有错误（题是树的后序周游，对应二叉树的中序，我没时间想提笔就写后续框架……），再加上OS问答题的扣分，半伸展树再扣多一点我就考不到这个分数了呵呵。所以大家考场上一定能写就写；不必非常注意卷面，张老师和陈老师都是注重实干的人，只要你正确做出来不在乎你的纸面是否整齐漂亮（当然看见工整的卷面是大家都希望的事情）。像我今年在DS的打印文件系统那题和OS的PV操作题都修改了几次，卷面挺不雅观，不过应该没害我丢多少分呵呵。
一般考试的重点：（我的教材已经送给学弟了，所以凭记忆列出，仅供参考，大家还是应全面仔细复习）
考程序（包括程序填空，改错，算法设计）：二叉树，树，图，内排序，
考应用（比如填空，解答，问答，画图）：外排，索引（B树），高级树（AVL树）（近年来看高级树上出题渐多）。
当然，这些只是知识点可能的考察方式，不绝对的，比如考内排序的应用题完全可能的。另外线性表（栈，队列，栈在后缀前缀变换中的应用），KMP，高级线性结构（主要是多维数组，广义表）这些相对简单一点，但也都是很重要的，并且程序题和应用题都可以出，大家也要重视。
数据结构的复习不用现在就开始，现在抓好数学和英语的基础就行，像我去年是8月16号才第一次翻开教材来复习的，大家要是着急可以暑假开始时就看，完全来得及。
这里给出系列的链接：
（1）自我定位篇：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=60645
（2）政治英语复习篇：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=60824
（3）高等数学复习篇：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=61732
（4）离散数学复习篇：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=61733
（5）数据结构复习篇：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=61734
（6）操作系统复习篇：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=61735
[此贴子已经被admin于2008-4-24 23:28:52编辑过]
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 计算机考研交流 』 → [原创] 走进pku，回首漫漫考研路（5）——数据结构复习篇
(订阅本版)
2008/4/23 22:06:00
新浪微博
[原创] 走进pku，回首漫漫考研路（5）——数据结构复习篇
