复试-专业问题

朴灿烈づ我的快乐病毒、 2022-10-20 00:59 149阅读 0赞

这两种方法在形式上相像，其区别在于：pa是指针变量，a是数组名。值得注意的是：pa是一个可以变化的指针变量，而a是一个常数。因为数组一经被说明，数组的地址也就是固定的，因此a是不能变化的，不允许使用a＋＋、＋＋a或语句a＋=10，而pa＋＋、＋＋pa、pa＋=10则是正确的。

假设现在我们有以下数组：

int a[5] = { 1,2,3,4,5 };
    那么，在C语言中如何取得数组中的元素呢？
    
    第一种方式：直接通过下标获取
    
    //取得第0个元素
    printf("%d\n", a[0]);

第二种方式：通过数组的地址，在C语言中，数组的名称实际上就是该数组首个元素的地址，可以通过(\*名称)获取其中的值。

//获取第0个元素
    printf("%d\n", *a);
    //获取第1个元素，只需要将地址+1，存储输出的是是连续的内存空间
    printf("%d\n", *(a+1));

第三种方式：通过指向该数组的指针。

//声明一个指针，同时让其指向a    
    int* p = a;
    //通过解引用来获取指针p指向的值，获得第0个元素
    printf("%d\n", *p);
    //指针+1即可获得第1个元素
    printf("%d\n", *(p + 1));

*  （1）栈（stack）：数调用过程中的各种参数、局部变量、返回值以及函数返回地址。
 *  （2）堆（heap）：用于程序动态申请分配和释放空间。C语言中的malloc和free，C++中的new和delete均是在堆中进行的。
 *  （3）全局（静态）存储区：分为DATA段和BSS段。DATA段（全局初始化区）存放初始化的全局变量和静态变量；BSS段（全局未初始化区）存放未初始化的全局变量和静态变量。
 *  （4）文字常量区：存放常量字符串。程序结束后由系统释放。
 *  （5）程序代码区：存放程序的二进制代码。

英文自我介绍，提问你做过哪些项目并介绍项目内容实现方法，问你来自哪里介绍你的家乡/学校，研究生计划，为什么想要读研等问题。

# 计算机网络 #

牢记每一层的协议及其内容、应用。

1.  物理层：
2.  数据链路层
    
    功能：**为网络层提供服务；封装成帧（透明传输）；链路管理；流量控制；差错控制；**
3.  网络层
    
    1.  **功能一：路由选择与分组转发（最佳路径）**
    2.  **功能二：异构网络互联**
    3.  **功能三：拥塞控制（全局性）**
    
    协议：IP协议
4.  传输层
    
    1.  传输层提供进程和进程之间的逻辑通信。  
        网络层提供主机之间的逻辑通信。
    2.  复用和分用  
        复用：应用层所有的应用进程都可以通过传输层再传输到网络层。  
        分用：传输层从网络层收到数据后交付指明的应用进程。
    3.  传输层对收到的报文进行差错检测。
    4.  数据链路层的首部校验和只校验了首部
    5.  传输层的两种协议TCP与UDP。

### 物理层 ###

在物理层上所传送的数据单位是比特。 物理层(physical layer)的作用是实现相邻计算机节点之间比特流的透明传送，尽可能屏蔽掉具体传输介质和物理设备的差异。使其上面的数据链路层不必考虑网络的具体传输介质是什么。“透明传送比特流”表示经实际电路传送后的比特流没有发生变化，对传送的比特流来说，这个电路好像是看不见的。

解释什么DNS，为什么要用DNS，有了IP地址为什么还要有域名？域名结构为什么这样设计？ICMP、IGMP协议；IP地址的分类？等。  
1.OSl，TCP/IP；五层协议的体系结构，以及各层协议  
2.IP地址的分类

*  分类的IP地址(网络号+主机号)  
    ![08cd72d2872dce9353b738140f35e78d.png][]
 *  子网的划分（网络号+子网号+主机号)
 *  构成超网（无分类编址方法）

**3.ARP是地址解析协议，简单语言解释一下工作原理**  
1.首先，每个主机都会在自己的ARP缓冲区中建立一个ARP列表，  
以表示IP地址和MAC地址之间的对应关系。

