华清远见西安中心20231018知识点总结

华清远见嵌入式开发知识点总结，内容包含数据结构、IO、并发编程、网络编程 的重点难点，大家也可以用于备考复习。

20231016复习

• 数据结构
  • 线性表
    • 顺序表
      • 顺序表是一种线性表，它用一组连续的存储单元来存储线性表的元素，其特点是随机访问元素的时间复杂度为O(1)
    • 链表
      • 链表是一种数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。链表中的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针指向空值。链表可以用来实现栈、队列等数据结构
    • 栈
      • 栈是一种线性数据结构，它具有后进先出（Last In First Out，LIFO）的特点。栈的基本操作包括入栈（push）和出栈（pop），入栈将元素压入栈顶，出栈将栈顶元素弹出
    • 队列
      • 队列是一种线性数据结构，它具有先进先出（FIFO）的特点。在队列中，新元素插入到队列的一端，称为队尾，已有元素从队列的另一端删除，称为队头
    • 循环队列
      • 循环队列是一种环形的队列结构，它可以充分利用数组空间，避免了普通队列在出队操作后需要移动元素的问题。循环队列有两个指针，一个指向队头，一个指向队尾，当队尾指针到达数组末尾时，会回到数组开头，形成一个环
  • 二叉树
    • 二叉排序树
      • 若左子树不为空，则左子树上所有节点的值均小于它的根节点的值
      • 若右子树不为空，则右子树上所有节点的值均大于它的根节点的值
      • 左、右子树也分别为二叉排序树
      • 没有键值相等的节点
      • 二叉排序树的主要应用是实现快速查找和排序。在二叉排序树中，查找、插入和删除操作的时间复杂度均为O(logn)
    • 霍夫曼树
      • 霍夫曼树是一种带权路径长度最短的树，也称为最优二叉树。它的构造过程是：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为霍夫曼树
        • 1、将n个权值看成n棵只有一个结点的二叉树
        • 2、在森林中选取两棵根结点权值最小的树合并，得到一棵新树，新树的根结点权值为其左右子树的根结点权值之和
        • 3、将新树插入到森林中，并删除原来两棵树
        • 4、重复步骤2和3，直到森林中只有一棵树为止，这棵树就是霍夫曼树
  • 算法
    • 查找
      • 折半查找
        • 折半查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。该算法每次查找都将待查找区间折半，直到找到目标元素或者区间缩小为0为止。折半查找的时间复杂度为O(log n)
      • 索引查找
        • 索引查找是一种在数据结构中查找特定元素的方法，它通过使用预先计算的索引来加快查找速度。索引通常是一个数组，其中包含指向数据结构中每个元素的指针或关键字的值。通过使用索引，可以避免在数据结构中进行线性搜索，从而提高查找效率
      • 二叉查找树
        • 1、若左子树非空，则左子树上所有节点的值均小于它的根节点的值
        • 2、若右子树非空，则右子树上所有节点的值均大于它的根节点的值
        • 3、左右子树本身也分别是二叉查找树
      • Hash(散列)
        • 散列树是一种数据结构，它将数据按照散列函数的结果分配到不同的子树中，每个子树又是一棵二叉搜索树。这样可以在保持二叉搜索树的查找、插入、删除等操作的同时，提高散列函数的效率，减少冲突
      • 平衡树
        • 平衡树是一种自平衡的二叉搜索树，它能够保证在最坏情况下基本动态集合操作的时间复杂度为 O(log n)。平衡树的常见实现有红黑树、AVL树、Treap等
      • B-树
        • 1、B-树是一种自平衡的树形数据结构，它可以用来存储大量的数据并且能够在对数时间内进行查找、插入和删除操作。B-树通常用于数据库和文件系统中，因为它们需要高效地处理大量的数据
        • 2、B-树的特点是每个节点可以存储多个元素，并且每个节点都有多个子节点。B-树的节点通常被称为页，每个页可以存储多个元素和指向子节点的指针。B-树的高度通常比较小，因此它可以在磁盘上进行高效的操作
        • 3、B-树的查找、插入和删除操作都是基于二分查找的，因此它们的时间复杂度都是 O(log n)。B-树的平衡性保证了它们的性能不会随着数据量的增加而降低
      • B+树
        • B+树是一种常用的数据结构，通常用于数据库索引和文件系统中。它是一种多路搜索树，每个节点可以存储多个关键字和对应的指针，而且所有叶子节点都在同一层上，方便范围查询
          • 1、所有关键字都在叶子节点上，非叶子节点只存储关键字的索引
          • 2、所有叶子节点都在同一层上，方便范围查询
          • 3、叶子节点之间通过指针连接，形成一个有序链表，方便范围查询和遍历
          • 4、非叶子节点的关键字个数比其子节点的个数少1，这样可以保证树的平衡性
      • 红黑树(AVL)
        • 红黑树是一种自平衡的二叉查找树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子节点的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此，红黑树是一种弱平衡树
          • 1、每个节点要么是红色，要么是黑色
          • 2、根节点是黑色
          • 3、每个叶子节点（NIL节点，空节点）是黑色的
          • 4、如果一个节点是红色的，则它的两个子节点都是黑色的
          • 5、对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点
    • 排序
      • 简单冒泡
        • arr是待排序的数组，n是数组的长度。这个代码使用了两层循环，外层循环控制排序的轮数，内层循环控制每一轮中相邻元素的比较和交换
      • 简单选择
        • 简单选择排序是一种基于比较的排序算法，其基本思想是每次从待排序的元素中选出最小（或最大）的一个元素，放到已排好序的元素序列的最后，直到所有元素均排序完毕
        • arr为待排序的数组，n为数组长度，i和j分别为外层和内层循环的计数器，min_index为当前未排序部分中最小元素的下标
      • 简单插入
        • arr是待排序的数组，
        • n是数组的长度。算法的基本思想是将数组分为已排序和未排序两部分，每次从未排序部分中取出一个元素，插入到已排序部分中的合适位置
      • 快速排序
      • 堆排序
        • 大顶堆
        • 小顶堆
      • 基数排序
      • 桶排序
      • 归并排序
  • 结构
    • 图
      • 邻接矩阵
        • 邻接矩阵是一种表示图的方法，它使用一个二维数组来表示图中各个节点之间的连接关系。如果两个节点之间有边相连，则在邻接矩阵中对应的位置上填入1，否则填入0
      • 十字链表
        • 十字链表是一种特殊的链表结构，它可以用来表示稀疏矩阵。在十字链表中，每个节点有两个指针，一个指向同一行的下一个节点，另一个指向同一列的下一个节点。同时，每个节点还有两个指针，一个指向同一行的头节点，另一个指向同一列的头节点
    • 图的算法
      • 深度优先遍历
      • 广度优先遍历
        • 广度优先遍历（BFS）是一种图形搜索算法，它从根节点开始，逐层遍历整张图，即先访问距离根节点最近的节点，然后是距离根节点稍远的节点，依次进行搜索，直到遍历完整张图。BFS 通常使用队列来实现
      • 拓扑排序
      • 背包客问题
      • 最短路径算法
  • 面试题
    • 1、顺序表和链表的区别
      • 相同点
        • 逻辑结构
      • 不同点
        • 存储结构
        • 实现过程（元素之间关系）
        • 使用场景
        • 优势
        • 劣势
    • 2、栈和队列的区别
    • 3、如何使用两个栈实现一个队列
    • 4、如何使用两个队列实现栈
