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(%d\n, 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年百度精选面试题及答案）全部内容，收藏起来下次访问不迷路！
