數(shù)據(jù)結(jié)構(gòu)與實(shí)訓(xùn)張紅霞 白桂梅 主編 習(xí)題答案

1、第1章 習(xí)題答案1. 填空題1在計(jì)算機(jī)中的存儲映像是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)或存儲表示 數(shù)據(jù)元素的表示 元素之間關(guān)系的表示 數(shù)據(jù)元素。2已經(jīng)實(shí)現(xiàn) 是一個(gè)概念 別離 別離3時(shí)、空效率 指人對算法閱讀理解的難易程度 對于非法的輸入數(shù)據(jù)，算法能給出相應(yīng)的響應(yīng)，而不是產(chǎn)生不可預(yù)料的后果。4軟硬件環(huán)境 問題規(guī)模的5最壞6On4 On2 7時(shí)間復(fù)雜度8n On22. 判斷題123456789103. 簡答題1略見教材第3頁的1.2數(shù)據(jù)結(jié)構(gòu)的根本概念2an-1，On b n-1 , Onc11* n+1, Onn為初始值100d , O en , On第2章 習(xí)題及答案1、填空題1address+m*i2順

2、序 順序 順序 鏈?zhǔn)酱鎯?鏈?zhǔn)酱鎯?亦相鄰 不一定4n-i+15 0ila的長度 -1jlb的長度-1 0klc的長度-16 插入的位置，節(jié)點(diǎn)數(shù)n順序表長度n7其前驅(qū) O(n) O18其前驅(qū) 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)單向循環(huán)鏈表雙向循環(huán)鏈表存儲密度高低查找后繼的時(shí)間復(fù)雜度O(1)O(1)查找前驅(qū)的時(shí)間復(fù)雜度O(n)O(1)2在帶頭結(jié)點(diǎn)的單鏈表上，查找指針p所指結(jié)點(diǎn)的前驅(qū)。3交換指針p與指針q所指結(jié)點(diǎn)的值。4算法設(shè)計(jì)題(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個(gè)元素開始的k個(gè)元素*/ if (il.listlength-1| k0) printf(“Error);

4、return;if (i+k=l.listlength) /*表中從i個(gè)元素起到最后一個(gè)元素有k個(gè)元素*/ for ( j=i+k; jl.listlength; j+) l.elemj-k=l.elemj; l.listlengt=l.listlength-k; else /*表中從i個(gè)元素起直到最后一個(gè)元素缺乏k個(gè)元素*/ l.listlength=i;(3)void insert(LinkList h, ElementType x)/*將x插入到遞增鏈表h中，插入后的鏈表有序性不變*/ if (hnext=Null) /*空表時(shí)*/ 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)/*在不帶頭結(jié)點(diǎn)且長度大于1的單向循環(huán)鏈表中，p指向某結(jié)點(diǎn)，刪除p的前驅(qū)結(jié)點(diǎn)*/ ppp=

6、pnext;while (pppnextnext != p)ppp =pppnext;/*刪除p的前驅(qū)結(jié)點(diǎn)*/pp=pppnext;pppnext=ppnext;free(pp);(5) void delete (LinkList h)/*h為帶頭結(jié)點(diǎn)的，非降序排列的單鏈表的頭指針，刪除表中值相同的結(jié)點(diǎn)，使之只保存一個(gè)*/ 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)/*刪除帶頭結(jié)點(diǎn)的單鏈表h指向頭結(jié)點(diǎn)中值為x的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)*/ 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的帶頭結(jié)點(diǎn)的單鏈表的頭指針，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的帶頭結(jié)點(diǎn)的遞增有序的單鏈表的頭指針，C=AB由lc鏈表返回*/ lc=(LinkList) malloc (sizeof(LinkNode); lcnext=null;tail=lc; /*tail指向lc鏈的尾結(jié)點(diǎn)*/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對應(yīng)的順序遞增表為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)/*遞歸計(jì)算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,對應(yīng)的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無下劃線的序列可以通過相應(yīng)的入、出棧得到?？梢酝ㄟ^入、出棧得到的輸出序列中的每一個(gè)數(shù)，在它后面的比它小的數(shù)應(yīng)是降序排列的。(6)void AddQueue(Queue q, ElementType e) /*入隊(duì)*/ = maxsige) printf (“n overflow); return;q.elem(q.front+q.count) % MaxSize=e;q.count+; ElementType D

