數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題(附答案)

1、一、 算法設(shè)計題（每題15分，共60分）答題要求：用自然語言說明所采用算法的思想；給出每個算法所需的數(shù)據(jù)結(jié)構(gòu)定義，并做必要說明；寫出對應(yīng)的算法程序，并做必要的注釋。1、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域next。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保留一個。3、約瑟夫環(huán)問題（Josephus問題）是指編號為1、2、，n的n（n0）個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到所有的人全部

2、出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計一個算法，模擬此過程。4、編程實現(xiàn)單鏈表的就地逆置。23在數(shù)組 A1.n中有n個數(shù)據(jù)，試建立一個帶有頭結(jié)點的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個.5、設(shè)計一個盡可能的高效算法輸出單鏈表的倒數(shù)第K個元素。3、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分） （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通過對（1）的

3、分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。5、設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai-1時，將ai進棧；當(dāng)ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。設(shè)有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，.，Wn。問能否從這n件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,.，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在下

4、列算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)若S=0則Knaptrue否則若（S0且n1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個盡可能高效（時間、空間）的算法，將R中保存的序列循環(huán)左移p（0prchild=(2)_; (3)_=q;if(p-lchild) (4)_; if(p-rchild) (5)_; 25.設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個兒子的結(jié)點個數(shù)N2;只有非空左兒子的個數(shù)NL;只有非空右兒子的結(jié)點個數(shù)NR和葉子結(jié)點個數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typede

5、f struct nodeint data; struct node *lchild,*rchild;node;int N2,NL,NR,N0;void count(node *t) if (t-lchild!=NULL) if (1)_ N2+; else NL+;else if (2)_ NR+; else (3)_ ;if(t-lchild!=NULL)(4)_; if (t-rchild!=NULL) (5)_; 26.樹的先序非遞歸算法。void example(b) btree *b; btree *stack20, *p；int top;if (b!=null) top=1; s

6、tacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;27.由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#define MAX 100typedef struct Nodechar info; struct Node *llink, *rlink; TNODE;cha

7、r predMAX,inodMAX; main(int argc,int *argv) TNODE *root;if(argc3) exit 0;strcpy(pred,argv1); strcpy(inod,argv2);root=restore(pred,inod,strlen(pred);postorder(root);TNODE *restore(char *ppos,char *ipos,int n) TNODE *ptr； char *rpos; int k;if(ninfo=(1)_;for(2)_ ; rposllink=restore(ppos+1, (4)_,k );ptr

8、-rlink=restore (5)_+k,rpos+1,n-1-k);return ptr;postorder(TNODE*ptr) if(ptr=NULL) return; postorder(ptr-llink); postorder(ptr-rlink); printf(“%c”,ptr-info); 28. 證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。29. 試找出滿足下列條件的二叉樹1）先序序列與后序序列相同 2）中序序列與后序序列相同3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同 30. 設(shè)一棵二叉樹的結(jié)點結(jié)構(gòu)為 (LLINK,INFO,RLINK),

9、ROOT為指向該二叉樹根結(jié)點的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點的指針，試編寫一算法ANCESTOR（ROOT，p,q,r）,該算法找到p和q的最近共同祖先結(jié)點r。31. 設(shè)T是一棵滿二叉樹，編寫一個將T的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞歸算法。32. 請設(shè)計一個算法，要求該算法把二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表，表頭指針為head。 二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點的右指針域來存放單鏈表指針。分析你的算法的時、空復(fù)雜度。33. 設(shè)兩棵二叉樹的的根結(jié)點地址分別為p和q，采用二叉鏈表的形式存儲這兩棵樹上所有的結(jié)點。請編寫程序，判斷它們是否相似。34. 一棵二叉

10、樹以二叉鏈表來表示，求其指定的某一層k(k1)上的葉子結(jié)點的個數(shù)。35. 二叉樹T的中序遍歷序列和層次遍歷序列分別是BAFDGCE和ABCDEFG，試畫出該二叉樹，并寫出由二叉樹的中序遍歷序列和層次遍歷序列確定二叉樹的算法。36. 設(shè)二叉樹的結(jié)點結(jié)構(gòu)是（Lc,data,Rc），其中Lc、Rc分別為指向左、右子樹根的指針，data是字符型數(shù)據(jù)。試寫出算法，求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點的值。2、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，若存在，則以頂點序列的方式輸出該回路（找到一條即可）。（注：圖中不存在頂點到自己的?。?、給

11、定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短?試設(shè)計一個解答上述問題的算法，并應(yīng)用該算法解答如圖所示的實例。（20分）1256342236104469127 圖1 連通網(wǎng)G1、對圖1所示的連通網(wǎng)G，請用Prim算法構(gòu)造其最小生成樹（每選取一條邊畫一個圖）。4、已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,寫出G的拓撲排序的結(jié)果。37.在有向圖G中，如果r到G中的每個結(jié)點都有路徑可達，則稱結(jié)點r

12、為G的根結(jié)點。編寫一個算法完成下列功能：（1）建立有向圖G的鄰接表存儲結(jié)構(gòu)；（2）判斷有向圖G是否有根，若有，則打印出所有根結(jié)點的值。38二部圖（bipartite graph） G=（V，E）是一個能將其結(jié)點集V分為兩不相交子集V 1和V2=V-V1的無向圖，使得：V1中的任何兩個結(jié)點在圖G中均不相鄰，V2中的任何結(jié)點在圖G中也均不相鄰。（1）請各舉一個結(jié)點個數(shù)為5的二部圖和非二部圖的例子。（2）請用C或PASCAL編寫一個函數(shù)BIPARTITE判斷一個連通無向圖G是否是二部圖，并分析程序的時間復(fù)雜度。設(shè)G用二維數(shù)組A來表示，大小為n*n（n為結(jié)點個數(shù)）。請在程序中加必要的注釋。若有必要可直

13、接利用堆?；蜿犃胁僮??！?39我們可用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。所謂“破圈法”就是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請給出用“破圈法”求解給定的帶權(quán)連通無向圖的一棵最小代價生成樹的詳細算法，并用程序?qū)崿F(xiàn)你所給出的算法。注：圈就是回路。40. 請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲。41. 假設(shè)K1，Kn是n個關(guān)鍵詞，試解答：試用二叉查找樹的插入算法建立一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序為K1，K2，Kn時，用算法建立一棵以LLINK / RLINK 鏈接表示的二叉查找樹。42. 給出折半

