数据结构复习

《数据结构复习》由会员分享，可在线阅读，更多相关《数据结构复习（5页珍藏版）》请在装配图网上搜索。

1、1、线性2构：结构中的数据元素之间存在一对一的关系。2、数据结构的 形式定义为：数据结构是一个二元组：DData-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)输出

2、6、算法效率的度量：时间复杂度空间复杂度7、线性表中元素的个数n称为线性表的长度，n=0时称为空表； 线性表：是n个数据元素的有限序列。同一线性表中的元素必须是同一类型的；问2：结构体中间的那个 struct LNode是什么意思？? 答2：在最后一行白“缩写LNode还没出现之前，只能用原始的struct LNode来进行变量说明。此处说明了指针分量*next的数据类型是struct LNode问题：一个旅行社要从n名旅客中选出一名幸运旅客，为他提供免费环球旅行服务。方法是，大家站成圈，然后选定一个 m,从第1个人开始报数，报到 m时，这个人OUT,然后从下直到最后剩下一个人就是幸运之星。问

3、题就是谁scanf(%d,&n); / 总人数为 n/p指向数组a口的首地址/数组初始化一个人开始重新从1报数，重复这个过程, 是幸运者呢？或者说是怎样才能赢大奖。main()int a50,n; int *p; int i, k, m; printf(please input people number:); 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) *(p+i)=0;k=0; m+; i+; if(i=n) i=0;报数为k=3的人出列/m为出列的人数/i = n时，循环whi

4、le(*p= = 0)p+;printf(the last people number is:%dn,*p);8、 栈必须按“后进先出 ”的规则进行操作、栈只允许在表尾一端进行插入和删除9、 通常称往栈顶插入元素的操作为“入栈 ”、称删除栈顶元素的操作为“出栈 ”。10、从数据结构的角度看，栈和队列也是线性表、栈（Stack） 是限定仅在表尾进行插入或删除操作的线性表。11、队列（Queue）： 也是运算受限的线性表。是一种先进先出（First In First Out ，简称 FIFO）的线性表。只允许在表的一端进行插入，而在另一端进行删除。队首 （front） ： 允许进行删除的一端称为队

5、首。 队尾 （rear） ： 允许进行插入的一端称为队尾。即队列的修改是依先进先出的原则进行的12、接受用户从终端输入的程序或数据，并存入用户的数据区。? 退格符“#”退行服“”13、树的存储结构双亲表示法：假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲在链表中的位置。孩子表示法：多重链表，每个指针指向一棵子树的根结点。孩子兄弟表示法：二叉树表示法，链表中两个链域分别指向该结点的第一个孩子和下一个兄弟结点。（左边为孩子节点，右边为兄弟节点）14、 先序遍历（T L R）若二叉树非空（1 ）访问根结点；（ 2）先序遍历左子树；（ 3）先序遍历右子树15、 中序遍历（L

6、T R）若二叉树非空（1 ）中序遍历左子树（2）访问根结点（3）中序遍历右子树16、 后序遍历（L R T）若二叉树非空（1 ）后序遍历左子树（2）后序遍历右子树（3）访问根结点17、 Huffman 树的构造在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和；在 F 中删除这两棵树，同时将新得到的树加入F 中；重复、，直到F只含一颗树为止。18、 构造Huffman树时，为了规范，规定F=Ti,尼？，Tn中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树作为

7、新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。19、图的遍历通常分为深度优先查找和广度优先查找两种方式。深度优先：访问指定的某顶点 v,把它当作当前的顶点访问当前顶点的下一个未访问过的邻顶点重复 2，知道当前顶点的所有邻接点都被访问完沿搜索路径回退，退到尚有邻接点未被访问的结点，将该结点作为当前结点，重复以上步骤，直到所有结点都访问过为止广度优先：先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问到；由近到远访问，依次访问和v 有路径长度为1、 2、 3.的顶点。图中尚有顶点未访问到，则另选图中一个未曾被访问的顶点做起点，重复上述过程，直至所有顶点被访问完为止。20、

8、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历21、构造最小生成树的算法有许多，基本原则是：尽可能选取权值最小的边，但不能构成回路；选才n- n-1条边构成最小生成树。21、最小生成树的算法思想：普里姆（Prim）算法 若从顶点vo出发构造，U=v。, te=； 先找权值最小的边（u, v）,其中uCU且vC V-U,并且子图不构成环，则 U= UU v, TE=TE （u, v）; 重复，直到U=V为止。则TE中必有n-1条边，T=（U, TE）就是最小生成树。22、拓扑排序算法 在AOV网中选择一个没有前驱的顶点且输出；在AOV网中

9、删除该顶点以及从该顶点出发的（以该顶点为尾的弧）所有有向弧（边）； 重复、，直到图中全部顶点都已输出 （图中无环）或图中不存在无前驱的顶点 （图中 必有环）。23、关键路径：从源点到汇点的路径长度最长的路径。关键路径上的所有活动都是关键活动。Vi事件的最早发生时间ve （i）正向取最大值Vi事件的最迟发生时间vl （i）逆向取最小值活动ai的最早开始时间（弧j,k表示ai）e（i尸ve（j）活动ai的最迟开始时间:l（i）=vl（k）-ai24、最短路径：基本思想：从图的给定源点到其它各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径

10、长度。? 即按长度递增的次序生成各顶点的最短路径，先求出长度最小的一条最短路径，然 后求出长度第二小的最短路径，依此类推，直到求出长度最长的最短路径。25、在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（C）倍。? A. 1/2B. 2? C. 1D. 426、G是一个非连通无向图，共有 28条边，则该图至少有_9一个顶点设G为具有N个顶点的无向连通图，则 G中至少有_N-1_条边图没有顺序映像的存储结构，但可以借助数组的数据类型来表示元素之间的关系27、关键路径：从源点到汇点的路径长度最长的路径。28、树型结构是一类非常

11、重要的非线性结构。29、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行排序，根为1号，则49号结点的左孩子编号为 _98已知二叉树有50个叶结点，且仅有一个孩子的结点数为30个，求树的总结点数 129_二叉树有50个叶子结点，则二叉树的总结点数至少有99个完全二叉树的第8层有8个结点，则该树的叶子结点树为 _68个完全二叉树的第7层有10个叶子结点，则整个树的结点数最多是_235个30、设二叉排序树中的关键字互不相同：则 最小元素无左孩子，最大元素无右孩子，此命题是否正确？是 最大和最小元素一定是叶子结点吗？不是一个新插入的结点一定是一个新添加的叶子结点吗？是31、二叉排序树

12、(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 11，采用开放地址法的线性探测方法解决冲突，请构造该关键字序列的哈希表。采用开放地址法的二次探测方法解决冲突，请构造该关键字序列的哈希表。01255230134561468271178910841934790125523013451434276687891084197911Di:1 -1 4 -4 9 -9