2022年DS第二章_课后习题答案 .pdf

《2022年DS第二章_课后习题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年DS第二章_课后习题答案 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、资料收集于网络如有侵权请联系网站删除谢谢精品文档第二章线性表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 插入到线性表的

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-last)

3、L-last=L-last-k;/*modify the length*/名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精品文档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 的数据元素。算法 1 void DeleteItem(SeqList*L,ElemType item)int i=0,j=L

4、-last;while(ij)while(ielemi!=item)i+;while(ielemi=item)j-;if(ielemi=L-elemj;i+;j-;L-last=i-1;算法 2 void 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;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精

5、品文档i+;j+;L-last=i-1;2.7 编写算法，在一非递减的顺序表L 中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。void DeleteRepeatItem(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 DelDa

6、ta(LinkList L,ElemType mink,ElemType maxk)Node*p=L-next,*pre=L;while(!p&p-data next;while(p)if(p-data maxk)break;else 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精品文档 pre-next=p-next;free(p);p=pre-next;T(n)=O(n);2.9 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2.,an）逆置为（an,an-1,.,a1）。（1）以一维

7、数组作存储结构。（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-next=L-next;L-next=p;p=q;2.10 已知一个带有表头结点的单链表,假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1；否则，至返回0。（提示：设置两个指针，步长为k）int

8、 SearchNode(LinkList L,int k)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精品文档Node*p=L,*q;int i=0;while(inext;if(p=NULL)return 0;/不存在倒数第k 个元素q=L-next;while(p-next!=NULL)/p到终点时，q 所指结点为倒数第k 个q=q-next;p=p-next;printf(%d,q-data);return 1;2.11 把元素递增排列的链表A 和 B 合并为 C,且 C 中元素递减排列,使用原空间。（头插法）LinkL

9、ist 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=C-next;C-next=pa;pa=temp;else temp=pb-next;pb-next=C-next;C-next=pb;pb=temp;/*将 pb 的元素前插到pc 表*/while(pb!=N

10、ULL)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 一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为O(n)，不能申请新空间。void AdjustList(LinkList L)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -资料收集

11、于网络如有侵权请联系网站删除谢谢精品文档 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;2.13 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s 为指向链表某个结点的指针，试编写算法在链表中删除指针s 所指结点

12、的前驱结点。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 s

13、plitLinkList(LinkList L,LinkList Lch,LinkList Lnum,LinkList Loth)Node*p=L-next;while(p!=NULL)if(p-data=a&p-datadata=A&p-datanext;p-next=Lch-next;Lch-next=p;p=temp;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精品文档else if(p-data=0&p-datanext;p-next=Lnum-next;Lnum-next=p;p=temp;else temp=p-n

14、ext;p-next=Loth-next;Loth-next=p;p=temp;2.15 设线性表 A=(a1,a2,am)，B=(b1,b2,bn)，试写一个按下列规则合并A、B 为线性表 C的算法，使得：C=(a1,b1,am,bm,bm+1,bn)当 m n 时；或者C=(a1,b1,an,bn,an+1,am)当 mn 时。线性表 A、B、C均以单链表作为存储结构，且 C表利用 A表和 B表中的结点空间构成。注意：单链表的长度值m和 n 均未显式存储。/将 A 和 B 合并为 C,C 已经被初始化为空单链表void MergeLinkList(LinkList A,LinkList B

15、,LinkList C)Node*pa=A-next，*pb=B-next,*pc=C;int tag=1;while(pa&pb)if(tag)pc-next=pa-next;pc=pc-next;pa=pa-next;tag=1;else pc-next=pb-next;pc=pc-next;pb=pb-next;tag=0;if(pa)pc-next=pa-next;else pc-next=pb-next;s 2.16 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。/A 为循环单链表，表示某多项式

16、；将A 拆分为 B 和 C/其中 B 只含奇次项，C 只含偶次项；奇偶按照幂次区分/B,C 均已被初始化为带头结点的单链表void SplitPolyList(PolyList A,PolyList B,PolyList C)PolyNode*pa=A-next,*rb=B,*rc=C;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精品文档while(pa)if(pa-exp%2=0)/偶次项rc-next=pa-next;rc=rc-next;pa=pa-next;else/奇次项rb-next=pa-next;rb=rb-n

17、ext;pa=pa-next;rb-next=NULL;rc-next=NULL;2.17 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data 域存放一个二进制位。并在此链表上实现对二进制数加1 的运算。void BinAdd(LinkList l)/*用带头结点的单链表L 存储二进制数，实现加1 运算*/Node*q,*r,*s;q=l-next;r=l;while(q!=NULL)/*查找最后一个值域为0的结点*/if(q-data=0)r=q;q=q-next;if(r!=l)r-data=1;/*将最后一个值域为0 的结点的值域赋为1*/else/*未找到值域

18、为0 的结点*/s=(Node*)malloc(sizeof(Node);/*申请新结点存放最高进位*/s-data=1;/*值域赋为 1*/s-next=L-next;L-next=s;/*插入到头结点之后*/r=s;r=r-next;while(r!=NULL)/*将后面的所有结点的值域赋为0*/r-data=0;r=r-next;2.18 多 项 式 P(x)采用书中所述链接方法存储。写一算法，对给定的x 值，求 P(x)的值。double Compute(PolyList PL,double x)名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -资料收集于网络如有侵权请联系网站删除谢谢精品文档 double sum=0;PolyNode*p=PL-next;while(p)sum=sum+p-coef*pow(x,p-exp);p=p-next;return sum;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -