1、假設K1，…，Kn是n個關鍵詞，試解答：試用二叉查找樹的插入算法建立一棵二叉查找樹，即當關鍵詞的插入次序為K1，K2，…，Kn時，用算法建立一棵以LLINK/RLINK鏈接表示的二叉查找樹。2、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，采用遞歸算法。intSimilar(BiTreep,q)//判斷二叉樹p和q是否相似{if(p==null&&q==null)return(1);elseif(!p&&q||p&&!q)return(0);elsereturn(Similar(p->lchild,q->lchild)&&Similar(p->rchild,q->rchild))}//結束Similar3、設從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an,試編寫算法實現(xiàn)：用棧結構存儲輸入的整數(shù)，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應對異常情況（入棧滿等）給出相應的信息。設有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，...，Wn。問能否從這n件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,...，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在下列算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)若S=0則Knap←true否則若（S<0）或(S>0且n<1)則Knap←false否則若Knap(1),_=true則print(W[n])；Knap←true否則Knap←Knap(2)_,_設有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1，則順序棧的容量至少應為多少？畫出具體進棧、出棧過程。假定采用帶頭結點的單鏈表保存單詞，當兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如：設str1和str2是分別指向兩個單詞的頭結點，請設計一個盡可能的高效算法，找出兩個單詞共同后綴的起始位置，分析算法時間復雜度。將n(n>1)個整數(shù)存放到一維數(shù)組R中。設計一個盡可能高效（時間、空間）的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即將R中的數(shù)據(jù)（x0,x1,x2,…,xn-1），變換為(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。4、我們可用“破圈法”求解帶權連通無向圖的一棵最小代價生成樹。所謂“破圈法”就是“任取一圈，去掉圈上權最大的邊”，反復執(zhí)行這一步驟，直到?jīng)]有圈為止。請給出用“破圈法”求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細算法，并用程序實現(xiàn)你所給出的算法。注：圈就是回路。5、根據(jù)二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全局指針變量pre（初值為null）和全局變量flag，初值為true。若非二叉排序樹，則置flag為false。#definetrue1#definefalse0typedefstructnode{datatypedata;structnode*llink,*rlink;}*BTree;voidJudgeBST（BTreet,intflag）//判斷二叉樹是否是二叉排序樹，本算法結束后，在調(diào)用程序中由flag得出結論。{if（t!=null&&flag）{Judgebst（t->llink,flag）；//中序遍歷左子樹if（pre==null）pre=t；//中序遍歷的第一個結點不必判斷elseif（pre->data<t->data）pre=t；//前驅指針指向當前結點else{flag=flase；}//不是完全二叉樹Judgebst（t->rlink,flag）；//中序遍歷右子樹}//JudgeBST算法結束6、二路插入排序是將待排關鍵字序列r[1..n]中關鍵字分二路分別按序插入到輔助向量d[1..n]前半部和后半部（注:向量d可視為循環(huán)表），其原則為，先將r[l]賦給d[1]，再從r[2]記錄開始分二路插入。編寫實現(xiàn)二路插入排序算法。7、(1)p->rchild(2)p->lchild(3)p->lchild(4)ADDQ(Q,p->lchild)(5)ADDQ(Q,p->rchild)25.(1)t->rchild!=null(2)t->rchild!=null(3)N0++(4)count(t->lchild)(5)count(t->rchild)26..(1)top++(2)stack[top]=p->rchild(3)top++(4)stack[top]=p->lchild27.(1)*ppos//根結點（2）rpos=ipos(3)rpos–ipos(4)ipos(5)ppos+18、設有一個數(shù)組中存放了一個無序的關鍵序列K1、K2、…、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關鍵字的次數(shù)不超過n。51.借助于快速排序的算法思想，在一組無序的記錄中查找給定關鍵字值等于key的記錄。設此組記錄存放于數(shù)組r[l..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind”信息。請編寫出算法并簡要說明算法思想。9、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。當n=1時，只有一個根結點，由中序序列和后序序列可以確定這棵二叉樹。設當n=m-1時結論成立，現(xiàn)證明當n=m時結論成立。設中序序列為S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一個元素Pm是根，則在中序序列中可找到與Pm相等的結點（設二叉樹中各結點互不相同）Si(1≤i≤m)，因中序序列是由中序遍歷而得，所以Si是根結點，S1，S2，…，Si-1是左子樹的中序序列，而Si+1,Si+2,…,Sm是右子樹的中序序列。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}listnode;typedeflistnode*linklist;voidjose(linklisthead,ints,intm){linklistk1,pre,p;intcount=1;pre=NULL;k1=head;/*k1為報數(shù)的起點*/while(count!=s)/*找初始報數(shù)起點*/{pre=k1;k1=k1->next;count++;}while(k1->next!=k1)/*當循環(huán)鏈表中的結點個數(shù)大于1時*/{p=k1;/*從k1開始報數(shù)*/count=1;while(count!=m)/*連續(xù)數(shù)m個結點*/{pre=p;p=p->next;count++;}pre->next=p->next;/*輸出該結點，并刪除該結點*/printf("%4d",p->data);free(p);k1=pre->next;/*新的報數(shù)起點*/}printf("%4d",k1->data);/*輸出最后一個結點*/free(k1);}main(){linklisthead,p,r;intn,s,m,i;printf("n=");scanf("%d",&n);printf("s=");scanf("%d",&s);printf("m=",&m);scanf("%d",&m);if(n<1)printf("n<0");else{/*建表*/head=(linklist)malloc(sizeof(listnode));/*建第一個結點*/head->data=n;r=head;for(i=n-1