2021年京東技術類（程序員）面試題

第1題：

?一、不定項選擇題

1、關于HTTP協議的說法，以下哪些說法是不正確的（）？ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?

A、有狀態，前后請求有關聯關系 ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?

B、FTP也可以使用HTTP協議 ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?

C、HTTP響應包括數字狀態碼，200代表此次請求有正確返回 ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?

D、HTTP和TCP，UDP在網絡分層里是同一層次的協議?????????????????

答案：ＡＢＤ

解析：

Ａ：Http是無狀態的協議

Ｂ：FTP有兩個端口，并且應用場景不一樣，協議的標準自然不一樣

Ｄ：HTTP是應用層的協議，而TCP/UDP是傳輸層的協議

第2題：

?二、單選題

2、以下代碼運行結果為（）

#include

int main()

{

??? uint32_t a = 100;

??? while (a > 0)

??? {

??? ? ? --a;

??? }

??? printf("%d", a);

??? return 0;

}

???????????

A、-1

B、100

C、0

D、死循環

答案：C

解析：Unsigned int型數字最小為0，因此不是死循環，a到0就跳出循環，最后輸出0

第3題：

3、以下哪種排序算法需要開辟額外的存儲空間（）??

A、選擇排序

B、歸并排序

C、快速排序

D、堆排序

答案：B

解析：歸并算法基本操作是合并兩個已經排序的表，因為這兩個表是已經排序的，所以若將輸出放到第三個表中則該算法可以通過對輸入數據一趟排序來完成，因此是需要額外存儲空間的

第4題：

?4、如果將固定塊大小的文件系統中的塊大小設置大一些，會造成（）。????

A、更好的磁盤吞吐量和更差的磁盤空間利用率

B、更好的磁盤吞吐量和更好的磁盤空間利用率

C、更差的磁盤吞吐量和更好的磁盤空間利用率

D、更差的磁盤吞吐量和更差的磁盤空間利用率

答案：A
解析：使用多大的塊大小，需要根據你的系統綜合考慮，如果系統用作郵件或者新聞服務器，使用較大的塊大小，雖然性能有所提高，但會造成磁盤空間較大的浪費。比如文件系統中的文件平均大小為2145byte，如果使用4096byte的塊大小，平均每一個文件就會浪費1951byte空間。如果使用1024byte的塊大小，平均每一個文件會浪費927byte空間。

第5題：

?5、若一顆二叉樹的前序遍歷為a,e,b,d,c,后序遍歷為b,c,d,e,a，則根節點的孩子節點（）

A、只有e

B、有e，b

C、有e，c

D、不確定

答案：A

解題思路：由先序遍歷第一個結點為a,則可知道樹的根節點為a。后序遍歷序列中根節點會把序列分為左右兩段，左段為左子樹上結點，右段為右子樹上結點，所以由后序遍歷序列可知b,c,d,e均為a結點的左子樹上的點，a不存在右子樹。再由先序遍歷序列知道e為根結點a的左孩子結點。即根節點的孩子結點只有e，且為左孩子。

第6題：

?6、在一個世世代代都重男輕女的村莊里，村長決定頒布一條法律，村子里沒有生育出兒子的夫妻可以一直生育直到生出兒子為止，假設現在村子上的男女比例是1:1，這條法律頒布之后的若干年后村子的男女比例將會（）???????

A、男的多

B、女的多

C、一樣多

D、不能確定

答案：B

解析：

用概率論中的期望來解這道題目。

假設生男生女的比例是0.5:0.5，即一樣。

那么一對夫妻，他們生的孩子是男孩的期望為

E(男孩)=1*0.5+1*0.52+。。。+1*0.5n=1-0.5n。

上面的公式說明的是一對夫妻，第一次生到男孩的概率是0.5，如果第一次生不到男孩，則第二次生男孩的概率為0.52,....則第n次才生到男孩的概率是0.5n

當n--》無窮大時，E(男孩)=1，即一對夫妻生男孩的期望數是1個，這和我們想的一樣，因為無論怎么生，生到1個男孩就停止，沒有生到就繼續生下去，無論如何，也只有一個男孩。

接下來，分析一下他們生女孩的期望數

E(女孩)=0*0.5+1*0.5+(1*0.5+0.52)+...+(1*0.5+0.52+...+0.5n-1)=(n-1)*0.5+(n-2)*0.52...0.5n-1=n*0.5-1+0.5n。

所以，上面的公式說明一對夫妻，第一次生到男孩，則生女孩數為0，第二次才生到男孩，則此時有1個女孩，這種生法概率為0.5,。。。則第n次才生到男孩，則此時已有n-1個女孩，這種生法的概率為(1*0.5+0.52+...+0.5n-1)，要是連續沒有生到男孩，那他們會一直生下去，即當n--》無窮大時，E(女孩)=n=無窮大。所以，如果一直沒有生到男孩子，則女孩會越來越多。

所以，一對夫妻他們生的男孩：女孩的比例約為1：n（n為自然數）。

