数据结构的几大块:
一 数组
数组的主要内容无非是顺序表、矩阵、字符串，其中重点当然是字符串，特别是模式匹配KMP算法。东大02、04、05年一直在考。这里提醒大家注意清华c++版的KMP算法不同于清华严蔚敏c语言版。还有一些经典算法需要掌握，比如01、05年考的n*m矩阵A[a..b,c..d],A[I,J]<=A[I,J+1],A[I,J]<=A[I+1,J],设计算法判断x是否在A中。还有01年的数组A中有n个数取m个数的所有组合。
二 链表
链表类及基本操作一定要掌握，链表的应用也就是矩阵和多项式。03年东大就考过用面向对象语言编写单链表类的插入和删除操作，尤显基本操作的重要。
三 树
毫无疑问树是一个非常重要的数据结构，几乎所有数据结构试卷都可以见证这一点，东大也不例外，尤其是二叉树。
我觉得重点就两个遍历和线索化，当然从中延伸的题目多不胜数，程序题是必然，也包括计算题，04年东大就曾考过:完全二叉数500个节点，问有多少叶子，度为1、2的节点分别为多少？03年如何将表达式转化为二叉数，编写算法打印节点x的所有祖先。求两节点最近的公共祖先。04年的中序线索化找前驱节点。06年的层次遍历森林B。还有就是最短路径和最小生成数，Prim、Dijkstr、Floyed算法和Topological order，经典的如小区医院问题。
以上皆为本人观点，恐有不妥，愿与大家交流。未完待续...
有的同学提到专业课复习日期问题，我觉得这还是自己掌握。每个人都有自己的复习计划，只要按照计划来就可以了。暑期复习当然不晚，如果觉得自己专业课功底还不错在晚点也没有关系，毕竟还有公共课吗？
对于专业课的复习我根据自己的经验提点建议:因为我们考四门专业课，可能你刚看完一门课，看下一门课没多久，前一门课又忘了些，所以我建议大家四门课同时看，比如可以一天一门，或者各科各章交替看，这样不会出现上述情形。还有就是建议大家教材多看几遍，不知道大家有没有这样的感觉，一本书每看一遍收获都是不一样的，专业课同样也是如此。
四 排序
几种常见的排序方法，时空复杂度（最好、最坏情况），稳定性，还有算法的附加条件。02年的建堆，03年的shell和链接基数排序，04年实际上是一道快排编程题，只不过要两次快排。外排序也要注意，05年考了置换-选择排序。
五 B树和散列
一棵m阶B树是一棵m路搜索树。注意B树的节点、层次、高度的计算，B树的插入删除。02、04、05都考了相关题目。
散列主要掌握hash函数，冲突处理，如04年第2题。
数据结构内容多，难度大，建议大家看书加做练习，真题可以帮助寻找规律，要认真做，以上为东南大学真题，仅供参考。 |
收藏
点赞!
反对!