14、查找的遞歸算法，并給出算法時間復(fù)雜度性分析。43. 寫出從哈希表中刪除關(guān)鍵字為K的一個記錄的算法，設(shè)哈希函數(shù)為H，解決沖突的方法為鏈地址法。44. 在用除余法作為散列函數(shù)、線性探測解決沖突的散列表中，寫一刪除關(guān)鍵字的算法，要求將所有可以前移的元素前移去填充被刪除的空位，以保證探測序列不致于斷裂。45. 假設(shè)一棵平衡二叉樹的每個結(jié)點都標(biāo)明了平衡因子b,試設(shè)計一個算法，求平衡二叉樹的高度。46. 有一個100*100的稀疏矩陣，其中1%的元素為非零元素，現(xiàn)要求用哈希表作存儲結(jié)構(gòu)。（1）請你設(shè)計一個哈希表（2）請寫一個對你所設(shè)計的哈希表中給定行值和列值存取矩陣元素的算法；并對你的算法所需時間和用一維

15、數(shù)組（每個分量存放一個非零元素的行值，列值，和元素值）作存儲結(jié)構(gòu)時存取元素的算法.2、畫出向小頂堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時，每加入一個數(shù)據(jù)后堆的變化。47. 冒泡排序算法是把大的元素向上移（氣泡的上?。?，也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的冒泡排序算法。48.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進行排序，請寫出這種排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）49. 6.有一種簡單的排序算法，叫做計數(shù)排序（count sorting）。這種排序算法對一個待排序的表(用數(shù)組表示)進行排序，并

