数据结构与算法分析：复习

复习内容基本知识基本技能题型及样题内容基本知识基本技能题型及样题考查目标理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析能够选择合适的数据结构和方法进行问题求解绪论抽象数据类型与数据结构问题、算法和程序算法的代价时间代价空间代价

算法分析渐近算法分析算法的最佳情况、最差情况和平均情况

上限、下限大Ｏ、大Ω和大Θ表示法化简法则线性表、栈和队列线性表的定义和术语线性表的抽象数据类型线性表的存储结构顺序表链表（单链表、双链表、单循环链表、双循环链表）线性表的应用栈顺序栈链式栈队列顺序队列链式队列栈和队列的应用二叉树二叉树的定义与术语满二叉树与完全二叉树的定义满二叉树定理及其推论二叉树结点类前序、中序和后序周游二叉树二叉树的实现方法用指针实现二叉树

用数组实现完全二叉树二叉检索树和平衡二叉树堆Huffman编码树树树的定义与术语树结点类与树类

树的周游方法树的父指针表示法利用UNION/FIND算法解决等价类问题树的实现图图的定义和术语

图的抽象数据类型图的存储结构邻接矩阵和邻接表图的两种周游算法深度优先和广度优先算法图的拓扑排序算法基于递归的拓扑排序算法基于队列的拓扑排序算法

最短路径问题单源最短路径的Dijkstra算法每对顶点间最短路径的Floyd算法最小支撑树Prim算法和Kruskal算法内排序冒泡排序选择排序插入排序Shell排序快速排序归并排序堆排序基数排序排序问题的下限查找查找的基本概念顺序查找法折半查找法B树散列方法散列函数冲突解决策略内容基本知识基本技能题型及样题分析简单程序段的运行时间代价根据给定的二叉树写出其前序、中序和后序周游序列根据二叉树的前序和中序周游序列，构造出对应的二叉树根据二叉树的中序和后序周游序列，构造出对应的二叉树根据给出的数据序列构造二叉检索树根据给出的数据序列构造一个堆根据给定的字母/频率表构造Huffman树，并给出各字母的Huffman编码根据一棵树的父指针表示构造出该树利用UNION/FIND算法解决等价类问题根据一棵树构造对应的二叉树根据图构造邻接矩阵或邻接表根据邻接矩阵或邻接表构造图构造图的深度优先搜索树（或写出图的深度优先搜索顶点序列）构造图的广度优先搜索树（或写出图的广度优先搜索顶点序列）根据给定的图构造顶点的拓扑序列用Dijkstra算法求单源最短路径用Floyd算法求每对顶点间的最短路径按照Prim算法构造图的最小支撑树按照Kruskal算法构造图的最小支撑树给出一组关键码，写出按某种排序算法进行排序的每一趟的结果根据三种不同的启发式规则访问自组织线性表在散列表中插入、检索和删除记录内容基本知识基本技能题型及样题单项选择题对一棵二叉检索树进行________周游得到的结点序列是一个有序序列。(A)前序(B)中序(C)后序(D)层序判断题若一个叶结点是某二叉树的中序周游序列的最后一个结点,则它也是该二叉树的前序周游序列的最后一个结点。()

填空题若某二叉树有30个叶结点,另有30个结点仅有一个子结点,则该二叉树总共有________个结点。解析题已知二叉树的前序和中序周游序列如下,画出该二叉树。算法设计题编写算法求