2.当源主机要发送数据时，首先检查ARP列表中是否有对应IP地址的目的主机的MAC地址，  
如果有，则直接发送数据，  
如果没有，就向本网段的所有主机发送ARP数据包，  
该数据包包括的内容有：源主机 IP地址，源主机MAC地址，目的主机的IP 地址。

3.当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，  
如果不是，则忽略该数据包，  
如果是，则首先从数据包中取出源主机IP地址和MAC地址写入到ARP列表中，  
如果已经存在，则覆盖，  
然后将自己的MAC地址写入ARP响应包中，告诉源主机自己是它想要找的MAC地址。

4.源主机收到ARP响应包后，将目的主机的IP地址和MAC地址写入ARP列表，并利用此信息发送数据。  
如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。

广播发送ARP请求，单播发送ARP响应。

4.TCP三次握手和四次挥手的全过程

5.在浏览器中输入www.baidu.com后执行的全部过程

**6.TCP和UDP的区别？**  
TCP与UDP区别

<table> 
 <thead> 
  <tr> 
   <th align="left"></th> 
   <th align="left">UDP</th> 
   <th>TCP</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">是否连接</td> 
   <td align="left">无连接</td> 
   <td>面向连接</td> 
  </tr> 
  <tr> 
   <td align="left">是否可靠</td> 
   <td align="left">不可靠传输，不使用流量控制和拥塞控制</td> 
   <td>可靠传输，使用流量控制和拥塞控制</td> 
  </tr> 
  <tr> 
   <td align="left">连接对象个数</td> 
   <td align="left">支持一对一，一对多，多对一和多对多交互通信</td> 
   <td>只能是一对一通信</td> 
  </tr> 
  <tr> 
   <td align="left">传输方式</td> 
   <td align="left">面向报文</td> 
   <td>面向字节流</td> 
  </tr> 
  <tr> 
   <td align="left">首部开销</td> 
   <td align="left">首部开销小，仅8字节</td> 
   <td>首部最小20字节，最大60字节</td> 
  </tr> 
  <tr> 
   <td align="left">适用场景</td> 
   <td align="left">适用于实时应用（IP电话、视频会议、直播等）</td> 
   <td>适用于要求可靠传输的应用，例如文件传输</td> 
  </tr> 
 </tbody> 
</table>

**7.DNS域名系统，简单描述其工作原理。**  
当DNS客户机需要在程序中使用名称时，它会查询DNS服务器来解析该名称。客户机发送的每条查询信息包括三条信息：指定的DNS域名，指定的查询类型，DNS域名的指定类别。基于UDP服务，端口53. 该应用一般不直接为用户使用，而是为其他应用服务，如HTTP，SMTP等在其中需要完成主机名到IP地址的转换。

1.  客户机向其本地域名服务器发出DNS请求报文
2.  本地域名服务器收到请求后，查询本地缓存，假设没有该记录，则以DNS客户的身份向根域名服务器发出解析请求
3.  根域名服务器收到请求后，判断该域名所属域，将对应的顶级域名服务器的IP地址返回给本地域名服务器
4.  本地域名服务器向顶级域名服务器发出解析请求报文
5.  顶级域名服务器收到请求后，将所对应的授权域名服务器的IP地址返回给本地域名服务器
6.  本地域名服务器向授权域名服务器发起解析请求报文
7.  授权域名服务器收到请求后，将查询结果返回给本地域名服务器
8.  本地域名服务器将查询结果保存到本地缓存，同时返回给客户机

8.了解交换机、路由器、网关的概念，并知道各自的用途

交换机（**多接口网桥**）：**扩展以太网**

![71deb919ed81f16c5d07478c5ee6154b.png][]

路由器：  
第一，网络互连  
第二，数据处理，提供包括分组过滤、分组转发、优先级、复用、加密、压缩和[防火墙][Link 1]等功能；  
第三，网络管理，路由器提供包括配置管理、性能管理、容错管理和流量控制等功能。

网段：一般指一个计算机网络中使用同一物理层设备（传输介质，中继器，集线器等）能够直接通讯的那一部分。

# 数据结构 #

## 栈 ##

出栈顺序满足卡特兰数： ( 1 / ( n + 1 ) ) ∗ C 2 n n (1/(n+1)) \* C\_\{2n\}^n (1/(n\+1))∗C2nn  
括号匹配，后缀式的求值

## 队列 ##

循环队列实现

## 稀疏矩阵的存储方法： ##

