数据结构速成攻略.doc

数据结构速成攻略考试题型：选择、填空、简答、算法。第1章 绪论1、存储结构（物理结构）： 顺序存储结构（特点：只存数据不存关系，其关系体现在存储位置上） 和 链式存储结构（特点：需存数据及其关系）2、逻辑结构： 集合 、 线性结构 、 树型结构 、 图型结构（其中树和图属于非线性结构）3、数据类型:原子类型（非结构，可分解）、结构类型（不可分解）4、算法的时间复杂度（一个算法的时间耗费的数量级）、空间复杂度与问题规模n有关 Eg： for（i=0；in;i+） for(j=0;jm;j+) Aij=0; 则时间复杂度为O(m*n)第2章线性表1、 线性表的顺序存储结构（随机存取）：顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。设每个元素需占用L个存储单元，则第i个数据元素ai的存储位置为Loc（ai）=Loc（ai）+L*（i-1）。当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，移动元素的个数取决于插入或删除元素的位置。若表长为n，则插入、删除操作平均移动个元素，算法时间复杂度为O（n）。优点：存储密度大（1），存储空间利用率高，便于访问。缺点：插入或删除元素时不方便。宜做查找这样的静态操作。若线性表长度变化不大（插入、删除等操作在表尾进行），且主要操作是查找，则采用顺序表。2、线性表的链式存储结构（顺序存取）：链式存储时，相邻数据元素可随意存放（逻辑相邻物理不一定相邻），但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。每个元素由结点（Node）构成，它至少包括两个域，数据域（data）：存储数据元素信息；指针域（link）：存储直接后继存储位置（指示数据元素之间的逻辑关系）。整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置。最后一个数据元素没有直接后继，现行链表中最后一个结点的指针为“空”（NULL）。优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（next=p-next; p-next=s;删除操作(核心语句)：q=p-next; p-next=q-next; free(q);在单链表中，除了首元结点外，任意结点内的存储位置由前驱结点的后继指针指示。在单链表中设置头结点的作用是简化链表操作。4、L为指向表头结点的指针，p为指向表尾结点的指针，p满足的条件（判断是哪类链表）：单链表 p-next=NULL循环链表（表中最后一个结点的指针域指向头结点，整个链表形成一个环） p-next=L双向链表（结点中有两个指针域，其一指向直接后继，另一指向直接前驱） p-next=NULL双向循环链表 p-next=NULL5、L为指向表头结点的指针，链表为空，应满足条件：单链表 L-next=NULL循环链表 L-next=L双向链表 L-next=NULL双向循环链表 L-next=NULL & L-prior=NULL第3章栈和队列1、栈 栈是限定仅在表尾进行插入（进栈Push）或删除（出栈Pop）操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的。2、队列队列是一种先进先出的线性表。队列只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为对头。3、栈和队列的顺序存储和链式存储 顺序栈（栈的顺序存储结构）是利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。（以栈顶指针top=0表示空栈） 顺序栈中入栈操作需判断栈满，出栈操作需判断栈空。链栈（栈的链式存储结构）是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。链栈中指针方向指向前驱结点。链栈入栈操作（不需判断栈满）：p-data=x;/设置新结点的值 p-next=top;/将新元素插入栈中 top=p；/将新元素设置为栈顶链栈出栈操作（需判断栈空）：p-top;/指向被删除的栈 top=top-next;/修改栈顶指针 free（p）；4、循环队列，队空、队满的条件设数组维数M，两个指针front（队头指针）、rear（队尾指针）队空：front=rear队满：（rear+1）%M=front 入队列：rear=（rear+1）%M出队列：front=（front+1）%M循环队列中是否能插入下一个元素与队头指针与队尾指针有关。循环队列用数组Am存放其元素值，已知队头指针front、队尾指针rear，则当前队列中元素个数是（rear-front+m）%m。第4章字符串1、字符串的操作StrAssign(&T,chars):生成一个其值等于chars的串T。StrCopy(&T,S):由串S复制得串T。StrEmpty（S）:若S为空串，则返回TRUE，否则返回FALSE。StrCompare（S,T）:若ST则返回值0,若S=T则返回值=0，若ST则返回值=0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分。二叉树的五中形态（由三个结点构成）：空树、只含根节点、右子树为空树、左子树为空树、左右子树均不为空树。3、二叉树的性质在二叉树的第i层上至多有2i-1个结点（i1）。深度为k的二叉树至多有2k-1个结点（k1）。对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则n0=n2+1。4、二叉树的顺序存储和链接存储二叉树的顺序存储特点（仅适用于完全二叉树）：一组地址连续的存储单元存储各结点(定义一个一维数组)；自上而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储。缺点：空间利用率太低！二叉链表：链表的头指针指向二叉树的根节点。结点结构至少包含：数据域和左右孩子指针域 lchild data rchild在含有n个结点的二叉链表中有n+1个空链域。三叉链表结点结构包含：数据域、左右孩子指针域和双亲指针。5、在二叉树的的先序、中序和后续三种遍历序列中，已知二叉树的先序遍历序列和中序遍历序列，可求得另一种序列。解题思路：由先序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应先序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。先序遍历二叉树：访问根节点。先序遍历左子树。先序遍历右子树。中序遍历二叉树：中序遍历左子树。访问根节点。中序遍历右子树。后序遍历二叉树：后序遍历左子树。后序遍历右子树。访问根节点。先序序列的第一个结点是根节点，中序序列根节点处于左右子树的中序序列之间。6、中序线索化二叉树（书132）指向结点前驱和后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。7、完全二叉树的概念和性质一颗深度为k且2k-1个结点的二叉树称为满二叉树（没有度为1的结点）。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。完全二叉树的特点：叶子结点只可能在层次最大的两层上出现。对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。具有n个结点的完全二叉树的深度为log2n+1。如果对一颗有n个结点的完全二叉树（深度为log2n+1）的结点按层序编号（从第一层到第log2n+1层，每层从左到右），则对任意几点i（1in），有：如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是结点i/2。如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。如果2i+1n，则结点i无右孩子，否则其右孩子是结点2i+1。Eg：完全二叉树的第五层有6个叶子。求该树结点个数最多是多少。最大层高：6（叶子只可能存在在最高2层）前5层结点数：25-1=31第5层的结点数：25-1=16则第6层应有结点数：（16-6）*2=20该树结点个数最多是：31+20=51个8、构造赫夫曼树为字符进行编码，并求出带全路径长度WPL。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度计为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi(i=1,2,.n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。构造：对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。重复两步，直到集合F中只有一棵二叉树为止。9、森林的遍历先序遍历森立：访问森林中第一棵树的根节点先序遍历第一棵树中根节点的子树森林先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历森立：中序遍历森立中第一棵树的根节点的子树森林访问第一棵树的根节点中序遍历除去第一棵树之后剩余的树构成的森林。10、二叉树与森林的转换 二叉树的根结点是森林中第一棵树的根结点二叉树的左子树是由第一棵树根结点的子树森林所对应的二叉树二叉树的右子树是由除第一棵树之外其余树组成的森林所对应的二叉树11、赫夫曼编码任意构造一棵以所有要编码的字符为叶子结点的二叉树，并且约定：左分支表示 0；右分支表示 1 。如果把从根结点到某叶子节点的路径上分支字符组成的字符串作为相应字符的编码，那么可以得到一种前缀编码。注意：每个字符的编码长度等于从根结点到该叶子结点的路径长度。第7章 图1、熟悉图的两种存储方法，图的邻接矩阵表示和图的邻接表表示（见手写）2、画出无向图的邻接矩阵（或邻接表），并根据邻接矩阵（或邻接表）写出从某顶点出发进行深度优先搜索（或广度优先搜索）所得的序列（见手写）3、生成连通网的最小生成树的普里姆算法和克鲁斯卡尔算法，哪种算法适于边稀疏的连通网，并简述该算法。构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。普里姆算法基本思想：Step1：取图中任意一个顶点 v 作为生成树的根；Step2：往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小；Step3：继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。普里姆算法基本思想：Step1：取图中任意一个顶点 v 作为生成树的根；Step2：往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小；Step3：继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。比较两种算法：普里姆算法：O(n2)、适用于稠密图；克鲁斯卡尔算法：O(eloge)、适用于稀疏图4、用克鲁斯卡尔算法（或普里姆算法）求出最小生成树，写出求解过程。（见手写）第9章查找1、构造平衡的二叉排序树（