大連東軟數(shù)據(jù)結(jié)構(gòu)編程題參考模板

1、數(shù)據(jù)結(jié)構(gòu)編程題1) 題1完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組首地址，len為數(shù)組長度，要求函數(shù)f能夠?qū)?shù)組元素重新排列奇數(shù)在前，偶數(shù)在后。 答案：void f(int *a, int len) int i, j;for(i=0; i<len-1; i+) int flg=1;for(j=0; j<len-1-i; j+) if(aj%2=0 && aj+1%2) int tmp=aj;aj=aj+1;aj+1=tmp;flg=0;if(flg) break;2) 題2完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組的首地址，len為數(shù)組長度，要求函數(shù)f能夠返回數(shù)組最大元素的個數(shù)

2、。答案：int f(const int *a, int len) int i, max=0, cnt=1;/max用于保存最大元素的序號，cnt用于記錄個數(shù) for(i=1; i<len; i+)if(amax<ai) max=i;cnt=1; else if(amax=ai) +cnt;1 / 11return cnt;3) 題3完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組的首地址，len為數(shù)組長度，要求函數(shù)f能夠?qū)?shù)組元素按照個位排降序，同時要求使用的算法要保證排序穩(wěn)定性。答案：解法一：（插入排序）void f(int *a, int len) int i, j, tmp;for(i=

3、1; i<len; +i) tmp=ai;if(!(ai%10>a0%10) /對某數(shù)進行%10運算，即可獲取其個位上的值 for(j=i-1; tmp%10>aj%10; -j)aj+1=aj;aj+1=tmp; else for(j=i; j>0; -j)aj=aj-1;a0=tmp;解法二：（冒泡排序）void f(int *a, int len) int i, j, flg, tmp;for(i=0; i<len-1; +i) flg=0;for(j=0; j<len-i-1; j+)if(aj+1%10>aj%10) tmp=aj+1; aj

4、+1=aj;aj=tmp;if(flg=0) break;4) 題4完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組首地址，len數(shù)組長度，要求函數(shù)f返回數(shù)組中元素是否構(gòu)成大根堆，是返回1，否返回0.答案：_Bool f(const int *a, int len) int i;for(i=(len-1)/2; i>=0; -i) if(ai<a2*(i+1)-1 | ai<a2*(i+1) return false;return true;5) 題5完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組首地址，len為數(shù)組長度，x為一個整數(shù)，假設(shè)數(shù)組元素已排好降序，要求函數(shù)f運用折半查找算法，查找數(shù)組中

5、是否存在x，存在返回1，不存在返回0。答案：_Bool f(const int *a, int len, int x) int low=0, high=len-1, mid=(low+high)/2;while(low<high) if(amid=x) return true; else if(amid<x) high=mid; else if(amid>x) low=mid+1;mid=(low+high)/2;return false;6) 題6完成函數(shù)f的實現(xiàn)，參數(shù)s和t分別表示兩個字符串首地址，要求函數(shù)f返回字符串t在字符串s中出現(xiàn)的次數(shù)，例如：f(“aaa”, “a

6、a”)返回2。答案：int f(const char *s, const char *t) int len1=strlen(s), len2=strlen(t), i, num=0;for(i=0 ;i<len1-len2+1; +i)if(strncmp(s+i, t, len2)=0)+num;return num;7) 題7代碼中，結(jié)構(gòu)體Node表示雙鏈表節(jié)點，其中p指向前驅(qū)，n指向后繼；結(jié)構(gòu)體List表示鏈表，指針head指向鏈表頭節(jié)點，tail指向鏈表尾節(jié)點，當(dāng)鏈表為空時，head和tail為0（NULL）。完成函數(shù)f的實現(xiàn)，參數(shù)lp表示鏈表結(jié)構(gòu)的指針，要求函數(shù)f能夠刪除lp指

7、向鏈表的尾節(jié)點，并釋放內(nèi)存（假設(shè)鏈表節(jié)點內(nèi)存來自堆區(qū)），函數(shù)f的返回值表示刪除操作是否成功，成功返回1，否則返回0。答案：_Bool f(List *lp) if(lp->tail=NULL)return false;Node *cur=lp->tail;lp->tail=cur->p;if(lp->tail=NULL)lp->head=NULL;elselp->tail->n=NULL;free(cur);return true;8) 題8代碼中，結(jié)構(gòu)體Node表示二叉樹節(jié)點，其中l(wèi)eft指向左孩子，right指向右孩子；完成函數(shù)f的實現(xiàn)，參數(shù)

