共计 4125 个字符,预计需要花费 11 分钟才能阅读完成。
输出 [www.baidu.com] 在浏览器的残缺过程,越具体越好。
浏览器获取输出的域名 [www.baidu.com]
浏览器向域名零碎 DNS 申请解析 [www.baidu.com]的 IP 地址
DNS 解析出百度服务器的 IP 地址
浏览器与服务器建设 TCP 连贯(默认端口 80)
浏览器收回 HTTP 申请,申请百度首页
服务器通过 HTTP 申请把首页文件发给浏览器
TCP 连贯开释
浏览器解析首页文件,展现 web 界面
请形容 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++ 的内存模型有三种不同的内存区域,即:自在存
依据 c/c++ 对象生命周期不同,c/c++ 的内存模型有三种不同的内存区域,即:自在存储区,动静区、动态区。
自在存储区:部分非动态变量的存储区域,即平时所说的栈;
动静区:用 new,malloc 调配的内存,即平时所说的堆;
动态区:全局变量,动态变量,字符串常量存在的地位;
注:代码尽管占内存,但不属于 c/c++ 内存模型的一部分;
疾速排序的思维、工夫复杂度、实现以及优化办法?
疾速排序的三个步骤:
(1)抉择基准:在待排序列中,依照某种形式挑出一个元素,作为 “ 基准 ”(pivot);
(2)宰割操作:以该基准在序列中的理论地位,把序列分成两个子序列。此时,在基准右边的元素都比该基准小,在基准左边的元素都比基准大;
(3)递归地对两个序列进行疾速排序,直到序列为空或者只有一个元素。
基准的抉择:
对于分治算法,当每次划分时,算法若都能分成两个等长的子序列时,那么分治算法效率会达到最大。即:同一数组,工夫复杂度最小的是每次选取的基准都能够将序列分为两个等长的;工夫复杂度最大的是每次抉择的基准都是以后序列的最大或最小元素;
快排代码实现:
咱们个别抉择序列的第一个作为基数,那么快排代码如下:
`void quicksort(vector<int> &v,int left, int right)
{
if(left < right)//false 则递归完结
{
int key=v[left];// 基数赋值
int low = left;
int high = right;
while(low < high) // 当 low=high 时,示意一轮宰割完结
{
while(low < high && v[high] >= key)//v[low] 为基数,从后向前与基数
比 较
{
high–;
}
swap(v[low],v[high]);
while(low < high && v[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(vector<int> &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 (j > left && unsorted[j – 1] > temp)
{
unsorted[j] = unsorted[j – 1];
j–;
}
unsorted[j] = temp;
}
}
}
int SelectPivotOfThree(vector<int> &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 地位的元素作为枢轴,而不必扭转宰割函数了
}
`
这里须要留神的有两点:
①插入排序算法实现代码;②三数取中函数不仅仅要实现取中,还要将中值移到最低位,从而保障原宰割函数仍然可用。
实际中如何优化 MySQL?
四条从成果上第一条影响最大,前面越来越小。
① SQL 语句及索引的优化
② 数据库表构造的优化
③ 系统配置的优化
④ 硬件的优化
两条相交的单向链表,如何求他们的第一个公共节点?
①如果两个链表相交,则从相交点开始,前面的节点都雷同,即最初一个节点必定相
同;
②从头到尾遍历两个链表,并记录链表长度,当二者的尾节点不同,则二者必定不相
交;
③尾节点雷同,如果 A 长为 LA,B 为 LB,如果 LA>LB, 则 A 前 LA-LB 个先跳过;
——更多如链表相干经典问题:求单向部分循环链表的入、将两个有序链表合并合成
一个有序链表、链表逆序、求倒数第 K 个节点,判断是否有环等。
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 数组首地址,只会删除第一个对象的值。
还有这么多面试题刷不晓得够不够,须要面试题的能够分享哦