《数据结构与实训课后答案全集》由会员分享，可在线阅读，更多相关《数据结构与实训课后答案全集（38页珍藏版）》请在金锄头文库上搜索。
1、1第 1 章 习题答案1. 填空题（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示） 数据元素的表示 元素之间关系的表示 数据元素。（2）已经实现 是一个概念 分离 分离（3）时、空效率 指人对算法阅读理解的难易程度 对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。（4）软硬件环境 问题规模的（5）最坏（6）O（n 4） O（n 2） （7）时间复杂度（8）n O（ n2）)1(2. 判断题（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）3. 简答题（1）略（见教材第 3 页的 1.2 数据结构的基本概念）（2） （a）n-1 ， O（n ）
2、（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 的长度 -1j lb 的长度-1 0klc 的长度-1（6） 插入的位置，节点数 n（顺序表长度 n）2)1(n（7）其前驱 O(n) O（1）（8）其前驱 O(n) O（1）（9）pnext=pnext next（10）headnext=Null head=Null headnext=head head=Nu
3、ll（11）headnext=headnextnext head=headnext（12）x=ppriordata; ppriordata=pnext data; pnextdata=x;（13）p=headprior(或 pnext=head)2判断题（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）3简答题(1)2单向循环链表 双向循环链表存储密度 高 低查找后继的时间复杂度 O(1) O(1)查找前驱的时间复杂度 O(n) O(1)（2）在带头结点的单链表上，查找指针 p 所指结点的前驱。（3）交换指针 p 与指针 q 所指结点的值。4算法设计题(1)void reverse
4、(SeqList l) for (i=0; il.eleml.listlength-1-i;(2)void delete(SeqList, int i, int k)/*从顺序表中删除自第 i 个元素开始的 k 个元素*/ if (il.listlength-1| k=x) | (p1next!=Null & p1data=x)*/ q=(LinkList) malloc (sizeof(ListNode); qdata=x;p2next=q;qnext=p1;(4)void delete (LinkList p)/*在不带头结点且长度大于 1 的单向循环链表中，p 指向某结点，删除 p 的前
5、驱结点*/ ppp=pnext;while (pppnextnext != p)ppp =pppnext;/*删除 p 的前驱结点*/pp=pppnext;pppnext=ppnext;free(pp);(5) void delete (LinkList h)/*h 为带头结点的，非降序排列的单链表的头指针，删除表中值相同的结点，使之只保留一个*/ p=h next;if (!p) return;x=pdata;while (pnext)if (x != pnextdata) x = pnextdata;p = pnextelse q=p next;pnext=pnext next;free(
6、q);4void 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 的带头结点的
7、单链表的头指针，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);5（8）LinkList intersection(LinkLi
8、st la, LinkList lb)/*la,lb,lc 分别为表示集合 A,B,C 的带头结点的递增有序的单链表的头指针， C=AB 由 lc链表返回*/ lc=(LinkList) malloc (sizeof(LinkNode); lcnext=null;tail=lc; /*tail 指向 lc 链的尾结点*/if (!(la next) return(lc);elsepa=lanext;if (!(lbnext) return(lc);while (pa) pb=lbnext;while (pb & padata != pbdata)pb=pbnext;if (pb) insert
9、(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;tail next=p;tail=p;SeqList intersection(SeqList la, SeqList lb)/*集合 A,B,C 对应的顺序递增表为 la,lb,lc，C=AB 由 lc 表示*/ lc.listlength=0;if (
10、la.listlength=0 | lb.listlength=0) return(lc)for ( a=0; amin & p1data=0 & hdata0)*/ if (n=0)if (n = 0)return(1);else return( n*g(n/2) );11 11g(5)n g5 5g(2)11 11g(5)n g5 5g(2)11 11g(5)n g2 2g(1)5 5g(2)11 11g(5)n g2 2g(1)1 1g(0)5 5g(2)11 11g(5)n g2 2g(1)1 1g(0)0 15 5g(2)11 11g(5)n g2 25 1011 11g(5)n g
11、11 110n g5 5g(2)11 11g(5)n g2 2g(1)1 1(3) 9int 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) $stackd stackr$stackd3stackr$stackd3*stackr$stackd stackr$stackd3stackr$stackd3*stackr$stackd3*(5*(-(5-(3
12、52stackr$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,2102,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
13、 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
14、(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; i= a & ch = A& ch x， 这情况下向 j 小的方向继续查找；二是 Ai,j=0 & !flag)16if(bij=x) flag=1;else if (bijx) j-; else i+;if(flag) *row=i;*column=j;else *row=-1;*column=-1;算法讨论算法中查找 x 的路线从右上角开始，向下（当 xbi,j）或向左（当 xB.datapb.c) A.datapc.r=x;A.datapc.c=B.datapb.c;A.datapc.d=B.datapb.d;pb+; pc+;els
