资源描述：
《复旦大学软件工程考研(MSE)数据结构复习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构2016MSE考研冲刺课程安排课程介绍栈、队列和向量树查找排序图课程目的（以最小代价）通过考试！不是成为专家不是初学授课试题结构考试满分60分考试题型：问答、分析、编程样题－问答和编程题插入排序、选择排序、冒泡排序、快速排序中最快的排序方法是________试论述什么叫Hash冲突及有那些处理方法编程实现对二叉树所有节点的统计课程安排课程介绍栈、队列和向量树查找排序图链表、栈和队列大纲描述：单链表,双向链表,环形链表,带哨兵节点的链表栈的基本概念和性质,栈ADT及其顺序,链接实现;栈的应用;栈与递归;队列的基本概念和性质,队列ADT及其顺序,链接实现;队
2、列的应用;向量基本概念和性质;向量ADT及其数组、链接实现;线性表基本概念和性质线性表是n个数据元素的有限序列常见线性表包括数组、链表、栈、队列等线性表的两种实现方式顺序链式对比：插入（有序、无序）、删除、查找、读取环形链表环形链表又称循环列表，是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点栈的基本概念和性质栈：栈是限定仅在表尾进行插入和删除操作的线性表后进先出特性（LIFO）栈顶、栈底、出栈、入栈例题设有一个栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则栈的容量至少
3、应为多少？答案：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为整除，mo
4、d为求余。算法：将算法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的后缀形式是___
5、______________。练习中缀表达式a*(b+c)/d转为后缀表达式是————？例题计算后缀表达式12+4*2/的值为——？答案：6思路：顺序计算或转换为中缀表达式计算习题计算后缀表达式32－4*2/3＋的值为——？递归一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数优点：结构清晰、程序易读、正确性容易得到证明缺点：效率相对较低队列的基本概念和性质队列：队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表先进先出特性（FIFO）队尾、队头、入队、出队例题在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此
6、时的队头元素是——，队尾元素是————。答案：c，d双向队列双向队列：亦称双端队列（Deque）是限定插入和删除操作在表的两端进行的线性表可以用于包装产生栈和队列课程安排课程介绍栈、队列和向量树查找排序图树大纲描述：树的基本概念和术语；树的前序、中序、后序、层次序遍历；二叉树及其性质；普通树与二叉树的转换；树的存储结构,标准形式;完全树(completetree)的数组形式存储;树的应用，Huffman树。树的基本概念和术语树：是n（n≥0）个结点的有限集在任意一棵非空树中：有且仅有一个特定的称为根的结点当n>1时，其余结点可以分为m（m>0）个互不相交的有限集
7、，其中每个集合本身又是一棵树，并且称为根的子树树属于层次结构数据结构树的基本概念和术语节点标签父节点、子节点、兄弟节点、祖先节点、子孙节点路径、树枝根、叶子次数内部节点、外部节点树的次数、K次树节点层次、树的高度和深度子树有序树、无序树森林、果园例题例题列出如上图所示树的所有叶子结点答案：K,L,F,G,M,I,J列出如上图所示树的所有分支结点答案：A,B,C,D,E,H树A为几次树？子树B呢？答案：3，2前页图所示树的高度为多少？答案：4树的基本概念和术语如果将树中结点的各子树看作从左到右有序的,则该树为有序树(orderedtree),否则为无序树。森林(f
8、orest)是m棵互不相