15、eleteQueue(Queue q)/*出隊(duì)*/ 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數(shù)組中，該序列合法返回1，否那么返回0*/ count=0;for (i=0; il.listlength; i+) if (l.elemi=I count+; else count-; if (count0) return(0); /*棧空時(shí)出棧*/ if (

16、count=0) return(1);else return(0); /*棧不空沒有回到初始狀態(tài)*/ 8typedef struct Qnode ElementType data; Struct Qnode *next; QueueNode;typedef QueueNode *LinkQueue;void AddQueue(LinkQueue rear, ElementType e)/*帶頭結(jié)點(diǎn)的循環(huán)鏈表隊(duì)列，只有指向尾結(jié)點(diǎn)的指針rear，對其實(shí)現(xiàn)入隊(duì)操作*/ p=(LinkQueue) malloc (sizeof(QueueNode);pdata=e;pnext=rearnext; re

17、arnext=p;rear=p;Elementype DeleteQueue(LinkQueue rear)/*帶頭結(jié)點(diǎn)的循環(huán)鏈表隊(duì)列，只有指向尾結(jié)點(diǎn)的指針rear，對其實(shí)現(xiàn)出隊(duì)操作*/ 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實(shí)現(xiàn)隊(duì)列q的入隊(duì)*/ Push (s1,e);ElementT

18、ype DeleteQueue(CirQueue q)/*借助于堆棧s1、s2實(shí)現(xiàn)隊(duì)列q的出隊(duì)*/ 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章 習(xí)題及答案1. 填空題1字符20 空格的個(gè)數(shù)314 “bc cad cabcadfabc “abc 8 1(true) “bc cad cbcadf “abcbc cad cabcadf “bcad cabcadf4

19、1975三維數(shù)組arr623的每個(gè)元素的長度為4個(gè)字節(jié)，如果數(shù)組以行優(yōu)先的順序存儲，且第1個(gè)元素的地址是4000，那么元素arr502的地址是4000+4*5*2*3+0*3*2=41282. 判斷題123456789103. (1) v=j(2) 符號表s30t53u78堆01234567891011abcxabcyzxabcyzfree3最壞情況下的時(shí)間復(fù)雜度為Om*n，其中m為串s的長度，n為串t的長度4三維數(shù)組arr623的每個(gè)元素的長度為4個(gè)字節(jié)，該數(shù)組要占6*2*3*4=144個(gè)字節(jié)，假設(shè)數(shù)組以列優(yōu)先的順序存儲，設(shè)第一個(gè)元素的首地址是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) 行優(yōu)先：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列優(yōu)先：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) 稀疏矩陣壓縮存儲后會失去隨機(jī)存取的功能，因?yàn)橄∈杈仃嚥荒芨鶕?jù)元素在矩陣中的位置求得在其在三元組順序表中的位置，而特殊矩陣那么可以。(8)當(dāng)3tm*n 即 時(shí)，三元組的表示才有意義。(9) i=j 或 i+j=n+1 4、算法設(shè)計(jì)題1void Ass

23、ign(BlockLink *s, char t)/*將存放在字符數(shù)組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)/* 統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。*/ fori0；i= a& ch = A& ch = Z /* 大寫字母

24、*/ i=ch-65+10;numi+； 3 int JudgEqual(ing a,int m,int n) /*判斷二維數(shù)組中所有元素是否互不相同，如是，返回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); /*元素互不相同*/ 二維數(shù)組中的每一個(gè)元素同其它元素都比擬一

