2020年百度精选面试题及答案

2020年百度精选面试题及答案

浏览器获取输入的域名

浏览器向域名系统 DNS 请求解析

DNS 解析出百度服务器的 IP 地址

浏览器与服务器建立 TCP 连接（默认端口 80）

浏览器发出 HTTP 请求，请求百度首页

服务器通过 HTTP 请求把首页文件发给浏览器

TCP 连接释放

浏览器解析首页文件，展示 web 界面

2. 请描述 C/C++程序的内存分区?

其实 C 和 C++的内存分区还是有一定区别的，但此处不作区分：

1）、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。

其

操作方式类似于数据结构中的栈。

2）、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由

OS 回

收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。

3）、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初

始化的

全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻

的另

一块区域。 - 程序结束后由系统释放。

4）、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放。

5）、程序代码区—存放函数体的二进制代码。

栈区与堆区的区别：

1）堆和栈中的存储内容：栈存局部变量、函数参数等。堆存储使用 new、malloc 申请

的变量等；

2）申请方式：栈内存由系统分配，堆内存由自己申请；

3）申请后系统的响应：栈——只要栈的剩余空间大于所申请空间，系统将为程序提供

内存，否则将报异常提示栈溢出。

堆——首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请

时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结

点链表 中删除，并将该结点的空间分配给程序；

4）申请大小的限制：Windows 下栈的大小一般是 2M，堆的容量较大；

5）申请效率的比较：栈由系统自动分配，速度较快。堆使用 new、malloc 等分配，较

慢；

总结：栈区优势在处理效率，堆区优势在于灵活；

内存模型：自由区、静态区、动态区；

根据 c/c++对象生命周期不同，c/c++的内存模型有三种不同的内存区域，即：自由存

储区，动态区、静态区。

自由存储区：局部非静态变量的存储区域，即平常所说的栈；

动态区： 用 new ，malloc 分配的内存，即平常所说的堆；

静态区：全局变量，静态变量，字符串常量存在的位置；

注：代码虽然占内存，但不属于 c/c++内存模型的一部分；

3. 快速排序的思想、时间复杂度、实现以及优化方法?

快速排序的三个步骤

