数据结构复习资料1.docx

《数据结构复习资料1.docx》由会员分享，可在线阅读，更多相关《数据结构复习资料1.docx（7页珍藏版）》请在课桌文档上搜索。

1、数据结构复习第一章绪论复习内容：(1)基本概念和术语(2)抽象数据类型的表示与实现(3)估算算法时间复杂度复习题：1.仿照三元组的抽象数据类型写出抽象数据类型有理数的定义(有理数是其份子、分母均为自然数且分母不为零的分数)。DTRatiOnaLNUm数据对象：D=el,e2n(n为整数集合)数据关系：Rl=,el是有理数份子，e2是有理数分母，且e20基本操作：InitRatiOnaLNUm(&T,vl,v2)操作结果：构达了有理数T,元素el,e2分别被赋以参数vl,v2的值。DestroyRational-Num(&T)操作结果：有理数T被销毁。Get(T,i,&C)初始条件：有理数T己存

2、在，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相乘，结果存入有理数

3、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=yif(yvz)temp=z;z=y;使tempzif(=temp)y=temp;elsey=x;x=temp;printf(x,y,z);!/Descending第二章线性表复习内容：(1) 线性表的类型和定义(2) 线性表的顺序表示和实现(3

4、) 线性表的链式存储和实现(4) 一元多项式的表示及相加线性表-顺序存储结构-顺序表线性表一-链式存储结构-链表线性表在顺序存储结构上实现查找、插入和删除的算法区分线性表的逻辑结构和存储结构复习题：1 .(1)在顺序表中插入或者删除一个元素，需要平均挪移【表中一半】元素，具体挪移的元素个数与【表长和该元素在表中的位置】有关。(2)顺序表中逻辑上相邻的元素的物理位置【必然】紧邻。单链表中逻辑上相邻的元素的物理位置【不一定】紧邻。2 .例2-1假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A=AUBo3 .简述顺序表和单链表的优缺点

5、。顺序表-优点：逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑。缺点：插入、删除操作需要挪移大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充。单链表一优点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除操作方便。单链表的缺点指针占用额外存储空间不能随机存取，查找速度慢。4.写出按正位序建立一个单链表的算法。voidCreateList_L(LinkList&L,intn)(正序输入n个数据元素，建立带头结点的单链表1.=(LinkList)malloc(sizeof(LNode);1.-next=NULL;/先建立一个带头结点的单链表for(i=1;

6、idata);/输入元素值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

7、-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(i1kLaJength)returnERROR；参数不合法e

8、lsefor(count=1;count=i+1;j-)1.a.elem-1=La.elemj;1.aJength-;returnok;DeleteK第二个for语句中，元素前移的次序错误；低效之处是每次删除一个元素的策略。改正后的算法：StatusDeIetKfSqList&La,intI1intk)本过程从顺序存储结构的线性表La中删除第i个元素起的k个元素If(Oi=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;elsereturnE

9、RROR；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,因

10、为4356出栈说明12已在栈中，则1不可能在2之前出栈。】3 .写出检验括号匹配的算法。(见作业)4 .假设将循环队列定义为：以域变量rear和Iength分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件。head=(q.rear+MAXLEN)-q.length1)%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第四章串复习内

11、容：(1) 串类型的定义；(2) 串的三种存储表示，定长顺序结构。块链存储结构和堆分配存储结构；(3) 串的各种基本操作的实现及其应用。复习题：1 .设计在顺序存储结构上实现求子串算法。StatusSubString(SString&Sub,SStringS,intpos,intlen)/用SUb返回串S的第POS个字符起长度为Ien的子串。其中1posWStrLength(三)且OWIenWStrLength(S卜PoS+1if(posS0HlenS0-pos+1)returnERROR;Subllen=Spos.pos+l-e1n；SubO=le;returnOK;/Substring2

12、.已知下列字符串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=ISV=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=THISSAMPLEISAGO

13、ODONE,；StrLength(s)=14；Index(v,g)=3；Index(u,g)=0.5东五章数组和广义表复习内容：17 )/ )/ Xu/ )/ 1 2 3 4 5 Zf 数组的类型定义数组的顺序表示和实现矩阵的压缩存储广义表的定义广义表的存储结构复习题：1.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非O元素。2,稀疏矩阵的压缩存储方法：【三元组顺序表，行逻辑链接的顺序表，十字链表】3 .设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每一个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为(B)0A（

14、八）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第六章树和二叉树复习要求：掌握树和二叉树的概念、存储结构，基本运算及其遍历，掌握哈夫曼树的概念和构造方法。复习内容：(1) 树的定义和基本术语(2) 二叉树(3) 遍历二又树和线索二叉树(4) 树和森林(5) 哈夫曼树及其应用复习题：1 .画出和下列己知序列对应的树T树的先根次序访问序列为Gfkdaiebchj树的后根次序访问序列为Dia

15、ekfcjhbg2 .画出和下列已知序列对应的森林F森林的先序访问序列为Abcdefghijkl森林的中序访问序列为Cbefdgajiklh字母在电文中出现的频率分别为 个字母设计哈夫曼编码。使用0-7的 比较两种方案的优缺点。3 .假设用于通信的电文仅由8个字母组成，0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10试为这8二进制表示形式是另一种编码方案。对于上述实例，WPL1=2.61WPL2=3方案1优于方案25.一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每一个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：(1)

16、各层结点数目是多少？(2)编号为P的结点的父结点(若存在)的编号是多少？(3)编号为P的结点的第i个儿子结点(若存在)的编号是多少？(4)编号为P的结点有有右兄弟的条件是什么？其右兄弟的编号是多少？答案：第i层有ki-个1结点;IP+(k-2)I(2)p=l时，该结点为根，无父结点；否则其父结点编号为ILkji(k=2)其第kT个儿子的编号为p-k。所以，如果他有儿子，则其第i个儿子的编号为Pk+(i-(k-l)；(4) (p-l)%kO时，该结点有右兄弟，其右兄弟的编号为p+1。第七章图复习要求：掌握图的有关概念、存储结构、遍历算法、生成树的求法以及拓扑排序的概念及求法。复习内容：u J 7

17、 J JZ 7 、/ (2(3(4(5(6复图的定义和术语图的存储结构图的遍历图的连通性问题有向无回图及其应用最短路径1 .对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_包_个和一组一个。2 .设有6个结点的无向卤，该图至少应有(A)条边才干确保是一个连通图。A.5B.6C.7D.83 .已知如右图所示的有向图，请给出该图的(1)每一个顶点的人/出度；(2)邻接矩阵(3)邻接表(4)逆邻接表(5)强连通分量答案：(1)每一个顶点的人/出度;顶点123456入度321122出度022313(2)邻接矩阵0000001001000100010010111000

18、00110010(3)邻接表+M0BH2E6524-14(4)逆邻接表23456-4.二-O二*S3*B0-H-3?有3个强连通分量4 .简述图的各种存储结构的合用类型？答：邻接矩阵：有向图和无向图邻接表(逆邻接表)：有向图和无向图十字链表：有向图邻接多重表：无向图5 .已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;AE=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,A(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25)；A用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中挨次得到的各条边。答：用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)206 .AOV网是一种有向无回路的图。7 .请对下面的无向带权图，(1)写出它的邻接矩阵，并按普里姆算法求其最小生成树；(2)写出它的邻接表，并按克鲁斯卡算法求其最小生成树。