西山居测试开发工程师一面

1. C++中的static关键字相关的特性
   1）函数中的静态变量：仅初始化一次，通过函数调用的结果值也保留。存储在数据段，而不是栈中
   2）静态类型对象：和静态变量一致，都存储在数据段，并且一直作用到程序结束。
   3）类中的静态成员变量：被所有类对象所共享，不使用构造函数进行初始化。必须显式初始化
   4）类中的静态方法：可以使用成员访问他，也可以使用类名和作用域解析::调用。不能访问普通成员函数和变量，只能访问静态成员变量和静态成员函数。
2. 如要让你写去单例模式怎么去写，大致说一下思路

//懒汉模式
//代码实例（线程不安全）
template<typename T>
class Singleton {
    public: static T& getInstance() {
        if (!value_)     {
            value_ = new T();
        }
        return *value_;
        
    }
    private:     Singleton();
    ~Singleton();
    static T* value_;
};
template<typename T>
T* Singleton<T>::value_ = nullptr;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//饿汉模式
template<typename T>
class Singleton {
    public: static T& getInstance()  {
        static T instance;
        return instance;
    }
    private:
    Singleton(){};
    Singleton(const Singleton&);
    Singleton& operator=(const Singleton&);
};
1
2
3
4
5
6
7
8
9
10
11
12

3. static关键字的生命周期
   整个程序的运行过程
4. static成员函数为什么不能访问非static成员变量
   在类实例化时，而非静态成员只有在实例化的时候才能创建。这时候如果静态成员中非静态成员，可能崩溃（访问一个不存在的对象）。
5. stl中的数据结构，vector，list，map，unordered_map的增删查改的时间复杂度
   vector：采用一维数组实现，元素内存连续存放。插入：o(n)，查看：o(1)，删除：o(n)
   list：采用双向链表实现。插入：o(1)，查看：o(1)，删除：o(1)
   map：采用红黑树实现。插入：o(nlogn)，查看：o(logn)，删除：o(logn)
   unordered_map：采用哈希表实现。插入：o(n)，查看：o(1)，删除：o(n)
6. 有n（10e7到10e8）个整数，求前k<100个数
   见链接
7. 有n个物品，物品i有重量wi和价值bi两个属性，背包的容量为c，求最大的价值。

