23、下列函數(shù)定義中，有語法錯(cuò)誤的是(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、有朋自遠(yuǎn)方來，他乘火車，輪船，汽車，飛機(jī)來的概率分別是0.3,0.2,0.1,0.4，坐各交通工具遲到的概率分別是1/4,1/3,1/12,0，下列語句中正確的是(CD)

　　A、如果他準(zhǔn)點(diǎn)，那么乘飛機(jī)的概率大于等于0.5

　　B、坐陸路(火車，汽車)交通工具準(zhǔn)點(diǎn)機(jī)會(huì)比坐水路(輪船)要低

　　C、如果他遲到，乘火車的概率是0.5

　　D、如果他準(zhǔn)點(diǎn)，坐輪船或汽車的概率等于坐火車的概率

　　第三部分 填空與問答

　　25、(4分)文件分配表FAT是管理磁盤空間的一種數(shù)據(jù)結(jié)構(gòu)，用在以鏈接方式存儲(chǔ)文件的系統(tǒng)中記錄磁盤分配和追蹤空白磁盤塊，整個(gè)磁盤僅設(shè)一張F(tuán)AT表，其結(jié)構(gòu)如下所示，如果文件塊號(hào)為2，查找FAT序號(hào)為2的內(nèi)容得知物理塊2的后繼物理塊是5，再查FAT序號(hào)為5的內(nèi)容得知物理塊5的后繼物理塊是7，接著繼續(xù)查FAT序號(hào)為7的內(nèi)容為“Λ”，即該文件結(jié)束標(biāo)志，

　　假設(shè)磁盤物理塊大小為1KB，并且FAT序號(hào)以4bits為單位向上擴(kuò)充空間。請(qǐng)計(jì)算下列兩塊磁盤的FAT最少需要占用多大的存儲(chǔ)空間?

　　(1)一塊540MB的硬盤 (2)一塊1.2GB的硬盤

　　分析：(1)磁盤塊大小為1KB，540MB的硬盤可以分成540MB/1KB=5.4105個(gè)磁盤塊，因此至少需要5.4105<220個(gè)編號(hào)，需要20bit存儲(chǔ)空間

　　(2)同理，1.2G至少需要1.2106<221個(gè)編號(hào)，為21bit，由于FAT序號(hào)以4bits為單位向上擴(kuò)充，因此需要24bit存儲(chǔ)空間

　　26、(4分)已知如下代碼，并在兩個(gè)線程中同時(shí)執(zhí)行f1和f2，待兩個(gè)函數(shù)都返回后，a的所有可能值是哪些?

　　int a = 2, b = 0, c = 0;

　　void f1() void f2()

　　{ {

　　a = a 2; c = a + 11;

　　a = b; a = c;

　　} }

　　分析：考慮四行代碼的執(zhí)行順序即可

　　(1)b=a2,c=a+11,a=c,a=b a=4

　　(2)b=a2,c=a+11,a=b,a=c a=13

　　(3)b=a2,a=b,c=a+11,a=c a=15

　　(4)c=a+11,a=c,b=a2,a=b a=26

　　27、(6分)設(shè)計(jì)一個(gè)最優(yōu)算法來查找一n個(gè)元素?cái)?shù)組中的最大值和最小值，已知一種需要比較2n次的方法，請(qǐng)給一個(gè)更優(yōu)的算法。請(qǐng)?zhí)貏e注意優(yōu)化時(shí)間復(fù)雜度的常數(shù)。

　　給出該算法最壞情況下的比較次數(shù)和該算法的步驟描述。(不用寫代碼，不給出比較次數(shù)的不得分)

　　分析：已知的比較2n次的方法，顯然是將每個(gè)元素和最大值、最小值各比一次，要減少比較次數(shù)，可以有多種優(yōu)化方法：

　　方法一：一個(gè)元素先和最大值比較，如果比最大值大，就不用再和最小值比較(或者先和最小值比較，如果比最小值小，就不用再和最大值比較)，一般情況下，這種優(yōu)化后的比較次數(shù)一定會(huì)少于2n

　　方法二：將數(shù)組元素按兩個(gè)，兩個(gè)分組，組內(nèi)兩元素有序存放，之后最小值跟組內(nèi)較小的值比較，最大值只需跟組內(nèi)較大的值比較，這樣每組的比較次數(shù)是3，共n/2組，總的時(shí)間復(fù)雜度是3n/2次。