顺序：三元组法和伪地址法  
链式：邻接表法和十字链表法

## KMP（O(m+n)） ##

#include<iostream>
    using namespace std;
    const int N=1000010;
    char p[N],s[N];
    int n,m;
    int ne[N];
    int main()
    {
        cin>>n>>p+1>>m>>s+1;
        
        for(int i=2,j=0;i<=n;i++)
        {
            while(j&&p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }
        for(int i=1,j=0;i<=m;i++)
        {
            while(j&&s[i]!=p[j+1]) j=ne[j];
            if(s[i]==p[j+1]) j++;
            if(j==n)
            {
                printf("%d ",i-j);
                j=ne[j];
            }
        }
        return 0;
    }

普通模式串比较优点：适合规模较大的外存字符串匹配，因为可以分段进行，先读入内存一部分进行匹配，完成之后即可写回外存，确保发生不匹配的时候不需要将之前的写回外存的部分再次读入，减少了I/O操作，提高效率。

## 二叉树 ##

五个主要性质

1.  在二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。
2.  深度为k(k>=0)的二叉树最少有k个结点，最多有２＾ｋ－１个结点。
3.  对于任一棵非空二叉树，若其叶结点数为n0，度为2的非叶结点数为n2，则ｎ0 = ｎ2 ＋１。  
    灵活运用：n个节点的树，空指针的个数为n+1.
4.  具有n个结点的完全二叉树的深度为int\_down(log(2，ｎ)+1=int\_UP(log(2，n+1))
5.  如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，．．．．．．，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ>=１ && ｉ<=ｎ）,则有以下关系：  
    （1）若 ｉ= 1，则结点i为根，无父结点；若 ｉ> 1，则结点 i 的父结点为结点int\_DOWN（ｉ / ２）;  
    （2）若 ２＊ｉ <= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；  
    （3）若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；  
    （4）若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１；  
    （5）若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１；  
    （6）结点ｉ所在的层次为 int\_DOWN（log（2，ｉ））＋１。

补充：  
n个节点可以构造的二叉树个数为卡特兰数： ( 1 / ( n + 1 ) ) ∗ C 2 n n (1/(n+1)) \* C\_\{2n\}^n (1/(n\+1))∗C2nn  
遍历的改进：非递归（避免了系统栈）或线索二叉树（避免用户栈）

数据结构：排序算法及时间复杂度，随手写一个你自己熟悉排序算法（伪代码形式），二叉树相关知识。  
九大排序[九大排序][Link 2]  
![12310e3ae6dc2990b414eb976771256b.png][]

**所有排序方法可分为两类，**

**（1）一类是稳定的，包括直接插入排序、起泡排序、和归并排序，基数桶式排序；**

**（2）另一类是不稳定的，包括直接选择排序、希尔排序、快速排序和堆排序。**

二叉搜索树：**中序遍历为顺序**

AVL树的旋转：

![1e2033344bf59627bcc590468ff5212f.png][]

右旋A：自己左儿子的右儿子–》自己的左儿子，自己–》自己的左儿子的右儿子。

左旋A：自己右儿子的左儿子–》自己的右儿子，自己–》自己的右儿子的左儿子。

![152d879af6cc1c1cf7edfe0d9954a8b0.png][]

#include<iostream>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    #include<unordered_map>
    using namespace std;
    const int N=10005,M=100005;
    int n,m,K,st[N],l[N],r[N],w[N],h[N],idx=0;
    
    void update(int u)
    {
    	h[u]=max(h[l[u]],h[r[u]])+1;
    }
    int get_balance(int u)
    {
    	return h[l[u]]-h[r[u]];
    }
    void R(int &u)
    {
    	int p=l[u];
    	l[u]=r[p],r[p]=u;
    	update(u),update(p);
    	u=p;
    }
    void L(int &u)
    {
    	int p=r[u];
    	r[u]=l[p],l[p]=u;
    	update(u),update(p);
    	u=p;
    }
    
    void insert(int &u,int val)
    {
    	if(u==-1)
    	{
    		u=++idx;
    		w[idx]=val;
    	}
    	else if(val<=w[u])
    	{
    		insert(l[u],val);
    		if(get_balance(u)==2)
    		{
    			 if(get_balance(l[u])==1) R(u);
    			 else  L(l[u]),R(u);
    		}
    	}
    	else
    	{
    		insert(r[u],val);
    		if(get_balance(u)==-2)
    		{
    			 if(get_balance(r[u])==-1) L(u);
    			 else  R(r[u]),L(u);
    		}
    	}
    	update(u);
    	
    }
    int q[N];
    int maxx=0;
    void bfs(int u)
    {
    	int hh=0,tt=-1;
    	
    	q[++tt]=u;
    	int id=0;
    	while(hh<=tt)
    	{
    		int t=q[hh++];
    		id++;
    		if(l[t]!=-1) q[++tt]=l[t],maxx=max(id*2,maxx);
    		if(r[t]!=-1) q[++tt]=r[t],maxx=max(id*2+1,maxx);
    		
    	}
    }
    int main()
    {
    	
    	cin>>n;
    	memset(l, -1, sizeof l);
        memset(r, -1, sizeof r);
        memset(w,0x3f,sizeof w);
    	int root=-1;
    	for(int i=1;i<=n;i++)
    	{
    		int val;
    		scanf("%d",&val);
    		insert(root,val);
    	}
    	bfs(root);
    	for(int i=0;i<n-1;i++)
        {
            printf("%d ",w[q[i]]);
        }
        printf("%d\n",w[q[n-1]]);
        //cout<<idx<<" "<<maxx<<endl;
    	 if(maxx>idx)
        {
            printf("NO");
        }
        else
        {
            printf("YES");
        }
    	return 0;
    }

在大量查找的情况下，平衡二叉树的效率更高，也是首要选择。在大量增删的情况下，红黑树是首选。

数据结构中有一类平衡的二叉搜索树，称为红黑树。

它具有以下 5 个属性：

*  节点是红色或黑色。
 *  根节点是黑色。
 *  所有叶子都是黑色。（叶子是 NULL节点）
 *  每个红色节点的两个子节点都是黑色。
 *  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

![306cc72a9828a06ca6b0d45bc26781ac.png][]

邻接矩阵与邻接表优缺点：  
邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少，会比较浪费空间。因为是一个 n∗n 的矩阵。

而邻接表的优点是节省空间，只存储实际存在的边。其缺点是关注顶点的度时，就可能需要遍历一个链表。还有一个缺点是，对于无向图，如果需要删除一条边，就需要在两个链表上查找并删除。

扩展  
逆邻接表  
在邻接表中对于有向图有一个很大的缺陷，如果我们比较关心顶点入度那么就需要遍历所有链表。为了避免这种情况出现，我们可以采用逆邻接表来存储，它存储的链表是别的顶点指向它。这样就可以快速求得顶点的入度。  
邻接表：反映的是顶点出度的情况。  
逆邻接表：反映的是顶点的入度情况。

十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到vi为尾的弧，也容易打到以vi为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点燃上，其实创建图的算法的时间复杂度与邻接表相同，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

## 图论 ##

**最短路**  
![0f41f2c90582e8e1afcecc5d0d32d004.png][]  
最短路算法分为两大类：  
m：边数，n:点数

*  单源最短路，常用算法有：
    
    1.  dijkstra，边权为正。在稠密图上的时间复杂度是 O( n 2 n^2 n2)，稀疏图上的时间复杂度是 O(mlogn)。  
        算法思想：![d28c6fff3f5d995aac0ccb1cb1fef6df.png][]  
        证明集合S里面的点已经是最短距离。假设集合S点为x，dist\[x\]有两个选择：dist\[x\]，dist\[u\]+d\[u\]\[s\],因为d\[u\]\[s\]>0且dist\[u\]>dist\[x\]。
    2.  bellman - ford算法，不论边权是正的是负。算法平均时间复杂度是 O(nm)  
        for n次  
        for 所有边 a,b,w (松弛操作)  
        dist\[b\] = min(dist\[b\],back\[a\] + w)
    3.  spfa，不论边权是正的是负。算法平均时间复杂度是 O(km)，k 是常数。 强烈推荐该算法。
 *  多源最短路，一般用floyd算法。代码很短，三重循环，时间复杂度是 O( n 3 n^3 n3)。

代码：

朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I

int g[N][N];  // 存储每条边
    int dist[N];  // 存储1号点到每个点的最短距离
    bool st[N];   // 存储每个点的最短路是否已经确定
    
    // 求1号点到n号点的最短路，如果不存在则返回-1
    int dijkstra()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        for (int i = 0; i < n - 1; i ++ )
        {
            int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
    
            // 用t更新其他点的距离
            for (int j = 1; j <= n; j ++ )
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    
            st[t] = true;
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II

typedef pair<int, int> PII;
    
    int n;      // 点的数量
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储所有点到1号点的距离
    bool st[N];     // 存储每个点的最短距离是否已确定
    
    // 求1号点到n号点的最短距离，如果不存在，则返回-1
    int dijkstra()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({0, 1});      // first存储距离，second存储节点编号
    
        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();
    
            int ver = t.second, distance = t.first;
    
            if (st[ver]) continue;
            st[ver] = true;
    
            for (int i = h[ver]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > distance + w[i])
                {
                    dist[j] = distance + w[i];
                    heap.push({dist[j], j});
                }
            }
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路

注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
    
    int n, m;       // n表示点数，m表示边数
    int dist[N];        // dist[x]存储1到x的最短路距离
    
    struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
    {
        int a, b, w;
    }edges[M];
    
    // 求1到n的最短路距离，如果无法从1走到n，则返回-1。
    int bellman_ford()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ )
            {
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                if (dist[b] > dist[a] + w)
                    dist[b] = dist[a] + w;
            }
        }
    
        if (dist[n] > 0x3f3f3f3f / 2) return -1;
        return dist[n];
    }

spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路  
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数

int n;      // 总点数
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储每个点到1号点的最短距离
    bool st[N];     // 存储每个点是否在队列中
    
    // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
    int spfa()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        queue<int> q;
        q.push(1);
        st[1] = true;
    
        while (q.size())
        {
            auto t = q.front();
            q.pop();
    
            st[t] = false;
    
            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                    {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环  
时间复杂度是 O(nm), n 表示点数，m 表示边数

int n;      // 总点数
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
    bool st[N];     // 存储每个点是否在队列中
    
    // 如果存在负环，则返回true，否则返回false。
    bool spfa()
    {
        // 不需要初始化dist数组
        // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
    
        queue<int> q;
        for (int i = 1; i <= n; i ++ )
        {
            q.push(i);
            st[i] = true;
        }
    
        while (q.size())
        {
            auto t = q.front();
            q.pop();
    
            st[t] = false;
    
            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                    if (!st[j])
                    {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    
        return false;
    }

floyd算法 —— 模板题 AcWing 854. Floyd求最短路

初始化：
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i == j) d[i][j] = 0;
                else d[i][j] = INF;
    
    // 算法结束后，d[a][b]表示a到b的最短距离
    void floyd()
    {
        for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= n; j ++ )
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

什么图一定包含欧拉回路?  
B 树和红黑树的区别是什么?  
欧拉回路和哈密尔顿回路有啥区别  
都是平衡的。 然后B+树的高度是log\_m的。 一个结点保存更多元素 因此对磁盘操作友好

操作系统：解释操作系统的文件、链接，什么是抖动？  
l 交流环节  
数据结构：决策树相关知识问的非常多，因为涉及到现在广泛应用的机器学习基础算法  
项目交流：  
项目整体介绍  
l 项目创新点、项目来源、项目的效益  
l 项目负责部分，采用了什么技术实现的，所写代码量，与现有类似系统相比的有什么优势  
l 然后老师会就你负责的部分深入问，比如你说采用了***技术老师反问现在用***\*\*比较多为什么不用，一系列的问题问道哑口无言未知  
论文交流：  
（1）论文第几作者；  
（2）论文中负责哪几部分；  
（3）论文发表的期刊的性质（中文核心、SCI、EI、国家级、省级等）；  
（4）有没有通讯作者（指导老师），若有老师给予你们什么帮助；  
（5）论文发表的意义或者说为什么要发表这篇论文；  
软著交流：此部分涉及的比较少，一般问在软著中第几位、软著的代码量、申请软著中你担任了什么角色此部分一般和项目交流结合。

# 操作系统 #

**线程和进程的区别**

1.  进程是资源分配最小单位，线程是程序执行的最小单位。
2.  进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段，线程没有独立的地址空间，它使用相同的地址空间共享数据；
3.  资源拥有：进程之间的资源是独立的；同一进程内的线程共享本进程的资源。
4.  线程之间通信更方便，同一个进程下，线程共享全局变量，静态变量等数据，进程之间的通信需要以通信的方式（IPC）进行；（但多线程程序处理好同步与互斥是个难点）

**进程的通信方式**

1.  共享存储
2.  消息传递  
    直接通信方式  
    间接通信方式（邮箱通信方式）
3.  管道通信  
    管道连接读进程和写进程实现他们通信的共享文件。（是共享存储的优化与发展，存储空间到缓冲区，可以实现一边读一遍写）

**I/O系统的层次结构**

1.用户层I/O软件

实现与用户的交互，用户可以直接调用此层提供的接口、函数等；

2.设备独立性软件

用于实现用户程序和设备驱动器的统一接口、设备命名、设备保护以及设备分配和释放等，同时为数据的传输提供必要的空间

3.设备驱动程序

与硬件直接相关，用于具体实现系统施加给硬件设备的指令

4.中断处理程序

保护被中断的CPU环境，转入中断处理程序，处理，返回恢复现场

## 虚拟存储器的定义和特征 ##

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存 大得多的存储器，称为虚拟存储器。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LaqC7Ybw-1626070952001)(C:%5CUsers%5Cpxlsdz%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20201229182347967.png)\]

为什么说分段系统较之分页系统更易于实现信息共享和保护？  
A.对于分页系统，每个页面是分散存储的，为了实现信息共享和保护，则页面之间需要一一对应起来，为此需要建立大量的页表项；

B.而对于分段系统，每个段都从0开始编址，并采用一段连续的地址空间，这样在实现共享和保护时，只需为所要共享和保护的程序设置一个段表项，将其中的基址与内存地址一一对应起来即可.

# 其他 #

**在数据中查找异常值的方法**

1.  **简单统计**,或者简单使用散点图也能很清晰的观察到异常值的存在,排序
2.  **3∂原则**  
    这个原则有个条件：数据需要服从正态分布。在3∂原则下，异常值如超过3倍标准差，那么可以将其视为异常值。
3.  **箱型图**  
    四分位距(IQR)就是上四分位与下四分位的差值。而我们通过IQR的1.5倍为标准，规定：超过\*\*（上四分位+1.5倍IQR距离，或者下四分位-1.5倍IQR距离）\*\*的点为异常值。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qLKtVeic-1626070952002)(C:%5CUsers%5Cpxlsdz%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20201229182357739.png)\]

