应届生互联网求职面试总结分享机器学习与数据挖掘工作补给站

五万字长文:C/C++ 面试知识总结（中）

2019-04-18  本文已影响0人  大菜鸟_

本文是：五万字长文:C/C++ 面试知识总结（上）的续篇

C++ 11

  1. shared_ptr

  2. unique_ptr

  3. weak_ptr

  4. auto_ptr（被 C++11 弃用）

shared_ptr

多个智能指针可以共享同一个对象，对象的最末一个拥有着有责任销毁对象，并清理与该对象相关的所有资源。

weak_ptr

weak_ptr 允许你共享但不拥有某对象，一旦最末一个拥有该对象的智能指针失去了所有权，任何 weak_ptr 都会自动成空（empty）。因此，在 default 和 copy 构造函数之外，weak_ptr 只提供 “接受一个 shared_ptr” 的构造函数。

unique_ptr

unique_ptr 是 C++11 才开始提供的类型，是一种在异常时可以帮助避免资源泄漏的智能指针。采用独占式拥有，意味着可以确保一个对象和其相应的资源同一时间只被一个 pointer 拥有。一旦拥有着被销毁或编程 empty，或开始拥有另一个对象，先前拥有的那个对象就会被销毁，其任何相应资源亦会被释放。

auto_ptr

被 c++11 弃用，原因是缺乏语言特性如 “针对构造和赋值” 的 std::move 语义，以及其他瑕疵。

auto_ptr 与 unique_ptr 比较

强制类型转换运算符

MSDN . 强制转换运算符：http://t.cn/E4WIt5W

static_cast

向上转换是一种隐式转换。

dynamic_cast

const_cast

reinterpret_cast

bad_cast

bad_cast 使用

try {  
    Circle& ref_circle = dynamic_cast<Circle&>(ref_shape);   
}  
catch (bad_cast b) {  
    cout << "Caught: " << b.what();  
}

运行时类型信息 (RTTI)

dynamic_cast

typeid

type_info

typeid、type_info 使用

class Flyable                       // 能飞的
{
public:
    virtual void takeoff() = 0;     // 起飞
    virtual void land() = 0;        // 降落
};
class Bird : public Flyable         // 鸟
{
public:
    void foraging() {...}           // 觅食
    virtual void takeoff() {...}
    virtual void land() {...}
};
class Plane : public Flyable        // 飞机
{
public:
    void carry() {...}              // 运输
    virtual void take off() {...}
    virtual void land() {...}
};

class type_info
{
public:
    const char* name() const;
    bool operator == (const type_info & rhs) const;
    bool operator != (const type_info & rhs) const;
    int before(const type_info & rhs) const;
    virtual ~type_info();
private:
    ...
};

class doSomething(Flyable *obj)                 // 做些事情
{
    obj->takeoff();

    cout << typeid(*obj).name() << endl;        // 输出传入对象类型（"class Bird" or "class Plane"）

    if(typeid(*obj) == typeid(Bird))            // 判断对象类型
    {
        Bird *bird = dynamic_cast<Bird *>(obj); // 对象转化
        bird->foraging();
    }

    obj->land();
};

