數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題_第1頁
數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題_第2頁
數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題_第3頁
數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題_第4頁
數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題_第5頁
已閱讀5頁,還剩6頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

算法設(shè)計(jì)題?1.設(shè)二叉樹b?t采用二叉?鏈表結(jié)構(gòu)存?儲。試設(shè)計(jì)一個(gè)?算法輸出二?叉樹中所有?非葉子結(jié)點(diǎn)?,并求出非葉?子結(jié)點(diǎn)的個(gè)?數(shù)。【答案】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.閱讀以下函?數(shù)arra?nge()intarran?ge(inta[],int1,inth,intx){//1和h分別?為數(shù)據(jù)區(qū)的?下界和上界?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〕寫出該函數(shù)?的功能;〔2〕寫一個(gè)調(diào)用?上述函數(shù)實(shí)?現(xiàn)以下功能?的算法:對一整型數(shù)?組b[n]中的元素進(jìn)?行重新排列?,將所有負(fù)數(shù)?均調(diào)整到數(shù)?組的低下標(biāo)?端,將所有正數(shù)?均調(diào)整到數(shù)?組的高低標(biāo)?端,假設(shè)有零值,那么置于兩者?之間,并返回?cái)?shù)組?中零元素的?個(gè)數(shù)。【答案】〔1〕該函數(shù)的功?能是:調(diào)整整數(shù)數(shù)?組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.假設(shè)線性表?以帶表頭結(jié)?點(diǎn)的循環(huán)單?鏈表表示。試設(shè)計(jì)一個(gè)?算法,在線性表的?第k個(gè)元素?前插入新元?素y。假設(shè)表長小?于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{∥二叉排序樹?的結(jié)點(diǎn)結(jié)構(gòu)?intdata;∥數(shù)據(jù)域struc?tBSTNo?de*lchil?d,*rchil?d;∥左、右孩子指針?}BSTNo?de,*BSTre?e;設(shè)計(jì)遞歸算?法,統(tǒng)計(jì)一棵二?叉排序樹T?中值小于a?的結(jié)點(diǎn)個(gè)數(shù)?。【答案】intf34(BSTre?eroot){intcount?;BSTNo?de*p;p=root;if(p&&p->data<a)count?++;f34(p->lchil?d);retur?ncount?;}5.設(shè)二叉樹T?采用二叉鏈?表結(jié)構(gòu)存儲?,試設(shè)計(jì)算法?求出二叉樹?中離根最近?的第一個(gè)葉?子結(jié)點(diǎn)。〔注:結(jié)點(diǎn)按從上?往下,自左至右次序編?號〕【答案】BTNod?e*First?leaf(BTNod?e*bt){InitQ?ueue(Q);//初始化隊(duì)列?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個(gè)結(jié)點(diǎn)?的完全二叉?樹被順序存?儲在一維數(shù)?組中,結(jié)點(diǎn)為字符?類型,編寫算法打?印出編號為?k的結(jié)點(diǎn)的?雙親和孩子?結(jié)點(diǎn)。【答案】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≤表長)個(gè)結(jié)點(diǎn)前。【答案】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.設(shè)二叉樹T?已按完全二?叉樹的形式?存儲在順序?表T中,試設(shè)計(jì)算法?根據(jù)順序表?T建立該二?叉樹的二叉?鏈表結(jié)構(gòu)。順序表T定?義如下:struc?ttree{intno;/*結(jié)點(diǎn)按完全?二叉樹的編?號*/ElEMT?Pdata;/*數(shù)據(jù)域*/}T[N];/*N為二叉樹?T的結(jié)點(diǎn)數(shù)?*/【答案】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.編寫算法判?斷帶表頭結(jié)?點(diǎn)的單鏈表?L是否是遞?增的。假設(shè)遞增返回?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.假設(shè)一線性?表由Fib?onacc?i數(shù)列的前?n〔n≥3〕項(xiàng)構(gòu)成,試以帶表頭?結(jié)點(diǎn)的單鏈?表作該線性?表的存儲結(jié)?構(gòu),設(shè)計(jì)算法建?立該單鏈表?,且將項(xiàng)數(shù)n?存儲在表頭?結(jié)點(diǎn)中。Fibon?acci數(shù)?列根據(jù)下式?求得: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.設(shè)二叉樹T?采用二叉鏈?表結(jié)構(gòu)存儲?,數(shù)據(jù)元素為?字符類型。設(shè)計(jì)算法將?二叉鏈表中?所有dat?a域?yàn)樾?字母的結(jié)點(diǎn)?改為大寫字母。【答案】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.假設(shè)線性表?以帶表頭結(jié)?點(diǎn)的循環(huán)單?鏈表表示。試設(shè)計(jì)一個(gè)?算法,在線性表的?第k個(gè)元素?前插入新元?素y。假設(shè)表長小?于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.有一帶表頭?結(jié)點(diǎn)的單鏈?表,其結(jié)點(diǎn)的元?素值以非遞?減有序排列?,編寫一個(gè)算?法在該鏈表?中插入一個(gè)?元素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{∥二叉排序樹?的結(jié)點(diǎn)結(jié)構(gòu)?intdata;∥數(shù)據(jù)域struc?tBSTNo?de*lchil?d,*rchil?d;∥左、右孩子指針?}BSTNo?de,*BSTre?e;設(shè)計(jì)遞歸算?法,統(tǒng)計(jì)一棵二?叉排序樹T?中值小于a?的結(jié)點(diǎn)個(gè)數(shù)?。【答案】intf34(BSTre?eroot){intcount?;BSTNo?de*p;p=root;if(p&&p->data<a)count?++;f34(p->lchil?d);retur?ncount?;}15.有一帶表頭?結(jié)點(diǎn)的單鏈?表,其結(jié)點(diǎn)的d?ata域的?類型為字符?型,編寫一個(gè)算?法刪除該鏈?表中的數(shù)字?字符。【答案】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.利用棧的基?本運(yùn)算,編寫一個(gè)算?法,實(shí)現(xiàn)將整數(shù)?轉(zhuǎn)換成二進(jìn)?制數(shù)輸出。【答案】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.設(shè)二叉樹T?采用二叉鏈?表結(jié)構(gòu)存儲?,數(shù)據(jù)元素為?int型,試設(shè)計(jì)一個(gè)?算法,假設(shè)結(jié)點(diǎn)左孩?子的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.設(shè)二叉樹T?采用二叉鏈?表結(jié)構(gòu)存儲?,試設(shè)計(jì)算法?求出二叉樹?的深度。【答案】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.設(shè)給定的哈?希表存儲空?間為H〔0~M-1〕,哈希函數(shù)的?構(gòu)造方法為?“除留余數(shù)法?〞,處理沖突的?方法為“線性探測法?〞,設(shè)計(jì)算法將?元素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.對于給定的?十進(jìn)制正整?數(shù),打印出對應(yīng)?的八進(jìn)制正?整數(shù)。〔利用棧〕【答案】voidDecTo?Oct(intnum){ initS?tack(s); //初始化棧 while?(n){k=n%8;n=n/8;push(s,k);}while?(Empty?Stack?(s))//判斷棧是否?為空{(diào)pop(s,k);print?f(“%d〞,k);}}21.一個(gè)正讀和?反讀都相同?的字符序列?稱為“回文〞。例如“abcba?〞和“1221〞是回文,而“abcde?〞不是回文。試寫一個(gè)算?法,要求利用棧?的根本運(yùn)算?識別一個(gè)以?@為結(jié)束符的?字符序列是?否是回文。【答案】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.有一帶表頭?結(jié)點(diǎn)的單鏈?表,其結(jié)點(diǎn)的元?素值以非遞?減有序排列?,編寫一個(gè)算?法刪除該鏈?表中多余的?元素值相同?的結(jié)點(diǎn)(值相同的結(jié)?點(diǎn)只保存一?個(gè))。【答案】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.編寫一個(gè)算?法,判斷帶表頭?結(jié)點(diǎn)的單鏈?表是否遞增?有序。【答案】intfun(LNode?*h){p=h->next;while?(p->next){q=p->next;if(q->data>p->data)retur?n0;p=q;}retur?n1;}24.假設(shè)有兩個(gè)?帶表頭結(jié)點(diǎn)?的單鏈表H?A和HB,設(shè)計(jì)算法將?單鏈表HB?插入到單鏈?表HA的第?i(0<i≤表長)個(gè)結(jié)點(diǎn)前。【答案】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.假設(shè)以帶頭?結(jié)點(diǎn)的單鏈?表表示有序?表,單鏈表的類?型定義如下?:typed?efstruc?tnode{DataT?ypedata;struc?tnode*next}LinkN?ode,*LinkL?ist;編寫算法,從有序表A?中刪除所有?和有序表B?中元素相同?的結(jié)點(diǎn)。【答案】(空)26.設(shè)二叉樹T?采用二叉鏈?表結(jié)構(gòu)存儲?,數(shù)據(jù)元素為?字符類型。設(shè)計(jì)算法分?別求出二叉?鏈表中da?ta域?yàn)橛?文字母和數(shù)?字字符的結(jié)點(diǎn)個(gè)數(shù)。【答案】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.假設(shè)以單鏈?表表示線性?表,單鏈表的類?型定義如下?:typed?efstruc?tnode{DataT?ypedata;struc?tnode*next;}LinkN?ode,*LinkL?ist;編寫算法,將一個(gè)頭指?針為hea?d且不帶頭?結(jié)點(diǎn)的單鏈?表改造為一?個(gè)含頭結(jié)點(diǎn)?且頭指針仍?為head?的單向循環(huán)?鏈表,并分析算法?的時(shí)間復(fù)雜?度。【答案】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;}時(shí)間復(fù)雜度?為:O(n)28.假設(shè)有向圖?以鄰接表方?式存儲,編寫一個(gè)算?法判別頂點(diǎn)?vi到頂點(diǎn)?vj是否存?在弧。【答案】intIsArc?s(ALgra?phG,inti,intj){/*判斷有向圖?G中頂點(diǎn)i?到頂點(diǎn)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.設(shè)二叉樹T?采用二叉鏈?表結(jié)構(gòu)存儲?,數(shù)據(jù)元素為?字符類型。設(shè)計(jì)算法求?出二叉鏈表?中data?域?yàn)榇髮懽?母的結(jié)點(diǎn)個(gè)?數(shù)。【答案】intcount?=0;/*count?為全局變量?*/voidalgo2?(BTNod?e*bt){if(bt){if(bt->data>=’A’&&b

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論