一.編程題

1.用C語(yǔ)言寫一個(gè)函數(shù)來(lái)執(zhí)行一串任務(wù)。任務(wù)是互相依賴的。比如B任務(wù)依賴A任務(wù)，則A完成B才能執(zhí)行。不考慮并發(fā)限制，假設(shè)所有的任務(wù)都能一次執(zhí)行成功，所有的任務(wù)執(zhí)行時(shí)間都相等。任務(wù)數(shù)據(jù)結(jié)構(gòu)原型為：

typedef struct {

int id；//該任務(wù)的ID

int *child；//該任務(wù)依賴的任務(wù)的ID

int child_num;//該任務(wù)依賴的任務(wù)的個(gè)數(shù)

}task；

函數(shù)原型：

bool doschedule（task*pask，int task_num ）;

以下函數(shù)可以直接調(diào)用：

void dotask（int id）；//執(zhí)行一個(gè)進(jìn)程

int waittask（int timeout）；//等待timeout時(shí)間，并返回一個(gè)執(zhí)行成功的任務(wù)的id，如果沒(méi)有任務(wù)在時(shí)間片內(nèi)完成，則返回-1

bool killtask（int id）；//殺掉一個(gè)進(jìn)程

2.如果考慮并發(fā)限制，應(yīng)該怎么改進(jìn)？

二。簡(jiǎn)答題

1.闡述棧和堆在生命周期、速度、內(nèi)存性能等方面的不同點(diǎn)。假如現(xiàn)在有一個(gè)緩沖區(qū)域絕大多數(shù)只需要1KB空間，極少數(shù)極端情況下需要100MB，怎么樣合理分配內(nèi)存？

2.說(shuō)明以下包含const修飾符的語(yǔ)句的意義

a). double * ptr=&value；

b). const double * ptr=&value;

c). double *const ptr =&value;

d).const double *const  ptr=&value;

3.請(qǐng)問(wèn)c語(yǔ)言中怎么去除const修飾？

比如：

const double value=0.2f；

double *ptr；

ptr怎么樣獲取value的值？

三.算法設(shè)計(jì)題

1.在一維坐標(biāo)軸上存在許多條線段，用最簡(jiǎn)單的算法找出重合長(zhǎng)度最長(zhǎng)得兩條線段。比如線段A（1,5）、B（2,8）、C（3,9），則B和C的重合長(zhǎng)度最長(zhǎng)，為5.

2.是一道求最短路徑的問(wèn)題，例子給出了一個(gè)包含5個(gè)節(jié)點(diǎn)的有向圖，標(biāo)有權(quán)值，求始點(diǎn)到終點(diǎn)的距離，圖就不畫了 。 

這兩道題都需要詳細(xì)寫明算法與函數(shù)設(shè)計(jì) -_-

四.系統(tǒng)設(shè)計(jì)題

百度的某某服務(wù)機(jī)制類似于CS（customer-server），有時(shí)候大量用戶訪問(wèn)服務(wù)器S，導(dǎo)致S運(yùn)行效率緩慢。為了提升效率，擬在C上利用一些空余的結(jié)果空間作為緩存。已知在C的一臺(tái)客戶機(jī)上，每天接收1000w query，其中500w uniq query，每個(gè)query 5KB，客戶機(jī)內(nèi)存3GB，硬盤500GB。做出一個(gè)方案，說(shuō)明系統(tǒng)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、性能優(yōu)化等方面的設(shè)計(jì)。