25、次，數(shù)組中共m*n個(gè)元素，第1個(gè)元素同其它m*n-1個(gè)元素比擬，第2個(gè)元素同其它m*n-2 個(gè)元素比擬，第m*n-1個(gè)元素同最后一個(gè)元素(m*n)比擬一次,所以在元素互不相等時(shí)總的比擬次數(shù)為 (m*n-1)+(m*n-2)+2+1=m*n(m*n-1)/2。在有相同元素時(shí),可能第一次比擬就相同,也可能最后一次比擬時(shí)相同,設(shè)在每個(gè)位置上均可能相同,這時(shí)的平均比擬次數(shù)約為m*n(m*n-1)/4，總的時(shí)間復(fù)雜度是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中的鞍點(diǎn)，鞍點(diǎ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+)if(Aij=min) /*判斷這個(gè)(些)最小值是否鞍點(diǎn)*/for(flag=1, k=0; km; k+) if(minx， 這情況下向j 小的方向繼續(xù)查找；二是

27、Ai,jx，下步應(yīng)向i大的方向查找；三是Ai,j=x，查找成功。否那么，假設(shè)下標(biāo)已超出范圍，那么查找失敗。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的標(biāo)志*/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的路線從右上角開始，向下當(dāng)xbi,j或向左當(dāng)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+) /*對矩陣的每一行進(jìn)行加法*/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的非葉子結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)的編號是(i-1)*k+j+1。 編號為i的結(jié)點(diǎn)有右兄弟的條件是(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 轉(zhuǎn)換后的二叉樹：AGBDCMLENFHIJKOPQR 題中圖5-35改為5-36 雙親數(shù)組

32、表示： 易于求祖先dataparent0A-11B02C03D24E25F2孩子鏈表表示法：易于求子孫120A1B2C3D4E5F345孩子兄弟表示法：易于求子孫ABCrootDEF8哈夫曼樹為：72423026161511876542 帶權(quán)路徑長度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; /設(shè)棧的容量足夠大 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的結(jié)點(diǎn)，

35、找到返回其所在層數(shù)否那么返回0 BinTree p,f,stack150; /設(shè)棧的容量足夠大 int h,stack250 /stack2用來保存p結(jié)點(diǎn)所在的層數(shù) int top=-1; /置空棧。stack1和stack2可共用一個(gè)棧頂指針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的先序后繼假設(shè)*p有左孩子即ltag=0，那么左孩子為后繼；假設(shè)*p無左孩子即ltag=1，那么右孩子為后繼ThBinTree PreOrderSucc(ThBinTree root) if (root-ltag=0)return root-lchild; elsereturn root-rchild; 在后序線索樹中查找*p的后序前驅(qū)假設(shè)*p有右孩子即rtag=0，那么右孩子為前驅(qū)；假設(shè)*p無右孩子即rtag=1，那么左孩子為前驅(qū)。ThBinTree PreOrderPre(ThBinTre

37、e root) if (root-rtag=0)return root-rchild; elsereturn root-lchild;第6章 習(xí)題答案 (1) e=(2) n(n 1)(3)入度(4)先序 層次 (5) n-1(6)O(n2) O(elog2e) kruskal (7)4(8)邊的數(shù)目(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邊數(shù)為鄰接矩陣中非零或非元素?cái)?shù)目除以2。假設(shè)鄰接矩陣A中的元素Aij的值為非零，那么頂點(diǎn)Vi和Vj之間有邊相連對于任意一個(gè)頂點(diǎn)i，它的度為鄰接矩陣第i行或第i列的非零或非元素?cái)?shù)目。4題中無向圖改為有向圖。邊弧數(shù)為鄰接表中所有單鏈表的邊結(jié)點(diǎn)數(shù)目。假設(shè)第i個(gè)單鏈表中存在一個(gè)邊結(jié)點(diǎn)，其adjvex域的值為j，那么頂點(diǎn)Vi和Vj之間有邊弧相連對于任意一個(gè)頂點(diǎn)i，它的入度為所有單鏈表中adjvex域的

39、值為i的邊結(jié)點(diǎn)數(shù)目，它的出度為第i個(gè)單鏈表中邊結(jié)點(diǎn)數(shù)目。5鄰接表：012345112662513 0340567 74 把題中V1改V0。 深度優(yōu)先搜索：V0，V1，V3，V4，V7，V2，V5，V6 廣度優(yōu)先搜索：V0，V1，V2，V3，V4，V5，V6，V7612245DACBFE1224ACBFE122ACBE12ACB1ACA 12245DACBFE1224DACBFE122DACBFE12DACBFE1DACBFE 權(quán)值：1+2+2+4+5=147題中圖的頂點(diǎn)標(biāo)記改為數(shù)字，如下列圖，且求從1到其它頂點(diǎn)的最短路徑。10001022041510300015004005圖236142201

40、020154153010104 循環(huán)集合Sv距離數(shù)組dist路徑數(shù)組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采用鄰接表作為存儲結(jié)構(gòu)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) /頂點(diǎn)j被訪問過 p=p-nextarc; /繼續(xù)找頂點(diǎn)i的下一個(gè)鄰接點(diǎn) else printf(“%c,g.vertexj.data); /訪問鄰接頂點(diǎn)j visitedj=1; /做訪問標(biāo)記 stack+top=p; /被訪問過的頂點(diǎn)指針進(jìn)棧 p=g.vertexj.firsta

42、rc; /沿著頂點(diǎn)j深度優(yōu)先搜索 if (top-1) p=stacktop-; p=p-nextarc; (2)先建一個(gè)空的鄰接矩陣，然后在鄰接表上順序地取每個(gè)單鏈表中的邊結(jié)點(diǎn)，如果邊結(jié)點(diǎn)不為空，那么將鄰接矩陣中對應(yīng)元素置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; /對應(yīng)鄰接矩陣第i行，第p-adjvex列的值

43、為1 p=p-nextarc; (3)在鄰接矩陣上一行對應(yīng)于一個(gè)頂點(diǎn)，而且每行的非零元素的個(gè)數(shù)等于對應(yīng)頂點(diǎn)的出度。因此，當(dāng)某行非零元素的個(gè)數(shù)為0時(shí)，那么對應(yīng)頂點(diǎn)的出度為0。所以，從第一行開始，查找每行是否有非零元素，如沒有，那么計(jì)數(shù)器加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;鄰接表中的邊表恰好就是出邊表。因此，其表頭數(shù)組中firstarc域?yàn)榭盏膫€(gè)數(shù)

