数据结构复习资料1.docx
数据结构复习第一章绪论复习内容：(1)基本概念和术语(2)抽象数据类型的表示与实现(3)估算算法时间复杂度复习题：1.仿照三元组的抽象数据类型写出抽象数据类型有理数的定义(有理数是其份子、分母均为自然数且分母不为零的分数)。DTRatiOnaLNUm数据对象：D=<el,e2>el,e2n(n为整数集合)数据关系：Rl=<el,e2>,el是有理数份子，e2是有理数分母，且e20基本操作：InitRatiOnaLNUm(&T,vl,v2)操作结果：构达了有理数T,元素el,e2分别被赋以参数vl,v2的值。DestroyRational-Num(&T)操作结果：有理数T被销毁。Get(T,i,&C)初始条件：有理数T己存在，i1,2.操作结果：用。返回T有理数的份子和分母的值，i=l返回份子，i=2返回分母。Put(&T,i,e)初始条件：有理数T已存在，i32.操作结果：改变有理数T的份子或者分母的值为e,i=l改变份子，i=2改变分母。AddRational_Num(Tl,T2,&T3)初始条件：看理数T已存在。操作结果：有理数TKT2相加，结果存入有理数T3<,SubRational_Num(Tl,T2,&T3)初始条件：看理数T已存在。操作结果：有理数TkT2相减，结果存入有理数T3oMulRationalNum(Tl,T2,&T3)初始条件：看理数T已存在。操作结果：有理数TKT2相乘，结果存入有理数T3。DivRational_Num(T1,T2,&T3)初始条件：看理数T已存在。操作结果：有理数Tl.T2相除，结果存入有理数T3oADTRationalNum2.设n为正整数，请确定下列各程序段中前置以记号的语句的频度：i=1；k=0;while(i<=n-1)k÷=10*i;i÷+;)答案：n-12 2)for(i=2;i<=n;+i)for=2;j<=i-t+j)+x;ai,j=x;)答案：1+2+3+.+n-2=(n-1X-2)2=(n2-3n+2)23 .试写一算法，自大至小挨次输出顺序读入的三个整数X,Y和Z的值。voidDescendingOscanf(x,y,z);if(xvy)temp=x;x=y;y=temp;使x>=yif(yvz)temp=z;z=y;使temp>zif(×>=temp)y=temp;elsey=x;x=temp;printf(x,y,z);!/Descending第二章线性表复习内容：(1) 线性表的类型和定义(2) 线性表的顺序表示和实现(3) 线性表的链式存储和实现(4) 一元多项式的表示及相加线性表-顺序存储结构-顺序表线性表一-链式存储结构-链表线性表在顺序存储结构上实现查找、插入和删除的算法区分线性表的逻辑结构和存储结构复习题：1 .(1)在顺序表中插入或者删除一个元素，需要平均挪移【表中一半】元素，具体挪移的元素个数与【表长和该元素在表中的位置】有关。(2)顺序表中逻辑上相邻的元素的物理位置【必然】紧邻。单链表中逻辑上相邻的元素的物理位置【不一定】紧邻。2 .例2-1假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A=AUBo3 .简述顺序表和单链表的优缺点。顺序表-优点：逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑。缺点：插入、删除操作需要挪移大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充。单链表一优点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除操作方便。单链表的缺点指针占用额外存储空间不能随机存取，查找速度慢。4.写出按正位序建立一个单链表的算法。voidCreateList_L(LinkList&L,intn)(正序输入n个数据元素，建立带头结点的单链表1.=(LinkList)malloc(sizeof(LNode);1.->next=NULL;/先建立一个带头结点的单链表for(i=1;i<n;i+)(p=(LinkList)malloc(sizeof(LNode);scanf(&p->data);/输入元素值p->next=L->next;1.->next=p;/插入/CreateList_L5 .已知L是带裘头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。(1)删除P结点的语句序列是【JLGCN】o(2)删除尾元结点的语句序列是【IKCN】。J / l )l l o- 1 IJ1 l / 17 AbcdefghoJKLMN z( /( /( ( /( /( /( /( /( /( /( /(P=P->next;P->next=P;P->next=P->next->next;P=P->next->next;WhiIe(PI=NULL)P=P->next;while(Q->next!=NULL)P=Q;Q=Q->next;)while(P->next!=Q)P=P->next;while(P->next->next!=Q)P=P->next;while(P->next->next!=NULL)P=P->next;Q=P;Q=P->next;P=L;1.=L->next;free(Q);6 .指出以下算法中的错误和低效(即费时)之处，并将它改写为一个既正确又高效的算法。StatusDeletK(SqList&La,intI1intk)本过程从顺序存储结构的线性表La中删除第i个元素起的k个元素If(i<1k<0i+k>LaJength)returnERROR；参数不合法elsefor(count=1;count<k;count+)/删除一个元素for(j=La.length;j>=i+1;j-)1.a.elem-1=La.elemj;1.aJength-;returnok;DeleteK第二个for语句中，元素前移的次序错误；低效之处是每次删除一个元素的策略。改正后的算法：StatusDeIetKfSqList&La,intI1intk)本过程从顺序存储结构的线性表La中删除第i个元素起的k个元素If(O<i<=a.length)&&<0<=k<=a.length-i)for(j=i+k;j<=La.length;j+)1.a.elemi+=La.elemj;1.aJength=La.length-k;returnok;elsereturnERROR；DeleteK第三章栈和队列复习内容：(1) 栈的定义及实现(2) 栈的应用(3) 队列的定义及实现(4) 队列的应用复习题：1 .栈和队列的共同特点是(A)。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2 .利用栈的结构对列车车箱进行调度则如果进站的车箱序列为123,则可能得到的出站车箱序列是什么？123,132,213,231,321如果进站的车箱序列为123456,则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出以'S'表示进栈和以'X'表示出栈的栈操作序列)。【可以得到135426,不可能得到435612,因为'4356'出栈说明12已在栈中，则1不可能在2之前出栈。】3 .写出检验括号匹配的算法。(见作业)4 .假设将循环队列定义为：以域变量rear和Iength分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件。head=(q.rear+MAXLEN)-q.length÷1)%MAXLEN其中MAXLEN为队列可用的最大空间。5 .设顺序循环队列Q0：MT的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为(C)o（八）R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M第四章串复习内容：(1) 串类型的定义；(2) 串的三种存储表示，定长顺序结构。块链存储结构和堆分配存储结构；(3) 串的各种基本操作的实现及其应用。复习题：1 .设计在顺序存储结构上实现求子串算法。StatusSubString(SString&Sub,SStringS,intpos,intlen)/用SUb返回串S的第POS个字符起长度为Ien的子串。"其中1posWStrLength(三)且OWIenWStrLength(S卜PoS+1if(pos<1pos>S0Hlen<0len>S0-pos+1)returnERROR;Subllen=Spos.pos+l-e1n；SubO=le;returnOK;/Substring2 .已知下列字符串a=fTHIS,f='ASAMPLE,c=iGOOD,d='NE',b='',S=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2),t=Replace(f,Substring(f,3,6),c),U=Concat(SubString(c,3,l),d),g='IS'V=Concat(s,Concat(b,Concat(t,Concat(b,u),请问：s,t,v,StrLcngth(s),Index(v,g),IndeX(U,g)各是什么？答：s=THISSAMPLEIS'；t='AGOOD,；V='THISSAMPLEISAGOODONE,；StrLength(s)=14；Index(v,g)=3；Index(u,g)=0.5东五章数组和广义表复习内容：17 )/ )/ Xu/ )/ 1 2 3 4 5 Zf < < z(x t>数组的类型定义数组的顺序表示和实现矩阵的压缩存储广义表的定义广义表的存储结构复习题：1.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非O元素。2,稀疏矩阵的压缩存储方法：【三元组顺序表，行逻辑链接的顺序表，十字链表】3 .设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每一个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为(B)0A（八）10(B)19(C)28(D)554 .三角如阵%00彩，000%Ma按行序为主序：alI2a22a31a32一anlannk0iLl3Tin-ynn*TTTl1.oc(aij)=?答案：Loc(aij)=Loc(all)+i*(i-l)2+(j-l)*L第六章树和二叉树