(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 基准（pivot）；

(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准

左边的元素都比该基准小，在基准右边的元素都比基准大；

(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

基准的选择：

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效

率会达到最大。

即：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时

间复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；

快排代码实现：

我们一般选择序列的第一个作为基数，那么快排代码如下：

void quicksort(vectorint v,int left, int right)

{

if(leftright)//false 则递归结束

{

int key=v[left];//基数赋值

int low = left;

int high = right;

while(lowhigh) //当 low=high 时，表示一轮分割结束

{

while(lowhighv[high] = key)//v[low]为基数，从后向前与基数比

较

{

high--;

}

swap(v[low],v[high]);

while(lowhighv[low] = key)//v[high]为基数，从前向后与基数比

较

{

low++;

}

swap(v[low],v[high]);

}

//分割后，对每一分段重复上述操作

quicksort(v,left,low-1);

quicksort(v,low+1,right);

}

}

注：上述数组或序列 v 必须是引用类型的形参，因为后续快排结果需要直接反映在原序

列中；

优化：

上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最

差的 o(n^2)。所以，优化方向就是合理的选择基数。

常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等），

如下：

①当序列区间长度小于 7 时，采用插入排序；

②当序列区间长度小于 40 时，将区间分成 2 段，得到左端点、右端点和中点，我们对

这三个点取中数作为基数；

③当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分

别再得到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取

中数，然后将该值作为基数。

具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：

int key=v[left];//基数赋值

if (right-left+1=7) {

insertion_sort(v,left,right);//插入排序

return;

}else if(right-left+1=8){

key=SelectPivotOfThree(v,left,right);//三个取中

}else{

//三组三个取中，再三个取中（使用 4 次 SelectPivotOfThree，此处不具体展示）

}

需要调用的函数：

void insertion_sort(vectorint unsorted,int left, int right) //插入排序算法

{

for (int i = left+1; i = right; i++)

{

if (unsorted[i - 1]unsorted[i])

{

int temp = unsorted[i];

int j = i;

while (jleftunsorted[j - 1]temp)

{

unsorted[j] = unsorted[j - 1];

j--;

}

unsorted[j] = temp;

}

}

}

int SelectPivotOfThree(vectorint arr,int low,int high)

//三数取中，同时将中值移到序列第一位

{

int mid = low + (high - low)/2;//计算数组中间的元素的下标

//使用三数取中法选择枢轴

if (arr[mid]arr[high])//目标: arr[mid] = arr[high]

{

swap(arr[mid],arr[high]);

}

if (arr[low]arr[high])//目标: arr[low] = arr[high]

{

swap(arr[low],arr[high]);

}

if (arr[mid]arr[low]) //目标: arr[low] = arr[mid]

{

swap(arr[mid],arr[low]);

}

//此时，arr[mid] = arr[low] = arr[high]

return arr[low];

//low 的位置上保存这三个位置中间的值

//分割时可以直接使用 low 位置的元素作为枢轴，而不用改变分割函数了

}

这里需要注意的有两点：

①插入排序算法实现代码；

②三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然

可用。

4. 请描述 IO 多路复用机制?

IO 模型有 4 中：同步阻塞 IO、同步非阻塞 IO、异步阻塞 IO、异步非阻塞 IO；IO 多路

复用属于 IO 模型中的异步阻塞 IO 模型，在服务器高性能 IO 构建中常常用到。

同步异步是表示服务端的，阻塞非阻塞是表示用户端，所以可解释为什么 IO 多路复用

（异步阻塞）常用于服务器端的原因；

文件描述符（FD，又叫文件句柄）：描述符就是一个数字，它指向内核中的一个结构体

(文件路径，数据区等属性)。具体来源：Linux 内核将所有外部设备都看作一个文件来

操作，对文件的操作都会调用内核提供的系统命令，返回一个 fd(文件描述符)。

下面开始介绍 IO 多路复用：

（1）I/O 多路复用技术通过把多个 I/O 的阻塞复用到同一个 select、poll 或 epoll 的

阻塞上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。与传统的多线

程/多进程模型比，I/O 多路复用的最大优势是系统开销小，系统不需要创建新的额外

进程或者线程。

（2）select，poll，epoll 本质上都是同步 I/O，因为他们都需要在读写事件就绪后自

己负责进行读写，也就是说这个读写过程是阻塞的，而异步 I/O 则无需自己负责进行读

写，异步 I/O 的实现会负责把数据从内核拷贝到用户空间。

（3）I/O 多路复用的主要应用场景如下：

服务器需要同时处理多个处于监听状态或者多个连接状态的套接字；

服务器需要同时处理多种网络协议的套接字；

（4）目前支持 I/O 多路复用的系统调用有 select，poll，epoll，epoll 与 select 的

原理比较类似，但 epoll 作了很多重大改进，现总结如下：

①支持一个进程打开的文件句柄 FD 个数不受限制（为什么 select 的句柄数量受限制：

select 使用位域的方式来传递关心的文件描述符，因为位域就有最大长度，在 Linux

下是 1024，所以有数量限制）；

②I/O 效率不会随着 FD 数目的增加而线性下降；

③epoll 的 API 更加简单；

（5）三种接口调用介绍：

①select 函数调用格式：

#include sys/select.h

#include sys/time.h

int select(int maxfdp1,fd_set *readset,fd_set *writeset,fd_set

*exceptset,const struct timeval *timeout)

//返回值：就绪描述符的数目，超时返回 0，出错返回-1

②poll 函数调用格式：

# include poll.h

int poll ( struct pollfd * fds, unsigned int nfds, int timeout);

③epoll 函数格式（操作过程包括三个函数）：

#include sys/epoll.h

int epoll_create(int size);

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int

timeout);

（6）作用：一定程度上替代多线程/多进程，减少资源占用，保证系统运行的高效率；

5. 实践中如何优化 MySQL?

四条从效果上第一条影响最大，后面越来越小。

① SQL 语句及索引的优化

② 数据库表结构的优化

③ 系统配置的优化

④ 硬件的优化

6. 什么情况下设置了索引但无法使用?

① LIKE 语句，模糊匹配

② OR 语句

③ 数据类型出现隐式转化（如 varchar 不加单引号的话可能会自动转换为 int 型）

7. SQL 语句的优化.

1.对查询进行优化，应尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的

列上建立索引。

2.应尽量避免在 where 子句中使用!=或操作符，否则将引擎放弃使用索引而进行全

表扫描。

3.应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索

引而进行全表扫描，如：

select id from t where num is null

可以在 num 上设置默认值 0，确保表中 num 列没有 null 值，然后这样查询：

select id from t where num=0

4.应尽量避免在 where 子句中使用 or 来连接条件，否则将导致引擎放弃使用索引而

进行全表扫描，如：

select id from t where num=10 or num=20

可以这样查询：

select id from t where num=10

union all

select id from t where num=20

5.下面的查询也将导致全表扫描：

select id from t where name like %abc%

若要提高效率，可以考虑全文检索。

6.in 和 not in 也要慎用，否则会导致全表扫描，如：

select id from t where num in(1,2,3)

对于连续的数值，能用 between 就不要用 in 了：

select id from t where num between 1 and 3

7.如果在 where 子句中使用参数，也会导致全表扫描。因为 SQL 只有在运行时才会解

析局部变量，但优化程序不能将访问计划的选择推迟到运行时；它必须在编译时进行选

择。然而，如果在编译时建立访问计划，变量的值还是未知的，因而无法作为索引选择

的输入项。如下面语句将进行全表扫描：

select id from t where num=@num

可以改为强制查询使用索引：

select id from t with(index(索引名)) where num=@num

8.应尽量避免在 where 子句中对字段进行表达式操作，这将导致引擎放弃使用索引而

进行全表扫描。如：

select id from t where num/2=100

应改为:

select id from t where num=100*2

9.应尽量避免在 where 子句中对字段进行函数操作，这将导致引擎放弃使用索引而进行

全表扫描。如：

select id from t where substring(name,1,3)=abc--name 以 abc 开头的 id

select id from t where datediff(day,createdate,2005-11-30)=0--2005-11-30

生成的 id

应改为:

select id from t where name like abc%

select id from t where createdate=2005-11-30 and createdate2005-12-1

10.不要在 where 子句中的“=”左边进行函数、算术运算或其他表达式运算，否则系

统将可能无法正确使用索引。

11.在使用索引字段作为条件时，如果该索引是复合索引，那么必须使用到该索引中的

第一个字段作为条件时才能保证系统使用该索引，否则该索引将不会被使用，并且应尽

可能的让字段顺序与索引顺序相一致。

12.不要写一些没有意义的查询，如需要生成一个空表结构：

select col1,col2 into #t from t where 1=0

这类代码不会返回任何结果集，但是会消耗系统资源的，应改成这样：

create table #t(...)

13.很多时候用 exists 代替 in 是一个好的选择：

select num from a where num in(select num from b)

用下面的语句替换：

select num from a where exists(select 1 from b where num=a.num)

14.并不是所有索引对查询都有效，SQL 是根据表中数据来进行查询优化的，当索引列

有大量数据重复时，SQL 查询可能不会去利用索引，如一表中有字段 sex，male、female

几乎各一半，那么即使在 sex 上建了索引也对查询效率起不了作用。

15.索引并不是越多越好，索引固然可以提高相应的 select 的效率，但同时也降低了

insert 及 update 的效率，因为 insert 或 update 时有可能会重建索引，所以怎样

建索引需要慎重考虑，视具体情况而定。一个表的索引数最好不要超过 6 个，若太多则

应考虑一些不常使用到的列上建的索引是否有必要。

16.应尽可能的避免更新 clustered 索引数据列，因为 clustered 索引数据列的顺序

就是表记录的物理存储顺序，一旦该列值改变将导致整个表记录的顺序的调整，会耗费

相当大的资源。若应用系统需要频繁更新 clustered 索引数据列，那么需要考虑是否

应将该索引建为 clustered 索引。

17.尽量使用数字型字段，若只含数值信息的字段尽量不要设计为字符型，这会降低查

询和连接的性能，并会增加存储开销。这是因为引擎在处理查询和连接时会逐个比较字

符串中每一个字符，而对于数字型而言只需要比较一次就够了。

18.尽可能的使用 varchar/nvarchar 代替 char/nchar ，因为首先变长字段存储空间

小，可以节省存储空间，其次对于查询来说，在一个相对较小的字段内搜索效率显然要

高些。

19.任何地方都不要使用 select * from t ，用具体的字段列表代替“*”，不要返回

用不到的任何字段。

20.尽量使用表变量来代替临时表。如果表变量包含大量数据，请注意索引非常有限（只

有主键索引）。

21.避免频繁创建和删除临时表，以减少系统表资源的消耗。

22.临时表并不是不可使用，适当地使用它们可以使某些例程更有效，例如，当需要重

复引用大型表或常用表中的某个数据集时。但是，对于一次性事件，最好使用导出表。

23.在新建临时表时，如果一次性插入数据量很大，那么可以使用 select into 代替

create table，避免造成大量 log ，以提高速度；如果数据量不大，为了缓和系统表

的资源，应先 create table，然后 insert。

24.如果使用到了临时表，在存储过程的最后务必将所有的临时表显式删除，先

truncate table ，然后 drop table ，这样可以避免系统表的较长时间锁定。

25.尽量避免使用游标，因为游标的效率较差，如果游标操作的数据超过 1 万行，那么

就应该考虑改写。

26.使用基于游标的方法或临时表方法之前，应先寻找基于集的解决方案来解决问题，

基于集的方法通常更有效。

27.与临时表一样，游标并不是不可使用。对小型数据集使用 FAST_FORWARD 游标通常

要优于其他逐行处理方法，尤其是在必须引用几个表才能获得所需的数据时。在结果集

中包括“合计”的例程通常要比使用游标执行的速度快。如果开发时间允许，基于游标

的方法和基于集的方法都可以尝试一下，看哪一种方法的效果更好。

28.在所有的存储过程和触发器的开始处设置 SET NOCOUNT ON ，在结束时设置 SET

NOCOUNT OFF 。无需在执行存储过程和触发器的每个语句后向客户端发送

DONE_IN_PROC 消息。

29.尽量避免向客户端返回大数据量，若数据量过大，应该考虑相应需求是否合理。

30.尽量避免大事务操作，提高系统并发能力。

8. 在一个带头结点的单链表 HL 中,若要在第一个元素之前插

入一个由指针 p 指向的结点。其语句为？

在插入节点时:先要将待插入节点 p 的后继节点设为第一个元素, 也就是 p-next=HL

next。然后再将头结点 HL 的后继节点改为 p 节点,HL-next=p。下图中红色的箭头说

明

了插入操作执行的顺序,如果顺序不当,就会丢失指向第一个元素的指针,破坏链表结构

其语句为： p-next=HL-next; HL-next=p;

9. 如何设计一个高并发的系统?

① 数据库的优化，包括合理的事务隔离级别、SQL 语句优化、索引的优化；

② 使用缓存，尽量减少数据库 IO；

③ 分布式数据库、分布式缓存；

④ 服务器的负载均衡；

10. 两条相交的单向链表，如何求他们的第一个公共节点?

①如果两个链表相交，则从相交点开始，后面的节点都相同，即最后一个节点肯定相同；

②从头到尾遍历两个链表，并记录链表长度，当二者的尾节点不同，则二者肯定不相交；

③尾节点相同，如果 A 长为 LA，B 为 LB，如果 LALB,则 A 前 LA-LB 个先跳过；

——更多如链表相关经典问题：求单向局部循环链表的入、将两个有序链表合并合成一

个有序链表、链表逆序、求倒数第 K 个节点，判断是否有环等。

11. new/delete 和 malloc/free 的底层实现?

malloc 和 new 的区别：

1）malloc 与 free 是 C++/C 语言的标准库函数，new/delete 是 C++的运算符。它们都

可用于申请动态内存和释放内存；

2）new 返回指定类型的指针，并且可以自动计算所需要大小。而 malloc 则必须要由

程序员计算字节数，并且在返回后强行转换为实际类型的指针；

3）new/delete 在对象创建的同时可以自动执行构造函数初始化，在对象在消亡之前会

自动执行析构函数。而 malloc 只管分配内存，并不能对所得的内存进行初始化，所以

得到的一片新内存中，其值将是随机的；

既然 new/delete 的功能覆盖了 malloc/free，为什么 C++还要保留 malloc/free？因为

C++程序经常要调用 C 函数，而 C 程序只能用 malloc/free 管理动态内存。

new/delete、malloc/free 底层实现原理：

概述：new/delete 的底层实现是调用 malloc/free 函数实现的，而 malloc/free 的底

层实现也不是直接操作内存而是调用系统 API 实现的。

new/delete 的两种分配方式原理图如下：

注意，针对上图最末尾所述的“new[]/delete[]时会多开辟 4 字节用于存储对象个数”，

作如下说明：

①对于内置类型：

new []不会在首地址前 4 个字节定义数组长度。

delete 和 delete[]是一样的执行效果，都会删除整个数组，要删除的长度从 new 时即

可知道。

②对于自定义类型：

new []会在首地址前 4 个字节定义数组长度。

当 delete[]时，会根据前 4 个字节所定义的长度来执行析构函数删除整个数组。

如果只是 delete 数组首地址，只会删除第一个对象的值。

12. overload、override、overwrite 的介绍.

（1）overload（重载），即函数重载：

①在同一个类中；

②函数名字相同；

③函数参数不同（类型不同、数量不同，两者满足其一即可）；

④不以返回值类型不同作为函数重载的条件。

（2）override（覆盖，子类改写父类的虚函数），用于实现 C++中多态：

①分别位于父类和子类中；

②子类改写父类中的 virtual 方法；

③与父类中的函数原型相同。

（3）overwrite（重写或叫隐藏，子类改写父类的非虚函数，从而屏蔽父类函数）：

①与 overload 类似，但是范围不同，是子类改写父类；

②与 override 类似，但是父类中的方法不是虚函数。

13. 什么是守护进程?

（1）什么是守护进程？

守护进程（Daemon Process），也就是通常说的 Daemon 进程（精灵进程），是 Linux

中的后台服务进程。它是一个生存期较长的进程，通常独立于

控制终端并且周期性地执行某种任务或等待处理某些发生的事件。

守护进程是个特殊的孤儿进程，这种进程脱离终端，为什么要脱离终端呢？之所以脱离

于终端是为了避免进程被任何终端所产生的信息所打断，其在执

行过程中的信息也不在任何终端上显示。

（2）如何查看守护进程？

在终端敲：ps axj

从上图可以看出守护进行的一些特点：

守护进程基本上都是以超级用户启动（ UID 为 0 ）

没有控制终端（ TTY 为 ？）

终端进程组 ID 为 -1 （ TPGID 表示终端进程组 ID）

14. 请描述小端/大端机器.

小端/大端的区别是指低位数据存储在内存低位还是高位的区别。其中小端机器指：数

据低位存储在内存地址低位，高位数据则在内存地址高位；大端机器正好相反。

当前绝大部分机器都是小端机器，就是比较符合人们逻辑思维的数据存储方式，比如

intel 的机器基本就都是小端机器。

15. 请描述长连接与短连接.

（1）就是 TCP 长连接和 TCP 短连接：

①TCP 长连接：TCP 长连接指建立连接后保持连接而不断开。若一段时间内没有数据传

输，服务器会发送心跳包给客户端，判断客户端是否还在线，叫做 TCP 长连接中的 keep

alive。一般步骤：连接→数据传输→保持连接(心跳)→数据传输→保持连接(心跳)

→……→关闭连接；

②TCP 短连接：指连接建立并传输数据完成后，就断开连接。一般步骤：连接→数据传

输→关闭连接；

③使用场景：长连接适合单对单通信且连接数不太多的情况；短连接适合连接数多且经

常更换连接对象的；

（2）HTTP 是什么连接：

①在 HTTP/1.0 中，默认使用的是短连接。但从 HTTP/1.1 起，默认使用长连接，用以

保持连接特性。使用长连接的 HTTP 协议，会在响应头有加入这行代码：

Connection:keep-alive

注意：此处的 keep-alive 和上述 TCP 长连接原理介绍中的 keep alive 不是一个意思：

此处表示告知服务器本 http 请求是长连接模式，而 TCP 长连接中的 keep alive 表示对

客户端的保活检测。

②http 长连接并不是一直保持连接

http 的长连接也不会是永久保持连接，它有一个保持时间如 20s（从上一次数据传输完

成开始计时），可以在不同的服务器软件（如 Apache）中设定这个时间，若超过该时

间限制仍然无数据通信传输，服务器就主动关闭该连接。注：实现长连接要客户端和服

务端都支持长连接。

③http 连接实质：http 的长连接/短连接实质上就是 TCP 的长/短连接。

16. C++中引用与指针的联系与区别?

联系：引用是变量的别名，可以将引用看做操作受限的指针；

区别：

1） 指针是一个实体，而引用仅是个别名；

2）引用只能在定义时必须初始化，指针可以不初始化为空；

3）引用初始化之后其地址就不可改变（即始终作该变量的别名直至销毁，即从一而终。

注意：并不表示引用的值不可变，因为只要所指向的变量值改变。引用的值也就改变了），

但指针所指地址是不可变的；如下：

int m=23,n=13;

int a=m;

a=12; //合法，相当于修改 m=12

a=n; //合法，相当于修改 m=13

17. 一个大的含有 50M 个 URL 的记录，一个小的含有 500 个

URL 的记录，找出两个记录里相同的 URL。

首先使用包含 500 个 url 的文件创建一个 hash_set。

然后遍历 50M 的 url 记录，如果 url 在 hash_set 中，则输出此 url 并从 hash_set 中删

除这个 url。

所有输出的 url 就是两个记录里相同的 url。

18. 海量日志数据，提取出某日访问百度次数最多的那个 IP。

如果日志文件足够的大，大到不能完全加载到内存中的话。

那么可以考虑分而治之的策略，按照 IP 地址的 hash(IP)%1024 值，将海量日志存储到

1024 个小文件中。每个小文件最多包含 4M 个 IP 地址。

对于每个小文件，可以构建一个 IP 作为 key，出现次数作为 value 的 hash_map，并记

录当前出现次数最多的 1 个 IP 地址。

有了 1024 个小文件中的出现次数最多的 IP，我们就可以轻松得到总体上出现次数最多

的 IP。

17. 有 10 个文件，每个文件 1G，每个文件的每一行都存放

的是用户的 query，每个文件的 query 都可能重复。如何

按照 query 的频度排序？

1）读取 10 个文件，按照 hash(query)%10 的结果将 query 写到对应的文件中。这样我

们就有了 10 个大小约为 1G 的文件。任意一个 query 只会出现在某个文件中。

2）对于 1）中获得的 10 个文件，分别进行如下操作

-利用 hash_map（query，query_count）来统计每个 query 出现的次数。

-利用堆排序算法对 query 按照出现次数进行排序。

-将排序好的 query 输出的文件中。

这样我们就获得了 10 个文件，每个文件中都是按频率排序好的 query。

3）对 2）中获得的 10 个文件进行归并排序，并将最终结果输出到文件中。

20. 有一根 27 厘米长的细木杆，在第 3 厘米，7 厘米，11

厘米，17 厘米，23 厘米这五个位置上各有一只蚂蚁，木杆

很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还

是右是任意的，他们只会朝前走或掉头，但不会后退，当两

只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每

秒钟可以走 1 厘米的距离。求所有蚂蚁都离开木杆的最小时

间和最大时间。

两只蚂蚁相遇后，各自掉头朝相反方向走。如果我们不考虑每个蚂蚁的具体身份，这和

两只蚂蚁相遇后，打个招呼继续向前走没有什么区别。

所有蚂蚁都离开木杆的最小时间为

max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11

所有蚂蚁都离开木杆的最大时间为

max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24

21. 判断两棵树是否相等，请实现两棵树是否相等的比较，

相等返回 1，否则返回其他值，并说明算法复杂度。

数据结构为:

typedef struct TreeNode

{

char c;

TreeNode *leftchild;

TreeNode *rightchild;

}TreeNode;

函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);

注：A、B 两棵树相等当且仅当 RootA-c==RootB--c,而且 A 和 B 的左右子树相等或者

左右互换相等。

递归方法：

bool CompTree(TreeNode *tree1, TreeNode *tree2)

{

if (tree1 == NULLtree2 == NULL)

return true;

if (tree1 == NULL || tree2 == NULL)

return false;

if (tree1-c != tree2-c)

return false;

if ( (CompTree(tree1-leftchild, tree2-leftchild)

CompTree(tree1-rightchild, tree2-rightchild)) ||

CompTree(tree1-leftchild, tree2-rightchild)

CompTree(tree1-rightchild, tree2-leftchild) )

return true;

}

时间复杂度：

在树的第 0 层，有 1 个节点，我们会进行 1 次函数调用；

在树的第 1 层，有 2 个节点，我们可能会进行 4 次函数调用；

在树的第 2 层，有 4 个节点，我们可能会进行 16 次函数调用；

......

在树的第 x 层，有 2^x 个节点，我们可能会进行(2^x)^2 次函数调用；

所以假设总节点数为 n，则算法的复杂度为 O(n^2)。

22. 将多个集合合并成没有交集的集合。

给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}

