大連東軟數(shù)據(jù)結構編程題

頁腳

..

數(shù)據(jù)結構編程題

1)題1

完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組首地址，len為數(shù)組長度，要求函數(shù)f能夠將數(shù)組元素重新排列奇數(shù)在前，偶數(shù)

在后。

答案：

voidf(int*a,intlen){

inti,j;

for(i=0;i<len-1;i++){

intflg=1;

for(j=0;j<len-1-i;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的實現(xiàn)，參數(shù)a為int數(shù)組的首地址，len為數(shù)組長度，要求函數(shù)f能夠返回數(shù)組最大元素的個數(shù)。答案：

intf(constint*a,intlen){

inti,max=0,t=1;//max用于保存最大元素的序號，cnt用于記錄個數(shù)

for(i=1;i<len;i++)

if(a[max]<a[i]){

max=i;

cnt=1;

}elseif(a[max]==a[i]){

++cnt;

}

returnt;

}

..

3)題3

完成函數(shù)f的實現(xiàn)，參數(shù)a為int數(shù)組的首地址，len為數(shù)組長度，要求函數(shù)f能夠將數(shù)組元素按照個位排降序，同時

要求使用的算法要保證排序穩(wěn)定性。

答案：

解法一：(插入排序)

voidf(int*a,intlen){

inti,j,tmp;

for(i=1;i<len;++i){

tmp=a[i];

if(!(a[i]%10>a[0]%10)){//對某數(shù)進行%10運算，即可獲取其個位上的值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;

}

}

}

解法二：(冒泡排序)

voidf(int*a,intlen){

inti,j,flg,tmp;

for(i=0;i<len-1;++i){

flg=0;

for(j=0;j<len-i-1;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的實現(xiàn)，參數(shù)a為int數(shù)組首地址，len數(shù)組長度，要求函數(shù)f返回數(shù)組中元素是否構成大根堆，是返回1，否返回0.

答案：

_Boolf(constint*a,intlen){

inti;

for(i=(len-1)/2;i>=0;--i){

if(a[i]<a[2*(i+1)-1]||a[i]<a[2*(i+1)]){

returnfalse;

}

}

returntrue;

}

5)題5

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

答案：

_Boolf(constint*a,intlen,intx){

intlow=0,high=len-1,mid=(low+high)/2;

while(low<high){

if(a[mid]==x){

returntrue;

}elseif(a[mid]<x){

high=mid;

}elseif(a[mid]>x){

low=mid+1;

}

mid=(low+high)/2;

}

returnfalse;

}

頁腳

..

6)題6

完成函數(shù)f的實現(xiàn)，參數(shù)s和t分別表示兩個字符串首地址，要求函數(shù)f返回字符串t在字符串s中出現(xiàn)的次數(shù)，例如：f(“aaa”,“aa”)返回2。

答案：

intf(constchar*s,constchar*t){

intlen1=strlen(s),len2=strlen(t),i,num=0;

for(i=0;i<len1-len2+1;++i)

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

++num;

returnnum;

}

7)題7

代碼中，結構體Node表示雙鏈表節(jié)點，其中p指向前驅，n指向后繼；結構體List表示鏈表，指針head指向鏈表頭節(jié)點，tail指向鏈表尾節(jié)點，當鏈表為空時，head和tail為0(NULL)。完成函數(shù)f的實現(xiàn)，參數(shù)lp表示鏈表結構的指針，要求函數(shù)f能夠刪除lp指向鏈表的尾節(jié)點，并釋放存(假設鏈表節(jié)點存來自堆區(qū))，函數(shù)f的返回值表示刪除操作是否成功，成功返回1，否則返回0。

答案：

_Boolf(List*lp){

if(lp->tail==NULL)

returnfalse;

Node*cur=lp->tail;

lp->tail=cur->p;

if(lp->tail==NULL)

lp->head=NULL;

else

lp->tail->n=NULL;

free(cur);

returntrue;

}

頁腳

..

8)題8

代碼中，結構體Node表示二叉樹節(jié)點，其中l(wèi)eft指向左孩子，right指向右孩子；完成函數(shù)f的實現(xiàn)，參數(shù)root表示

二叉樹根節(jié)點指針，要求函數(shù)f返回該樹的深度，提示可用先序遍歷。

答案：

intf(constNode*root){

if(root==NULL)

return0;

intl=f(root->left);

intr=f(root->right);

returnl>r?l+1:r+1;

}

9)題9

