(完整)數(shù)據(jù)結(jié)構(gòu)算法設計題

(完整)數(shù)據(jù)結(jié)構(gòu)算法設計題(完整)數(shù)據(jù)結(jié)構(gòu)算法設計題萬維試題庫系統(tǒng)第14頁(完整)數(shù)據(jù)結(jié)構(gòu)算法設計題一、算法設計題1。設二叉樹bt采用二叉鏈表結(jié)構(gòu)存儲。試設計一個算法輸出二叉樹中所有非葉子結(jié)點,并求出非葉子結(jié)點的個數(shù)?！敬鸢浮縤ntcount=0；voidalgo2(BTNode*bt)｛if(bt)｛if（bt->lchild||bt—〉rchild)｛printf（bt—>data);count++；}algo2（bt->lchild）；algo2（bt—〉rchild）;｝}2。閱讀下列函數(shù)arrange(）intarrange（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)returni;elsereturni－1;}（1）寫出該函數(shù)的功能；（2）寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法:對一整型數(shù)組b［n］中的元素進行重新排列，將所有負數(shù)均調(diào)整到數(shù)組的低下標端，將所有正數(shù)均調(diào)整到數(shù)組的高下標端，若有零值，則置于兩者之間,并返回數(shù)組中零元素的個數(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=arrange（b，0，n－1,0）；p=arrange(b,0,n－1，1）；q=arrange（b,p+1，n－1，1）；q=arrange（b，0,p,0)；returnq－p;returnp－q;｝｝3。假設線性表以帶表頭結(jié)點的循環(huán)單鏈表表示。試設計一個算法，在線性表的第k個元素前插入新元素y。假如表長小于k,則插在表尾?！敬鸢浮縱oidalgo1(LNode＊h，intk，ElemTypey）{q=h;P=h—〉next;j=1;while（p！=h＆&j<k）{q=p；p=p—〉next;j++;｝s=(LNode＊）malloc(sizeof（Lnode));s-〉data=y;q-〉next=s；s—〉next=q；｝4.二叉排序樹的類型定義如下：typedefstructBSTNode{∥二叉排序樹的結(jié)點結(jié)構(gòu)intdata；∥數(shù)據(jù)域structBSTNode＊lchild，＊rchild；∥左、右孩子指針｝BSTNode,＊BSTree;設計遞歸算法，統(tǒng)計一棵二叉排序樹T中值小于a的結(jié)點個數(shù)。【答案】intf34（BSTreeroot){intcount;BSTNode*p；p=root;if（p＆&p->data〈a）count++；f34（p—>lchild);returncount;}5。設二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，試設計算法求出二叉樹中離根最近的第一個葉子結(jié)點。（注：結(jié)點按從上往下，自左至右次序編號）【答案】BTNode*Firstleaf（BTNode*bt)｛InitQueue(Q）;//初始化隊列Qif(bt){EnQueue（Q，bt);;while(！EmptyQueue(Q))｛DeQueue（Q,p);if(！p—>lchild＆&!p->rchild）returnp;if(p-〉lchild）EnQueue(Q，p->lchild）;if（p->rchild）EnQueue(Q，p—〉rchild）;｝}｝6。已知一棵具有n個結(jié)點的完全二叉樹被順序存儲在一維數(shù)組中，結(jié)點為字符類型，編寫算法打印出編號為k的結(jié)點的雙親和孩子結(jié)點。【答案】intalgo2（charbt[]，intn，intk）｛if(k〈1||k〉n)return0；if(k==1）printf(“%cisaroot\n”,bt［1])；elseprintf(“%c’sparentis％c\n”，bt[k］，bt［k/2]）；if(2＊k<=n）printf（“%c'slchildis％c\n”，bt[k],bt[2*k］）；elseprintf（“％cisnotlchild\n",bt［k］)）；if（2*k+1〈=n）printf（“％c'srchildis%c\n”，bt［k]，bt[2＊k+1］）；elseprintf(“%cisnotrchild\n"，bt[k])）;return1;}7.編寫算法,將非空單鏈表hb插入到單鏈表ha的第i(0〈i≤表長)個結(jié)點前?！敬鸢浮縤ntalgo1(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中，試設計算法根據(jù)順序表T建立該二叉樹的二叉鏈表結(jié)構(gòu).順序表T定義如下:structtree｛intno；/*結(jié)點按完全二叉樹的編號＊/ElEMTPdata;/＊數(shù)據(jù)域*/}T[N］；/＊N為二叉樹T的結(jié)點數(shù)*/【答案】BTNode＊creat_tree（structtreeT［N]）｛BTNode＊p[MAX]；t=NULL；for(i=0;i〈N；i++){s=（BTNode*)malloc（sizeof（BTNode)）；s->data=T[i］.data；s—>lchild=s-〉rchild=NULL；m=T［i］.no；p［m］=s; if（m==1)t=s; else｛j=m/2； if（m%2==0）p［j]—>lchild=s;elsep[j]—>rchild=s;｝//slse}//forreturnt；}//creat_tree9。編寫算法判斷帶表頭結(jié)點的單鏈表L是否是遞增的。若遞增返回1，否則返回0。【答案】intalgo1（LNode＊L)｛if(!L->next)return1；p=L-〉next;while(p—>next)｛if（p-〉data<p->next->data)p=p—>next；elsereturn0;｝return1;}10。假設一線性表由Fibonacci數(shù)列的前n（n≥3）項構(gòu)成,試以帶表頭結(jié)點的單鏈表作該線性表的存儲結(jié)構(gòu)，設計算法建立該單鏈表,且將項數(shù)n存儲在表頭結(jié)點中。Fibonacci數(shù)列根據(jù)下式求得:1（n=1）f(n)=1(n=2）f（n-2）+f（n-1)（n≥3)【答案】LNode＊Creatlist(LNode*h，intn){h=（LNode＊）malloc（sizeof(Lnode));h—〉data=n；h-〉next=p=(LNode*）malloc（sizeof（Lnode））;p—>next=q=(LNode＊）malloc（sizeof（Lnode））;p->data=q->data=1；for(i=3；i<=n；i++){q->next=s=(LNode*)malloc（sizeof(Lnode));s—〉data=p—>data+q-〉data；s—>next=NULL；p=q；q=s；｝returnh；｝11.設二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為字符類型。設計算法將二叉鏈表中所有data域為小寫字母的結(jié)點改為大寫字母。【答案】voidalgo2（BTNode*bt）｛if(bt）｛if（bt->data>=’a'＆＆bt-〉data〈=’z')bt->data—=32;algo2(bt—〉lchild)；algo2（bt-〉rchild)；｝｝12。假設線性表以帶表頭結(jié)點的循環(huán)單鏈表表示。試設計一個算法，在線性表的第k個元素前插入新元素y。假如表長小于k，則插在表尾?！敬鸢浮縱oidInsertlist(LNode*h，intk，ElemTypey）{q=h；P=h->next;j=1；while（p！=h＆＆j〈k){q=p;p=p—〉next;j++；}s=(LNode＊）malloc(sizeof（Lnode））;s—>data=y;q—〉next=s;s->next=q;｝13.有一帶表頭結(jié)點的單鏈表，其結(jié)點的元素值以非遞減有序排列，編寫一個算法在該鏈表中插入一個元素x,使得插入后的單鏈表仍有序?！敬鸢浮縱oidalgo1(LNode*H，ElemTpx）{s=(LNode＊）malloc(sizeof(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。二叉排序樹的類型定義如下：typedefstructBSTNode｛∥二叉排序樹的結(jié)點結(jié)構(gòu)intdata；∥數(shù)據(jù)域structBSTNode*lchild，＊rchild；∥左、右孩子指針｝BSTNode，＊BSTree;設計遞歸算法,統(tǒng)計一棵二叉排序樹T中值小于a的結(jié)點個數(shù)。【答案】intf34(BSTreeroot）｛intcount；BSTNode＊p；p=root;if(p&&p—〉data<a)count++;f34（p—〉lchild）；returncount；｝15。有一帶表頭結(jié)點的單鏈表，其結(jié)點的data域的類型為字符型，編寫一個算法刪除該鏈表中的數(shù)字字符.【答案】voidDel_digit(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.利用棧的基本運算，編寫一個算法，實現(xiàn)將整數(shù)轉(zhuǎn)換成二進制數(shù)輸出。【答案】voidreturnDtoO（intnum）{ initStack（s）； while(n）{k=n%2;n=n/2;push（s,k)；}while(EmptyStack(s)）{pop(s,k);printf(“％d”，k);}}17。設二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為int型，試設計一個算法，若結(jié)點左孩子的data域的值大于右孩子的data域的值,則交換其左、右子樹?！敬鸢浮縱oidalgo2（bitreptrbt)｛bitreptrx;if（bt){if((bt->lchild＆&bt—〉rchild)&＆(bt—〉lchild—〉data〉bt—〉rchild->data））{x=bt—>lchild；bt—>lchild=bt—〉rchild；bt-〉rchild=x；｝algo2(bt->lchild);algo2(bt->rchild);}}18.設二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，試設計算法求出二叉樹的深度。【答案】intDeep（BTNode＊bt)｛if（bt==NULL）return0；left=Deep（bt->lchild）;right=Deep（bt-〉rchild）;return(left>right？left：right)+1；｝19。設給定的哈希表存儲空間為H（0～M—1）,哈希函數(shù)的構(gòu)造方法為“除留余數(shù)法”，處理沖突的方法為“線性探測法”，設計算法將元素e填入到哈希表中?！敬鸢浮縱oidhash—insert（hashTableh[],intm，ElemTypee)｛j=e％p;if(h［j］!=NULL)h［j]=e；else｛do｛j=(j+1)%m；}while(h［j］!=NULL)；h[j］=e;}｝20.對于給定的十進制正整數(shù),打印出對應的八進制正整數(shù)。（利用棧）【答案】voidDecToOct（intnum）｛ initStack（s）； //初始化棧 while(n){k=n%8；n=n/8；push(s，k);}while（EmptyStack（s））//判斷棧是否為空｛pop(s，k）；printf（“％d”,k)；}｝21.一個正讀和反讀都相同的字符序列稱為“回文"。例如“abcba”和“1221”是回文，而“abcde"不是回文。試寫一個算法,要求利用棧的基本運算識別一個以@為結(jié)束符的字符序列是否是回文?！敬鸢浮縤ntPair(char＊str){InitStack(s）；p=strfor（;*p！='@’；p++）Push(s,*p);while（StackEmpty（s）)｛Pop（s,y);if(y！=*str++）return0;}return1；}22。有一帶表頭結(jié)點的單鏈表,其結(jié)點的元素值以非遞減有序排列，編寫一個算法刪除該鏈表中多余的元素值相同的結(jié)點（值相同的結(jié)點只保留一個)?！敬鸢浮縱oidDelsame(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.編寫一個算法，判斷帶表頭結(jié)點的單鏈表是否遞增有序?！敬鸢浮縤ntfun(LNode*h)｛p=h-〉next；while（p-〉next）｛q=p->next;if（q—>data>p—>data）return0;p=q；}return1；｝24。假設有兩個帶表頭結(jié)點的單鏈表HA和HB,設計算法將單鏈表HB插入到單鏈表HA的第i（0〈i≤表長）個結(jié)點前?！敬鸢浮縱oidfun（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。假設以帶頭結(jié)點的單鏈表表示有序表，單鏈表的類型定義如下：typedefstructnode｛DataTypedata;structnode*next}LinkNode,*LinkList；編寫算法,從有序表A中刪除所有和有序表B中元素相同的結(jié)點.【答案】（空)26.設二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為字符類型。設計算法分別求出二叉鏈表中data域為英文字母和數(shù)字字符的結(jié)點個數(shù).【答案】intletter=0，digit=0；/＊全局變量*/voidalgo2(BTNode＊bt）｛if(bt）｛if(bt-〉data>='A'&＆bt->data〈=’Z’|｜bt—〉data>=’a’&＆bt->data<=’z’)letter++;if（bt->data〉=’0'＆&bt-〉data〈='9’)digit++；algo2(bt—〉lchild）;algo2(bt-〉rchild);｝｝27.假設以單鏈表表示線性表，單鏈表的類型定義如下:typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList；編寫算法,將一個頭指針為head且不帶頭結(jié)點的單鏈表改造為一個含頭結(jié)點且頭指針仍為head的單向循環(huán)鏈表,并分析算法的時間復雜度。【答案】LinkListf34（LinkListhead）｛LinkListp，s；p=head；while(p->next)p=p-〉next;s=（LinkList)malloc（sizeof（LinkNode));s-〉next=head；p—>next=s；head=s;returnhead；｝時間復雜度為:O(n）28。假設有向圖以鄰接表方式存儲,編寫一個算法判別頂點vi到頂點vj是否存在弧?！敬鸢浮縤ntIsArcs(ALgraphG,inti,intj){/＊判斷有向圖G中頂點i到頂點j是否有弧,是則返回1，否則返回0*/p=G［i］.firstarc;while(p！=NULL){if(p—〉adjvex==j)return1;p=p-〉nextarc;｝return0；｝29.設二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為字符類型。設計算法求出二叉鏈表中data域為大寫字母的結(jié)點個數(shù)?！敬鸢浮縤ntcount=0；/*count為全局變量*/voidalgo2(BTNode*bt){if(bt）{if(bt->data〉=