8、root表示二叉樹根節(jié)點指針，要求函數(shù)f返回該樹的深度，提示可用先序遍歷。答案：int f(const Node *root) if(root=NULL)return 0;int l=f(root->left);int r=f(root->right);return l>r?l+1:r+1;9) 題9代碼中，結(jié)構(gòu)體Node表示二叉樹節(jié)點，其中l(wèi)eft指向左孩子，right指向右孩子；完成函數(shù)f的實現(xiàn)，參數(shù)root表示二叉樹根節(jié)點指針，要求函數(shù)f釋放該樹全部節(jié)點占用的內(nèi)存（假設(shè)節(jié)點內(nèi)存來自堆區(qū)），提示可用后序遍歷。答案：int f(Node *root) if(root=NUL

9、L)return;f(root->left);f(root->right);free(root);10) 題10代碼中，結(jié)構(gòu)體Node表示單鏈表的節(jié)點，data是整型數(shù)據(jù)域，next是指向后繼的指針；完成函數(shù)f的實現(xiàn)，參數(shù)head是某鏈表的頭節(jié)點，參數(shù)x表示一個整數(shù)，要求函數(shù)f返回鏈表中數(shù)據(jù)域大于x的節(jié)點的個數(shù)。答案：int f(Node *head, int x) Node *p;int cnt=0;for(p=head; p!=NULL; p=p->next)if(p->data>x)cnt+;return cnt;11) 題11完成函數(shù)f的實現(xiàn)，參數(shù)n表示正

10、整數(shù)，參數(shù)a表示二維數(shù)組首地址，a表示的二維數(shù)組用于存儲n個系欸但有向圖的鄰接矩陣，aij=1時表示節(jié)點i到節(jié)點j有邊，函數(shù)f需要返回有向圖中出度大于入度的頂點的個數(shù)。答案：int f(int n, const _Bool ann) int i, j, cnt=0;for(i=0; i<n; i+) int in=0, out=0;for(j=0; j<n; j+)if(aji)in+;if(aij)out+;if(out>in)cnt+;return cnt;12) 題12完成函數(shù)f的實現(xiàn)，參數(shù)n表示正整數(shù)，參數(shù)a表示一個一位數(shù)組首地址，i表示一個正整數(shù)（0<=i&l

11、t;n），a表示的一維數(shù)組用于存儲n個節(jié)點無向圖的鄰接矩陣的上三角壓縮存儲，函數(shù)f需要返回?zé)o向圖中節(jié)點i的度。答案：int f(int n, const _Bool a, int i) int j, k=0;int m=n-i;for(j=0; j<i; j+)k+=(n-);int cnt=0;for(j=k; j<k+m; j+)if(aj)cnt+;return cnt;13) 題13完成函數(shù)f的實現(xiàn)，參數(shù)s表示字符串首地址，字符串中僅有（和），函數(shù)f返回一個布爾值，當(dāng)字符串中的（和）恰好匹配時返回真，否則返回假。答案：_Bool f(const char *s) int s

12、tack=0, i;/stack表示棧，stack=0時?？說or(i=0; si!='0' i+)if(si='')stack+;else if(si='' && stack>0)stack-;elsereturn false;if(stack=0)return true;return false;14) 題14完成函數(shù)f的實現(xiàn)，參數(shù)s1和s2分別表示兩個字符串首地址，要求函數(shù)f實現(xiàn)不區(qū)分大小寫字母的字符串比較，當(dāng)s1比s2小時f返回負數(shù)，當(dāng)s1比s2大時返回正數(shù)，字母串相等返回0。答案int f(const char *

13、s1, const char *s2) int i;for(i=0; s1i!='0' | s2i!='0' i+)if(s1i=s2i) continue; else if(s1i>='A' && s1i<='Z' | s1i>='a' && s1i<='z' && s2i>='A' && s2i<='Z' | s2i>='a' && s2i<='z' && abs(s1i-s2i)=abs('A'-'a') continue; else if(s1i>s2i) return 1; else return -1;return 0;15) 題15完成函數(shù)f的實現(xiàn)，參數(shù)a、b、c表示三個int數(shù)組的首地址，la和lb表示數(shù)組a和b的長度，假設(shè)數(shù)組a和b存在升序。要求函數(shù)f完成將數(shù)組a和b的內(nèi)容歸并到數(shù)組c中，即a和b的內(nèi)容復(fù)制至數(shù)組c后，c也有升序，