《DS第二章-课后习题答案培训教材》由会员分享，可在线阅读，更多相关《DS第二章-课后习题答案培训教材（10页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表2.1 填空题 (1)一半 插入或删除的位置 (2)静态 动态 (3)一定 不一定 (4)头指针 头结点的next 前一个元素的next2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D2.3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性
2、表的有序性。void InserList(SeqList *L,ElemType x) int i=L-last; if(L-last=MAXSIZE-1) return FALSE; /顺序表已满 while(i=0 & L-elemix) L-elemi+1=L-elemi; i-; L-elemi+1=x; L-last+;2.5 删除顺序表中从i开始的k个元素int DelList(SeqList *L,int i,int k) int j,l; if(iL-last) printf(The Initial Position is Error!); return 0; if(k=L-l
3、ast) L-last=L-last-k; /*modify the length*/ for(j=i-1,l=i+k-1;llast;j+,l+) L-elemj=L-eleml; L-last=L-last-k; return 1;2.6 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，删除线性表中所有值为item的数据元素。算法1void DeleteItem(SeqList *L,ElemType item) int i=0,j=L-last; while(ij) while(ielemi!=item) i+; while(ielemi=
4、item) j-; if(ielemi=L-elemj; i+; j-; L-last=i-1;算法2void DeleteItem (SeqList *L,ElemType e)int i,j;i=j=0;while(L-elemi!=e & ilast)i+;j=i+1;while(jlast)while(L-elemj=e & jlast)j+;if(jlast)L-elemi=L-elemj;i+; j+;L-last=i-1;2.7 编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。void DeleteRepeatItem(
5、SeqList *L) int i=0,j=1; while(jlast) if(L-elemi=L-elemj) j+; else L-elemi+1=L-elemj; i+; j+; L-last=i; 2.8已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。void DelData(LinkList L,ElemType mink,ElemType maxk)Node *p=L-next,*pre=L;while(!p & p-data next;while(p
6、) 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）。（1） 以一维数组作存储结构。（2） 以单链表作存储结构。(略)(1)void ReverseArray(ElemType a,int n)int i=0,j=n-1;ElemType t;while(inext; L-next=NULL; while(p!=NULL) q=p-next; p-n
7、ext=L-next; L-next=p; p=q; 2.10已知一个带有表头结点的单链表,假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，至返回0。（提示：设置两个指针，步长为k）int SearchNode(LinkList L,int k)Node *p=L,*q;int i=0;while(inext; if(p=NULL) return 0; /不存在倒数第k个元素q=L-next;while(p-next!=NULL) /p到终点时，q所指结点为倒
8、数第k个q=q-next; p=p-next;printf(%d,q-data);return 1;2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。（头插法）LinkList ReverseMerge(LinkList *A, LinkList *B) LinkList C; Node *pa=A-next,*pb=B-next; /pa和pb分别指向A,B的当前元素 A-next=NULL; C=A; while(pa!=NULL & pb!=NULL) if(pa-data data) /*将pa的元素前插到pc表*/ temp=pa-next; pa-next
9、=C-next; C-next=pa; pa=temp; else temp=pb-next; pb-next=C-next; C-next=pb; pb=temp; /*将pb的元素前插到pc表*/ while(pb!=NULL) temp=pa-next; pa-next=C-next; C-next=pa; pa=temp; /*将剩余pa的元素前插到pc表*/ while(pb!=NULL) temp=pb-next; pb-next=C-next; C-next=pb; pb=temp; /*将剩余pb的元素前插到pc表*/ return hc;2.12一单链表，以第一个元素为基准，
10、将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为O(n)，不能申请新空间。void AdjustList(LinkList L) Node *pFlag=L-next,*q=L-next-next,*temp=NULL; pflag-next=NULL; while(q!=NULL) if(q-data data) /插到链表首端 temp=q-next; q-next=L-next; L-next=q; q=temp; Else /插到pFlag结点后面 temp=q-next; q-next=pFlag-next; pFlag-next=q; q=temp;
11、2.13假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。void DelPreNode(Node* s) Node* p=s; while(p-next-next!=s) p=p-next; free(p-next); p-next=s;2.14已知由单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。/L为待拆分链表/Lch为拆分后的字母链；Lnum为拆分后的数字链，Loth为拆分后的其他字符链/Lch,Lnum,Loth均已被初始化为带头结点的单循环链表，采用头插法void splitLinkList(LinkList L,LinkList Lch,LinkList Lnum,LinkList Loth) Node *p=L-next; while(p!=NULL) if( (p-data =a & p-data=z)|
