腾讯 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  

#include

#include  

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

#include  

#include  

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

{ 

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服务器解析，并实时传输到后台统计系统，请逆设计该“后台统计系统”，以完成统计。