洛阳理工数据结构复习必过

选择题〔2*10=20)1、链表的特点线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。数据元素ai的存储映像称为结点，包括2个域：存数据的数据域、存后继存储位置的指针域。1)线性链表(单链表)特点：每个结点只包含1个指针域。在单链表的第一个结点之前附设的一个结点，称之为头结点。假设L是LinkList型变量，那么L为单链表的头指针，它指向表中第一个结点；L->next为第一个结点地址，L->next=NULL为空表。生成结点：p=(LinkList)malloc(sizeof(LNode))回收结点：free(q)2)循环链表特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的操作与线性链表根本一致，差异仅在于算法中的循环条件不是P或P->next是否为空，而是它们是否等于头指针。3)双向链表特点：有2个指针域，其一指向直接后继，另一指向直接前趋。2、栈对的特点1.栈：是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底，不含有元素的空表称为空栈；栈又称为后进先出的线性表。2.队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而另一端删除元素。允许插入的一端叫做队尾，允许删除的一端那么称为队头。1)链队列：用链表示的队列。一个队列需要两个分别指示队头和队尾的指针〔分别成为头指针和尾指针〕才能确定唯一。和单链表一样，也给链队列添加一个头结点，并令头指针指向头结点。2)循环队列：与顺序栈类似，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。3、二维数组Am*n计算任意ai*j元素地址。A1*1为首地址假设线性表的每个元素需占用size个存储单元。以行存储：Loc[i,j]=Loc[1,1]+〔n*(i-1)+j-1〕*size以列存储：Loc[i,j]=Loc[1,1]+〔m*(j-1)+i-1〕*size3、二叉树性质，特点1.二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树〔即二叉树中不存在度大于2的结点〕，并且，二叉树的子树有左右之分，其次序不能任意颠倒。2.二叉树的性质：1)性质1：在二叉树的第i层上至多有2的i减1次方个结点(i≥1)。2)性质2：深度为k的二叉树至多有2的k次方减1个结点(k≥1)。深度为k的二叉树至少有k个结点(k≥1)。深度为k的完全二叉树至少有2的k次方减2的k减1次方个结点(k≥1)。3)性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，那么n0=n2+1。4)性质4：具有n个结点的完全二叉树的深度为[log2n]+1。5)性质5：如果对一棵有n个结点的完全二叉树〔其深度为[log2n]+1〕的结点按层序编号〔从第1层到第[log2n]+1层，每层从左到右〕，那么对任一结点i〔1≤i≤n〕有：a)如果i=1，那么结点i是二叉树的根，无双亲；如果i>1，那么其双亲PARENT(i)是结点[i/2]。b)如果2i>n，那么结点i无左孩子〔结点i为叶子结点〕；否那么其左孩子LCHILD(i)是结点2i。c)如果2i+1>n，那么结点i无右孩子；否那么其右孩子RCHILD(i)是结点2i+1。5、计算时间复杂度时间复杂度：算法中根本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n))；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如：(a){++x;s=0;}(b)for(i=1;i<=n;++i){++x;s+=x;}(c)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}含根本操作“x增1”的语句的频度分别为1、n和n²，那么这3个程序段的时间复杂度分别为O(1)、O(n)和O(n²)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(logn)、指数阶O(2的n次方)等。7、连通图的概念连通图：在无向图中，任意两个顶点之间都有路径。连通分量：在无向图中的极大连通子图。二、填空题〔1*15=15〕1、六个空是第一章，概念1.数据：是描述客观事物的数值，字符以及能输入到机器且能被处理的各种符号的总称的集合。2.数据元素：是组成数据的根本单位，是数据集合的个体，在计算机程序中通常作为一个整体进行考虑和处理。3.数据对象：是性质相同的数据元素的集合，是数据的一个子集。4.数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合。5.数据类型：是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。6.数据的抽象：计算机中使用的是二进制数，汇编语言中那么可给出各种数据的十进制表示，他们是二进制数据的抽象。7.抽象数据类型〔ADT〕:是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。ADT包括定义和实现两方面，其中定义是独立于实现的。8.逻辑结构：是数据元素之间的逻辑关系的描述。其4类根本结构：集合、线性结构、树形结构、图状结构或网状结构9.物理结构〔存储结构〕：是数据结构在计算机中的表示〔又称映像〕。其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构。9.数据结构目的是为了在计算机中实现操作，数据结构就是研究一类数据的表示以其相关的运算操作。按某种逻辑关系组织起来的一批数据，按一定的逻辑映像方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫数据结构。6.算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。其5个重要特性：有穷性、确定性、可行性、输入、输出2.用数组模拟链表结构数组模拟链表，是一种半静态链表，是链表的线性存储，比链式存储要简单的多了。每个链表可以用一对数组或一个记录数组表示，每个元素是有两个数据域：分别是数据data域和下一个结点在数组中的位置next域〔整型的〕。这样插入，删除，遍历等，都可以归结到数组操作了，这就比链式存储容易多了，却不丧失链表快速插入删除的优势。以下所说的指针，都是模拟指针，代表某元素在数字中的位置。一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号，并且方便调试；缺点是不能动态的分配内存。当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法有时候被叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的〔但是可以说成是用数组实现的链表〕现要在编号为K,K+1的两个结构体数据之间插入数据"x"，"x"存在空闲的arr[9]里，K=3时即在"d""e"之间插入"x"#include<stdio.h>#defineK3voidmain(){struct{intdata;intnum;}arr[10]={{'a',1},{'b',2},{'c',3},{'d',4},{'e',5},{'f',6},{'g',7},{'h',8},{0,0},{0,0}};intpos=0;arr[K].num=9;arr[9].data='x';arr[9].num=(K+1);while(arr[pos].data!=0){printf("%c,",arr[pos].data);pos=arr[pos].num;}printf("\n");}输出:a,b,c,d,x,e,f,g,h,3、链表必考1.优点链表的主要优势有两点：一是插入及删除操作的时间复杂度为O(1)；二是可以动态改变大小。2.缺点由于其链式存储的特性，链表不具备良好的空间局部性，也就是说，链表是一种缓存不友好的数据结构。4、二叉树，完全二叉树1.二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树〔即二叉树中不存在度大于2的结点〕，并且，二叉树的子树有左右之分，其次序不能任意颠倒。2.满二叉树：一颗深度为k且有2的k次方减1个结点的二叉树。3.完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。先序：__B__EHI__FG__K中序：D__HEIA__CJG__后序：__H__EBF__KG__A三、应用题(6*5=30)1、树两个题，有图与无图例题1：中序序列BDCEAFHG前序序列ABCDEFGH例题2.〔1〕一个二叉树如图1所示：写出该二叉树的先序，中序，后序遍历序列；〔2〕把图1对应的二叉树转换为所对应的森林；〔3〕一棵二叉树的中序遍历序列为：dfebagc，先序遍历序列为：abdefcg，请画出这棵二叉树。2、图两个图，没权重，无向图1.图：多个结点，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。2.无向完全图：有n(n-1)/2条边的无向图。3.有向完全图：有n(n-1)条边的有向图。4.入度：以顶点V为头的弧的数目称为V的入度。5.出度：以V为尾的弧的数目称为V的出度。3、一道双向链表1.设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列〔设双向链表中结点的两个指针域分别为llink和rlink〕。答：操作序列如下：q->rlink=p->rlinkp->rlink=qq->rlink->llink=qq->llink=p注意答案不唯一四、读程序〔5*3=15〕1、链表typedefstructLNode{intdata;StructNode*next;}Node,*Linklist;InitList(Linklist*H){*H=(Linklist)malloc(sizeof(LNode));//建立头结点(*H)->next=NULL;//建立空的单链表H求长度intListLength(LinklistL){//求带头结点的单链表长度Inti;Node*P;P=L->next;j=0;//用来存放单链表的长度While(p!=NULL){P=P->next;j++;}Returnj;}2、二叉树/*下面程序段计算二叉树的叶子节点个数*/intcountleaf(BitreeT){if(T==NULL)//如果节点为空，那么返回0return0;elseif((T->lchild==NULL)&&(T->rchild==NULL))//否那么如果节点左右孩子有一个为空，另一个存在，那么返回1return1;elsereturn(countleaf(T->lchild)+countleaf(T->rchild));//否那么返回左右子树叶子节点之和}3、c语言相关的，时间复杂度voidBubbleSort(inta[],intp)//冒泡排序算法{inti,j,temp;for(i=0;i<N-1;i++){for(j=N-1;j>i;j--)//比拟,找出本趟最小关键字的记录if(a[j]<a[j-1]){temp=a[j];//进行交换,将最小关键字记录前移a[j]=a[j-1];a[j-1]=temp;}}五、编程题〔10*2=20〕1、单链表Linklistchange(Linklisthead)//逆置算法{Linklistp,q;p=head->next;//P指向链表第一个元素head->next=NULL;//断开头结点与链表while(p!=NULL){q=p;p=p->next;q->next=head->next;//相当于头插法构建新的链表head->next=q;//每下一个结点始终在第一个位置}returnhead;}2、二叉树voidPreOrderTraverse(BiTreeBT){if(BT