Effective C++

  1. 视 C++ 为一个语言联邦（C、Object-Oriented C++、Template C++、STL）

  2. 宁可以编译器替换预处理器（尽量以 const、enum、inline 替换 #define）

  3. 尽可能使用 const

  4. 确定对象被使用前已先被初始化（构造时赋值（copy 构造函数）比 default 构造后赋值（copy assignment）效率高）

  5. 了解 C++ 默默编写并调用哪些函数（编译器暗自为 class 创建 default 构造函数、copy 构造函数、copy assignment 操作符、析构函数）

  6. 若不想使用编译器自动生成的函数，就应该明确拒绝（将不想使用的成员函数声明为 private，并且不予实现）

  7. 为多态基类声明 virtual 析构函数（如果 class 带有任何 virtual 函数，它就应该拥有一个 virtual 析构函数）

  8. 别让异常逃离析构函数（析构函数应该吞下不传播异常，或者结束程序，而不是吐出异常；如果要处理异常应该在非析构的普通函数处理）

  9. 绝不在构造和析构过程中调用 virtual 函数（因为这类调用从不下降至 derived class）

  10. 令 operator= 返回一个 reference to *this （用于连锁赋值）

  11. 在 operator= 中处理 “自我赋值”

  12. 赋值对象时应确保复制 “对象内的所有成员变量” 及 “所有 base class 成分”（调用基类复制构造函数）

  13. 以对象管理资源（资源在构造函数获得，在析构函数释放，建议使用智能指针，资源取得时机便是初始化时机（Resource Acquisition Is Initialization，RAII））

  14. 在资源管理类中小心 copying 行为（普遍的 RAII class copying 行为是：抑制 copying、引用计数、深度拷贝、转移底部资源拥有权（类似 auto_ptr））

  15. 在资源管理类中提供对原始资源（raw resources）的访问（对原始资源的访问可能经过显式转换或隐式转换，一般而言显示转换比较安全，隐式转换对客户比较方便）

  16. 成对使用 new 和 delete 时要采取相同形式（new 中使用 [] 则 delete []，new 中不使用 [] 则 delete）

  17. 以独立语句将 newed 对象存储于（置入）智能指针（如果不这样做，可能会因为编译器优化，导致难以察觉的资源泄漏）

  18. 让接口容易被正确使用，不易被误用（促进正常使用的办法：接口的一致性、内置类型的行为兼容；阻止误用的办法：建立新类型，限制类型上的操作，约束对象值、消除客户的资源管理责任）

  19. 设计 class 犹如设计 type，需要考虑对象创建、销毁、初始化、赋值、值传递、合法值、继承关系、转换、一般化等等。

  20. 宁以 pass-by-reference-to-const 替换 pass-by-value （前者通常更高效、避免切割问题（slicing problem），但不适用于内置类型、STL迭代器、函数对象）

  21. 必须返回对象时，别妄想返回其 reference（绝不返回 pointer 或 reference 指向一个 local stack 对象，或返回 reference 指向一个 heap-allocated 对象，或返回 pointer 或 reference 指向一个 local static 对象而有可能同时需要多个这样的对象。）

  22. 将成员变量声明为 private（为了封装、一致性、对其读写精确控制等）

  23. 宁以 non-member、non-friend 替换 member 函数（可增加封装性、包裹弹性（packaging flexibility）、机能扩充性）

  24. 若所有参数（包括被this指针所指的那个隐喻参数）皆须要类型转换，请为此采用 non-member 函数

  25. 考虑写一个不抛异常的 swap 函数

  26. 尽可能延后变量定义式的出现时间（可增加程序清晰度并改善程序效率）

  27. 尽量少做转型动作（旧式：(T)expression、T(expression)；新式：const_cast(expression)、dynamic_cast(expression)、reinterpret_cast(expression)、static_cast(expression)；尽量避免转型、注重效率避免 dynamic_casts、尽量设计成无需转型、可把转型封装成函数、宁可用新式转型）

  28. 避免使用 handles（包括 引用、指针、迭代器）指向对象内部（以增加封装性、使 const 成员函数的行为更像 const、降低 “虚吊号码牌”（dangling handles，如悬空指针等）的可能性）

  29. 为 “异常安全” 而努力是值得的（异常安全函数（Exception-safe functions）即使发生异常也不会泄露资源或允许任何数据结构败坏，分为三种可能的保证：基本型、强列型、不抛异常型）

  30. 透彻了解 inlining 的里里外外（inlining 在大多数 C++ 程序中是编译期的行为；inline 函数是否真正 inline，取决于编译器；大部分编译器拒绝太过复杂（如带有循环或递归）的函数 inlining，而所有对 virtual 函数的调用（除非是最平淡无奇的）也都会使 inlining 落空；inline 造成的代码膨胀可能带来效率损失；inline 函数无法随着程序库的升级而升级）

  31. 将文件间的编译依存关系降至最低（如果使用 object references 或 object pointers 可以完成任务，就不要使用 objects；如果能过够，尽量以 class 声明式替换 class 定义式；为声明式和定义式提供不同的头文件）

  32. 确定你的 public 继承塑模出 is-a（是一种）关系（适用于 base classes 身上的每一件事情一定适用于 derived classes 身上，因为每一个 derived class 对象也都是一个 base class 对象）

  33. 避免遮掩继承而来的名字（可使用 using 声明式或转交函数（forwarding functions）来让被遮掩的名字再见天日）

  34. 区分接口继承和实现继承（在 public 继承之下，derived classes 总是继承 base class 的接口；pure virtual 函数只具体指定接口继承；非纯 impure virtual 函数具体指定接口继承及缺省实现继承；non-virtual 函数具体指定接口继承以及强制性实现继承）

  35. 考虑 virtual 函数以外的其他选择（如 Template Method 设计模式的 non-virtual interface（NVI）手法，将 virtual 函数替换为 “函数指针成员变量”，以 tr1::function成员变量替换 virtual 函数，将继承体系内的 virtual 函数替换为另一个继承体系内的 virtual 函数）

  36. 绝不重新定义继承而来的 non-virtual 函数

  37. 绝不重新定义继承而来的缺省参数值，因为缺省参数值是静态绑定（statically bound），而 virtual 函数却是动态绑定（dynamically bound）

  38. 通过复合塑模 has-a（有一个）或 “根据某物实现出”（在应用域（application domain），复合意味 has-a（有一个）；在实现域（implementation domain），复合意味着 is-implemented-in-terms-of（根据某物实现出））

  39. 明智而审慎地使用 private 继承（private 继承意味着 is-implemented-in-terms-of（根据某物实现出），尽可能使用复合，当 derived class 需要访问 protected base class 的成员，或需要重新定义继承而来的时候 virtual 函数，或需要 empty base 最优化时，才使用 private 继承）

  40. 明智而审慎地使用多重继承（多继承比单一继承复杂，可能导致新的歧义性，以及对 virtual 继承的需要，但确有正当用途，如 “public 继承某个 interface class” 和 “private 继承某个协助实现的 class”；virtual 继承可解决多继承下菱形继承的二义性问题，但会增加大小、速度、初始化及赋值的复杂度等等成本）

  41. 了解隐式接口和编译期多态（class 和 templates 都支持接口（interfaces）和多态（polymorphism）；class 的接口是以签名为中心的显式的（explicit），多态则是通过 virtual 函数发生于运行期；template 的接口是奠基于有效表达式的隐式的（implicit），多态则是通过 template 具现化和函数重载解析（function overloading resolution）发生于编译期）

  42. 了解 typename 的双重意义（声明 template 类型参数是，前缀关键字 class 和 typename 的意义完全相同；请使用关键字 typename 标识嵌套从属类型名称，但不得在基类列（base class lists）或成员初值列（member initialization list）内以它作为 basee class 修饰符）

  43. 学习处理模板化基类内的名称（可在 derived class templates 内通过 this-&gt; 指涉 base class templates 内的成员名称，或藉由一个明白写出的 “base class 资格修饰符” 完成）

  44. 将与参数无关的代码抽离 templates（因类型模板参数（non-type template parameters）而造成代码膨胀往往可以通过函数参数或 class 成员变量替换 template 参数来消除；因类型参数（type parameters）而造成的代码膨胀往往可以通过让带有完全相同二进制表述（binary representations）的实现类型（instantiation types）共享实现码）

  45. 运用成员函数模板接受所有兼容类型（请使用成员函数模板（member function templates）生成 “可接受所有兼容类型” 的函数；声明 member templates 用于 “泛化 copy 构造” 或 “泛化 assignment 操作” 时还需要声明正常的 copy 构造函数和 copy assignment 操作符）

  46. 需要类型转换时请为模板定义非成员函数（当我们编写一个 class template，而它所提供之 “与此 template 相关的” 函数支持 “所有参数之隐式类型转换” 时，请将那些函数定义为 “class template 内部的 friend 函数”）

  47. 请使用 traits classes 表现类型信息（traits classes 通过 templates 和 “templates 特化” 使得 “类型相关信息” 在编译期可用，通过重载技术（overloading）实现在编译期对类型执行 if…else 测试）

  48. 认识 template 元编程（模板元编程（TMP，template metaprogramming）可将工作由运行期移往编译期，因此得以实现早期错误侦测和更高的执行效率；TMP 可被用来生成 “给予政策选择组合”（based on combinations of policy choices）的客户定制代码，也可用来避免生成对某些特殊类型并不适合的代码）

  49. 了解 new-handler 的行为（set_new_handler 允许客户指定一个在内存分配无法获得满足时被调用的函数；nothrow new 是一个颇具局限的工具，因为它只适用于内存分配（operator new），后继的构造函数调用还是可能抛出异常）