要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集。

例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}。

（1）请描述你解决这个问题的思路；

（2）请给出主要的处理流程，算法，以及算法的复杂度

（3）请描述可能的改进。

集合使用 hash_set 来表示，这样合并时间复杂度比较低。

1、给每个集合编号为 0，1，2，3...

2、创建一个 hash_map，key 为字符串，value 为一个链表，链表节点为字符串所在集

合的编号。遍历所有的集合，将字符串和对应的集合编号插入到 hash_map 中去。

3、创建一个长度等于集合个数的 int 数组，表示集合间的合并关系。例如，下标为 5

的元素值为 3，表示将下标为 5 的集合合并到下标为 3 的集合中去。开始时将所有值都

初始化为-1，表示集合间没有互相合并。在集合合并的过程中，我们将所有的字符串都

合并到编号较小的集合中去。

遍历第二步中生成的 hash_map，对于每个 value 中的链表，首先找到最小的集合编

号（有些集合已经被合并过，需要顺着合并关系数组找到合并后的集合编号），然后将

链表中所有编号的集合都合并到编号最小的集合中（通过更改合并关系数组）。

4、现在合并关系数组中值为-1 的集合即为最终的集合，它的元素来源于所有直接或间

接指向它的集合。

算法的复杂度为 O(n)，其中 n 为所有集合中的元素个数。

