《數(shù)據(jù)結(jié)構(gòu)》答案

1、算法設(shè)計(jì)題2-4的第1題經(jīng)過(guò)調(diào)試發(fā)現(xiàn)原來(lái)的那個(gè)是錯(cuò)的，下面這個(gè)調(diào)試成功。算法思想是：將原鏈表中的頭結(jié)點(diǎn)和首元結(jié)點(diǎn)斷開(kāi)，并使頭結(jié)點(diǎn)的指針域?yàn)榭?，?gòu)成一個(gè)新的空表。然后將原鏈表中的結(jié)點(diǎn)依次插入這個(gè)新表的頭部，令每次插入的結(jié)點(diǎn)都成為新鏈表的首元結(jié)點(diǎn)。 int Contrary( LinkList &L ) if( !L ) return 0;Node*p=L->next,*q;/q可以在while的花括號(hào)內(nèi)定義，但每次循環(huán)都要新建變量，浪費(fèi)時(shí)間 L->next=NULL; while(p) q=p->next; p->next=L->next; L->ne

2、xt=p; p=q; return 1; 閱讀理解題3-3的第4題的代碼中第二個(gè) for循環(huán)應(yīng)該為： for ( i=0;i<5;i+) Insertset(b ,r1i); 運(yùn)算操作題4-1的第3題中的兩個(gè)指針front和rear所指的位置和書(shū)本以及老師的PPT不一樣，但都是可行的，不過(guò)我覺(jué)得書(shū)上和PPT的好一些：front指向隊(duì)首元素，rear指向隊(duì)尾元素的下一位置。 (其實(shí)front和rear都是整型值，是數(shù)組元素的下標(biāo)，不是真正的指針。)運(yùn)算操作題6-1-1 MEC7H'_L'-Z I29 ) , 78 ( 62 ( ,70 )刪除12刪除492S1634口1：T

3、 - /30i30廣義表：46( 52 (12,37 ( 運(yùn)算操作題6-1-2 刪除72 (1 ZJ Z <<>) 1 * 刪除28 30運(yùn)算操作題6-1-33838 6438 64 5215 38526415 3852647315 384064735215 38406473524815 3840557352486415 264038735248645512 1540382652486455 73運(yùn)算操作題6-1-4刪除1215 26 40 38 64 52 48刪除1526 38 40 48 64 52刪除2638 48 40 52 64刪除3840 48 64 52運(yùn)算操

4、作題6-1-5廣義表：(2,3 ) , 6 ) , 10 ) , ( (7,8 ) , 14 )WPL = ( 10 + 14 ) X2 + ( 6 + 7 + 8 ) X3 + ( 2 + 3 ) X4運(yùn)算操作題6-1-6字符編碼碼長(zhǎng)a00004b012c0013d00014e11電文總長(zhǎng)=4 X4 + 7 X2 + 5 X3 + 2 X4 + 9 X 1運(yùn)算操作題6-1-7運(yùn)算操作題6-1-9ASL =( 1 + 2 X2 + 2 X3 + 3 X4 + 2 X 5 ) / 10運(yùn)算操作題7-1-1全都是離散數(shù)學(xué)的內(nèi)容運(yùn)算操作題7-1-3依照矩陣和鄰接表所產(chǎn)生的兩種遍歷序列各自相等。a圖：

5、深度優(yōu)先遍歷：0 1 2 8 3 4 5 6 7 9廣度優(yōu)先遍歷：0 1 4 2 7 3 8 6 9 5b圖：深度優(yōu)先遍歷：0 1 4 5 8 7 2 3 6廣度優(yōu)先遍歷：0 1 3 4 2 6 7 5 8運(yùn)算操作題7-1-4深度優(yōu)先遍歷：0 3 6 7 4 1 2 5 8廣度優(yōu)先遍歷：0 3 4 6 7 1 2 8 5運(yùn)算操作題8-1-1普里姆算法的邊的序列：( 0 ,1)，(1 ,6 )，( 6 ,2 )，( 2 ,3 )，(3 ,4)，( 4 ,5)克魯斯卡算法的邊的序列：( 1 ,6)，(2 ,3 )，( 0 ,1 )，( 6 ,2 )，(3 ,4)，( 4 ,5)運(yùn)算操作題8-1-2

6、不畫(huà)圖了，只寫(xiě)出邊的序列。以下各點(diǎn)的最短路徑是按順序生成的：0-3: < 0,3>0-5: < 0,5>0-1:<0,3>,<3,1>0>6:<0,5>,<5,6>0-4:<0,5>,<5,6>,<6,4>0-2:<0,5>,<5,6>,<6,4>,< 4,2>0-7:<0,5>,<5,6>,<6,4>,< 4,2> , < 2,7>運(yùn)算操作題8-1-3( 1 ) ( 0 ,

7、3 )，( 4 ,7 )， ( 3 ,5 )， ( 5 ,6 )， ( 1 ,2 )， ( 0 ,1 )， ( 6 ,7 )(2 ) 0 -3: ( 0 ,3 ) 0-5: ( 0 ,3 ) 0-1: ( 0 ,1 ) 0-6: ( 0 ,3 ) 0-2: ( 0 ,1 ) 0-7: ( 0 ,3 ) 0-4: ( 0 ,3 )( 3 ,5 )( 3 ,6 )( 1 ,2 )( 3 ,6 )， ( 6 ,7 )運(yùn)算操作題8-1-4弗洛伊德算法老師沒(méi)有講，作業(yè)也沒(méi)有做過(guò)，不用考( 3 ,6 )， ( 6 ,7 )， ( 7 ,4 )本來(lái)在很多情況下拓?fù)湫蛄胁⒉晃ㄒ唬旅鎯深}它要求是唯一的，所以

