复旦大学软件工程考研(MSE)数据结构复习资料

数据结构2016MSE考研冲刺课程安排课程介绍栈、队列和向量树查找排序图课程目的（以最小代价）通过考试！不是成为专家不是初学授课试题结构考试满分60分考试题型：问答、分析、编程样题－问答和编程题插入排序、选择排序、冒泡排序、快速排序中最快的排序方法是________试论述什么叫Hash冲突及有那些处理方法编程实现对二叉树所有节点的统计课程安排课程介绍栈、队列和向量树查找排序图链表、栈和队列大纲描述：单链表,双向链表,环形链表,带哨兵节点的链表栈的基本概念和性质,栈ADT及其顺序,链接实现;栈的应用;栈与递归;队列的基本概念和性质,队列ADT及其顺序,链接实现;队列的应用;向量基本概念和性质;向量ADT及其数组、链接实现;线性表基本概念和性质线性表是n个数据元素的有限序列常见线性表包括数组、链表、栈、队列等线性表的两种实现方式顺序链式对比：插入（有序、无序）、删除、查找、读取环形链表环形链表又称循环列表，是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点栈的基本概念和性质栈：栈是限定仅在表尾进行插入和删除操作的线性表后进先出特性（LIFO）栈顶、栈底、出栈、入栈例题设有一个栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则栈的容量至少应为多少？答案：3栈的基本概念和性质设计递归问题的非递归算法一般需要用到栈机制三个数a、b、c进栈，不可能出现c、a、b顺序出栈例题若某栈的输入序列为a、b、c，则所有可能的出栈序列有___种，所有不可能的出栈序列有____种。答案：5，1例题若栈的输入序列为1,2,3,4，则——是不可能的栈输出序列之一。答案：4，3，1，2习题若某栈的输入序列为a、b、c、d，则所有可能的出栈序列有___种，所有不可能的出栈序列有____种。请写出所有可能的序列和不可能的序列。栈的应用数制转换十进制数字与d进制数字的转换N=(Ndivd)×d+Nmodd其中div为整除，mod为求余。算法：将算法3.1中8换成d例题十进制数1167等于八进制数——？答案：2217思路：计算方法：除余倒排法验证方法：指数相加法习题十进制数1167等于七进制数——？栈的应用表达式求值：中缀表达式转后缀表达式后缀表达式求值三种表达式：前缀表达式+ab中缀表达式a+b后缀表达式ab+例题中缀表达式a+b×c–d转为后缀表达式是————？答案：abc×＋d－例题中缀表达式（a+b）×c–d转为后缀表达式是————？答案：ab＋c×d－思路：数字位序不变，运算符位置改变后缀表达式无括号，运算顺序同中缀表达式习题中缀表达式A-(B+C)*D/E的后缀形式是_________________。练习中缀表达式a*(b+c)/d转为后缀表达式是————？例题计算后缀表达式12+4*2/的值为——？答案：6思路：顺序计算或转换为中缀表达式计算习题计算后缀表达式32－4*2/3＋的值为——？递归一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数优点：结构清晰、程序易读、正确性容易得到证明缺点：效率相对较低队列的基本概念和性质队列：队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表先进先出特性（FIFO）队尾、队头、入队、出队例题在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是——，队尾元素是————。答案：c，d双向队列双向队列：亦称双端队列（Deque）是限定插入和删除操作在表的两端进行的线性表可以用于包装产生栈和队列课程安排课程介绍栈、队列和向量树查找排序图树大纲描述：树的基本概念和术语；树的前序、中序、后序、层次序遍历；二叉树及其性质；普通树与二叉树的转换；树的存储结构,标准形式;完全树(completetree)的数组形式存储;树的应用，Huffman树。树的基本概念和术语树：是n（n≥0）个结点的有限集在任意一棵非空树中：1.有且仅有一个特定的称为根的结点2.当n1时，其余结点可以分为m（m0）个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树树属于层次结构数据结构树的基本概念和术语节点标签父节点、子节点、兄弟节点、祖先节点、子孙节点路径、树枝根、叶子次数内部节点、外部节点树的次数、K次树节点层次、树的高度和深度子树有序树、无序树森林、果园例题例题列出如上图所示树的所有叶子结点答案：K,L,F,G,M,I,J列出如上图所示树的所有分支结点答案：A,B,C,D,E,H树A为几次树？子树B呢？答案：3，2前页图所示树的高度为多少？答案：4树的基本概念和术语如果将树中结点的各子树看作从左到右有序的,则该树为有序树(orderedtree),否则为无序树。森林(forest)是m棵互不相交的树的集合。如果把一棵树的根砍去，剩下的部分就是森林。如果原来的树是有序的,则砍去根后的森林也是有序的,此时称该森林为有序森林或果园。二叉树及其性质二叉树（BinaryTree）另一种树形结构，特点是每个结点至多只有二棵子树，且子树有左右之分，其次序不能任意颠倒二叉树可能的五种基本形态二叉树及其性质在二叉树的第i层上至多有2i－1个结点（i≥1）例题一棵二叉树第五层上至多有多少个结点？至少多少？答案：16，1二叉树及其性质深度为k的二叉树至多有2k－1个结点（k≥1）例题深度为n(n0)的二叉树最多有_____个结点。答案：2n-1例题一棵深度为5的二叉树至多有多少个结点？至少多少？答案：31，5例题高度为h(h0)的二叉树最少有________个结点？答案：h二叉树及其性质对于任何二叉树,如果叶子节点数为n0,度为2的节点数为n2,则n0=n2+1例题在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n2=________。答案：n0－1例题若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为______________。答案：9例题若一二叉树有2度结点100个，则其叶结点有多少个？答案：101例题若二叉树中度为2的结点有15个，度为1的结点有10个，共有多少个结点？答案：41例题在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有__________个叶结点。答案：6构造法二叉树及其性质满二叉树：一棵深度为k且有2k－1个结点的二叉树可以对满二叉树的结点进行连续编号，约定编号从根开始，自上而下，自左而右。完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。二叉树及其性质完全二叉树特点：叶子结点只可能出现在层次最大的两层上对任一结点，若其右分支下子孙的最大层次为l，其左下分支的子孙的最大层次必为l或者l＋1。深度为k的完全二叉树第k层最少1个结点，最多2k-1-1个结点；整棵树最少2k-1个结点，最多2k-2个结点例题若某完全二叉树的深度为h，则该完全二叉树中至少有______个结点。答案：2h-1例题若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有______个结点。答案：25-1+3＝34例题一个具有767个结点的完全二叉树，其叶子结点个数为____。答案：384分析：可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n=n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n=2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝[（n＋1）/2]，就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得：384。二叉树及其性质具有n个结点的完全二叉树的深度为[log2n]+1例题具有2000个结点的二叉树，其深度至少为_________。答案：11二叉树及其性质如果含有n1个节点的二叉树的高度为[log2n]＋1,将其所有结点按层次序编号,则对于任一节点j(1jn),有如果j=1,则节点j是树的根,无双亲;如果j1,则其父节点parent(j)是节点[j/2]如果2jn,则节点j无左子节点;否则其左子节点为2j如果2j+1n,则节点j无右子节点;否则其右子节点为2j+1证明完全树的数组形式存储完全树的数组形式存储算法将其编号为i的结点元素存储在一维数组下标为i－1的分量中例题已知数组[20,30,19,87,30,40]表示一棵完全二叉树，请画出该树。练习答案树的遍历树的遍历按某种搜索路径巡访树中每个结点，使每个结点均被访问一次仅且一次二叉树的遍历可分为前序、中序、后序、层次序等普通树的遍历可以分为先根、后根、层次序等树的遍历二叉树的遍历前序、中序、后序定义层次序：从上而下，从左至右常见问题已知树写遍历结果已知遍历结果画树依据：二叉树的前序和中序遍历可以唯一确定一棵二叉树思路：前序定根，中序定左右递归和非递归算法实现例题写出左图所示二叉树的前序、中序、后序、层次序遍历结果例题答案前序：ABDCEFG中序：DBAECFG后序：DBEGFCA层次序：ABCDEFG例题假设一棵二叉树的前序遍历为EBADCHGFIKJ，中序遍历为ABCDEFGHIJK，请画出该树。例题答案树的遍历普通树的遍历前根：先遍历根结点，再依次前根遍历各棵子树后根：先后根遍历各课子树，再遍历根结点已知树写遍历结果已知遍历结果画树思路：先根定根，后根定子树例题写出如右图所示树的先根、后根、层次序遍历结果例题答案前序：ABECFGHD后序：EBFHGCDA层次序：ABCDEFGH练习给出如图所示树的先根、后根和层次序遍历结果练习答案前根：ABEFHIGCJKLDMNOQP后根：EHIFGBKLJCNQOPMDA层次序：ABCDEFGJMHIKLNOPQ例题画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ树的后根次序访问序列为DIAEKFCJHBG例题答案普通树与二叉树的转换对于任意k次树到相应二叉树的转换算法对于具有子节点n1,n2…nk的节点n,将n1作为其左子节点,且kj+1作为kj(1jk-1)的右子节点思路：“不同层在左，同层在右”普通树与二叉树的转换对于任意森林到相应二叉树的转换算法为设T=(T1,T2…..Tm)为m(m0)棵树的序列,而BT(T1,T2…..Tm)为相应的二叉树,则如果m=0,则BT为空树如果m0,则T1的根节点就是BT的根节点,而BT的左子树是T1的子树T11,T12…T1K转换成的BTl(T11,T12…T1K),其右子树为BTr(T2…..Tm)例题将下页图所示森林转换为等价的二叉树例题例题答案练习将如图所示树转换为二叉树练习答案Huffman树Huffman树：又称最优树，是一类带权路径长度最短的树基本概念：树的路径长度：从根到每一结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记做WPL。Huffman树基本概念：假设有n个权值wi，试构造一棵有n个叶子结点的二叉树，每个叶子的结点带权为wi，则其中WPL最小的二叉树称为最优二叉树或赫夫曼树算法见下页Huffman算法(1)由给定的n个权值{w0,w1,w2,…,wn-