三、綜合題

　　1、有一顆結(jié)構(gòu)如下的樹(shù)，對(duì)其做鏡像反轉(zhuǎn)后如下，請(qǐng)寫(xiě)出能實(shí)現(xiàn)該功能的代碼。注意：請(qǐng)勿對(duì)該樹(shù)做任何假設(shè)，它不一定是衡樹(shù)，也不一定有序。

　　1 1

　　/ | \ / | \

　　2 3 4 4 3 2

　　/|\ /\ | | / \ / | \

　　6 5 7 8 9 10 10 9 8 7 5 6

　　答：以孩子、兄弟的存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)這棵樹(shù)，使之成為一顆二叉樹(shù)，然后對(duì)二叉樹(shù)進(jìn)行鏈表的轉(zhuǎn)換。

　　[cpp] view plaincopytypedef struct TreeNode

　　{

　　int data;

　　struct TreeNode *firstchild;

　　struct TreeNode *nextsibling;

　　}TreeNode,*Tree;

　　void MirrorTree(Tree root)

　　{

　　if(!root)

　　return ;

　　if(root->firstchild)

　　{

　　Tree p=root->firstchild;

　　Tree cur=p->nextsibling;

　　p->nextsibling=NULL;

　　while(cur)

　　{

　　Tree curnext=cur->nextsibling;

　　cur->nextsibling=p;

　　if(p->firstchild)

　　MirrorTree(p);

　　p=cur;

　　cur=curnext;

　　}

　　root->firstchild=p;

　　}

　　}

　　int main(void)

　　{

　　TreeNode *root=(TreeNode *)malloc(sizeof(TreeNode));

　　Init();

　　MirrorTree(root);

　　OutPut();

　　}

　　2、假設(shè)某個(gè)網(wǎng)站每天有超過(guò)10億次的頁(yè)面訪(fǎng)問(wèn)量，出于安全考慮，網(wǎng)站會(huì)記錄訪(fǎng)問(wèn)客戶(hù)端訪(fǎng)問(wèn)的ip地址和對(duì)應(yīng)的時(shí)間，如果現(xiàn)在已經(jīng)記錄了1000億條數(shù)據(jù)，想統(tǒng)計(jì)一個(gè)指定時(shí)間段內(nèi)的區(qū)域ip地址訪(fǎng)問(wèn)量，那么這些數(shù)據(jù)應(yīng)該按照何種方式來(lái)組織，才能盡快滿(mǎn)足上面的統(tǒng)計(jì)需求呢，設(shè)計(jì)完方案后，并指出該方案的優(yōu)缺點(diǎn)，比如在什么情況下，可能會(huì)非常慢?

　　答：用B+樹(shù)來(lái)組織，非葉子節(jié)點(diǎn)存儲(chǔ)(某個(gè)時(shí)間點(diǎn)，頁(yè)面訪(fǎng)問(wèn)量)，葉子節(jié)點(diǎn)是訪(fǎng)問(wèn)的IP地址。這個(gè)方案的優(yōu)點(diǎn)是查詢(xún)某個(gè)時(shí)間段內(nèi)的IP訪(fǎng)問(wèn)量很快，但是要統(tǒng)計(jì)某個(gè)IP的訪(fǎng)問(wèn)次數(shù)或是上次訪(fǎng)問(wèn)時(shí)間就不得不遍歷整個(gè)樹(shù)的葉子節(jié)點(diǎn)。答：

　　或者可以建立二級(jí)索引，分別是時(shí)間和地點(diǎn)來(lái)建立索引。

　　四、附加題

　　1、寫(xiě)出C語(yǔ)言的地址對(duì)齊宏ALIGN(PALGNBYTES)，其中P是要對(duì)齊的地址，ALIGNBYTES是要對(duì)齊的字節(jié)數(shù)(2的N次方)，比如說(shuō)：ALIGN(13,16)=16

　　[cpp] view plaincopyALIGN(P,ALIGNBYTES) ( (void*)( ((unsigned long)P+ALIGNBYTES-1)&~(ALIGNBYTES-1) ) )

　　2、在高性能服務(wù)器的代碼中經(jīng)常會(huì)看到類(lèi)似這樣的代碼：

　　typedef union

　　{

　　erts_smp_rwmtx_t rwmtx;

　　byte cache_line_align_[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(erts_smp_rwmtx_t))];

　　}erts_meta_main_tab_lock_t;

　　erts_meta_main_tab_lock_t main_tab_lock[16];

　　請(qǐng)問(wèn)其中用來(lái)填充的cache_line_align的作用是?

　　3、在現(xiàn)代web服務(wù)系統(tǒng)的設(shè)計(jì)中，為了減輕源站的壓力，通常采用分布式緩存技術(shù)，其原理如下圖所示，前端的分配器將針對(duì)不同內(nèi)容的用戶(hù)請(qǐng)求分配給不同的緩存服務(wù)器向用戶(hù)提供服務(wù)。

　　分配器

　　/ | \

　　緩存 緩存 ...緩存

　　服務(wù)器1 服務(wù)器2 ...服務(wù)器n

　　1)請(qǐng)問(wèn)如何設(shè)置分配策略，可以保證充分利用每個(gè)緩存服務(wù)器的存儲(chǔ)空間(每個(gè)內(nèi)容只在一個(gè)緩存服務(wù)器有副本)

　　2)當(dāng)部分緩存服務(wù)器故障，或是因?yàn)橄到y(tǒng)擴(kuò)容，導(dǎo)致緩存服務(wù)器的數(shù)量動(dòng)態(tài)減少或增加時(shí)，你的分配策略是否可以保證較小的緩存文件重分配的開(kāi)銷(xiāo)，如果不能，如何改進(jìn)?

　　3)當(dāng)各個(gè)緩存服務(wù)器的存儲(chǔ)空間存在差異時(shí)(如有4個(gè)緩存服務(wù)器，存儲(chǔ)空間比為4：9：15：7)，如何改進(jìn)你的策略，按照如上的比例將內(nèi)容調(diào)度到緩存服務(wù)器?