数据结构复习.docx

《数据结构复习.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、线性结构:结构中的数据元素之间存在一对一的关系。2、数据结构的形式定义为：数据结构是一个二元组：·Data-Structure=(D，S)·其中：D是数据元素的有限集，S是D上关系的有限集。例1复数的数据结构定义如下：·Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}3、元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。4、程序=算法+数据结构5、算法的五个特性（1）有穷性（2）确定性（3）可行性4

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

3、从1报数，重复这个过程，直到最后剩下一个人就是幸运之星。问题就是谁是幸运者呢？或者说是怎样才能赢大奖。main(){inta[50],n;int*p;inti,k,m;printf("pleaseinputpeoplenumber:");scanf("%d",&n);//总人数为np=a;//p指向数组a[]的首地址for(i=0;i

4、==n)i=0;//i=n时，循环}while(*p==0)p++;printf("thelastpeoplenumberis:%d",*p);8、栈必须按“后进先出”的规则进行操作、栈只允许在表尾一端进行插入和删除9、通常称往栈顶插入元素的操作为“入栈”、称删除栈顶元素的操作为“出栈”。10、从数据结构的角度看，栈和队列也是线性表、栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。11、队列(Queue)：也是运算受限的线性表。是一种先进先出(FirstInFirstOut，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。队首(front)

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

6、树15、中序遍历（LTR）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树16、后序遍历（LRT）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点17、Huffman树的构造²在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和；²在F中删除这两棵树，同时将新得到的树加入F中；²重复②、③，直到F只含一颗树为止。18、构造Huffman树时，为了规范，规定F={T1,T2,⋯,Tn}中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取

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