可以知道，只有當n<1時，女孩比例才會比男孩小。

不過我們可以發現在數軸上，（0,1）區間要比（1，無窮）區間的長度小得多，這說明n>1的概率要大于n<1的概率。所以一對夫妻生女孩數大于男孩數的概率要比 ?生男孩數大于女孩數的概率 大。

那么對于村里m對夫妻的情況，當m足夠大的時候，根據大數定律，這樣的情況更明顯，即夫妻生女孩數大于男孩數的概率要比 ?生男孩數大于女孩數的概率 大。

所以，按照這種規定，之后男女比例會失調，女孩會比男孩多。

這也和重男輕女造成的結果互相吻合。

第7題：

?7、批處理操作系統的目的是（）。

A、提高系統資源利用率

B、提高系統與用戶的交互性能

C、減少用戶作業的等待時間

D、降低用戶作業的周轉時間

答案：A

解析：批處理操作系統不具有交互性，它是為了提高CPU的利用率而提出的一種操作系統。

第8題：

?8、設有一個關系：DEPT(DNO,DNAME),如果要找出倒數第三個字母為W，并且至少包含4個字母的DNAME，則查詢條件子句應寫成WHERE DNAME LIKE（）?????

A、'_ _W_%'

B、'_%W_ _'

C、'_W__'

D、'_W_%'

答案：B

解析：在SQL語言中，我們可以使用兩個通配符：%和_，其中“%”表示0個或多個字符，而“_”則表示一個字符。在本題的查找條件中，要求倒數第三個字母為W，應表示成“W_ ?_”，并且還要求至少包含4個字母，而當以“%”開頭時，它表示的字符可以不存在，所以開頭應加一個“_”，那么查詢條件子句應寫成WHERE ?DNAME LIKE'_% W_ _'。

第9題：

9、已知的一個無向圖（邊為正數）中頂點A,B的一條最短路P，如果把各個邊的權重（即相鄰兩個頂點的距離）變為原來的2倍，那么在新圖中，P仍然是A,B之間的最短路，以上說法是（）

A、錯誤

B、正確

答案：B

?

第10題：

?10、如下程序的時間復雜度為（其中m>1,e>0）（）

x = m;

y = 1;

while （x - y > e）

{

x = (x + y) / 2;

??? y = m / x;

}

print(x);

???????????

A、log m

B、m的平方

C、m的1/2方

D、m的1/3方

答案：A

解析：

算法的時間復雜度O（n）,在n比較小的時候，規律不明顯。想象一下，logX,X1/2,X1/3函數的曲線，在x比較小時區別不大。但是當x比較大時差別比較明顯。

所以我們在取m>1,e>0時，不妨將m取較大數，e取較小數(當m較大時e相當于0)。然后看函數內部執行。

x=m,y=1;

x-y>0;

?

1.x=(x+y)/2=(m+1)/2 m非常大，則 x=m/2;

y=m/x, x=m/2 則 y=2;

?

2.x=(x+y)/2=(m/2+2)/2=m/4+1 m非常大，則 x=m/4; ? ?

y=m/x, x=m/4 則 y=4;?????

3.x=(x+y)/2=(m/4+4)/2=m/8+2?m非常大，則 x=m/8;

y=m/x, x=m/8 則 y=8;
?

........

x=m/2n,y=2n

當x-y=m/2 ? ? n ? ? -2 ? ? n=0時 m/2 ? ? n ? ? -2 ? ? n=0 m=22n => n=(logm)/2

第11題：

?11、求fun（484）的返回值（）?

bool fun(int n){

?????int sum=0;

?????for(int i=1;n>sum;i=i+2)

?????????sum=sum+i;

?????return (n==sum);

}

????????

A、True

B、False

答案：A

解析：

loop 1：sum=1, i=3
loop 2：sum=4, i=5
loop 3：sum=9, i=7
loop 4：sum=16,i=9
loop 5：sum=25,i=11
loop 6：sum=36,i=13
loop 7：sum=49,i=15
...
通過規律可以發現sum的值為循環次數的平方，22*22=484，循環退出時sum=484，函數返回true。
?

第12題：

?12、關于主對角線（從左上角到右下角）對稱的矩陣為對稱矩陣；如果一個矩陣中的各個元素取值為0或1，那么該矩陣為01矩陣，求大小為N*N的01對稱矩陣的個數？（）????

A、power(2，n)

B、power(2，n*n/2)

C、power(2，(n*n+n)/2)

D、power(2，(n*n-n)/2)

答案：C

解析：

對稱矩陣由它的上三角矩陣唯一確定。

只要它主對角線和主對角線右上方的元素都確定了。主對角線左下方的元素根據對稱的原則便可確定。

因此需要確定n*(n+1)/2個元素

第13題：

13、現代的語言（如Java）的編譯器的詞法分析主要依靠（）。??????????

A、有限狀態自動機

B、確定下推自動機

C、非確定下推自動機

