大连东软数据结构编程题.docxVIP

数据结构编程题题1完成函数f的实现，参数a为int数组首地址，len为数组长度，要求函数f能够将数组元素重新排列奇数在前，偶数在后。答案：void f(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完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够返回数组最大元素的个数。答案：int f(constint *a, intlen) {inti, max=0, cnt=1;//max用于保存最大元素的序号，cnt用于记录个数for(i=1; ilen; i++)if(a[max]a[i]) {max=i;cnt=1;} else if(a[max]==a[i]) { ++cnt;}return cnt;}题3完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够将数组元素按照个位排降序，同时要求使用的算法要保证排序稳定性。答案：解法一：（插入排序）void f(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;}}}解法二：（冒泡排序）void f(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完成函数f的实现，参数a为int数组首地址，len数组长度，要求函数f返回数组中元素是否构成大根堆，是返回1，否返回0.答案：_Bool f(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)]) {return false;}}return true;}题5完成函数f的实现，参数a为int数组首地址，len为数组长度，x为一个整数，假设数组元素已排好降序，要求函数f运用折半查找算法，查找数组中是否存在x，存在返回1，不存在返回0。答案：_Bool f(constint *a, intlen, int x) {int low=0, high=len-1, mid=(low+high)/2;while(lowhigh) {if(a[mid]==x) {return true;} else if(a[mid]x) {high=mid;} else if(a[mid]x) {low=mid+1;}mid=(low+high)/2;}return false;}题6完成函数f的实现，参数s和t分别表示两个字符串首地址，要求函数f返回字符串t在字符串s中出现的次数，例如：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 ;ilen1-len2+1; ++i)if(strncmp(s+i, t, len2)==0)++num;return num;}题7代码中，结构体Node表示双链表节点，其中p指向前驱，n指向后继；结构体List表示链表，指针head指向链表头节点，tail指向链表尾节点，当链表为空时，head和tail为0（NULL）。完成函数f的实现，参数lp表示链表结构的指针，要求函数f能够删除lp指向链表的尾节点，并释放内存（假设链表节点内存来自堆区），函数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;elselp-tail-n=NULL;fr