数据结构复习题提纲(整理)

《数据结构复习题提纲(整理)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、WORD文档可编辑复习提纲第一章数据结构概述基本概念与术语（P3）1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科.2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合2．数据元素是数据的基本单位3．数据对象相同性质的数据元素的集合4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作.（1）数据的逻辑结构指数据元素之间固有的逻辑关系.（2）数据的存储结构指数据元素及其关系在计算机内的表示(3)数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等.5.时

2、间复杂度分析--------------------------------------------------------------------------------------------------------------------1、名词解释：数据结构、二元组2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。4、以下程序段的时间复杂度为__

3、_O(N2)_____。inti,j,x;for(i=0;i=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列//顺序表结构#defineMAXSIZE100typedefintDataT

4、ype;Typedefstruct{DataTypeitems[MAXSIZE];Intlength;}Sqlist,*LinkList;//初始化链表voidInitList(LinkList*L){(*L)=(LinkList)malloc(sizeof(LNode));if(!L){cout<<”初始化失败!”;return;}(*L)->next=NULL;}//插入数据voidInsertList(LinkListL,intpos,DataTypex){LinkListp=L,q;inti=0;while(p&&inext;i++;

5、}if(!p

6、

7、i>pos-1){cout<<”插入位置错误”;return;}InitList(&q);q->next=p->next;p->next=q;q->data=x;}//销毁链表技术资料专业分享WORD文档可编辑voidDestoryList(LinkListL){LinkListt;while(L){t=L;L=L->next;free(t);}}//遍历链表voidTraverseList(LinkListL){LinkListt=L;while(L){t=t->next;cout<data<<””;}cout<

8、idDeleteList(LinkListL,intpos){LinkListp=L,q;inti=0;while(p&&inext;i++;}if(!p

9、

10、i>pos-1){cout<<”删除位置错误!!”;return;}q=p->next;p->next=q->next;free(q):}第一章栈和队列1.栈（1）栈的结构与定义（2）顺序栈操作算法：入栈、出栈、判断栈空等（3）链栈的结构与定义技术资料专业分享WORD文档可编辑1.队列（1）队列的定义--------------------------------------------

11、--------------------------------------------------------------------1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（）A.BCDAEB.EDACBC.BCADED.AEDCB2、栈的顺序表示仲，用TOP表示栈顶元素，那么栈空的条件是（）A.TOP==STACKSIZEB.TOP==1C.TOP==0D.TOP==-13、允许在一端插入，在另一端删除的线性表称为____队列____。插入的一端为____队尾____，删除的一端为_____队头___。4、栈的特点是