16、將排序結(jié)果存放到另一個新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同，計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小，假設(shè)針對某一個記錄，統(tǒng)計出的計數(shù)值為c，那么，這個記錄在新的有序表中的合適的存放位置即為c。 (1) (3分)給出適用于計數(shù)排序的數(shù)據(jù)表定義; (2) (7分)使用Pascal或C語言編寫實現(xiàn)計數(shù)排序的算法； (3) (4分)對于有n個記錄的表，關(guān)鍵碼比較次數(shù)是多少? (4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什么?50. 9設(shè)有一個數(shù)組中存放了一個無序的關(guān)鍵序列K1、K2、Kn?，F(xiàn)要求將Kn放在將元素

17、排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組rl.h中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“not find”信息。請編寫出算法并簡要說明算法思想。52. 二路插入排序是將待排關(guān)鍵字序列r1.n中關(guān)鍵字分二路分別按序插入到輔助向量d1.n前半部和后半部（注:向量d可視為循環(huán)表），其原則為，先將rl賦給d1，再從r2 記錄開始分二路插入。編寫實現(xiàn)二路插入排序算法。二、 算法設(shè)計題（每題15分，共60分）1、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包

18、括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域next。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保留一個。#include typedef char datatype;typedef struct node datatype data; struct node * next; listnode;typedef listnode* linklist;/*-*/* 刪除單鏈表中重復(fù)的結(jié)點 */*-*/linklist deletelist(linklist head) listnode *p,*s,*q; p=head-next; whi

19、le(p) s=p; q=p-next; while(q) if(q-data=p-data) s-next=q-next;free(q); q=s-next; else s=q; /*找與P結(jié)點值相同的結(jié)點*/ q=q-next; p=p-next; return head; 3、約瑟夫環(huán)問題（Josephus問題）是指編號為1、2、，n的n（n0）個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到所有的人全部出列為止。現(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計一個算法，模擬此過程。#includetypedef

20、 int datatype;typedef struct nodedatatype data; struct node *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1為報數(shù)的起點*/ while (count!=s) /*找初始報數(shù)起點*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*當(dāng)循環(huán)鏈表中的結(jié)點個數(shù)大于1時*/ p=

21、k1; /*從k1開始報數(shù)*/ count=1; while (count!=m) /*連續(xù)數(shù)m個結(jié)點*/ pre=p; p=p-next; count+; pre-next=p-next; /*輸出該結(jié)點，并刪除該結(jié)點*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的報數(shù)起點*/ printf(%4d,k1-data); /*輸出最后一個結(jié)點*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); p

22、rintf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0;i-) /*建立剩余n-1個結(jié)點*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循環(huán)鏈表*/ jose(head,s,m); /*調(diào)用函數(shù)*/ 4、 void LinkList_reverse(Linklist &L) /鏈表的就地逆置;為簡化算法,假設(shè)表長大于2 p=L-next;q=p-next;s=q-next;p-

23、next=NULL; while(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐個插入新表表頭q-next=p;s-next=q;L-next=s;/LinkList_reverse23、題目分析本題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出Ai（0=inext=h; /形成空循環(huán)鏈表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重復(fù)數(shù)據(jù)不再輸入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-nex

24、t=s; s-next=p;/將結(jié)點s鏈入鏈表中/for return(h);算法結(jié)束3、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分） （1）A和D是合法序列，B和C 是非法序列。 （2）設(shè)被判定的操作序列已存入一維數(shù)組A中。 int Judge(char A) /判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。 i=0; /i為下標(biāo)。 j=k=0; /j和k分別為I和字母O的的個數(shù)。 while(Ai!=0) /當(dāng)未到字符數(shù)組尾就作。

25、switch(Ai) caseI: j+; break; /入棧次數(shù)增1。 caseO: k+; if(kj)printf(“序列非法n”)；exit(0); i+; /不論Ai是I或O，指針i均后移。 if(j!=k) printf(“序列非法n”)；return(false); else printf(“序列合法n”)；return(true); /算法結(jié)束。5#define maxsize ?？臻g容量 void InOutS(int smaxsize) /s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時為?？铡?for(i=1;

26、i=n; i+) /n個整數(shù)序列作處理。 scanf(“%d”,&x); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時入棧。 if(top=maxsize-1)printf(“棧滿n”);exit(0);else s+top=x; /x入棧。 else /讀入的整數(shù)等于-1時退棧。 if(top=0)printf(“?？課”);exit(0); else printf(“出棧元素是%dn”,stop-)； /算法結(jié)束。若第n件物品能放入背包，則問題變?yōu)槟芊裨購膎-1件物品中選出若干件放入背包（這時背包可放入物品的重量變?yōu)閟-wn）。若第n件物品不能放入背包，則考慮從n

27、-1件物品選若干件放入背包（這時背包可放入物品仍為s）。若最終s=0,則有一解；否則，若s0但物品數(shù)n1,則無解。（1）s-wn,n-1 /Knap(s-wn,n-1)=true（2）s,n-1 / KnapKnap(s,n-1)3S6S2S3S4S5S5S1S1S1S1S1S1分別求出str1、str2的長度m、n 將兩個鏈表的表尾對齊。p、q兩個指針。 p、q兩個指針同步移動，直到指向相同結(jié)點。先將n個數(shù)據(jù)(前后對應(yīng)交換)原地逆置，然后再將前np和后p個分別原地逆置。Void reverse(int r, int left, int right)int k=left, j=right, t

