算法設計題?1.設二叉樹b?t采用二叉?鏈表結構存?儲。試設計一個?算法輸出二?叉樹中所有?非葉子結點?，并求出非葉?子結點的個?數。【答案】intcount?=0;voidalgo2?(BTNod?e*bt){if(bt){if(bt->lchil?d||bt->rchil?d){print?f(bt->data);count?++;}algo2?(bt->lchil?d);algo2?(bt->rchil?d);}}2.閱讀以下函?數arra?nge()intarran?ge(inta[],int1,inth,intx){//1和h分別?為數據區的?下界和上界?inti,j,t；i=1；j=h；while?(i<j){while?(i<j&&a[j]>=x)j--；while?(i<j&&a[j]>=x)i++；if(i<j){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]<x)retur?ni；elseretur?ni－1；}〔1〕寫出該函數?的功能；〔2〕寫一個調用?上述函數實?現以下功能?的算法：對一整型數?組b[n]中的元素進?行重新排列?，將所有負數?均調整到數?組的低下標?端，將所有正數?均調整到數?組的高低標?端，假設有零值，那么置于兩者?之間，并返回數組?中零元素的?個數。【答案】〔1〕該函數的功?能是：調整整數數?組a[]中的元素并?返回分界值?i，使所有＜x的元素均?落在a[1..i]上，使所有≥x的元素均?落在a[i＋1..h]上。〔2〕intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arran?ge(b,0,n－1,0)；p=arran?ge(b,0,n－1,1)；q=arran?ge(b,p+1,n－1,1)；q=arran?ge(b,0,p,0)；retur?nq－p；retur?np－q；}}3.假設線性表?以帶表頭結?點的循環單?鏈表表示。試設計一個?算法，在線性表的?第k個元素?前插入新元?素y。假設表長小?于k，那么插在表尾?。【答案】voidalgo1?(LNode?*h,intk,ElemT?ypey){q=h;P=h->next;j=1;while?(p!=h&&j<k){q=p;p=p->next;j++;}s=(LNode?*)mallo?c(sizeo?f(Lnode?));s->data=y;q->next=s;s->next=q;}4.二叉排序樹?的類型定義?如下：typed?efstruc?tBSTNo?de{∥二叉排序樹?的結點結構?intdata;∥數據域struc?tBSTNo?de*lchil?d,*rchil?d;∥左、右孩子指針?}BSTNo?de,*BSTre?e;設計遞歸算?法，統計一棵二?叉排序樹T?中值小于a?的結點個數?。【答案】intf34(BSTre?eroot){intcount?;BSTNo?de*p;p=root;if(p&&p->data<a)count?++;f34(p->lchil?d);retur?ncount?;}5.設二叉樹T?采用二叉鏈?表結構存儲?，試設計算法?求出二叉樹?中離根最近?的第一個葉?子結點。〔注：結點按從上?往下，自左至右次序編?號〕【答案】BTNod?e*First?leaf(BTNod?e*bt){InitQ?ueue(Q);//初始化隊列?Qif(bt){EnQue?ue(Q,bt);;while?(!Empty?Queue?(Q)){DeQue?ue(Q,p);if(!p->lchil?d&&!p->rchil?d)retur?np;if(p->lchil?d)EnQue?ue(Q,p->lchil?d);if(p->rchil?d)EnQue?ue(Q,p->rchil?d);}}}6.一棵具?有n個結點?的完全二叉?樹被順序存?儲在一維數?組中，結點為字符?類型,編寫算法打?印出編號為?k的結點的?雙親和孩子?結點。【答案】intalgo2?(charbt[],intn,intk){if(k<1||k>n)retur?n0;if(k==1)print?f(“%cisaroot\n〞,bt[1]);elseprint?f(“%c’sparen?tis%c\n〞,bt[k],bt[k/2]);if(2*k<=n)print?f(“%c’slchil?dis%c\n〞,bt[k],bt[2*k]);elseprint?f(“%cisnotlchil?d\n〞,bt[k]));if(2*k+1<=n)print?f(“%c’srchil?dis%c\n〞,bt[k],bt[2*k+1]);elseprint?f(“%cisnotrchil?d\n〞,bt[k]));retur?n1;}7.編寫算法，將非空單鏈?表hb插入?到單鏈表h?a的第i(0<i≤表長)個結點前。【答案】intalgo1?(LNode?*ha,LNode?*hb,inti){for(p=hb;p->next;p=p->next);for(j=1,q=ha;j<i;j++)q=q->next;p->next=q->next;q->next=hb->next；free(hb);}8.設二叉樹T?已按完全二?叉樹的形式?存儲在順序?表T中，試設計算法?根據順序表?T建立該二?叉樹的二叉?鏈表結構。順序表T定?義如下：struc?ttree{intno;/*結點按完全?二叉樹的編?號*/ElEMT?Pdata;/*數據域*/}T[N];/*N為二叉樹?T的結點數?*/【答案】BTNod?e*creat?_tree?(struc?ttreeT[N]){BTNod?e*p[MAX];t=NULL;for(i=0;i<N;i++){s=(BTNod?e*)mallo?c(sizeo?f(BTNod?e));s->data=T[i].data;s->lchil?d=s->rchil?d=NULL;m=T[i].no;p[m]=s; if(m==1)t=s; else{j=m/2; if(m%2==0)p[j]->lchil?d=s;elsep[j]->rchil?d=s;}//slse}//forretur?nt;}//creat?_tree?9.編寫算法判?斷帶表頭結?點的單鏈表?L是否是遞?增的。假設遞增返回?1，否那么返回0?。【答案】intalgo1?(LNode?*L){if(!L->next)retur?n1;p=L->next;while?(p->next){if(p->data<p->next->data)p=p->next;elseretur?n0;}retur?n1;}10.假設一線性?表由Fib?onacc?i數列的前?n〔n≥3〕項構成，試以帶表頭?結點的單鏈?表作該線性?表的存儲結?構，設計算法建?立該單鏈表?，且將項數n?存儲在表頭?結點中。Fibon?acci數?列根據下式?求得：1(n=1)f(n)=1(n=2)f(n-2)+f(n-1)(n≥3)【答案】LNode?*Creat?list(LNode?*h,intn){h=(LNode?*)mallo?c(sizeo?f(Lnode?));h->data=n;h->next=p=(LNode?*)mallo?c(sizeo?f(Lnode?));p->next=q=(LNode?*)mallo?c(sizeo?f(Lnode?));p->data=q->data=1;for(i=3;i<=n;i++){q->next=s=(LNode?*)mallo?c(sizeo?f(Lnode?));s->data=p->data+q->data;s->next=NULL;p=q;q=s;}retur?nh;}11.設二叉樹T?采用二叉鏈?表結構存儲?，數據元素為?字符類型。設計算法將?二叉鏈表中?所有dat?a域為小寫?字母的結點?改為大寫字母。【答案】voidalgo2?(BTNod?e*bt){if(bt){if(bt->data>=’a’&&bt->data<=’z’)bt->data-=32;algo2?(bt->lchil?d);algo2?(bt->rchil?d);}}12.假設線性表?以帶表頭結?點的循環單?鏈表表示。試設計一個?算法，在線性表的?第k個元素?前插入新元?素y。假設表長小?于k，那么插在表尾?。【答案】voidInser?tlist?(LNode?*h,intk,ElemT?ypey){q=h;P=h->next;j=1;while?(p!=h&&j<k){q=p;p=p->next;j++;}s=(LNode?*)mallo?c(sizeo?f(Lnode?));s->data=y;q->next=s;s->next=q;}13.有一帶表頭?結點的單鏈?表，其結點的元?素值以非遞?減有序排列?，編寫一個算?法在該鏈表?中插入一個?元素x，使得插入后?的單鏈表仍?有序。【答案】voidalgo1?(LNode?*H,ElemT?px){s=(LNode?*)mallo?c(sizeo?f(LNode?));s->data=x;q=H;p=H->next;while?(p&&p->data<=x){q=p;p=p->next;}s->next=p;q->next=s;}14.二叉排序樹?的類型定義?如下：typed?efstruc?tBSTNo?de{∥二叉排序樹?的結點結構?intdata;∥數據域struc?tBSTNo?de*lchil?d,*rchil?d;∥左、右孩子指針?}BSTNo?de,*BSTre?e;設計遞歸算?法，統計一棵二?叉排序樹T?中值小于a?的結點個數?。【答案】intf34(BSTre?eroot){intcount?;BSTNo?de*p;p=root;if(p&&p->data<a)count?++;f34(p->lchil?d);retur?ncount?;}15.有一帶表頭?結點的單鏈?表，其結點的d?ata域的?類型為字符?型，編寫一個算?法刪除該鏈?表中的數字?字符。【答案】voidDel_d?igit(LNode?*h){for(p=h;p->next;){q=p->next;if(q->data>=’0’&&q->data<=’9’){p->next=q->next;free(q);}elsep=q;}}16.利用棧的基?本運算，編寫一個算?法，實現將整數?轉換成二進?制數輸出。【答案】voidretur?nDtoO?(intnum){ initS?tack(s); while?(n){k=n%2;n=n/2;push(s,k);}while?(Empty?Stack?(s)){pop(s,k);print?f(“%d〞,k);}}17.設二叉樹T?采用二叉鏈?表結構存儲?，數據元素為?int型，試設計一個?算法，假設結點左孩?子的dat?a域的值大?于右孩子的?data域?的值，那么交換其左?、右子樹。【答案】voidalgo2?(bitre?ptrbt){bitre?ptrx;if(bt){if((bt->lchil?d&&bt->rchil?d)&&(bt->lchil?d->data>bt->rchil?d->data)){x=bt->lchil?d;bt->lchil?d=bt->rchil?d;bt->rchil?d=x;}algo2?(bt->lchil?d);algo2?(bt->rchil?d);}}18.設二叉樹T?采用二叉鏈?表結構存儲?，試設計算法?求出二叉樹?的深度。【答案】intDeep(BTNod?e*bt){if(bt==NULL)retur?n0;left=Deep(bt->lchil?d);right?=Deep(bt->rchil?d);retur?n(left>right??left:right?)+1;}19.設給定的哈?希表存儲空?間為H〔0～M-1〕，哈希函數的?構造方法為?“除留余數法?〞，處理沖突的?方法為“線性探測法?〞，設計算法將?元素e填入?到哈希表中?。【答案】voidhash-inser?t(hashT?ableh[],intm,ElemT?ypee){j=e%p;if(h[j]!=NULL)h[j]=e;else{do{j=(j+1)%m;}while?(h[j]!=NULL);h[j]=e;}}20.對于給定的?十進制正整?數,打印出對應?的八進制正?整數。〔利用棧〕【答案】voidDecTo?Oct(intnum){ initS?tack(s); //初始化棧 while?(n){k=n%8;n=n/8;push(s,k);}while?(Empty?Stack?(s))//判斷棧是否?為空{pop(s,k);print?f(“%d〞,k);}}21.一個正讀和?反讀都相同?的字符序列?稱為“回文〞。例如“abcba?〞和“1221〞是回文，而“abcde?〞不是回文。試寫一個算?法，要求利用棧?的根本運算?識別一個以?@為結束符的?字符序列是?否是回文。【答案】intPair(char*str){InitS?tack(s)；p=strfor(;*p!=’@’;p++)Push(s,*p);while?(Stack?Empty?(s)){Pop(s,y);if(y!=*str++)retur?n0;}retur?n1;}22.有一帶表頭?結點的單鏈?表，其結點的元?素值以非遞?減有序排列?，編寫一個算?法刪除該鏈?表中多余的?元素值相同?的結點(值相同的結?點只保存一?個)。【答案】voidDelsa?me(LNode?*h){if(h->next){for(p=h->next;p->next;){q=p->next;if(p->data==q->data){p->next=q->next;free(q);}elsep=q;}}23.編寫一個算?法，判斷帶表頭?結點的單鏈?表是否遞增?有序。【答案】intfun(LNode?*h){p=h->next;while?(p->next){q=p->next;if(q->data>p->data)retur?n0;p=q;}retur?n1;}24.假設有兩個?帶表頭結點?的單鏈表H?A和HB，設計算法將?單鏈表HB?插入到單鏈?表HA的第?i(0<i≤表長)個結點前。【答案】voidfun(LNode?*ha,LNode?*hb,inti){for(p=hb;p->next;p=p->next);for(j=1,q=ha;j<i;j++)q=q->next;;p->next=q->next;q->next=hb->next；free(hb);}25.假設以帶頭?結點的單鏈?表表示有序?表，單鏈表的類?型定義如下?：typed?efstruc?tnode{DataT?ypedata;struc?tnode*next}LinkN?ode,*LinkL?ist;編寫算法，從有序表A?中刪除所有?和有序表B?中元素相同?的結點。【答案】(空)26.設二叉樹T?采用二叉鏈?表結構存儲?，數據元素為?字符類型。設計算法分?別求出二叉?鏈表中da?ta域為英?文字母和數?字字符的結點個數。【答案】intlette?r=0，digit?=0；/*全局變量*/voidalgo2?(BTNod?e*bt){if(bt){if(bt->data>=’A’&&bt->data<=’Z’||bt->data>=’a’&&bt->data<=’z’)lette?r++;if(bt->data>=’0’&&bt->data<=’9’)digit?++;algo2?(bt->lchil?d);algo2?(bt->rchil?d);}}27.假設以單鏈?表表示線性?表,單鏈表的類?型定義如下?:typed?efstruc?tnode{DataT?ypedata;struc?tnode*next;}LinkN?ode,*LinkL?ist;編寫算法,將一個頭指?針為hea?d且不帶頭?結點的單鏈?表改造為一?個含頭結點?且頭指針仍?為head?的單向循環?鏈表,并分析算法?的時間復雜?度。【答案】LinkL?istf34(LinkL?isthead){LinkL?istp,s;p=head;while?(p->next)p=p->next;s=(LinkL?ist)mallo?c(sizeo?f(LinkN?ode));s->next=head;p->next=s;head=s;retur?nhead;}時間復雜度?為:O(n)28.假設有向圖?以鄰接表方?式存儲，編寫一個算?法判別頂點?vi到頂點?vj是否存?在弧。【答案】intIsArc?s(ALgra?phG,inti,intj){/*判斷有向圖?G中頂點i?到頂點j是?否有弧,是那么返回1?,否那么返回0?*/p=G[i].first?arc;while?(p!=NULL){if(p->adjve?x==j)retur?n1;p=p->nexta?rc;}retur?n0;}29.設二叉樹T?采用二叉鏈?表結構存儲?，數據元素為?字符類型。設計算法求?出二叉鏈表?中data?域為大寫字?母的結點個?數。【答案】intcount?=0；/*count?為全局變量?*/voidalgo2?(BTNod?e*bt){if(bt){if(bt->data>=’A’&&b