数据结构与实训[张红霞等主编]习题答案

1第1章习题答案1.填空题（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。（2）已经实现是一个概念分离分离（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。（4）软硬件环境问题规模的（5）最坏（6）O（n4）O（n2）（7）时间复杂度（8）n2)1(nnO（n2）2.判断题（1）×（2）×（3）√（4）√（5）√（6）√（7）×（8）×（9）×（10）×3.简答题（1）略（见教材第3页的1.2数据结构的基本概念）（2）（a）n-1，O（n）（b）n-1,O（n）（c）11*n+1,O（n）（n为初始值100）（d）n,O（n）（e）n,O（n）第2章习题及答案1、填空题（1）address+m*i（2）顺序顺序顺序链式存储链式存储（3）亦相邻不一定（4）n-i+1（5）0≤i≤la的长度-1≤j≤lb的长度-10≤k≤lc的长度-1（6）2)1(nn插入的位置，节点数n（顺序表长度n）（7）其前驱O(n)O（1）（8）其前驱O(n)O（1）（9）p→next=p→next→next（10）head→next==Nullhead==Nullhead→next==headhead==Null（11）head→next=head→next→nexthead=head→next（12）x=p→prior→data;p→prior→data=p→next→data;p→next→data=x;（13）p==head→prior(或p→next==head)2．判断题（1）×（2）√（3）×（4）×（5）×（6）×（7）√（8）×（9）×（10）×3．简答题(1)2单向循环链表双向循环链表存储密度高低查找后继的时间复杂度O(1)O(1)查找前驱的时间复杂度O(n)O(1)（2）在带头结点的单链表上，查找指针p所指结点的前驱。（3）交换指针p与指针q所指结点的值。4．算法设计题(1)voidreverse(SeqListl){for(i=0;i=(l.listlength-1)/2;i++)l.elem[i]—l.elem[l.listlength-1-i];}(2)voiddelete(SeqList,inti,intk)/*从顺序表中删除自第i个元素开始的k个元素*/{if(i0||il.listlength-1||k0){printf(“Error”);return;}if(i+k=l.listlength)/*表中从i个元素起到最后一个元素有k个元素*/{for(j=i+k;jl.listlength;j++)l.elem[j-k]=l.elem[j];l.listlengt=l.listlength-k;}else/*表中从i个元素起直到最后一个元素不足k个元素*/l.listlength=i;}(3)voidinsert(LinkListh,ElementTypex)/*将x插入到递增链表h中，插入后的链表有序性不变*/{if(h→next==Null)/*空表时*/{q=(linklist)malloc(sizeof(ListNode));q→next=Null;q→data=x;h→next=q;}p1=h→next;p2=h;while(p1→next!=Null&&p1→datax){p2=p1;p1=p1→next;}if(p1→next==Null&&p1→datax)3{q=(linklist)malloc(sizeof(ListNode));q→next=Null;q→data=x;p1→next=q;}else/*(p1→next==Null&&p1→data=x)||(p1→next!=Null&&p1→data=x)*/{q=(LinkList)malloc(sizeof(ListNode);q→data=x;p2→next=q;q→next=p1;}}(4)voiddelete(LinkListp)/*在不带头结点且长度大于1的单向循环链表中，p指向某结点，删除p的前驱结点*/{ppp=p→next;while(ppp→next→next!=p)ppp=ppp→next;/*删除p的前驱结点*/pp=ppp→next;ppp→next=pp→next;free(pp);}(5)voiddelete(LinkListh)/*h为带头结点的，非降序排列的单链表的头指针，删除表中值相同的结点，使之只保留一个*/{p=h→next;if(!p)return;x=p→data;while(p→next)if(x!=p→next→data){x=p→next→data;p=p→next}else{q=p→next;p→next=p→next→next;free(q);}}4voiddelete(LinkListh)/*删除带头结点的单链表h（指向头结点）中值为x的结点的前驱结点*/{if(!(h→next))return;if(!(h→next→next))return;p1=h→next→next;p2=h;while(p1→next&&p1→data!=x){p1=p1→next;p2=p2→next;}if(p1→data==x){q=p2→next;p2→next=p1;free(q);}}(7)Linklistsubtraction(LinkListla,LinkListlb)/*la,lb分别为表示集合A,B的带头结点的单链表的头指针，A-B由la链表返回*/{if(!(la→next))return(la);else{pa1=la→next;pa2=la;}if(!(lb→next))return(la);while(pa1){pb=lb→next;while(pb&&pa1→data!=pb→data)pb=pb→next;if(pb)/*pa1→data==pb→data*/{pa2→next=pa1→next;free(pa1);pa1=pa2→next;}else{pa1=pa1→next;pa2=pa2→next;}}return(la);}5（8）LinkListintersection(LinkListla,LinkListlb)/*la,lb,lc分别为表示集合A,B,C的带头结点的递增有序的单链表的头指针，C=A∩B由lc链表返回*/{lc=(LinkList)malloc(sizeof(LinkNode));lc→next=null;tail=lc;/*tail指向lc链的尾结点*/if(!(la→next))return(lc);elsepa=la→next;if(!(lb→next))return(lc);while(pa){pb=lb→next;while(pb&&pa→data!=pb→data)pb=pb→next;if(pb)insert(lc,tail,pa→data);pa=pa→next;}return(lc);}voidinsert(LinkListl,LinkListtail,ElemenTypex)/*将值x插入到单链表l的尾部*/{p=(LinkList)malloc(sizeof(LinkNode))p→data=x;p→next=null;tail→next=p;tail=p;}SeqListintersection(SeqListla,SeqListlb)/*集合A,B,C对应的顺序递增表为la,lb,lc，C=A∩B由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.elem[b]!=la.elem[a];b++)if(blb.listlength){lc.elem[lc.listlength]=la.elem[a];lc.listlength++;}}retuen(lc);}6(9)voiddelete(LinkListh,ElementTypeminElementTypemax)/*h是带头结点的无序单链表的头指针，删除结点值大于min小于max的结点*/{if(!(h→next))return;p1=h→next;p2=h;while(p1)if(p1→datamin&&p1→datamax){p2→next=p1→next;free(p1);p1=p2→next;}else{p1=p1→next;p2=p2→next;}}(10)voidseparation(LinkListh,LinkList*ph1,LinkList*ph2)/*h为带头结点的单链表的头指针，该表中含有两类字符数据元素：字母与数字，拆分h为两条带头结点的单项循环链表*ph1、*ph2，其中*ph1链中存放字母，*ph2链中存放数字*/{if(!(h→next))return;p=h→next;free(h);*ph1=(LinkList)malloc(sizeof(LinkNode));(*ph1)→next=*ph1;*ph2=(LinkList)malloc(sizeof(LinkNode));(*ph2)→next=*ph2;while(p){h=p;p=p→next;if(h→data=’0’&&h→data=’9’)/*数字字符插入到*ph2链*/{h→next=(*ph2)→next;(*ph2)→next=h;}else/*字母字符插入到*ph1链*/{h→next=(*ph1)→next;(*ph1)→next=h;}}}(11)7voidmerge(DoubleListhead1,DoubleListhead2)/*head1、head2分别为两个带头结点的双向循环链表的头指针，将head1链接到head2*/{if(head1→next==head1)return;/*head1为空链表*/head2→prior→next=head1→next;head1→next→prior=head2→prior;head1→prior→next=head2;head2→prior=head1→prior;free(head1);}(12)voiddelete(DoubleListhead,DoubleNode*p)/*head为带头结点的双向循环链表的头指针，p指向head链中的某一个结点，删除p的前驱结点*/{if(p→prior==head)return;/*p结点无前驱结点*/q=p→prior;/*q指向p的前驱结点*/p→prior→prior→next=p;p→prior=p→prior→prior;free(q);}第3章习题及答案1．填空题（1）1，3，51（2）push,pop,push,push,pop,push,pop,pop（3）栈空栈满（4）O(1)O(1)（5）=s.top-1=s.top+1（6）s（7）空（8）栈底栈顶（9）队尾队首（头）（10）是否为空是否为满（11）21（12）front→next==rear（13）front==rear(rear+1)%MAX==frontrear+MAX-frort2．判断题（1）√（2）×（3）√（4）√（5）×（6）√（7）√（8）×（9）√（10）√3．简答题（1）当进行入队操作时，队尾指针的值已经到达数组空间的最大下标（MaxSize-1），而队首指针的值却大于0，这时就产生了假溢出现象。（2）使栈s中的元素顺序置逆。（3）借助于另一链栈t，使得链栈s去掉指定的元素e。84．算法设计题（1）intmaxvalue(SeqStacks)/*s是存有整数序列a1,a2,…,an的堆栈，用递归求其中的最大值