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

第1章 习题答案1. 填空题（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示） 数据元素的表示 元素之间关系的表示 数据元素。（2）已经实现 是一个概念 分离 分离（3）时、空效率 指人对算法阅读理解的难易程度 对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。（4）软硬件环境 问题规模的（5）最坏（6）O（n4） O（n2） （7）时间复杂度（8）n 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） , O（） （e）n , O（n）第2章 习题及答案1、填空题（1）address+m*i（2）顺序 顺序 顺序 链式存储 链式存储（3）亦相邻 不一定（4）n-i+1（5） 0ila的长度 -1jlb的长度-1 0klc的长度-1（6） 插入的位置，节点数n（顺序表长度n）（7）其前驱 O(n) O（1）（8）其前驱 O(n) O（1）（9）pnext=pnext next（10）headnext=Null head=Null headnext=head head=Null（11）headnext=headnextnext head=headnext（12）x=ppriordata; ppriordata=pnextdata; pnextdata=x;（13）p=headprior(或pnext=head)2判断题（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）3简答题(1)单向循环链表双向循环链表存储密度高低查找后继的时间复杂度O(1)O(1)查找前驱的时间复杂度O(n)O(1)（2）在带头结点的单链表上，查找指针p所指结点的前驱。（3）交换指针p与指针q所指结点的值。4算法设计题(1)void reverse(SeqList l) for (i=0; i=(l.listlength-1)/2; i+)l.elemil.eleml.listlength-1-i;(2)void delete(SeqList, int i, int k)/*从顺序表中删除自第i个元素开始的k个元素*/ if (il.listlength-1| k0) printf(“Error”);return;if (i+k=l.listlength) /*表中从i个元素起到最后一个元素有k个元素*/ for ( j=i+k; jl.listlength; j+) l.elemj-k=l.elemj; l.listlengt=l.listlength-k; else /*表中从i个元素起直到最后一个元素不足k个元素*/ l.listlength=i;(3)void insert(LinkList h, ElementType x)/*将x插入到递增链表h中，插入后的链表有序性不变*/ if (hnext=Null) /*空表时*/ q=(linklist) malloc (sizeof(ListNode);qnext=Null;qdata=x;hnext =q;p1=hnext; p2=h;while (p1next != Null & p1datax) p2=p1; p1=p1next;if ( p1next=Null & p1data=x) | (p1next!=Null & p1data=x)*/ q=(LinkList) malloc (sizeof(ListNode); qdata=x;p2next=q;qnext=p1;(4)void delete (LinkList p)/*在不带头结点且长度大于1的单向循环链表中，p指向某结点，删除p的前驱结点*/ ppp=pnext;while (pppnextnext != p)ppp =pppnext;/*删除p的前驱结点*/pp=pppnext;pppnext=ppnext;free(pp);(5) void delete (LinkList h)/*h为带头结点的，非降序排列的单链表的头指针，删除表中值相同的结点，使之只保留一个*/ p=hnext;if (!p) return;x=pdata;while (pnext)if (x != pnextdata) x = pnextdata;p = pnextelse q=pnext;pnext=pnextnext;free(q);void delete (LinkList h)/*删除带头结点的单链表h（指向头结点）中值为x的结点的前驱结点*/ if (!(hnext ) return;if (!(hnextnext) return;p1=hnextnext; p2=h;while (p1next & p1data != x ) p1=p1next;p2=p2next;if (p1data = x) q=p2next;p2next=p1;free(q);(7) Linklist subtraction (LinkList la, LinkList lb)/*la,lb分别为表示集合A,B的带头结点的单链表的头指针，A-B由la链表返回*/ if (!(lanext) return (la);else pa1=lanext ; pa2=la;if (!(lbnext) return (la);while (pa1) pb=lbnext ; while (pb & pa1data!=pbdata) pb=pbnext;if (pb) /*pa1data=pbdata*/ pa2next=pa1next;free(pa1);pa1=pa2next;else pa1=pa1next;pa2=pa2next; return (la);（8）LinkList intersection(LinkList la, LinkList lb)/*la,lb,lc分别为表示集合A,B,C的带头结点的递增有序的单链表的头指针，C=AB由lc链表返回*/ lc=(LinkList) malloc (sizeof(LinkNode); lcnext=null;tail=lc; /*tail指向lc链的尾结点*/if (!(lanext) return(lc);else pa=lanext;if (!(lbnext) return(lc);while (pa) pb=lbnext;while (pb & padata != pbdata) pb=pbnext;if (pb) insert(lc, tail, padata);pa=panext; return(lc);void insert (LinkList l, LinkList tail, ElemenType x)/*将值x插入到单链表l的尾部*/ p=(LinkList) malloc (sizeof(LinkNode)pdata=x; pnext=null;tailnext=p;tail=p;SeqList intersection(SeqList la, SeqList lb)/*集合A,B,C对应的顺序递增表为la,lb,lc，C=AB由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.elemb != la.elema; b+) if (bmin & p1data=0 & hdata0)*/ if (n=0)if (n = 0)return(1);else return( n*g(n/2) );11 11g(5)n g 5 5g(2)11 11g(5)n g 5 5g(2)11 11g(5)n g 2 2g(1) 5 5g(2)11 11g(5)n g 2 2g(1)11g(0) 5 5g(2)11 11g(5)n g 2 2g(1)11g(0)01 5 5g(2)11 11g(5)n g 2 2 5 1011 11g(5)n g 11 110n g 5 5g(2)11 11g(5)n g 2 2g(1)11(3) int akm( int m, int n)/*递归计算akm( m, n)的值*/ if (m=0 & n=0)if (m=0) return(n+1);else if (n=0) return( akm(m-1,1) );else return( akm(m-1,akm(m,n-1) );(4) $stackdstackr$stackd3stackr$stackd3*stackr$stackdstackr$stackd3stackr$stackd3*stackr$stackd3*(5*(-(5-(352stackr$stackd*(33stackr$stackd*33stackr$stackd9stackr$stackd+9stackr$stackd9(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)stackr+7stackr$stackd16(5)对于输入序列1,2,3,4,对应的24种排列是：1,2,3,4 1,2,4,3 1,3,2,4 1,3,4,2 1,4,2,3 1,4,3,22,1,3,4 2,1,4,3 2,3,1,4 2,3,4,1 2,4,1,3 2,4,3,13,1,2,4 3,1,4,2 3,2,1,4 3,2,4,1 3,4,1,2 3,4,2,14,1,2,3 4,1,3,2 4,2,1,3 4,2,3,1 4,3,1,2 4,3,2,1无下划线的序列可以通过相应的入、出栈得到。可以通过入、出栈得到的输出序列中的每一个数，在它后面的比它小的数应是降序排列的。(6)void AddQueue(Queue q, ElementType e) /*入队*/ if (q.count = maxsige) printf (“n overflow”); return;q.elem(q.front+q.count) % MaxSize=e;q.count+; ElementType DeleteQueue(Queue q)/*出队*/ if (q.count=0) return(nil);e=q.elemq.front;q.front=(q.front+1) % MaxSize;q.count-;return(e);(7) A,D是合法的int legality(SeqList l)/*入、出栈序列存放在l.elem数组中，该序列合法返回1，否则返回0*/ count=0;for (i=0; il.listlength; i+) if (l.elemi=I count+; else count-; if (count0) return(0); /*栈空时出栈*/ if (count=0) return(1);else return(0); /*栈不空（没有回到初始状态*/ （8）typedef struct Qnode ElementType data; Struct Qnode *next; QueueNode;typedef QueueNode *LinkQueue;void AddQueue(LinkQueue rear, ElementType e)/*带头结点的循环链表队列，只有指向尾结点的指针rear，对其实现入队操作*/ p=(LinkQueue) malloc (sizeof(QueueNode);pdata=e;pnext=rearnext; rearnext=p;rear=p;Elementype DeleteQueue(LinkQueue rear)/*带头结点的循环链表队列，只有指向尾结点的指针rear，对其实现出队操作*/ if( rearnext=rear) printf(“n empty”);return(nil);p=rearnextnext; e=pdata;rearnextnext=rearnextnextnext;free(p);return(e);(9)void AddQueue(CirQueue q, ElementType e)/*借助于堆栈s1、s2实现队列q的入队*/ Push (s1,e);ElementType DeleteQueue(CirQueue q)/*借助于堆栈s1、s2实现队列q的出队*/ if (Empty(s1) & Empty(s2) printf(“n empty”);return(nil);elseif ( !Empty(s2) ) Pop (s2);else while( !Empty(s1) )Push (s2, Pop(s1) );Pop(s2);第4章 习题及答案1. 填空题（1）字符（2）0 空格的个数（3）14 “bc cad cabcadfabc” “abc” 8 1(true) “bc cad cbcadf” “abcbc cad cabcadf” “bcad cabcadf”（4）197（5）三维数组arr623的每个元素的长度为4个字节，如果数组以行优先的顺序存储，且第1个元素的地址是4000，那么元素arr502的地址是4000+4*（5*2*3+0*3*2）=41282. 判断题（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）3. (1) v=j(2) 符号表s30t53u78堆01234567891011abcxabcyzxabcyzfree（3）最坏情况下的时间复杂度为O（m*n），其中m为串s的长度，n为串t的长度（4）三维数组arr623的每个元素的长度为4个字节，该数组要占6*2*3*4=144个字节，若数组以列优先的顺序存储，设第一个元素的首地址是4000，则元素arr502的存储地址是4029。（5） (0,0,1),(0,3,2),(1,1,3),(2,3,5),(3,0,2),(3,2,5)(6) 行优先：a 0,0,0,0 a 0,0,0,1 a 0,0,0,2 a 0,0,1,0 a 0,0,1,1 a 0,0,1,2a 0,1,0,0 a 0,1,0,1 a 0,1,0,2 a 0,1,1,0 a 0,1,1,1 a 0,1,1,2a 0,2,0,0 a 0,2,0,1 a 0,2,0,2 a 0,2,1,0 a 0,2,1,1 a 0,2,1,2a 1,0,0,0 a 1,0,0,1 a 1,0,0,2 a 1,0,1,0 a 1,0,1,1 a 1,0,1,2a 1,1,0,0 a 1,1,0,1 a 1,1,0,2 a 1,1,1,0 a 1,1,1,1 a 1,1,1,2 a 1,2,0,0 a 1,2,0,1 a 1,2,0,2 a 1,2,1,0 a 1,2,1,1 a 1,2,1,2列优先：a 0,0,0,0 a 1,0,0,0 a 0,1,0,0 a 1,1,0,0 a 0,2,0,0 a 1,2,0,0a 0,0,1,0 a 1,0,1,0 a 0,1,1,0 a 1,1,1,0 a 0,2,1,0 a 1,2,1,0a 0,0,0,1 a 1,0,0,1 a 0,1,0,1 a 1,1,0,1 a 0,2,0,1 a 1,2,0,1a 0,0,1,1 a 1,0,1,1 a 0,1,1,1 a 1,1,1,1 a 0,2,1,1 a 1,2,1,1a 0,0,0,2 a 1,0,0,2 a 0,1.0,2 a 1,1,0,2 a 0,2,0,2 a 1,2,0,2a 0,0,1,2 a 1,0,1,2 a 0,1,1,2 a 1,1,1,2 a 0,2,1,2 a 1,2,1,2(7) 稀疏矩阵压缩存储后会失去随机存取的功能，因为稀疏矩阵不能根据元素在矩阵中的位置求得在其在三元组顺序表中的位置，而特殊矩阵则可以。(8)当3tm*n 即 时，三元组的表示才有意义。(9) i=j 或 i+j=n+1 4、算法设计题（1）void Assign(BlockLink *s, char t)/*将存放在字符数组t中常量赋给s*/ ss=s; for(i=0; t0!=0; i+) if ( i % NodeNum = 0 ) j=0;p=(BlockLink*) malloc (sizeof(BlockLink);pnext=Null; ssnext=p; ss=p; pdataj=ti; j+;while (j!=NodeNum-1) pdataj=#;j+;（2）void frequency(int num)/* 统计输入字符串中数字字符和字母字符的个数。*/ for（i0；i= a& ch = A& ch = Z） /* 大写字母 */ i=ch-65+10;numi+； （3） int JudgEqual(ing a,int m,int n) /*判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。*/ for(i=0; im; i+)for(j=0; jn-1; j+) for(p=j+1; pn; p+) /*和同行其它元素比较*/if(aij=aip) return(0);for(k=i+1; km; k+) /*和第i+1行及以后元素比较*/for(p=0; pn; p+)if(aij=akp) return(0); return(1); /*元素互不相同*/ 二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为 (m*n-1)+(m*n-2)+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在每个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4，总的时间复杂度是O(m2*n2)。（4）#define MaxSize 线性表可能的最大长度typedef struct int row, column; elementtypedef struct element elemMaxSize;int listlength; SeqList;void GetSaddle(int A，int m，int n, SeqlList s) /*求矩阵Amn中的鞍点，鞍点的位置存放在顺序表s中*/s.listlength=0;for(i=0; im; i+)for(min=Ai0, j=0; jn; j+)if(Aijmin) min=Aij; /*求一行中的最小值*/for(j=0; jn; j+)if(Aij=min) /*判断这个(些)最小值是否鞍点*/for(flag=1, k=0; km; k+) if(minx， 这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否则，若下标已超出范围，则查找失败。void search(ElementType A,int m,int n,ElementType x,int *row,int *column) /* m*n的矩阵b,本算法查找x在矩阵b中的位置（*row,*column）*/ i=0; j=n; flag=0; /*flag是成功查到x的标志*/while(i=0 & !flag)if(bij=x) flag=1; else if (bijx) j-; else i+;if(flag) *row=i;*column=j;else *row=-1;*column=-1; 算法讨论算法中查找x的路线从右上角开始，向下（当xbi,j）或向左（当xbi,j）。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（bm,0），比较m+n次。（6）void TSMatrix_Addto(TSMatrix &A,TSMatrix B)/将三元组矩阵B加到A上for(i=0;iA.nums;i+)/*把A的所有元素都移到尾部以腾出位置*/A.dataMaxSize-A.nums+i=A.datai;pa=MaxSize-A.nums; pb=0; pc=0;for(x=0; xA.rows; x+) /*对矩阵的每一行进行加法*/while(A.datapa.rx) pa+;while(B.datapb.rB.datapb.c) A.datapc.r=x;A.datapc.c=B.datapb.c;A.datapc.d=B.datapb.d;pb+; pc+;elseA.datapc.r=x;A.datapc.c=A.datapa.c;A.datapc.d=A.datapa.dpa+; pc+;while(A.datapa=x) /*插入A中剩余的元素(第x行)*/A.datapc.r=x;A.datapc.c=A.datapa.c;A.datapc.d=A.datapa.dpa+; pc+;while(B.datapb=x) /*插入B中剩余的元素(第x行)*/ A.datapc.r=x;A.datapc.c=B.datapb.c;A.datapc.d=B.datapb.d;pb+; pc+;A.nums=pc;for(i=A.nums; i=2） 编号为i的非叶子结点的第j个孩子结点的编号是(i-1)*k+j+1。 编号为i的结点有右兄弟的条件是(i-1)%k0，其右兄弟的编号是i+1。（6）（a）先序序列：12345 中序序列：24531 后序序列：54321 （b）先序序列：12345 中序序列：13542 后序序列：54321（c）先序序列：123578624 中序序列：17583624 后序序列：78563421（d）先序序列：124735689 中序序列：472153869 后序序列：742589631先序线索树：中序线索树：后序线索树：132476598132476598NULL132476598NULLNULLNULL先序线索树中序线索树后序线索树（7）a的先序序列：ABCDEF a的后序序列：BDEFCAb的先序序列：GHIJK b的后序序列：IJKHGc的先序序列：LMPQRNO c的后序序列：QRPMNOL 森林的先序序列：ABCDEFGHIJKLMPQRNO 森林的后序序列：BDEFCAIJKHGQRPMNOL 转换后的二叉树：AGBDCMLENFHIJKOPQR 题中图5-35改为5-36 双亲数组表示： 易于求祖先dataparent0A-11B02C03D24E25F2孩子链表表示法：易于求子孙120A1B2C3D4E5F345孩子兄弟表示法：易于求子孙ABCrootDEF（8）哈夫曼树为：72423026161511987642 带权路径长度WPL=30*1+16*2+5*4+7*4+8*4+2*5+4*5=172（9）CABCDFAB6EABDFCEGHFHIJKE(a)(b)(c)DG（10）AEBCDFHIGJKLOMN（11）哈夫曼树及编码为：010001000011100111000011005941332618152120138119761111110101110104.（1）void PreOrderz(