《《数据结构-C语言描述》(陈慧南 主编)课后习题答案 西安电子科技大学出版社.doc》由会员分享，可在线阅读，更多相关《《数据结构-C语言描述》(陈慧南 主编)课后习题答案 西安电子科技大学出版社.doc（11页珍藏版）》请在三一文库上搜索。
1、思路岛答案网 整理提供第一章 绪论1（第14页，第（18）题） 确定划线语句的执行次数，计算它们的渐近时间复杂度。(1) i=1; k=0; do k=k+10*i; i+; while(i=2），n=1时执行1次 。(2）i=1; x=0; do x+; i=2*i; while （in）; 划线语句的执行次数为 log2n。(3) for(int i=1;i=n;i+) for(int j=1;j=i;j+) for (int k=1;k=(y+1)*(y+1) y+; 划线语句的执行次数为 n 。第二章 两种基本的数据结构2-4Loc(Aijk)=134+(i*n*p+j*p+k)*2
2、2-9.第34页 习题(2).9 void Invert(T elements, int length) /length数组长度 / elements为需要逆序的数组 T e; for (int i=1;iLink; p-Link=first; first=p; p=q;第三章 栈与队列1 第54页 习题(1） 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。 1）A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A答：（1） Push（A）; Pop(A)
3、 ; Push(B); Pop(B); Push(C) ; Pop(C); Push(D) ; Pop(D); Push(E) ; Pop(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. Stack1 Stack2 TOP1 T
4、OP2栈满 Top2-Top1=1 Top1n-1 栈2空9：void PrintQueue(Queue q) int first=q.Front+1; while (first)%q.MaxQueue)!=q.Rear) printf(%d n ,q.Elementsfirst); first=first+1; printf(%d n ,q.Elementsfirst);void PrintQueue2(Queue q) for(int i=1; q.Front!=q.Rear; i+) printf(%d n ,q.Elements(q.Front+1)%q.MaxQueue); q.Fr
5、ont=(q.Front+1)%q.MaxQueue; void PrintQueue3(Queue q) for(; q.Front!=q.Rear; q.Front=(q.Front+1)%q.MaxQueue) printf(%d n ,q.Elements(q.Front+1)%q.MaxQueue); 第四章 线性表与数组1（85页）int Search_Insert(List *lst, T x)int i, j;j=lst-Size-1; for (i=lst-Size-1; i=0; i-) if(lst-Elementsi=x) return i; if (lst-Size=
6、lst-MaxList) return -1; while(lst-Elementsjx)lst-Elementsj+1=lst-Elementsj;j-;lst-Elementsj+1=x;lst-Size+;return j+1;void Search_Delete(List *lst, T x, T y)int i=0;if(lst-Size=0)printf(the list is empty,can not be deleted!n);return;for (int j=0; jSize; j+)if(lst-ElementsjElementsjy)lst-Elementsi=lst
7、-Elementsj;i=i+1;lst-Size=i;13（第86页，第13题）给出下列稀疏矩阵的顺序三元组的行优先和列优先表示。答：14（第86页，第14题） 对题图4-5的稀疏矩阵执行矩阵转置时数组num和k的值。 答：第五章 树第2题，第141页， 对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵第3题，P141 n0=n2+2*n3+.+ (m-1)nm+1第5题，P142（1)或者为空二叉树，或者所有结点的左子树都是空的单支树（2）或者为空二叉树，或者只有根结点的二叉树（3）或者为空二叉树，或者所
8、有结点的右子树都是空的单支树第7题，第142页， 给出对图6-31中的树的先序遍历和后序遍历的结果。答：先序： 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）中序遍历 B D C E A F H G （2）后序遍历 D E C B H G F A 画出该二叉树。答： 第8（3）题 第142页，int count=0；void SizeOfLeaf(BTNode *t) if (t) if(!(t-RC
9、hild)&(!(t-LChild) count=count+1; SizeOfLeaf(t-LChild); SizeOfLeaf(t-RChild); 第13题 第142页， 将图题6-32中的树转换成二叉树， 并将图6-31中的二叉树转换成森林。 第18题 第1438页， 设S=A,B,C,D,E,F，W=2,3,5,7,9,12，对字符集合进行哈夫曼编码，W为各字符的频率。（1) 画出哈夫曼树（2）计算带权路径长度 编码：A：1010 B: 1011 C: 100 D: 00E:01F: 11第六章 集合第4题，P155对半搜索算法要求其必须针对顺序存储的有序表。顺序搜索从头搜到尾，所
10、以不影响。补充：已知（1，2，3，4，5，6，7，8，9，10，11）找到9比较几次？M=(1+11)/2=6 比较一次69 ,找7，11M=(7+11)/2=99=9 比较2次成功所以一共比较2次成功第七章 搜索树1第189页，第（1）,建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？第八章 散列与跳表第3题，第209页， 设散列表ht11，散列函数h(key)=key % 11。采用线性探查法解决冲突，试用关键字值序 列：70，25，80，35，60，45，50，55 建立散列表。线性探查法： 伪随机探查法：P=1301
11、23456789105545352570805060对80： （3+13）%11=5 对60： （5+13）%11=7二次探查法0123456789104535802570605055对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页， 双散列法：7025803560455055H143325160H29160123456789105580352570604550对80： （3+1*9
12、）%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) 每个顶点的入度和出度； (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个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。画出该邻接表。 深度优先遍历：0，1，3，4，5，2宽度优先遍历：0，1，
13、3，4，2，5第14题 P244（2）计算带权路径长度P第第11章P11-2直接插入排序：初始序列（61）87 12 03 08 70 97 75 53 26第1趟 （61 87）12 03 08 70 97 75 53 26第2趟 （12 61 87）03 08 70 97 75 53 26第3趟 （03 12 61 87）08 70 97 75 53 26第4趟 （03 08 12 61 87）70 97 75 53 26第5趟 （03 08 12 61 70 87） 97 75 53 26第6趟 （03 08 12 61 70 87 97）75 53 26第7趟 （03 08 12 61
14、 70 75 87 97）53 26第8趟 （03 08 12 53 61 70 75 87 97）26第9趟 （03 08 12 26 53 61 70 75 87 97）简单选择排序 初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 （03）87 12 61 08 70 97 75 53 26第2趟 （03 08）12 61 87 70 97 75 53 26第3趟 （03 08 12）61 87 70 97 75 53 26第4趟 （03 08 12 26）87 70 97 75 53 61第5趟 （03 08 12 26 53）70 97 75 87 61第
15、6趟 （03 08 12 26 53 61）97 75 87 70第7趟 （03 08 12 26 53 61 70）75 87 97第8趟 （03 08 12 26 53 61 70 75）87 97第9趟 （03 08 12 26 53 61 70 75 87）97冒泡排序初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 61 12 03 08 70 87 75 53 26 97 第2趟 12 03 08 61 70 75 53 26 87 97第3趟 03 08 12 61 70 53 26 75 87 97第4趟 03 08 12 61 53 26 70 7
16、5 87 97第5趟 03 08 12 53 26 61 70 75 87 97第6趟 03 08 12 26 53 61 70 75 87 97第7趟 03 08 12 26 53 61 70 75 87 97快速排序：初始序列 61 87 12 03 08 70 97 75 53 26第1趟 53 26 12 03 08 61 97 75 70 87第2趟 08 26 12 03 53 61 97 75 70 87第3趟 03 08 12 26 53 61 97 75 70 87第4趟 03 08 12 26 53 61 97 75 70 87第5趟 03 08 12 26 53 61 87 75 70 97第6趟 03 08 12 26 53 61 70 75 87 97第7趟 03 08 12 26 53 61 70 75 87 97