《数据结构与实训课后答案全集》由会员分享，可在线阅读，更多相关《数据结构与实训课后答案全集（38页珍藏版）》请在金锄头文库上搜索。
1、 第1章习题答案1.填空题1在计算机中的存储映像是逻辑结构在计算机中的实现或存储表示数据元素的表示元素之间关系的表示数据元素。2已经实现 是一个概念 别离别离3时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。4软硬件环境问题规模的5最坏6On4On2 7时间复杂度8n On22. 判断题123456789103. 简答题1略见教材第3页的1.2数据结构的根本概念2an-1，On b n-1 ,Onc11* n+1, Onn为初始值100d , O en ,On第2章 习题与答案1、填空题1address+m*i2顺序 顺序 顺序 链式存
2、储 链式存储3亦相邻 不一定4n-i+15 0ila的长度-1jlb的长度-10klc的长度-16插入的位置，节点数n顺序表长度n7其前驱O(n) O18其前驱O(n) O19pnext=pnext next10headnext=Nullhead=Nullheadnext=head head=Null11headnext=headnextnext head=headnext12x=ppriordata;ppriordata=pnextdata;pnextdata=x;13p=headprior(或pnext=head)2判断题123456789103简答题(1)单向循环链表双向循环链表存储密度
3、高低查找后继的时间复杂度O(1)O(1)查找前驱的时间复杂度O(n)O(1)2在带头结点的单链表上，查找指针p所指结点的前驱。3交换指针p与指针q所指结点的值。4算法设计题(1)void reverse(SeqList l) for (i=0;i=(l.listlength-1)/2;i+)l.elemil.eleml.listlength-1-i;(2)void delete(SeqList,int i,int k)/*从顺序表中删除自第i个元素开场的k个元素*/ if(il.listlength-1| k0) printf(“Error);return;if(i+k=l.listlengt
4、h)/*表中从i个元素起到最后一个元素有k个元素*/ for ( j=i+k;jl.listlength;j+)l.elemj-k=l.elemj; l.listlengt=l.listlength-k; else/*表中从i个元素起直到最后一个元素缺乏k个元素*/ l.listlength=i;(3)void insert(LinkList h,ElementType x)/*将x插入到递增链表h中，插入后的链表有序性不变*/ if(hnext=Null) /*空表时*/ q=(linklist) malloc (sizeof(ListNode);qnext=Null;qdata=x;hne
5、xt =q;p1=hnext; p2=h;while (p1next!=Null & p1datax) p2=p1; p1=p1next;if( p1next=Null & p1data=x) | (p1next!=Null & p1data=x)*/ q=(LinkList) malloc (sizeof(ListNode); qdata=x;p2next=q;qnext=p1;(4)void delete (LinkList p)/*在不带头结点且长度大于1的单向循环链表中，p指向某结点，删除p的前驱结点*/ppp=pnext;while (pppnextnext!=p)ppp =pppn
6、ext;/*删除p的前驱结点*/pp=pppnext;pppnext=ppnext;free(pp);(5) void delete (LinkList h)/*h为带头结点的，非降序排列的单链表的头指针，删除表中值一样的结点，使之只保存一个*/ p=hnext;if(!p) return;x=pdata;while (pnext)if(x!=pnextdata) x= pnextdata;p= pnextelseq=pnext;pnext=pnextnext;free(q);void delete (LinkList h)/*删除带头结点的单链表h指向头结点中值为x的结点的前驱结点*/ if
7、 (!(hnext ) return;if (!(hnextnext) return;p1=hnextnext; p2=h;while (p1next & p1data!=x) p1=p1next;p2=p2next;if (p1data=x) q=p2next;p2next=p1;free(q);(7) Linklist subtraction (LinkList la, LinkList lb)/*la,lb分别为表示集合A,B的带头结点的单链表的头指针，A-B由la链表返回*/ if (!(lanext) return (la);elsepa1=lanext ; pa2=la;if (!
8、(lbnext) return (la);while (pa1) pb=lbnext ;while (pb & pa1data!=pbdata) pb=pbnext;if (pb) /*pa1data=pbdata*/ pa2next=pa1next;free(pa1);pa1=pa2next;elsepa1=pa1next;pa2=pa2next; return (la);8LinkList intersection(LinkList la, LinkList lb)/*la,lb,lc分别为表示集合A,B,C的带头结点的递增有序的单链表的头指针，C=AB由lc链表返回*/ lc=(Link
9、List) malloc (sizeof(LinkNode); lcnext=null;tail=lc; /*tail指向lc链的尾结点*/if (!(lanext) return(lc);elsepa=lanext;if (!(lbnext) return(lc);while (pa) pb=lbnext;while (pb & padata!=pbdata)pb=pbnext;if (pb) insert(lc,tail,padata);pa=panext; return(lc);void insert (LinkList l, LinkList tail, ElemenType x)/*
10、将值x插入到单链表l的尾部*/ p=(LinkList) malloc (sizeof(LinkNode)pdata=x; pnext=null;tailnext=p;tail=p;SeqList intersection(SeqList la, SeqList lb)/*集合A,B,C对应的顺序递增表为la,lb,lc，C=AB由lc表示*/lc.listlength=0;if (la.listlength=0 | lb.listlength=0) return(lc)for( a=0; ala.listlength;a+) for(b=0; blb.listlength & lb.elemb!=la.elema;b+)if (bmin & p1data=0 & hdata=9) /*数字字符插入到*ph2链*/ hnext=(*ph2)next;(*ph2)next=h;else /*字母字符插入到*ph1链*/ hnext=(*ph1)next; (*ph1) next=h;(11)void me