8、拓?fù)湫蛄信c頂點(diǎn)入 棧出棧的順序有關(guān)。運(yùn)算操作題8-1-51 4 0 2 3 5 7 6 8 9運(yùn)算操作題8-1-61 0 2 4 3 5 7 6 8 9 10運(yùn)算操作題8-1-7( 1 ) 設(shè) ve( i ) 和 vl( i ) 分別表示事件i 的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間。ve( 0 ) = 0ve( 1 ) = ve( 0 ) + a1 = 5ve( 2 ) = ve( 0 ) + a2 = 6ve( 3 ) = Max ve( 1 ) + a3 , ve(2) + a4 = Max 8,12 = 12ve( 4 ) = Max ve( 2 ) + a5 , ve(3) + a6 = Ma

9、x 9,15 = 15ve( 5 ) = ve( 3 ) + a7 = 16ve( 6 ) = Max ve( 3 ) + a8 , ve( 4 ) + a9 = Max 16 , 16 = 16ve( 7 ) = ve( 4 ) + a10 = 17ve( 8 ) = Max ve( 6 ) + a12 , ve( 7 ) + a13 = Max 21 , 19 = 21vl( 9 ) = 23vl( 8 ) = vl( 9 )vl( 7 ) = vl( 8 )vl( 6 ) = vl( 8 )vl( 5 ) = vl( 9 )vl( 4 ) = Min vl( 6 )ve( 9 ) = M

10、ax ve( 5 ) + a11 , ve( 8 ) + a14 = Max 20 , 23 = 23a14 = 21a13 = 19a12 = 16a11 = 19-a9 , vl( 7 ) - a10 = Min 15 ,17 = 15vl( 3 ) = Min vl( 5 )- a7 , vl( 6)- a8, vl( 4 )- a3 = Min 15 ,12,12 =12vl( 2 ) = Min vl( 3 )- a4 , vl( 4 )- a5 = Min 6,12 = 6vl( 1 ) = vl( 3 )- a3 = 9vl( 0 ) = 0(2 ) 因?yàn)関e( 9 ) = 23

11、,所以完成整個(gè)工程至少的時(shí)間為23。(3 )設(shè)3( i )和l( i )分別為活動(dòng)i的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間，則 l( i ) e( i ) 為每個(gè)活動(dòng)的開(kāi)始時(shí)間余量?；顒?dòng) i由弧< j,k >表示。根據(jù)(1 )題所得的結(jié)果和關(guān)系 e( i ) =ve( j )、l( i ) = vl( k ) w<j,k> ,得出下表：活動(dòng)ell-e< 0,1 >ve( 0 )=0vl( 1 )a1=44< 0,2>ve( 0 )=0vl( 2 )a2=00< 1,3>ve(1)=5vl( 3 )a3=94< 2,3>ve( 2 )

12、=6vl( 3 )一 a4=60< 2,4>ve( 2 )=6vl( 4 )a5=126< 3,4>ve( 3 )=12vl( 4 )a6=120< 3,5>ve( 3 )=12vl( 5 )a7=153< 3,6>ve( 3 )=12vl( 6 )a8=120< 4,6>ve( 4 )=15vl( 6 )a9=150< 4,7>ve( 4 )=15vl( 7 )a10=172< 5,9>ve( 5 )=16vl( 9 )a11=193< 6,8>ve( 6 )=16vl( 8 )a12=160&l

13、t; 7,8>ve( 7 )=17vl( 8 )a13=192< 8,9>ve( 7 )=21vl( 9 )a14=210(4 ) e( i ) 等于l( i ) 的活動(dòng)(即開(kāi)始時(shí)間剩余量為0的活動(dòng))為關(guān)鍵活動(dòng)，所以圖中的關(guān)鍵活動(dòng)為：< 0,2> , < 2,3> , < 3,4> , < 3,6> , < 4,6> , < 6,8> , < 8,9> 。所以圖中的關(guān)鍵路徑有兩條： < 0,2> , < 2,3> , < 3,4> , < 4,6>

