牛客模拟面试-04

TCP/IP四层模型是什么？

TCP/IP四层模型自顶向下分别为

应用层(HTTP、FTP、SMTP等) 传输层(TCP、UDP等) 网络层(IP等) 网络接入层(数据链路层和网络层, Ethenet以太网卡协议)

在计算机网络中要做到正确的数据交换，就必须提前约定好相应的规则。TCP/IP四层模型是一个协议栈，统一了计算机网络标准，方便数据的交换。它自上而下依次为：应用层，管理了进程间通信的规则。传输层，提供数据传输服务。网际层，对报文进行了封装成为数据报。网络接口层，选择路由线路，进行数据传输。

加分回答

在计算机网络中要做到正确的数据交换，就必须提前约定好相应的规则。TCP/IP四层模型是一个协议栈，统一了计算机网络标准，方便数据的交换。它自上而下依次为：

应用层：应用层是体系结构中的最高层，是应用进程间通信和交互的规则，进程指计算机中运行的程序。也是用户与应用程序之间的一个接口，操作程序（软件，Web应用），进而触发更下层的服务。

协议：HTTP、HTTPS、FTP、TFTP、SMTP等
传输层：对两台主机进程（应用层）提供数据传输服务。定义了传输数据的进程端口号，负责数据包的排序、差错检验和流量控制等。

协议：UDP、TCP
网际层：对传输层交付的报文进行基本的封装，添加IP首部信息变成数据报，让数据报能够达到目标主机。

协议：ICMP、IGMP、IP（IPv4、IPv6）
网络接口层：本层兼并了数据链路层和物理层的功能，所以既是数据传输的媒介，也为网络层提供了一条精确的线路。在TCP/IP四层协议中本层功能基本和OSI后两层没有区别，可以回看OSI七层模型最后两层。

说一说C++ 中哪些函数不能是虚函数？

【得分点】

普通函数（非成员函数）、构造函数、析构函数、友元函数、静态成员函数、内联成员函数

【参考答案】

标准回答

C++ 中，普通函数（非成员函数）、构造函数、友元函数、静态成员函数、内联成员函数这些不能是虚函数。

普通函数（非成员函数）

普通函数（非成员函数）只能被重载，不能被重写，所以声明为虚函数也没有意义，编译器编译时就会绑定函数地址。

构造函数

创建派生类对象时，会调用派生类的构造函数，派生类的构造函数中将会调用基类的一个构造函数，这种顺序不同于继承机制。因此派生类不继承基类的构造函数，所以将构造函数声明为虚函数没有意义。

友元函数

友元函数不是类成员，而只有成员函数才能是虚函数。

静态成员函数

静态成员函数对于每个类来说只有一份代码，所有的对象都共享这一份代码，没有动态绑定的必要性。静态成员函数属于一个类而非某一对象，没有this 指针，它无法进行对象的判别。

内联成员函数

内联函数在编译时被展开，虚函数在运行时才能动态的绑定函数。

STL的组成部分

【得分点】

容器、算法、迭代器、函数对象、适配器、空间配置器

【参考答案】

标准回答

STL 简单的分为 3 个部分：容器、算法、迭代器，详细可以分为 6 个部分：容器、算法、迭代器、函数对象、适配器、空间适配器。

容器

容器是各种数据结构，用来存放数据。从实现角度来看，容器是一种class template。

算法

算法是用来操作容器中的数据，如对数据进行排序、查找元素等。从实现的角度来看，算法是一种function tempalte。

迭代器

迭代器扮演了容器与算法之间的胶合剂，能够用来遍历容器中的元素，类似指针，是广义指针。从实现角度来看，迭代器是一种将operator* , operator-> , operator++，operator-- 等指针相关操作予以重载的 class template。

函数对象

函数对象是类似于函数的对象，可以是类对象或函数指针，行为类似函数，可作为算法的某种策略。从实现角度来看，函数对象是一种重载了operator() 的 class 或者 class template。

适配器

适配器在STL 组件中，扮演着轴承、转换器的角色，用来修饰容器或者仿函数或迭代器接口，用于将一种接口转换成另一种接口，从而使原本不兼容的接口能够很好地一起运作。

空间配置器

空间配置器负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte。

链表求和

时间复杂度O(n) 空间复杂度O(n) 不需要用辅助栈


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <iostream>

using namespace std;

struct ListNode
{
    /* data */
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode *addInList(ListNode *head1, ListNode *head2)
    {

        if (head1 == NULL && head2 == NULL)
        {
            return NULL;
        }
        else if (head1 == NULL || head2 == NULL)
        {
            return head1 == NULL ? head2 : head1;
        }

        // 反转head1
        head1 = reverse(head1);
        // 反转head2
        head2 = reverse(head2);

        // 创建新的链表头节点
        ListNode *head = new ListNode(-1);
        ListNode *cur = head;

        int carry = 0;

        while (head1 != NULL || head2 != NULL)
        {
            int num = carry;

            if (head1 != NULL)
            {
                num += head1->val;
                head1 = head1->next;
            }

            if (head2 != NULL)
            {
                num += head2->val;
                head2 = head2->next;
            }

            // 求出进位
            carry = num / 10;
            num = num % 10;

            cur->next = new ListNode(num);
            cur = cur->next;
        }

        if (carry > 0)
            cur->next = new ListNode(carry);

        return reverse(head->next);
    }

    ListNode *reverse(ListNode *head)
    {
        if (head == NULL)
            return head;
        ListNode *cur = head;
        ListNode *pre = NULL;

        while (cur != NULL)
        {
            ListNode *tail = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tail;
        }

        return pre;
    }
};