数据结构 c语言描述 第二版 (陈慧南 著) 西安电子科技大学出版社 课后答案 11页

'课后答案网您最真诚的朋友www.hackshp.cn网团队竭诚为学生服务，免费提供各门课后答案，不用积分，甚至不用注册，旨在为广大学生提供自主学习的平台！课后答案网：www.hackshp.cn视频教程网：www.efanjy.comPPT课件网：www.ppthouse.com课后答案网www.hackshp.cn 第一章绪论1．（第14页，第（18）题）确定划线语句的执行次数，计算它们的渐近时间复杂度。(1)i=1;k=0;do{k=k+10*i;i++;}while(i<=n-1)划线语句的执行次数为n-1（n>=2），n=1时执行1次。(2）i=1;x=0;do{x++;i=2*i;}while（i=(y+1)*(y+1))y++;划线语句的执行次数为⎣√n⎦。www.hackshp.cn第二章两种基本的数据结构2-4．Loc(A[i][j][k])=134+(i*n*p+j*p+k)*22-9.第34页习题(2).9voidInvert(Telements[],intlength){//length数组长度//elements[]为需要逆序的数组Te;for(inti=1;i<=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2-12．第34页习题(12)voidpInvert(Node*first){Node*p=first,*q;first=NULL;while(p){q=p->Link;p->Link=first;khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com first=p;p=q;}}第三章栈与队列1．第54页习题(1）khdaw.com设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。1）A,B,C,D,E2)A,C,E,B,D3)C,A,B,D,E4)E,D,C,B,A答：课后答案网（1）Push（A）;Pop(A);Push(B);Pop(B);Push(C);Pop(C);Push(D);Pop(D);Push(E);www.hackshp.cnPop(E);2）不能得到，因为E，B，D而言，E最先出栈，则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。3）不能得到，因为C,A,B而言，C最先出栈，则表明，此时A和B均在栈中，由于A优先于B近栈，所以B应比A先出栈。(4)Push（A）;Push（B）;Push（C）;Push（D）；Push（E）;Pop(E);Pop(D);Pop(C);Pop(B);Pop(A);5.Stack1Stack2TOP1TOP2栈满Top2-Top1==1Top1<0栈1空Top2>n-1栈2空9：voidPrintQueue(Queueq){intfirst=q.Front+1;while(((first)%q.MaxQueue)!=q.Rear)khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com {printf("%dn",q.Elements[first]);first=first+1;}printf("%dn",q.Elements[first]);}voidPrintQueue2(Queueq){for(inti=1;q.Front!=q.Rear;i++){printf("%dn",q.Elements[(q.Front+1)%q.MaxQueue]);q.Front=(q.Front+1)%q.MaxQueue;khdaw.com}}voidPrintQueue3(Queueq){课后答案网for(;q.Front!=q.Rear;q.Front=(q.Front+1)%q.MaxQueue){printf("%dwww.hackshp.cnn",q.Elements[(q.Front+1)%q.MaxQueue]);}}第四章线性表与数组1（85页）intSearch_Insert(List*lst,Tx){inti,j;j=lst->Size-1;for(i=lst->Size-1;i>=0;i--){if(lst->Elements[i]==x){returni;}}if(lst->Size==lst->MaxList){return-1;}while(lst->Elements[j]>x)khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com {lst->Elements[j+1]=lst->Elements[j];j--;}lst->Elements[j+1]=x;lst->Size++;returnj+1;}voidSearch_Delete(List*lst,Tx,Ty){inti=0;if(lst->Size==0){printf("thelistisempty,cannotbedeleted!n");khdaw.comreturn;}for(intj=0;jSize;j++){if((lst->Elements[j]Elements[j]>y)){课后答案网lst->Elements[i]=lst->Elements[j];i=i+1;}}www.hackshp.cnlst->Size=i;}13．（第86页，第13题）给出下列稀疏矩阵的顺序三元组的行优先和列优先表示。答：14．（第86页，第14题）khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。答：第五章树第2题，第141页，对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？答：（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵第3题，P141n0khdaw.com=n2+2*n3+….+(m-1)nm+1第5题，P142（1)或者为空二叉树，或者所有结点的左子树都是空的单支树（2）或者为空二叉树，或者只有根结点的二叉树（3）或者为空二叉树，或者所有结点的右子树都是空的单支树课后答案网第7题，第142页，给出对图6-31中的树的先序遍历和后序遍历的结果。www.hackshp.cn答：先序：D，E，H,F，J，G，C,K,A，B中序：H，E，J，F，G，K，C，D,A，B后序：H，J，K，C，G,F，E，B，A,D第6题第142页，设对一棵二叉树进行中序遍历和后序遍历的结果分别为：（1）中序遍历BDCEAFHG（2）后序遍历DECBHGFA画出该二叉树。答：第8（3）题第142页，intcount=0；voidSizeOfLeaf(BTNode*t){if(t){if((!(t->RChild))&&(!(t->LChild)))khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com {count=count+1;}SizeOfLeaf(t->LChild);SizeOfLeaf(t->RChild);}}第13题第142页，将图题6-32中的树转换成二叉树，khdaw.com课后答案网并将图6-31中的二叉树转换成森林。www.hackshp.cn第18题第1438页，设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率。（1)画出哈夫曼树（2）计算带权路径长度khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 编码：A：1010B:1011C:100D:00E:01F:11第六章集合第4题，P155对半搜索算法要求其必须针对顺序存储的有序表。顺序搜索从头搜到尾，所以不影响。补充：已知（1，2，3，4，5，6，7，8，9，10，11）找到9比较几次？khdaw.comM=(1+11)/2=6比较一次6<9,找[7，11]M=(7+11)/2=99=9比较2次成功课后答案网所以一共比较2次成功第七章搜索树1．第189页，第（www.hackshp.cn1）,建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？第八章散列与跳表第3题，第209页，设散列表ht[11]，散列函数h(key)=key%11。采用线性探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55建立散列表。线性探查法：khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 伪随机探查法：P=130123456789105545352570805060对80：（3+13）%11=5对60：（5+13）%11=7二次探查法khdaw.com0123456789104535802570605055对80：（3+1*1）%11=4（3-1*1）%11=2对35：（2+1*1）%11=3（2-1*1）%11=1对45：（1+1*1）%11=2课后答案网（12-1*1）%11=0对55：（0+1*1）%11=1（0-1*1）%11=10第4题，第209页，双散列法：www.hackshp.cn7025803560455055H143325160H29160123456789105580352570604550对80：（3+1*9）%11=1对45：（1+1*1）%11=2（1+2*1）%11=3（1+3*1）%11=4（1+4*1）%11=5（1+5*1）%11=6对50：（6+1*6）%11=1（6+2*6）%11=7第九章图第（1）题，第243页，对下面的有向图求(1)每个顶点的入度和出度；khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com (2)强连通分量(3)邻接矩阵第（2）题，第243页，当以边〈1，0〉，〈1，3〉，〈2，1〉，〈2，4〉，〈3，2〉，〈3，4〉，〈4，0〉，〈4，1〉，〈4，5〉，〈5，0〉的次序从只有6个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。khdaw.com画出该邻接表。课后答案网www.hackshp.cn深度优先遍历：0，1，3，4，5，2宽度优先遍历：0，1，3，4，2，5第14题P244第第11章P11-2直接插入排序：初始序列（61）871203087097755326第1趟（6187）1203087097755326第2趟（126187）03087097755326第3趟（03126187）087097755326第4趟（0308126187）7097755326第5趟（030812617087）97755326khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 第6趟（03081261708797）755326第7趟（0308126170758797）5326第8趟（030812536170758797）26第9趟（03081226536170758797）简单选择排序初始序列（61871203087097755326第1趟（03）871261087097755326第2趟（0308）1261877097755326第3趟（030812）61877097755326第4趟（03081226）877097755361第5趟（0308122653）7097758761第6趟（030812265361）97758770第7趟（03081226536170）758797第8趟（0308122653617075）8797khdaw.com第9趟（030812265361707587）97课后答案网冒泡排序初始序列（61871203087097755326第1趟61120308708775532697第2趟www.hackshp.cn12030861707553268797第3趟03081261705326758797第4趟03081261532670758797第5趟03081253266170758797第6趟03081226536170758797第7趟03081226536170758797快速排序：初始序列61871203087097755326第1趟53261203086197757087第2趟08261203536197757087第3趟03081226536197757087第4趟03081226536197757087第5趟03081226536187757097第6趟03081226536170758797第7趟03081226536170758797khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com'