數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題

1、 算法設(shè)計(jì)題1. 設(shè)二叉樹bt采用二叉鏈表結(jié)構(gòu)存儲(chǔ)。試設(shè)計(jì)一個(gè)算法輸出二叉樹中所有非葉子結(jié)點(diǎn)，并求出非葉子結(jié)點(diǎn)的個(gè)數(shù)?！敬鸢浮縤nt count=0;void algo2(BTNode *bt) if (bt) if(bt->lchild | bt->rchild) printf(bt->data); count+; algo2(bt->lchild); algo2(bt->rchild); 2. 閱讀下列函數(shù)arrange() int arrange(int a,int 1,int h,int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界 int i,j,t； i=1

2、；j=h； while(i<j) while(i<j && aj>=x)j-； while(i<j && aj>=x)i+； if(i<j) t=aj；aj=ai；ai=t； if(ai<x) return i； else return i1； （1）寫出該函數(shù)的功能； （2）寫一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組bn中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)?！敬鸢浮浚?）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素

3、并返回分界值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,n1,1)； q= arrange(b,0,p,0)； return qp； return pq； 3. 假設(shè)線性表以帶表頭結(jié)點(diǎn)的循環(huán)單鏈表表示。試設(shè)計(jì)一個(gè)算法，在線性表的第k個(gè)元素前插入新元素y。假如表長小于k，則插在表尾?！敬鸢浮縱oid algo1(LNode *h,i

4、nt k,ElemType y)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. 二叉排序樹的類型定義如下：typedef struct BSTNode 二叉排序樹的結(jié)點(diǎn)結(jié)構(gòu)int data; 數(shù)據(jù)域struct BSTNode *lchild, *rchild; 左、右孩子指針BSTNode,*BSTree;設(shè)計(jì)遞歸算法，統(tǒng)計(jì)一棵二叉排序樹T中

5、值小于a的結(jié)點(diǎn)個(gè)數(shù)。【答案】int f34(BSTree root) int count; BSTNode *p; p=root; if ( p && p->data<a) count+; f34(p->lchild); return count;5. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)算法求出二叉樹中離根最近的第一個(gè)葉子結(jié)點(diǎn)。（注：結(jié)點(diǎn)按從上往下，自左至右次序編號(hào)）【答案】BTNode * Firstleaf(BTNode *bt) InitQueue(Q); /初始化隊(duì)列Q if(bt) EnQueue(Q,bt); while(!EmptyQueue

6、(Q) DeQueue(Q,p); if(!p->lchild && !p->rchild) return p; if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); 6. 已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹被順序存儲(chǔ)在一維數(shù)組中，結(jié)點(diǎn)為字符類型,編寫算法打印出編號(hào)為k的結(jié)點(diǎn)的雙親和孩子結(jié)點(diǎn)。【答案】 int algo2(char bt,int n,int k) if (k<1|k>n) return 0;if( k=1) printf(“ %

7、c is a rootn”, bt1);else printf(“ %cs parent is %cn”, btk, btk/2); if(2*k<=n) printf(“ %cs lchild is %cn”, btk, bt2*k); else printf(“ %c is not lchildn”, btk); if(2*k+1<=n) printf(“ %cs rchild is %cn”, btk, bt2*k+1);else printf(“ %c is not rchildn”, btk);return 1; 7. 編寫算法，將非空單鏈表hb插入到單鏈表ha的第i(0

8、<i表長)個(gè)結(jié)點(diǎn)前?！敬鸢浮縤nt algo1(LNode *ha, LNode *hb,int i) 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已按完全二叉樹的形式存儲(chǔ)在順序表T中，試設(shè)計(jì)算法根據(jù)順序表T建立該二叉樹的二叉鏈表結(jié)構(gòu)。順序表T定義如下：struct tree int no; /* 結(jié)點(diǎn)按完全二叉樹的編號(hào)*/ ElEMTP data; /

