快速排序。（2018）
它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。
请仔细阅读分析源码，填写划线部分缺失的内容。
#include <stdio.h>
int quick_select(int a[], int l, int r, int k)
{
int p = rand() % (r - l + 1) + l;
int x = a[p];
{ int t = a[p]; a[p] = a[r]; a[r] = t;}
int i = l, j = r;
while(i < j)
{
while(i < j && a[i] < x) i++;
if(i < j) {
a[j] = a[i];
j--;
}
while(i < j && a[j] > x) j--;
if(i < j) {
a[i] = a[j];
i++;
}
}
a[i] = x;
p = i;
if(i - l + 1 == k) return a[i];
if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
else return quick_select(a, l, i - 1, k);
}
int main()
{
int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
printf("%d\n", quick_select(a, 0, 14, 5));
return 0;
}
注意：只填写划线部分缺少的代码，不要抄写已经存在的代码或符号。
答案： a, i+1, r, k-(i-l+1)
取数位（2017）
求1个整数的第k位数字有很多种方法。
以下的方法就是一种。
// 求x用10进制表示时的数位长度
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
// 取x的第k位数字
int f(int x, int k){
if(len(x)-k==0) return x%10;
return _____________________; //填空
}
int main()
{
int x = 23574;
printf("%d\n", f(x,3));
return 0;
} 对于题目中的测试数据，应该打印5。
请仔细分析源码，并补充划线部分所缺少的代码。
注意：只提交缺失的代码，不要填写任何已有内容或说明性的文字。
答案： f(x/10,k) 。
最大公共子串(2017)
最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路，并补全划线部分缺失的代码。
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __________________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
} 答案： a[i-1][j-1]+1.
快速排序（2016）
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
#include <stdio.h>
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while(i<r && a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a,i,j);
}
______________________;
return j;
}
void quicksort(int a[], int p, int r)
{
if(p<r)
{
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int main()
{
int i;
int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
int N = 12;
quicksort(a, 0, N-1);
for(i=0; i<N; i++) printf("%d ",a[i]);
printf("\n");
return 0;
} 答案：swap(a,p,j).
抽签（2016）
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
….
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
….
(以下省略，总共101行)
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
void f(int a[], int k, int m, char b[])
{
int i,j;
if(k==N){
b[M] = 0;
if(m==0) printf("%s\n",b);
return;
}
for(i=0; i<=a[k]; i++){
for(j=0; j<i; j++) b[M-m+j] = k+'A';
______________________; //填空位置
}
}
int main()
{
int a[N] = {4,2,2,1,1,3};
char b[BUF];
f(a,0,M,b);
return 0;
} 答案：f(a,k+1, m-i,b) 。
m-i是减去每组相应的人数。
格子中输出（2015）
StringInGrid函数会在一个指定大小的格子中打印指定的字符串。
要求字符串在水平、垂直两个方向上都居中。
如果字符串太长，就截断。
如果不能恰好居中，可以稍稍偏左或者偏上一点。
下面的程序实现这个逻辑，请填写划线部分缺少的代码。
#include <stdio.h>
#include <string.h>
void StringInGrid(intwidth, int height, const char* s)
{
int i,k;
char buf[1000];
strcpy(buf, s);
if(strlen(s)>width-2) buf[width-2]=0;
printf("+");
for(i=0;i<width-2;i++) printf("-");
printf("+\n");
for(k=1; k<(height-1)/2;k++){
printf("|");
for(i=0;i<width-2;i++) printf(" ");
printf("|\n");
}
printf("|");
printf("%*s%s%*s",_____________________________________________); //填空
printf("|\n");
for(k=(height-1)/2+1; k<height-1; k++){
printf("|");
for(i=0;i<width-2;i++) printf(" ");
printf("|\n");
}
printf("+");
for(i=0;i<width-2;i++) printf("-");
printf("+\n");
}
int main()
{
StringInGrid(20,6,"abcd1234");
return 0;
} * 修饰符在printf中的含义完全不同。如果写成printf(“%6d”, 123)，这是设置域宽的意思。同理，%6s也是域宽。* 修饰符正是用来更灵活的控制域宽。使用%*s，表示这里的具体域宽值由后面的实参决定，如printf(“%*s”, 6, “abc”)就是把”abc”放到在域宽为6的空间中右对齐。
答案：(width-strlen(s)-2)/2," ",s,(width-strlen(s)-2)/2," " 。
九数组分数（2015）
1,2,3...9 这九个数字组成一个分数，其值恰好为1/3，如何组法？
下面的程序实现了该功能，请填写划线部分缺失的代码。
#include <stdio.h>
void test(int x[])
{
int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
if(a*3==b)printf("%d / %d\n", a, b);
}
void f(int x[], int k)
{
int i,t;
if(k>=9){
test(x);
return;
}
for(i=k;i<9; i++){
{t=x[k];x[k]=x[i]; x[i]=t;}
f(x,k+1);
_____________________________________________// 填空处
}
}
int main()
{
int x[] = {1,2,3,4,5,6,7,8,9};
f(x,0);
return0;
} 答案：{ t=x[k]; x[k]=x[i]; x[i]=t; }
交换值之后，调用f(x,k+1);之后，要把值交换回来。
转方阵（2012）
对一个方阵转置，就是把原来的行号变列号，原来的列号变行号
例如，如下的方阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
转置后变为：
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16
但，如果是对该方阵顺时针旋转（不是转置），却是如下结果：
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
下面的代码实现的功能就是要把一个方阵顺时针旋转。
void rotate(int* x, int rank)
{
int* y = (int*)malloc(___________________); // 填空
for(int i=0; i<rank * rank; i++)
{
y[_________________________] = x[i]; // 填空
}
for(i=0; i<rank*rank; i++)
{
x[i] = y[i];
}
free(y);
}
int main(int argc, char* argv[])
{
int x[4][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
int rank = 4;
rotate(&x[0][0], rank);
for(int i=0; i<rank; i++)
{
for(int j=0; j<rank; j++)
{
printf("%4d", x[i][j]);
}
printf("\n");
}
return 0;
} 
京公网安备 11010502036488号