淘寶面試題

一、單選題

1、我們有很多瓶無色的液體，其中有一瓶是毒藥，其它都是蒸餾水，實驗的小白鼠喝了以後會在5分鐘後死亡，而喝到蒸餾水的小白鼠則一切正常。現在有5只小白鼠，請問一下，我們用這五隻小白鼠，5分鐘的時間，能夠檢測多少瓶液體的成分()

a 5瓶 b 6 c 31 d 32

2、若某連結串列最常用的操作是在最後一個結點之後插入一個結點和刪除最後一個結點，則採用()儲存方式最節省時間?

A 單鏈表 B 帶頭結點的非迴圈雙鏈表 C 帶頭節點的雙迴圈連結串列 D 迴圈連結串列

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 D. Epoll

6、IpV6地址包含了()位

A. 16 B. 32 C. 64 D.128

7、資料庫裡建索引常用的資料結構是()

A 連結串列 B佇列 C 樹 D 雜湊表

8、在公司區域網上ping 沒有涉及到的網路協議是()

A. ARp B. DNS C. TCp D. ICMp

二、填空題

1、http屬於()協議，ICMp屬於()協議

2、深度為k的完全二叉樹至少有()個結點，至多有()個結點

3、位元組為6位的二進位制有符號整數，其最小值是()

4、設有28盞燈，擬公用一個電源，則至少需有4插頭的接線板數()個。

三、綜合題

1、有一顆結構如下的樹，對其做映象反轉後如下，請寫出能實現該功能的程式碼。注意：請勿對該樹做任何假設，它不一定是平衡樹，也不一定有序。

1 1

/ | / |

2 3 4 4 3 2

/| / | | / / |

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

2、 假設某個網站每天有超過10億次的頁面訪問量，出於安全考慮，網站會記錄訪問客戶端訪問的ip地址和對應的時間，如果現在已經記錄了1000億條資料，想 統計一個指定時間段內的區域ip地址訪問量，那麼這些資料應該按照何種方式來組織，才能儘快滿足上面的統計需求呢，設計完方案後，並指出該方案的優缺點， 比如在什麼情況下，可能會非常慢?

四、附加題

1、寫出C語言的地址對齊巨集ALIGN(pALGNBYTES)，其中p是要對齊的地址，ALIGNBYTES是要對齊的'位元組數(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、在現代web服務系統的設計中，為了減輕源站的壓力，通常採用分散式快取技術，其原理如下圖所示，前端的分配器將針對不同內容的使用者請求分配給不同的快取伺服器向用戶提供服務。

分配器

/ |

快取 快取 ...快取

伺服器1 伺服器2 ...伺服器n

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

2)當部分快取伺服器故障，或是因為系統擴容，導致快取伺服器的數量動態減少或增加時，你的分配策略是否可以保證較小的快取檔案重分配的開銷，如果不能，如何改進?

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