数据结构复习.docx

1、 线性结构 :结构中的数据元素之间存在一对一的关系。2、数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。例1 复数的数据结构定义如下： Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C23、 元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。4、 程序=算法+数据结构5、 算法的五个特性（1）有穷性 （2）确定性 （3）可行性 4）输入 5）输出 6、算法效率的度量：时间复杂度 空间复杂度7、线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； 线性表：是n个数据元素的有限序列。同一线性表中的元素必须是同一类型的；问2：结构体中间的那个struct LNode 是什么意思？ 答2：在最后一行的“缩写”LNode还没出现之前，只能用原始的struct LNode 来进行变量说明。此处说明了指针分量*next的数据类型是struct LNode 问题：一个旅行社要从n名旅客中选出一名幸运旅客，为他提供免费环球旅行服务。方法是，大家站成圈，然后选定一个m，从第1个人开始报数，报到m时，这个人OUT，然后从下一个人开始重新从1报数，重复这个过程，直到最后剩下一个人就是幸运之星。问题就是谁是幸运者呢？或者说是怎样才能赢大奖。main()int a50,n; int *p; int i, k, m; printf(please input people number:); scanf(%d,&n); /总人数为n p=a; /p指向数组a的首地址 for(i=0;in;i+) *(p+i)=i+1; /数组初始化 i=0;k=0;m=0; while(mn-1) if(*(p+i)!=0) k+; if(k=3) /报数为k=3的人出列 *(p+i)=0; k=0; m+; /m为出列的人数 i+; if(i=n) i=0; /i = n时，循环 while(*p= = 0) p+; printf(the last people number is:%dn,*p);8、 栈必须按“后进先出”的规则进行操作 、栈只允许在表尾一端进行插入和删除 9、 通常称往栈顶插入元素的操作为“入栈”、称删除栈顶元素的操作为“出栈”。 10、从数据结构的角度看，栈和队列也是线性表、栈(Stack) 是限定仅在表尾进行插入或删除操作的线性表。11、队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。 队首(front) ：允许进行删除的一端称为队首。队尾(rear) ：允许进行插入的一端称为队尾。即队列的修改是依先进先出的原则进行的12、 接受用户从终端输入的程序或数据，并存入用户的数据区。 退格符“#” 退行服“”13、树的存储结构双亲表示法：假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲在链表中的位置。 孩子表示法：多重链表，每个指针指向一棵子树的根结点。孩子兄弟表示法：二叉树表示法，链表中两个链域分别指向该结点的第一个孩子和下一个兄弟结点。（左边为孩子节点，右边为兄弟节点）14、先序遍历（T L R） 若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树 15、中序遍历（L T R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树16、后序遍历（L R T）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点17、Huffman树的构造 在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和； 在F中删除这两棵树，同时将新得到的树加入F中； 重复、，直到F只含一颗树为止。18、 构造Huffman树时，为了规范，规定F=T1,T2, ,Tn中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。19、图的遍历通常分为深度优先查找和广度优先查找两种方式。深度优先：访问指定的某顶点v，把它当作当前的顶点 访问当前顶点的下一个未访问过的邻顶点 重复2，知道当前顶点的所有邻接点都被访问完 沿搜索路径回退，退到尚有邻接点未被访问的结点，将该结点作为当前结点，重复以上步骤，直到所有结点都访问过为止广度优先：先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问到；由近到远访问，依次访问和v有路径长度为1、2、3.的顶点。图中尚有顶点未访问到，则另选图中一个未曾被访问的顶点做起点，重复上述过程，直至所有顶点被访问完为止。20、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历21、构造最小生成树的算法有许多，基本原则是：l 尽可能选取权值最小的边，但不能构成回路；l 选择n-1条边构成最小生成树。21、 最小生成树的算法思想：普里姆(Prim)算法l 若从顶点v0出发构造，U=v0，TE=；l 先找权值最小的边(u，v)，其中uU且vV-U，并且子图不构成环，则U= Uv，TE=TE(u，v) ；l 重复 ，直到U=V为止。则TE中必有n-1条边， T=(U，TE)就是最小生成树。22、拓扑排序 算法 在AOV网中选择一个没有前驱的顶点且输出； 在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ； 重复、，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。23、关键路径：从源点到汇点的路径长度最长的路径。关键路径上的所有活动都是关键活动。 Vi事件的最早发生时间ve（i） 正向取最大值 Vi事件的最迟发生时间vl（i） 逆向取最小值 活动ai的最早开始时间（弧表示ai） e(i)=ve(j) 活动ai的最迟开始时间:l(i)=vl(k)-ai24、最短路径：基本思想：从图的给定源点到其它各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径长度。 即按长度递增的次序生成各顶点的最短路径，先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，依此类推，直到求出长度最长的最短路径。25、在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。 A1/2 B2 C1 D426、G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点设G为具有N个顶点的无向连通图，则G中至少有_N-1_ 条边图没有顺序映像的存储结构，但可以借助数组的数据类型来表示元素之间的关系27、关键路径：从源点到汇点的路径长度最长的路径。28、树型结构是一类非常重要的非线性结构。29、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行排序，根为1号，则49号结点的左孩子编号为_98_已知二叉树有50个叶结点，且仅有一个孩子的结点数为30个，求树的总结点数_129_二叉树有50个叶子结点，则二叉树的总结点数至少有_99_个完全二叉树的第8层有8个结点，则该树的叶子结点树为_68_个完全二叉树的第7层有10个叶子结点，则整个树的结点数最多是_235_个30、设二叉排序树中的关键字互不相同：则 最小元素无左孩子，最大元素无右孩子，此命题是否正确？是 最大和最小元素一定是叶子结点吗？不是 一个新插入的结点一定是一个新添加的叶子结点吗？是31、二叉排序树(Binary Sort Tree)或者是一棵空树；或者是具有下列性质的二叉树：1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3、它的左右子树也分别是二叉排序树。若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列32、平衡二叉树(AVL)或者是空树，或者是满足下列性质的二叉树：它的左子树和右子树也都是平衡二叉树，且左子树和右子树深度之差的绝对值不大于1。33、哈希表基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。34、设关键字序列是(19, 14, 23, 01, 68, 84, 27, 55, 11, 34, 79)，散列表长度是11，散列函数是H(key)=key MOD 1