2021年阿里巴巴工程師A筆試面試題

下列關(guān)鍵字序列為堆的是______。

A.100，60，70，50，32，65
B.60，70，65，50，32，100
C.65，100，70，32，50，60
D.70，65，100，32，50，60
E.32，50，100，70，65，60
F.50，100，70，65，60，32

答案：A

如果一個(gè)博物館參觀(guān)者到達的速率是每分鐘 20 人，平均每個(gè)人在館內停留20分鐘，那么該博物館至少需要容納______人才行？

A.100
B.200
C.300
D.400
E.500
F.600

答案：D

計算三個(gè)稠密矩陣 A、B、C 的乘積 ABC，假定三個(gè)矩陣的尺寸分別為 m*n, n*p,p*q，且 m

A.(AB)C
B.A(BC)
C.(AC)B
D.(BC)A
E.(CA)B

答案：A

通過(guò)算法生成的隨機數是“偽隨機”的，也就是說(shuō)，在設定好第一個(gè)數之后，后面的數字的序列是確定的，并且經(jīng)過(guò)一個(gè)非常大的循環(huán)會(huì )回到第一個(gè)數的狀態(tài)，然后周而復始。顯然，搖號、抽獎的程序是不能通過(guò)偽隨機數來(lái)實(shí)現的�，F實(shí)中常�；谀撤N熱噪聲來(lái)實(shí)現真正的隨機數。假定某熱噪聲是標準正態(tài)分布，那么能否將它轉換成(0,1)區間上的均勻分布______？

A.忽略測量和計算誤差，可以轉換為(0,1)區間上的均勻分布
B.無(wú)法轉換為(0,1)區間上的均勻分布
C.信息不足，無(wú)法判斷
D.借助偽隨機數生成算法可以轉換為(0,1)區間上的均勻分布
E.僅僅靠偽隨機數生成算法，就可以生成(0,1)區間上的均勻分布
F.以上說(shuō)法都不對

答案：A

有一個(gè)用數組 C[1..m]表示的環(huán)形隊列，m 為數組的長(cháng)度。假設 f 為隊頭元素在數組中的位置，r 為隊尾元素的后一位置(按順時(shí)針?lè )较?。若隊列非空，則計算隊列中元素個(gè)數的公式應為？

A.（m+r-f）mod m
B.r-f
C.(m-r+f) mod m
D.(m-r-f) mod m
E.(r-f) mod m

答案：A

某足球隊有四名外援，分別來(lái)自巴西、荷蘭、意大利和美國。他們分別擅長(cháng)前 鋒、后衛或守門(mén)，其中：
① 美國外援單獨擅長(cháng)守門(mén)；
② 意大利外援不擅長(cháng)前鋒；
③ 巴西外援和另外某個(gè)外援擅長(cháng)相同的位置；
④ 荷蘭外援擅長(cháng)的位置和巴西外援不同。
以上條件可以推出巴西外援擅長(cháng)的位置是______。

A.前鋒
B.守門(mén)
C.后衛
D.前鋒或守門(mén)
E.后衛或守門(mén)
F.前鋒或后衛

答案：C

二分查找樹(shù)里查詢(xún)一個(gè)關(guān)鍵字的最壞時(shí)間復雜度是______

A.O(n)
B.O(n log n)
C.O(n^2)
D.O(n^3)
E.O(logn)
F.不確定

答案：A

假設某段通信電文僅由 6 個(gè)字母 ABCDEF 組成，字母在電文中出現的頻率分別為2，3，7，15，4，6。根據這些頻率作為權值構造哈夫曼編碼，最終構造出的哈夫曼樹(shù)帶權路徑長(cháng)度與字母 B 的哈夫曼編碼分別為_(kāi)_____。(這里假定左節點(diǎn)的值小于右節點(diǎn)的值)

A.86，1011
B.70，1000
C.86，0001
D.70，0010
E.92，1000
F.92，0100

答案：A

并發(fā)進(jìn)程執行的相對速度是______。

A.由進(jìn)程的程序結構決定
B.由進(jìn)程本身來(lái)控制
C.進(jìn)程被創(chuàng )建時(shí)決定
D.與進(jìn)程調度策略有關(guān)
E.與進(jìn)程的銷(xiāo)毀時(shí)間有關(guān)
F.由內存分配策略決定

答案：D

某團隊有 2/5 的人會(huì )寫(xiě) Java 程序，有 3/4 的人會(huì )寫(xiě) C++程序，這個(gè)團隊里同時(shí)會(huì )寫(xiě) Java 和 C++的最少有______人。

