騰訊 2021年數據庫管理SQL面試題

數據庫表設計最合理的是 （）

A.學生{id,name,age} ,學科{id,name} 分數{學生id，學科id，分數} 

B.學生{id,name,age} ,分數{學生id，學科名稱，分數} 

C.分數{學生姓名，學科名稱，分數} 

D.學科{id,name},分數{學生姓名，學科id，分數}

A

在數據庫系統中，產生不一致的根本原因是 （）

A．數據存儲量太大 B．沒有嚴格保護數據 C．未對數據進行完整性控制 D．數據冗余

D

15L和27L兩個杯子可以精確地裝（  ）L水？

A. 53 B. 25 C. 33 D. 52

C

考慮左遞歸文法 S->Aa|b、 A ->Ac | Sd |e，消除左遞歸后應該為（ ） 

A.S->Aa|b A->bdA'|A' A->cA'|adA' |ε

B.S->Ab|a A->bdA'|A  A->cA'|adA' |ε

C.S->Aa|b A->cdA'|A' A->bA'|adA' |ε

D.S->Aa|b A->bdA'|A' A->caA'|dA' |ε

A

下列排序算法中，初始數據集合對排序性能無影響的是（） 

A．插入排序 B．堆排序 C．冒泡排序 D．快速排序

B

插入和冒泡再原數據有序的情況下會出現性能的極端情況（O(n)，O(n^2)）.快速排序在對一個基本有序或已排序的數組做反向排序時，每次patition的操作，大部分元素都跑到了一遍，時間復雜度會退化到O(n^2)。

二分查找在一個有序序列中的時間復雜度為（ ） 

A.O(N) B.O(logN) C.O(N*N) D.O(N*logN)

b

路由器工作在網絡模型中的哪一層（ ）？

A.數據鏈路層

B.物理層

C.網絡層

D.應用層

C

對于滿足SQL92標準的SQL語句：select foo,count(foo) from pokes where foo>10 group by foo having count(*)>5 order by foo，其執行順序應該是（ ）

A.FROM ->WHERE -> GROUP BY -> HAVING -> SELECT ->ORDER BY 

B.FROM ->GROUP BY ->WHERE ->  HAVING -> SELECT ->ORDER BY 

C.FROM ->WHERE -> GROUP BY -> HAVING ->ORDER -> BYSELECT  

D.FROM ->WHERE ->ORDER BY -> GROUP BY -> HAVING -> SELECT  

A

SQL Select語句完整的執行順序： 1）from子句組裝來自不同數據源的數據； 

2）where子句基于指定的條件對記錄行進行篩選；

3）group by子句將數據劃分為多個分組；

4）使用聚集函數進行計算； 5）使用having子句篩選分組； 6）計算所有的表達式； 

7）使用order by對結果集進行排序。 只有select選出了相應的表 才能對其排序，刪除之類的操作，因此 合理的答案應該為 from --where-- group by-- having --select-- order by

UNIX系統中，目錄結構采用( )

Ａ．單級目錄結構 Ｂ．二級目錄結構 Ｃ．單純樹形目錄結構 Ｄ．帶鏈接樹形目錄結構

B

請問下面的程序一共輸出多少個“-”( ) 

#include <stdio.h> 

#include <sys/types.h>

#include <unistd.h> 

int main(void) 

{ int i;

for(i=0; i<2; i++) 

{ fork(); //復制父進程，調用一次，返回兩次 

printf("-"); //緩沖區數據 

}

 return 0; 

} 

A.2個 B .4個 C.6個 D.8個

D

請問下面的程序一共輸出多少個“-”？

#include <stdio.h>

#include <sys/types.h> 

#include <unistd.h> 

int main(void) 

{ int i; 

for(i=0; i<2; i++) 

{ fork(); //復制父進程，調用一次，返回兩次

 printf("-\n"); //緩沖區數據 

} 

return 0;

} 

A.2個 B .4個 C.6個 D.8個

C

避免死鎖的一個著名的算法是（ ） 

A.先入現出法 B.銀行家算法 C.優先級算法 D.資源按需分配法

B

怎么理解分配延遲（dispatch lantency） (  )

