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

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

1)題1 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)a為int數(shù)組首地址，len為數(shù)組長(zhǎng)度，要求函數(shù)f能夠?qū)?shù)組元素重新排列奇數(shù)在前，偶數(shù)在后。

答案：

void f(int *a, intlen){ inti, j;for(i=0;i

intflg=1;

for(j=0;j

if(a[j]%2==0 && a[j+1]%2){

inttmp=a[j];

a[j]=a[j+1];

a[j+1]=tmp;

flg=0;

}

}

if(flg)break;} } 2)題2 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)a為int數(shù)組的首地址，len為數(shù)組長(zhǎng)度，要求函數(shù)f能夠返回?cái)?shù)組最大元素的個(gè)數(shù)。

答案：

int f(constint *a, intlen){

inti, max=0, cnt=1;//max用于保存最大元素的序號(hào)，cnt用于記錄個(gè)數(shù) for(i=1;i

max=i;

cnt=1;} else if(a[max]==a[i]){

++cnt;} return cnt;} 3)題3 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)a為int數(shù)組的首地址，len為數(shù)組長(zhǎng)度，要求函數(shù)f能夠?qū)?shù)組元素按照個(gè)位排降序，同時(shí)要求使用的算法要保證排序穩(wěn)定性。

答案：

解法一：（插入排序）

void f(int *a, intlen){ inti, j, tmp;for(i=1;i

tmp=a[i];

}

} if(!(a[i]%10>a[0]%10)){//對(duì)某數(shù)進(jìn)行%10運(yùn)算，即可獲取其個(gè)位上的值

for(j=i-1;tmp%10>a[j]%10;--j)

a[j+1]=a[j];a[j+1]=tmp;} else { for(j=i;j>0;--j)

a[j]=a[j-1];a[0]=tmp;} 解法二：（冒泡排序）

void f(int *a, intlen){ inti, j, flg, tmp;for(i=0;i

flg=0;

for(j=0;j

if(a[j+1]%10>a[j]%10){

tmp=a[j+1];

a[j+1]=a[j];

a[j]=tmp;

}

if(flg=0)

break;} } 4)題4 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)a為int數(shù)組首地址，len數(shù)組長(zhǎng)度，要求函數(shù)f返回?cái)?shù)組中元素是否構(gòu)成大根堆，是返回1，否返回0.答案：

_Bool f(constint *a, intlen){ inti;for(i=(len-1)/2;i>=0;--i){

if(a[i]

return false;

} } return true;}

5)題5 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)a為int數(shù)組首地址，len為數(shù)組長(zhǎng)度，x為一個(gè)整數(shù)，假設(shè)數(shù)組元素已排好降序，要求函數(shù)f運(yùn)用折半查找算法，查找數(shù)組中是否存在x，存在返回1，不存在返回0。

答案：

_Bool f(constint *a, intlen, int x){ int low=0, high=len-1, mid=(low+high)/2;while(low

if(a[mid]==x){

return true;

} else if(a[mid]

high=mid;

} else if(a[mid]>x){

low=mid+1;

}

mid=(low+high)/2;} return false;} 6)題6 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)s和t分別表示兩個(gè)字符串首地址，要求函數(shù)f返回字符串t在字符串s中出現(xiàn)的次數(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;i

if(strncmp(s+i, t, len2)==0)

++num;return num;}

7)題7 代碼中，結(jié)構(gòu)體Node表示雙鏈表節(jié)點(diǎn)，其中p指向前驅(qū)，n指向后繼；結(jié)構(gòu)體List表示鏈表，指針head指向鏈表頭節(jié)點(diǎn)，tail指向鏈表尾節(jié)點(diǎn)，當(dāng)鏈表為空時(shí)，head和tail為0（NULL）。完成函數(shù)f的實(shí)現(xiàn)，參數(shù)lp表示鏈表結(jié)構(gòu)的指針，要求函數(shù)f能夠刪除lp指向鏈表的尾節(jié)點(diǎn)，并釋放內(nèi)存（假設(shè)鏈表節(jié)點(diǎn)內(nèi)存來(lá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;else

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

答案：

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表示二叉樹(shù)節(jié)點(diǎn)，其中l(wèi)eft指向左孩子，right指向右孩子；完成函數(shù)f的實(shí)現(xiàn)，參數(shù)root表示二叉樹(shù)根節(jié)點(diǎn)指針，要求函數(shù)f釋放該樹(shù)全部節(jié)點(diǎn)占用的內(nèi)存（假設(shè)節(jié)點(diǎn)內(nèi)存來(lái)自堆區(qū)），提示可用后序遍歷。

答案：

int f(Node *root){ if(root==NULL)

return;f(root->left);f(root->right);free(root);} 10)題10 代碼中，結(jié)構(gòu)體Node表示單鏈表的節(jié)點(diǎn)，data是整型數(shù)據(jù)域，next是指向后繼的指針；完成函數(shù)f的實(shí)現(xiàn)，參數(shù)head是某鏈表的頭節(jié)點(diǎn)，參數(shù)x表示一個(gè)整數(shù)，要求函數(shù)f返回鏈表中數(shù)據(jù)域大于x的節(jié)點(diǎn)的個(gè)數(shù)。答案：

int f(Node *head, int x){ Node *p;intcnt=0;for(p=head;p!=NULL;p=p->next)

if(p->data>x)

cnt++;return cnt;} 11)題11 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)n表示正整數(shù)，參數(shù)a表示二維數(shù)組首地址，a表示的二維數(shù)組用于存儲(chǔ)n個(gè)系欸但有向圖的鄰接矩陣，a[i][j]==1時(shí)表示節(jié)點(diǎn)i到節(jié)點(diǎn)j有邊，函數(shù)f需要返回有向圖中出度大于入度的頂點(diǎn)的個(gè)數(shù)。

答案：

int f(int n, const _Bool a[n][n]){ inti, j, cnt=0;for(i=0;i

int in=0, out=0;

for(j=0;j

if(a[j][i])

in++;

if(a[i][j])

out++;

if(out>in)

cnt++;} return cnt;} 12)題12 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)n表示正整數(shù)，參數(shù)a表示一個(gè)一位數(shù)組首地址，i表示一個(gè)正整數(shù)（0<=i

int f(int n, const _Bool a[], inti){ int j, k=0;int m=n-i;for(j=0;j

k+=(n--);intcnt=0;for(j=k;j

if(a[j])

cnt++;return cnt;} 13)題13 完成函數(shù)f的實(shí)現(xiàn)，參數(shù)s表示字符串首地址，字符串中僅有‘（’和‘）’，函數(shù)f返回一個(gè)布爾值，當(dāng)字符串中的‘（’和‘）’恰好匹配時(shí)返回真，否則返回假。

答案：

_Bool f(const char *s){

} int stack=0, i;//stack表示棧，stack=0時(shí)?？?for(i=0;s[i]!='