54数据结构

习题一1、简要回答术语：数据，数据元素，数据结构，数据类型。数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是？元素之间的相互联系（关系）称为逻辑结构。四种基本类型是集合、线性结构、树型结构、图状结构或网状结构。数据结构在计算机中的表示（又称为映像）称为数据的物理结构，又称为存储结构。区别和联系：数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素之间的逻辑关系，而不管其在计算机中的存储方式，数据的逻辑结构分为线性结构和非线性结构。需要注意以下几点：逻辑结构与数据元素本身的形式、内容无关；与数据元素的相对位置无关；与所含数据元素的个数无关；与数据的存储无关，他独立于计算机。数据的存储结构是数据逻辑结构在计算机存储器里的，即数据的存储结构是数据及其逻辑结构在计算机中的表现，存储结构除了存储数据元素之外还必须能隐式或显式的表示数据元素之间的逻辑关系，这样，在逻辑上相邻的数据元素在存储结构中就未必相邻。数据的存储结构分为顺序存储结构和链式存储结构。数据的逻辑结构和物理结构是密不可分的两个方面，一个逻辑结构可表示成多种存储结构，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。3、数据结构的主要运算包括哪些？⑴建立(Create)一个数据结构；⑵消除(Destroy)一个数据结构；⑶从一个数据结构中删除(Delete)一个数据元素；⑷把一个数据元素插入(Insert)到一个数据结构中；⑸对一个数据结构进行访问(Access)；⑹对一个数据结构(中的数据元素)进行修改(Modify)；⑺对一个数据结构进行排序(Sort)；⑻对一个数据结构进行查找(Search)。4、算法分析的目的是什么？算法分析的主要方面是什么？目的：分析算法的效率以求改进或对不同的算法进行比较算法分析的主要方面是：空间复杂性和时间复杂性。5、分析一下程序段的时间复杂度，请说明分析的理由或原因。（1）Sum1(intn){intp=1,sum=0,m;for(m=1;m=n;m++){p*=m;sum+=p;}Return(sum);}（2）Sum2(intn){intsum=0,m,t;For(m=1;m=n;m++){p=1;For(t=1;t=m;t++)p*=t;Sum+=p;}Return(sum);}(3)Fact(intn){if(n=1)return1;Elsereturn(n*fact(n-1));}⑴基本操作的语句频度为：2n，其时间复杂度为：O(n)。⑵基本操作的语句频度为：1+2+3+…+n=n(n-1)/2，其时间复杂度为：O(n2)。⑶基本操作的语句频度为：n，其时间复杂度为：O(n)。习题二1、简述下列术语：线性表，顺序表，链表线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。2、何时选用顺序表，何时选用链表作为线性表的存储结构为宜？各自的主要有缺点是什么？在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：（1）基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。（2）基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定元素进栈顺序)，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。3、在顺序表中插入和删除一个结点平均需要移动多少个结点？具体的移动次数取决于哪两个因素？在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。4、链表多表示的元素是否有序，如有序，则有序性体现于何处？链表所表示的元素是否一定要在物理上是相邻的？有序表的有序性又如何理解？链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。5、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。定义structNode{intval;structNode*x;};插入:Node*insert(Node*head,intx){Node*pre=NULL,*h=head;while((head!=NULL)&&(head-valx)){pre=head;head=head-next;}Node*temp=newNode;temp-val=x;temp-next=head;if(pre==NULL){returntemp;}pre-next=temp;returnh;}6、写一求单链表的结点数目ListLength(L)的算法。intListLength(L){inti=0;ElemType*p;p=&L;if(!p)exit(-1);if(p.next==NULL)return0;elsewhile(p.next!=NULL){p++;i++;}returni;}7、写一算法将单链表中值重复的结点删除，使所得的结果链表中所有的结点值均不相同。voidDeletElem(SqListL){ElemType*p,*q,*s;inti=1;intj;p=&L.next.next;for(i;iL.length;i++){q=&L.next;for(j=1;j=i;j++){if(q-data==p-data){p.next=(p-1).next;s=p;p++;free(s);}}if(ji)p++;}}8、写一算法从一给定的向量A删除之在x到y（x=y）之间的所有元素voidDeletElem(SqListL,intx,inty){、ElemType*p,*q;inti=0;intj;p=&L.next;for(i;iL.length;i++){if(p.data=x||p.data=y){q=p;(p-1).next=p.next;p++;free(q);}elsep++;}}9、设A和B是两个按元素值递增的有序单链表，写一算法将A和B归并为按元素值递减有序的单链表C，试分析算法的时间复杂度。voidListInsert(SqListA,SqListB,SqListC){ElemType*p,*q,*s;P=&A;q=&B;s=&C;while(p.next!=NULL||q.next!=NULL){if(p.next.data=q.next.data){if(s.next!=NULL)p.next=s.next;s.next=p.next;p++;}else{if(s.next!=NULL)q.next=s.next;s.next=q.next;q++;}}while(p.next!=NULL){p.next=s.next;s.next=p.next;}while(q.next!=NULL){q.next=s.next;s.next=q.next;}}习题三1.设有一个栈，元素进栈的次序为a,b,c。问经过栈操作后可以得到哪些输出序列？abcbcacbabacacb2.循环队列的优点是什么？如何判断它的孔和满？循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？队列为空：front=rear。队满：rear=MAX-1或front=rear(队首指针front，一个队尾指针rear)4.设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？循环队列为空：front=rear。循环队列满：(rear+1)%MAX=front。(队首指针front，一个队尾指针rear)5.利用栈的基本操作，写一个返回栈S中结点个数的算法intStackSize(SeqStacckS)，并说明S为何不作为指针参数的算法？intStackSize(SeqStackS){//计算栈中结点个数intn=0;if(!EmptyStack(&S)){Pop(&S);n++;}returnn;}上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。6.一个双向栈S是在同一个向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。视为此双向栈设计初始化InitStack（S），入栈Push（S,i,x），出栈Pop（S,i,x）算法，其中i为0或者1，用以表示栈号。双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：//双向栈的栈结构类型与以前定义略有不同#defineStackSize100//假定分配了100个元素的向量空间#definecharDatatypetypedefstruct{DatatypeData[StackSize]inttop0;//需设两个指针inttop1;}DblStackvoidInitStack(DoubleStack*S){//初始化双向栈S-top0=-1;S-top1=StackSize;//这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错}intEmptyStack(DblStack*S,inti){//判栈空(栈号i)return(i==0&&S-top0==-1||i==1&&S-top1==StackSize);}intFullStack(DblStack*S){//判栈满return(S-top0==S-top1-1);}voidPush(DblStack*S,inti,DataTypex){//进栈(栈号i)if(FullStack(S))Error(