9、* 數(shù)據(jù)域 */ TN; /* N為二叉樹T的結(jié)點(diǎn)數(shù)*/【答案】 BTNode *creat_tree(struct tree TN) BTNode *pMAX; t=NULL; for(i=0;i<N;i+) s=(BTNode *)malloc(sizeof(BTNode); s->data=Ti.data; s->lchild=s->rchild=NULL; m=Ti.no; pm=s; if(m=1) t=s; else j=m/2; if(m%2=0) pj->lchild=s; else pj->rchild=s; /slse /for retu

10、rn t; / creat_tree9. 編寫算法判斷帶表頭結(jié)點(diǎn)的單鏈表L是否是遞增的。若遞增返回1，否則返回0?！敬鸢浮縤nt algo1 (LNode *L) if(!L->next) return 1; p=L->next; while(p->next) if(p->data < p->next->data) p=p->next; else return 0; return 1;10. 假設(shè)一線性表由Fibonacci數(shù)列的前n（n3）項(xiàng)構(gòu)成，試以帶表頭結(jié)點(diǎn)的單鏈表作該線性表的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法建立該單鏈表，且將項(xiàng)數(shù)n存儲(chǔ)在表頭結(jié)點(diǎn)中。Fi

11、bonacci數(shù)列根據(jù)下式求得： 1 (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); 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 *)m

12、alloc(sizeof(Lnode); s->data=p->data+q->data; s->next=NULL; p=q;q=s; return h; 11. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲(chǔ)，數(shù)據(jù)元素為字符類型。設(shè)計(jì)算法將二叉鏈表中所有data域?yàn)樾懽帜傅慕Y(jié)點(diǎn)改為大寫字母?！敬鸢浮?void algo2(BTNode *bt) if (bt) if(bt->data>=a&& bt->data<=z) bt->data-=32; algo2(bt->lchild); algo2(bt->rchild);

13、12. 假設(shè)線性表以帶表頭結(jié)點(diǎn)的循環(huán)單鏈表表示。試設(shè)計(jì)一個(gè)算法，在線性表的第k個(gè)元素前插入新元素y。假如表長小于k，則插在表尾?！敬鸢浮縱oid Insertlist(LNode *h,int k,ElemType y) 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é)點(diǎn)的單鏈表，其結(jié)點(diǎn)的元素值以非遞減有序排列，編寫一個(gè)算法

14、在該鏈表中插入一個(gè)元素x，使得插入后的單鏈表仍有序。【答案】void algo1 (LNode *H, ElemTp x) 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. 二叉排序樹的類型定義如下：typedef struct BSTNode 二叉排序樹的結(jié)點(diǎn)結(jié)構(gòu)int data; 數(shù)據(jù)域struct BSTNode *lchild

15、, *rchild; 左、右孩子指針BSTNode,*BSTree;設(shè)計(jì)遞歸算法，統(tǒng)計(jì)一棵二叉排序樹T中值小于a的結(jié)點(diǎn)個(gè)數(shù)。【答案】int f34(BSTree root) int count; BSTNode *p; p=root; if ( p && p->data<a) count+; f34(p->lchild); return count;15. 有一帶表頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)的data域的類型為字符型，編寫一個(gè)算法刪除該鏈表中的數(shù)字字符?！敬鸢浮?void Del_digit (LNode *h) for(p=h;p->next;) q=p-

16、>next; if(q->data>=0&& q->data <=9) p->next=q->next; free(q); else p=q; 16. 利用棧的基本運(yùn)算，編寫一個(gè)算法，實(shí)現(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)存儲(chǔ)，數(shù)據(jù)元素為int型，試設(shè)計(jì)一個(gè)算法，若結(jié)點(diǎn)左孩子的

17、data域的值大于右孩子的data域的值，則交換其左、右子樹?！敬鸢浮縱oid algo2(bitreptr bt) bitreptr x; 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); 1

18、8. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)算法求出二叉樹的深度。【答案】int Deep(BTNode *bt) if (bt=NULL) return 0; left=Deep(bt->lchild); right=Deep(bt->rchild);return (left>right?left:right)+1; 19. 設(shè)給定的哈希表存儲(chǔ)空間為H（0M-1），哈希函數(shù)的構(gòu)造方法為“除留余數(shù)法”，處理沖突的方法為“線性探測法”，設(shè)計(jì)算法將元素e填入到哈希表中?！敬鸢浮縱oid hash-insert(hashTable h,int m,ElemType e) j=e%p

