大连东软数据结构编程题

数据结构编程题1)题1完成函数f的实现，参数a为int数组首地址，len为数组长度，要求函数f能够将数组元素重新排列奇数在前，偶数在后。答案：voidf(int*a,intlen){inti,j;for(i=0;ilen-1;i++){intflg=1;for(j=0;jlen-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完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够返回数组最大元素的个数。答案：intf(constint*a,intlen){inti,max=0,cnt=1;//max用于保存最大元素的序号，cnt用于记录个数for(i=1;ilen;i++)if(a[max]a[i]){max=i;cnt=1;}elseif(a[max]==a[i]){++cnt;}returncnt;}3)题3完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够将数组元素按照个位排降序，同时要求使用的算法要保证排序稳定性。答案：解法一：（插入排序）voidf(int*a,intlen){inti,j,tmp;for(i=1;ilen;++i){tmp=a[i];if(!(a[i]%10a[0]%10)){//对某数进行%10运算，即可获取其个位上的值for(j=i-1;tmp%10a[j]%10;--j)a[j+1]=a[j];a[j+1]=tmp;}else{for(j=i;j0;--j)a[j]=a[j-1];a[0]=tmp;}}}解法二：（冒泡排序）voidf(int*a,intlen){inti,j,flg,tmp;for(i=0;ilen-1;++i){flg=0;for(j=0;jlen-i-1;j++)if(a[j+1]%10a[j]%10){tmp=a[j+1];a[j+1]=a[j];a[j]=tmp;}if(flg=0)break;}}4)题4完成函数f的实现，参数a为int数组首地址，len数组长度，要求函数f返回数组中元素是否构成大根堆，是返回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完成函数f的实现，参数a为int数组首地址，len为数组长度，x为一个整数，假设数组元素已排好降序，要求函数f运用折半查找算法，查找数组中是否存在x，存在返回1，不存在返回0。答案：_Boolf(constint*a,intlen,intx){intlow=0,high=len-1,mid=(low+high)/2;while(lowhigh){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完成函数f的实现，参数s和t分别表示两个字符串首地址，要求函数f返回字符串t在字符串s中出现的次数，例如：f(“aaa”,“aa”)返回2。答案：intf(constchar*s,constchar*t){intlen1=strlen(s),len2=strlen(t),i,num=0;for(i=0;ilen1-len2+1;++i)if(strncmp(s+i,t,len2)==0)++num;returnnum;}7)题7代码中，结构体Node表示双链表节点，其中p指向前驱，n指向后继；结构体List表示链表，指针head指向链表头节点，tail指向链表尾节点，当链表为空时，head和tail为0（NULL）。完成函数f的实现，参数lp表示链表结构的指针，要求函数f能够删除lp指向链表的尾节点，并释放内存（假设链表节点内存来自堆区），函数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;elselp-tail-n=NULL;free(cur);returntrue;}8)题8代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f返回该树的深度，提示可用先序遍历。答案：intf(constNode*root){if(root==NULL)return0;intl=f(root-left);intr=f(root-right);returnlr?l+1:r+1;}9)题9代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f释放该树全部节点占用的内存（假设节点内存来自堆区），提示可用后序遍历。答案：intf(Node*root){if(root==NULL)return;f(root-left);f(root-right);free(root);}10)题10代码中，结构体Node表示单链表的节点，data是整型数据域，next是指向后继的指针；完成函数f的实现，参数head是某链表的头节点，参数x表示一个整数，要求函数f返回链表中数据域大于x的节点的个数。答案：intf(Node*head,intx){Node*p;intcnt=0;for(p=head;p!=NULL;p=p-next)if(p-datax)cnt++;returncnt;}11)题11完成函数f的实现，参数n表示正整数，参数a表示二维数组首地址，a表示的二维数组用于存储n个系欸但有向图的邻接矩阵，a[i][j]==1时表示节点i到节点j有边，函数f需要返回有向图中出度大于入度的顶点的个数。答案：intf(intn,const_Boola[n][n]){inti,j,cnt=0;for(i=0;in;i++){intin=0,out=0;for(j=0;jn;j++)if(a[j][i])in++;if(a[i][j])out++;if(outin)cnt++;}returncnt;}12)题12完成函数f的实现，参数n表示正整数，参数a表示一个一位数组首地址，i表示一个正整数（0=in），a表示的一维数组用于存储n个节点无向图的邻接矩阵的上三角压缩存储，函数f需要返回无向图中节点i的度。答案：intf(intn,const_Boola[],inti){intj,k=0;intm=n-i;for(j=0;ji;j++)k+=(n--);intcnt=0;for(j=k;jk+m;j++)if(a[j])cnt++;returncnt;}13)题13完成函数f的实现，参数s表示字符串首地址，字符串中仅有‘（’和‘）’，函数f返回一个布尔值，当字符串中的‘（’和‘）’恰好匹配时返回真，否则返回假。答案：_Boolf(constchar*s){intstack=0,i;//stack表示栈，stack=0时栈空for(i=0;s[i]!='\0';i++)if(s[i]=='{')stack++;elseif(s[i]=='}'&&stack0)stack--;elsereturnfalse;if(stack==0)returntrue;returnfalse;}14)题14完成函数f的实现，参数s1和s2分别表示两个字符串首地址，要求函数f实现不区分大小写字母的字符串比较，当s1比s2小时f返回负数，当s1比s2大时返回正数，字母串相等返回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完成函数f的实现，参数a、b、c表示三个int数组的首地址，la和lb表示数组a和b的长度，假设数组a和b存在升序。要求函数f完成将数组a和b的内容归并到数组c中，即a和b的内容复制至数组c后，c也有升序，同时当a和b中存在相等元素时，需要优先向c中写入a中的等值元素。答案：voidf(int*a,intla,int*b,intlb,int*c){inti,j,k;for(i=0,j=0,k=0;ila&&jlb;k++)if(b[j]a[i])c[k]=b[j++];elsec[k]=a[i++];while(ila)c[k++]=a[i++];while(jlb)c[k++]=b[j++];}