//每个物品有多个（完全背包问题）
#include
#include
#include
#include
using namespace std;
class thing{
public:
    int wi;
    int bi;
};
int main(){
    int n,c;
    cin>>n>>c;
    vector<thing> val(n);
    for(int i=0;i<n;i++)
        cin>>val[i].wi>>val[i].bi;
    vector<int> dp(c+1,0);
    for(int i=0;i<n;i++){
        for(int j=val[i].wi;j<=c;j++){
            dp[j]=max(dp[j],dp[j-val[i].wi]+val[i].bi);
        }
    }
    cout<<dp[c]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//每个物品只有一个（0/1背包问题）
#include
#include
#include
#include
using namespace std;
class thing{
public:
    int wi;
    int bi;
};
int main(){
    int n,c;
    cin>>n>>c;
    vector<thing> val(n);
    for(int i=0;i<n;i++)
        cin>>val[i].wi>>val[i].bi;
    vector<int> dp(c+1,0);
    for(int i=0;i<n;i++){
        for(int j=c;j>=val[i].wi;j--){
            dp[j]=max(dp[j],dp[j-val[i].wi]+val[i].bi);
        }
    }
    cout<<dp[c]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

8. 递归的规模比较大，会带来什么样的后果呢？
   递归代码易造成堆栈溢出。函数调用会使用栈来保存临时变量，每调用一个函数，都会将临时变量封装成栈帧压入内存栈，等函数执行完返回时才出栈。

9. C++的传参类型
   传值：参数传递到函数后，只是一个局部变量，修改这个变量无法改变实参的值。
   传指针：传进函数里的同样是一个值，但这个值是一个地址。通过指针里面保存的地址来修改指针保存地址里面的值
   传引用：相当于是一个别名，传递的是参数的地址

10. 指针的地址空间在C和C++用什么去开辟的
    malloc和new

11. malloc和new有什么区别
    malloc/free和new/delete的共同点是：都是从堆上申请空间，并且需要用户手动释放。
    malloc/free和new/delete不同的地方是：
    1）malloc和free是函数，new和delete是操作符
    2）malloc申请的空间不会初始化，new可以初始化
    3）malloc申请空间时，需要手动计算空间大小并传递，new只需在其后跟上空间的类型即可
    4）malloc的返回值为void*, 在使用时必须强转，new不需要，因为new后跟的是空间的类型
    5）malloc申请空间失败时，返回的是NULL，因此使用时必须判空，new不需要，但是new需要捕获异常
    6）申请自定义类型对象时，malloc/free只会开辟空间，不会调用构造函数与析构函数，而new在申请空间 后会调用构造函数完成对象的初始化，delete在释放空间前会调用析构函数完成空间中资源的清理

12. 频繁的操作申请和释放内存操作有什么后果？
    内存碎片
    1） 内部碎片是由于采用固定大小的内存分区，当一个进程不能完全使用分给它的固定内存区域时就产生了内部碎片，通常内部碎片难以完全避免；
    2）外部碎片是由于某些未分配的连续内存区域太小，以至于不能满足任意进程的内存分配请求，从而不能被进程利用的内存区域。

13. 一般什么情况下会出现内存泄漏
    产生内存泄漏的主要原因是利用malloc或者new等分配内存的方式申请内存后，由于主观或者客观原因没有进行释放，导致申请的内存区域没有及时得到释放导致的。
    1）析构函数中未匹配地释放内存
    2）基类的析构函数没有设为虚函数，
    3）关于二维指针数组释放
    4）shared_ptr的循环引用问题
    5）指针变量没有被初始化（如果值不定，可以初始化为NULL）
    6）指针所指内存被释放后，没有置为NULL。
    7）指针操作超越了变量的作用范围，比如返回指向栈内存的指针就是野指针。

14. 为什么会出现野指针
    1）指针没有被初始化
    2）指针被free或者delete后，指针指向的内存被释放了，指针本身没有被设置为NULL
    3）指针超过了变量的作用范围

15. C++的智能指针
    见链接

16. weak_ptr用来解决什么问题？
    见链接

17. RAII机制
    见链接

18. TCP和UDP之间的区别
    UDP–是面向无连接的不可靠传输，首部开销小（头部占用8字节），尽最努力交付，面向报文（每次收发都是一整个报文段），没有拥塞控制不可靠（只管发不管过程和结果），支持一对一、一对多和多对多的通信方式。优点是快，少了很多首部信息和重复确认的过程，节省了大量的网络资源；缺点是不可靠不稳定，只管数据的发送不管过程和结果，网络不好的时候很容易造成数据丢失。适用于语音通话、视频会议等应用场景； TCP–是面向连接的可靠传输，首部开销较大（最少20个字节），可靠交付（有大量的机制保护TCP连接数据的可靠性），面向字节流（不保留数据报边界的情况下以字节流的方式进行传输，这也是长连接的由来），单播（只能端对端的连接），全双工通讯（允许双方同时发送消息，也是四次挥手的由来）。优点是稳定、可靠、有确认、窗口、重传、拥塞控制机制，在数据传完之后，还会断开连接节约系统资源。缺点是慢、效率低、占用系统资源高，在传递数据之前要先建立连接。适用于文件传输、超文本传输等应用场景。

19. 客户端和服务器开发的步骤
    

20. 三次握手
    

21. 三次握手可以两次吗？有什么问题吗？
    不可以
    三次握手的首要原因是为了防止旧的重复连接初始化造成混乱。
    同步双方初始序列号

22. 服务器怎么还原成原始数据
    TCP拆包的作用是将任务拆分处理，降低整体任务出错的概率，以及减小底层网络处理的压力。拆包过程需要保证数据经过网络的传输，又能恢复到原始的顺序。这中间，需要数学提供保证顺序的理论依据。TCP利用（发送字节数、接收字节数）的唯一性来确定封包之间的顺序关系。

23. 为什么要用epoll
    select本质上是通过设置或者检查存放fd标志位的数据结构数据结构来进行下一步的处理，时间复杂度：O(n)
    　缺点：
    　　1) 每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大；
    　　2) 同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大；
    　　3) 单个进程可监视的fd数量被限制；
    　　4) 对socket进行扫描是线性扫描；
    优点：
    　　1）select的可移植性更好，在某些Unix系统上不支持poll()。
    　　2）select对于超时值提供了更好的精度：微秒，而poll是毫秒。
    　　poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待对垒中加入一项继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，知道设备就绪或者主动超时，被唤醒后它又要再次遍历fd这个过程经理了多次无谓的遍历。时间复杂度O(n)
    缺点：
    　　1）大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义；
    　　2）与select一样，poll返回后，需要轮询pollfd来获取就绪的描述符。
    优点：
    　　1）poll() 不要求开发者计算最大文件描述符加一的大小。
    　　2）poll() 在应付大数目的文件描述符的时候速度更快，相比于select。
    　　3）它没有最大连接数的限制，原因是它是基于链表来存储的。
    　　epoll可以理解为event poll，不同于忙轮询和无差别轮询，epoll会把哪个流发生了怎样的I/O事件通知我们。所以我们说epoll实际上是事件驱动（每个事件关联上fd）的，此时我们对这些流的操作都是有意义的。（复杂度降低到了O(1)）
    缺点：
    　　1）相对select来说, epoll的跨平台性不够用 只能工作在linux下, 而select可以在windows linux apple上使用。
    　　2）相对select来说 还是用起来还是复杂了一些, 不过和IOCP比起来 增加了一点点的复杂度却基本上达到了IOCP的并发量和性能, 而复杂度远远小于IOCP
    　　3）相对IOCP来说 对多核/多线程的支持不够好, 性能也因此在性能要求比较苛刻的情况下不如IOCP.
    优点：
    　　1）IO效率不随FD数目增加而线性下降：epoll不存在这个问题，它只会对"活跃"的socket进行操作。
    　　2）使用mmap加速内核与用户空间的消息传递：epoll通过内核和用户空间共享一块内存来实现的。
    　　