　　把數(shù)組兩兩一對(duì)分組，如果數(shù)組元素個(gè)數(shù)為奇數(shù)，就最后單獨(dú)分一個(gè)，然后分別對(duì)每一組的兩個(gè)數(shù)比較，把小的放在左邊，大的放在右邊，這樣遍歷下來，總共比較的次數(shù)是 N/2 次;在前面分組的基礎(chǔ)上，那么可以得到結(jié)論，最小值一定在每一組的左邊部分找，最大值一定在數(shù)組的右邊部分找，最大值和最小值的查找分別需要比較N/2 次和N/2 次;這樣就可以找到最大值和最小值了，比較的次數(shù)為

　　N/2 3 = (3N)/2 次

　　如圖會(huì)更加清晰：

　　28、(8分)已知三個(gè)升序整數(shù)數(shù)組a[l]、b[m]、c[n]，請(qǐng)?jiān)谌齻�(gè)數(shù)組中各找一個(gè)元素，使得組成的三元組距離最小，三元組的距離定義是：假設(shè)a[i]、b[j]和c[k]是一個(gè)三元組，那么距離為distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|)，請(qǐng)?jiān)O(shè)計(jì)一求最小三元組距離的最優(yōu)算法，并分析時(shí)間復(fù)雜度。(不用寫代碼，不分析時(shí)間復(fù)雜度不得分)

　　解：這道題目有兩個(gè)關(guān)鍵點(diǎn)：

　　第一個(gè)關(guān)鍵點(diǎn)：max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 --公式(1)

　　我們假設(shè)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)

　　根據(jù)公式(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)看成一個(gè)整體，使用公式(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|) //求出來了等價(jià)公式，完畢!

　　第二個(gè)關(guān)鍵點(diǎn)：如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值，x1，x2，x3，分別是三個(gè)數(shù)組中的任意一個(gè)數(shù)，這一題，我只是做到了上面的推導(dǎo)，后面的算法設(shè)計(jì)是由csdn上的兩個(gè)朋友想出來的方法，他們的CSDN的ID分別為 “云夢(mèng)澤” 和 “ shuyechengying”.

　　算法思想是：

　　用三個(gè)指針分別指向a,b,c中最小的數(shù)，計(jì)算一次他們最大距離的Distance ，然后在移動(dòng)三個(gè)數(shù)中較小的數(shù)組指針，再計(jì)算一次，每次移動(dòng)一個(gè)，直到其中一個(gè)數(shù)組結(jié)束為止，最慢(l+ m + n)次，復(fù)雜度為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[])

　　{

　　//暴力解法，大家都會(huì)，不用過多介紹了!

　　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 = j;

　　// store = k;

　　}

　　}

　　}

　　}

　　// printf("the min is %d\n", minABC);

　　// printf("the three number is %-3d%-3d%-3d\n", a[store[0]], b[store], c[store]);

　　return MinSum;

　　}

　　int MinDistance(int a[], int b[], int c[])

　　{

　　int MinSum = 0; //最小的絕對(duì)值和

　　int Sum = 0; //計(jì)算三個(gè)絕對(duì)值的和，與最小值做比較

　　int MinOFabc = 0; // a[i] , b[j] ,c[k]的最小值

　　int cnt = 0; //循環(huán)次數(shù)統(tǒng)計(jì)，最多是l + m + n次

　　int i = 0, j = 0, k = 0; //a,b,c三個(gè)數(shù)組的下標(biāo)索引

　　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]的最小值

　　//判斷哪個(gè)是最小值，做相應(yīng)的索引移動(dòng)

　　if(MinOFabc == a[i])

　　{

　　if(++i >= l) break;

　　}//a[i]最小,移動(dòng)i

　　if(MinOFabc == b[j])

　　{

　　if(++j >= m) break;

　　}//b[j]最小,移動(dòng)j

　　if(MinOFabc == c[k])

　　{

　　if(++k >= n) break;

　　}//c[k]最小,移動(dòng)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個(gè)數(shù)字：1至50。在接下來的49輪操作中，每次做如下動(dòng)作：選取兩個(gè)黑板上的數(shù)字a和b檫去，在黑板上寫|b-a|。請(qǐng)問最后一次動(dòng)作之后剩下數(shù)字可能是什么?為什么?(不用寫代碼，不寫原因不得分)

　　分析：50以內(nèi)的奇數(shù)都有可能

　　【算法工程師 附加題】請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，在滿足質(zhì)因數(shù)僅為3,5,7或其組合的數(shù)中，找出第K大的數(shù)。比如K=1,2,3時(shí)，分別應(yīng)返回3,5,7。要求算法時(shí)間復(fù)雜度最優(yōu)。

　　分析：滿足質(zhì)因數(shù)僅為3,5,7或其組合的數(shù)，貌似可以表示成a(n)=3i5j7k，然后用基數(shù)排序，貌似方法不好使……