代碼中，結構體Node表示二叉樹節(jié)點，其中l(wèi)eft指向左孩子，right指向右孩子；完成函數(shù)f的實現(xiàn)，參數(shù)root表示

二叉樹根節(jié)點指針，要求函數(shù)f釋放該樹全部節(jié)點占用的存(假設節(jié)點存來自堆區(qū))，提示可用后序遍歷。

答案：

intf(Node*root){

if(root==NULL)

return;

f(root->left);

f(root->right);

free(root);

}

10)題10

代碼中，結構體Node表示單鏈表的節(jié)點，data是整型數(shù)據(jù)域，next是指向后繼的指針；完成函數(shù)f的實現(xiàn)，參數(shù)head

是某鏈表的頭節(jié)點，參數(shù)x表示一個整數(shù)，要求函數(shù)f返回鏈表中數(shù)據(jù)域大于x的節(jié)點的個數(shù)。

答案：

intf(Node*head,intx){

Node*p;

intt=0;

for(p=head;p!=NULL;p=p->next)

if(p->data>x)

cnt++;

returnt;

}

..

11)題11

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

答案：

intf(intn,const_Boola[n][n]){

inti,j,t=0;

for(i=0;i<n;i++){

intin=0,out=0;

for(j=0;j<n;j++)

if(a[j][i])

in++;

if(a[i][j])

out++;

if(out>in)

cnt++;

}

returnt;

}

12)題12

完成函數(shù)f的實現(xiàn)，參數(shù)n表示正整數(shù)，參數(shù)a表示一個一位數(shù)組首地址，i表示一個正整數(shù)(0<=i<n)，a表示的一維數(shù)組用于存儲n個節(jié)點無向圖的鄰接矩陣的上三角壓縮存儲，函數(shù)f需要返回無向圖中節(jié)點i的度。

答案：

intf(intn,const_Boola[],inti){

intj,k=0;

intm=n-i;

for(j=0;j<i;j++)

k+=(n--);

intt=0;

for(j=k;j<k+m;j++)

if(a[j])

cnt++;

returnt;

}

頁腳

..

13)題13

完成函數(shù)f的實現(xiàn)，參數(shù)s表示字符串首地址，字符串中僅有‘(’和‘)’，函數(shù)f返回一個布爾值，當字符串中的‘(’

和‘)’恰好匹配時返回真，否則返回假。

答案：

_Boolf(constchar*s){

intstack=0,i;//stack表示棧，stack=0時?？說or(i=0;s[i]!='\0';i++)

if(s[i]=='{')

stack++;

elseif(s[i]=='}'&&stack>0)

stack--;

else

returnfalse;

if(stack==0)

returntrue;

returnfalse;

}

14)題14

完成函數(shù)f的實現(xiàn)，參數(shù)s1和s2分別表示兩個字符串首地址，要求函數(shù)f實現(xiàn)不區(qū)分大小寫字母的字符串比較，當s1

比s2小時f返回負數(shù)，當s1比s2大時返回正數(shù)，字母串相等返回0。

答案

intf(constchar*s1,constchar*s2){

inti;

for(i=0;s1[i]!='\0'||s2[i]!='\0';i++)

if(s1[i]==s2[i]){

continue;

}elseif(s1[i]>='A'&&s1[i]<='Z'||s1[i]>='a'&&s1[i]<='z'&&s2[i]>='A'&&s2[i]<='Z'||s2[i]>='a'&&s2[i]<='z'

&&abs(s1[i]-s2[i])==abs('A'-'a')){

continue;

}elseif(s1[i]>s2[i]){

return1;

}else{

return-1;

}

return0;

}

頁腳

..

15)題15

完成函數(shù)f的實現(xiàn)，參數(shù)a、b、c表示三個int數(shù)組的首地址，la和lb表示數(shù)組a和b的長度，假設數(shù)組a和b存在升序。要求函數(shù)f完成將數(shù)組a和