活动介绍

大厂精选面试题及答案（百度篇）

preview
试读
43页
需积分: 0 0 下载量 48 浏览量 更新于2024-03-13 收藏 650KB PDF 举报
百度面试精选原题，附有详细答案，内容涉及广，共两万余字，四十多页
百度精选面试题及答案
1. 输入 www.baidu.com 在浏览器的完整过程，越详细越好。
浏览器获取输入的域名 ww. baidu. com
浏览器向域名系统 DNS 请求解析 ww. baidu. com 的 IP 地址
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) 申请大小的限制：WindowsT 栈的大小一般是 2M,堆的容量较大；
5) 申请效率的比较：栈由系统自动分配，速度较快。堆使用 new、malloc 等分配，较 慢；
总结：栈区优势在处理效率，堆区优势在于灵活；
内存模型：自由区、静态区、动态区；
根据 c/c++对象生命周期不同，c/c++的内存模型有三种不同的内存区域，即：自由存 储区，
动态区、静态区。
自由存储区：局部非静态变量的存储区域，即平常所说的栈；
动态区：用 new , malloc 分配的内存，即平常所说的堆；
靜态区：全局变量，静态变量，字符串常量存在的位置；
注：代码虽然占内存，但不属于 c/c 卄内存模型的一部分；
3. 快速排序的思想、时间复杂度、实现以及优化方法？
快速排序的三个步骤
(1) 选择基准：在待排序列中，按照某种方式挑出一个元素，作为’基准(pivot);
(2) 分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准 左边
的元素都比该基准小，在基准右边的元素都比基准大：
(3) 通归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
基准的选择：
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效 率会
达到最大。
艮卩：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时 间
复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；
快排代码实现：
我们一般选择序列的第一个作为基数，那么快排代码如下：
void quicksort(vector<int> int left, irrt right)
[
if (left < right)//false 则递归结束
{
int key=v[left];//基数賦值
int low = left:
int high = right:
while (low < high) //当 lou«=high 时，表示一抡分割结束
{
while (low < high && v [high] >= key)〃v[low]为基数，从后向前与基数比
较
!
high—:
}
swzp (v[lov/], v [high]): while (low < high && v[low] <= key)//v [high]
^1 基数，从前向后与基数比 较
!
lovH-；
}
(vflow]
3
v[high]):
}
//分割后，对每一分段重复上述操作
quicksort (v, left, low-1):
quicksort (v, lovrt-1, right):
注：上述数组或序列 V 必须是引用类型的形参，因为后续快排结果需要直接反映在原序 列中；
优化：
上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最 差的
0(n*2)o 所以，优化方向就是合理的选择基数。
常见的做法“三数取中〃法(序列太短还要结合其他排序法，如插入排序、选择排序等), 如下：
① 当序列区间长度小于 7 时，采用插入排序：
② 当序列区间长度小于 40 时，将区间分成 2 段，得到左端点、右端点和中点，我们对 这三
个点取中数作为基数；
③ 当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分 别再得
到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取 中数，然后
将该值作为基数。
具体代码只是在上一份的代码中将“基数赋值"改为①②③对应的代码即可：
int key=v[left];//基数谶值
if (right-left+l<=7) {
insertion_sort (v, left, right);〃插入排序
return;
Jelse if (right-left+l<=8) (
key=SelectPivotOfThree (v, left, right)；〃三个取中
}else{
〃三组三个取中，再三个取中(使用 4 次 SelectPivotOfThree，此处不具体展示)
}
需要调用的函数：
void insertion_sort (vector<irrt> &unsotrted, irrt left, irrt right) //插入排序算法
[
for (int i = left+1: i <= right: i++)
[
if (unsorted[i - 1] > unsorted[i])
int temp = unsorted[i]: int j = i;
while (j > left && unsorted[j - 1] > temp) [
unsorted[j] = unsorted[j - 1]:
unsorted [j] = tenp:
int SelectPivotOf Three (vector<int> &arr, int low, irrt high)
//三数取中，同时将中值移到序列第一位
[
int mid = low + (high - low)/2;〃计算数组中间的元素的下标
//使用三数取中法迭择枢轴
if (arr[mid] > arr[high])//目标：arr[mid] <= arr[high]
[
swzp (arr [mid], arr [high]):
}
if (arr[low] > arr[high])//目标：arr[low] <= arr[high]
[
swzp (arr [low], arr [high]):
}
if (arr [mid] > arr[low]) 〃目标：arr[low] >= arr[mid]
[
swzp (arr [mid], arr [low]):
}
〃此时，arr [mid] <= arr[low] <= arr [high]
return arr[low]：
//low 的位置上保存这三个位置中间的值
〃分割时可以直接使用 low 位置的元素作为枢轴，而不用改変分割函数了
}
这里需要注意的有两点：
① 插入排序算法实现代码；
② 三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然 可
用。
4. 请描述 IO 多路复用机制?
10 模型有 4 中：同步阻塞 10、同步非阻塞 10、异步阻塞 10、异步非阻塞 10； 10 多路 复用
属于 10 模型中的异步阻塞 10 模型，在服务器高性能 10 构建中常常用到
。
同步异步是表示服务端的，阻塞非阻塞是表示用户端，所以可解释为什么 10 多路复用 （异步
阻塞）常用于服务器端的原因；
文件描述符（知，又叫文件句柄）：描述符就是一个数字，它指向内核中的一个结构体 （文
件路径，数据区等属性）。具体来源：Linux 内核将所有外部设备都看作一个文件来 操作，
对文件的操作都会调用内核提供的系统命令，返回一个 fd（文件描述符）。 下面开始介绍
10 多路复用：
（1） I/。多路复用技术通过把多个 I/。的阻塞复用到同一个 select、poll 或 epoll 的 阻塞
上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。与传统的多线 程/多进程
模型比，I/。多路复用的最大优势是系统开销小，系统不需要创建新的额外 进程或者线程。
（2） select, poll, epoll 本质上都是同步 I/O,因为他们都需要在读写事件就绪后自 己负责
进行读写，也就是说这个读写过程是阻塞的，而异步 I/O 则无需自己负责进行读 与，异步 I/O
的实现会负责把数据从内核拷贝到用户空间。
（3） I/O 多路复用的主要应用场景如下：
服务器需要同时处理多个处于监听状态或者多个连接状态的套接字；
服务器需要同时处理多种网络协议的套接字；
（4） 目前支持 I/O 多路复用的系统调用有 select, poll, epoll, epoll 与 select 的 原理比
较类似，但 epoll 作了很多重大改进，现总结如下：
① 支持一个进程打开的文件句柄知个数不受限制（为什么 select 的句柄数量受限制:
select 使用位域的方式来传逢关心的文件描述符，因为位域就有最大长度，在 Linux 下是
1024,所以有数量限制）5
② I/O 效率不会随着 FD 数目的増加而线性下降；
©epoll 的 API 更加简单；
（5） 三种接口调用介绍：
① select 函数调用格式：
#include <sys/select. h>
#include < sys/1ime. h>
int select（int maxfdpi, fd_set *readset, fd_set *wxiteset, fd_set
*exceptset, const struct timeval *tineout）
//返回值：就绪描述符的数目，超时返回。，出错返回 T
② poll®数调用格式：
# include <poll. h>
int poll （ struct pollfd * fds, unsigned int nfds, int timeout）;
©epoll®数格式（操作过程包括三个函数）：
Sinelude〈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 语句及索引的优化
② 数据库表结构的优化
®系统配置的优化
@硬件的优化

剩余42页未读，继续阅读

身份认证 购VIP最低享 7 折!
30元优惠券
资源推荐
资源评论
给你一颗语法糖
  • 粉丝: 660
上传资源 快速赚钱
voice
center-task 前往需求广场，查看用户热搜

最新资源