DS第二章课后习题答案

《DS第二章课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表2.1填空题(1)一半插入或删除的位置(2)静态动态(3)一定不一定(4)头指针头结点的next前一个元素的next2.2选择题(1)A(2)DAGKHDAELIAFIFA(IDA)(3)D(4)D(5)D2.3头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址；头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放；首元素结点：第一个元素的结点。2.4已知顺序表L递增有序，写一算法，将X

2、插入到线性表的适当位置上，以保持线性表的有序性。voidInserList(SeqList*L,ElemTypex){inti=L->last;if(L->last>=MAXSIZE-1)returnFALSE;//顺序表已满while(i>=0&&L->elem[i]>x){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;L->last++;}2.5删除顺序表中从i开始的k个元素intDelList(SeqList*L,inti,intk){intj,l;if(i<

3、=0

4、

5、i>L->last){printf("TheInitialPositionisError!");return0;}if(k<=0)return1;/*NoNeedtoDelete*/if(i+k-2>=L->last)L->last=L->last-k;/*modifythelength*/for(j=i-1,l=i+k-1;llast;j++,l++)L->elem[j]=L->elem[l];L->last=L->last-k;return1;}2.6已知长度为n的线性表A采用顺序存储结

6、构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，删除线性表中所有值为item的数据元素。[算法1]voidDeleteItem(SeqList*L,ElemTypeitem){inti=0,j=L->last;while(ielem[i]!=item)i++;while(ielem[i]==item)j--;if(ielem[i]=L->elem[j];i++;j--;}}L->last=i-1;}[算法2]voidDeleteIt

7、em(SeqList*L,ElemTypee){inti,j;i=j=0;while(L->elem[i]!=e&&i<=L->last)i++;j=i+1;while(j<=L->last){while(L->elem[j]==e&&j<=L->last)j++;if(j<=L->last){L->elem[i]=L->elem[j];i++;j++;}}L->last=i-1;}2.7编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。 voidD

8、eleteRepeatItem(SeqList*L){inti=0,j=1;while(j<=L->last){if(L->elem[i]==L->elem[j])j++;else{L->elem[i+1]==L->elem[j];i++;j++;}}L->last=i;}2.8已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。voidDelData(LinkListL,ElemT

9、ypemink,ElemTypemaxk){Node*p=L->next,*pre=L;while(!p&&p->data<=mink)//寻找开始删除的位置{pre=p;p=p->next;}while(p){if(p->data>maxk)break;else{pre->next=p->next;free(p);p=pre->next;}}}T(n)=O(n);2.9试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）

10、。（1）以一维数组作存储结构。（2）以单链表作存储结构。(略)(1)voidReverseArray(ElemTypea[],intn){inti=0,j=n-1;ElemTypet;while(inext;L->next=NULL;while(p!=NULL){q=p->next;p