DS第二章_课后习题答案讲述.doc

第二章 线性表 2.1 填空题 (1)一半 插入或删除的位置 (2)静态 动态 (3)一定 不一定 (4)头指针 头结点的next 前一个元素的next 2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 void InserList(SeqList *L,ElemType x) { int i=L-last; if(L-last=MAXSIZE-1) return FALSE; //顺序表已满 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个元素 int DelList(SeqList *L,int i,int k) { int j,l; if(i=0||iL-last) {printf(The Initial Position is Error!); return 0;} if(k=0) return 1; /*No Need to Delete*/ if(i+k-2=L-last) L-last=L-last-k; /*modify the length*/ for(j=i-1,l=i+k-1;lL-last;j++,l++) L-elem[j]=L-elem[l]; L-last=L-last-k; return 1; } 2.6 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，删除线性表中所有值为item的数据元素。 [算法1] void DeleteItem(SeqList *L,ElemType item) { int i=0,j=L-last; while(ij) { while(ij L-elem[i]!=item) i++; while(ij L-elem[i]==item) j--; if(ij) { L-elem[i]=L-elem[j]; i++; j--;} } L-last=i-1; } [算法2] void DeleteItem (SeqList *L,ElemType e) { int i,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)。 void DeleteRepeatItem(SeqList *L) { int i=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的元素（若表中存在这样的元素），分析你的算法的时间复杂度。 void DelData(LinkList L,ElemType mink,ElemType maxk) { Node *p=L-next