数据结构与实训张红霞 白桂梅 主编 习题答案

1、第1章 习题答案1. 填空题1在计算机中的存储映像是逻辑结构在计算机中的实现或存储表示 数据元素的表示 元素之间关系的表示 数据元素。2已经实现 是一个概念 别离 别离3时、空效率 指人对算法阅读理解的难易程度 对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。4软硬件环境 问题规模的5最坏6On4 On2 7时间复杂度8n On22. 判断题123456789103. 简答题1略见教材第3页的1.2数据结构的根本概念2an-1，On b n-1 , Onc11* n+1, Onn为初始值100d , O en , On第2章 习题及答案1、填空题1address+m*i2顺

2、序 顺序 顺序 链式存储 链式存储3亦相邻 不一定4n-i+15 0ila的长度 -1jlb的长度-1 0klc的长度-16 插入的位置，节点数n顺序表长度n7其前驱 O(n) O18其前驱 O(n) O19pnext=pnext next10headnext=Null head=Null headnext=head head=Null11headnext=headnextnext head=headnext12x=ppriordata; ppriordata=pnextdata; pnextdata=x;13p=headprior(或pnext=head)2判断题123456789103简答

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);

4、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

5、(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=

6、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 (

7、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 (

8、!(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);8LinkList intersection(LinkList la, LinkList lb)/*la,lb,l

9、c分别为表示集合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

10、(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)f

11、or ( 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

12、 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$stackd3sta

13、ckr$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,

14、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) /*入队*/ = maxsige) printf (“n overflow); return;q.elem(q.front+q.count) % MaxSize=e;q.count+; ElementType D

15、eleteQueue(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 (

16、count=0) return(1);else return(0); /*栈不空没有回到初始状态*/ 8typedef 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; re

17、arnext=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);ElementT

18、ype 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字符20 空格的个数314 “bc cad cabcadfabc “abc 8 1(true) “bc cad cbcadf “abcbc cad cabcadf “bcad cabcadf4

19、1975三维数组arr623的每个元素的长度为4个字节，如果数组以行优先的顺序存储，且第1个元素的地址是4000，那么元素arr502的地址是4000+4*5*2*3+0*3*2=41282. 判断题123456789103. (1) v=j(2) 符号表s30t53u78堆01234567891011abcxabcyzxabcyzfree3最坏情况下的时间复杂度为Om*n，其中m为串s的长度，n为串t的长度4三维数组arr623的每个元素的长度为4个字节，该数组要占6*2*3*4=144个字节，假设数组以列优先的顺序存储，设第一个元素的首地址是4000，那么元素arr502的存储地址是402

20、9。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

21、,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

22、,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、算法设计题1void Ass

23、ign(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+;2void frequency(int num)/* 统计输入字符串中数字字符和字母字符的个数。*/ fori0；i= a& ch = A& ch = Z /* 大写字母

24、*/ 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); /*元素互不相同*/ 二维数组中的每一个元素同其它元素都比拟一

25、次，数组中共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 elem

26、ent 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 小的方向继续查找；二是

27、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

28、=-1;*column=-1; 算法讨论算法中查找x的路线从右上角开始，向下当xbi,j或向左当xbi,j。向下最多是m，向左最多是n。最正确情况是在右上角比拟一次成功，最差是在左下角bm,0，比拟m+n次。6void 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+) /*对矩阵的每一行进行加法*/wh

29、ile(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=

30、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。6a先序序列：12345 中序序列：24531 后序序列：54321 b先序序列：12345 中序序列：13542 后序序列：54321c先序序列：12357864 中序序列：17583624 后序序列：78563421d先序

31、序列：124735689 中序序列：472153869 后序序列：742589631先序线索树：中序线索树：后序线索树：132476598132476598NULL132476598NULLNULLNULL先序线索树中序线索树后序线索树7a的先序序列：ABCDEF a的后序序列：BDEFCAb的先序序列：GHIJK b的后序序列：IJKHGc的先序序列：LMPQRNO c的后序序列：QRPMNOL 森林的先序序列：ABCDEFGHIJKLMPQRNO 森林的后序序列：BDEFCAIJKHGQRPMNOL 转换后的二叉树：AGBDCMLENFHIJKOPQR 题中图5-35改为5-36 双亲数组

32、表示： 易于求祖先dataparent0A-11B02C03D24E25F2孩子链表表示法：易于求子孙120A1B2C3D4E5F345孩子兄弟表示法：易于求子孙ABCrootDEF8哈夫曼树为：72423026161511876542 带权路径长度WPL=30*1+16*2+5*4+7*4+8*4+2*5+4*5=1729CABCDFAB6EABDFCEGHFHIJKE(a)(b)(c)DG10AEBCDFHIGJKLOMN11哈夫曼树及编码为：010001000011100111000011005941332618152120138119761111110101110104.1void P

33、reOrderz(BinTree root) BinTree sM; /设栈的容量足够大 top= -1; p=root; do while (p!=NULL)printf(“%c,p-data); s+top=p; p=p-child;if (top!= -1)p=stop-; p=p-rchild; while (top!= -1)| (p!=NULL);(2)int count=0;void countnode1(BinTree root) if (root=NULL) return; if (root-lchild!=NULL & root-rchild=NULL) | (root-l

34、child=NULL & root-rchild!=NULL)count+; countnode1(root-lchild); countnode1(root-rchild);(3)int count(BinTree root) if (root=NULL) return 0; if (root-lchild=NULL & root-rchild=NULL) return 1; return count(root-lchild)+count(root-rchild);(4)int level(BinTree root, ElemType x)/在以root为根的二叉树中按先序查找值为x的结点，

35、找到返回其所在层数否那么返回0 BinTree p,f,stack150; /设栈的容量足够大 int h,stack250 /stack2用来保存p结点所在的层数 int top=-1; /置空栈。stack1和stack2可共用一个栈顶指针p=root; h=1; /根为第一层do while (p!=NULL & p-data!=x) stack1+top=p; stack2top=h; p=p-lchild; h+; if (p!=NULL) return h; else if (top!=-1) p=stack1top; h=stack2top-; p=p-rchild; h+; w

36、hile (p!=NULL) | (top!=-1);return 0;(5) 在先序线索树中查找*p的先序后继假设*p有左孩子即ltag=0，那么左孩子为后继；假设*p无左孩子即ltag=1，那么右孩子为后继ThBinTree PreOrderSucc(ThBinTree root) if (root-ltag=0)return root-lchild; elsereturn root-rchild; 在后序线索树中查找*p的后序前驱假设*p有右孩子即rtag=0，那么右孩子为前驱；假设*p无右孩子即rtag=1，那么左孩子为前驱。ThBinTree PreOrderPre(ThBinTre

37、e root) if (root-rtag=0)return root-rchild; elsereturn root-lchild;第6章 习题答案 (1) e=(2) n(n 1)(3)入度(4)先序 层次 (5) n-1(6)O(n2) O(elog2e) kruskal (7)4(8)边的数目(9)n2-e(10)n+1123456789101v4v2v5v3v1 邻接矩阵：0 1 0 1 01 0 0 1 10 0 0 1 11 1 1 0 00 1 1 0 0 邻接表：123451412 224 43553TD(V1)=2 TD(V2)=3 TD(V3)=2 TD(V4)=3 TD

38、(V5)=22邻接矩阵为：0 0 0 0 0 01 0 0 1 0 00 0 0 0 0 10 0 1 0 1 11 0 0 0 0 01 1 0 0 1 0 邻接表为：012345520003 14543边数为邻接矩阵中非零或非元素数目除以2。假设邻接矩阵A中的元素Aij的值为非零，那么顶点Vi和Vj之间有边相连对于任意一个顶点i，它的度为邻接矩阵第i行或第i列的非零或非元素数目。4题中无向图改为有向图。边弧数为邻接表中所有单链表的边结点数目。假设第i个单链表中存在一个边结点，其adjvex域的值为j，那么顶点Vi和Vj之间有边弧相连对于任意一个顶点i，它的入度为所有单链表中adjvex域的

39、值为i的边结点数目，它的出度为第i个单链表中边结点数目。5邻接表：012345112662513 0340567 74 把题中V1改V0。 深度优先搜索：V0，V1，V3，V4，V7，V2，V5，V6 广度优先搜索：V0，V1，V2，V3，V4，V5，V6，V7612245DACBFE1224ACBFE122ACBE12ACB1ACA 12245DACBFE1224DACBFE122DACBFE12DACBFE1DACBFE 权值：1+2+2+4+5=147题中图的顶点标记改为数字，如下列图，且求从1到其它顶点的最短路径。10001022041510300015004005图236142201

40、020154153010104 循环集合Sv距离数组dist路径数组path123456123456初始化102015-111-1-1-111,330191525-131-1-1321,3,22019152925-131-12331,3,2,6601915292925-13162341,3,2,6,4401915292925-13162351,3,2,6,4,5501915292925-1316238V0，V4，V1，V5，V2，V3 V0，V4，V1，V2，V5，V3 V0，V4，V5，V1，V2，V3 V4，V5，V0，V1，V2，V3 V4，V0，V1，V2，V5，V3 V4，V0，V5

41、，V1，V2，V34.1采用邻接表作为存储结构void dfs1(Adjlist g, int v) int visitedN; ArcNode *stackN,*p; int j,top=-1; for (j=1;j-1) while (p!=NULL) j=p-adjvex; if (visitedj!=0) /顶点j被访问过 p=p-nextarc; /继续找顶点i的下一个邻接点 else printf(“%c,g.vertexj.data); /访问邻接顶点j visitedj=1; /做访问标记 stack+top=p; /被访问过的顶点指针进栈 p=g.vertexj.firsta

42、rc; /沿着顶点j深度优先搜索 if (top-1) p=stacktop-; p=p-nextarc; (2)先建一个空的邻接矩阵，然后在邻接表上顺序地取每个单链表中的边结点，如果边结点不为空，那么将邻接矩阵中对应元素置1。void listtomat(AdjList g1,AdjMatrix *g2) for (i=0;ig1.vexnum;i+) for (j=0;jarcsij=0; /初始化邻接矩阵 g2-vexnum=g1.vennum; g2-arcnum=g1.arcnum; for (i=0;iarcsip-adjvex=1; /对应邻接矩阵第i行，第p-adjvex列的值

43、为1 p=p-nextarc; (3)在邻接矩阵上一行对应于一个顶点，而且每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为0时，那么对应顶点的出度为0。所以，从第一行开始，查找每行是否有非零元素，如没有，那么计数器加1。int sumzero1(Adjmatrix g) count=0; for (i=0;ig.vexnum;i+) flag=0; for (j=0;jg.vexnum;j+) if (gij!=0) flag=1; if (flag=0) count+; return count;邻接表中的边表恰好就是出边表。因此，其表头数组中firstarc域为空的个数

44、等于出度为0的元素个数。int sumzero2(AdjList g) count=0; for (i=0;ig.vexnum;i+) if (g.vertexi.firstarc=NULL) count+; return count;第7章 习题答案(1) 平均查找长度(2) 哈希查找(3)顺序 有序(4)越大 (5) (n + 1)(6)开放定址法 拉链法 (7)3(8)2(9)中序(10)建表123456789101表中只有一个关键字等于给定值k的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+n)=(n+1)/2；两者相同。无序表：顺序查找不成功时，平均查找

45、长度为n+1；有序表，平均查找长度为1/(n+1)*(1+2+(n+1)=(n+2)/2；两者不相同。表中只有m个关键字等于给定值k的记录，无序表：ASL=n+1；有序表：ASL=n+1/2+m；两者不相同。241802613386877303计算哈希地址：H(13)=(13 mod 7)+1=7 H(15)=(15mod 7)+1=2 H(22)=(22 mod 7)+1=2 H(8)=(8 mod 7)+1=2 H(34)=(34 mod 7)+1=7 H(19)=(19 mod 7)+1=6 H(21)=(21 mod 7)+1=1 H(29)=(29 mod 7)+1=20123456

46、78211522829191334012345678910212 8 1913293478012345621152219 8 2913344.1int SeqSearch(RecordType r, int n, KeyType k) i=0; rn.key=k; while (ri.key!=k) i+; if (irchild!=NULL) f=bt; bt=bt-rchild;return f-key; (3)int level(BSTree bt, KeyType k) d=0; if (bt=NULL) return 0; /空树深度为0 else d+; /根结点深度为1while

47、 (bt-data!=k) if (bt-datarchild; /右子树中查找 else bt=bt-rchild; /左子树中查找 d+; return d;(4)#define N 50int IsBSTree(BSTree bt)BSNode *stackN,*p; KeyType k; int isbst，top; isbst=1; /标志变量，首先假定bt是二叉排序树 top=-1; /置空栈 p=bt; /p从根出发while (isbst & (p!=NULL | top!=-1) while (p!=NULL) k=p-key; if (p-lchild-keyk | p-r

48、child-keyrchild!=NULL) stack+top=p-rchild; p=p-lchild; if (top!=-1)p=stacktop-; return isbst;(5)BSTree BSTDeleteAll(BSTree t, KeyType k)BSTree p; p=BSTSearch1(t,k); /查找关键字值不小于x的结点 while (p!=NULL) t=BSTDelete(t,p); /删除p所指示结点 p=BSTSearch1(t,k); 注：函数BSTSearch1，BSTDelete参阅教材,7.3.4。第8章 习题答案1、填空题1 i2 n-13

49、 n/24 O(n2)5 O(n)6 冒泡排序7 希尔排序8 直接插入排序9 插入排序 、 选择排序10 79，46，71，35，41，25，5611 25，41，35，46，56，79，7112 n/2 n-1 O(nlogn)13 正 反 反14 直接选择排序、希尔排序、堆排序、快速排序15 堆排序、快速排序、归并排序、归并排序、快速排序、堆排序2、判断题123456789103、简答题1略 参考教材写。2易于链表实现的是插入排序、归并排序和基数排序3初始状态为逆序时，直接插入、直接选择和冒泡排序的比拟次数分别为(n+2)(n-1)/2、n(n-1)/2、n(n-1)/2，移动次数分别为(

50、n+4)(n-1)/2，3(n-1)，3n(n-1)/2，因此文件逆序时采用直接选择排序较好。4在初始状态为逆序情况下，采用冒泡排序是稳定排序。5高度为h的堆，最多有2h-1个元素，最少有2h-1个元素。在高度为h的大顶堆中，关键字最小的元素存放在堆的第h层上的最后一个元素的位置w上，其中2h-1 w2h-1。6最好选用堆排序，比照其他效率较高的排序算法，大都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中局部元素的有序性，而堆排序那么每次输出一个极值元素，且比拟次数不超过，要好于如冒泡排序、选择排序等简单排序算法，由题意，只选择前10个大元素，所以可以利用大顶堆进行排序。7d是

51、8，分配和收集8趟，rd是26，队列个数26。8是大顶堆不是堆，可以调整为下面的小顶堆 1234567891012243065335648988670是大顶堆不是堆，可以把它调整为下面的小顶堆12345678910111205232035283829615676401004、算法设计题1分析与解答给head单链表设置一个附加表头结点，在排序过程中，单链表分成两个子表，即排序子表和未排序子表，首先将单链表的头结点和第一个结点看成是已经排序的子表，设置rear指针指向已排序子表的最后一个结点，初始时也就是单链表的第一个结点。设置h指针指向未排序子表的第一个结点，初始时也就是单链表的第二个结点，每次取出未排序子表的第一个结点，将其插入到前面已排序子表的适宜位置上。设置q指针从已排序子表的第一个结点出发，顺序查找适宜位置；并设置指针p用来跟踪q的直接前驱，以便插入操作。typedef struct node int data; struct node *next;ListNode;typedef ListNode *LinkList;Instersort (LinkList head) ListNode *p,*q,*h,*rear; rear=headnext;/*rear指向已排序子表的最后一个结点，初始时为单链表的第一个结点*/ h=rearne