保研专业课参考

数据结构

1.什么是平衡树？平衡树是怎么创建的？

• 每个节点的左子树和右子树的高度差绝对值至多为1
• 二叉树中的每棵子树都要求是平衡二叉树
• 平衡二叉树的前提是一棵二叉排序树

2.二叉排序树的性质：

• 若它的左子树不空，则左子树所有节点的值均小于它的根节点的值
• 若它的右子树不空，则右子树所有节点的值均大于其根节点的值

3.如何编程判断一棵二叉树是完全二叉树

完全二叉树：子节点从左往右生长，一层生长完才可以生长一层。

• 如果树为空，返回false

• 否则，开始层次遍历二叉树用队列

• 如果一个节点的左孩子为空，右孩子不为空，则返回false

• 如果一个结点的左孩子为不空，并且右孩子为空 或者 右孩子和左孩子都为空那么进行下面的判断

  • 如果后面遍历的节点都是叶子节点，返回true
  • 否则返回false

4.二叉树怎么求高度（山大计算机）

首先，树高是树中结点的最大层 数

递归求解高度：

后序遍历：

对每个结点进行如下操作：

• 如果为空，返回高度为0
• 后序遍历求左子树高度
• 后序遍历求右子树高度
• 对这个结点进行下面的操作：
  • 比较左右子树的高度大小
  • 如果左>右，返回左子树高度+1，否子返回右子树高度+1

//递归
/*递归走到树的最底层，再通过比较左右子树的高度，取较高一棵+1，一直累加到树根。*/  
int Height(Tree& t){
	if(t == NULL) return 0; //当前结点为空，返回0
	//由下至上比较左右子树高度得到最终高度 
	return Height(t->left) > Height(t->right) ? Height(t->left) + 1 : Height(t->right) + 1;
} 
 
//非递归 
/*改编自层次遍历，由根向下每遍历一层，深度+1*/ 
int Depth(Tree& t) {
    if(t == NULL) return 0;
    int depth = 0; //树的深度 
    queue q;
    q.push(t);
    while(!q.empty()){
        int n = q.size();
        for(int i = 0;ileft) q.push(s->left);
            if(s->right) q.push(s->right);
        }
        depth += 1; //深度+1 
    } 
    return depth;
}

层次遍历法（广度优先遍历）求二叉树高：

使用队列，外层循环使用while循环判断队列q不为空，然后每一次外层循环中都获得队列中元素的个数即这一层次中的宽度n，内层循环使用for循环，即遍历n次，每一次内部循环都取出队列头，将该结点的子结点都入队。在内部循环接收在外部循环内每一次高度加1。当队列中的值都遍历结束后返回高度即树的高度。

5.在图中找到一个连通图，有n个顶点，n-1条边使得边上的权值最小

• Prim算法（到生成树的最近顶点法）
• 克鲁斯卡尔算法（最短边策略）

6.查找算法

• 顺序查找（哨兵）O(n),

• 二分查找 O(lgn)

• 二叉排序树

  • 左子树都比根节点小，右子树都比根节点大
  • 子树同样也是二叉排序树
  • 中序遍历可得到有序序列
  • 删除三种情况
    • 删除节点为叶子节点，直接删除
    • 删除节点只有左子树或者只有右子树，删除后直接将子树与该节点父亲节点相连
    • 删除节点既有左子树，又有右子树：
      • 前驱替代：左子树中的最大值节点替代之
      • 后继替代：右子树中的最小节点替代之

• 哈希表

7.B树与B+树的区别是什么（信工所三室2022夏令营）

8.树的有关概念

https://blog.csdn.net/qq_56012214/article/details/124430447

**二叉树：**要么二叉树是一棵空树，要么二叉树由根节点，左子树和右子树组成，且左子树和右子树都是二叉树。左子树与右子树有次序。

**满二叉树：**二叉树中的每一层的结点数目都达到了该层的最大结点数目

**完全二叉树：**除了最后一层外，二叉树的每一层节点数都达到当前层的最大节点数目，且最后一层节点数目只有从左到右存在若干节点，这些连续结点的右边不存在结点。

二叉排序树：

二叉树的左子树的所有结点的数据域均小于或等于根节点的数据域，右子树的所有结点的数据域均大于根节点的数据域。