题目中的例子：

0:{aaabbbccc}

1:{bbbddd}

2:{eeefff}

3:{ggg}

4:{dddhhh}

生成的 hash_map，和处理完每个值后的合并关系数组分别为

aaa:0。[-1,-1,-1,-1,-1]

bbb:0,1。[-1,0,-1,-1,-1]

ccc:0。[-1,0,-1,-1,-1]

ddd:1,4。[-1,0,-1,-1,0]

eee:2。[-1,0,-1,-1,0]

fff:2。[-1,0,-1,-1,0]

ggg:3。[-1,0,-1,-1,0]

hhh:4。[-1,0,-1,-1,0]

所以合并完后有三个集合，第 0，1，4 个集合合并到了一起。

23. 平面内有 11 个点，由它们连成 48 条不同的直，由这些

点可连成多少个三角形？

首先你要分析，平面中有 11 个点，如果这些点中任意三点都没有共线的，那么一共应

该有 C(11，2)=55， 可是，题目中说可以连接成 48 条直线，那么这 11 个点中必定有

多点共线的情况。 55-48=7，从 7 来分析：

假设有一组三个点共线，那么可以组成的直线在 55 的基础上应该减去 C(3，2)-1=2

2*3=6≠7，因此，可以断定不仅有三点共线的，也可能有四个点共线的可能。