Google C++ Style Guide

英文：Google C++ Style Guide ：http://t.cn/RqhluJP

中文：C++ 风格指南：http://t.cn/ELDTnur

Google C++ Style Guide 图

STL

STL 索引

STL 方法含义索引：http://t.cn/E4WMXXs

STL 容器

容器 底层数据结构 时间复杂度 有无序 可不可重复 其他
array 数组 随机读改 O(1) 无序 可重复 支持快速随机访问
vector 数组 随机读改、尾部插入、尾部删除 O(1)
头部插入、头部删除 O(n)		 无序 可重复 支持快速随机访问
list 双向链表 插入、删除 O(1)
随机读改 O(n)		 无序 可重复 支持快速增删
deque 双端队列 头尾插入、头尾删除 O(1) 无序 可重复 一个中央控制器 + 多个缓冲区，支持首尾快速增删，支持随机访问
stack deque / list 顶部插入、顶部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
queue deque / list 尾部插入、头部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
priority_queue vector + max-heap 插入、删除 O(log2n) 有序 可重复 vector容器+heap处理规则
set 红黑树 插入、删除、查找 O(log2n) 有序 不可重复
multiset 红黑树 插入、删除、查找 O(log2n) 有序 可重复
map 红黑树 插入、删除、查找 O(log2n) 有序 不可重复
multimap 红黑树 插入、删除、查找 O(log2n) 有序 可重复
hash_set 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复
hash_multiset 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复
hash_map 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复
hash_multimap 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复

