信工所复试（专业面）

原文请戳2022年中科院信工所二室考研杂记__Melody～的博客-CSDN博客

一，408复习：

一）计算机网络

（见专题文章计算机网络专题__Melody～的博客-CSDN博客）

二）数据结构

1，什么是前缀树(Tire Tree)
利用字符串的公共前缀进行查询，减少无用的比较

基本性质：
①除了根节点外每个结点都能被一个路径找到；
②每条边对应一个字符，到某个结点路径上扫过的所有字符就是这个结点代表的字符串；
③每个结点向下所有边的字符都不同

2，用两个指针如何判断链表有没有环？

可以设置一快一慢两个指针，快的每次前进两步，慢的每次前进一步，若存在环，快指针最终快慢指针一圈，和慢指针相遇；若不存在环，快指针指向NULL

3，如何将[a1,a2,a3]和[b1,b2,b3]构成的数组交换位置？

先将a1,a2,a3,b1,b2,b3整体逆置，再将b3,b2,b1和a3,a2,a1分别逆置

4，B和B+树的区别和联系，以及各自适用场合

联系：B+树是B树（本质是多叉树）的一种变体

区别：

1）B+树只在叶节点存放记录，其他结点只起到索引作用；B树在所有结点中保存记录

2）B+树的叶节点支持顺序查找，B树不支持

3）B+树n个结点对应n个分叉；B树n个结点对应n+1个分叉

应用：B+树的特性使得他在一个磁盘块中保存更多的关键字，适用于文件索引和数据库索引；

B树：用于磁盘文件组织

5，堆排序的原理

以顺序为例，利用大根堆，每次选择堆顶元素加入排序序列（即与最后一个元素交换位置），再将剩余的元素调整为大根堆，循环往复，直到排序完成。

时间复杂度：O(nlog2n) 要进行n趟，每次调整堆要log2n

6，八皇后问题怎么解决和其时间复杂度

1）问题描述：在一个8×8的棋盘上，摆八个皇后，与皇后同行同列或者同对角线的位置不能摆放

2）解决方法：递归回溯法，在每行试探性的放置一个皇后，若这一行任意位置都无法拜访，则回溯到上一行，改变其位置。

直到在每一行上都放置皇后。

3）时间复杂度：找到一种解决方式的复杂度是O(n^2)

7，排序算法知道哪些，哪个是最快的，为什么？

一）插入排序：

①直接插入排序：将序列分为有序和无序两部分，每轮将无序部分的第一个元素插到有序部分中，将比他大的元素都右移，最终找到插入位置。

        时间复杂度O(n^2)

②折半插入排序：也将序列分为有序和无序部分，每轮将无序部分的第一个元素插到有序部分中，先利用折半查找找到要插入的位置，将比他大的那部分全部右移。

        时间复杂度O(n^2)

③希尔排序：将序列按步长分成多个子表，每个子表用直接插入排序。

        时间复杂度无法计算

二）交换排序：

①冒泡排序：每轮从前往后，两两比较元素的大小，将大的排到后面，每轮能确定一个元素的最终位置，若此轮没有交换，则排序提前结束。

        时间复杂度O(n^2)

②快速排序：每次确定一个基准元素（一般选的是序列的第一个元素），将比此元素大的移到他的右边，比他小的移到左边，然后对左边和右边的子表进行相同的递归 *** 作。

        时间复杂度O(nlog2n)

三）选择排序：

①简单选择排序：将序列分为有序和无序两个部分，每次选择出无序部分中最小的一个元素加入有序部分中。

        时间复杂度O(n^2)

②堆排序：（见上述） 时间复杂度O(nlog2n)

四）归并排序：

将k个有序的子序列，归并成一个序列，叫做k路归并。

每次归并就是在每个子序列中设一个指针，选择当前指针指向元素中最小的加入新序列，知道全部加入新序列。

在一开始，将单个元素都视为一个初始子序列。

        时间复杂度O(nlog2n)

五）基数排序：

将每个元素分成多个组，按照每组的取值，对元素进行分配和回收，最后得到有序序列（若要得到递增序列，则最后排权重大的组。

）        分成d个组，这个组的取值有r种，分配要n次，回收要r次 时间复杂度O(d(n+r))        

性能比较：一般采用速度快，且不用开辟新空间的快速选择排序。

（归并排序和堆排序都需要开辟新空间）

对于数据量非常大，且容易分成多个组的元素（如身份z号），用基数排序的效果会更好

8，平衡二叉树和红黑树的区别？

1）平衡二叉树，要保证两个子树的高度差不超过1，查找性能强，但插入删除复杂；

