2021年秋季阿里巴巴校園招聘軟件研發(fā)工程師試題及答案

1.單項選擇題

1.假設(shè)把整數(shù)關(guān)鍵碼K散列到N個槽列表，以下哪些散列函數(shù)是好的散列函數(shù)

A:h(K)=K/N;

B:h(K)=1;

C:h(K)=KmodN;

D:h(K)=(K+rand(N))modN,rand(N)返回0到N-1的整數(shù)

答案:D

2.下面排序算法中，初始數(shù)據(jù)集的排列順序?qū)λ惴ǖ男阅軣o影響的是：

A:堆排序B：插入排序

C:冒泡排序D:快速排序

答案:A(插入排序：最優(yōu)時間復雜度。(n)最差時間復雜度。(nA2)平均時間復雜度O

(M2)

冒泡排序：最優(yōu)時間復雜度0(n)最差時間復雜度O(M2)平均時間復

雜度O(M2)

快速排序：最優(yōu)時間復雜度O(nlogn)最差時間復雜度。(M2)平均

時間復雜度O(nlogn)

堆排序：最優(yōu)時間復雜度O(nlogn)最差時間復雜度O(nlogn)平均時

間復雜度O(nlogn))

3.下面說法錯誤的選項是：

A:CISC計算機比RISC計算機指令多

B:在指令格式中，采用擴展操作碼設(shè)計方案的目的是為了保持指令字長不變而增

加尋址空間

C:增加流水線段數(shù)理論上可以進步CPU頻率

D:馮諾依曼體系構(gòu)造的主要特征是存儲程序的工作方式

答案:B

4.不屬于馮諾依曼體系構(gòu)造必要組成局部是：

A:CPUB:CacheC:RAMD:ROM

答案:B

5.一個棧的入棧序列式ABCDE那么不可能的出棧序列是：

A:DECBAB:DCEBAC:ECDBAD:ABCDE

答案:C

6.你認為可以完成編寫一個C語言編譯器的語言是：

A：匯編B:C語言C:VBD:以上全可以

答案：D

7.關(guān)于C++/JAVA類中的static成員和對象成員的說法正確的選項是:

A：static成員變量在對象構(gòu)造時候生成

B:static成員函數(shù)在對象成員函數(shù)中無法調(diào)用

C:虛成員函數(shù)不可能是static成員函數(shù)

D:static成員函數(shù)不能訪問static成員變量

答案：A

8：

9：某進程在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時進程的狀態(tài)將:

A:從就緒變?yōu)檫\行B:從運行變?yōu)榫途w

C:從運行變?yōu)樽枞鸇:從阻塞變?yōu)榫途w

答案：C

10：下面算法的時間復雜度為：

Int{(unsignedintn)

(

|f(n==0||n==1)

Return1;

日se

Returnn*f(n-1);

)

A:0(1)B:O(n)C:O(N*N)D:O(n!)

答案：B

11：n從1開場，每個操作可以選擇對n力口1或者對n加倍。假設(shè)想獲得整數(shù)2021,最少需要

多少個操作。

A:18B:24C:21D；不可能

答案：A,對2021用除法，顯示

2021->2021->1006->503->502->251->250->125->124->62->31->30->15->14->7->6->3->

2->1

正向只能是+1和X2,所以逆向只能-1和/2,由上過程可得18次

12：對于一個具有n個頂點的無向圖，假設(shè)采用鄰接表數(shù)據(jù)構(gòu)造表示，那么存放表頭節(jié)點

的數(shù)組大小為：

A:nB:n+1C:n-1D:n+邊數(shù)

答案：A

13：

13.考慮一個特殊的hash函數(shù)h,能將任一字符串hash成一個整數(shù)k,其概率

P(k)=2"(-k),k=1,2,…，8。對一個未知大小的字符串渠合S中的每一個元

素取hash值所組成的集合為h(S)o若h(S)中最大的元素maxh⑻=懂，

那么S的大小的期望是一。

A、1024B、512C、5D、10

答案:A.對于幾何中的每個字符串取hash可以看作是同分布的獨立重復事件，所以每一個事

件出現(xiàn)10的概率都是p=1/1024,那么當出現(xiàn)的時候，期望的次數(shù)就是1/p,1024.

14：如下函數(shù)，在32bit系統(tǒng)foo(2八31?3)的值是：

Intfoo(intx)

Returnx&-x;

)

A：0B:1C:2D:4

答案：B

15：對于順序存儲的線性數(shù)組，訪問節(jié)點和增加節(jié)點刪除節(jié)點的時間復雜度為：

A:0(n),0(n)B:0(n),0(1)C:0(1),0(n)D:O(n),O(n)

答案：C

16:在32為系統(tǒng)環(huán)境，編譯選項為4字節(jié)對齊，那么sizeof(A)和sizeof(B)是：

StructA

(

Inta;

shortb;

intc;

chard;

)；

StructB

(

inta;

shortb;

charc;

intc;

)；

A:16,16B:13,12C：16,12D:11,16

答案：C

17:袋中有紅球，黃球，白球各一個，每次任意取一個放回，如此連續(xù)3次，那么以下事件中

概率是8/9的是：

A:顏色不全一樣B:顏色全不一樣C:顏色全一樣D:顏色無紅色

答案：A

18：一個洗牌程序的功能是將n張牌的順序打亂，以下關(guān)于洗牌程序的功能定義說法最恰

當?shù)氖牵?/p>

A:每張牌出如今n個位置上的概率相等

B:每張牌出如今n個位置上的概率獨立

