![中國人才網](http://static.cnrencai.com/img/cn_logo2.jpg"){kind=logo}
一、單選題
1、我們有很多瓶無色的液體，其中有一瓶是毒藥，其它都是蒸餾水，實驗的小白鼠喝了以后會在5分鐘后死亡，而喝到蒸餾水的小白鼠則一切正�！，F(xiàn)在有5只小白鼠，請問一下，我們用這五只小白鼠，5分鐘的時間，能夠檢測多少瓶液體的成分()
a 5瓶 b 6 c 31 d 32
2、若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用()存儲方式最節(jié)省時間?
A 單鏈表 B 帶頭結點的非循環(huán)雙鏈表 C 帶頭節(jié)點的雙循環(huán)鏈表 D 循環(huán)鏈表
3、如果需要對磁盤上的1000W條記錄構建索引，你認為下面哪種數據結構來存儲索引最合適?()
A Hash Table B. AVL-Tree C. B-Tree D. List
4、可用來檢測一個web服務器是否正常工作的命令是()
A ping B tracert C. telnet D. ftp
5、下面哪個操作是Windows獨有的I/O技術()
A. Select B.Poll C.IOCP D. Epoll
6、IPV6地址包含了()位
A. 16 B. 32 C. 64 D.128
7、數據庫里建索引常用的數據結構是()
A 鏈表 B隊列 C 樹 D 哈希表
8、在公司局域網上ping www.taobao.com沒有涉及到的網絡協(xié)議是()
A. ARP B. DNS C. TCP D. ICMP
二、填空題
1、http屬于()協(xié)議，ICMP屬于()協(xié)議
2、深度為k的完全二叉樹至少有()個結點，至多有()個結點
3、字節(jié)為6位的二進制有符號整數，其最小值是()
4、設有28盞燈，擬公用一個電源，則至少需有4插頭的接線板數()個。
三、綜合題
1、有一顆結構如下的樹，對其做鏡像反轉后如下，請寫出能實現(xiàn)該功能的代碼。注意：請勿對該樹做任何假設，它不一定是平衡樹，也不一定有序。
1 1
/ | \ / | \
2 3 4 4 3 2
/|\ /\ | | / \ / | \
6 5 7 8 9 10 10 9 8 7 5 6
2、假設某個網站每天有超過10億次的頁面訪問量，出于安全考慮，網站會記錄訪問客戶端訪問的ip地址和對應的時間，如果現(xiàn)在已經記錄了1000億條數據，想統(tǒng)計一個指定時間段內的區(qū)域ip地址訪問量，那么這些數據應該按照何種方式來組織，才能盡快滿足上面的統(tǒng)計需求呢，設計完方案后，并指出該方案的優(yōu)缺點，比如在什么情況下，可能會非常慢?
四、附加題
1、寫出C語言的地址對齊宏ALIGN(PALGNBYTES)，其中P是要對齊的地址，ALIGNBYTES是要對齊的字節(jié)數(2的N次方)，比如說：ALIGN(13,16)=16
2、在高性能服務器的代碼中經常會看到類似這樣的代碼：
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)擴容，導致緩存服務器的數量動態(tài)減少或增加時，你的分配策略是否可以保證較小的緩存文件重分配的開銷，如果不能，如何改進?
3)當各個緩存服務器的存儲空間存在差異時(如有4個緩存服務器，存儲空間比為4：9：15：7)，如何改進你的策略，按照如上的比例將內容調度到緩存服務器?