数据结构 复习要点
题型
一、选择题（15*2分）
二、填空题（5*2分）
三、判断题（5*2分）
四、简答分析题（4*5分）
单链表的概念
单链表是一组任意的存储单元,存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中的任意位置，为了能正确表示元素之间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储其后继元素的所在的地址信息，这个地址信息称为指针，这两部分组成了数据元素的存储映像，称为结点。
二叉树遍历及通过遍历结果构造二叉树
前序——根左右
中序——左根右
后序——左右根
层序——先访问的节点其左右孩子也先访问
可以根据前序中序——树，也可以根据中序后序——树（必须有中序）。 哈夫曼树和WPL
哈夫曼树：给出一组具有确定权值的叶子结点，可以构造出不同的二叉树，将其中带权路径长度最小的二叉树。
WPL：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度。
折半查找的前提和方法
前提:
1、 线性表中的记录必须按关键码排序。
2、 必须采用顺序存储。
方法：
在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区查找，不断重复上述工程（递归），直到查找成功，或查找的区域无记录，查找失败。
五、综合题(3*10分)
Prim算法
P162 最小生成树算法
拓扑排序
