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