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

1、(完整)數(shù)據(jù)結(jié)構(gòu)算法設(shè)計題(完整)數(shù)據(jù)結(jié)構(gòu)算法設(shè)計題第 PAGE 15第15頁萬維試題庫系統(tǒng)一、算法設(shè)計題1。 設(shè)二叉樹bt的個數(shù)。【答案】int count=0；void algo2(BTNode *bt)if (bt)if（bt-lchild | btrchild) printf（btdata);count+；algo2（bt-lchild； algo2（btrchild）;2。 閱讀下列函數(shù)arrange(）int arrange（int a,int 1，int h,int x）/1和h分別為數(shù)據(jù)區(qū)的下界和上界int i，j，t；i=1；j=h； while(iwhile（i=x）i+;

2、 if(ij) t=j；aj=ai；ai=；if(aix) return else return i1;寫出該函數(shù)的功能；寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法:對一整型數(shù)組bn中的元素進(jìn)行重新排列，將所有負(fù)數(shù)數(shù)組中零元素的個數(shù)?！敬鸢浮?1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有x的元素均落在a1。.i上， 使所有x的元素均落在ai1.。h上。(2）int f(int b，int n)或int f（int b，int n）int p,q；int p，q；p=arrange（b，0，n1,0；p=arrange(b,0,n1，1；q= arrange（b,p+1，1，1；q

3、=arrange（b，0,p,0)；return qp;return pq;3。 假設(shè)線性表以帶表頭結(jié)點的循環(huán)單鏈表表示。試設(shè)計一個算法，在線性表的第k個元素前插入新元素y。假如表長小于k,則插在表尾?！敬鸢浮縱oid algo1(LNode h，int k，ElemType y） q=h; P=hnext; j=1;while（ p！=h & jdata a）count+； f34（plchild);return count;5。 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，試設(shè)計算法求出二叉樹中離根最近的第一個葉子結(jié)點（從上往下，自左至右次序編號）【答案】BTNode * Firstleaf（BTNo

4、de *bt) InitQueue(Q）; /初始化隊列Q if(bt)EnQueue（Q，bt); while(！EmptyQueue(Q) DeQueue（Q,p);if(！plchild & !p-rchild） return if(p- lchild） EnQueue(Q，p-lchild）; if（p-rchild） EnQueue(Q，prchild）;6。 已知一棵具有n個結(jié)點的完全二叉樹被順序存儲在一維數(shù)組中，結(jié)點為字符類型，編寫算法打印出編號為k的結(jié)點的雙親和孩子結(jié)點?！敬鸢浮縤nt algo2（charbt，int n，int k if (k1|kn) return 0；i

5、f( k=1） printf(“ %c is a rootn”,bt1)；else printf(“%csparent iscn”， btk，btk/2； if(2knext; p=p- next)； for（j=1，q=ha；ji; j+)q=qnext； p-next=qnext;qnext=hbnextfree（hb；8。 設(shè)二叉樹T已按完全二叉樹的形式存儲在順序表T中，試設(shè)計算法根據(jù)順序表T建立該二叉樹的二叉鏈表結(jié)構(gòu).順序表T定義如下:struct treeintno；/*結(jié)點按完全二叉樹的編號/ ElEMTP data;/ 數(shù)據(jù)域 */TN；/N為二叉樹T的結(jié)點數(shù)*/【答案】BTNo

6、de creat_tree（struct tree TN） BTNode pMAX； t=NULL；for(i=0;iN；i+)s=BTNode c（f（) s-data=Ti.data；slchild=s-rchild=NULL； m=Ti.no；pm=s; if（m=1) t=s;else j=m/2；if（m%2=0） pjlchild=s; else pjrchild=s;/slse/for return t；/ creat_tree9。 編寫算法判斷帶表頭結(jié)點的單鏈表L是否是遞增的。若遞增返回1，否則返回0。【答案】intalgo1 （LNode L)if(!L-next) retu

7、rn 1； p=L- next; while(pnext)if（p-data next-data) p=pnext； else return 0;return 1;10。 假設(shè)一線性表由Fibonacci數(shù)列的前nFibonacci1（n=1）f(n)= 1(n=2）f（n-2）+f（n-1) （n3)【答案】LNode Creatlist(LNode *h，int n) h=（LNode ）malloc（sizeof(Lnode); hdata=n；h-next=p=(LNode*）malloc（sizeof（Lnode）; pnext=q=(LNode ）c（fe） p-data= q-d

8、ata=1for(i=3；inext=s=(LNode *)malloc （sizeof(Lnode); sdata=pdata+q-data； snext=NULL； p=q；q=s； returnh；11. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為字符類型。設(shè)計算法將二叉鏈表中所有data域為小寫字母的結(jié)點改為大寫字母?！敬鸢浮縱oidalgo2BTNodet if(btif（bt-data=a bt-data=z)bt-data=32;algo2(btlchild)； algo2（bt-rchild)；12。 假設(shè)線性表以帶表頭結(jié)點的循環(huán)單鏈表表示。試設(shè)計一個算法，在線性表的第k個元素

9、前插入新元素y。假如表長小于k，則插在表尾。【答案】void Insertlist(LNode *h，int k，ElemType y）q=h； P=h-next; j=1； while（p！=hjq=p;p=pnext;j+；s=(LNode ）fe sdata=y;qnext=s; s-next=q;13. x,使得插入后的單鏈表仍有序?！敬鸢浮縱oid algo1 (LNode *H， ElemTp x）s=(LNode ） malloc (sizeof(LNode）); s-data=x;q=H； p=H-next;while ( p pdata=x ）q=p; p=pnext;sne

10、xt=p; q-next=s；14。 二叉排序樹的類型定義如下：typedef struct BSTNode 二叉排序樹的結(jié)點結(jié)intdata；數(shù)據(jù)域struct BSTNode *lchild， rchild； 左、右孩子指針BSTNode，BSTree;設(shè)計遞歸算法,統(tǒng)計一棵二叉排序樹T中值小于a的結(jié)點個數(shù)?！敬鸢浮縤nt f34(BSTree root）int count； BSTNode p； p=root;if ( p & p datanext;if(q-data=0& q-data =9）p-next=qnext；free（q）;elsep=q;16. 利用棧的基本運算，編寫一個算

11、法，實現(xiàn)將整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)輸出?！敬鸢浮縱oid returnDtoO（int num）initStack（s； while(n） k=n%2;n=n/2;push（s,k)；while(EmptyStack(s)） pop(s,k);printf(“d”，k);17。 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為int型，試設(shè)計一個算法，若結(jié)點左孩子的data域的值大于右孩子的data域的值,則交換其左、右子樹?！敬鸢浮縱oid algo2（bitreptr bt) bitreptr x;if （bt)if (bt-lchild & btrchild) & (btlchild data bt

12、rchild-data） ） x= btlchild ；btlchild= btrchild； bt-rchild=x；algo2(bt-lchild); algo2(bt-rchild);18. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲，試設(shè)計算法求出二叉樹的深度。【答案】int Deep（BTNode bt)if （bt=NULL） return 0； left=Deep（bt-lchild）; right=Deep（bt-rchild）;return (leftright？left：right)+1；19。 設(shè)給定的哈希表存儲空間為H（0M1）,哈希函數(shù)的構(gòu)造方法為“除留余數(shù)法”，處理沖突的方法為

13、“線性探測法”，設(shè)計算法將元素e填入到哈希表中?！敬鸢浮縱oid hashinsert（hashTable h,int m，ElemType e) j=ep;if(hj!=NULL) hj=e； elsedo j=(j+1) %m；while(hj!=NULL )； hj=e;（利用棧）【答案】void DecToOct（int num）initStack（s；/ while(n) k=n%8；n=n/8；push(s，k);while（EmptyStack（s）/判斷棧是否為空 pop(sk； printf（“d”,k)；“abcba”和“1221”“abcde為結(jié)束符的字符序列是否是回文。

14、【答案】int Pair(char str ) InitStack(s； p=strfor （ ; *p！=； p+ ） Push(s,*p);while（StackEmpty（s）) Pop（s,y);if(y！=*str+ ） return 0;return 1；22。 值相同的結(jié)點（【答案】void Delsame (LNode *h)if(h-next) for（p=ht；t） q=pnext；if(pdata=q-a p-next=qnext;free(q);else p=q;23. 編寫一個算法，判斷帶表頭結(jié)點的單鏈表是否遞增有序。【答案】int fun(LNode *h ) p=

15、h-next； while（p- q=p-next ; if（qdatapdata）return p=q；return 1；24。 假設(shè)有兩個帶表頭結(jié)點的單鏈表HA和HBHBHA的第i（0i表長）結(jié)點前。【答案】void fun（LNode *ha, LNode *hb,int i) for(p=hb；p-next； p=pnext）; for(j=1，q=ha；ji; j+）q=qnext; ； p-next=qnext;q-next=hb-nextfree（hb);25。 typedef struct nodeDataType data; struct node *nextLinkNode

16、, *LinkList；編寫算法,從有序表A中刪除所有和有序表B中元素相同的結(jié)點.【答案】（空)設(shè)二叉樹Tdata字母和數(shù)字字符的結(jié)點個數(shù).【答案】int letter=0，digit=0；/全局變量void algo2(BTNode btif (btif(btdata=A& =Z| btdata=a& bt-datadata=0& bt-data=9) digit +；algo2(btlchild）; algo2(bt-rchild);typedef struct node DataType data; struct node LinkNode, *LinkList；編寫算法,將一個頭指針為

17、head且不帶頭結(jié)點的單鏈表改造為一個含頭結(jié)點且頭指針仍為head的單向循環(huán)鏈表,并分析算法的時間復(fù)雜度?！敬鸢浮縇inkList f34（LinkList head）LinkList p，s； p=head；while (p-next)p=p- next; s=（LinkList)malloc（sizeof（LinkNode); s-next=head；pnext=s； head=s; return head；時間復(fù)雜度為:O(n）28。 假設(shè)有向圖以鄰接表方式存儲,編寫一個算法判別頂點v 到頂點v 是否存在弧。ij【答案】int IsArcs(ALgraph G,int i,int j)

18、/ 判斷有向圖G中頂點i到頂點j是否有弧,是則返回1，否則返回0*/ p=Gi.firstarc;while (p！=NULL) if(padjvex =j)return 1; p=p-nextarc;return 0；設(shè)二叉樹Tdata的結(jié)點個數(shù)。【答案】int count=0；/* count為全局變量*/void algo2(BTNode *bt) if (bt）if(bt-data=A&btdatarchild）;typedef struct dunodechar data;struct dunode prior， *next;DuNode；現(xiàn)用該鏈表存放字符串，編寫一個算法 ,判斷該字符串是否中心對稱關(guān)系。例如字符串“xyzzyx”和“xyzyx” 都是中心對稱的?！敬鸢浮縤nt fun(DuNode *h ) p=hnext；q=hprior； while(p!=q & pprior!=q)if（q-data=p-data) r else return 0；return