假设有一组四个点共线，那么可以组成的直线在 55 的基础上应该减去 C(4，2)-1=5

（备注，五个点共线的可能不存在，因为，C(5，2)-1=97，故不可能有五条直线共线。）

因此，三点共线少 2 条，4 点共线少 5 条，只有一个 4 点共线，一个 3 点共线才能满足

条件，其余情况不能满足少了 7 条直线。

那么，这 11 个点能组成的三角形的个数为，C(11，3)-C(3，3)-C(4，3)=165-1-4=160 （备

注，三个点共线不能组成三角形）

24. 在常用的 C 编译环境中, 已知 struct {int a; double b;char

c;} A; 求 sizeof(A)的返回值?

24

25. 若有宏定义: #define MOD(x, y) x%y 则执行以下语句后的

输出结果是?

int a=13, b=94;

printf(%dn, MOD(b, a+4));

7

26. 用两个栈实现一个 FIFO 队列.

一个用来入栈,一个用来出栈.

27. 描述 IPv6 相对 IPv4 带来了哪些技术差异.

IPv4 有 4 个 8 位二级制数表示, 工 4 个字节.

浏览器向域名系统 DNS 请求解析

IPv6 地址空间从 IPV4 的 32 位扩展到 128 位 IPv6 实现了包头设计的简化,降低了网络

