数据结构课后习题解析第二章

1、第二章习题描绘以下三个观点的差别：头指针，头结点，首元素结点。填空：（1）在次序表中插入或删除一个元素，需要均匀移动元素，详细挪动的元素个数与有关。（2）在次序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。（3）在带头结点的非空单链表中，头结点的储存地点由指示，首元素结点的储存地点由指示，除首元素结点外，其余任一元素结点的储存地点由指示。3已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从以下语句中选择适合的语句序列。a.在P结点后插入S结点的语句序列是：。b.在P结点前插入S结点的语句序列是：。c.在表首插入S结点的语句序

2、列是：。d.在表尾插入S结点的语句序列是：。供选择的语句有：1）P-next=S;2）P-next=P-next-next;3）P-next=S-next;4）S-next=P-next;5）S-next=L;6）S-next=NULL;7）Q=P;8）while(P-next!=Q)P=P-next;9）while(P-next!=NULL)P=P-next;10）P=Q;11）P=L;12）L=S;13）L=P;4.设线性表存于a(1:arrsize)的前elenum个重量中且递加有序。试写一算法，将X插入到线性表的适合地点上，以保持线性表的有序性。5.写一算法，从次序表中删除自第i个元素

3、开始的k个元素。6.已知线性表中的元素（整数）以值递加有序摆列，并以单链表作储存结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的复度（注意：mink和maxk是定的两个参量，它的随意的整数）。7.分以不一样的存构性表的就地逆置算法，即在原表的存空将性表（a1,a2.,an）逆置（an,an-1,.,a1）。（1）以一数作存构，性表存于a(1:arrsize)的前elenum个重量中。（2）以表作存构。8.假两个按元素增有序摆列的性表A和B，均以表作存构，写算法，将A表和B表并成一个按元素减有序摆列的性表C，并要求利用原表（即A表和B表的

4、）点空寄存表C。9.假有一个循表的度大于1，且表中既无点也无指。已知s指向表某个点的指，写算法在表中除指s所指点的前点。10.已知有表表示的性表中含有三字符的数据元素（如字母字符、数字字符和其它字符），写算法来结构三个以循表表示的性表，使每个表中只含同一的字符，且利用原表中的点空作三个表的点空，点可另辟空。11.性表A=(a1,a2,am)，B=(b1,b2,bn)，写一个按以下归并A、B性表C的算法，使得：C=(a1,b1,am,bm,bm+1,bn)当mn；或许C=(a1,b1,an,bn,an+1,am)当mn。性表A、B、C均以表作存构，且C表利用A表和B表中的点空组成。注意：表的度m

5、和n均未式存。12.将一个用循表表示的稀少多式分解成两个多式，使两个多式中各自含奇次或偶次，并要求利用原表中的点空来组成两个表。13.成立一个点的性表，用以寄存入的二制数，表中每个点的data域寄存一个二制位。并在此表上二制数加1的运算。14.多式P(x)采纳本中所述接方法存。写一算法，定的x，求P(x)的。1将若干城市的信息存入一个点的表，点中的城市信息包含城市名、城市的地点坐。要求：（1）定一个城市名，返回其地点坐；2）定一个地点坐P和一个距离D，返回所有与P的距离小于等于D的城市。2瑟夫。瑟夫的一种描绘是：号1，2，n的n个人按方向坐一圈，每人持有一个密（正整数）。一开始任一个整数作数上

6、限m,从第一个人开始自1开始序数，到m停止数。m的人出列，将他的密作新的m，从他在方向上的下一个人开始从头从1数，这样下去，直至所有的人所有出列止。一个程序，求出出列序。利用向循表作存构模此程，依据出列序打印出各人的号。比如m的初20；n=7，7个人的密挨次是：3，1，7，2，4，8，4，出列的序6，1，4，7，2，3，5。第二章答案瑟夫瑟夫的一种描绘：号1,2,n的n个人按方向坐一圈，每一个人拥有一个密（正整数）。一开始任一个数上限m,从第一个人开始自1开始序数，到m停止数。m的人出列，将他的密作新的m，从他在方向上的下一个人开始从头从1数，这样下去，直至所有的人所有出列止。一个程序，求出出