**平衡二叉树：**前提是二叉排序树，任意节点的左子树与右子树高度之差的绝对值不超过1，子树也为平衡二叉树

B树：

一棵m阶B树或者是一棵空树，或者是满足要求的m叉树：

• 树中的每个结点至多有m个孩子节点，至多有m-1个关键字
• 除根结点外，其他非叶子结点至少有（m/2取上边界）棵子树，至少有（m/2取上边界-1）个关键字
• 若根结点不是叶子结点，则至少有2棵子树

B+树：

红黑树：

满足红黑性质的AVL树：

• 每个结点要么是红色，要么是黑色
• 根结点是黑色
• 叶结点是黑色
• 不存在两个相邻的红结点（即红结点的父节点和子结点均是黑色）
• 对每一个结点，从该结点到任意叶结点的简单路径上，所含黑结点数量想同

9.数组与链表的区别

算法

1.动态规划

1. 动态规划与分治法的区别

分治法将问题划分为互不相交的子问题，递归的求解子问题，再将他们的解组合起来求原问题的解；

动态规划应用于子问题相互重叠的情况；

2.动态规划的使用场合

具备以下两种性质的问题：

• 最优子结构 （一个问题的最优解包含其子问题的最优解）
• 重叠子问题 （问题的递归算法反复的求解相同的子问题）

2.最短路径算法

• Dijkstra

  • 求单源、无负权的最短路
  • 松弛操作
  • 时间复杂度O(n^2)

• Floyd

  • 求多源、无负权的最短路
  • 从i号顶点到j号顶点只经过前k号点的最短路程

  for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j]
  

• Bellman-Ford

  • 求单源最短路径，可以判断有无负权回路
  • 每次遍历过程中，对所有的边进行遍历判断

3.单源最短路径用什么方法解决？

• Dijkstra算法：迪杰斯特拉算法，是一种贪心算法。
• 分支限界法
• Bellman-Ford算法
• SPFA算法（队列优化算法）

4. 弗洛伊德（Floyd）算法与迪杰斯特（Dijkstra）算法的区别

（1） 弗洛伊德（Floyd）算法：图中的每一个顶点都是出发顶点，需要求出每一个被看成为出发顶点的顶点到其他顶点的最短路径
（2）迪杰斯特拉（Dijkstra）算法：选定图中某一个顶点作为出发顶点，求出出发顶点到其他顶点的最短路径

5.有哪些排序算法？他们的复杂度是怎样的？

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 ： 一个算法执行所耗费的时间。

空间复杂度 ：运行完一个程序所需内存的大小。

1. 冒泡排序（Bubble Sort）稳定

冒泡排序 是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。（把最大的交换到无序区的最后）

• 步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

稳定排序。

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

