1、算法設(shè)計題1. 設(shè)二叉樹bt采用二叉鏈表結(jié)構(gòu)存儲。試設(shè)計一個算法輸出二叉樹中所有非葉子結(jié)點，并求出非葉子結(jié)點的個數(shù)。【答案】int 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；j=h； while(ij) while

2、(i=x)j-； while(i=x)i+； if(ij) t=aj；aj=ai；ai=t； if(ainext; j=1;while( p!=h & jnext; j+;s=(lnode *)malloc(sizeof(lnode);s-data=y;q-next=s;s-next=q; 4. 二叉排序樹的類型定義如下：typedef struct bstnode 二叉排序樹的結(jié)點結(jié)構(gòu)int data; 數(shù)據(jù)域struct bstnode *lchild, *rchild; 左、右孩子指針bstnode,*bstree;設(shè)計遞歸算法，統(tǒng)計一棵二叉排序樹t中值小于a的結(jié)點個數(shù)?！敬鸢浮縤nt

3、f34(bstree root) int count; bstnode *p; p=root; if ( p & p-datalchild); return count;5. 設(shè)二叉樹t采用二叉鏈表結(jié)構(gòu)存儲，試設(shè)計算法求出二叉樹中離根最近的第一個葉子結(jié)點。（注：結(jié)點按從上往下，自左至右次序編號）【答案】btnode * firstleaf(btnode *bt) initqueue(q); /初始化隊列q if(bt) enqueue(q,bt); while(!emptyqueue(q) dequeue(q,p); if(!p-lchild & !p-rchild) return p; if

4、(p-lchild) enqueue(q,p-lchild); if(p-rchild) enqueue(q,p-rchild); 6. 已知一棵具有n個結(jié)點的完全二叉樹被順序存儲在一維數(shù)組中，結(jié)點為字符類型,編寫算法打印出編號為k的結(jié)點的雙親和孩子結(jié)點?！敬鸢浮?int algo2(char bt,int n,int k) if (kn) return 0;if( k=1) printf(“ %c is a rootn”, bt1);else printf(“ %cs parent is %cn”, btk, btk/2); if(2*k=n) printf(“ %cs lchild is

5、%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(0next; p=p-next); for(j=1,q=ha;jnext; p-next=q-next; q-next=hb-next ； free(hb); 8. 設(shè)二叉樹t已按完全二叉樹的形式存儲在順序表t中，試設(shè)

6、計算法根據(jù)順序表t建立該二叉樹的二叉鏈表結(jié)構(gòu)。順序表t定義如下：struct tree int no; /* 結(jié)點按完全二叉樹的編號*/ elemtp data; /* 數(shù)據(jù)域 */ tn; /* n為二叉樹t的結(jié)點數(shù)*/【答案】 btnode *creat_tree(struct tree tn) btnode *pmax; t=null; for(i=0;idata=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;

7、 /slse /for return t; / creat_tree9. 編寫算法判斷帶表頭結(jié)點的單鏈表l是否是遞增的。若遞增返回1，否則返回0?！敬鸢浮縤nt algo1 (lnode *l) if(!l-next) return 1; p=l-next; while(p-next) if(p-data next-data) p=p-next; else return 0; return 1;10. 假設(shè)一線性表由fibonacci數(shù)列的前n（n3）項構(gòu)成，試以帶表頭結(jié)點的單鏈表作該線性表的存儲結(jié)構(gòu)，設(shè)計算法建立該單鏈表，且將項數(shù)n存儲在表頭結(jié)點中。fibonacci數(shù)列根據(jù)下式求得： 1

8、(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;inext=s=(lnode *)malloc(sizeof(lnode); s-data=p-data+q-data; s-next=null;

9、p=q;q=s; return h; 11. 設(shè)二叉樹t采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為字符類型。設(shè)計算法將二叉鏈表中所有data域為小寫字母的結(jié)點改為大寫字母?！敬鸢浮?void algo2(btnode *bt) if (bt) if(bt-data=a& bt-datadata-=32; algo2(bt-lchild); algo2(bt-rchild); 12. 假設(shè)線性表以帶表頭結(jié)點的循環(huán)單鏈表表示。試設(shè)計一個算法，在線性表的第k個元素前插入新元素y。假如表長小于k，則插在表尾。【答案】void insertlist(lnode *h,int k,elemtype y) q=h;

10、p=h-next; j=1; while( p!=h & jnext; j+;s=(lnode *)malloc(sizeof(lnode); s-data=y; q-next=s; s-next=q; 13. 有一帶表頭結(jié)點的單鏈表，其結(jié)點的元素值以非遞減有序排列，編寫一個算法在該鏈表中插入一個元素x，使得插入后的單鏈表仍有序?！敬鸢浮縱oid algo1 (lnode *h, elemtp x) s=(lnode *) malloc (sizeof(lnode); s-data=x; q=h; p=h-next;while ( p & p-datanext;s-next=p; q-next

11、=s; 14. 二叉排序樹的類型定義如下：typedef struct bstnode 二叉排序樹的結(jié)點結(jié)構(gòu)int data; 數(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-datalchild); return count;15. 有一帶表頭結(jié)點的單鏈表，其結(jié)點的data域的類型為字符型，編寫一個算法刪除該鏈表中的數(shù)字字符?！敬鸢浮?

12、void del_digit (lnode *h) for(p=h;p-next;) q=p-next; if(q-data=0& q-data next=q-next; free(q); else p=q; 16. 利用棧的基本運算，編寫一個算法，實現(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é)點

13、左孩子的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); 18. 設(shè)二叉樹t采用二叉鏈表結(jié)構(gòu)存儲，試設(shè)計算法求出二叉樹的深度?！敬鸢浮縤nt deep(btnode *bt) if (bt=n

14、ull) return 0; left=deep(bt-lchild); right=deep(bt-rchild);return (leftright?left:right)+1; 19. 設(shè)給定的哈希表存儲空間為h（0m-1），哈希函數(shù)的構(gòu)造方法為“除留余數(shù)法”，處理沖突的方法為“線性探測法”，設(shè)計算法將元素e填入到哈希表中?！敬鸢浮縱oid hash-insert(hashtable h,int m,elemtype e) j=e%p; if(hj!=null) hj=e; else do j=(j+1) %m;while(hj!=null );hj=e; 20. 對于給定的十進(jìn)制正整數(shù)

15、,打印出對應(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. 一個正讀和反讀都相同的字符序列稱為“回文”。例如“abcba”和“1221”是回文，而“abcde”不是回文。試寫一個算法，要求利用棧的基本運算識別一個以為結(jié)束符的字符序列是否是回文?！敬鸢浮縤nt pair(char *str ) initstack(s)； p=str for ( ;

16、*p!=; p+ ) push(s,*p); while(stackempty(s) pop(s,y);if(y!=*str+ ) return 0; return 1; 22. 有一帶表頭結(jié)點的單鏈表，其結(jié)點的元素值以非遞減有序排列，編寫一個算法刪除該鏈表中多余的元素值相同的結(jié)點(值相同的結(jié)點只保留一個)?！敬鸢浮?void delsame (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); else p=q; 23. 編寫一個算法，判斷帶表頭結(jié)點的單鏈

17、表是否遞增有序。【答案】int fun(lnode *h ) p=h-next; while(p-next) q=p-next ;if(q-datap-data) return 0;p=q; return 1; 24. 假設(shè)有兩個帶表頭結(jié)點的單鏈表ha和hb，設(shè)計算法將單鏈表hb插入到單鏈表ha的第i(0next; p=p-next); for(j=1,q=ha;jnext; ; p-next=q-next; q-next= hb-next ； free(hb); 25. 假設(shè)以帶頭結(jié)點的單鏈表表示有序表，單鏈表的類型定義如下： typedef struct node datatype dat

18、a; struct node *next linknode, *linklist; 編寫算法，從有序表a中刪除所有和有序表b中元素相同的結(jié)點?！敬鸢浮?空)26. 設(shè)二叉樹t采用二叉鏈表結(jié)構(gòu)存儲，數(shù)據(jù)元素為字符類型。設(shè)計算法分別求出二叉鏈表中data域為英文字母和數(shù)字字符的結(jié)點個數(shù)。【答案】int letter=0，digit=0； /*全局變量*/ void algo2(btnode *bt) if (bt) if(bt-data=a& bt-datadata=a& bt-datadata=0& bt-datalchild); algo2(bt-rchild); 27. 假設(shè)以單鏈表表示線性

19、表,單鏈表的類型定義如下:typedef struct node datatype data; struct node *next; linknode, *linklist; 編寫算法,將一個頭指針為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; p-next=s; head=s;

20、return head; 時間復(fù)雜度為:o(n)28. 假設(shè)有向圖以鄰接表方式存儲，編寫一個算法判別頂點vi到頂點vj是否存在弧?！敬鸢浮縤nt isarcs(algraph g,int i,int j) /* 判斷有向圖g中頂點i到頂點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)存儲，數(shù)據(jù)元素為字符類型。設(shè)計算法求出二叉鏈表中data域為大寫字母的結(jié)點個數(shù)?！敬鸢浮縤nt count=0；/* count為全局變量*/ void algo2(btnode *bt) if (bt) if(bt-data=a& bt-datalchild); algo2(bt-rchild