完成函数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;
}
}
1) 题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;
}
2) 题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;
}
}
3) 题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;
}
4) 题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;
}
5) 题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;
}
6) 题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)
return false;
Node *cur=lp->tail;
lp->tail=cur->p;
if(lp->tail==NULL)
lp->head=NULL;
else
lp->tail->n=NULL;
free(cur);
return true;
}
7) 题8
代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f返回该树的深度，提示可用先序遍历。
答案：
intf(const Node *root) {
if(root==NULL)
return 0;
int l=f(root->left);
int r=f(root->right);
return l>r?l+1:r+1;
}
8) 题9
代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f释放该树全部节点占用的内存（假设节点内存来自堆区），提示可用后序遍历。
答案：
intf(Node *root) {
if(root==NULL)
return;
f(root->left);
f(root->right);
free(root);
}
9) 题10
代码中，结构体Node表示单链表的节点，data是整型数据域，next是指向后继的指针；完成函数f的实现，参数head是某链表的头节点，参数x表示一个整数，要求函数f返回链表中数据域大于x的节点的个数。
答案：
intf(Node *head, int x) {
Node *p;
int cnt=0;
for(p=head; p!=NULL; p=p->next)
if(p->data>x)
cnt++;
return cnt;
}
10)题11
完成函数f的实现，参数n表示正整数，参数a表示二维数组首地址，a表示的二维数组用于存储n个系欸但有向图的邻接矩阵，a[i][j]==1时表示节点i到节点j有边，函数f需要返回有向图中出度大于入度的顶点的个数。
答案：
intf(int n, const _Bool a[n][n]) {
int i, j, cnt=0;
for(i=0; i<n; i++) {
int in=0, out=0;
for(j=0; j<n; j++)
if(a[j][i])
in++;
if(a[i][j])
out++;
if(out>in)
cnt++;
}
return cnt;
}
11)题12
完成函数f的实现，参数n表示正整数，参数a表示一个一位数组首地址，i表示一个正整数（0<=i<n），a表示的一维数组用于存储n个节点无向图的邻接矩阵的上三角压缩存储，函数f需要返回无向图中节点i的度。
答案：
intf(int n, const _Bool a[], int i) {
int j, k=0;
int m=n-i;
for(j=0; j<i; j++)
k+=(n--);
int cnt=0;
for(j=k; j<k+m; j++)
if(a[j])
cnt++;
return cnt;
}
12)题13
完成函数f的实现，参数s表示字符串首地址，字符串中仅有‘（’和‘）’，函数f返回一个布尔值，当字符串中的‘（’和‘）’恰好匹配时返回真，否则返回假。
答案：
_Boolf(const char *s) {
int stack=0, i;//stack表示栈，stack=0时栈空
for(i=0; s[i]!='\0'; i++)
if(s[i]=='{')
stack++;
else if(s[i]=='}' && stack>0)
stack--;
else
return false;
if(stack==0)
return true;
return false;
}
13)题14
完成函数f的实现，参数s1和s2分别表示两个字符串首地址，要求函数f实现不区分大小写字母的字符串比较，当s1比s2小时f返回负数，当s1比s2大时返回正数，字母串相等返回0。
答案
intf(const char *s1, const char *s2) {
int i;
for(i=0; s1[i]!='\0' || s2[i]!='\0'; i++)
if(s1[i]==s2[i]) {
continue;
} else if(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;
} else if(s1[i]>s2[i]) {
return 1;
} else {
return -1;
}
return 0;
}
14)题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, int la, int *b, int lb, int *c) {
int i, j, k;
for(i=0, j=0, k=0; i<la &&j<lb; k++)
if(b[j]<a[i])
c[k]=b[j++];
else
c[k]=a[i++];
while(i<la)
c[k++]=a[i++];
while(j<lb)
c[k++]=b[j++];
}
答案：
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;
}
}
1) 题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;
}
2) 题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;
}
}
3) 题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;
}
4) 题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;
}
5) 题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;
}
6) 题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)
return false;
Node *cur=lp->tail;
lp->tail=cur->p;
if(lp->tail==NULL)
lp->head=NULL;
else
lp->tail->n=NULL;
free(cur);
return true;
}
7) 题8
代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f返回该树的深度，提示可用先序遍历。
答案：
intf(const Node *root) {
if(root==NULL)
return 0;
int l=f(root->left);
int r=f(root->right);
return l>r?l+1:r+1;
}
8) 题9
代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f释放该树全部节点占用的内存（假设节点内存来自堆区），提示可用后序遍历。
答案：
intf(Node *root) {
if(root==NULL)
return;
f(root->left);
f(root->right);
free(root);
}
9) 题10
代码中，结构体Node表示单链表的节点，data是整型数据域，next是指向后继的指针；完成函数f的实现，参数head是某链表的头节点，参数x表示一个整数，要求函数f返回链表中数据域大于x的节点的个数。
答案：
intf(Node *head, int x) {
Node *p;
int cnt=0;
for(p=head; p!=NULL; p=p->next)
if(p->data>x)
cnt++;
return cnt;
}
10)题11
完成函数f的实现，参数n表示正整数，参数a表示二维数组首地址，a表示的二维数组用于存储n个系欸但有向图的邻接矩阵，a[i][j]==1时表示节点i到节点j有边，函数f需要返回有向图中出度大于入度的顶点的个数。
答案：
intf(int n, const _Bool a[n][n]) {
int i, j, cnt=0;
for(i=0; i<n; i++) {
int in=0, out=0;
for(j=0; j<n; j++)
if(a[j][i])
in++;
if(a[i][j])
out++;
if(out>in)
cnt++;
}
return cnt;
}
11)题12
完成函数f的实现，参数n表示正整数，参数a表示一个一位数组首地址，i表示一个正整数（0<=i<n），a表示的一维数组用于存储n个节点无向图的邻接矩阵的上三角压缩存储，函数f需要返回无向图中节点i的度。
答案：
intf(int n, const _Bool a[], int i) {
int j, k=0;
int m=n-i;
for(j=0; j<i; j++)
k+=(n--);
int cnt=0;
for(j=k; j<k+m; j++)
if(a[j])
cnt++;
return cnt;
}
12)题13
完成函数f的实现，参数s表示字符串首地址，字符串中仅有‘（’和‘）’，函数f返回一个布尔值，当字符串中的‘（’和‘）’恰好匹配时返回真，否则返回假。
答案：
_Boolf(const char *s) {
int stack=0, i;//stack表示栈，stack=0时栈空
for(i=0; s[i]!='\0'; i++)
if(s[i]=='{')
stack++;
else if(s[i]=='}' && stack>0)
stack--;
else
return false;
if(stack==0)
return true;
return false;
}
13)题14
完成函数f的实现，参数s1和s2分别表示两个字符串首地址，要求函数f实现不区分大小写字母的字符串比较，当s1比s2小时f返回负数，当s1比s2大时返回正数，字母串相等返回0。
答案
intf(const char *s1, const char *s2) {
int i;
for(i=0; s1[i]!='\0' || s2[i]!='\0'; i++)
if(s1[i]==s2[i]) {
continue;
} else if(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;
} else if(s1[i]>s2[i]) {
return 1;
} else {
return -1;
}
return 0;
}
14)题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, int la, int *b, int lb, int *c) {
int i, j, k;
for(i=0, j=0, k=0; i<la &&j<lb; k++)
if(b[j]<a[i])
c[k]=b[j++];
else
c[k]=a[i++];
while(i<la)
c[k++]=a[i++];
while(j<lb)
c[k++]=b[j++];
}