function bubbleSort(arr) {
    varlen = arr.length;
    for(vari = 0; i < len - 1; i++) {
        for(varj = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j+1]) {       // 相邻元素两两对比
                vartemp = arr[j+1];       // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    returnarr;
}

2、选择排序（Selection Sort）不稳定

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。（查找最小的放到无序区的最前，保存最小数的索引与第i个交换）

不稳定排序。

• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

function selectionSort(arr) {
    varlen = arr.length;
    varminIndex, temp;
    for(vari = 0; i < len - 1; i++) {
        minIndex = i;
        for(varj = i + 1; j < len; j++) {
            if(arr[j] < arr[minIndex]) {    // 寻找最小的数
                minIndex = j;                // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    returnarr;
} 

3、插入排序（Insertion Sort）稳定

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 最佳情况：T(n) = O(n)
• 最坏情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

function insertionSort(arr) {
    varlen = arr.length;
    varpreIndex, current;
    for(vari = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

4、希尔排序（Shell Sort）不稳定

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

不稳定排序。

5、归并排序 （Merge Sort) 稳定

• 步骤1：把长度为n的输入序列分成两个长度为n/2的子序列；
• 步骤2：对这两个子序列分别采用归并排序；
• 步骤3：将两个排序好的子序列合并成一个最终的排序序列。

稳定排序。

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)

6、快速排序 Quick Sort（英语）不稳定

步骤1：从数列中挑出一个元素，称为 “基准”（pivot ）；
步骤2：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
步骤3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

• 最佳情况：T(n) = O(nlogn)

• 最差情况：T(n) = O(n2)

• 平均情况：T(n) = O(nlogn)

  优点： 缺点：很脆弱，容易平方级

• 快速排序是原地排序（只需要非常小的一个辅助栈）

• 快速排序时间消耗，长度为N的数组排序时间与NlgN成正比

public class QuickSort {
	public static void quickSort(int[] arr) {
		// 对函数进行封装
		quickSor(arr, 0, arr.length - 1);
	}
	public static void quickSor(int[] arr, int left, int right) {
		if (left >= right) return;
		int i = left;// 左哨兵
		int j = right;// 右哨兵
		int index = arr[i];// 基准数
		int t = 0;	
		while (i < j) {
			//当右侧数据大于基准数时，右指针向左扫描
			while (arr[j] > index) {
				j--;
			}
			//当左侧数据小于基准数时，左指针右左扫描
			while (arr[i] < index) {
				i++;
			}
			//当二者都停下时，交换数据
			if (i < j) {
				t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
			//当整个过程完成时，将基准数和分界处的数据互换
			arr[left] = arr[i];
			arr[i] = index;
			//递归处理
			quickSor(arr, left, i - 1);
			quickSor(arr, i + 1, right);
		}
	}
}

快排和归并区别：

归并排序的思路是先递归切割，然后依次向上归并，自下而上完成排序；快速排序则是先划分，再递归切割，然后划分，再切割，切割完成排序完成，自上而下完成排序。

归根到底，归并排序和快速排序在递归和关键操作（归并和划分）执行顺序上的不同，是由归并和划分的本质不同造成的。归并的前提是两个有序数组，所以需要一直递归向下切割直到找到两个只有1个元素的基本数组，然后就可以归并了，所以必须先递归切割再归并；而快速排序的向下递归切割，必须依赖划分的结果（划分完成一次排序，然后返回标杆位置），所以必须先划分再递归切割数组。

7、 堆排序 Heap Sort 不稳定

第8非叶子节点的索引就是arr.length / 2 -1。
// 先根据堆性质，找出它左右节点的索引
int left = 2 * i + 1;
int right = 2 * i + 2;

1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；3、重复步骤

不稳定。

• 最佳情况：T(n) = O(nlogn)

• 最差情况：T(n) = O(nlogn)

• 平均情况：T(n) = O(nlogn)

• 基数排序 vs 计数排序 vs 桶排序

  这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序： 根据键值的每位数字来分配桶
  • 计数排序： 每个桶只存储单一键值
  • 桶排序： 每个桶存储一定范围的数值

8、计数排序 稳定

计数排序要求输入的数据必须是有确定范围的整数。
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。

• 最佳情况：T(n) = O(n+k)
• 最差情况：T(n) = O(n+k)
• 平均情况：T(n) = O(n+k)

9、桶排序 （Bucket sort） 稳定

假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

• 最佳情况：T(n) = O(n+k)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n+k)

10、基数排序（Radix Sort） 稳定

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

6.无序数组寻找中位数

7.最长公共子序列

• c[i][j]表示串1前i个字符、串2前j个字符的最长公共自序列长度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-erFU45vy-1664520350175)(山大软院面试.assets/image-20220710083036134.png)]

• 如果想要得到串本身：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l5azB6JM-1664520350177)(山大软院面试.assets/image-20220710083109521.png)]

8.最长公共子串

• 当A[i]!=B[j],dp[i][j]=0
• 当A[i]==B[j],
  • 当i=0||j=0,dp[i][j] = 1
  • 否则 dp[i][j] = dp[i-1][j-1] + 1

9.0-1背包问题

10.第K大的数

• 借助最小堆，保持堆的大小为K ， O（nlogK ）
• 基于快速排序，只关注位置k,O(n)

11.什么是时间复杂度

定性描述该算法的时间

12.顺序表与链表的比较

13.头指针与头结点的区别：

头指针：

• 是指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针
• 无论链表是否为空，头指针不为空
• 头指针是链表的必要元素

头结点：

• 为了操作统一和方便，放在链表第一个元素结点之前，数据域一般无意义
• 头结点不一定是链表的必要元素

