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

1、数据结构与实训课后答案全集第1章习题答案1. 填空题（ 1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。（2）已经实现是一个概念分离分离（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据， 算法能给出相应的响应，而不是产生不可预料的后果。（4）软硬件环境问题规模的（5）最坏（6）O（n4）O（n2）（7）时间复杂度（8）nn(1n)O（n2）22. 判断题（ 1）（ 2）（ 3）（ 4）（ 5）（ 6）（ 7）（ 8）（ 9）（ 10）3. 简答题（ 1）略（见教材第 3 页的 1.2 数据结构的基本概念）（2）（a）n-1

2、，O（n）（b）n-1 ,2O（ n）（ c）11* n+1, O（n）（n 为初始值 100）（d）n,O（ n ）（e）n ,O（ n）第 2 章 习题及答案1、填空题（ 1）address+m*i（ 2）顺序 顺序 顺序 链式存储 链式存储（ 3）亦相邻不一定（ 4）n-i+1（5） 0ila 的长度-1j lb 的长度 -10klc 的长度 -1n(1n)（6）2插入的位置，节点数n（顺序表长度 n）（ 7 ） 其 前 驱O(n)O（1）（ 8 ） 其 前 驱O(n)O（1）（ 9）pnext=p next next（ 10 ） head next=Nullhead=Null3head

3、next=headhead=Null（ 11 ） head next=head next nexthead=headnext（12）x=pprior data;pprior data=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、所指结点的值。4算法设计题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