28、emp;while (k0&pn) reverse(r,0,n-1)；reverse(r,0,n-p-1)；reverse(r,n-p,n-1)；4. 題目分析題目中要求矩陣兩行元素的平均值按遞增順序排序，由于每行元素個數(shù)相等，按平均值排列與按每行元素之和排列是一個意思。所以應(yīng)先求出各行元素之和，放入一維數(shù)組中，然后選擇一種排序方法，對該數(shù)組進行排序，注意在排序時若有元素移動，則與之相應(yīng)的行中各元素也必須做相應(yīng)變動。void Translation（float *matrix，int n）/本算法對nn的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。int i,j,k,l；fl

29、oat sum，min； /sum暫存各行元素之和 float *p, *pi, *pk;for(i=0; in; i+) sum=0.0; pk=matrix+i*n; /pk指向矩陣各行第1個元素. for (j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和.*(p+i)=sum; /將一行元素之和存入一維數(shù)組. /for ifor(i=0; in-1; i+) /用選擇法對數(shù)組p進行排序 min=*(p+i); k=i; /初始設(shè)第i行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj; /記新的最小值及行號.if(i!=

30、k) /若最小行不是當(dāng)前行,要進行交換(行元素及行元素之和) pk=matrix+n*k; /pk指向第k行第1個元素. pi=matrix+n*i; /pi指向第i行第1個元素. for(j=0;jn;j+) /交換兩行中對應(yīng)元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum; sum=pi; pi=pk; pk=sum; /交換一維數(shù)組中元素之和. /if/for i free(p); /釋放p數(shù)組./ Translation算法分析 算法中使用選擇法排序,比較次數(shù)較多,但數(shù)據(jù)交換(移動)較少.若用其它排序方法,雖可減少比較次數(shù),但數(shù)據(jù)移動會增多.算

31、法時間復(fù)雜度為O(n2).7題目分析我們用l代表最長平臺的長度，用k指示最長平臺在數(shù)組b中的起始位置（下標(biāo)）。用j記住局部平臺的起始位置，用i指示掃描b數(shù)組的下標(biāo)，i從0開始，依次和后續(xù)元素比較，若局部平臺長度（i-j）大于l時，則修改最長平臺的長度k（l=i-j）和其在b中的起始位置（k=j），直到b數(shù)組結(jié)束，l即為所求。void Platform (int b , int N) /求具有N個元素的整型數(shù)組b中最長平臺的長度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最長平臺i+; j=i; /新平臺起點printf(“最長平臺

32、長度%d，在b數(shù)組中起始下標(biāo)為%d”，l，k)；/ Platform8題目分析矩陣中元素按行和按列都已排序，要求查找時間復(fù)雜度為O（m+n），因此不能采用常規(guī)的二層循環(huán)的查找。可以先從右上角（i=a,j=d）元素與x比較，只有三種情況：一是Ai,jx， 這情況下向j 小的方向繼續(xù)查找；二是Ai,jx，下步應(yīng)向i大的方向查找；三是Ai,j=x，查找成功。否則，若下標(biāo)已超出范圍，則查找失敗。void search(datatype A , int a,b,c,d, datatype x) /n*m矩陣A,行下標(biāo)從a到b,列下標(biāo)從c到d,本算法查找x是否在矩陣A中. i=a; j=d; flag=0

33、; /flag是成功查到x的標(biāo)志 while(i=c) if(Aij=x) flag=1;break; else if (Aijx) j-; else i+; if(flag) printf(“A%d%d=%d”,i,j,x); /假定x為整型. else printf(“矩陣A中無%d 元素”，x)； 算法search結(jié)束。算法討論算法中查找x的路線從右上角開始，向下（當(dāng)xAi,j）或向左（當(dāng)xAi,j）。向下最多是m，向左最多是n。最佳情況是在右上角比較一次成功，最差是在左下角（Ab,c），比較m+n次，故算法最差時間復(fù)雜度是O(m+n）。22、題目分析數(shù)組A和B的元素分別有序，欲將兩數(shù)組

34、合并到C數(shù)組，使C仍有序，應(yīng)將A和B拷貝到C，只要注意A和B數(shù)組指針的使用，以及正確處理一數(shù)組讀完數(shù)據(jù)后將另一數(shù)組余下元素復(fù)制到C中即可。void union(int A,B,C,m,n)/整型數(shù)組A和B各有m和n個元素，前者遞增有序，后者遞減有序，本算法將A和B歸并為遞增有序的數(shù)組C。i=0; j=n-1; k=0;/ i，j，k分別是數(shù)組A,B和C的下標(biāo)，因用C描述，下標(biāo)從0開始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法結(jié)束4、要求二叉樹按二叉鏈表形式存儲。15分（1）寫一個建立二叉樹的算法。（2）寫一個判別

35、給定的二叉樹是否是完全二叉樹的算法。BiTree Creat() /建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu)ElemType x；BiTree bt;scanf(“%d”,&x); /本題假定結(jié)點數(shù)據(jù)域為整型if(x=0) bt=null;else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“輸入錯誤”)；return(bt);/結(jié)束 BiTreeint JudgeComplete(BiTree bt) /判斷二叉樹是否是完全二叉樹,如是，

