苏大872大纲.doc

数据结构:
由于数据结构出题老师换了,所以2016年的题目也稍有改动,全是大题。苏大的参考书是严蔚敏的数据结构,但是本部计科的貌似是用的老外的黑色的数据结构与算法分析。
所以最好准备点算法的知识。知识点的话我就以严蔚敏的书来写了。
第一章:绪论
主要是名词解释,16年没考,不知道17还考不考。
主要知道时间复杂度,空间复杂度,会求。
第二章:线性表
这一张不出意外会考一题,一般以链表居多。(16年的貌似算法就考了一个,好像是在一个链表中筛选出符合要求的数据把他们组成另外一个链表,具体细节记不清楚了).
线性表的定义以及表示,循环链表,双向链表都要会,算法比较多,难度一般。,问老师时他说要考。。。但是貌似没考过,看与不看自便。。。
第三章:栈和队列
具体算法考得不多,主要是为了后面的递归,图等算法打下基础,但是要会计算相关的题目了解相关术语。表达式求值要会,书上的什么迷宫求解,离散时间模拟就算了。
第四章:串
考的不多,以概念为主,具体算法貌似没怎么考过,模式匹配有时间看看,最起码相关的名词,算法思想要会。其他的看看,有个印象。
第五章:数组和广义表。
知道数组的相关名词比如:矩阵的压缩存储,特殊矩阵,稀疏矩阵,以及地址的计算。广义表不考。
第六章:树与二叉树
这章不出意外必考。16年的题目貌似在最后一题,大体的要求是:3个节点的二叉树有5种不同的形态,问N个节点有多少种,用递归实现。貌似是这个,要是错了当我没说。卡塔兰函数的递归,应该是,反正没写出来。
树的定义和相关基本术语要知道,。线索二叉树苏大不考(老师这样说的,考了别打我。。。)遍历的必须会,递归以及非递归,为难你的话就让你写后序遍历的非递归。树和森林要会的,说白了还是二叉树。树的等价问题不考。赫夫曼树要会,相关的算法以及计算也要会。 不考。
这一章题目众多,要会灵活运用。。。。
第七章:图
图的十字链表表示法,邻接多重表表示不考。(还是那句话,考到了别打我,老师这样说的,换老师就不好说了)图的遍历必须会。DFS的非递归什么的熟练掌握。图的连通性问题要会的。那个关节点和重联通分量不考。关键路径不考,拓扑要会,拓扑的代码貌似不考。
最短路径最小生成树什么的那必须会了,不过苏大貌似不考弗洛伊达算法。
第八章:不考
第九章:查找


二叉排序树,平衡二叉树要会。今年考了。给你一组数据,然后动态建立AVL树,还问了什么是AVL树等等。。。。二叉排序树貌似考了忘了。。。
哈希表(重点)
苏大就爱这家伙,今年又考了,是问答题,什么是哈希,如何构造,如何解决冲突等等。
第十章:内排
不必说了,重中之重。要知道具体的细节,会手动写出每一趟结果,知道每个排序的特性特点,最重要的是快排和堆排以及他们的衍生问题。
,知道具体操作就好了,希尔归并什么的代码考到的概率不大。
第十一,十二章不考。
至于参考书,基础薄弱的看天勤的吧,基础好的看王道,其他的书也可以。不过建议天勤的知识点,王道的习题。
DS比较难,具体题目也恶心,把天勤,王道的题目最好都会做。。。。
今年还考了一些算法的知识,比如动态规划问题。。。