14.如何判断链表是否有环

1.穷举遍历

首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就重新遍历已经遍历的结点判断该节点是否已经遍历过，如果发现新节点之前的所有结点中存在相同结点ID，则说明结点被遍历过两次，链表有环，否则，就继续遍历下一个新节点。O(n^2) O(1)

2.哈希表缓存

首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作 O(N) O(N)

3.快慢指针

首先创建两个指针1和2，同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

O(N) O（1）

如果有一个磁盘满了 我想找到里面的冗余的重复文件，你怎么快速找出来重复文件？

C++

1. C中static有什么作用

• 隐藏功能：当同时编译多个文件时，所有未加static前缀的全局变量和函数都具有全局可见性，而加入static的变量仅在当前文件可见。
• 保持变量内容的持久：存储在静态数据区的变量会在程序刚开始运行时就完成初始化，也是唯一的一次初始化。例如如果static局部变量在函数内定义，它的生存期为整个源程序，其作用域为函数内，只能在定义该变量的函数内使用该变量。

2. 多态，虚函数，纯虚函数

• 多态：是对不同对象接收相同消息时产生不同的动作
• 多态体现在运行和编译两个方面：
  • 在程序运行时的多态性由继承和虚函数来实现
  • 在程序编译时的多态性体现在函数和运算符的重载上

3. C++ new 和 malloc的区别

new操作符从自由存储区(free store)上为对象动态分配内存空间,而malloc函数从堆上动态分配内存。

4. 数组与列表

区别：

• 列表的数据类型可以不同，数组的数据类型必须相同
• 数组是基于向量化操作的 ，而列表不是
• 列表由更多的存储空间

线性代数

1. 矩阵特征值怎么求

Ax=λx (A-λE)x=0

2.n阶矩阵A可对角化的充要条件？

A有n个线性无关的特征向量

概率论

1.可数集和非可数集的概念

可数集（Countable set），是指每个元素都能与自然数集N的每个元素之间能建立一一对应的集合。

不可数集，不可数集是无穷集合中的一种。一个无穷集合和自然数集合之间要是不存在一个双射（不存在一一对应关系/法则），那么它就是一个不可数集。

机器学习

1. 激活函数

1.Sigmoid

2.tanh(x)

3.ReLU函数

2.机器学习范式

1.监督学习

监督学习模型主要可以划分为以下两种：

• 分类（Classification）：训练的模型主要用于预测类别标签，例如手写数字识别；
• 回归（Regression）：训练的模型主要用来预测数值，例如房价预测；

2.无监督学习

• 聚类（Clustering）：对输入数据进行分组；
• 密度估计（Density Estimation）：学习输入数据的分布；
• 可视化（Visualization）：对数据简单进行统计或将高维数据映射到低维向量空间进行可视化；

3.强化学习

操作系统

https://blog.csdn.net/m0_52571748/article/details/119512934

1. 内核态用户态

• 特权指令：只能由操作系统内核部分使用，不允许用户直接使用的指令。

  如，进程管理（可软中断）I/O指令、置终端屏蔽jincluding指令、清内存、建存储保护、设置时钟指令（这几种记好，属于内核态）。

• 非特权指令：

  所有程序均可直接使用。

2. 进程progress和线程thread是什么

• 进程：是进程实体运行的过程，它是系统进行资源分配和调度的一个独立单位。
• 线程：是操作系统能够进行运算调度的最小单位，是被包含在进程之中的，是进程中的实际运作单位。

（1）根本区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位。

在开销方面：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。

所处环境：在操作系统中能同时运行多个进日4程（程序）；而在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）

线程间通信：

线程间通信常用的方法有如下三种：
①全局变量。由于属于同一个进程的各个线程共享操作系统分配该进程的资源，故解决线程间通信最简单的一种方法是使用全局变量。
②参数传递方式。主线程创建子线程并让其子线程为其完成特定的任务，主线程在创建子线程时，可以通过传给线程函数的参数和其通信。
③Message消息机制。常用的Message通信的接口主要有两个：PostMessage和PostThreadMessage。PostMessage为线程向主窗口发送消息，而PostThreadMessage是任意两个线程之间的通信接口。
④线程同步法。还可以通过线程同步来实现线程间通信。例如有两个线程，线程A写入数据，线程B读出线程A准备好的数据并进行一些操作。这种情况下，只有当线程A写好数据后线程B才能读出，只有线程B读出数据后线程A才能继续写入数据，这两个线程之间需要同步进行通信。