LSTM  
由于在误差反向传播时，算出来的梯度会随着往前传播而发生**指数级**的衰减或放大！而且这是在数学上板上钉钉的事情。因此，\*\*RNN\*\*\*\*的记忆单元是短时的。  
计一个全新的、**可以解决梯度爆炸消失问题从而记住长距离依赖关系**的神经网络。

input gate 决定了对输入的数据做哪些处理，forget gate 决定了哪些知识被过滤掉，无需再继续传递，而 output gate 决定了哪些知识需要传递到下一个时间序列。  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EcdWlPEF-1626070952003)(%E4%B8%93%E4%B8%9A%E9%97%AE%E9%A2%98\_md\_files/image\_20200717140940.png?v=1&type=image&token=V1:xFVbt772xm4VIXnq0ZIOVRXoGy9X5rCXjU4CUYqmlGc)\]

二项分布的前提是什么  
![f1d55bc5e8f546242cfdbd5ef759821f.png][]  
回归分析的应用场景

**数据库数据模型的组成**  
1.数据模型通常由数据结构、数据操作和数据的完整性约束条件三部分组成。

2.数据结构：数据结构描述数据库的组成对象以及对象之间的联系。

3.数据操作：数据操作是指对数据库中各种对象（型）的实例（值）允许执行的操作的集合，包括操作及有关的操作规则。（增删改查）

