2015阿里巴巴實習筆試

1、設棧S初始狀態為空。元素a,b,c,d,e,f依次通過棧S，若出棧的順序為c,f,e,d,b,a，則棧S的容量至少應該為______ 。

3

4

5

6

2、10個相同的糖果，分給三個人，每個人至少要得一個。有 種不同分法。

33

34

35

36

3、小數值1.5625的二進制表示是____。

101.1001

0.001

101.111

1.1001

4、某二叉樹的先序遍歷是12453，中序遍歷是42513，那麼其後續遍歷是______。

45231

42351

12345

54321

5、主機甲和主機乙間已建立一個TCP連接，主機甲向主機乙發送了兩個連續的TCP段，分別包含300字節和500字節的有效載荷，第一個段的序列號為200，主機乙正確接收到兩個段後，發送給主機甲的確認序列號是 。

500

700

800

1000

6、在N個亂序數字中查找第k大的數字，時間複雜度可以減小至 。

O(N*logN)

O(N)

O(1)

O(N^2)

7、平均速度最快的排序算法是______。

Shell排序

快速排序

冒泡排序

插入排序

8、以下指令集架構屬於複雜指令集架構的是____。

ARM

MIPS

SPARC

以上皆不是

9、有兩個N*N的矩陣A和B，想要在PC上按矩陣乘法基本算法編程實現計算A*B。假設N較大，本機內存也很大，可以存下A、B和結果矩陣。那麼，為了計算速度，A和B在內存中應該如何存儲(按行存指先存儲第一行，再第二行，直到最後一行;按列存指先存儲第一列，再第二列，直到最後一列)

A按行存，B按行存。

A按行存，B按列存。

A按列存，B按行存。

A按列存，B按列存。

10、設一棵二叉樹中有3個葉子節點，有8個度為1的節點，則該二叉樹中總的節點數為______。

12

13

14

15

11、IP數據報頭採用______字節序，在此字節序下從低地址到高地址0×1234的表示形式為______。

big_endian， 0×12 0×34 0 0

little_endian，0×34 0×12 0 0

big_endian， 0 0 0×12 0×34

little_endian，0 0 0×34 0×12

12、下列敍述中正確的是____。

循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構

在循環隊列中，只需要隊頭指針就能反映隊列中元素的動態變化情況

在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況

循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定

13、將一個從大到小的數組，用以下排序方法排序成從小到大的`，______最快。

插入排序

冒泡排序

快速排序

堆排序

14、在一個元素個數為N的數組裏，找到升序排在N/5位置的元素的最優算法時間複雜度是______。

O(n)

O(n log n)

O(n(log n)2)

O(n 3/2)

15、 已有變量定義和函數調用語句;編程-代碼

int a=25;

print_value(&a);

則下面函數的正確輸出結果是______。

void print_value(int* x)

{

printf(“%x”,++*x);

}

25

26

19

1a

16、在二進制數據中，小數點向右移一位，則數據______。

除以10

除以2

乘以2

乘以10

17、設集合A={1,2,3},A上的關係R={(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備 。

自反性

傳遞性

對稱性

反對稱性

18、下列敍述中正確的是 。

循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構

在循環隊列中，只需要隊頭指針就能反映隊列中元素的動態變化情況

在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況

循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定

19、假定x=500，求下面函數的返回值______ 。

int fun(int x)

{

int countx = 0;

while (x)

{

countx++;

x = x & (x 1);

}

return countx;

｝

2

3

5

6

20、有一台帶一個千兆網卡的服務器A，會把接收到的消息轉發給另外兩台帶一個千兆網卡的服務器B和C，B和C上面的一個服務進程處理一條10K字節的消息需要2毫秒。如果在B和C上面各跑80個服務進程，在不考慮CPU負載和進程切換、內存佔用、傳輸損耗和交互損耗的情況下，B和C服務器每秒一共大約可以處理______條10K字節的消息。

50000

60000

70000

80000

21、以下措施中，有可能改進分佈式系統讀寫(IO)性能的有____。

網絡從千兆網升級為萬兆網

優化調度系統，儘量做到任務與數據相近(Locality)

數據預取機制

實現異步讀寫機制

22、無鎖化編程有哪些常見方法?______ 。

針對計數器，可以使用原子加

只有一個生產者和一個消費者，那麼就可以做到免鎖訪問環形緩衝區(Ring Buffer)

RCU(Read-Copy-Update)，新舊副本切換機制，對於舊副本可以採用延遲釋放的做法

CAS(Compare-and-Swap)，如無鎖棧，無鎖隊列等待

23、程序

struct T {

char a;

int *d;

int b;

int c:16;

double e;

};

T *p;

在64位系統上以下描述正確的是 。

sizeof(p) == 8

sizeof(*p) == 32

sizeof(p->a) == 1

sizeof(p->e) == 4

24、下面所述步驟中，是創建進程所必須的步驟是_____。

由調度程序為進程分配CPU

建立一個進程控制塊

為進程分配內存

為進程分配文件描述符

25、有一種用左右值表示樹形結構的存儲格式，其中左右值有一些相當有用的場景，但是每個節點的左右值需要遍歷樹形結構計算出來。一個示例：

N[1,12]

|__N[2,7]

| |__N[3,4]

| |__N[5,6]

|__N[8,11]

|__N[9,10]

請完成遍歷算法給節點賦左右值。

typedef struct node_t {

int left;

int right;

int n_children;

1 children;

} NODE;

int visit(NODE * node, int value) {

node->left = value;

int i = 0;

for(i=0; in_children; i++) {

2

}

3

return value;

}

int initLR(NODE* root) {

return visit(root, 1);

}

26、我們需要在淘寶的商品中提取一批優質商品(有特色、質量好、服務好等)，比如需要提取100萬件，準確率要求是95%。我們有n個不同的方法可以提取這些商品，但每個方法在保持準確率滿足要求的情況下都不能做到提取完整的100萬件商品。因此可以把這n個方法得到的滿足要求的商品集按如下方法合併起來：如果一個商品被k個方法選為優質商品，則將它的分數設為k;按照k從大到小排序選取前100萬件。但實際中發現這樣選出的100萬件商品不符合精度要求，請解釋可能的原因。還可以向哪個方向努力?

27、有個學校的15個女生一直3個一羣上學。請問該如何安排才能使這些女生每週7天每天都和兩個不同的同伴結伴同行呢?例如：用A到O來標識這些女孩，7天A正好和B到O這14個女孩各同行一次。而B到O每個人和都和其他14個女孩各同行一次。

28、長度為100的環形雙向鏈表，A指針順時針方向每次走3步，B指針逆時針方向每次走5步，每次走完判斷是否相遇，初始狀態B在A逆時針方向相距20，走100次，AB指針能相遇幾次?

29、某招聘筆試共有120人蔘加，考試有6道題。1-6道分別有86人，88人，92人，76人，72人和70人答對，如果答對3道或3道以上通過筆試，問至少有多少人通過?

30、Wait()和sleep()的區別