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

下列關鍵字序列為堆的是______。

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

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

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

答案：D

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

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

答案：A

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

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

答案：A

有一個用數組 C[1..m]表示的環形隊列，m 為數組的長度。假設 f 為隊頭元素在數組中的位置，r 為隊尾元素的后一位置(按順時針方向)。若隊列非空，則計算隊列中元素個數的公式應為？

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

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

A.前鋒
B.守門
C.后衛
D.前鋒或守門
E.后衛或守門
F.前鋒或后衛

答案：C

二分查找樹里查詢一個關鍵字的最壞時間復雜度是______

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

答案：A

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

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

答案：A

并發進程執行的相對速度是______。

A.由進程的程序結構決定
B.由進程本身來控制
C.進程被創建時決定
D.與進程調度策略有關
E.與進程的銷毀時間有關
F.由內存分配策略決定

答案：D

某團隊有 2/5 的人會寫 Java 程序，有 3/4 的人會寫 C++程序，這個團隊里同時會寫 Java 和 C++的最少有______人。

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

答案：A

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

A.把所有的純凈水全部倒入瓶子，然后把水倒掉
B.將純凈水平均分成兩份，用每一份清水洗一遍瓶子。
C.每次注入體積為 v 的純凈水清洗瓶子，直到純凈水用盡
D.每次注入體積為 2v 的純凈水清洗瓶子，直到純凈水用盡
E.將用過的水重新諸如瓶子，多次清洗
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

畢業典禮后，某宿舍三位同學把自己的畢業帽扔了，隨后每個人隨機地拾起帽子，三個人中沒有人選到自己原來帶的帽子的概率是

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

答案：B

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

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

答案：D

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

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

答案：F

第16題：

若干個等待訪問磁盤者依次要訪問的磁道為 19， 43， 40， 4， 79，11，76，當前磁頭位于 40 號柱面，若用最短尋道時間優先磁盤調度算法，則訪問序列為___

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++內存分配中說法錯誤的是：______。

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

答案：A

下列關于網絡編程錯誤的是______。

A.UDP 是不可靠服務
B.主動關閉的一端會出現 TIME_WAIT 狀態
C.服務端編程會調用 listen(),客戶端也可以調用 bind()
D.TCP 建立和關閉連接都只需要三次握手
E.Linux 通過提供提供 socket 接口來進行網絡編程
F.長連接相對短連接可以節省建立連接的時間

答案：D

在 32 位操作系統中，下列類型占用 8 個字符的為______。

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 進制 則:______

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

[問答題]

題目描述

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

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

[問答題]

題目描述

寫一個函數,輸入一個二叉樹,樹中每個節點存放了一個整數值,函數返回這棵二叉樹中相差最大的兩個節點間的差值絕對值。請注意程序效率。

先求每個子樹的最大值和最小值,遞歸實現。

[問答題]

題目描述：

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

最長公共子序列

看過《算法導論》的人應該知道，動態規劃中一個非常經典的例子就是LCS(Longest Common Length)最長公共子序列問題。下面我們來回顧一下LCS的概念。

? ? 假設有兩個字符串，X=，Y=，那么它們的最長公共子序列為，它的特點在于每個字符可以不連續。LCS問題在實際中也有非常多的應用，比如說用于論文查重等。

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

?
? ? 下面進入本文的重點。如果將LCS的條件加嚴，要求子序列中的字符必須是連續的。那么應該如何求解這個最長公共連續子序列呢？

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

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

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

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