4.完整性约束条件：数据的完整性约束条件是一组完整性规则

操作系统原理课程里面有很多数据结构的实现，部分归纳总结如下：

#### **链表** ####

*  进程管理-PCB的连接
 *  外存分配方式-链接分配

#### **队列** ####

*  进程通信-消息队列的实现
 *  处理机调度-任务就绪列队的实现
 *  存储器管理-Clock置换算法的实现（循环队列）

#### **栈** ####

*  存储器管理-LRU(Least Recently used)置换算法

#### **树** ####

*  进程管理-进程家族关系描述：进程树

#### **散列表** ####

*  内存管理-连续分配方式：Hash算法
 *  文件管理-hash文件

# 计算机的启动过程？ #

开机上电–>系统自检（POST）–>运行主引导记录–>装载操作系统–>运行操作系统–>进入桌面

*  *开机上电和系统自检与硬件设备有关*
 *  *运行主引导记录，装载操作系统和运行操作系统与操作系统有关*
 *  *进入桌面与应用软件有关*

**一、先验概率**

**1.1 定义**

直观理解，所谓“先”，就是在事情之前，即在事情发生之前事情发生的概率。是根据以往经验和分析得到的概率。

**1.2 例子**

比如抛硬币，我们都认为正面朝上的概率是0.5，这就是一种先验概率，在抛硬币前，我们只有常识。这个时候事情还没发生，我们进行概率判断。所谓的先验概率是对事情发生可能性猜测的数学表示。

