人人 2021 研發崗面試題

?一、單選題

3417（34的17次方）對6取余， 結果是多少？

?????????

A? 2

B? 3

C? 4

D? 5

?C

34^17=(30+4)^17，然后二項展開，30^17能被6整除，且展開項中只要有30的項都能被7整除，余數必然在4^17中產生，容易得到，4任意次方的余數都是4。所以答案是4。

第2題：

?有如下算式成立，13*7=88，是采用（）進制計算的。

?

A? 14

B? 13

C? 12

D? 11

?B

14進制換算成10進制 ?如a選項計算（14+3）*7是否等于8*14+8?

以此類推哪個成立選哪個

答案是b

第3題：

?有字符序列（Q,H,C,Y,P,A,M,N,R,D,F,X）,新序列（M,H,C,D,F,A,Q,N,R,Y,P,X）是下列（）排序算法一趟掃描結果。

??????

A? 希爾排序

B? 快速排序

C? 堆排序

D? 冒泡排序

?A

應該是希爾排序，是中間相隔5個字母進行的希爾排序，第一次比較是：Q-M H-N C-R Y-D P-F A-X依次比較交換位置。

第4題：

?二叉排序樹中的最小值在二叉排序樹的何處?

??????

A? 只能在根節點

B? 只能在葉子節點

C? 可能在葉子節點， 也可能在根節點，也可能在只有右孩子的父節點

D? 可以在任何節點

?C

二叉排序樹中的最小值節點就是最左邊的那個，當只有一個根節點的時候，最小值就位于根節點了。

第5題：

?一個含有n個頂點和e條邊的簡單無向圖， 在其鄰接矩陣存儲結構中共有（）個零元素。

????????

A? e

B? 2e

C? n的2次方-e

D? n的2次方-2e

?D

因為有n個頂點，所以有n*n個元素，2*e個非零元素（無向圖，對稱），所以有n*n-2*e個零元素。

第6題：

?下面程序中， 輸出是什么？

int fun(int x){

????int count = 0;

????while(x){

????????count++;

????????x = x &(x-1)

????}

????return count;

}

int main(){

????cout << "fun(2021)=" << fun(2021)<

}

? ????????

A? fun(2021)=11

B? fun(2021)=10

C? fun(2021)=9

D? fun(2021)=8

?B

本題是統計一個數有多少個1的，2021=11111011111共10個1.

第7題：

?若系統中有五臺繪圖儀，有多個進程均需要使用兩臺，規定每個進程一次僅允許申請一臺，則至多允許（ ）個進程參于競爭，而不會發生死鎖。

?????????

A? 2

B? 3

C? 4

D? 5

?C

4臺，當5個進程的時候如果都同時申請到了1臺，就發生死鎖了。如果是4個進程，那必然有一個能申請到2臺。

第8題：

?通過文件名存取文件時，文件系統內部的操作過程是通過？

??

A? 文件在目錄中查找文件數據存取位置。

B? 文件名直接找到文件的數據，進行存取操作。

C? 文件名在目錄中查找對應的i節點，通過i節點存取文件數據。

D? 文件名在目錄中查找對應的超級塊，在超級塊查找對應i節點，通過i節點存取文件數據

?C

如果一個文件有多個數據塊，這些數據塊很可能不是連續存放的，應該如何尋址到每個塊呢？實際上，根目錄的數據塊是通過其inode中的索引項Blocks[0]找到的，事實上，這樣的索引項一共有15個，從Blocks[0]到Blocks[14]，每個索引項占4字節。前12個索引項都表示塊編號，例如上面的例子中Blocks[0]字段保存著24，就表示第24個塊是該文件的數據塊，如果塊大小是1KB，這樣可以表示從0字節到12KB的文件。如果剩下的三個索引項Blocks[12]到Blocks[14]也是這么用的，就只能表示最大15KB的文件了，這是遠遠不夠的，事實上，剩下的三個索引項都是間接索引。

第9題：

?以下哪個協議不是無狀態協議？

?????

A? TCP協議

B? HTTP協議

C? UDP協議

D? FTP協議

?A

無狀態服務器是指一種把每個請求作為與之前任何請求都無關的獨立的事務的服務器 ?

<>(第二版)第546頁有這樣一句話: ? ?
?????雖然HTTP使用TCP的服務,但HTTP本身是無狀態協議.客戶發送請求報文來初始化這個事務.服務器發送響應來回答. ?

暗示了TCP協議是一個有狀態的協議

第10題：

?二、填空題

12個元素的排序數組進行二分查找，每個元素被查找的概率是相等的，平均比較次數為_______ 。