24. 为什么要用线程池，线程池用来做什么？
    线程池是由服务器预先创建的一组子线程，线程池中的线程数量应该和CPU数量差不多线程池中的所有子线程都运行着相同的代码。当有新的任务到来时，主线程将通过某种方式选择线程池中的某一个子线程来为之服务。相比于动态的创建子线程，选择一个已经存在的子线程的代价显然要小很多。
    主线程使用某种算法主动选择子线程；
    主线程和所有子线程通过一个共享工作队列来同步，子线程都睡眠在该工作队列上。当有新的任务到来时，主线程将任务添加到工作队列中。这将唤醒正在等待任务的子线程，不过只有一个子线程将获得新任务的“接管权”，他可以从工作队列中取出任务并执行之，而其他子线程将继续睡眠在工作队列上。

25. 一个选课系统 一个人5门课，10到10点半可选。怎么进行测试？
    开放题，从以下几点来展开说
    黑盒测试：
    黑盒测试也称功能测试或数据驱动测试，它是在已知产品所应具有的功能，通过测试来检测每个功能是否都能正常使用，在测试时，把程序看作一个不能打开的黑盆子，在完全不考虑程序内部结构和内部特性的情况下，测试者在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数锯而产生正确的输出信息，并且保持外部信息（如数据库或文件）的完整性。
    “黑盒”法着眼于程序外部结构、不考虑内部逻辑结构、针对软件界面和软件功能进行测试。“黑盒”法是穷举输入测试，只有把所有可能的输入都作为测试情况使用，才能以这种方法查出程序中所有的错误。实际上测试情况有无穷多个，因此不仅要测试所有合法的输入，而且还要对那些不合法但是可能的输入进行测试。
    常用的黑盒测试方法有：等价类划分法；边界值分析法；因果图法；场景法；正交实验设计法；判定表驱动分析法；错误推测法；功能图分析法。
    白盒测试：
    白盒测试也称为结构测试或逻辑驱动测试，是针对被测单元内部是如何进行工作的测试。它根据程序的控制结构设计测试用例，主要用于软件或程序验证。白盒测试法检查程序内部逻辑结构，对所有的逻辑路径进行测试，是一种穷举路径的测试方法，但即使每条路径都测试过了，但仍然有可能存在错误。因为：穷举路径测试无法检查出程序本身是否违反了设计规范，即程序是否是一个错误的程序；穷举路径测试不可能检查出程序因为遗漏路径而出错；穷举路径测试发现不了一些与数据相关的错误。
    白盒测试需要遵循的原则有：1. 保证一个模块中的所有独立路径至少被测试一次；2. 所有逻辑值均需要测试真（true）和假（false）；两种情况；3. 检查程序的内部数据结构，保证其结构的有效性；4. 在上下边界及可操作范围内运行所有循环。
    常用白盒测试方法：
    静态测试：不用运行程序的测试，包括代码检查、静态结构分析、代码质量度量、文档测试等等，它可以由人工进行，充分发挥人的逻辑思维优势，也可以借助软件工具（Fxcop）自动进行。
    动态测试：需要执行代码，通过运行程序找到问题，包括功能确认与接口测试、覆盖率分析、性能分析、内存分析等。
    白盒测试中的逻辑覆盖包括语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖和路径覆盖。六种覆盖标准发现错误的能力呈由弱到强的变化：1.语句覆盖每条语句至少执行一次。2.判定覆盖每个判定的每个分支至少执行一次。3.条件覆盖每个判定的每个条件应取到各种可能的值。4.判定/条件覆盖同时满足判定覆盖条件覆盖。5.条件组合覆盖每个判定中各条件的每一种组合至少出现一次。6.路径覆盖使程序中每一条可能的路径至少执行一次。