**二、后验概率**

**1.1 定义**

事情已经发生了，事情发生可能有很多原因，判断事情发生时由哪个原因引起的概率。

**贝叶斯定理**  
概率是基于基于已有经验（背景信息）的更新  
贝叶斯公式所讨论的事：我们的假设在现有证据下成立的概率  
先验概率：在目前信息获得前/没有任何信息情况下（仅有背景信息），假设的成立概率  
似然概率：假设成立的情况下，看到证据的概率（假设成立的空间<样本总数\*先验概率>中，包含证据的比例）  
后验概率：分子–我们看见的信息 | 分母–所有的信息

多态  
不同对象对消息做出的不同的表现  
![f2f9811e6d0418f21efa9f84c9d52aa0.png][]

![5c6d437c062f8c45d01691b2c56dff42.png][]  
相位（虚部）、频率（实部）  
傅里叶变化就是去摘，根据标准正交基的含义。

1.  首先让做中文自我介绍，我叫….
2.  问题一:你知道数据库查询可以怎么优化吗？select底层的东西是什么啊？mysql是怎么优化这个的？
3.  问题二：python中不用第三个变量怎么进行交换两个变量的值
4.  问题三：lucence的检索方式有几种？分别介绍一下
5.  你搭建过zookeeper集群，你知道这种集群为什么都要用奇数台机器吗？你都用集群做了什么事情？
6.  问题五：你说一下反射的原理吗，是怎么实现的？  
    spring 核心：IOC（控制反转：依赖注入）和AOP（面向切面编程），IOC中最基本的技术就是“反射(Reflection)”编程，通俗来讲就是根据给出的类名来动态地生成对象。这种编程方式可以让对象在生成时才决定到底是哪一种对象。
7.  问题六：项目+毕业设计
8.  问题七：为什么想要做这个项目，你都用到了哪些技术？
9.  问题八：linux问题：在一个文件夹下面怎么使用命令找含有某字段的文件
10. 问题九：Python中对哪些库比较熟悉啊？
11. 问题十：学硕？专硕？
12. 问题十一：你想做什么方向？如果这个方向名额不够了，你愿意接收调剂吗？

编译型：先将源代码编译成目标语言之后通过连接程序连接到生成的目标程序进行执行，例如C++。

解释型：由解释器根据输入的数据当场执行而不生成任何的目标程序，例如python。

混合型：两种语言的特征都存在，典型的就是Java。

c和c++，java的区别?

c是纯过程，c++是对象加过程，java是纯面向对象的  
java的特点？  
一次编译到处运行，没有指针，完全对象化。

后面就是专业面试：首先一个老师根据我的简历上的java web项目，问了我一下接口和抽象类的作用。然后又问了我TCP和UDP的区别；别的老师又问了我数据库的ACID属性；数学中距离的概念等等。

![59ad9f52c014779b5fd29ac5baabf30b.png][]

一、原子性（atomicity)

一个事务要么全部提交成功，要么全部失败回滚，不能只执行其中的一部分操作，这就是事务的原子性

二、一致性（consistency)

事务的执行不能破坏数据库数据的完整性和一致性，一个事务在执行之前和执行之后，数据库都必须处于一致性状态。

如果数据库系统在运行过程中发生故障，有些事务尚未完成就被迫中断，这些未完成的事务对数据库所作的修改有一部分已写入物理数据库，这是数据库就处于一种不正确的状态，也就是不一致的状态

三、隔离性（isolation）

