找第k小问题的分治算法. 算法开始将n个数分成5个1组，共个组，然后取每组的中位数构成集合M，递归利用找第k小算法，计算M的中位数，用作为标准划分数组，得到子问题和. 递归求解其中一个子问题即可. 如果开始分组时是3个元素一组，算法在最坏情况下的时间复杂度将达到，如果开始分组时取7个元素一组，那么用划分数组后产生的子问题最大规模将达到（），算法在最坏情况下的时间复杂度是（），两个括号里分别应该填：

找第k小问题的分治算法. 算法开始将n个数分成5个1组，共个组，然后取每组的中位数构成集合M，递归利用找第k小算法，计算M的中位数，用作为标准划分数组，得到子问题和. 递归求解其中一个子问题即可. 如果开始分组时是3个元素一组，算法在最坏情况下的时间复杂度将达到，如果开始分组时取7个元素一组，那么用划分数组后产生的子问题最大规模将达到（ ），算法在最坏情况下的时间复杂度是（ ），两个括号里分别应该填：

A、

B、

C、

D、

A、O(nlogn)

B、O(n^2)

C、O(n)

D、O(logn)

编写一个程序，求出两个数m和n的最大公约数和最小公倍数。 编程提示：求最大公约数的方法有三种： 1．从两个数中较小数的开始向下判断，如果找到一个整数能同时被m和n整除，则终止循环。设n为m和n中较小的数，则如下程序段可实现： for(k=n; k>=1; k--) if(m%k==0 && n%k ==0) break; k即为最大公约数。/* c5-2.c 求最大公约数算法1 */ #include "stdio.h" #include <stdlib.h> int main( ) { return 0; } 2．从整数1开始向上找，直至m和n中较小的数，每找到一个能同时被m和n整除的整数，将其存入一个变量中，当循环结束时，变量中存放的即为最大公约数。设n为m和n中较小的数，则如下程序段可实现： for(k=1; k<=n; k++) if(m%k="=0" && n%k="=0)" x="k;" 变量x的值即为最大公约数。 * c5-3.c 求最大公约数算法2 #include> #include <stdlib.h> int main( ) { return 0; } 3．用辗转相除法，即将求m和n的最大公约数问题转化为求其中的除数和两个数相除所得余数的公约数。每次循环中，先求两个数的余数，然后以除数作为被除数，以余数作为除数，当余数为0时结束循环，此时除数即为最大公约数。设m和n中n为较小的数，则可用如下程序段实现： b=m%n; while(b!=0) { m=n; n=b; b=m%n;} printf("%d\n",n); /* c5-4.c 求最大公约数算法3 */ #include <stdio.h> #include <stdlib.h> int main( ) { return 0; } 两个数的最大公约数和最小公倍数的关系为：最小公倍数=m*n/最大公约数,可利用此关系进行程序设计。

面试题:最小的k个数

题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

对于n个元素的关键字序列{k1，k2，…，kn}，当且仅当满足关系ki≤K2i且ki≤K2i(2i≤n,2i+1≤n)称其为小根堆，反之则为大根堆。以下序列中，(38)不符合堆的定义。

A．(5，10，15，76，39，27，18)

B．(5，10，18，76，39，27，15)

C．(59，27，36，15，8，25，9)

D．(59，36，27，15，8，25，9)

【题目描述】

 阅读以下说明和流程图，填补流程图和问题中的空缺(1)～(5)，将解答填入答题纸的对应栏内。

【说明】

   设整型数组A[1：N]每个元素的值都是1到N之间的正整数。一般来说，其中会有一些元素的值是重复的，也有些数未出现在数组中。下面流程图的功能是查缺查重，即找出A[1：N]中所有缺的或重复的整数，并计算其出现的次数（出现次数为0时表示缺）。流程图中采用的算法思想是将数组A的下标与值看作是整数集[1：N]加上的一个映射，并用数组C[1：N]记录各整数出现的次数，需输出所有缺少的或重复的数及其出现的次数。

【流程图】

【问题】

 如果数组A[1：5]的元素分别为{3，2，5，5，1}，则算法流程结束后输出结果为： (5) 。

 输出格式为：缺少或重复的元素，次数（0表示缺少）

【我提交的答案】：

【参考答案分析】：

【我的疑问】

c[k]=0不是结束循环了嘛，为什么还会输出

阅读以下程序并填空。

该程序的功能是：输入10个整数，将其中的前5个数从小到大排序，然后输出这10个数。

include <stdio.h>

void sort(①__________) ① _________

{int i,m,t;

for(i=0;i<n-1;i++)

for(m=i+1;m<n;m++)

if(②_________) ②_________

{t=a[m];a[m]=a[i];a[i]=t;}

}

main()

{int k,a[10];

for(k=0;k<10;k++)

scanf("%d",&a[k]);

③_________; ③_________

for(k=0;k<10;k++)

printf("%d",a[k]);

}

下列程序的功能是：将一正整数序列{K1，K2，…，K9}重新排成一个新的序列。新序列中，比K1小的数都在K1的左面(后续的再向左存放)，比K1大的数都在K1的右面(后续的再向右存放)，从K1向右扫描。要求编写函数jsValue()实现此功能，最后调用函数writeDat()把新序列输出到文件out90.dat中。

说明：在程序中已给出了10个序列，每个序列中有9个正整数，并存入数组a[10][9]中，分别求出这10个新序列。

例如：序列排序前 {6，8，9，1，2，5，4，7，3}

序列排序后 {3，4，5，2，1，6，8，9，7}

注意：部分源程序已给出。

请勿改动主函数main()和写函数writeDat()的内容。

试题程序：

include＜stdio.h＞

jsValue(int a[10][9])

{

}

main ()

{

int a[10] [9]={{6,8,9,1,2,5,4,7,3},

{3,5,8,9,1,2,6,4,7},

{8,2,1,9,3,5,4,6,7},

{3,5,1,2,9,8,6,7,4},

{4,7,8,9,1,2,5,3,6},

{4,7,3,5,1,2,6,8,9},

{9,1,3,5,8,6,2,4,7},

{2,6,1,9,8,3,5,7,4},

{5,3,7,9,1,8,2,6,4},

{7,1,3,2,5,8,9,4,6},

};

int i,j;

jsValue (a);

for (i=0;i＜10; i++)

{

for(j=0;j＜9;j++)

{

printf("%d",a[i] [j]);

if(j＜=7) printf(",");

}

printf ("\n");

}

writeDat (a);

}

writeDat (int a[10] [9])

{

FILE *fp;

int i,j;

fp=fopen ("out90.dat", "w");

for (i=0;i＜10; i++)

{

for(j=0;j＜9;j++)

{

fprintf (fp, "%d", a [i] [j] );

if (j＜=7) fprintf (fp, ", ");

}

fprintf (fp, "\n");

}

fclose (fp);

}

方程(x-1)(x-2)＝k2的一个根大于1，另一个根小于1。

(1)是＞5

(2)k＜10

一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1一1，余下的，n一2k-1+1个结点在第七层的任一位置上。( )【北京师范大学2005三、2(5分)】

此题为判断题(对，错)。