STL 算法

STL 算法

http://t.cn/aEv0DV

算法 底层算法 时间复杂度 可不可重复
find 顺序查找 O(n) 可重复
sort 内省排序 O(n*log2n) 可重复

数据结构

顺序结构

顺序栈（Sequence Stack）

SqStack.cpp：http://t.cn/E4WxO0b

顺序栈数据结构和图片

typedef struct {
    ElemType *elem;
    int top;
    int size;
    int increment;
} SqSrack;

队列（Sequence Queue）

队列数据结构

typedef struct {
    ElemType * elem;
    int front;
    int rear;
    int maxSize;
}SqQueue;
非循环队列

非循环队列图片

SqQueue.rear++

循环队列

循环队列图片

SqQueue.rear = (SqQueue.rear + 1) % SqQueue.maxSize

顺序表（Sequence List）

SqList.cpp

顺序表数据结构和图片

typedef struct {
    ElemType *elem;
    int length;
    int size;
    int increment;
} SqList;

链式结构

LinkList.cpp

LinkList_with_head.cpp

链式数据结构

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

链队列（Link Queue）

链队列图片

线性表的链式表示

单链表（Link List）

单链表图片

双向链表（Du-Link-List）

双向链表图片

循环链表（Cir-Link-List）

循环链表图片

哈希表

HashTable.cpp

概念

哈希函数：H(key): K -> D , key ∈ K

构造方法

冲突处理方法

线性探测的哈希表数据结构

线性探测的哈希表数据结构和图片


typedef char KeyType;

typedef struct {
    KeyType key;
}RcdType;

typedef struct {
    RcdType *rcd;
    int size;
    int count;
    bool *tag;
}HashTable;

递归

概念

函数直接或间接地调用自身

递归与分治

递归与迭代

广义表

头尾链表存储表示

广义表的头尾链表存储表示和图片

// 广义表的头尾链表存储表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode {
    ElemTag tag;
    // 公共部分，用于区分原子结点和表结点
    union {
        // 原子结点和表结点的联合部分
        AtomType atom;
        // atom 是原子结点的值域，AtomType 由用户定义
        struct {
            struct GLNode *hp, *tp;
        } ptr;
        // ptr 是表结点的指针域，prt.hp 和 ptr.tp 分别指向表头和表尾
    } a;
} *GList, GLNode;
扩展线性链表存储表示

扩展线性链表存储表示和图片

// 广义表的扩展线性链表存储表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode1 {
    ElemTag tag;
    // 公共部分，用于区分原子结点和表结点
    union {
        // 原子结点和表结点的联合部分
        AtomType atom; // 原子结点的值域
        struct GLNode1 *hp; // 表结点的表头指针
    } a;
    struct GLNode1 *tp;
    // 相当于线性链表的 next，指向下一个元素结点
} *GList1, GLNode1;

二叉树

BinaryTree.cpp

性质

  1. 非空二叉树第 i 层最多 2(i-1) 个结点 （i >= 1）

  2. 深度为 k 的二叉树最多 2k - 1 个结点 （k >= 1）

  3. 度为 0 的结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1

  4. 有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1

  5. 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点

  6. 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋

  7. 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i

  8. 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1

