数据结构与实训课后答案全集.doc

《数据结构与实训课后答案全集.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第1章习题答案1.填空题（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。（2）已经实现是一个概念分离分离（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。（4）软硬件环境问题规模的（5）最坏（6）O（n4）O（n2）（7）时间复杂度（8）nO（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

2、+1,O（n）（n为初始值100）（d）,O（）（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）插入的位置，节点数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→nex

3、t（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)38单向循环链表双向循环链表存储密度高低查找后继的时间复杂度O(1)O(1)查找前驱的时间复杂度O(n)O(1)（2）在带头结点的单链表上，查找指针p所指结点的前驱。（3）交换指针p与指针q所指结点的值。4．算法设计题(1)voidreverse(SeqListl){for(i=0;i<=(l.l

4、istlength-1)/2;i++)l.elem[i]<—>l.elem[l.listlength-1-i];}(2)voiddelete(SeqList,inti,intk)/*从顺序表中删除自第i个元素开始的k个元素*/{if(i<0

5、

6、i>l.listlength-1

7、

8、k<0){printf(“Error”);return;}if(i+k<=l.listlength)/*表中从i个元素起到最后一个元素有k个元素*/{for(j=i+k;j

9、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→data

10、x)38{q=(linklist)malloc(sizeof(ListNode));q→next=Null;q→data=x;p1→next=q;}else/*(p1→next==Null&&p1→data>=x)

11、

12、(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→ne

13、xt→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