大连东软数据结构编程题

/数据结构编程题题1完成函数f的实现，参数a为int数组首地址，len为数组长度，要求函数f能够将数组元素重新排列奇数在前，偶数在后。答案：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完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够返回数组最大元素的个数。答案：intf(constint*a,intlen){ inti,max=0,cnt=1;//max用于保存最大元素的序号，cnt用于记录个数 for(i=1;i<len;i++) if(a[max]<a[i]){ max=i; cnt=1; }elseif(a[max]==a[i]){ ++cnt; } returncnt;}题3完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够将数组元素按照个位排降序，同时要求使用的算法要保证排序稳定性。答案：解法一：（插入排序）voidf(int*a,intlen){ inti,j,tmp; for(i=1;i<len;++i){ tmp=a[i]; if(!(a[i]%10>a[0]%10)){//对某数进行%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完成函数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完成函数f的实现，参数a为int数组首地址，len为数组长度，x为一个整数，假设数组元素已排好降序，要求函数f运用折半查找算法，查找数组中是否存在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完成函数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;i<len1-len2+1;++i) if(strncmp(s+i,t,len2)==0) ++num; returnnum;}题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; else lp->tail->n=NULL; free(cur); returntrue;}题8代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f返回该树的深度，提示可用先序遍历。 答案：intf(constNode*root){ if(root==NULL) return0; intl=f(root->left); intr=f(root->right); returnl>r?l+1:r+1;}题9代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f释放该树全部节点占用的内存（假设节点内存来自堆区），提示可用后序遍历。 答案：intf(Node*root){ if(root==NULL) return; f(root->left); f(root->right); free(root);}题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->data>x) cnt++; returncnt;}题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;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++; } returncnt;}题12完成函数f的实现，参数n表示正整数，参数a表示一个一位数组首地址，i表示一个正整数（0<=i<n），a表示的一维数组用于存储n个节点无向图的邻接矩阵的上三角压缩存储，函数f需要返回无向图中节点i的度。 答案：intf(intn,const_Boola[],inti){ intj,k=0; intm=n-i; for(j=0;j<i;j++) k+=(n--); intcnt=0; for(j=k;j<k+m;j++) if(a[j]) cnt++; returncnt;}

题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]=='}'&&stack>0) stack--; else returnfalse; if(stack==0) returntrue; returnfalse;}题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完成函数f的实现，参数a、b、c表示三个int数组的首地址，la和lb表示数组a和b的长度，假设数组a和b存在升序。要求函数f完成将数组a和b的内容归并到数组c中，即a和b的内容复制至数组c后，c也有升序，同时当a和b中存在相等元素时