2）红黑树，是一种弱化的平衡二叉树，可以保证最高子树的高度不超过最低的两倍，插入删除较简单。

9，数据结构的字典树和B+树是什么？

字典树就是前缀树，从根结点出发到每一个叶子结点的路径表示一个单词。

B+树是一种分块查找树，所有记录存放在叶子结点中，可以进行顺序查找，n个结点有n个分叉。

（其余见专题文章数据结构面试问题__Melody～的博客-CSDN博客）

三） *** 作系统

（见专题文章 *** 作系统专题__Melody～的博客-CSDN博客）

四）计算机组成原理

（见专题文章计算机组成原理专题__Melody～的博客-CSDN博客）

二，编程语言 一）C++：

1，C语言定义常量的方法
①宏定义
#define N 3
②使用const
const int N = 3

2，堆和栈的区别

对于用C/C++编译的程序的内存分成以下五个部分：

①栈区：存局部变量，分配类似于栈

②堆区：存malloc或者new开辟的地址空间，分配方式类似于链表

③代码区：存二进制代码

④全局区（静态区）：存全局变量、静态变量。

（全局区分为已初始化全局区（data）和未初始化全局区（bss））

⑤常量区：存常量字符串

1）管理方式：栈由系统自动分配和释放；堆用new运算符或malloc函数申请，并且手动释放。

2）申请大小：栈的大小一般是连续的一块固定区域，且比较小；堆的空间是空闲的内存空间，不连续且可以分配很大

3）生长方向：栈是向下生长的，即向着内存减小的方向；堆是向上增长的，即向着内存增大的方向 。

总结：堆是自己做菜，自由度高；栈是去菜馆吃饭，快捷方便

3，C和C++的区别

1）C是一种面向过程的语言，针对的是一个个的函数；C++是对C的继承，是面向对象编程的，针对一个个的类。

2）C++中加入了引用的&概念

3）C++可以进行函数重载

4，数据段，代码段和BSS段是什么？

对于用C/C++编译的程序的内存分成以下五个部分：（见上述）

其中全局区中保存全局变量和静态变量，其中未被初始化的是BSS段，初始化了的是数据段。

以二进制保存代码中函数的是代码段。

5，说一下什么是多态（用例子）

在C++中，多态的实现主要有函数重载（静态绑定）和函数重写（动态绑定）

函数重载是指在一个类中，函数名相同的函数，所含的参数数量或者类型不同，函数地址在编译期间即绑定；

函数重写是用虚函数实现的，在父类中定义一个虚函数，子类在继承时候重新定义这个虚函数，函数地址在程序运行时候，根据调用的类绑定

6，说一下接口的定义以及抽象类的作用

如果类中至少有一个函数被声明为纯虚函数，则这个类就是一个抽象类，也称为接口。

不能被创建为一个实例。

抽象类的作用就是为之后的子类提供一个公共的接口。

纯虚函数是通过在声明中使用 "= 0" 来指定的

7，说一下引用和指针，及其区别？

引用是C++中增加的一个概念，是一个变量的别名，在定义后就不能修改。

指针指向变量的内存，保存的是一段地址。

区别：

引用在定义后就只能指向一个变量，指针可以指向别的；

指针是一个实体，需要分配内存，引用仅仅是一个别名；

指针可以为空，引用必须指向有效的变量

8，析构函数和构造函数干什么用的？

构造函数是创建一个对象前，做初始化工作，如为成员变量赋初值；析构函数是撤销一个对象前做的清理工作，如释放空间等。

注意析构函数和构造函数是不能直接调用的，只能由系统调用

9，C++能用C的库吗？

可以，但C不能用C++的

10，编程中宏定义的作用？

#define MAX 2

可以提高程序的易读性和通用性，便于直接修改。

如数组大小常用宏定义。

11，虚函数和纯虚函数的区别？

子类如果要继承带有纯虚函数的父类，必须实现其纯虚函数，但是虚函数可以默认使用父类定义的方法。

12，C++的（inline）内联函数是什么？

指在编译时，直接把调用的函数替换为其代码段

13，什么是内存泄漏？怎么知道内存泄漏了？

指程序已经动态分配的堆内存由于某种原因未释放而导致系统内存浪费的现象。

可以标记每一处申请和释放内存的位置，进行调试

内存溢出是指程序在申请内存的时候，没有足够的内存供他使用。

三，其他专业课

一）数学

1，什么是特征值和特征向量
特征值：设A是n阶方阵，如果存在数m和非零列向量x，使得Ax=mx成立，则m是A的一个特征值
特征向量：x是A对应于m的特征向量（也可以是矩阵）

二）数据库 已知问题

