1、1、我們用l代表最長平臺的長度，用k指示最長平臺在數組b中的起始位置下標。用j記住局部平臺的起始位置，用i指示掃描b數組的下標，i從0開始，依次和后續元素比較，假設局部平臺長度i-j大于l時，那么修改最長平臺的長度kl=i-j和其在b中的起始位置k=j，直到b數組結束，l即為所求。void Platform (int b , int N) /求具有N個元素的整型數組b中最長平臺的長度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最長平臺i+; j=i; /新平臺起點printf(“最長平臺長度%d，在b數組中起始下標為%d，l，k)

2、；/ Platform2、請設計一個算法，要求該算法把二叉樹的葉子結點按從左到右的順序連成一個單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時用葉子結點的右指針域來存放單鏈表指針。分析你的算法的時、空復雜度。3、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當前權值最大的邊后，就去測試圖是否仍連通，假設不再連通，那么將該邊恢復。假設仍連通，繼續向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權連通無向圖的一棵最小

3、代價生成樹。typedef struct int i,j,wnode; /設頂點信息就是頂點編號，權是整型數 node edge; scanf( %d%d,&e,&n) ; /輸入邊數和頂點數。 for (i=1;i=e;i+) /輸入e條邊：頂點，權值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權值大小，對邊進行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數e=n-1. if (connect(k) /刪除第k條邊假設仍連通。 edgek.w=

4、0; eg-; /測試下一條邊edgek，權值置0表示該邊被刪除k+; /下條邊 /while /算法結束。 connect()是測試圖是否連通的函數，可用圖的遍歷實現，4、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全局指針變量pre初值為null和全局變量flag，初值為true。假設非二叉排序樹，那么置flag為false。#define true 1#define false 0typedef struct node datatype data; struct node *llink,*rlink; *BTree; voi

5、d JudgeBSTBTree t,int flag/ 判斷二叉樹是否是二叉排序樹，本算法結束后，在調用程序中由flag得出結論。 ift!=null & flag Judgebstt-llink,flag；/ 中序遍歷左子樹 ifpre=nullpre=t；/ 中序遍歷的第一個結點不必判斷 else ifpre-datadatapre=t；/前驅指針指向當前結點 elseflag=flase； /不是完全二叉樹 Judgebst t-rlink,flag；/ 中序遍歷右子樹/JudgeBST算法結束5、二路插入排序是將待排關鍵字序列r1.n中關鍵字分二路分別按序插入到輔助向量d1.n前半部和

6、后半部注:向量d可視為循環表，其原那么為，先將rl賦給d1，再從r2 記錄開始分二路插入。編寫實現二路插入排序算法。6、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。29. 試找出滿足以下條件的二叉樹1先序序列與后序序列相同 2中序序列與后序序列相同3先序序列與中序序列相同 4中序序列與層次遍歷序列相同7、設從鍵盤輸入一整數的序列：a1, a2, a3，an,試編寫算法實現：用棧結構存儲輸入的整數，當ai-1時，將ai進棧；當ai=-1時，輸出棧頂整數并出棧。算法應對異常情況入棧滿等給出相應的信息。設有一個背包可以放入的物品重量為S，現有n件物品，重量分別為W1，W2，.，Wn。

7、問能否從這n件物品中選擇假設干件放入背包，使得放入的重量之和正好是S。設布爾函數Knap(S，n)表示背包問題的解，Wi(i=1,2,.，n)均為正整數，并已順序存儲地在數組W中。請在以下算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)假設S=0那么Knaptrue否那么假設S0且n1)個整數存放到一維數組R中。設計一個盡可能高效時間、空間的算法，將R中保存的序列循環左移p0pnext;q=p-next;s=q-next;p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; /把L的元素逐個插入新表表頭 q-next=p;s-

8、next=q;L-next=s;/LinkList_reverse9、#define maxsize ?？臻g容量 void InOutS(int smaxsize) /s是元素為整數的棧，本算法進行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時為?？铡?for(i=1; ilchild!=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) btre

9、e *b; btree *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d,p-data);if (p-rchild!=null)(1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;11、設有一個數組中存放了一個無序的關鍵序列K1、K2、Kn?，F要求將Kn放在將元素排序后的正確位置上，試編寫實現該功能的算法，要求比較關鍵字的次數不超過n。51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關鍵字值等于key的記錄。設此組記錄

10、存放于數組rl.h中。假設查找成功，那么輸出該記錄在r數組中的位置及其值，否那么顯示“not find信息。請編寫出算法并簡要說明算法思想。12、約瑟夫環問題Josephus問題是指編號為1、2、，n的nn0個人按順時針方向圍坐成一圈，現從第s個人開始按順時針方向報數，數到第m個人出列，然后從出列的下一個人重新開始報數，數到第m的人又出列，如此重復直到所有的人全部出列為止。現要求采用循環鏈表結構設計一個算法，模擬此過程。#includetypedef int datatype;typedef struct nodedatatype data; struct node *next;listnod

11、e;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1為報數的起點*/ while (count!=s) /*找初始報數起點*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*當循環鏈表中的結點個數大于1時*/ p=k1; /*從k1開始報數*/ count=1; while (count!=m) /*連續數m個結點*/ pre=p; p=p-next; co

12、unt+; pre-next=p-next; /*輸出該結點，并刪除該結點*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的報數起點*/ printf(%4d,k1-data); /*輸出最后一個結點*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0

13、;i-) /*建立剩余n-1個結點*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循環鏈表*/ jose(head,s,m); /*調用函數*/ 13、后序遍歷最后訪問根結點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹結點的指針，當訪問到某結點時，棧中所有元素均為該結點的祖先。此題要找p和q 的最近共同祖先結點r ,不失一般性，設p在q的左邊。后序遍歷必然先遍歷到結點p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續遍歷到結點q時，將棧中元

14、素從棧頂開始逐個到輔助棧中去匹配，第一個匹配即相等的元素就是結點p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示結點的左子女已被訪問，tag=1表示結點的右子女已被訪問stack;stack s,s1;/棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)/求二叉樹上結點p和q的最近的共同祖先結點r。top=0; bt=ROOT; while(bt!=null |top0)while(bt!=null & bt!=p & bt!=q) /結點入棧s+top.t=bt; stop.tag=0; bt=bt-lc

15、hild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左側,遇結點p時，棧中元素均為p的祖先結點for(i=1;i0;i-)/；將棧中元素的樹結點到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-rchild; /沿右分枝向下遍歷/結束while(bt!=null |top0)return(null);/、p無公共祖先/結束Ancestor14、冒泡排序算法是把大的元素向上移氣泡的上浮，也可以把小的元素向下移氣泡的下沉請給出