A.分配器停止一個進程到開啟另一個進程的時間 

B. 處理器將一個文件寫入磁盤的時間 

C. 所有處理器占用的時間 

D.以上都不對

A

以下哪一個不是進程的基本狀態？( ) 

A. 阻塞態 B.執行態 C.就緒態 D. 完成態

D

假定我們有3個程序，每個程序花費80%的時間進行I/O，20%的時間使用CPU。每個程序啟動時間和其需要使用進行計算的分鐘數如下，不考慮進程切換時間。

程序編號         1      2       3

啟動時間        00:00    00:10    00:15

需要CPU時間（分鐘） 3.5     2       1.5

請問在多線程/進程環境下，系統的總響應時間是（） 

A.22.5 B.23.5 C.24.5 D.25.5

B

在所有非搶占CPU調度算法中，系統平均響應時間最優的是（ ） 

A.實時調度算法 B.短任務優先算法 C.時間片輪轉算法 D.先來先服務算法

C

什么是內存抖動（Thrashing）? 

A.非常頻繁的換頁活動 B.非常高的CPU執行活動 C.一個極長的執行進程 D.一個極大的虛擬內存交換活動

A

Belay's Anomaly 出現在哪里（ ） 

A.內存管理算法 B.內存換頁算法 C.預防死鎖算法 D.磁盤調度算法

B

下面的函數使用二分查找算法，對已按升序排序的數組返回所要查找的數值的數據位置，請填寫缺少的兩句語句：

int* BinarySearch(int* arrayAddress, int arrayLength, int valueToSearch) 

{ int head = 0 ; 

int tail = arrayLength - 1; 

while(head < tail) { 

mid = (head + tail)/2; 

if(arrayAddress[mid] > valueToSeatcj) tail = mid - 1;

 else head= mid + 1; 

} 

if(tail < arrayLength && arrayAddress[tail] == valueToSearch) return &arrayAddress[tail]; 

else

return NULL; 

}

tail = mid -1 ;

head = mid + 1;

一個有N個正數元素的一維數組（A[0], A[1], A[2]...,A[N-1]）, 求連續子數組和的最大值。 

int max(int a,int b) int MaxSum(int *A, int length) 

{ 

int nStart = A[0]; 

int nAll = A[0]; 

for(int i=1; i<lenght; i++) 

{ 

nStart = max(nAll + A[i], 0); 

nAll = max(nAll, nStart);

} 

return nAll; 

}

nStart = max(nAll + A[i] , 0); nAll = max(nAll, nStart);

最長遞增子序列（LIS）表示在一個序列中，保持遞增的最長子序列，比如（2，1，4，2，3，7，4，6）的LIS是{1,2,3,4,6},則LIS的長度是  . 對于一個有N個元素的序列，得到LIS的長度的最優時間復雜度是  ，空間復雜度是    

5

O(nlogn)

o(n)

給一系列的數1，2，3，，，n(有序的)和一個棧（stack），這個棧無限大，將這n個數按照順序放入棧中，但是隨機的從棧中彈出，n=5，一共有多少中彈棧方式。

42

這是卡特蘭數的典型應用。Catalan數的定義令h(1)=1，Catalan數滿足遞歸式：h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1)，n>=2該遞推關系的解為：h(n) = C(2n,n)/(n+1)，n=1,2,3,...（其中C(2n,n)表示2n個中取n個的組合數）

 h(5) = C(10,5)/6 = 42

其他方向附加題 

微博廣告投放是騰訊收入來源之一，為了保證投放的廣告對用戶更有幫助，必須分析用戶對什么最感興趣。用戶的每條微薄都可以拆分成幾個關鍵字，騰訊微博每個月會收集到上T的關鍵字，請你分析出其中出現次數最多的十個關鍵字。

騰訊新聞首頁改版之后，為了精確掌握改版效果，需要準實時統計每篇文章的IP數量，即從文章發表之后，有多少個不同的ip的用戶讀過這篇文章。每個用戶訪問請求都會被web服務器解析，并實時傳輸到后臺統計系統，請逆設計該“后臺統計系統”，以完成統計。