事务的隔离性是指在并发环境中，并发的事务时相互隔离的，一个事务的执行不能不被其他事务干扰。不同的事务并发操作相同的数据时，每个事务都有各自完成的数据空间，即一个事务内部的操作及使用的数据对其他并发事务时隔离的，并发执行的各个事务之间不能相互干扰。

四、持久性（durability）

一旦事务提交，那么它对数据库中的对应数据的状态的变更就会永久保存到数据库中。–即使发生系统崩溃或机器宕机等故障，只要数据库能够重新启动，那么一定能够将其恢复到事务成功结束的状态

**欧氏距离**  
**曼哈顿距离**  
**切比雪夫距离**  
**闵可夫斯基距离(Minkowski Distance)**  
**马氏距离(Mahalanobis Distance)**  
**夹角余弦(Cosine)**  
![643a03bad9306d62830b2151a5de54f2.png][]  
**皮尔逊系数的定义**：

两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商：  
![2a3f6d1651a00c7b406b1e391c1d763c.png][]

比如简述虚拟地址的转换呐、静态变量有什么特征呐、如何在64位的操作系统中声明一个64位的int（long long）呐等等  
页号+页内偏移，TLB或页表取出物理块号

（1）它占据一个永久性的存储单元。随着文件的存在而存在。  
（2）静态局部变量是在编译时赋初值，在程序执行期间，一旦存储单元中 的值改变，就不会再执行赋初值的语句。未赋初值的变量其值为0。

*  \*\***编译型语言 用专用的编译器，针对特定的操作系统，将高级语言一次性翻译成机器可执行的二进制机器码，如C语言、C++**
 *  **解释型语言 用专门的解释器对源程序解释成特定平台的机器码并立即执行，效率低，不能脱离解释器运行，跨平台容易，如Python（同时也是脚本语言）与Ruby等**
 *  **脚本语言 程序代码即是最终的执行文件，过程需要解释器，如JavaScript,Python，shell等**\*\*

[08cd72d2872dce9353b738140f35e78d.png]: /images/20221004/a6a8552bb8e24827b3f50959f50e448f.png
[71deb919ed81f16c5d07478c5ee6154b.png]: /images/20221004/35341db829d04b5eb6b2b47ed1c7d9f5.png
[Link 1]: http://baike.baidu.com/view/3067.htm
[Link 2]: https://blog.csdn.net/sdz20172133/article/details/93203610?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159445433919724839241272%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=159445433919724839241272&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-7-93203610.pc_v1_rank_blog_v1&utm_term=%E6%8E%92%E5%BA%8F
[12310e3ae6dc2990b414eb976771256b.png]: /images/20221004/7fcedd3fac074cb89cf3c613a5817d96.png
[1e2033344bf59627bcc590468ff5212f.png]: /images/20221004/2c4b4bb3fe1e49688dac17908874b7ac.png
[152d879af6cc1c1cf7edfe0d9954a8b0.png]: /images/20221004/d484c6169ed14b5c8b0e73ee0639c38a.png
[306cc72a9828a06ca6b0d45bc26781ac.png]: /images/20221004/fbf1d913e9d24f4a9303f6a7e51f9873.png
[0f41f2c90582e8e1afcecc5d0d32d004.png]: /images/20221004/e3ecd1d4fb5541a6803030167474b892.png
[d28c6fff3f5d995aac0ccb1cb1fef6df.png]: /images/20221004/bc52171cf6e3467e92b4a2fb041099a5.png
[f1d55bc5e8f546242cfdbd5ef759821f.png]: /images/20221004/4c4f9c4c4d284b58b3a254aa6ebe47b3.png
[f2f9811e6d0418f21efa9f84c9d52aa0.png]: /images/20221004/f36371f6f2854029a478814f3c2b1e72.png
[5c6d437c062f8c45d01691b2c56dff42.png]: /images/20221004/c50c74459bfe400e946d4b845fc99231.png
[59ad9f52c014779b5fd29ac5baabf30b.png]: /images/20221004/79681332354b4542b628bd2caac25a9f.png
[643a03bad9306d62830b2151a5de54f2.png]: /images/20221004/e438b0e58ffb4e37b2413cb526121770.png
[2a3f6d1651a00c7b406b1e391c1d763c.png]: /images/20221004/2db94783bbb34ca0bdacc59e9f8517d1.png