数据结构期末复习重点知识点总结

第一章绪论一、数据结构包括：逻辑结构、存储结构、运算（操作）三方面内容。二、线性结构特点是一对一。树特点是一对多 图特点是多对多数据结构的四种存储结构：顺序存储、链式存储、索引存储、散列存储顺序存储结构和链式存储结构的区别？线性结构的顺序存储结构是一种随机存取的存储结构。线性结构的链式存储是一种顺序存取的存储结构。逻辑结构分类：集合线性树图，各自的特点。或者分为线性结构和非线性结构。算法的特征P13五、时间复杂度(1)i=1;k=0;

while(i<n)

{k=k+10*i;i++;

}

分析：

i=1;//1

k=0;//1

while(i<n)//n

{k=k+10*i;//n-1

i++;//n-1

}

由以上列出的各语句的频度，可得该程序段的时间消耗：

T(n)=1+1+n+(n-1)+(n-1)=3n

可表示为T(n)=O(n)

六、数据项和数据元素的概念。第二章线性表一、线性表有两种存储结构：顺序存储和链式存储，各自的优、缺点。线性表的特点。三、顺序表的插入、思想、时间复杂度o(n)、理解算法中每条语句的含义。（1）插入的条件：不管是静态实现还是动态实现，插入的过程都是从最后一个元素往后挪动，腾位置。静态是利用数组实现，动态是利用指针实现。不管静态还是动态，在表中第i个位置插入，移动次数都是n-i+1。四、顺序表的删除、思想、时间复杂度o(n)、理解算法中每条语句的含义。（1）删除的条件：不管是静态实现还是动态实现，删除的过程都是从被删元素的下一位置向前挪动。静态是利用数组实现，动态是利用指针实现。不管静态还是动态，删除表中第i个元素，移动次数都是n-i。五、顺序表的优缺点？为什么要引入链表？答：顺序表的优点是可以随机存取，缺点是前提必须开辟连续的存储空间且在第一位置做插入和删除操作时，数据的移动量特别大。如果有一个作业是100k，但是内存最大的连续存储空间是99K，那么这个作业就不能采用顺序存储方式，必须采用链式存储方式。六、顺序表和链表合并七、带头结点不为空的单链表的条件是什么？L->next!=NULL;带头结点为空的条件是什么？L->next==NULL;不带头结点不为空的单链表的条件是什么？L!=NULL;不带头结点为空的单链表的条件是什么？L==NULL;带头结点的双循环链表为空的条件是？L->next==L->prior==L头指针、头结点、首元结点（第一个结点）的概念单链表中插入、删除相关操作。双链表的插入和删除。第三章栈和队列一、栈和队列的特点、相同点和不同点。举例说明其不同点。栈的特点：先进后出或后进先出。队列特点：先进先出。栈和队列的相同点是只允许在端点处插入和删除元素不同点：二、循环队列的相关操作。1、置空队列Voidinitqueue(cirqueue*q){q->front=q->rear=0;q->count=0;}2、判空intqueueempty(cirqueue*q){if(q->count==0)return(1);elsereturn(0);}3、判队满intqueuefull(cirqueue*q)｛retuenq->count=maxsize;｝4、入队voidenqueue（cirqueue*q,datatypex）{if(q->count==m)//判队满{printf(“overflow“);exit(0);}q->data[q->rear]=x;q->rear=(q->rear+1)%M;q->count++;}5、出队datatypedequeue(cirqueue*q){if(q->count==0)//判队空{printf(“queuenull“);exit(0);}Temp=q->data[q->font]q->count--;q->front=(q->front+1)%m;//删除队头元素}6、取队头元素datatypegetqueue(cirqueue*q)｛if(q->count==0){printf(“queuenull“);exit(0);}returnq->data[q->font];}三、理解顺序表、顺序栈、顺序队的区别？顺序表：可以在任意合法的位置上做插入和删除。顺序栈：只可以在顺序表的同一端上做插入和删除。顺序队：在顺序表的一端做插入，另一端做删除。理解链表、链栈、链队的区别？链表：可以在任意合法的位置上做插入和删除。链栈：只可以在链表的首结点位置做插入和删除。链队：在链表的首结点位置做删除，尾结点后做插入。四、(题)若用一个大小为6的数组来实现循环队列，且当前的rear和front的值分别为2和5，当从队列中删除一个元素，再插入两个元素后，rear和front的值分别为__2__、__4__。五、(题)设环形队列数组的下标是0～N-1,其头尾指针分别为f和r，则其元素个数为:（r-f+N）%N第五章数组一、数组不能做插入和删除，只能做取值和赋值操作。二、数组只能采取顺序存储（行优先和列优先）三、数组行优先计算公式（下标从0和1开始）（假设每个数据元素占L个存储单元，则数组A中任一元素aij的存储位置为：）LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*LLOC(aij)=LOC(a00)+[i*n+j]*L数组列优先计算公式（下标从0和1开始）LOC(aij)=LOC(a11)+[(j-1)*m+i-1]*LLOC(aij)=LOC(a00)+[j*m+i]*L四、为什么要对特殊矩阵进行压缩存储？答：主要为了节省存储空间。对称矩阵和三角矩阵各长什么样？（对称矩阵以对角线是对称的三角矩阵是非零数组成三角形）六、对称矩阵的压缩存储所需存储空间至少n(n+1)/2。三角矩阵的压缩存储所需存储空间至少n(n+1)/2+1。七、对称矩阵的压缩存储可以存其下三角上的元素公式八、（题）广义表取表头和取表尾第六章树一、（二叉树）树的四个性质性质1：二叉树的第i层上至多有2i-1（i³1）个结点。性质2：深度为k的二叉树中至多2k-1个结点。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。性质4：具有n个结点的完全二叉树的深度k为└log2n┘+1。二、满二叉树和完全二叉树的区别是什么？满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。深度为k的二叉树，最少有k个结点，最多有2k-1深度为k的完全二叉树，最少有2k-1-1k-1层全是满的+1个结点,最多有2k-1k-1层全是满的二叉树的遍历？（128页）四、树.森林和二叉树的相互转换（138页）五、树、森林的遍历（138页）六、赫夫曼树（又称最优二叉树或哈夫曼树）、赫夫曼树编码1.赫夫曼树中，权越大的叶子离根越近，其形态不唯一，但是WPL带权路径长度一定是最小。2.一定要会构造赫夫曼树，在构造好的赫夫曼树上会构造赫夫曼编码。（认真看题目要求）（146页）七、递归算法设计题1．已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写出求一棵二叉树高度的算法。IntBTreeHeight(BiTreeBT){if(BT==NULL)return0;else{h1=BTreeHeight(BT->LChild);h2=BTreeHeight(BT->RChild);if(h1>h2)return(h1+1);elsereturn(h2+1);}}2．已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*Rchild；}BiTNode,*BiTree；BiTreeT；其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写算法，求出二叉树中2度结点个数。intdegree2nodenum(BiTreeT){if(T){if(T->lchild！=NULL&&T->child！=NULL)count++;leafnodenum(l->lchild);leafnodenum(l->rchild);}returncount;}3．已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;BiTreeT；其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，写一算法，求出二叉树中的叶子结点个数。voidBTreeLeaf(BiTreeBT){if(BT){if(BT->LChild==NULL&&BT->RChild==NULL)count++;BTreeLeaf(BT->LChild);//访问左子树BTreeLeaf(BT->RChild);//访问右子树}}或下面算法均可编写递归算法，计算二叉树中叶子结点的数目。intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目

{

if(!T)return0;//空树没有叶子

elseif(!T->lchild&&!T->rchild)return1;//叶子结点

elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数

}//LeafCount_BiTreePPT上的三种遍历递归算法和课本上P131先序递归创建二叉链表。先序遍历的递归算法：voidNLR(BinTreeT){if(T!=null){printf("%c",T->data);NLR(T->Lchild);NLR(T->Rchild);}}中序遍历的递归算法：voidLNR(BinTreeT){if(T!=null){NLR(T->Lchild);printf("%c",T->data);NLR(T->Rchild);}}后序遍历的递归算法：voidNLR(BinTreeT){if(T!=null){NLR(T->Lchild);NLR(T->Rchild);printf("%c",T->data);}}5.给定一棵二叉树，其根指针为root。试写出求二叉树结点数目的算法（递归算法或非递归算法）。 【提示】采用递归算法实现。intcount(BiTreet){if(t==NULL)return0;elsereturncount(t->lchild)+count(t->rchild)+1;}6.以二叉链表为存储结构，写一算法交换各结点的左右子树。【分析】依题意，设t为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算基于后序遍历实现：交换左子树上各结点的左右子树；交换右子树上各结点的左右子树；再交换根结点的左右子树。【算法】voidExchg(BiTree*t){BinNode*p;if(t){P=(*t)->lchild;(*t)->lchild=(*t)->rchild;(*t)->rchild=p;Exchg(&((*t)->lchild));Exchg(&((*t)->rchild));}}7.已知一棵二叉树采用二叉链表结构存储，每个结点的值为整数类型。要求：给出相应的语言描述，在此基础上设计计算二叉树中所有结点值之和的算法。typedefstructlink{intdata;structlink*lchild;structlink*rchild;}bitnode,*bitree;voidsum(bitree*bt,int&s){ if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }第七章图一、图的相关概念，公式图是一种较线性表和树更为复杂的数据数据结构。公式：G(V,E)二、连通、连通图、强连通、强连通图的概念、连通分量、强连通分量连通、连通图、连通分量◆连通：无向图中，若vi到vj有一条路径，则称vi,vj连通。◆连通图：无向图中若对于任意两个不同的顶点vi和vj都连通，称G为连通图。例：无向图G3和无向图G4都是连通图◆连通分量：无向图中G的最大连通子图称为G的连通分量。任何连通图的连通分量只有一个，即是其自身。

非连通的无向图有多个连通分量。◆强连通：有向图中,vi–vj及vj—vi都有路径，则vi,vj强连通。◆强连通图：有向图中若对于任意两个不同的顶点vi和vj都存在从vi到vj及vj到vi的路径，则称G是强连通图。◆强连通分量：有向图的极大强连通子图称为G的强连通分量。任何强连通图的强连通分量只有一个，即是其自身。非强连通的有向图有多个强连通分量。三、图有两种存储结构：邻接矩阵和邻接表。1.给出一个图，必须会写出其邻接矩阵和邻接表。2.要会在邻接矩阵和邻接表上进行深度优先遍历和广度优先遍历。3．各自特点。4．两种存储结构上会做遍历四、最小生成树第九章查找一、折半查找为什么不适用于链表存储结构？从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。二、折半查找的过程、判定树、成功平均查找长度？过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。三、堆积、冲突、同义词的概念同义词：k1≠k2，但H（k1）＝H（k2），即映射到同一哈希地址上的关键码k1和k2为同义词。冲突：k1≠k2，但H（k1）＝H（k2），将不同的关键码映射到同一个哈希地址上，即同义词之间发生地址争夺的现