36、返回1，否則，返回0int tag=0; BiTree p=bt, Q; / Q是隊列，元素是二叉樹結(jié)點指針，容量足夠大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化隊列，根結(jié)點指針入隊while (!QueueEmpty(Q)p=QueueOut(Q); /出隊 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入隊 else if (p-lchild) return 0; /前邊已有結(jié)點為空，本結(jié)點不空 else tag=1; /首次出現(xiàn)結(jié)點為空 if (p-rchild & !tag)

37、 QueueIn(Q,p-rchild); /右子女入隊 else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete3、已知一棵二叉樹的中序遍歷結(jié)果為：DBFEAGHCI，后序遍歷結(jié)果為：DFEBHGICA。（1）畫出這棵二叉樹，并寫出它的前序遍歷結(jié)果；（2）將這棵二叉樹轉(zhuǎn)換成等價的森林或樹。前序遍歷結(jié)果為：ABDEFCGHI24. (1)p-rchild (2)p-lchild (3)p-lchild (4)ADDQ(Q,p-lchild) (5)ADDQ(Q,p-rchild)25. (1)t-rchild

38、!=null (2)t-rchild!=null (3)N0+ (4)count(t-lchild) (5)count(t-rchild)26. .(1)top+ (2) stacktop=p-rchild (3)top+ (4)stacktop=p-lchild27. (1)*ppos / 根結(jié)點 （2）rpos=ipos (3)rposipos (4)ipos (5)ppos+128. 證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。當(dāng)n=1時，只有一個根結(jié)點，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。設(shè)中序序列為S1，S2，S

39、m,后序序列是P1,P2,，Pm。因后序序列最后一個元素Pm是根，則在中序序列中可找到與Pm相等的結(jié)點（設(shè)二叉樹中各結(jié)點互不相同）Si(1im)，因中序序列是由中序遍歷而得，所以Si是根結(jié)點，S1，S2，Si-1是左子樹的中序序列，而Si+1,Si+2,Sm是右子樹的中序序列。若i=1，則S1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點數(shù)是m-1,則S2，S3，Sm和P1，P2，Pm-1可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則Sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點數(shù)是m-1，則S1，S2，Sm-1和P1，P2，Pm-1唯一確定左子樹，從而也確定了二叉樹。最后，當(dāng)1i0)whi

40、le(bt!=null & bt!=p & bt!=q) /結(jié)點入棧s+top.t=bt; stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左側(cè),遇結(jié)點p時，棧中元素均為p的祖先結(jié)點for(i=1;i0;i-)/；將棧中元素的樹結(jié)點到s1去匹配pp=si.t;for (j=top1;j0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 & stop.tag=1) top-; /退棧if (top!=0)stop.tag=1;bt=stop.t-rc

41、hild; /沿右分枝向下遍歷/結(jié)束while(bt!=null |top0)return(null);/、p無公共祖先/結(jié)束Ancestor31. .題目分析對一般二叉樹，僅根據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/將滿二叉樹的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點的下標(biāo)。if(h1=l1)posth2=prel1; /根結(jié)點half=(h1-l1)/2; /左或右子樹的結(jié)點數(shù)PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) /將左子樹先序序列轉(zhuǎn)為后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /將右子樹先序序列轉(zhuǎn)為后序序列 /PreToPost32. .題目分析葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rc