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

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

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

3、0010_) /對(duì)某數(shù)進(jìn)行_x0010_ for(j=i-1; tmp_x0010_aj_x0010_; -j) aj+1=aj; aj+1=tmp; else for(j=i; j0; -j) aj=aj-1; a0=tmp; 解法二：（冒泡排序） void f(int *a, int len) int i, j, flg, tmp; for(i=0; ilen-1; +i) flg=0; for(j=0; jaj_x0010_) tmp=aj+1; aj+1=aj; aj=tmp; if(flg=0) break; 題44) ，1len數(shù)組長度，要求函數(shù)f返回?cái)?shù)組中元素是否構(gòu)成大根堆，是返

4、回a完成函數(shù)f的實(shí)現(xiàn)，參數(shù)為int數(shù)組首地址， 0.否返回 答案： _Bool f(const int *a, int len) int i; for(i=(len-1)/2; i=0; -i) if(aia2*(i+1)-1 | aia2*(i+1) return false; return true; 5 題5)f為一個(gè)整數(shù)，假設(shè)數(shù)組元素已排好降序，要求函數(shù)為數(shù)組長度，x為int數(shù)組首地址，lena完成函數(shù)f的實(shí)現(xiàn)，參數(shù) 0。x，存在返回1，不存在返回運(yùn)用折半查找算法，查找數(shù)組中是否存在 答案：_Bool f(const int *a, int len, int x) int low=0,

5、 high=len-1, mid=(low+high)/2; while(lowhigh) if(amid=x) return true; else if(amidx) low=mid+1; mid=(low+high)/2; return false; 題66) 例如：中出現(xiàn)的次數(shù)，返回字符串ft在字符串s完成函數(shù)f的實(shí)現(xiàn)，參數(shù)s和t分別表示兩個(gè)字符串首地址，要求函數(shù) 。f(“aaa”, “aa”)返回2 答案： int f(const char *s, const char *t) int len1=strlen(s), len2=strlen(t), i, num=0; for(i=0

6、;itail=NULL) return false; Node *cur=lp-tail; lp-tail=cur-p; if(lp-tail=NULL) lp-head=NULL; else lp-tail-n=NULL; free(cur); return true; 88) 題表示的實(shí)現(xiàn)，參數(shù)right指向右孩子；完成函數(shù)froot代碼中，結(jié)構(gòu)體Node表示二叉樹節(jié)點(diǎn)，其中l(wèi)eft指向左孩子， 返回該樹的深度，提示可用先序遍歷。f二叉樹根節(jié)點(diǎn)指針，要求函數(shù) 答案： int f(const Node *root) if(root=NULL) return 0; int l=f(root-l

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

8、data是整型數(shù)據(jù)域， x返回鏈表中數(shù)據(jù)域大于的節(jié)點(diǎn)的個(gè)數(shù)。是某鏈表的頭節(jié)點(diǎn)，參數(shù)x表示一個(gè)整數(shù)，要求函數(shù)f 答案：int f(Node *head, int x) Node *p; int cnt=0; for(p=head; p!=NULL; p=p-next) if(p-datax) cnt+; return cnt; 題1111) 個(gè)系欸但有向圖的表示的二維數(shù)組用于存儲(chǔ)nn表示正整數(shù)，參數(shù)a表示二維數(shù)組首地址，a完成函數(shù)f的實(shí)現(xiàn)，參數(shù) f需要返回有向圖中出度大于入度的頂點(diǎn)的個(gè)數(shù)。i到節(jié)點(diǎn)j有邊，函數(shù)鄰接矩陣，aij=1時(shí)表示節(jié)點(diǎn) 答案： int f(int n, const _Bool

9、 ann) int i, j, cnt=0; for(i=0; in; i+) int in=0, out=0; for(j=0; jin) cnt+; return cnt; 12 題12)表示正整數(shù)，參數(shù)a表示一個(gè)一位數(shù)組首地址，i表示一個(gè)正整數(shù)（0=in）完成函數(shù)f的實(shí)現(xiàn)，參數(shù)n，a表示的一維數(shù)組用于存儲(chǔ)n個(gè)節(jié)點(diǎn)無向圖的鄰接矩陣的上三角壓縮存儲(chǔ)，函數(shù)f需要返回?zé)o向圖中節(jié)點(diǎn)i的度。 答案： int f(int n, const _Bool a, int i) int j, k=0; int m=n-i; for(j=0; ji; j+) k+=(n-); int cnt=0; for(j=

10、k; j0) stack-; else return false; if(stack=0) return true; return false; 1414) 題s1當(dāng)要求函數(shù)f實(shí)現(xiàn)不區(qū)分大小寫字母的字符串比較，參數(shù)s1和s2分別表示兩個(gè)字符串首地址，的實(shí)現(xiàn)，完成函數(shù)f 。大時(shí)返回正數(shù)，字母串相等返回0f返回負(fù)數(shù)，當(dāng)s1比s2比s2小時(shí) 答案 int f(const char *s1, const char *s2) int i; for(i=0; s1i!=0 | s2i!=0; i+) if(s1i=s2i) continue; else if(s1i=A & s1i=a & s1i=A & s2i=a & s2is2i) return 1; else return -1; return 0; 題1515) 存在ba和alb表示數(shù)組和b的長度，假設(shè)數(shù)組c完成函數(shù)f的實(shí)現(xiàn)，參數(shù)a、b、表示三個(gè)int數(shù)組的首地址，la和ba和c后，c也有升序，同時(shí)當(dāng)中，即a和b的內(nèi)容歸并到數(shù)組ca和b的內(nèi)容復(fù)制至數(shù)組升序。要求函數(shù)f完成將數(shù)組 a中的等值元素。中存在相等元素時(shí)，需要優(yōu)先向c中寫入