D、圖靈機

答案：A

解析：詞法分析階段是編譯過程的第一個階段。這個階段的任務是從左到右一個字符一個字符地讀入源程序，即對構成源程序的字符流進行掃描然后根據構詞規則識別單詞(也稱單詞符號或符號)。

第14題：

?14、如下函數的f(1)的值為(? )

int f(int n){

????static int i=1;

?????if(n>=5)

?????????return n;

?????n=n+i;

?????i++;

?????return f(n);

}

??? ????????

A、5

B、6

C、7

D、8

答案：C

解析：該函數為遞歸調用。

f(1)：n=2;i=2;調用f(2)
f(2)：n=4;i=3;調用f(4)
f(4)：n=7;i=4;調用f(7)
f(7)：返回7
即最終函數返回結果為7

第15題：

?二、填空題

15、123456789101112...2021除以9的余數是（?? ）

答案：1

分析：這個大數可分解為 1 * 10n + 2 * 10n-1 + ... ?+?2021 * 100?（①式）。而 10m?- 1 （m為自然數）都可以被 9 ? 整除。將①式減掉 1 * 9999...9（共n-1個9）+ 2 * 9999...9（共n-2個9）... + 2021 * 9 ? 之后余數不變。這問題轉化為求 1 + 2 + ... + 2021 的余數，1一直加到2021的和為(1+2021)*2021/2 ? ?=?2029105，?2029105 MOD 9 = 1。所以余數為 1。

第16題：

?三、解答題

16、給定字符串（ASCII碼0-255）數組，請在不開辟額外空間的情況下刪除開始和結尾處的空格，并將中間的多個連續的空格合并成一個。例如：" ? i ? ?am a ? ? ?little boy. ? ?"，變成"i am a little boy",語言不限，但不要用偽代碼作答，函數輸入輸出請參考如下的函數原型：

C++函數原型：

void FormatString(char str[],int len){

}

? ?

答案：

char* removeEmpty(char *str, char ch) {

????char *it1 = str;

????char *it2 = str;

????while (*it2 != '\0') {

????????//while (*it2 == ch) {it2++; }

????????while (*it2 == ch ?&& *(it2 + 1) == ch)

????????{

????????????it2++;

????????}

????????*it1++ = *it2++;

????}

?????return str;

}

void FormatString(char str[], int len){

????str = removeEmpty(str, ' ');

}

第17題：

?17、給定一顆二叉樹，以及其中的兩個node（地址均非空），要求給出這兩個node的一個公共父節點，使得這個父節點與兩個節點的路徑之和最小。描述你程序的最壞時間復雜度，并實現具體函數，函數輸入輸出請參考如下的函數原型：
C++函數原型：

strucy TreeNode{

?????TreeNode* left; ? //指向左子樹

?????TreeNode* right; ? //指向右子樹

?????TreeNode* father; ? //指向父親節點

};

TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){

}

答案：由于有父節點指針，這道題目的難度一下子就降低了許多。

思路一：我們首先找到兩個節點的高度差，然后從較靠近根結點的一層開始向上找，若父節點為同一節點則該節點為解。

int getHeight(TreeNode *node) {

??? int height = 0;

??? while (node) {

??? ? ? height++;

??? ? ? node = node->parent;

??? }

??? return height;

}

?

TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {

??? int height1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;

??? if (diff < 0) {

??? ? ? diff = -diff;

????????while(diff--) {

???????????? second = second->parent;

????????}

??? } else {

??????? while(diff--) {

??? ? ????? first = first->parent;

????????}

????}

??? while (first != second) {

??? ? ? first = first->parent;

??? ? ? second = second->parent;

??? }

??? return first;

}

?

思路二：若允許浪費空間，那么可以用兩個Stack來存儲從first和second到根結點的各個節點，然后出棧時比較地址是否一致，最后一個地址一致的節點為解。

兩種方法最壞時間復雜度均為O(n)。

第18題：

?18、有n枚硬幣按照0到n-1對它們進行編號，其中編號為i的硬幣面額為vi，兩個人輪流從剩下硬幣中取出一枚硬幣歸自己所有，但每次取硬幣的時候只能取剩下的硬幣中編號最小的硬幣或者編號最大的硬幣，在兩個都采用最優策略的情況下，作為先取硬幣的你請編寫程序計算出你能獲得硬幣總面額的最大值？（請簡述算法原理，時間復雜度并實現具體的程序），語言不限。

int MaxValue(int v[],int n){

}

? ?

答案：

/*區間dp？？？*/

int MaxValue(int v[],int n)

{

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

??? ? ? dp[i][i] = v[i];

??? for(int i=n-1;i>=1;i--)

??? {

??? ? ? for(int j=i+1;j<=n;j++)

??? ? ? ? ? //區間dp

??? ? ? ? ? dp[i][j] = max(dp[i+1][j]+v[i],dp[i][j-1]+v[j]);

??? }

??? return dp[1][n];

}