• IO
  • 1、文件系统
    • 文件系统是一个存储，组织，管理文件/设备的软件
      • 真实文件系统
        • 管道文件系统
          • LINUXC管道文件系统是一种特殊的文件系统，它允许进程通过读写文件的方式进行进程间通信。管道文件系统的实现原理是通过创建一个特殊的文件，然后将数据写入该文件，再由另一个进程读取该文件中的数据，从而实现进程间通信
        • 磁盘文件系统
        • socket文件系统
          • Linux的socket文件系统是一种特殊的文件系统，它允许进程通过文件系统接口来进行网络通信。在Linux中，所有的网络通信都被抽象成了文件操作，这些文件被称为socket文件。socket文件系统提供了一种方便的方式来进行网络编程，使得开发者可以像操作文件一样来进行网络通信
        • 消息队列文件系统
          • LINUXC消息队列文件系统是一种IPC机制，用于进程间通信。它允许一个或多个进程向一个队列中发送消息，而另外的进程则可以从该队列中读取消息。消息队列是一种可靠的通信方式，可以在不同的进程之间传递数据，而不需要像管道或共享内存那样需要进程之间的同步
      • 虚拟文件系统
        • LINUXC中的虚拟文件系统（Virtual File System，VFS）是一种抽象层，它隐藏了不同文件系统之间的差异，使得应用程序可以通过相同的系统调用来访问不同的文件系统。VFS定义了一组通用的文件操作接口，如打开、关闭、读取、写入等，这些接口被所有文件系统所共享。当应用程序调用这些接口时，VFS会根据文件系统类型调用相应的文件系统驱动程序来完成具体的操作
      • 网络文件系统
        • NFS
          • 即VFS，是Linux抽象出来的一个统一对所有真实的文件系统进行管理使用的软件，虚拟文件系统是有目录结构的
            • LINUXC网络文件系统（Linux CIFS）是一种用于在Linux系统中访问Windows共享文件夹的协议。它允许Linux用户像访问本地文件一样访问远程Windows共享文件夹，从而实现了跨平台文件共享
      • 分布式文件系统
      • 特殊的文件系统
  • 2、文件类型
    • IO文件类型指的是输入输出文件类型，常见的有文本文件和二进制文件两种。文本文件是以ASCII码形式存储的文件，可以用文本编辑器打开查看和编辑；而二进制文件则是以二进制形式存储的文件，不能直接用文本编辑器打开查看和编辑
  • 3、系统调用
    • 系统调用是指操作系统提供给应用程序使用的一组接口，应用程序可以通过这些接口向操作系统发出请求，以便获取操作系统的服务。常见的系统调用包括文件操作、进程管理、网络通信等
  • 4、标准IO
    • 标准IO缓冲区的类型
    • 如何更改标准IO的缓冲区大小
    • 如何刷新标准IO的缓冲区
    • 标准IO缓冲区的大小
      • 标准IO缓冲区的大小是由操作系统决定的，不同的操作系统可能会有不同的大小。在Linux系统中，标准输入输出缓冲区的大小通常为4096字节
  • 5、文件IO
    • 标准IO和文件IO的区别
      • 来源
      • 是不是系统调用
      • 有没有缓冲机制
      • 操作对象
      • 可移植性
      • 系统开销
      • 应用场景
      • 操作接口
  • 6、库
    • 库的类型
    • 如何制作
    • 静态库和动态库的区别
      • 后缀
      • 生成方式
      • 共享性
      • 链接时间
      • 应用场景
