【23xiu.com-爱上秀-教育信息门户网】
23、下列函数定义中，有语法错误的是(D)
A、void fun(int x, int *y){x *= *y;}
B、int * fun(int *x, int y){return x += y;}
C、void fun(int *x, int y){*x += y;}
D、void fun(int x, int *y){*x *= *y;}
24、有朋自远方来，他乘火车，轮船，汽车，飞机来的概率分别是0.3,0.2,0.1,0.4，坐各交通工具迟到的概率分别是1/4,1/3,1/12,0，下列语句中正确的是(CD)
A、如果他准点，那么乘飞机的概率大于等于0.5
B、坐陆路(火车，汽车)交通工具准点机会比坐水路(轮船)要低
C、如果他迟到，乘火车的概率是0.5
D、如果他准点，坐轮船或汽车的概率等于坐火车的概率
第三部分 填空与问答
25、(4分)文件分配表FAT是管理磁盘空间的一种数据结构，用在以链接方式存储文件的系统中记录磁盘分配和追踪空白磁盘块，整个磁盘仅设一张FAT表，其结构如下所示，如果文件块号为2，查找FAT序号为2的内容得知物理块2的后继物理块是5，再查FAT序号为5的内容得知物理块5的后继物理块是7，接着继续查FAT序号为7的内容为“Λ”，即该文件结束标志，
假设磁盘物理块大小为1KB，并且FAT序号以4bits为单位向上扩充空间。请计算下列两块磁盘的FAT最少需要占用多大的存储空间?
(1)一块540MB的硬盘 (2)一块1.2GB的硬盘
分析：(1)磁盘块大小为1KB，540MB的硬盘可以分成540MB/1KB=5.4*105个磁盘块，因此至少需要5.4*105<220个编号，需要20bit存储空间
(2)同理，1.2G至少需要1.2*106<221个编号，为21bit，由于FAT序号以4bits为单位向上扩充，因此需要24bit存储空间
26、(4分)已知如下代码，并在两个线程中同时执行f1和f2，待两个函数都返回后，a的所有可能值是哪些?
int a = 2, b = 0, c = 0;
void f1() void f2()
{ {
a = a * 2; c = a + 11;
a = b; a = c;
} }
分析：考虑四行代码的执行顺序即可
(1)b=a*2,c=a+11,a=c,a=b a=4
(2)b=a*2,c=a+11,a=b,a=c a=13
(3)b=a*2,a=b,c=a+11,a=c a=15
(4)c=a+11,a=c,b=a*2,a=b a=26
27、(6分)设计一个最优算法来查找一n个元素数组中的最大值和最小值，已知一种需要比较2n次的方法，请给一个更优的算法。请特别注意优化时间复杂度的常数。
给出该算法最坏情况下的比较次数和该算法的步骤描述。(不用写代码，不给出比较次数的不得分)
分析：已知的比较2n次的方法，显然是将每个元素和最大值、最小值各比一次，要减少比较次数，可以有多种优化方法：
方法一：一个元素先和最大值比较，如果比最大值大，就不用再和最小值比较(或者先和最小值比较，如果比最小值小，就不用再和最大值比较)，一般情况下，这种优化后的比较次数一定会少于2n
方法二：将数组元素按两个，两个分组，组内两元素有序存放，之后最小值跟组内较小的值比较，最大值只需跟组内较大的值比较，这样每组的比较次数是3，共n/2组，总的时间复杂度是3n/2次。
把数组两两一对分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较，把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是 N/2 次;在前面分组的基础上，那么可以得到结论，最小值一定在每一组的左边部分找，最大值一定在数组的右边部分找，最大值和最小值的查找分别需要比较N/2 次和N/2 次;这样就可以找到最大值和最小值了，比较的次数为
N/2 * 3 = (3N)/2 次
如图会更加清晰：
28、(8分)已知三个升序整数数组a[l]、b[m]、c[n]，请在三个数组中各找一个元素，使得组成的三元组距离最小，三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|)，请设计一求最小三元组距离的最优算法，并分析时间复杂度。(不用写代码，不分析时间复杂度不得分)
解：这道题目有两个关键点：
第一个关键点： max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 --公式(1)
我们假设x1=a[ i ]，x2=b[ j ]，x3=c[ k ]，则
Distance = max(|x1 – x2|, |x1 – x3|, |x2 – x3|) = max( max(|x1 – x2|, |x1 – x3|) , |x2 – x3|) --公式(2)
根据公式(1)，max(|x1 – x2|, |x1 – x3|) = 1/2 ( |2x1 – x2– x3| + |x2 – x3|)，带入公式(2)，得到
Distance = max( 1/2 ( |2x1 – x2– x3| + |x2 – x3|) , |x2 – x3| )
=1/2 * max( |2x1 – x2– x3| , |x2 – x3| ) + 1/2*|x2 – x3| //把相同部分1/2*|x2 – x3|分离出来
=1/2 * max( |2x1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一个整体，使用公式(1)
=1/2 * 1/2 *((|2x1 – 2x2| + |2x1 – 2x3|) + 1/2*|x2 – x3|
=1/2 *|x1 – x2| + 1/2 * |x1 – x3| + 1/2*|x2 – x3|
=1/2 *(|x1 – x2| + |x1 – x3| + |x2 – x3|) //求出来了等价公式，完毕!
第二个关键点：如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值，x1，x2，x3，分别是三个数组中的任意一个数，这一题，我只是做到了上面的推导，后面的算法设计是由csdn上的两个朋友想出来的方法，他们的CSDN的ID分别为 “云梦泽” 和 “ shuyechengying”.
算法思想是：
用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针，再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n)
代码如下：
#include
#include
#include
#define l 3
#define m 4
#define n 6
int Mymin(int a, int b, int c)
{
int Min = a < b ? a : b;
Min = Min < c ? Min : c;
return Min;
}
int Solvingviolence(int a[], int b[], int c[])
{
//暴力解法，大家都会，不用过多介绍了!
int i = 0, j = 0, k = 0;
int MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
// int store[3] = {0};
int Sum = 0;
for(i = 0; i < l; i++)
{
for(j = 0; j < m; j++)
{
for(k = 0; k < n; k++)
{
Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
if(MinSum > Sum)
{
MinSum = Sum;
// store[0] = i;
// store[1] = j;
// store[2] = k;
}
}
}
}
// printf("the min is %d\n", minABC);
// printf("the three number is %-3d%-3d%-3d\n", a[store[0]], b[store[1]], c[store[2]]);
return MinSum;
}
int MinDistance(int a[], int b[], int c[])
{
int MinSum = 0; //最小的绝对值和
int Sum = 0; //计算三个绝对值的和，与最小值做比较
int MinOFabc = 0; // a[i] , b[j] ,c[k]的最小值
int cnt = 0; //循环次数统计，最多是l + m + n次
int i = 0, j = 0, k = 0; //a,b,c三个数组的下标索引
MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
for(cnt = 0; cnt <= l + m + n; cnt++)
{
Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
MinSum = MinSum < Sum ? MinSum : Sum;
MinOFabc = Mymin(a[i] ,b[j] ,c[k]);//找到a[i] ,b[j] ,c[k]的最小值
//判断哪个是最小值，做相应的索引移动
if(MinOFabc == a[i])
{
if(++i >= l) break;
}//a[i]最小,移动i
if(MinOFabc == b[j])
{
if(++j >= m) break;
}//b[j]最小,移动j
if(MinOFabc == c[k])
{
if(++k >= n) break;
}//c[k]最小,移动k
}
return MinSum;
}
int main(void)
{
int a[l] = {5, 6, 7};
int b[m] = {13, 14, 15, 17};
int c[n] = {19, 22, 24, 29, 32, 42};
printf("\nBy violent solution ,the min is %d\n", Solvingviolence(a, b, c));
printf("\nBy Optimal solution ,the min is %d\n", MinDistance(a, b, c));
return 0;
}
29(8分)在黑板上写下50个数字：1至50。在接下来的49轮操作中，每次做如下动作：选取两个黑板上的数字a和b檫去，在黑板上写|b-a|。请问最后一次动作之后剩下数字可能是什么?为什么?(不用写代码，不写原因不得分)
分析：50以内的奇数都有可能
【算法工程师 附加题】请设计一个算法，在满足质因数仅为3,5,7或其组合的数中，找出第K大的数。比如K=1,2,3时，分别应返回3,5,7。要求算法时间复杂度最优。
分析：满足质因数仅为3,5,7或其组合的数，貌似可以表示成a(n)=3i*5j*7k，然后用基数排序，貌似方法不好使……