数据结构考试复习总结.docx

《数据结构考试复习总结.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1，数据结构这几种结构逻辑结构存储结构时间复杂度2，线性表-》链表-》顺序表理解线性表，出的题目会很难，自己好好复习链式存贮是什么，顺序存储是什么，他们的区别顺序存储：将线性表中的元素依次存储到数组中----顺序存储方式--顺序表。链式存贮：用不连续的、或连续的存储单元存储线性表元素；每个数据元素后，加上一个地址域，此地址为其直接后继的地址；数据元素和地址域组成结点（节点）。插入，删除，两个链表。合并，逆转，理解之上的应用选择题，简单的线性表的性质，编程题，叉积，补积题目都是链表的，数组的长度是固定不变的，数组是线性表的一种。而线

2、性表有多种形式，其长度可变。线性表与数组的区别？2，两种特殊的线性表，理解栈和队列的特点？栈的特性后进先出(LIFO--LastInFirstOut)，或先进后出(FILO--FirstInLastOut)栈是操作受限的线性表。栈的操作模拟表达式求解过程（画出来）队列会画这玩意}递归，会看他的那个玩意2，掌握这玩意；不需要编程广义表;取表头，取表尾会过程广义表的定义【定义】L是由n个元素a1,a2,…,an组成的有限序列，其中：ai是一个原子（不可分割的元素），或者是一个广义表（子表）；记作：L=(a1,a2…an)，称n(n>=

3、0)为表的长度。N=0时L为空表，记作：L=()。广义表的存储结构得绘画3，树的性质，选择题1、·每个节点有零个或多个子节点；2、·没有父节点的节点称为根节点；3、·每一个非根节点有且只有一个父节点；4、除了根节点外，每个子节点可以分为多个不相交的子树。【性质1】第i层的结点数≤2i-1；【性质2】高度为k（k≥1）的二叉树的结点总数≤2k-1；【性质3】设二叉树的叶子结点数为n0，度为2的结点数为n2，则:n0=n2+1。有n个（n≥1）结点的完全二叉树的高度为:对完全二叉树进行层次编号，编号为i的结点，若左孩子存在，则其左孩子

4、的编号为：2i；若右孩子存在，则其右孩子的编号为：2i+1；其父结点的编号为：i/2二叉树性质线性序列，中序序列三种遍历方法，必须得会森林，树和森林和二叉树的转化（画图）必考应用题会有画图哈夫曼树，会构建哈夫曼树查找排序，都得掌握，每种方法的潮涨方法，全都是重点平衡二叉树散列表，散列表的冲突如何处理，应用题最后一张，可能不考编程题，写出过程选择题，编程题，应用题编程题;线性表，树，应用题：树之类的