存储结构

二叉树数据结构

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
顺序存储

二叉树顺序存储图片

链式存储

二叉树链式存储图片

遍历方式

分类

其他树及森林

树的存储结构

并查集

一种不相交的子集所构成的集合 S = {S1, S2, …, Sn}

平衡二叉树（AVL树）

性质

平衡二叉树图片

最小失衡树

平衡二叉树插入新结点导致失衡的子树

调整：

红黑树

红黑树的特征是什么？

  1. 节点是红色或黑色。

  2. 根是黑色。

  3. 所有叶子都是黑色（叶子是 NIL 节点）。

  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）（新增节点的父节点必须相同）

  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。（新增节点必须为红）

调整

  1. 变色

  2. 左旋

  3. 右旋

应用
红黑树、B 树、B+ 树的区别？

B 树（B-tree）、B+ 树（B+-tree）

B 树、B+ 树图片

image

<figcaption style="margin: 10px 0px 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; overflow-wrap: break-word !important; line-height: inherit; text-align: center; color: rgb(153, 153, 153); font-size: 0.7em;">B 树（B-tree）、B+ 树（B+-tree）</figcaption>

特点
应用
区别
B树的优点

对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。

B+树的优点

B 树、B+ 树区别来自：differences-between-b-trees-and-b-trees、B树和B+树的区别：

http://t.cn/RrBAaZa

http://t.cn/E4WJhmZ

八叉树

八叉树图片

image

八叉树（octree），或称八元树，是一种用于描述三维空间（划分空间）的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。

用途

算法

排序

