?单源起点最短路径的Dijkstra算法?最短路径的任一局部也是最短路径。?每两点间最短路径的Floyd算法?定义P(i, j, k)表示从顶点vi到顶点vj经序号不大于k的顶点的最短路径，P(i, j, -1)表示从顶点vi到顶点vj的直达弧，则有：P(i, j, k) = min{P(i, j, k-1), P(i, k, k-1) + P(k, j, k-1)}从顶点vi到顶点vj的最短路径即P(i, j, n-1)。最短路径（2009年统考试题，10’）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；③重复步骤②，直到u是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。?有向无环图??拓扑排序关键路径点和弧的关系?ve[i] = max{ve[j]+Wji| vi是vj的邻接点，Wji是弧
《数据结构》考研精要教师：彭四伟?逻辑结构与逻辑结构?逻辑结构的比较?物理结构的比较?图?????邻接矩阵和邻接表图的遍历最小生成树最短路径关键路径折半查找法散列表的构造、查找B-树的结构、查找、插入和删除B+树的结构简单插入排序法交换排序法希尔排序法快速排序法堆排序法二路归并排序法各种排序方法的比较?算法复杂度?复杂度分析?复杂度比较?线性表?存储结构?操作实现?应用问题?查找?????栈、队列和数组?栈和队列的性质?栈和队列的应用?特殊矩阵的实现?内排序????????树和二叉树?????二叉树的性质二叉树的遍历树和二叉树的关系二叉排序树平衡二叉树统考大纲分析?1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。?2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。?3.能够选择合适的数据结构和方法进行问题求解，具备采用C 或C++或JAVA 语言设计与实现算法的能力。统考大纲分析2009年分值分布2010年分值分布历届试题分析2011年分值分布2009年选择题分布内排序, 4栈和队列, 2查2010年选择题分布内排序, 4栈和队找, 2列, 4查找, 2二叉图, 2树, 8图, 4二叉树, 8查找, 2内排序, 4图, 2栈和队列, 4复杂度, 2历届试题分析二叉树, 820011年选择题分布
（2010年统考试题）对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是A：该树一定是一棵完全二叉树B：树中一定没有度为1的结点C：树中两个权值最小的结点一定是兄弟结点D：树中任一非叶结点的权值一定不小于下一级任一结点的权值?顶点、弧、邻接???????出度、入度有向图、无向图（边）完全图、稀疏图、稠密图网、AOE网、AOV网路径、简单路径、回路、简单回路连通图、强连通图、连通分量、强连通分量生成树图的术语（2009年统考试题）下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1 A.只有I B. 只有II C.I和II D.I和III（2010年统考试题）若无向图G-（V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是A ：6 B：15 C：16 D：21（2011年统考试题）下列关于图的叙述中，正确的是Ⅰ. 回路是简单路径Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路A. 仅ⅡB. 仅Ⅰ、ⅡC. 仅ⅢD. 仅Ⅰ、Ⅲ??深度优先遍历广度优先遍历图的遍历??MST性质Prim算法?从任一顶点出发，逐级输出最短边。?Kruskal算法?按权值从小到大输出不构成回路的边。最小生成树
???线索二叉树是针对约定的遍历序利用空闲左子指针指向遍历序上的前一个结点利用空闲右子指针指向遍历序上的后一个结点线索二叉树（2010年统考试题）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是b左子右兄弟efjkncdilopqmbefjnkoclpqmid树、森林和二叉树（2009年统考试题）将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系II.兄弟关系III. u的父结点与v的父结点是兄弟关系A.只有II B.I和II C.I和III D.I、II和III （2011年统考试题）已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是A. 115 B. 116 C. 1895 D. 1896????二叉排序树的性质二叉排序树的查找二叉排序树的插入二叉排序树的删除二叉排序树
（2011年统考试题）对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是A. 95, 22, 91, 24, 94, 71 B. 92, 20, 91, 34, 88, 35C. 21, 89, 77, 29, 36, 38 D. 12, 25, 71, 68, 33, 34?平衡调整算法????LL－RRR－LLR－LRRL－RL平衡二叉树（2010年统考试题）在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是A：13，48 B：24，48 C：24，53 D：24，90设输入序列：45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 873239324516323216161645774577453939384545386844947777949421213321384444683844688794333987?哈夫曼树?性质：没有度为1的结点?哈夫曼算法?优先合并最小结点?哈夫曼编码哈夫曼树和哈夫曼算法
????装载因子散列函数冲突解决策略散列表的查找散列表（2010年统考试题，10’）将关键字序列（7、8、11、18、9、14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H（key）=（key×3）MODT，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7问题：（1）请画出所构造的散列表；（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。（2011年统考试题）为提高散列(Hash)表的查找效率，可以采取的正确措施是Ⅰ.增大装填（载）因子Ⅱ.设计冲突（碰撞）少的散列函数Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象A.仅ⅠB.仅ⅡC.仅Ⅰ、ⅡD.仅Ⅱ、Ⅲ?B-树对一棵3阶B-树，除根结点外，每个结点中的子树个数不少于2，不多于3，即每个结点中最多含有2个关键字，最少含有1个关键字。306515244789917212833384955769298设输入序列：45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 26构造3阶B-树如下：32321632323245444444454444443232324477324477161645774577942121323232323238323832383877777777777716161638383844454545457794949494161616161621212116262126162116333321383333383838393938393939394545454545456894686868949494949494