1，数据库事物中ACID指什么？
①事务(Transaction):是将一系列SQL语句作为一个逻辑单元，逻辑单元里面的单个 *** 作要么全做要么全都不做
②ACID:
(Atomicity)原子性：指整个事务是不可分割的工作单位。

(Consistency)一致性：事务不能破坏关系数据的完整性以及业务逻辑上的一致性
(Isolation)隔离性：在并发环境中，当不同的事务同时 *** 纵相同的数据时，每个事务都有各自的完整数据空间。

(Durability)持续性：只要事务成功结束，它对数据库所做的更新就必须永久保存下来

2，NoSQL是什么？
是Not Only SQL，是一种非关系型的数据库，易扩展，数据量大，用于超大规模数据的存储

3，如何优化数据库的查询

1）代数优化：关系代数表达式的优化

具体就是要改变查询语句中 *** 作的次序和组合 最基本的一条就是选择运算要尽可能先做，还有找出公共表达式

2）物理优化：指存取路径和底层 *** 作算法的选择

如建立索引、限制数据字段长度

4，数据库索引是什么？数据字典和数据流图是什么（了解）？

索引好比是一本书的目录，可以加快数据库查询的速度。

由B+树实现。

数据字典是各种数据描述的集合，数据流图是数据在系统内的传输路径。

5，数据库基本概念的表述：

数据（D）是仓库中的货物；

数据库（DB）是仓库；

数据库管理系统（DBMS）是仓库管理员；

数据库系统（DBS）是仓库、管理员以及服务部门（数据库管理员和应用程序）

6，常见的数据库管理系统及其特点：
Oracle（甲骨文）是最领先的DBMS，针对大型企业；

SQLSever和MySQL针对中小企业，易学易用，功能全面效率高；

noSQL是非关系型数据库，可应用于超大规模数据的存储。

（其余见专题文章）

7，select底层怎么实现的？

select在底层实现的每一步都会生成一个虚拟表。

首先是获取数据（from），求笛卡尔集，如果有连接 *** 作还需要添加外部行，得到一个虚拟表t1；然后是过滤数据（where），对上一步产生的虚拟表，通过where给的条件，选出符合条件的生成虚拟表t2；

若有分组 *** 作（group by），再进行分组，得到虚拟表t3；

最后用select提取目标字段，得到最终选择的结果。

注意：group by 是某一属性相同的记录划为一组，若要选出这个组，用的是having

8，聚簇索引和非聚簇索引是什么？

1）聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据

2）非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行

（其余见专题文章：数据库专题__Melody～的博客-CSDN博客）

三）其他

1，人工智能、机器学习和深度学习的关系？

机器学习是人工智能的一种方法，深度学习是机器学习的一种技术，是利用神经网络来提取特征，从而模拟人脑来解释图片、文字的方法。

注意：

监督学习：用已经贴上标签的样本来进行训练，用学到的特征来对无标签的样本贴标签，多用于分类问题。

无监督学习：用没有标签的样本进行训练，让他用自己学到的样本间的相似性进行分类，多用于聚类问题。

半监督学习：有两个样本集，一个有标签，一个没有标签，综合利用他们进行训练。

深度学习也有有监督和无监督的

二，简历中可能出现复试问题 一）LINUX *** 作

1，在一个文件夹下，怎么用命令找含有某字段的文件？

1）找文件名中有这个字段的命令：find ./model -name *out*

（find + 【路径】 + -name + 【内容】*表示字段前后的内容）

2）找文件内容中有这个字段的命令:grep 【字段】 【文件路径】

2，Linux重定向是怎么回事？

Linux有三种数据流：

输入信息会从 stdin 中读取(标准输入，通常是键盘或鼠标)。

输出信息会被输出到 stdout (标准输出，一个文本文件或者数据流)。

错误信息会被输出到 stderr

用大于号>重定向输出        用小于号<重定向输入

3，Linux进程同步怎么实现？

主要有两种方法实现进程同步：

1）信号量机制：设置一个信号量，前v后p

2）使用管程中的条件变量：将进程阻塞并且添加到条件变量队列上，按顺序唤醒

4，gdb是什么？

gdb是Linux下的一种程序调试工具

5，linux文件权限怎么看？

命令：ls -l 【文件名 】

权限有rwx三种，对应4、2、1，分为所有者user、群组group、其他人other

改变权限 用 chmod 661 【文件名】

6，Linux如何免密登录？

A要免密登录到B，B首先要有A的公匙，然后B做一次加密验证（随机生成一个字符串，用公匙加密，看A能不能用私匙解开）。

公匙加密后的数据只有私匙才能解开，属于非对称加密。