2.轮询与中断

轮询与中断是外部设备与中央处理器交互的两种方式。

中断：

由硬件或软件发出IRQ（中断信号），一旦CPU接收到中断信号，CPU暂停当前执行的任务，并保留现场，去相应中断请求。

轮询：

I/O设备有状态寄存器，用来描述设备当前的工作状态，当设备的状态发生改变时，设备将修改相应状态寄存器位。通过不断查询设备的状态寄存器，CPU可以了解设备状态，从而进行必要的I/O操作。

3.进程与线程（信工所三室夏令营2022）

进程（Process）是资源分配的基本单位，线程（Thread）是CPU调度的基本单位。

1.进程间六种通信：

https://www.plju.com/?id=20666

2.线程间通信

锁机制：包括互斥锁、条件变量、读写锁

wait/notify 等待

Volatile内存共享

信号量机制：

信号机制

https://juejin.cn/post/6969122698563682311

4.每个进程都会被分配一个栈，栈的作用（山大计算机夏令营2022）

内核在创建进程的时候，会为进程创建相应的堆栈。每个进程会有两个栈，一个是用户栈，存在于用户空间，一个是内核栈，存在于内核空间。当进程在用户空间运行时，cpu堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；当进程在内核空间时，cpu 堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈。

5.进程调度算法

• 先来先服务
• 短作业优先
• 高优先权优先（抢占式、非抢占式）
• 最短剩余时间优先
• 时间片轮转
• 高相应比优先
• 多级反馈队列

磁盘调度算法

• 先来先服务
• 最短寻道时间优先
• 扫描（电梯调度算法）
• 循环扫描

中断分类

• 内部异常中断
• 软中断
• 外部中断

系统调用&中断&库函数

https://blog.csdn.net/lqy971966/article/details/103657953

用户态切换到内核态

• 系统调用——软中断
• 异常——硬中断
• 硬件中断——外部中断

数据库

https://blog.csdn.net/weixin_43117620/article/details/109198252

1.事务的概念与特性

概念：事务 是一个操作序列，包含了一组数据库操作命令。事务把这些命令作为一个整体向系统提交或撤销操作请求，即这些数据库操作命令要么执行，要么不执行，因此事务是一个不可分割的逻辑单元。

特性:

• 原子性 Atomicity 事务是一个完整的操作。事务的各元素是不可分的。
• 一致性 Consistency 当事务完成时，数据必须处于一致状态。如A账户转账给B账户，A账户减钱与B账户加钱必须是全做或全不做，即数据库必须处在一致状态。
• 隔离性 Isolation 对数据进行修改的所有并发事务是彼此隔离的,这表明事务必须是独立的，它不应以任何方式依赖于或影响其他事务
• 持久性 Durability 事务完成之后，它对于系统的影响是永久性的。该修改即使出现致命的系统故障也将一直保持。

ACID

计算机网络

https://blog.csdn.net/m0_52571748/article/details/119513761

1.ping 基于什么协议

ICMP：Internet Control Message Protocol 网络控制报文协议

2.网际协议IP

网络层有三个协议在IP协议中：

ARP 地址解析协议 Address Resolution Protocol

ICMP 网际控制报文协议 Internet Control Message Protocol

IGMP 网际组管理协议 Internet Group Management Protocol

1.ICMP

分为 ICMP差错报文　和　ICMP询问报文

2.ICMP与ARP的区别

https://blog.csdn.net/raidtest/article/details/40212789

1.3.报文三种交换方式

电路交换 报文交换 分组交换

2.1 信道复用技术

频分复用 时分复用 波分复用 码分复用

网络层是不是可靠传输的？

网络层只检查IP数据报的首部，不检验数据部分是否出错，而传输层对收到的报文进行首部和数据部分进行差错检测。

端与端通信？
应用进程之间的通信，在传输层之间。

逻辑通信的意思？