14、; , < 6,8> , < 8,9> < 0,2> , < 2,3> , < 3,6> , < 6,8> , < 8,9>它們的路徑長(zhǎng)度都為 23。所有關(guān)鍵活動(dòng)所構(gòu)成的圖為：(5 )關(guān)鍵活動(dòng)決定整個(gè)工程的持續(xù)時(shí)間。所以加速關(guān)鍵活動(dòng)< 0,2> , < 2,3> ,<3,4> ,< 3,6> , < 4,6> , < 6,8> , < 8,9>可以整個(gè)工程提前完成。運(yùn)算操作題9-1-1若進(jìn)行順序查找，將 n=30代入公式ASL

15、= (n + 1) / 2 得ASL = 15.5 。若進(jìn)行二分(折半)查找，將n=30代入公式ASL="%'" 一 T 得ASL = 4.1也可以通過(guò)二叉判定樹(shù)來(lái)確定ASL若進(jìn)行分塊查找，由于原表有序，所以可分兩種情況討論： 若用順序查找確定所在塊，則將s=6, n=30代入公式ASL = ( n/s + s )/2 + 1 中，得ASL = 6.5若用二分查找確定所在塊，則將s=6, n=30代入公式t 1得 ASL = 5.6運(yùn)算操作題9-1-2 和運(yùn)算操作題9-1-3 相同一次探測(cè)成功時(shí)，H(key) = key %13線性探測(cè)再散列白哈希函數(shù)為H =( H

16、( key ) + d i ) %m (d i =1, 2, 3,，m-1且1 w i wm-1)32%13 = 6 探測(cè)1次75%13 = 10探測(cè)1次29%13 = 3 探測(cè)1次63%13= 11 探測(cè)1次48%13= 9 探測(cè)1次94%13= 3 有沖突，再探測(cè) Hi= (3+1)%13 = 4 探測(cè)2次25%13= 12 探測(cè)1次46%13= 7 探測(cè)1次18%13= 5 探測(cè)1次70%13=5有沖突，再探測(cè) H1= (5+1)%13 = 6有沖突，再探測(cè) 士= (6+2)%13 = 8探測(cè)3次56%13=4 有沖突，再探測(cè) H產(chǎn)(4+1)%13 = 5有沖突，再探測(cè) 七二(5+2)%

17、13 = 7有沖突，再探測(cè) H3= (7+3)%13 = 10 有沖突，再探測(cè) H4= (10+4)%13 = 1 探測(cè)5次ASL =(1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 3 + 5)/11=1.63X3275296348942546187056H(X)61031193127554沖突后線性探查的次數(shù)124處理沖突后的實(shí)際地址4810 12 3 45 67 89 10 11 125629941832467048756325運(yùn)算操作題9-1-41 1對(duì)于線性探測(cè)再散列，ASL 上 L-=n , “ =n/m, n為記錄數(shù)，m為哈希表長(zhǎng)(散列表長(zhǎng)）。聯(lián)立以上兩式

18、得:.=-父)=4002C45L-1)運(yùn)算操作題10-1-1紅色數(shù)字為已經(jīng)排好序的部分第1趟:4674 1653 14 26 40 38 86 65 27 34第2趟:1646 7453 14 26 40 38 86 65 27 34第3趟:1646 537414 26 40 38 86 65 27 34第4趟:141646537426 40 38 86 65 27 34第5趟:14162646537440 38 86 65 27 34第6趟:1416264046537438 86 65 27 34第7趟:141626384046537486 65 27 34第8趟:1416263840465

19、37486 65 27 34第9趟：第10趟:1414第11趟:14162638404653657486 27 3416 26 2716 26 2738344046536574 86 3438 40465365 74 86運(yùn)算操作題10-1-2紅色數(shù)字為已經(jīng)排好序的部分,藍(lán)色數(shù)字為每趟結(jié)束前被交換的數(shù)據(jù)（和最后一個(gè)紅色數(shù)字交換）第1趟:147416 53462640 38 86 65 27 34第2趟:14167453 46 264038 86 65 27 34第3趟:14162653 467440 38 86 65 27 34第4趟:1416262746 74 40 38 86 655334

20、第5趟:第6趟:14141616262627273434第7趟:1416262734第8趟:1416262734第9趟:1416262734第10趟:14162627第11趟:1416262774 40 38 86 65 533838383846343438384040404074 86 65 53 4674 86 65 53 4646 86 65 534653 658640404646535365658674747474 86運(yùn)算操作題10-1-3排序時(shí)的調(diào)堆是從完全二叉樹(shù)頂部向排序前的建堆是從完全二叉樹(shù)的底部往上篩選的過(guò)程,下篩選的過(guò)程。因?yàn)轭}目要求按關(guān)鍵字升序排列，所以建大根堆比較方便。 初始堆的建堆過(guò)程：467416531434403886652726467416536534403886142726467416866534403853142726467440866534163853142726468640746534163853142726867440536534163846142726初始堆所對(duì)應(yīng)的完全二叉樹(shù):34/1/13H Td I -L 27 N6堆排序