?37/12

平均查找長度公式為：ASL={[(n+1)/n]*log2^(n+1)}-1，也可以直接算出來，1*1+2*2+3*4+4*5=37，故其次數為37/12。

第11題：

?（a1+a2+a3+…+an)/b與a1/b+a2/b+…an/b（除法為整除）最大差值為?_______? 。

?n-1

假設a[i]=m[i]*b+(b-x[i]),m[i]為整數,x[i]趨近于0，sum = x[i](i = ?0->n),sum也趨近于0

令X =（a1+a2+...+an）/b = m[1]+m[2]+m[3]...+m[n]+(n*b-sum)/b;

? Y = a1/b+a2/b+...+an/b = m[1]+m[2]+...+m[n];

? X-Y=(n*b-sum)/b

? [X-Y] = n-1;([]表示取整數，因為X-Y = n-sum/b

第12題：

?三、問答題

某星球上出現了一種怪物， 這種怪物是單親繁殖，從出生起第3個月起每個月就能繁衍一批后代共m個，但是這種怪物很短命，生存第5個月后就會斃命。目前該星球有一個這樣的怪物，請編寫程序計算n個月后怪物的總數。(這里我們假定第5個月怪物繁衍后再斃命)

?

#include

using namespace std;

int sum(int n,int m)

{

????int res=1;

????int A[100];

????A[0]=1;

????A[1]=0;

????A[2]=0;

????if(n<3)

????????return res;

????for(int i=3;i<=n;i++)

????{???

????????A[i]=(res-A[i-1]-A[i-2])*m;

????????res+=A[i];

????????if(i>=5)

????????????res-=A[i-5];

????}

????return res;

}

int main()

{

????int n,m;

????cin>>n>>m;

????cout<

????return 0;

}

第13題：

?有一個二叉樹， 節點全部為整數，如何找到一個子樹，它所有節點的和最大？要求編程序實現。

?使用遞歸方法，可以使用前序遍歷，首先分別計算左右子樹各自的子樹和，然后記錄目前最大的；

再加入當前的父節點，再計算父節點開頭的子樹是否最大；該層遞歸上去即可。

public class MaxSumSubTree {
? ? class TreeNode{
? ? ? ? TreeNode left,right;
? ? ? ? int tag;
? ? ? ? TreeNode(int tag){
? ? ? ? ? ? this.tag = tag;
? ? ? ? }
? ? }

? ? private TreeNode maxRoot = new TreeNode(0);
? ? public int find(TreeNode root){
? ? ? ? if(root==null){
? ? ? ? ? ? return 0;
? ? ? ? } else{
? ? ? ? ? ? int lSum = find(root.left);
? ? ? ? ? ? int rSum = find(root.right);
? ? ? ? ? ? if(maxRoot.tag ? ? ? ? ? ? ? ? maxRoot = root.left;
? ? ? ? ? ? if(maxRoot.tag ? ? ? ? ? ? ? ? maxRoot = root.right;
? ? ? ? ? ? return root.tag+lSum+rSum;
? ? ? ? }
? ? }
}

第14題：

?一般在大型系統中，都會為每個資源分配一個唯一的ID，在大型系統中這個并非易事，目前人人網一天產生新鮮事在千萬量級，現在由你來設計一個產生新鮮事ID的模塊。要求寫出解題思路和偽代碼。

拿分法寶：

1） 新鮮事ID絕對不能重復

2）你可以借助DB等輔助工具，提供InsertDB， UpdateDB， QueryDB三API供你使用， 假設訪問DB不會有異常。
3) ?高并發情況要考慮， 提供Lock, Unlock兩個API供你使用。
4） 要求寫出解題思路和偽代碼出來。

?解題思路：

1、使用單例模式。定義一個sequenceGenerator單例類， ? 聲明一個getSequence方法，將sequence序號依次相加 ? 。

2、產生 ? ID ? 的規則是：將 ? ID設置為字符串。ID =? ? 當前日期+整型sequence。

偽代碼：

public class SequenceGenerator {

private SequenceGenerator generatorInstance = null;

private long sequence = 0;

private SequenceGenerator (){}

public static SequenceGenerator getInstance(){

? ?if(generatorInstance == null){

? ? ? synchoronized(this){

? ? ? ?generatorInstance ?= new SequenceGenerator ();

? ?}

? ?return generatorInstance ?;

?}

}

public ? ?synchronized int getSequence(){

? ? ?? ? if(++sequence沒有超過long型的最大值）return sequence；

? ??

}

}