A.3
B.4
C.5
D.8
E.15
F.20

答案：A

有一個(gè)裝過(guò)食鹽的瓶子，容積是 w，在食鹽用完之后，還有一些食鹽粉末（體 積可以忽略）殘留在瓶子壁上�，F在要把該瓶子改裝糖，給你 u 體積的純凈 水，用來(lái)清洗該瓶子。在每次清洗之后，瓶子里會(huì )殘留至少 v 體積的水（食鹽 溶液，可以忽略鹽的體積） 。假設 w>u>v，請問(wèn)下述哪種方式使用這些純凈 水，能把瓶子洗得最干凈______？

A.把所有的純凈水全部倒入瓶子，然后把水倒掉
B.將純凈水平均分成兩份，用每一份清水洗一遍瓶子。
C.每次注入體積為 v 的純凈水清洗瓶子，直到純凈水用盡
D.每次注入體積為 2v 的純凈水清洗瓶子，直到純凈水用盡
E.將用過(guò)的水重新諸如瓶子，多次清洗
F.以上方法清洗效果相同

答案：C

下列 C 代碼中，不屬于未定義行為的有：______。

A.int i=0;i=(i++);
B.char *p=”hello”;p[1]=’E’
C.char *p=”hello”;char ch=*p++
D.int i=0;printf(“%d%d\n”,i++ i--)
E.都是未定義行為
F.都不是未定義行為

答案：C

畢業(yè)典禮后，某宿舍三位同學(xué)把自己的畢業(yè)帽扔了，隨后每個(gè)人隨機地拾起帽子，三個(gè)人中沒(méi)有人選到自己原來(lái)帶的帽子的概率是

A.1/2
B.1/3
C.1/4
D.1/6
E.1/8
F.1/9

答案：B

村長(cháng)帶著(zhù) 4 對父子參加爸爸去哪兒第三季第二站某村莊的拍攝。村里為了保護小孩不被拐走有個(gè)前年的規矩，那就是吃飯的時(shí)候小孩左右只能是其他小孩或者自己的父母。那么 4 對父子在圓桌上共有___種坐法。 （旋轉一下，每個(gè)人面對的方向變更后算是一種新的坐法）

A.144
B.240
C.288
D.480
E.576
F.960

答案：D

分布式系統中，______不是可擴展性所需要的

A.無(wú)狀態(tài)應用集群
B.分布式緩存
C.負載均衡
D.硬件共享存儲
E.分而治之的策略
F.以上所有都是

答案：F

第16題：

若干個(gè)等待訪(fǎng)問(wèn)磁盤(pán)者依次要訪(fǎng)問(wèn)的磁道為 19， 43， 40， 4， 79，11，76，當前磁頭位于 40 號柱面，若用最短尋道時(shí)間優(yōu)先磁盤(pán)調度算法，則訪(fǎng)問(wèn)序列為_(kāi)__

A.19,43,40,4,79,11,76
B.40,43,19,11,4,76,79
C.40,43,76,79,19,11,4
D.40,43,76,79,4,11,19
E.40,43,76,79,11,4,19
F.40,19,11,4,79,76,43

答案：B

C++內存分配中說(shuō)法錯誤的是：______。

A.對于棧來(lái)講，生長(cháng)方向是向上的，也就是向著(zhù)內存地址增加的方向
B.對于堆，大量的 new/delete 操作會(huì )造成內存空間的不連續
C.堆容易產(chǎn)生 memory leak D，堆的效率比棧要低的多
D.堆的效率比棧要低得多
E.棧變量引用容易逃逸
F.以上都對

答案：A

下列關(guān)于網(wǎng)絡(luò )編程錯誤的是______。

A.UDP 是不可靠服務(wù)
B.主動(dòng)關(guān)閉的一端會(huì )出現 TIME_WAIT 狀態(tài)
C.服務(wù)端編程會(huì )調用 listen(),客戶(hù)端也可以調用 bind()
D.TCP 建立和關(guān)閉連接都只需要三次握手
E.Linux 通過(guò)提供提供 socket 接口來(lái)進(jìn)行網(wǎng)絡(luò )編程
F.長(cháng)連接相對短連接可以節省建立連接的時(shí)間

答案：D

在 32 位操作系統中，下列類(lèi)型占用 8 個(gè)字符的為_(kāi)_____。