7、列序。利用向循表作存构模此程，依据出列序打印出各人的号。比如m的初20；n=7，7个人的密挨次是：3,1,7,2,4,8,4,出列序6,1,4,7,2,3,5。【解答】算法以下：typedefstructNodeintpassword;intnum;structNode*next;Node,*Linklist;voidJosephus()LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(sizeof(Node);/*初始化向循表if(L=NULL)printf(n表申不到空!);return;L-next=NULL;r=L;printf(入数据

8、n的(n0):);scanf(%d,&n);for(j=1;jpassword=C;p-num=j;r-next=p;r=p;r-next=L-next;printf(入第一个数上限m(m0):);scanf(%d,&m);printf(*n);printf(出列的序:n);q=L;p=L-next;while(n!=1)/*算出列的序*/j=1;while(jnext;j+;printf(%d-,p-num);m=p-password;/*得新密*/n-;q-next=p-next;/*p出列*/r=p;p=p-next;free(r);printf(%dn,p-num);分以不一样的存构表

9、的就地逆置算法，即在原表的存空将性表a1,a2,an）逆置(an,an-1,a1)。【解答】（1）用一数作存构voidinvert(SeqList*L,int*num)intj;ElemTypetmp;for(j=0;jnext=NULL)p=L-next;return;/*表空*/q=p-next;p-next=NULL;while(q!=NULL)/*/*摘下第一个点，生成初始逆置表从第二个点起挨次插入目前逆置表*/*/r=q-next;q-next=L-next;L-next=q;q=r;将性表A=(a1,a2,am),B=(b1,b2,bn)归并成性表C,C=(a1,b1,am,bm,

10、bm+1,.bn)当mn,A表和B表中的点空组成。注意：LinkListmerge(LinkListA,LinkListB,LinkListC)Node*pa,*qa,*pb,*qb,*p;pa=A-next;/*pa表示pb=B-next;p=A;/*利用p来指向新接的表的表尾，初始指向表A的点A的目前点*/*/while(pa!=NULL&pb!=NULL)/*利用尾插法成立接以后的表*/qa=pa-next;qb=qb-next;p-next=pa;/*交替表A和表B中的点接到新表中；*/p=pa;p-next=pb;p=pb;pa=qa;pb=qb;if(pa!=NULL)if(pb!

11、=NULL)p-next=pa;p-next=pb;/*A/*B的度大于的度大于B的度*/A的度*/C=A;Return(C);提示：第2章性表描绘以下三个观点的区：指，点，首元素点。填空：（1）在序表中插入或除一个元素，需要均匀移一半元素，详细移的元素个数与插入或除的地点相关。2）在序表中，上相的元素，其物理地点相。在表中，上相的元素，其物理地点相。（3）在点的非空表中，点的存地点由指示，首元素点的存地点由指示，除首元素点外，其余任一元素点的存地点由其直接前的next域指示。已知L是无表点的表，且P点既不是首元素点，也不是尾元素点。按要求从以下句中适合的句序列。在P点后插入S点的句序列是：（

12、4）、（1）。在P点前插入S点的句序列是：（7）、（11）、（8）、（4）、（1）。在表首插入S点的句序列是：（5）、（12）。在表尾插入S点的句序列是：（11）、（9）、（1）、（6）。供的句有：1）P-next=S;2）P-next=P-next-next;3）P-next=S-next;4）S-next=P-next;5）S-next=L;6）S-next=NULL;7）Q=P;8）while(P-next!=Q)P=P-next;9）while(P-next!=NULL)P=P-next;10）P=Q;11）P=L;12）L=S;13）L=P;已知性表L增有序。写一算法，将X插入到L的

13、适合地点上，以保持性表序性。提示：voidinsert(SeqList*L;ElemTypex)L的有方法11）找出插入地点i，（2）移位，（3）方法2参P.229写一算法，从序表中除自第i个元素开始的k个元素。提示：注意i和k的合法性。（集体搬家，“新房”、“旧房”）方法1以待移元素下m（“旧房号”）中心，算移入地点（“新房号”）：for(m=i1+k;mlast;m+)Lelemmk=Lelemm;方法3同以待移元素下m和移入地点j中心：以移入地点j中心，算待移元素下：已知性表中的元素（整数）以增有序摆列，并以表作存构。写一高效算法，除表中所有大于mink且小于maxk的元素（若表中存在的

14、元素），剖析你的算法的复度（注意：mink和maxk是定的两个参量，它的随意的整数）。提示：注意mink和maxk的合法性：minknext;while(p!=NULL&pdatanext;（2）找到最后一个点的后s，找放点s=p;while(s!=NULL&st=s;s=sdatanext;free(t);（3）prenext=s;分以不一样的存构性表的就地逆置算法，即在原表的存空将性表（a1,a2.,an）逆置（an,an-1,.,a1）。（1）以一数作存构，性表存于a(1:arrsize)的前elenum个重量中。（2）以表作存构。方法1:在原点后从头插一遍方法2:可三个同步移的指p,q

15、,r，将q的后r改p假两个按元素增有序摆列的性表A和B，均以表作存构，写算法，将A表和B表并成一个按元素减有序的摆列的性表C，并要求利用原表（即A表和B表的）点空寄存表C.提示：参例2-1方法1voidmerge(LinkListA;LinkListB;LinkList*C)pa=Anext;pb=Bnext;*C=A;(*C)next=NULL;while(pa!=NULL&pb!=NULL)if(padatadata)smaller=pa;pa=panext;smallernext=(*C)next;(*C)next=smaller;/*插法*/elsesmaller=pb;pb=pbne

16、xt;smallernext=(*C)next;(*C)next=smaller;while(pa!=NULL)smaller=pa;pa=pasmallernext=(*C)(*C)next=smaller;next;next;while(pb!=NULL)smaller=pb;pb=pbsmallernext=(*C)(*C)next=smaller;next;next;方法2LinkListmerge(LinkListA;LinkListB)LinkListC；pa=Anext;pb=Bnext;C=A;Cnext=NULL;returnC;假有一个循表的度大于1，且表中既无点也无指。已

17、知s指向表某个点的指，写算法在表中除指s所指点的前点。提示：指p指向s点的前的前，p与s有何关系？已知有表表示的性表中含有三字符的数据元素（如字母字符、数字字符和其余字符），写算法来结构三个以循表表示的性表，使每个表中只含同一的字符，且利用原表中的点空作三个表的点空，点可另辟空。性表A=(a1,a2,am)，B=(b1,b2,bn)，写一个按以下归并A、B性表C的算法，使得：C=(a1,b1,am,bm,bm+1,bn)当mn；或许C=(a1,b1,an,bn,an+1,am)当mn。性表A、B、C均以表作存构，且C表利用A表和B表中的点空组成。注意：表的度m和n均未式存。提示：voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListmerge(LinkListA;LinkListB)将一个用循表表示的稀少多式分解成两个多式，使两个多式中各自含奇次或偶次，并要求利用原表中的点空来组成两个表。提示：注明用指是尾指。成立一个点的性表，用以寄存入的二制数，表中每个点的一个二制位。并在此表上二制数加1的运算。提示：可将低位放在前面。多式P(x)采纳本中所述接方法存。写一算法，定的x，求提示：floatPolyValue(Polylistp;floatx)data域寄存P(x)的。1将若干城市的信息存入一个点的表，点中的城市信息