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

1 自定义圆形类，要求有属性：半径和圆心，要求有成员函数：构造函数、设置圆心函数、设置半径函数、读取圆心函数（2个分别读圆心的横纵坐标）、读取半径的函数，读取面积函数。 class Circle { private: float r; //半径 float x; float y; public: Circle(float r, float x, float y){this->r=r;}; void setCenter(float x1, float y1){x=x1;y=y1;} float getX(){return x;} float getY(){return y;} float getR(){return r;} float getArea(){return 3.14*r*r;} };2 自定义矩形类，要求有属性：左上角坐标、长和宽，要求有成员函数：构造函数、设置和读取各个属性的函数、求面积函数。 class RectAngle { private: float x; float y; float l; float w; public: RectAngle(float x,float y,float l,float w){ this->x=x,this->y=y,this->l=l,this->w=w}; void setw(float w1){w=w1;} void setl(float la){l=la;} void setx(float x1){x=x1;} void sety(float y1){y=y1;} float getX(){return x;} float getY(){return y;} float getL(){return l;} float getW(){return w;} float getArea(){ return w*l;} };3 自定义time类型，表示一天中的时间，细化到秒，属性自拟，函数要求：构造、设置和读取时、分、秒。 clas

3 自定义time类型，表示一天中的时间，细化到秒，属性自拟，函数要求：构造、设置和读取时、分、秒。 class time { private: int hour;int minute; int second; public: time(int h,int m,int s){ hour=h,minute=m,second=s;}; void seth(int h1){h=h1;} void setm(int m1){m=m1;} void sets(int s1){s=s1;} int getH(){return h;} int getM(){return m;} int getS(){return s;} };4 自定义date类型，表示日期，细化到日，属性自拟，函数要求：构造、设置和读取年、月、日。 class date{ private: int y; int m; int d;public: data(int y,int m,int d){ this->y=y,this->m=m,this->d=d;}; void setY(int y1){y=y1;} void setM(int m1){ m=m1:} void setD(int d1){d=d1;} int getD(){return d;} int getY(){ return y;} int getM(){return m;}};

5 假设已经存在以下类型list表示int双向链表，并且所有的函数已经实现 class list { public: list(); ~list(); bool empty()const;//判断是否为空 void insert_at_head(int);//在头部插入 void insert_at_tail(int);//在尾部插入 void delete_from_head();//从头删除 void delete_from_tail();//从尾删除 int head()const;//读取头部元素 int tail()const;//读取尾部元素 };要求定义类型stack，表示int栈，stack需要继承list，并实现函数：入栈push，出栈pop，读栈顶top，判断栈空empty class stack:protected list { public: void push(int num){insert_at_tail(num);}//尾部插入 void pop(){delete_from_tail();}//尾部删除 int top(){return tail();}//读尾部 bool empty(){return empty();}//判断栈空 };6 假设已经存在以下类型list表示int双向链表，并且所有的函数已经实现 class list { public: list(); ~list(); bool empty()const;//判断是否为空 void insert_at_head(int);//在头部插入 void insert_at_tail(int);//在尾部插入 void delete_from_head();//从头删除 void delete_from_tail();//从尾删除 int head()const;//读取头部元素 int tail()const;//读取尾部元素 };要求定义类型stack，表示int栈，stack需要复合list的对象，并实现函数：入栈push，出栈pop

6 假设已经存在以下类型list表示int双向链表，并且所有的函数已经实现 class list { public: list(); ~list(); bool empty()const;//判断是否为空 void insert_at_head(int);//在头部插入 void insert_at_tail(int);//在尾部插入 void delete_from_head();//从头删除 void delete_from_tail();//从尾删除 int head()const;//读取头部元素 int tail()const;//读取尾部元素 };要求定义类型stack，表示int栈，stack需要复合list的对象，并实现函数：入栈push，出栈pop，读栈顶top，判断栈空empty class stack { private: list l; //list子对象 public: void push(int num){l.insert_at_tail(num);}//尾部插入 void pop(){l.delete_from_tail();}//尾部删除 int top(){return l.tail();}//读尾部 bool empty(){return l.empty();}//判断栈空 };

7 假设已经存在以下类型list表示int双向链表，并且所有的函数已经实现 class list { public: list(); ~list(); bool empty()const;//判断是否为空 void insert_at_head(int);//在头部插入 void insert_at_tail(int);//在尾部插入 void delete_from_head();//从头删除 void delete_from_tail();//从尾删除 int head()const;//读取头部元素 int tail()const;//读取尾部元素 };要求定义类型queue，表示int队列，queue需要继承list，并实现函数：入队push，出队pop，读队头front，判断队空empty class queue:protected list { public: void push(int num){insert_at_head(num);}//队头插入 void pop(){delete_from_tail();}//尾部删除 int front(){return head();}//读尾部 bool empty(){return empty();}//判断栈空 };

8 假设已经存在以下类型list表示int双向链表，并且所有的函数已经实现 class list { public: list(); ~list(); bool empty()const;//判断是否为空 void insert_at_head(int);//在头部插入 void insert_at_tail(int);//在尾部插入 void delete_from_head();//从头删除 void delete_from_tail();//从尾删除 int head()const;//读取头部元素 int tail()const;//读取尾部元素 };要求定义类型queue，表示int队列，queue需要复合list，并实现函数：入队push，出队pop，读队头front，判断队空empty class queue { private: list l; public: void push(int num){l.insert_at_head(num);}//队头插入 void pop(){l.delete_from_tail();}//尾部删除 int front(){return l.head();}//读尾部 bool empty(){return l.empty();}//判断栈空 };

9 自定义类型binary_op、plus_op、minus_op、multi_op、divid_op，要求binary_op表示二元的int操作，它的成员函数int op(int,int)const是纯虚函数，plus_op、minus_op、multi_op、divid_op是binary_op的派生类，需要重写（也成覆盖）基类的纯虚函数op，分别实现int数的加减乘除操作。 class binary_op { protected: int x, y; public: virtual int op(int,int)const = 0; }; class plus_op : public binary_op { public: //常成员函数 virtual int op(int,int)const{ return x+y;} }; class minus_op: public binary_op { public: //常成员函数 virtual int op(int,int)const{ return x-y;} }; class multi_op: public binary_op { public: //常成员函数 virtual int op(int,int)const{ return x*y;} }; class divid_op: public binary_op { public: //常成员函数 virtual int op(int,int)const{ if(y!=0) return x/y; else return 0;} };

10 根据原型 template<class T> int min(const T* arr,int len);编写函数模板，实现求数组中首个最小元素下标的功能。#include<iostream> using namespace std;template<class T>int min(const T* arr,int len){int i;for(i=0;i<len;i++){ if(arr[i+1]>arr[i]) return i; } } int main(){int arr[5]={4,3,4,6,8};float arr2[5]={3.0,4.0,2.0};cout<<min<int>(arr,5)<<endl;cout<<min<float>(arr2,5)<<endl;}

11 根据原型 template<class T> int max_end(const T* arr,int len);编写函数模板，实现求数组中最后一个最大元素下标的功能。#include<iostream> using namespace std;template<class T>int max_end(const T* arr,int len){int i;for(i=len-1;i>=0;i--){ if(arr[i]>arr[i-1]) return i; } } int main(){int arr[5]={1,3,4,6,8};float arr2[5]={3.0,4.0,2.0};cout<<max_end<int>(arr,5)<<endl;cout<<max_end<float>(arr2,5)<<endl;}

12 根据原型 int intersection(int*a1,int len1,int*a2,int len2, int *a3);编写函数，为两个无序int数组求交集，结果写入参数a3指向的数组中，并返回交集元素的个数。可以自己编写，也可以利用STL中现有的函数模板#include<iostream> using namespace std;int count=0;int intersection(int*a1,int len1,int*a2,int len2, int *a3){int i,j;for(i=0;i<len1;i++) for(j=0;j<len2;j++) if(a1[i]==a2[j]){ a3[count]=a1[i]; count++; } return count; }//编写函数，为两个无序int数组求交集，结果写入参数a3指向的数组中，并返回交集元素的个数。 int main(){ int arr[5]={1,3,4,6,5}; int arr2[5]={3,4,2},i; int arr3[99]; int* p=arr3; i=intersection(arr,5,arr2,5,p); cout<<i<<endl; for(i=0;i<count;i++) cout<<p[i]<<endl; }