三、綜合題

　　1、有一顆結構如下的樹，對其做鏡像反轉后如下，請寫出能實現(xiàn)該功能的代碼。注意：請勿對該樹做任何假設，它不一定是衡樹，也不一定有序。

　　1 1

　　/ | \ / | \

　　2 3 4 4 3 2

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

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

　　答：以孩子、兄弟的存儲結構來存儲這棵樹，使之成為一顆二叉樹，然后對二叉樹進行鏈表的轉換。

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

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

　　或者可以建立二級索引，分別是時間和地點來建立索引。

　　四、附加題

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

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

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

　　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];

　　請問其中用來填充的cache_line_align的作用是?

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

　　分配器

　　/ | \

　　緩存 緩存 ...緩存

　　服務器1 服務器2 ...服務器n

　　1)請問如何設置分配策略，可以保證充分利用每個緩存服務器的存儲空間(每個內容只在一個緩存服務器有副本)

　　2)當部分緩存服務器故障，或是因為系統(tǒng)擴容，導致緩存服務器的數(shù)量動態(tài)減少或增加時，你的分配策略是否可以保證較小的緩存文件重分配的開銷，如果不能，如何改進?

　　3)當各個緩存服務器的存儲空間存在差異時(如有4個緩存服務器，存儲空間比為4：9：15：7)，如何改進你的策略，按照如上的比例將內容調度到緩存服務器?