C:任何連續(xù)位置上的兩張牌的內(nèi)容獨立

D:n張牌的任何兩個不同排列出現(xiàn)的概率相等

答案：A

19：用兩種顏色去染排成一個圈的6個棋子，假如通過旋轉(zhuǎn)得到那么只算一種，一共有多少

種染色：

A:10B:11C:14:D:15

答案：C

解釋：應該有14種方案，設(shè)只有黑白兩色，默認白色，那么，用p(n)表示有n個黑棋的

種類

p(0)=p(6)=1

p(1)=p(5)=1

p(2)=p(4)=3〃相鄰的一種，隔一個的一種，兩個的一種

p(3)=4〃都相鄰的一種，BB0B的一種，BB00B的一種，B0B0B的一種，一共4種

綜上是14種

20：遞歸式的先序遍歷一個n節(jié)點，深度為d的二叉樹，那么需要棧空間的大小為：

A:O(n)B:O(d)C:O(logn)D:(nlogn)

答案：B

第二局部：多項選擇

21：兩個線程運行在雙核機器上，每個線程主線程如下，線程1：x=1;r1=y;線程2：y=1;r2=x;

X和y是全局變量，初始為0。以下哪一個是r1和r2的可能值：

A:r1=1,r2=1

B:r1=1,r2=0

C:r1=0,r2=0

D:r1=0,r2=1

答案：ABD

22.關(guān)于Linux系統(tǒng)的負載，以下表述正確的選項是：

A:通過就緒和運行的進程數(shù)來反映

B:通過TOP命令查看

C:通過uptime查看

D:Load:2.5,1.3,1.1表示系統(tǒng)的負載壓力在逐漸變小

答案：BC(對于A不確定)

23：關(guān)于排序算法的以下說法，錯誤的選項是：

A:快速排序的平均時間復雜度O(nlogn),最壞O(W2)

B:堆排序平均時間復雜度O(nlogn),最壞O(nlogn)

C:冒泡排序平均時間復雜度O(n"2),最壞O(M2)

D:歸并排序的平均時間復雜度O(nlogn),最壞O(n"2)

答案：D

解釋：歸并排序的平均時間復雜度O(nlogn),最壞O(nlogn)

24:假設(shè)函數(shù)rand_k會隨機返回一個【1,kJ之間的隨機數(shù)(k>=2),并且每個證書出現(xiàn)的

概率相等。目前有rand_7,通過調(diào)用rand_7()和四那么運算符，并適當增加邏輯判斷和循

環(huán)控制邏輯，以下函數(shù)可以實現(xiàn)的有：

A:rand3B:rand21C:rand23D:rand49

答案：ABCD

解釋：對于rand_x（x<7）的直接截斷，只要rand數(shù)大于x直接忽略，保證rand_x可以做

到概率相等。而對于其他的那么采用7Xrand_7+rand_7,可以-7得到rand_49,然后截斷

成rand_42,統(tǒng)一除以2,那么是rand_21,其他類似。

第三局部

25、某二叉樹的前序遍歷序列為-+a*b-cd/ef,后序遍歷序列為abcd-*+ef/-,問其中序遍歷

序歹U是---o

答案：a+b*c-d-e/f

26、某緩存系統(tǒng)采用LRU淘汰算法，假定緩存容量為4,并且初始為空，那么在順序訪問

以下數(shù)據(jù)項的時候1,5,1,3,2,4,1,2出現(xiàn)緩存命中的次數(shù)是——。最后緩存中即將準備淘汰的

數(shù)據(jù)項是一一。

答案：3,3

解釋：（LRU是LeastRecentlyUsed近期最少使用算法。）

1-?1,5-?5,1-?5,1,3-?5,1,3,2-?1,3,2,4-?3,2,4,1-73,4,1,2-?

首先1調(diào)入內(nèi)存，然后5調(diào)入內(nèi)存，然后1調(diào)入內(nèi)存（命中緩存），然后3調(diào)入內(nèi)存，然后2調(diào)

入內(nèi)存，然后4調(diào)入內(nèi)存（將最少使用的5置換出內(nèi)存），然后1調(diào)入內(nèi)存（命中緩存），然后

2調(diào)入內(nèi)存（命中緩存）。最后，最少使用的3將面臨被置換出的危險。

27、兩個較長的單向鏈表a和b,為了找出及誤單noed滿足nodeina并且nodeinb。請

設(shè)計空間使用盡量小的算法（用C/C++,java或者偽代碼）

[html]viewplaincopyprint?

1structnode

2（

3intv;

4node*next;

5）；

6/*

7返回鏈表的長度

8鏈表為空返回0

97

10size_tlistLen（node*p）

H（

12size_tnum=0;

13while（p!=NULL）

14

15num++;

16p=p->next;

17)

18returnnum;

19)

20〃假如找到了那么返回指針指向公共節(jié)點

21//假如不存在那么返回空指針

22node*findFirstCommenNode(node*pheada,node*pheadb)

23(

24size_tlenA=listLen(pheada);

25size_tlenB=listLen(pheadb);

26

27node*plistA=pheada;

28node*plistB=pheadb;

29〃調(diào)整長度

30//plistA指向較長的一個

31if(lenA<lenB)

32(

33plistB=pheada;

34plistA=pheadb;

35size_tt=lenA;

36lenA=lenB;

37lenB=t;

38)

39while(lenA>lenB)

40(

41plistA=plistA->next;

42-lenA;

43)

44〃一樣長了

45〃尋找公共節(jié)點

46while(plistA!=NULL&&plistA!=plistB)

47(

48plistA=plis