《《数据结构-C语言描述》答案--陈慧南主编》由会员分享，可在线阅读，更多相关《《数据结构-C语言描述》答案--陈慧南主编（8页珍藏版）》请在金锄头文库上搜索。
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;dox+; i=2*i; while （i=(y+1)*(y+1) y+;划线语句的执行次数为 n 。第二章两种基本的数据结构 2-4 Loc(Aijk)=134+(i*n*p+j*p+k)*22-9.第 34 页 习题(2).9 void Invert(T elements, int length) /length 数组长度/ elements为需要逆序的数组T
2、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) ; Push(B); Pop(B); Push(C) ; Pop(C); Push(D) ; Pop(D);Push(E) ; Pop(E);2）不能得到
3、，因为 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. TOP1 TOP2栈满 Top2-Top1=1 Top1n-1 栈 2 空9：void PrintQueue(Queue q) int f
4、irst=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.Front=(q.Front+1)%q.MaxQueue;void PrintQueue3(Queue q) for(;
5、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=lst-MaxList)return -1; while(lst-Elementsjx) lst-Elementsj+
6、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-Elementsj; i=i+1; lst-Size=i; 13 （第 86 页，第 1
7、3 题）给出下列稀疏矩阵的 顺序三元组的行优先和列优先表示。 答：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-RChi
9、ld)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：1010B: 1011 C: 100D: 00 E:01 F: 11第六章 集合 第 4 题，P155 对半搜索算法要求其必须针对顺序存储的有序表。 顺序搜索从头搜到尾，所以不影响。补充： 已知（1
10、，2，3，4，5，6，7，8，9，10，11）找到 9 比较几次？ M=(1+11)/2=6 比较一次 69 ,找7，11 M=(7+11)/2=9 9=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 建立散列表。 线性探查法：
11、伪随机探查法：P=13012345678910 5545352570805060 对 80： （3+13）%11=5 对 60： （5+13）%11=7二次探查法012345678910 4535802570605055 对 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 页， 双散列法： 7025803560455055 H143325160 H2916012345
12、678910 5580352570604550 对 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) 每个顶点的入度和出度；(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 个顶点没有边的图
13、开始，通过依此插入这些边，建立邻接表结构。 画出该邻接表。深度优先遍历：0，1，3，4，5，2 宽度优先遍历：0，1，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
14、 趟 （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 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 第 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 7