传输层之间的通信好像是沿水平方向传送数据，但事实上两个传输层之间并没哟一条水平方向的物理连接。

用户单击鼠标后发生事件的顺序：

1. 浏览器分析链接指向页面的URL
2. 浏览器向DNS请求解析IP地址
3. DNS解析出IP地址
4. 浏览器与服务器3此握手建立起TCP连接（默认端口号80）
5. 浏览器发送HTTP请求
6. 服务器处理浏览器发来的请求，返回要显示的页面html信息
7. 传输结束，4次握手释放连接
8. 将页面显示给用户

流量控制与拥塞避免之间的关系

TCP相关

1.介绍一下OSI七层模型和TCP五层模型

OSI七层模型：

物理层：利用物理传输介质为数据链路层提供物理连接

数据链路层：定义通过通信媒介互连的设备之间传输的规范

网络层：寻址和路由；

传输层：为上层协议提供端到端的可靠传输；

会话层：建立、断开和维护通信连接；

表示层：数据格式转换、数据压缩和数据加密；

应用层：为应用程序提供网络服务；

TCP五层模型：相比OSI七层模型，会话层，表示层，应用层合为应用层。

应用层：为应用程序提供服务

9.协议与服务的联系与区别

联系:

协议,是控制对等实体间进行通信的规则集

协议的实现保证了能够向上一层提供服务。要实现本层协议，还需要使用下面一层所提供的服务.

区别:

• 使用本层服务的实体只能看见服务而无法看见协议.下面的协议对上面的实体是透明的。
• 协议是 “水平的”，即协议是控制两个对等实体进行通信的规则。
  但服务是 “垂直的”,即是下层通过层间接口向上层提供服务。

2.什么是面向连接，面向无连接

（1）面向连接的服务：是指通信前需要建立连接，通信结束后需要进行连接释放。整个过程包括，连接建立、数据传送、连接释放。是按序传送、可靠传送的。 此外还包括传输可靠性的各种措施，比如超时重传、流量控制等；常见面向连接传输TCP。（2）无连接的服务：传送数据之前不许要建立连接，随时传就行，但是无法避免数据的丢失、重复等只能“尽最大努力地交付”，是不可靠地传输，常见面向无连接传输有UDP

3.什么是UDP和TCP？UDP和TCP的区别是什么？

都是传输层协议，是用来建立端到端的可靠传输的。

UDP仅提供最基本的数据传输功能，而不关心传输时的连接建立和断开、传输可靠性的保证，而是把这些问题都抛给了UDP上层的应用层程序处理。

TCP是一种面向连接的协议，包括传输时连接建立，数据传送，连接释放，还包括保证可靠传输的措施，如超时重传、流量控制。

区别如下：

4.TCP对应的应用层协议有哪些？UDP对应的应用层协议有哪些？

TCP对应典型的应用层协议：

• FTP：文件传输协议；
• SSH：远程登录协议；
• HTTP：超文本传输协议

UDP对应典型的应用层协议：

• DNS：域名解析协议；
• TFTP：简单文件传输协议；
• SNMP：简单网络管理协议；

5.介绍TCP三次握手？为什么不是两次？为什么不是四次？

6.介绍TCP四次挥手？为什么不是三次？为什么不是五次？

7.CSMA/CD协议（载波监听多点接入/碰撞检测协议）

先听后发、边听边发、冲突停发、随机重发。

8.RIP协议

RIP 内部网关协议

routing information protocol 路由信息协议

一种分布式的基于距离向量的路由选择协议

RIP协议要求网络中每一个路由器都维护从它自己到其他每一个墓地网络的唯一最佳距离记录

RIP的缺点：

• 限制了网络的规模，能使用 的最大距离为15
• 网络规模越大，开销越大
• 好消息传的快，坏消息传的慢（路由器将信息传给相邻邻居，距离短传播快；当网络出现故障时，路由信息无法到达邻居路由，邻居路由会将路由表中的距离加一，直到加到16才发现原来路由不可达）

特点

• 仅和相邻路由器交换信息
• 交换的信息是自己现在的路由表
• 每30秒交换一次路由信息，然后路由器根据新信息更新路由表。若超过180s没收到邻居路由器的通告，则判定邻居没了，并更新自己的路由表。