http://t.cn/E4WJUGz

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(1) 数组不稳定、链表稳定
插入排序 O(n2) O(n2) O(1) 稳定
快速排序 O(n*log2n) O(n2) O(log2n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定
归并排序 O(n*log2n) O(n*log2n) O(n) 稳定
希尔排序 O(n*log2n) O(n2) O(1) 不稳定
计数排序 O(n+m) O(n+m) O(n+m) 稳定
桶排序 O(n) O(n) O(m) 稳定
基数排序 O(k*n) O(n2)
稳定

均按从小到大排列

  • k：代表数值中的 “数位” 个数
  • n：代表数据规模
  • m：代表数据的最大值减最小值
  • 来自：wikipedia . 排序算法

查找

查找算法 平均时间复杂度 空间复杂度 查找条件
顺序查找 O(n) O(1) 无序或有序
二分查找（折半查找） O(log2n) O(1) 有序
插值查找 O(log2(log2n)) O(1) 有序
斐波那契查找 O(log2n) O(1) 有序
哈希查找 O(1) O(n) 无序或有序
二叉查找树（二叉搜索树查找） O(log2n)
红黑树 O(log2n)
2-3树 O(log2n - log3n)
B树/B+树 O(log2n)

图搜索算法

图搜索算法 数据结构 遍历时间复杂度 空间复杂度
BFS广度优先搜索 邻接矩阵
邻接链表		 O(|v|2)
O(|v|+|E|)		 O(|v|2)
O(|v|+|E|)
DFS深度优先搜索 邻接矩阵
邻接链表		 O(|v|2)
O(|v|+|E|)		 O(|v|2)
O(|v|+|E|)

其他算法

算法 思想 应用
分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并 循环赛日程安排问题、排序算法（快速排序、归并排序）
动态规划 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，适用于有重叠子问题和最优子结构性质的问题 背包问题、斐波那契数列
贪心法 一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法 旅行推销员问题（最短路径问题）、最小生成树、哈夫曼编码

Problems

Single Problem

Leetcode Problems

剑指 Offer

Cracking the Coding Interview 程序员面试金典

牛客网

操作系统

进程与线程

对于有线程系统：

对于无线程系统：

进程之间的通信方式以及优缺点

  1. 局限于单向通信

  2. 只能创建在它的进程以及其有亲缘关系的进程之间

  3. 缓冲区有限

  4. 长期存于系统中，使用不当容易出错

  5. 缓冲区有限

  1. 通信是通过将共享空间缓冲区直接附加到进程的虚拟地址空间中来实现的，因此进程间的读写操作的同步问题

  2. 利用内存缓冲区直接交换信息，内存的实体存在于计算机中，只能同一个计算机系统中的诸多进程共享，不方便网络通信

  1. 传输数据为字节级，传输数据可自定义，数据量小效率高

  2. 传输数据时间短，性能高

  3. 适合于客户端和服务器端之间信息实时交互

  4. 可以加密,数据安全性强

线程之间的通信方式

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制

进程之间的通信方式以及优缺点来源于：进程线程面试题总结

进程之间私有和共享的资源

线程之间私有和共享的资源

多进程与多线程间的对比、优劣与选择

对比
对比维度 多进程 多线程 总结
数据共享、同步 数据共享复杂，需要用 IPC；数据是分开的，同步简单 因为共享进程数据，数据共享简单，但也是因为这个原因导致同步复杂 各有优势
内存、CPU 占用内存多，切换复杂，CPU 利用率低 占用内存少，切换简单，CPU 利用率高 线程占优
创建销毁、切换 创建销毁、切换复杂，速度慢 创建销毁、切换简单，速度很快 线程占优
编程、调试 编程简单，调试简单 编程复杂，调试复杂 进程占优
可靠性 进程间不会互相影响 一个线程挂掉将导致整个进程挂掉 进程占优
分布式 适应于多核、多机分布式；如果一台机器不够，扩展到多台机器比较简单 适应于多核分布式 进程占优
优劣
优劣 多进程 多线程
优点 编程、调试简单，可靠性较高 创建、销毁、切换速度快，内存、资源占用小
缺点 创建、销毁、切换速度慢，内存、资源占用大 编程、调试复杂，可靠性较差
选择

多进程与多线程间的对比、优劣与选择来自：多线程还是多进程的选择及区别

Linux 内核的同步方式

原因

在现代操作系统里，同一时间可能有多个内核执行流在执行，因此内核其实象多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上，更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。

同步方式

来自：Linux 内核的同步机制，第 1 部分、Linux 内核的同步机制，第 2 部分

死锁

原因

产生条件

预防

文件系统

主机字节序与网络字节序

主机字节序（CPU 字节序）

概念

主机字节序又叫 CPU 字节序，其不是由操作系统决定的，而是由 CPU 指令集架构决定的。主机字节序分为两种：

存储方式

32 位整数 0x12345678 是从起始位置为 0x00 的地址开始存放，则：

内存地址 0x00 0x01 0x02 0x03
大端 12 34 56 78
小端 78 56 34 12

大端小端图片

[图片上传失败...(image-86c73-1555590815042)]
[图片上传失败...(image-d802-1555590815042)]

判断大端小端

判断大端小端

可以这样判断自己 CPU 字节序是大端还是小端：

#include <iostream>
using namespace std;

int main()
{
    int i = 0x12345678;

    if (*((char*)&i) == 0x12)
        cout << "大端" << endl;
    else    
        cout << "小端" << endl;

    return 0;
}
各架构处理器的字节序

网络字节序

网络字节顺序是 TCP/IP 中规定好的一种数据表示格式，它与具体的 CPU 类型、操作系统等无关，从而可以保重数据在不同主机之间传输时能够被正确解释。

网络字节顺序采用：大端（Big Endian）排列方式。

页面置换算法

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

分类

算法

全局：

局部：

计算机网络

计算机经网络体系结构：


计算机网络体系结构.png

各层作用及协议

分层 作用 协议
物理层 通过媒介传输比特，确定机械及电气规范（比特 Bit） RJ45、CLOCK、IEEE802.3（中继器，集线器）
数据链路层 将比特组装成帧和点到点的传递（帧 Frame） PPP、FR、HDLC、VLAN、MAC（网桥，交换机）
网络层 负责数据包从源到宿的传递和网际互连（包 Packet） IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP（路由器）
运输层 提供端到端的可靠报文传递和错误恢复（ 段Segment） TCP、UDP、SPX
会话层 建立、管理和终止会话（会话协议数据单元 SPDU） NFS、SQL、NETBIOS、RPC
表示层 对数据进行翻译、加密和压缩（表示协议数据单元 PPDU） JPEG、MPEG、ASII
应用层 允许访问OSI环境的手段（应用协议数据单元 APDU） FTP、DNS、Telnet、SMTP、HTTP、WWW、NFS

物理层

通道：

通道复用技术：

数据链路层

主要信道：

点对点信道

三个基本问题：

点对点协议（Point-to-Point Protocol）：

广播信道

广播通信：

限于文章字数限制，更多知识点总结请看“下篇”

扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有

扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）
上一篇 下一篇

猜你喜欢

热点阅读