A.short int
B.Int C long
C.Unsigned int
D.Long long
E.Char
F.Int

答案：D

在小端序的機器中,如果?

union X{

????int x;

????char y[4];

};

如果:
X a;
a.x=0x11223344;//16 進(jìn)制 則:______

A.a.y[0]=11
B.a.y[1]=11
C.a.y[2]=11
D.a.y[3]=11
E.a.y[0]=22
F.a.y[3]=22

答案：D

[問(wèn)答題]

題目描述

java 中的 wait()方法和 sleep()方法的區別是什么?

對于sleep()方法，我們首先要知道該方法是屬于Thread類(lèi)中的。而wait()方法，則是屬于Object類(lèi)中的。sleep()方法導致了程序暫停執行指定的時(shí)間，讓出cpu該其他線(xiàn)程，但是他的監控狀態(tài)依然保持者，當指定的時(shí)間到了又會(huì )自動(dòng)恢復運行狀態(tài)。
在調用sleep()方法的過(guò)程中，線(xiàn)程不會(huì )釋放對象鎖。
而當調用wait()方法的時(shí)候，線(xiàn)程會(huì )放棄對象鎖，進(jìn)入等待此對象的等待鎖定池，只有針對此對象調用notify()方法后本線(xiàn)程才進(jìn)入對象鎖定池準備。

[問(wèn)答題]

題目描述

寫(xiě)一個(gè)函數,輸入一個(gè)二叉樹(shù),樹(shù)中每個(gè)節點(diǎn)存放了一個(gè)整數值,函數返回這棵二叉樹(shù)中相差最大的兩個(gè)節點(diǎn)間的差值絕對值。請注意程序效率。

先求每個(gè)子樹(shù)的最大值和最小值,遞歸實(shí)現。

[問(wèn)答題]

題目描述：

給定一個(gè) query 和一個(gè) text,均由小寫(xiě)字母組成。要求在 text 中找出以同樣的順序連 續出現在 query 中的最長(cháng)連續字母序列的長(cháng)度。例如, query 為“acbac”,text 為 “acaccbabb”,那么 text 中的“cba”為最長(cháng)的連續出現在 query 中的字母序列,因此, 返回結果應該為其長(cháng)度 3。請注意程序效率。

最長(cháng)公共子序列

看過(guò)《算法導論》的人應該知道，動(dòng)態(tài)規劃中一個(gè)非常經(jīng)典的例子就是LCS(Longest Common Length)最長(cháng)公共子序列問(wèn)題。下面我們來(lái)回顧一下LCS的概念。

? ? 假設有兩個(gè)字符串，X=，Y=，那么它們的最長(cháng)公共子序列為，它的特點(diǎn)在于每個(gè)字符可以不連續。LCS問(wèn)題在實(shí)際中也有非常多的應用，比如說(shuō)用于論文查重等。

? ? 都說(shuō)表達一個(gè)動(dòng)態(tài)規劃算法的精髓在于狀態(tài)轉移方程，那么我們就順便回憶一下LCS的狀態(tài)轉移方程吧。如果用c[i, j]來(lái)表示序列Xi和Yi的LCS的長(cháng)度，那么有狀態(tài)轉移方程：

?
? ? 下面進(jìn)入本文的重點(diǎn)。如果將LCS的條件加嚴，要求子序列中的字符必須是連續的。那么應該如何求解這個(gè)最長(cháng)公共連續子序列呢？

? ? 為了便于書(shū)寫(xiě)，后文中再提到“最長(cháng)公共連續子序列”，我都一律用STRICT-LCS代替。

? ? 為了便于理解，還是用之前的兩個(gè)字符串來(lái)舉例說(shuō)明什么是STRICT-LCS。X=，Y=。那么它們的最長(cháng)公共連續子序列為。

? ? 我們仍然用Dynamic Programming求解。只不過(guò)在原來(lái)的基礎上需要改變。首先，我們定義c[i, j]跟原來(lái)的意義略有不同。這里c[i, j]指的是最后一個(gè)元素為Xi(=Yj)的STRICT-LCS的長(cháng)度，比如X=,Y=那么c[3, 3]=0，不管前面如何，如果Xi和Yj不相等，就得將c[i, j]清零，作為新的開(kāi)始。

? ? LCS中，c[i, j]的值隨著(zhù)i、j值增大而漸漸增大，有累計效應；但是STRICT-LCS中，c[i, j]的值隨時(shí)可能在某個(gè)時(shí)刻被清零。