44、等于出度為0的元素個(gè)數(shù)。int sumzero2(AdjList g) count=0; for (i=0;ig.vexnum;i+) if (g.vertexi.firstarc=NULL) count+; return count;第7章 習(xí)題答案(1) 平均查找長度(2) 哈希查找(3)順序 有序(4)越大 (5) (n + 1)(6)開放定址法 拉鏈法 (7)3(8)2(9)中序(10)建表123456789101表中只有一個(gè)關(guān)鍵字等于給定值k的記錄，無序表、有序表：順序查找成功時(shí)，平均查找長度均為1/(n)*(1+2+n)=(n+1)/2；兩者相同。無序表：順序查找不成功時(shí)，平均查找

45、長度為n+1；有序表，平均查找長度為1/(n+1)*(1+2+(n+1)=(n+2)/2；兩者不相同。表中只有m個(gè)關(guān)鍵字等于給定值k的記錄，無序表：ASL=n+1；有序表：ASL=n+1/2+m；兩者不相同。241802613386877303計(jì)算哈希地址：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+; /根結(jié)點(diǎn)深度為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; /標(biāo)志變量，首先假定bt是二叉排序樹 top=-1; /置空棧 p=bt; /p從根出發(fā)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); /查找關(guān)鍵字值不小于x的結(jié)點(diǎn) while (p!=NULL) t=BSTDelete(t,p); /刪除p所指示結(jié)點(diǎn) p=BSTSearch1(t,k); 注：函數(shù)BSTSearch1，BSTDelete參閱教材,7.3.4。第8章 習(xí)題答案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易于鏈表實(shí)現(xiàn)的是插入排序、歸并排序和基數(shù)排序3初始狀態(tài)為逆序時(shí)，直接插入、直接選擇和冒泡排序的比擬次數(shù)分別為(n+2)(n-1)/2、n(n-1)/2、n(n-1)/2，移動次數(shù)分別為(

50、n+4)(n-1)/2，3(n-1)，3n(n-1)/2，因此文件逆序時(shí)采用直接選擇排序較好。4在初始狀態(tài)為逆序情況下，采用冒泡排序是穩(wěn)定排序。5高度為h的堆，最多有2h-1個(gè)元素，最少有2h-1個(gè)元素。在高度為h的大頂堆中，關(guān)鍵字最小的元素存放在堆的第h層上的最后一個(gè)元素的位置w上，其中2h-1 w2h-1。6最好選用堆排序，比照其他效率較高的排序算法，大都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，而無法知道排序過程中局部元素的有序性，而堆排序那么每次輸出一個(gè)極值元素，且比擬次數(shù)不超過，要好于如冒泡排序、選擇排序等簡單排序算法，由題意，只選擇前10個(gè)大元素，所以可以利用大頂堆進(jìn)行排序。7d是

51、8，分配和收集8趟，rd是26，隊(duì)列個(gè)數(shù)26。8是大頂堆不是堆，可以調(diào)整為下面的小頂堆 1234567891012243065335648988670是大頂堆不是堆，可以把它調(diào)整為下面的小頂堆12345678910111205232035283829615676401004、算法設(shè)計(jì)題1分析與解答給head單鏈表設(shè)置一個(gè)附加表頭結(jié)點(diǎn)，在排序過程中，單鏈表分成兩個(gè)子表，即排序子表和未排序子表，首先將單鏈表的頭結(jié)點(diǎn)和第一個(gè)結(jié)點(diǎn)看成是已經(jīng)排序的子表，設(shè)置rear指針指向已排序子表的最后一個(gè)結(jié)點(diǎn)，初始時(shí)也就是單鏈表的第一個(gè)結(jié)點(diǎn)。設(shè)置h指針指向未排序子表的第一個(gè)結(jié)點(diǎn)，初始時(shí)也就是單鏈表的第二個(gè)結(jié)點(diǎn)，每次取出未排序子表的第一個(gè)結(jié)點(diǎn)，將其插入到前面已排序子表的適宜位置上。設(shè)置q指針從已排序子表的第一個(gè)結(jié)點(diǎn)出發(fā)，順序查找適宜位置；并設(shè)置指針p用來跟蹤q的直接前驅(qū)，以便插入操作。typedef struct node int data; struct node *next;ListNode;typedef ListNode *LinkList;Instersort (LinkList head) ListNode *p,*q,*h,*rear; rear=headnext;/*rear指向已排序子表的最后一個(gè)結(jié)點(diǎn)，初始時(shí)為單鏈表的第一個(gè)結(jié)點(diǎn)*/ h=rearne