• 并发编程
  • 进程
    • 1、什么是进程
    • 2、如何创建进程
    • 3、进程有哪些状态，如何转换的
    • 4、完美拷贝
      • 进程的完美拷贝是指在操作系统中，通过fork()系统调用创建一个子进程，子进程与父进程完全相同，包括代码、数据、堆栈等，但是拥有不同的进程ID。这种拷贝方式可以让子进程继承父进程的所有资源，包括打开的文件、信号处理方式等
    • 5、写时拷贝
    • 6、进程的调度算法/策略
    • 7、进程如何退出
      • 进程可以通过调用 exit() 函数来退出，也可以通过 return 语句从 main 函数中返回来退出。此外，还可以使用 _exit() 或者 _Exit() 函数来退出进程，这两个函数不会执行任何清理工作，直接终止进程
    • 8、进程的分类
    • 9、特殊的进程
    • 10、如何避免僵尸进程产生
    • 11、如何创建守护进程
    • 12、如何让进程执行特定的任务
    • 13、进程的优先级如何修改
    • 14、终端，进程组，会话组之间的关系
  • 线程
    • 1、什么是线程
      • 线程是操作系统能够进行运算调度的最小单位，它被包含在进程中，是进程中的实际运作单位，一个进程可以包含多个线程，每个线程都是一个独立的执行路径。线程相比进程具有更小的开销，更高的运行效率和更好的资源共享特性。线程之间可以共享进程的资源，如内存、文件句柄、网络连接等。同时，不同的线程可以并行执行，从而提高了程序的运行效率
    • 2、线程如何创建，执行特定的任务
    • 3、线程如何退出
    • 4、哪些数据是线程私有
      • 线程私有数据是指只能被当前线程访问的数据，它们存储在线程的栈空间中。每个线程都有自己的栈空间，因此线程私有数据不会被其他线程访问到。常见的线程私有数据包括函数的局部变量、函数参数、以及线程特定数据（Thread-Specific Data，TSD）
    • 5、哪些数据是多线程共享的
      • 在多线程编程中，多个线程可以同时访问和修改共享的数据。这些数据包括全局变量、静态变量、堆内存、公共资源等。如果多个线程同时对这些数据进行读写操作，就会出现数据竞争的问题，导致程序出现不可预期的结果
    • 6、threadlocal关键字的作用
  • 进程间通信
    • 1、无名管道和有名管道的区别
    • 2、管道的写阻塞和读阻塞
    • 3、管道的特点
    • 4、管道破裂
    • 5、什么是临界资源
    • 6、什么是临界区
    • 7、什么是同步
    • 8、什么是互斥
    • 9、同步和互斥的区别
    • 10、共享内存特点和使用方法
    • 11、信号
    • 12、信号驱动IO
    • 13、常用的信号和默认捕获操作
    • 14、如何修改信号的捕获操作
    • 15、信号量和消息队列的区别
    • 16、简述进程有多少种通信方式，区别是什么
  • 线程的同步和互斥
    • 1、线程的同步实现方式有几种，区别是什么
    • 2、有名信号量和无名信号量的区别
    • 3、线程互斥的实现方式有哪些
    • 4、线程锁和无名管道的区别
  • 区别
    • 1、进程和线程的区别
    • 2、如何防止死锁的产生
    • 3、生产者消费者模型是什么
    • 4、哲学家就餐问题
