测试面试题总结及问题解析
计算机网络(tcp/ip 详解卷 1、谢希仁的计算机网络)、数据库(sql 必知必会、数据库案例
应用)、操作系统(现代操作系统、清华的公开课)、数据结构和算法(剑指 offer、大话
数据结构、leetcode 只做了一点、还有牛客上的算法课)、java 语言( java 程序员面试宝
典、java 程序员的基本修养、大话设计模式只看了重要的 )、测试相关(软件测试的艺术、
从菜鸟到测试架构师、软件测试技术大全、selenium,qtp,junit 的一些相关资料和书)、linux
看了一点(鸟哥的私房菜基础篇和网络篇)。总之很多东西是看完就忘,我是边看会在 onenote
记笔记,忘了就回去翻笔记和书再看看。
——摘自牛客某位大神的总结
因为没有对知识点进行分类,所以我在每个问题后面加上了标签,表示属于哪本书,如果这
个看的还不明白就翻对应的书或者我给的博客链接看看,后面的星星表示知识点的重要程
度,我大概是根据面试被问及的次数标记的,仅供参考。问题是我整理别人的面经还有我自
己的一些面经,答案是我从书上或者一些博客上找的,所以我只是一个搬运工哈哈哈
1. 计算机网络里面 socket 通信常用的的函数叫啥?(计算机网络)
Socket:网络上的两个程序通过一个双向的通信连接实现数据的交换,根据连接启动的方
式以及本地套接字要连接的目标,套接字之间的连接过程可以分为三个步骤:服务器监听,
客户端请求,连接确认。
(1)服务器监听:服务器端套接字并不定位具体的客户端套接字,而是处于等待连接
的状态,实时监控网络状态。
(2)客户端请求:由客户端的套接字提出连接请求,要连接的目标是服务器端的套接
字。为此,客户端的套接字必须首先描述它要连接的服务器的套接字,指出服务器端套接字
的地址和端口号,然后就向服务器端套接字提出连接请求。
(3)连接确认:是指当服务器端套接字监听到或者说接收到客户端套接字的连接请求,
它就响应客户端套接字的请求,建立一个新的线程,把服务器端套接字的描述发给客户端,
一旦客户端确认了此描述,连接就建立好了。而服务器端套接字继续处于监听状态,继续接
收其他客户端套接字的连接请求。
常用的函数:
1. 创建:socket()函数,这个操作类似于打开文件操作,返回 socket 的 socket 描述符。
2. 绑定:bind()函数,把一个地址族的特定地址指定给 socket,而不是由系统随机分配.
3. listen()、connect()函数,客户端通过调用 connect 函数来建立与 TCP 服务器的连接。
服务器端调用 listen(),socket 开始等待客户的链接请求
4. accept()函数,服务器收到请求后,用 accept 接受请求,然后链接就建立了,可以开
始读写操作。
5. read(),write()读写操作
6. close()函数,读写完毕后要关闭相应的 socket 描述字
2 数据结构里面的排序算法(排序算法,表格很重要)
当 n 较大,则应采用时间复杂度为 O(Nlog2N)的排序方法:快速排序、堆排序或归并排
序。 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随
机分布时,快速排序的平均时间最短。黑色表中快速排序的空间复杂度不正确其他正确快速
排序的空间复杂度为 O(logN).
1. 从平均时间来看,快速排序是效率最高的,但快速排序在最坏情况下的时间性能不如
堆排序和归并排序。而后者相比较的结果是,在 n 较大时归并排序使用时间较少,但使用辅
助空间较多。
2. 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。
其中直接插入排序最简单,当序列基本有序或者 n 较小时,直接插入排序是好的方法,因
此常将它和其他的排序方法,如快速排序、归并排序等结合在一起使用。
3. 基数排序的时间复杂度也可以写成 O(d*n)。因此它最使用于 n 值很大而关键字较小的
的序列。若关键字也很大,而序列中大多数记录的最高关键字均不同,则亦可先按最高关键
字不同,将序列分成若干小的子序列,而后进行直接插入排序。
4. 从方法的稳定性来比较,基数排序是稳定的内排方法,所有时间复杂度为 O(n^2)的简
单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳
定的。稳定性需要根据具体需求选择
2.1 直接插入排序基本思想:
将一个记录插入到已排序好的有序表中,从而得到一个新记录数增 1 的有序表。即:先将序
列的第 1 个记录看成是一个有序的子序列,然后从第 2 个记录逐个进行插入,直至整个序列
有序为止。时间复杂度:O(n^2)
如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,
相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排
序是稳定的。
void insert(int a[],int n)
{
int i, j;
for(i=1;i
temp;j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
2.2 希尔排序(插入排序)基本思想:
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记
录“基本有序”时,再对全体记录进行依次直接插入排序。
操作方法:
选择一个增量序列 t1,t2,…,tk,其中 ti>tj(i每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表
进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序
列的长度。
我们简单处理增量序列:增量序列 d = {n/2 ,n/4, n/8 .....1} n 为要排序数的个数
即:先将要排序的一组记录按某个增量 d(n/2,n 为要排序数的个数)分成若干组子序列,每
组中记录的下标相差 d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量
(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为 1,最后使
用直接插入排序完成排序。
//元素后移
//插入到正确位置
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
}
意:增量因子中除 1 外没有公因子,且最后一个增量因子必须为 1。希尔排序方法是一个不稳
定的排序方法。
2.3 简单选择排序基本思想:
在要排序的一组数中,选出最小(或者最大)的一个数与第 1 个位置的数交换;然后在剩下
的数当中再找最小(或者最大)的与第 2 个位置的数交换,依次类推,直到第 n-1 个元素(倒
数第二个数)和第 n 个元素(最后一个数)比较为止。
操作方法:
第一趟,从 n 个记录中找出关键码最小的记录与第一个记录交换;
第二趟,从第二个记录开始的 n-1 个记录中再选出关键码最小的记录与第二个记录交换;
以此类推.....
第 i 趟,则从第 i 个记录开始的 n-i+1 个记录中选出关键码最小的记录与第 i 个记录交换,
直到整个序列按关键码有序。
void Select(int a[],int n)
{
int min = 0;
for(int i=0;ia[j])
min = j;
}
if(min!=i)
swap(a[i],a[min]);
}
}
2.4 堆排序(选择排序)基本思想:
堆排序是一种树形选择排序,是对直接选择排序的有效改进。堆的定义如下:具有 n 个元素
的序列(k1,k2,...,kn),当且仅当满足
时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不
小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:
(a)大顶堆序列:(96, 83,27,38,11,09)
(b) 小顶堆序列:(12,36,24,85,47,30,53,91)
初始时把要排序的 n 个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),
调整它们的存储顺序,使之成为一个堆,将堆顶元素输出,得到 n 个元素中最小(或最大)
的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为
堆,输出堆顶元素,得到 n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的
堆,并对它们作交换,最后得到有 n 个节点的有序序列。称这个过程为堆排序。
因此,实现堆排序需解决两个问题:
1. 如何将 n 个待排序的数建成堆;(建堆)
2. 输出堆顶元素后,怎样调整剩余 n-1 个元素,使其成为一个新堆。(调整堆)
首先讨论第二个问题:输出堆顶元素后,对剩余 n-1 元素重新建成堆的调整过程。
调整小顶堆的方法:
1)设有 m 个元素的堆,输出堆顶元素后,剩下 m-1 个元素。将堆底元素送入堆顶((最
后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。
2)将根结点与左、右子树中较小元素的进行交换。
3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方
法 (2).
4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方
法 (2).
5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。如图:
再讨论对 n 个元素初始建堆的过程。
建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。
1)n 个结点的完全二叉树,则最后一个结点是第 round(n/2)个结点的子树。
2)筛选从第 round(n/2)个结点为根的子树开始,该子树成为堆。
3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。
如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)