5、; j+)l.elemj-k=l.elemj;l.listlengt=l.listlength-k;else /* 表中从 i 个元素起直到最后一个元素不足 k 个元素 */5l.listlength=i;(3)voidinsert(LinkList h, ElementTypex)/* 将 x 插入到递增链表 h 中，插入后的链表有序性不变 */ if (h next=Null) /* 空表时 */ q=(linklist) malloc (sizeof(ListNode);qnext=Null;qdata=x;hnext =q;p1=h next;p2=h;while (p1 next !

6、= Null&p1datax) p2=p1; p1=p1next;if ( p1 next=Null& p1 data=x)| (p1next!=Null & p1 data=x)*/ q=(LinkList) malloc (sizeof(ListNode); qdata=x;p2next=q;qnext=p1;(4)voiddelete (LinkList p)/* 在不带头结点且长度大于 1 的单向循环链表中， p 指向某结点，删除 p 的前驱结点 */ppp=p next;while (ppp nextnext != p)ppp =ppp next;/* 删除 p 的前驱结点 */ p

7、p=ppp next;pppnext=pp next; free(pp);7(5)void delete (LinkList h)/*h 为带头结点的，非降序排列的单链表的头指针，删除表中值相同的结点，使之只保留一个*/ p=h next;if (!p)return;x=p data;while (p next)if (x != p nextdata) x = p nextdata; p = pnextelse q=p next;pnext=p nextnext; free(q);void delete (LinkList h)8/* 删除带头结点的单链表 h（指向头结点）中值为 x 的结点的

8、前驱结点 */if (!(h next )return;if (!(h nextnext)return;p1=hnextnext;p2=h;while (p1 next & p1 data != x )p1=p1next;p2=p2next;if (p1 data = x)q=p2next;p2next=p1;free(q);(7)Linklist subtraction (LinkList la, LinkList lb) /*la,lb 分别为表示集合 A,B 的带头结点的单链表的头指针， A-B 由 la 链表返回 */if (!(la next)9return (la);else pa

9、1=lanext ; pa2=la;if (!(lb next)return (la);while (pa1) pb=lb next ;while (pb & pa1 data!=pb data)pb=pb next;if (pb)/*pa1 data=pb data*/ pa2next=pa1 next;free(pa1);pa1=pa2next;else pa1=pa1next;pa2=pa2next;return (la);10（ 8）LinkList intersection(LinkList la, LinkList lb) /*la,lb,lc 分别为表示集合 A,B,C 的带头结

10、点的递增有序的单链表的头指针， C=A B 由 lc 链表返回*/ lc=(LinkList) malloc (sizeof(LinkNode);lc next=null;tail=lc; /*tail 指向 lc 链的尾结点 */ if (!(la next)return(lc);elsepa=lanext;if (!(lb next)return(lc);while (pa) pb=lb next;while (pb & pa data != pb data)pb=pb next;if (pb) insert(lc, tail, pa data); pa=panext;11return(l

11、c);voidinsert(LinkListl,LinkListtail,ElemenType x)/* 将值 x 插入到单链表 l 的尾部 */ p=(LinkList) malloc (sizeof(LinkNode) pdata=x;pnext=null; tail next=p;tail=p;SeqList intersection(SeqList la, SeqList lb)/* 集合 A,B,C 对应的顺序递增表为la,lb,lc ，C=A B 由 lc 表示 */ lc.listlength=0;if (la.listlength=0| lb.listlength=0)retu

12、rn(lc)for ( a=0; ala.listlength; a+) for ( b=0; blb.listlength & lb.elemb != la.elema; b+)if (bmin & p1 data= 0& h data0)*/ if (n=0)if (n = 0)return(1);18elsereturn( n*g(n/2) );0111g11gnnnnn112nnnn(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)19re

13、turn( akm(m-1,1) );elsereturn( akm(m-1,akm(m,n-1) );(4)(*5$3$3$3$3stack stackstackstackstackstackstackstackstackstack(a(b(c(d(e-(2(*5*5*3*3$3$3$3$3$9stackstackstackstackstackstackstackstackstackstack(f(g(h(i(j+7$9$9$16stackstackstackstackstackstack(k(l(m(5)20对于输入序列 1,2,3,4,对应的 24 种排列是：1,2,3,41,2,4,3

14、1,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1无下划线的序列可以通过相应的入、出栈得到。可以通过入、出栈得到的输出序列中的每一个数，在它后面的比它小的数应是降序排列的。(6)void AddQueue(Queue q, ElementType e)/* 入队 */ if (q.count = maxsige) printf ( “n o

15、verflow ”);return;q.elem(q.front+q.count) % MaxSize=e; q.count+;21ElementTypeDeleteQueue(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.l

16、istlength; i+)if (l.elemi= I count+;else count-;22if (count0)return(0);/* 栈空时出栈 */if (count=0)return(1);elsereturn(0); /* 栈不空（没有回到初始状态*/（ 8）typedef struct Qnode ElementType data; Struct Qnode *next; QueueNode;typedef QueueNode *LinkQueue;void AddQueue(LinkQueue rear, ElementType e)/* 带头结点的循环链表队列，只有指

17、向尾结点的指针 rear ，对其实现入队操作 */ p=(LinkQueue) malloc (sizeof(QueueNode); pdata=e;23pnext=rear next;rear next=p;rear=p;Elementype DeleteQueue(LinkQueue rear)/* 带头结点的循环链表队列，只有指向尾结点的指针 rear ，对其实现出队操作 */ if( rear next=rear) printf ( “n empty ”); return(nil);p=rear nextnext;e=pdata;rear nextnext=rear nextnextn

18、ext;free(p);return(e);(9)void AddQueue(CirQueue q, ElementType e)24/* 借助于堆栈 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(

19、s1) );Pop(s2);第 4 章 习题及答案1. 填空题25（1）字符（2）0空格的个数（ 3 ） 14“bccadcabcadfabc”“abc”81(true)“bccad 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)0 (

20、当 ij1)u1 (当 ij）2 （当 ij-1）v=j(2)符号表s30t5326u78堆012345678910 11abcx abcyzxa bcyzfree（ 3）最坏情况下的时间复杂度为 O（m*n ），其中 m 为串 s 的长度， n 为串 t 的长度（ 4）三维数组 arr623 的每个元素的长度为4 个字节，该数组要占 6*2*3*4=144 个字节，若数组以列优先的顺序存储， 设第一个元素的首地址是 4000，则元素 arr502 的存储地址是4029。（ 5）jk(5 l ) (i j ) 5l0 (0,0,1),(0,3,2),(1,1,3),(2,3,5),(3,0,2

21、),(3,2,5)(6)27行优先：a0,0,0,0a0,0,0,1a0,0,0,2a0,0,1,0a0,0,1,1a 0,0,1,2a0,1,0,0a0,1,0,1a0,1,0,2a0,1,1,0a0,1,1,1a 0,1,1,2a0,2,0,0a0,2,0,1a0,2,0,2a0,2,1,0a0,2,1,1a 0,2,1,2a1,0,0,0a1,0,0,1a1,0,0,2a1,0,1,0a1,0,1,1a 1,0,1,2a1,1,0,0a1,1,0,1a1,1,0,2a1,1,1,0a1,1,1,1a 1,1,1,2a1,2,0,0a1,2,0,1a1,2,0,2a1,2,1,0a1,2,

22、1,1a 1,2,1,2列优先：a0,0,0,0a1,0,0,0a0,1,0,0a1,1,0,0a0,2,0,0a 1,2,0,0a0,0,1,0a1,0,1,0a0,1,1,0a1,1,1,0a0,2,1,0a 1,2,1,0a0,0,0,1a1,0,0,1a0,1,0,1a1,1,0,1a0,2,0,1a 1,2,0,1a0,0,1,1a1,0,1,1a0,1,1,1a1,1,1,1a0,2,1,1a 1,2,1,128a 0,0,0,2a 1,0,0,2a 0,1.0,2a 1,1,0,2a0,2,0,2a 1,2,0,2a 0,0,1,2a 1,0,1,2a 0,1,1,2a 1,1,

23、1,2a0,2,1,2a 1,2,1,2(7) 稀疏矩阵压缩存储后会失去随机存取的功能，因为稀疏矩阵不能根据元素在矩阵中的位置求得在其在三元组顺序表中的位置， 而特殊矩阵则可以。n * m(8)当 3tm*n即 t3时，三元组的表示才有意义。(9) i=j 或 i+j=n+12(i1) ( 当 ij )k2(i1)1（当 ijn1）4、算法设计题（ 1）voidAssign(BlockLink *s, char t)/* 将存放在字符数组t 中常量赋给 s*/ ss=s;for(i=0; t0!= 0;i+) if ( i % NodeNum = 0 ) j=0;29p=(BlockLink*

24、)malloc(sizeof(BlockLink);pnext=Null;ss next=p;ss=p;pdataj=ti;j+;while (j!=NodeNum-1) pdataj= #; j+;（ 2）voidfrequency(int num)/* 统计输入字符串中数字字符和字母字符的个数。 */for （i 0；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

25、+) for(j=0; jn-1; j+)31 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) 比较一次 ,所以在元素互不相等

26、时总的 比 较 次 数 为 (m*n-1)+(m*n-2)+ +2+1=（ m*n ）(m*n-1)/2 。在有相同元素时 ,可能第一次比较就相同 ,也可能最后一次比较时相同 ,设在每个位置上均可能相同 ,这时的平均比较次数约为 （ m*n ） (m*n-1)/4 ， 总 的 时 间 复 杂 度 是 O(m 2*n 2)。32（ 4）#define MaxSize 线性表可能的最大长度 typedef struct int row, column; elementtypedef struct element elemMaxSize; int listlength; SeqList;void G

27、etSaddle(int A ，int m ，int n, SeqlList s)/* 求矩阵 A m n 中的鞍点，鞍点的位置存放在顺序表 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+)33if(Aij=min) /* 判断这个 (些)最小值是否鞍点 */for(flag=1,k=0;km;k+)if(minx ，这情况下向 j 小的方向继续查找； 二是 Ai,jx ，下步应向 i 大的方向查找；三是 Ai,j=x ，查找成功。否则，若下标已超出范围， 则查找失败。void search(ElementType A,int m,intn,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(