• 网络编程
  • 1、OSI七层协议模型简述一下
    • OSI七层协议模型是一种将计算机网络通信协议按照功能划分为七层的标准模型这七层分别是：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。每一层都有自己的功能和协议，通过这些协议的组合，实现了计算机网络的通信
  • 2、TCP\IP四层协议模型简述一下
    • TCP/IP四层协议模型包括应用层、传输层、网络层和数据链路层。其中，应用层负责应用程序之间的通信，传输层负责端到端的数据传输，网络层负责数据在网络中的传输和路由选择，数据链路层负责物理层和数据链路层之间的通信
  • 3、简述TCP/IP每一层都有哪些协议，功能是什么
  • 4、简述TCP和UDP的区别
  • 5、简述TCP三次握手和四次挥手的过程
  • 6、为什么是三次握手而不是两次
  • 7、为什么是四次挥手而不是三次
  • 8、为什么四次握手后客户端需要等待2ML
    • 四次握手是TCP连接的建立过程，客户端和服务器端都需要进行确认。在四次握手的最后一步，客户端发送ACK确认报文给服务器端，表示客户端已经准备好接收数据了。但是这个ACK报文可能会在传输过程中丢失，导致服务器端一直等待客户端的确认，浪费资源。因此，客户端需要等待2倍的最大报文段生命周期（2ML）时间，确保服务器端已经收到了ACK报文，避免出现超时重传等问题
  • 9、TCP为什么可靠
  • 10、如何划分子网
  • 11、IP地址的分类
  • 12、如何合并两个网络
  • 13、端口号的作用
  • 14、CS模型和BS模型的区别是什么
  • 15、绑定的作用是什么
    • 绑定的作用是将两个或多个实体或对象联系在一起，以便它们可以相互作用或共享信息。在计算机编程中，绑定通常用于将变量与特定的值或对象关联起来，以便在程序中使用。例如，将一个变量绑定到一个字符串，可以使程序在需要时引用该字符串。另一个例子是将函数绑定到一个按钮上，以便在用户单击该按钮时调用该函数
  • 16、accept的返回值表示什么，有什么作用
  • 17、TCP对端关闭后，另一端如何处理
  • 18、如何搭建并发服务器，有哪些技术，区别是什么
  • 19、ARP和RARP的区别
  • 20、如何设置文件读写方式为非阻塞IO
  • 21、UDP的使用场景是什么
    • UDP（User Datagram Protocol）是一种无连接的传输层协议，它不保证数据传输的可靠性，但是具有传输速度快的优点。因此，UDP适用于一些对数据可靠性要求不高，但是对传输速度要求较高的场景，例如视频直播、在线游戏等
  • 22、如何实现组播
  • 23、如何实现广播
  • 24、简述你知道的路由算法
  • 25、简述大小端字节序，以及如何写代码测试某一台设备为哪种字节序
  • 26、简述交换机和路由器的区别
  • 27、如何防止粘包
  • 28、ICMP和IGMP什么时候使用
  • 29、DNS传输层使用的是UDP还是TCP
    • DNS传输层使用的是UDP
• 其它
  • 1、Linux组成部分
  • 2、kernel的组成部分
    • 进程管理单元
    • 内存管理单元
    • 文件系统
    • 网路模块
    • 驱动