19、; if(hj!=NULL) hj=e; else do j=(j+1) %m;while(hj!=NULL );hj=e; 20. 對(duì)于給定的十進(jìn)制正整數(shù),打印出對(duì)應(yīng)的八進(jìn)制正整數(shù)。（利用棧）【答案】void DecToOct(int num)initStack(s); /初始化棧while(n) k=n%8;n=n/8; push(s,k); while(EmptyStack(s) /判斷棧是否為空 pop(s,k); printf(“%d”,k);21. 一個(gè)正讀和反讀都相同的字符序列稱為“回文”。例如“abcba”和“1221”是回文，而“abcde”不是回文。試寫一個(gè)算法，要求利用棧

20、的基本運(yùn)算識(shí)別一個(gè)以為結(jié)束符的字符序列是否是回文?！敬鸢浮縤nt Pair(char *str ) InitStack(s)； p=str for ( ; *p!=; p+ ) Push(s,*p); while(StackEmpty(s) Pop(s,y);if(y!=*str+ ) return 0; return 1; 22. 有一帶表頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)的元素值以非遞減有序排列，編寫一個(gè)算法刪除該鏈表中多余的元素值相同的結(jié)點(diǎn)(值相同的結(jié)點(diǎn)只保留一個(gè))?！敬鸢浮?void Delsame (LNode *h) if(h->next) for(p=h->next;p->

21、next;) q=p->next; if(p->data=q->data) p->next=q->next; free(q); else p=q; 23. 編寫一個(gè)算法，判斷帶表頭結(jié)點(diǎn)的單鏈表是否遞增有序?！敬鸢浮縤nt fun(LNode *h ) p=h->next; while(p->next) q=p->next ;if(q->data>p->data) return 0;p=q; return 1; 24. 假設(shè)有兩個(gè)帶表頭結(jié)點(diǎn)的單鏈表HA和HB，設(shè)計(jì)算法將單鏈表HB插入到單鏈表HA的第i(0<i表長)個(gè)結(jié)點(diǎn)前。

22、【答案】void fun(LNode *ha, LNode *hb,int i) 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)的單鏈表表示有序表，單鏈表的類型定義如下： typedef struct node DataType data; struct node *next LinkNode, *LinkList; 編寫算法，從有序表A中刪除所有和

23、有序表B中元素相同的結(jié)點(diǎn)?！敬鸢浮?空)26. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲(chǔ)，數(shù)據(jù)元素為字符類型。設(shè)計(jì)算法分別求出二叉鏈表中data域?yàn)橛⑽淖帜负蛿?shù)字字符的結(jié)點(diǎn)個(gè)數(shù)?！敬鸢浮縤nt letter=0，digit=0； /*全局變量*/ void algo2(BTNode *bt) if (bt) if(bt->data>=A&& bt->data<=Z| bt->data>=a&& bt->data<=z) letter +; if(bt->data>=0&& bt->data&

24、lt;=9) digit +; algo2(bt->lchild); algo2(bt->rchild); 27. 假設(shè)以單鏈表表示線性表,單鏈表的類型定義如下:typedef struct node DataType data; struct node *next; LinkNode, *LinkList; 編寫算法,將一個(gè)頭指針為head且不帶頭結(jié)點(diǎn)的單鏈表改造為一個(gè)含頭結(jié)點(diǎn)且頭指針仍為head的單向循環(huán)鏈表,并分析算法的時(shí)間復(fù)雜度?！敬鸢浮縇inkList f34(LinkList head) LinkList p,s; p=head; while (p->next)

25、p=p->next; s=(LinkList)malloc(sizeof(LinkNode); s->next=head; p->next=s; head=s; return head; 時(shí)間復(fù)雜度為:O(n)28. 假設(shè)有向圖以鄰接表方式存儲(chǔ)，編寫一個(gè)算法判別頂點(diǎn)vi到頂點(diǎn)vj是否存在弧。【答案】int IsArcs(ALgraph G,int i,int j) /* 判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有弧,是則返回1,否則返回0*/ p=Gi.firstarc; while (p!=NULL) if(p->adjvex =j) return 1; p=p->nextarc; return 0; 29. 設(shè)二叉樹T采用二叉鏈表結(jié)構(gòu)存儲(chǔ)，數(shù)據(jù)元素為字符類型。設(shè)計(jì)算法求出二叉鏈表中data域?yàn)榇髮懽帜傅慕Y(jié)點(diǎn)個(gè)數(shù)。【答案】int count=0；/* count為全局變量*/ void algo2(BTNode *bt) if (bt) if(bt->dat