哈尔滨工程大学2004年数据结构考研笔记-易考网-Easy考研网提供考研试卷专业清单-考研一站式_Easy考研网_考研资料、考研专业课试题、考研专业目录、考研参考书目、考研咨询、考研辅导报名、考研书籍、考研会员服务

哈尔滨工程大学2004年数据结构考研笔记

http://www.ezkaoyan.com 2006-4-17

线性：线性表：插入（重点），删除（重点）。栈，队列，数组，
字符串，广义表。循环链表和不循环链表注意是否带表头
数据结构以及循环结束条件。

非线性：树型：树，二叉树。树的转换（重点），树的存储结构（孩子兄弟表示法）
图：深度优先，广度优先，存储结构，最小生成树

顺序：一维数组：插入，删除平均移动（n-1）/2
邻接矩阵，三元组表。
存储结构
非顺序结构：线性链表，双向链表，十字链表，二叉链表，逆邻接表，邻接多重表。

第一章绪论一定要注意黑体字的概念，每年都有几分的填空！！！

增加分配空间的算法一定要注意成功或者不成功。

链队列设链队列指针目的是减少搜索

循环队列注意空，满的判断。

关于栈的应用看表达式求值。

数组下标地址的计算（重点）：以行序为主存储，以列序为主存储。三对角列，下三角，上三角。

稀疏矩阵的表示方法：三元组表和十字链表，但是不要求其算法。

广义表：其定义，头，尾，注意区分头，尾。

字符串：其定义，空串和空格串的区别。注意不要求模式匹配算法！

二叉树的性质：5个结构一定要看每年都出题！！！

二叉树的遍历：先，中，后序。由表达式变成二叉树，由二叉树变成表达式。
由前推表示写出后推表示。

线索二叉树：三种不同线索树，要会画线索树（重点），中序遍历非递归算法，后序遍历非递归算法用栈两次。

N个结点的二叉树用N+1个栈，空指针进栈。

哈夫曼树，其编码注意书中的例子。

二叉树要求写算法：遍历，搜索二叉树某个结点，按层遍历用队列（复试考了）这些算法一定要会！

深度优先递归算法变为非递归

最小生成树（不是唯一的）：N个结点N-1个边连通图。最小生成树的选边和选点生成其代价和相等。

拓扑排序（序列不唯一），关键路径（不唯一）：关键路径上的活动是关键活动。
拓扑排序算法

查找：顺序查找，平均查找长度（n+1）/2 ，设监视哨额目的是减少一次比较。

折半查找：平均查找长度（成功或者不成功），看书中的例子。

分块查找

二叉树排序：动态生成，查找，删除

平衡二叉树：四种变换方式，看书中的例子。

B－树：5个定义，第五条叶子在同一层。重点

哈希表：什么是哈希表，哈希表的查找，存取与关键字多少无关。

除留余数法――哈希表构造
定义好的解决冲突方法：主要的两种方法：开放地址法，再哈希法。

排序：插入排序，希尔排序，缩小增量。选择排序，
堆排序（重点）：算法，思想，建初始堆，次筛选法

归并算法（两两合并）基数，快速排序（关键字已经有序，没有优点）。

结束语：笔记我就记这些，这些内容都是考试范围内的，把这些内容看会了，你就可以得三位数的分数，但是，你还需要看教材，把教材上的定义，算法看明白，教材中的第8章和第12章不考，画星号的章节不考，所有递归算法不考，切记！04年的数据结构与以往的三年相比难度增大了不少，我遇测05年的试题难度会维持在这个水平。还有，你应该把近三年的试题做一遍，从试卷中可以发现你知识点的疏漏。