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