高等學校——數據結構習題答案-資料下載頁

　　

【正文】 read2(ThrNode *t) /* 中序遍歷線索化以t為根的二叉樹*/ { if( t ){ inthread2(tlchild)。 /*左子樹線索化*/ if(pre!=NULL){ if( prerchild==NULL){ /* 建立pre結點的后繼線索*/ preRtag=1。 prerchild=t。 } } pre=t。 /*pre指向t的前驅*/ inthread2(trchild)。 /*右子樹線索化*/ } }/* inthread2 */ 題圖 42FBDHKGJICAE11．畫出與題圖42所示二叉樹對應的森林。解：FBDHKGJICAE上機實習題 一、實習目的1．掌握樹的結構的非線性特點、遞歸性特點和動態數據結構等特點。 2．掌握二叉樹的存儲結構、各種遍歷算法以及基于遍歷算法的其他操作的實現。二、實習內容 1．編寫一個C語言程序，對二叉樹實現以下操作：（1）按先根、中根和后根次序遍歷二叉樹；（2）按二叉樹的層次輸出各結點（每一行輸出一層）；（3）利用遍歷算法，將二叉樹中所有結點的左右子樹交換。2．在一段文字中10個常用漢字及出現的頻度如下： 的 地 得 于 個 和 在 再 是 有 26 6 4 15 7 6 8 5 18 5 試為這些常用漢字設計哈夫曼編碼表。第五章 12341 V1入度2,出度1，v2入度1，出度2,v3入度1，出度0，v4入度1，出度2鄰接陣G0001101000001100鄰接表v1v4v2v1v3v4v1v2逆鄰接表v1v2v4v2v4v3v2v4v12廣度優先序列是：v2,v1,v3,v6,v4,v5深度優先序列是:v2,v1,v3,v4,v5,v63深度優先序列是：v1,v3,v4,v2,v5（根據存儲順序，如果根據序號大小有不同結果）4給出歸并順序： 普里姆：v1,v3v4v5v2克魯斯卡爾：v4,v5邊，v4,v2邊，v3,v4邊，v3,v1邊（有權值相同的邊，不唯一）５最短路徑(v1v3 )5 (v1v6) 15 (v1v4) 19 (v1v2) 20 (v1v5) 25 6 AOV網絡v1,v4,(或者v4,v1)可換。v2位置不可變，v5,v3(或者v3,v5)，v6不可變 鄰接表中: v1,v4,v2,v3,v5,v6第六章1 算法說明：本程序使用兩個結點鏈交換的方法，比較復雜，要簡化的同學可以直接交換內容。代碼可以省去三分之二。/*insert sort via LinkList*/struct Node{ int data。 struct Node *next。}。struct Node * locateCount(struct Node *h,int k){ int i=0。 struct Node *h1=h。 for(i=1。i=k。i++) h1=h1next。 return h1。} 。 show(struct Node *head){ struct Node *p。 p=headnext。 while(p!=0){ printf( : %3d : ,pdata)。 p=pnext。 } printf(\n)。 return。}sort(struct Node *head){ struct Node *h,*searchGoalPtr,*p,*q,*qStart,*preGoal。 struct Node *temp,*pt1,*pt2,*goalNext。 int count=2。 h=head。 preGoal=headnext。 searchGoalPtr=headnextnext。 qStart=head。 while(searchGoalPtr!=0){/*go */ hdata=searchGoalPtrdata。 q=qStart。 while(qnextdatahdata){ q=qnext。 } pt1=qnext。 qnext=searchGoalPtr。 pt2=searchGoalPtrnext。 searchGoalPtrnext=pt1。 preGoalnext=pt2。 preGoal=locateCount(head,count)。 count++。 searchGoalPtr=locateCount(head,count)。 show(head)。 }/*while*/}main(){ struct Node *h,*p1,tail。 int var=0。 h= (struct Node*) malloc(sizeof(struct Node))。 hdata=0。 hnext=0。 /*construct a linked list*/ while(1){ printf(Please input a Node,enter 1 end:)。 scanf(%d,amp。var)。 if (var==1) break。 p1=(struct Node*) malloc(sizeof(struct Node))。 p1data=var。 p1next=hnext。 hnext=p1。 } show(h)。 sort(h)。 show(h)。 /*yes constructed!*/ free(h)。 return 。}2 排序過程56 67 59 41 98 47 26 38 75 52 16 原始數據16 26 38 41 52 47 67 59 75 98 56 d=516 26 38 41 52 47 67 56 75 98 59 d=316 26 38 41 47 52 56 59 67 75 98 d=13 不需要，因為排序已經完成4 冒泡過程14 15 28 5 10 30 a14 15 5 10 28 30 b14 5 10 15 28 30 c10 14 15 28 30 d快速過程14 15 30 28 5 1010 15 30 28 5 1410 14 30 28 5 1510 5 30 28 14 1510 5 14 28 30 15 分左右再內部排序得10 14 15 28 305 直接插入5 冒泡5 快速146 提示：。7 /*insert sort via LinkList*/struct Node{ int data。 struct Node *next。}。 show(struct Node *head){ struct Node *p。 p=headnext。 while(p!=0){ printf( : %3d : ,pdata)。 p=pnext。 } printf(\n)。 return。}sort(struct Node *head){ struct Node *p,*ptr1,*ptr2。 int min。 int temp。 ptr1=headnext。 while(ptr1){ ptr2=ptr1next。 min=ptr1data。 while(ptr2){ if (ptr2datamin) { temp=ptr1data。 ptr1data=ptr2data。 ptr2data=temp。 }/*if*/ ptr2=ptr2next。 }/*ptr2*/ ptr1=ptr1next。 } show(head)。 }/*while*/main(){ struct Node *h,*p1,tail。 int var=0。 h= (struct Node*) malloc(sizeof(struct Node))。 hdata=0。 hnext=0。 /*construct a linked list*/ while(1){ printf(Please input a Node,enter 1 end:)。 scanf(%d,amp。var)。 if (var==1) break。 p1=(struct Node*) malloc(sizeof(struct Node))。 p1data=var。 p1next=hnext。 hnext=p1。 } show(h)。 sort(h)。 show(h)。 /*yes constructed!*/ free(h)。 return 。}8 4符合堆的特性。9 19 34 26 97 56 75是一個堆先19出堆，調整75上來，得 1975 34 26 97 56 ,調整后26 34 75 97 56 ，得26調整56上來得56 34 75 97 調整得34 56 75 97 出 34調整97上來得97 56 75調整得56 97 75 出56最后出75 和9710 56 67 59 41 98 47 26 38 75 52 16 L=156 67 41 59 47 98 26 38 52 75 16 L=241 56 59 67 26 38 47 98 16 52 75 L=416 26 38 41 47 52 56 59 67 75 98 結果原因是r 是一次歸并結果，放在r2里臨時存放，最后放回r以便下次再處理。第七章1．有一個有序文件，其中各記錄的關鍵字為：{3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87}，當用折半查找算法查找關鍵字為4,20,65時，其比較次數分別為多少?解：K=46571110128213151416491317K=20K=65判定樹該有序文件長度為17，根據折半查找算法畫出判定樹如下圖所示。從圖中可得出：當關鍵字為4,20,65時，其比較次數分別為3，4，3。２、 若對大小均為n的有序順序表和無序順序表分別進行順序查找，試就下列三種情況分別討論兩者在等查找概率時的平均查找長度是否相同?(1)查找失敗；(2)查找成功；(3)查找成功，表中有多個關鍵字等于給定值的記錄，一次查找要求找出所有記錄。解：(1)平均查找長度不相同。有序順序表小于等于無序順序表。(2)平均查找長度相同。(3) 平均查找長度不相同，有序順序表小于等于無序順序表。３、 試按下列次序將各關鍵字插入到二叉平衡樹中，畫出重新平衡的情況。關鍵字依次為：111解： 生成并調整成平衡二叉排序樹的過程如下圖(a)～(j)所示。89128RR89(b)不調整1289(c)調整(a)初始912821LL912281(e)調整91282(d)不調整9122815LR9128251LL9825112(f)調整39825112(g)不調整39825112(h)不調整63982511267RR1985621273(i)調整9111856212731211985621173111985621273RRRL(j)調整４、已知長度為12的表：（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）。(1) 試按表中元素的順序，依次插入一棵初始為空的