设备对包处理的负荷 IPv6 实现了实现了地址的自动化配置,无需部署 DHCP 也可实现地

址配置为了实现 IPv6 地址解析、路由、网络控制消息传递等功能,网络需要配合实现邻

居发现协议( Neighbor Discovery)、 ICMPVI6、 DHCPV6、 OSPFV3、BGP4+等新协议部

署或扩展 IPv6 部署过程中,网络可能会部署双栈、隧道或翻译等过渡方案实现与原有

PV4 网络互通

28. 内存主要用的 4 个区是?

栈区, 堆区, 静态区, 代码区

29. Linux 下进程通信的方式有哪些?

管道, 消息队列, 共享内存, 信号量, 信号, 套接口

30. 如何用队列来求一个二叉树的最大高度?

BFS

31. 下列哪个操作可以不需要再内核态执行?

A.系统调用 B.malloc/free C.软中断 D.内存换页

B

32. 应用程序 ping 发出的是什么报文?

ICMP 应答报文

33. 假定对长度为 n=119 的有序数组进行折半查找,则对应的

判定数的高度是多少?

7

2^7=128119

面试题太多了，小编就不一一的列举了，需要更详细的 可以加入QQ群：956314242 ，让我们一起技术讨论起来吧，小编编辑文章已编辑的手软

以上就是（2020年百度精选面试题及答案）全部内容，收藏起来下次访问不迷路！