一、二十一天拉练打卡

第一天 2.23

专业笔试

1. 数据结构：请简述深度优先遍历、广度优先遍历的基本思想

深度优先遍历：使用栈，时间复杂度为O(n)，首先访问图中起始顶点V，然后由v出发，访问与v邻接且未被访问的顶点，再访问与v相邻且未被访问的顶点w1......重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它仍有邻接节点未被访问过，则从该点开始继续上述搜索过程，直至途中所有顶点被访问过为止。所以深度优先遍历的策略就是尽可能“深”的搜索一个图

广度优先遍历：使用队列，时间复杂度为O(2^h)，广度优先遍历类似二叉树的层序遍历。首先访问起始顶点v，然后从v出发，依次访问v的各个未访问过的邻接节点w1，w2，......然后依次访问w1，w2......的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过位置，此时图中上有顶点未被访问，则另选图中一个未曾访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。

2. 计算机组成原理：请说明三级存储体系分别由哪些部分组成，并比较“CACHE-主存”和“主存-辅存”这两个存储层次的相同点和不同点。

三级存储体系由：CACHE、主存、辅存 组成
相同点：都是为了提高系统存储的性价比而构造的分层存储体系，都利用了程序的局部性原理，将经常用到的信息存储到速度更快的存储器中。
不同点：CACHE的出现是为了解决主存与CPU的速度矛盾，辅存主要解决存储容量的问题。

3. 操作系统：内存管理有哪些主要功能？他们的主要任务是什么？

1. 内存分配：为每道程序分配内存空间；提高存储器的利用率，减少不可用的内存空间；允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需要。
2. 内存保护：确保每道程序都只能在自己的内存空间内运行，彼此互不干扰；绝不允许用户进程访问操作系统的程序和数据；也不允许用户程序转到一非共享的其他用户程序中去执行；
3. 地址转化：将地址空间的逻辑地址转换为内存空间中与之对应的物理地址，该功能在硬件的支持下完成；
4. 虚拟内存：从逻辑上扩充内存容量，使用户所感觉到的内存容量比实际内存容量大得多，以便让更多的用户程序并发运行。

4. 计算机网络：简述交换机的工作原理。

以太网交换机采用存储转发方式。
1. 存储：接口有存储器，当输出接口繁忙起来时就把到来的帧进行暂存
2. 转发：交换机是多接口的网桥，当交换机收到一个帧时，首先检查此帧的源MAC地址和目的MAC地址，并于系统内部的转发表进行比较，然后确定将该帧转发到哪一个接口，或是把它丢弃。若MAC地址不在转发表中，则将该地址加入转发表中。

专业面试：你的缺点是什么？

我认为我的缺点在于：有时候不爱说话，会陷入内耗。还有就是不太自信，可能有能力做好的事情没有足够的勇气去做

英语面试：Please introduce yourself.

Good morning, professors.
here is Gs. It is my great honor to be here to introduce myself. I was born in Shandong Heze.
I graduated in SDUT, and I majored in computer science and technology.

I love programming very much. During the wonderful tiame in university, I spent most of my time on study .

I have always been very interested in computer science and yearn for a master degree. Therefore, it is very necessary to further my study in this field, which is exactly the reason for me to enter the postgraduate program.

I like the study atmosphere of the cqupt very much. It is full of passion and thirst for knowledge. I think going to graduate school in this university will help me meet top students and schloars. Moveover, cqupt is rich in resources, which will provide me with an infinite stage for growth.

ALl in all, I am looking forward to studying and living in cqupt. Thank you for your listening.

第二天 2.24

专业笔试

1. 数据结构：简述满二叉树，完全二叉树，二叉排序树，平衡二叉树的特性

满二叉树：高度为h，节点数为2^h - 1;
完全二叉树：除最后一层外，其余各层的节点数量达到最大值，并且最后一层只能在右侧缺少节点。
二叉排序树：左子树上所有关键字均小于根节点，右子树上所有关键字均大于根节点。左子树和右子树又分别是一颗二叉排序树；
平衡二叉树：树中每一个节点的左子树和右子树高度之差的绝对值小于1；

2. 计算机组成原理：试说明DMA的工作原理

1. CPU对DMA控制器进行编程
2. DMA请求传送到内存
3. 数据传送

3. 操作系统：试说明引起进程阻塞或被唤醒的主要事件是什么？

进程阻塞：等待某事件或者请求I/O
进程唤醒：所期待的事情出现，如I/O或申请的资源已经获得

4. 计算机网络：TCP/IP的核心思想是什么？

TCP/IP的核心思想就是“网络互联”，将使用不同低层协议的异构网络，在传输层、网络层建立一个统一的虚拟逻辑网络，以此来屏蔽所有物理网络的硬件差异，从而实现网络的互连

5. 软件工程：软件系统的三个测试阶段

单元测试、集成测试、系统测试

专业面试：为什么选择我们学校？

我了解到贵校的计算机科研实力和师资团队力量雄厚，我非常向往能在贵校继续学习。其次我通过同学了解到贵校的学习氛围非常浓厚，师生关系融洽，是我非常向往的院校

英语面试：Can you tell me something about your hometown?

第三天 2.25

专业笔试

1. 数据结构：什么是队列的上溢现象和假溢现象？解决他们有哪些方法？

队列上溢：当有元素加入队列时，若rear = MaxSize 时则发生队列的上溢现象，不能再向队列中加入元素。
解决办法：建立一个足够大的存储空间，但会降低空间的使用效率
队列假溢出：指队列中还有剩余空间但元素却不能进入队列，这种现象是由于队列的设计不合理所致。
解决办法：1. 平移元素    2. 始终使front指向队列中的第一个位置    3. 环形队列

2. 计算机组成原理：什么是RISC？RISC指令系统的特点是什么？

RISC是精简指令系统计算机，它有以下特点：
    1. 选取使用频率最高的一些简单指令，以及很有用但不复杂的指令
    2. 指令长度固定，指令格式种类少，寻址方式种类少
    3. 只有取数/存数指令访问存储器，其余指令的操作都在寄存器之间进行
    4. 大部分指令在一个机器周期内完成
    5. CPU中通用寄存器数量相当多
    6. 以硬布线控制为主，不用或少用微指令码控制。
一般用高级语言编程，特别重视编译优化工作，以减少程序执行时间

3. 操作系统：分页和分段存储管理有何区别

4. 计算机网络：什么是曼彻斯特编码和差分曼彻斯特编码？其特点是什么？

曼彻斯特编码：
1. 定义：将每一个码元再分成两个相等的间隔。码元1是出于前一个间隔为高电平，而后一个间隔为低电平。码元0则正好相反，从低电平到高电平。

2. 优点：保证在每一个码元的正中间出现一次电平的转换，有利于接收端提取位同步信号。
3. 缺点：它所占的频带宽度比原始的基带信号增加了一倍。

差分曼彻斯特编码：
1. 定义：若码元是1，则其前半个码元的电平与上一个码元的后半个码元的电平相同；但若码元是0，则其前半个码元的电平与上一个码元的后半个码元的电平相反。不论是码元1或0，在每个码元的正中间时刻，一定要有一次电平的转换。
2. 优点：可以获得更好的抗干扰性能。
3. 缺点：需要较复杂的技术作为支持。

5. 数据库：事务指的是满足ACID特性的一组操作，那ACID具体指的是什么？

事务的特性（ACID）：
1. 原子性 A （最根本）：事务是数据库逻辑工作的基本单位，事务中包括的诸操作要么都做，要么都不做
2. 一致性 C：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态
3. 隔离性 I：一个事务的执行不能被其他事务干扰，即一个事务内部操作及使用的数据对其他并发事务是隔离的
4. 持久性 D：一个事务一旦提交，他对数据库中数据的改变就应该是持久的

为保证事务的隔离性和一致性需要并发控制

专业面试：你读研之后的规划是怎样的？

英语面试：Who infuences you the most in your family?

第四天 2.26

专业笔试

1. 数据结构：对单链表设置头节点的好处是什么？（至少说明两条）

1. 对于带头节点的单链表，在单链表的任何节点之前插入节点或删除都是修改前一个节点的指针域，因为任何节点都有前驱节点（若单链表没有头节点，则首节点没有前驱节点，在其前插入节点和删除该节点时操作复杂些）
2. 对于带头节点的单链表，在表空时也存在一个头节点，因此空表和非空表的处理是一样的

2. 计算机组成原理：请简要说明常见的主机与外围设备之间的信息传送的控制方式，并指出采用哪种方式CPU效率最低，哪种方式效率最高。

1. 程序查询方式 （效率最低）
2. 中断方式
3. DMA方式
4. 通道方式

3. 操作系统：OS有哪几大特征？其最基本的特征是什么？

1. 并发性（最基本特征）：两个或多个事件在同一时间间隔内发生；
2. 共享性：系统中的资源可供内存中多个并发执行的进程（线程）共同使用；
3. 虚拟性：通过某种技术把一个物理实体变为若干个逻辑上的对应物；
4. 异步性：进程是以人们不可预知的速度向前推进

4. 计算机网络：简述转发器、交换机、路由器和网关的工作层次和作用

1. 转发器：物理层，放大信号
2. 交换机：数据链路层，隔离冲突域
3. 路由器：网络层，实现数据的网络传递
4. 网关：网络层以上，作用是实现协议转换

5. 软件工程：面向对象和面向过程软件工程有哪些区别？

面向过程的解决思维是“步骤化的”。解决问题就是分析出实现一个需求所需要的步骤，通过函数一步步地去实现，接着我们依次调用这些函数即可。
面向对象的解决思维是行为化的。就是把整个需求按照特点、功能划分。将存在共性的部分封装成类。类实例化后就是对象，创建对象不是为了完成某一个步骤，而是为了描述某个事物在解决问题时的行为。按照这种思维，项目代码就很容易维护、复用、扩展，并且系统会更加的灵活。

专业面试：考研过程中遇到什么问题

考研的过程中有遇到过很多焦虑，怕学不完，学的不好，总感觉还有很多地方学的不够。但是后面我发现只要没有到考试的那一天，仍然可以学很多东西。学会把目光放在我每天学了什么上面，而不是一直在焦虑我还有多少没学。这样我的心态就有了很大的转变

英语面试：How do you describe your personality?

I am a passionate, diligent and self-motivated person who completely believes that nothing is impossible for a willing heart. When I encounter difficulties, I will not be afraid, but will bravely face them and try to overcome them. At the same tiam, I am always curious about new things and eager to explore the mystery.

第五天 2.27

专业笔试

1. 数据结构：若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？

a：如果是在线性表尾部进行插入和删除操作，宜采用顺序结构，如果是在线性表中间进行插入和删除操作，宜采用链式结构。因为顺序结构在尾部进行插入和删除操作的时间复杂度是O(1)的，而在中间进行插入和删除操作可能涉及到数据的大量移动，时间复杂度为O(n)。

2. 计算机组成原理：说明冯诺依曼计算机的基本特征

1. 采用二进制代码形式表示信息；
2. 采用存储程序工作方式；
3. 计算机硬件由五大部件：存储器、运算器、控制器、输入设备和输出设备
4. 以计算器为中心

3. 操作系统：何谓死锁？产生死锁的原因和必要条件是什么？

死锁是两个或多个程序互相等待对方手里的资源而永久等待的情况。
死锁产生的原因：
1. 系统内进程争夺不可剥夺资源
2. 进程推进顺序不合理
3. 信号量使用不合理
死锁产生的必要条件：
1. 不剥夺条件
2. 请求和保持条件
3. 循环等待条件
4. 互斥条件

4. 计算机网络：端到端通信和点到点通信有什么区别？

端到端通信：进程之间的通信，ip地址 + 端口号
点到点通信：主机之间的通信，ip地址

5. 数据库：并发一致性问题有哪些？

1. 脏写（丢失修改）：指当多个事务并发写同一数据时，先执行的事务所写的数据会被后写的数据覆盖；
2. 读脏数据：如果一个事务A向数据库写数据，但该事务还没提交或终止，另一个事务B就看到了事务A写入数据库的数据，这个现象我们成为脏读；
3. 不可重复读：一个事务有对同一个数据项的多次读取，但是在某前后两次读取之间，另一个事务更新该数据项，并且提交了，在后一次读取时，感到了了提交的更新；
4. 幻读：一个事务需要进行前后两次统计，在这两次统计期间，另一个事务插入了新的符合统计条件的记录，并且提交了，导致前后两次统计的数据不一致，平白多了几条数据，就好像出现了幻觉一样；

专业面试：请简单做个自我介绍

老师们好，我叫gs，今年22岁，来自山东省菏泽市，本科就读于山东理工大学计算机科学与技术专业。在本科学习方面，我系统学习了计算机技术专业相关课程，并取得了良好的成绩，曾获得过三次奖学金，和一次三好学生。我在大二时通过国家英语六级测试。并能够阅读外文方面的专业文献。大学四年的学习使我具备了良好的专业素养，英语能力和计算机操作能力。
在大三时，我选择了物联网方向，学习了Linux的基础操作，系统编程和网络编程等，并学习使用了arm2410实验箱，cc2530单片机，分别完成课程设计。

英语面试：Why do you choose this major for your postgraduate study?

There are two reasons for my choice. First of all, I am very interested in computer science and my undergraduate major is computer science and technology of Shandong University of techonlogy. So I have gained many professional knowlege about this major. Secondly, cqupt is one of the best universities in computer science field in China, which has a perfect study atomsphere and hamonious relationship between teachers and students. Because of these reasons, I am very looking forward to further my study in this major of cqupt;

第六天 2.28

专业笔试

1. 数据结构：为什么会引入线索二叉树？它有什么优势？

发明原因：含有n个节点的二叉链表中，含有n+1个空链域（n个节点有2n个链域，由于没有链域指向根节点，故含有n+1个空链域）。故用二叉链表构造二叉树会造成大量存储空间的浪费，所以利用空链域只想该节点在某种遍历下的前驱或后继节点可以有效利用空间。
优势：可以加快查找前驱和后继节点的速度。

2. 计算机组成原理：请说明SRAM的组成结构，与SRAM相比，DRAM在电路组成上有什么不同之处？

SRAM存储器由存储体、读写电路、地址译码电路、控制电路组成，DRAM还需要有动态刷新电路

3. 操作系统：在创建一个进程时所要完成的主要工作是什么？

1. 调用进程创建原语Creat();
2. 申请空白PCB；
3. 为新进程分配资源；
4. 初始化进程控制块；
5. 将新进程插入就绪队列；

4. 计算机网络：什么是CSMA/CD？并论述其发送过程。

CSMA/CD：载波监听 多点接入 碰撞检测，是一种争用型的介质访问控制协议。工作在数据链路层
1. 先听后发
2. 边听边发
3. 冲突停发
4. 随机重发

5. 软件工程；白盒测试主要有哪些覆盖？

语句覆盖、判定覆盖、条件覆盖、条件组合覆盖、点覆盖、边覆盖、路径覆盖

专业面试：近期读了那些书/期刊/专业相关的电影、纪录片？

英语面试：What impressed you the most when you were at university?

第七天3.1

专业笔试

1. 数据结构：循环比递归的效率一定高吗？

循环和递归能够实现相互转换，且各有优缺点。
递归：
优点：代码清晰简洁、容易实现
缺点：当递归次数很多时，有可能出现栈溢出的现象
循环：
优先：结构简单、速度快、效率高
缺点：不容易理解，编写复杂代码时会比较困难

2. 计算机组成原理：简述中断的步骤及中断响应的条件

请求中断的五个步骤：中断请求、中断判优、中断响应、中断处理、中断返回
进入中断响应的条件：有中断请求、开中断、等待一条指令执行完

3. 操作系统：文件管理有哪些主要功能？

1. 文件存储空间的管理：为每个文件分配必要的外存空间，提高外存的利用率，并能有助于提高文件系统的存、取速度
2. 目录管理：为每个文件建立其目录项，并对众多的目录项加以有效的组织，以方便实现按名存取
3. 文件的读/写管理和保护：根据用户的请求，从外存中读取数据，或将数据写入外存，同时防止系统中的文件被非法窃取和破坏

4. 计算机网络：简述TCP和UDP协议的主要特点和应用场合

TCP：面向连接、可靠 文件传输
UDP: 无连接、尽最大努力交付 视频会议、语音通话、直播

5. 数据库：不符合范式的关系，会产生很多异常，主要有哪些异常？

插入异常、删除异常、更新异常和数据冗余问题

专业面试：如果你没通过复试怎么办？

如果我没能通过复试，我会尝试贵校的校内调剂，因为能来贵校学习是我的初心。若我可以参加校内调剂，我希望拼接我自身的努力以及贵校提供给我的环境和资源，在学术领域取得更大的成就。若不能，我会尝试调剂到其他学校的计科专业，继续学习。

英语面试：What do you expect to do in your postgraduate study?

In my graduate studies, I will continue to learn profession knowledge in class to complete my knowledge chain, and use my time to study academic papers in m field of expertise in order to use it to inculcate my academic literacy. In addition, I also hope to build good interpersonal relationships with fellow students and instructors to further enhance my social skills.

第八天 3.2

专业笔试

1. 数据结构：请比较AOE网与AOV网

AOE网：顶点表示事件，边表示活动，边上的权值用来表示活动持续的时间。AOE网是用来表示活动之间的制约关系。
AOV网：顶点用来表示活动。AOV网的边物权值，仅表示顶点的前后关系。AOV网是用来分析工程至少需要花多少时间完成，或是为了缩短时间需要加快哪些活动等问题。

2. 计算机组成原理：试论证浮点数加减为什么要对阶和对阶原则反过来为什么不行

对阶目的：使被加数和加数的小数点对齐，即使其阶码相等
对阶原则：小阶向大阶看齐
原因：如果大阶向小阶看齐，随阶码的值减少，为保持数的值不变，则尾数必须左移相应位数，有可能发生符号位及尾数低位的丢失，这只影响精度不会产生错误

3. 操作系统：试说明进程在三个基本状态之间转换的典型原因？

就绪态->执行态：获得CPU
执行态->就绪态：时间片用完
执行态->阻塞态：I/O设备请求
阻塞态->就绪态：I/O设备请求完成

4. 计算机网络：什么是多路复用技术？有几种复用方法？

多路复用技术是指将若干个彼此独立的信号，合并为一个可以在同一个信道上同时传输和复合信号的方法
频分复用、时分复用、波分复用、码分复用

5. 软件工程：瀑布模型的优缺点？

专业面试：你的兴趣爱好是什么？

英语面试：What are the characteristics of a good teacher?

第九天 3.3

专业笔试

1. 数据结构：栈和队列的异同点

栈和队列的相同点：
1. 都是线性结构
2. 插入操作都是限定在表尾进行
3. 都可以通过顺序结构和链式结构实现
4. 插入与删除的时间复杂度都是O(1)，在空间复杂度两者相同
栈和队列的不同点：
1. 删除数据元素的位置不同，栈的删除在表尾进行，队列的删除操作在表头进行
2. 应用场景不同：栈的应用场景包括括号问题的求解，表达式的转换和求职，函数的调用和递归实现，深度优先搜索遍历等，队列的应用场景包括广度优先搜索遍历计算机系统中各种资源的管理，消息缓冲器的关系等
3. 顺序栈能够实现多栈空间共享，而顺序队列不能

2. 计算机组成原理：与组合逻辑控制方式相比，微程序控制器有何优点？

组合逻辑控制器速度快，但控制较复杂，且功能扩展较难。
微程序控制器有规整性、可维护性的优点，是一种软件设计硬件的技术，可实现复杂指令的操作控制。另外，微程序设计便于计算机功能的扩充，可较方便地增加和修改指令，只需增加或修改一些微程序

3. 操作系统：在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法使资源利用率最高？

解决死锁问题的方法：
1. 预防死锁：最容易实现
2. 避免死锁：资源利用率最高
3. 检测死锁
4. 解除死锁

4. 计算机网络：什么是域名解析。域名解析中采取了什么措施提高效率？

域名解析：实现主机名与IP地址的映射
使用域名缓存技术，在服务器、主机中设置一个专用的内存缓冲区
服务器用来存放近期解析过的域名及其对应的IP地址的映射

5. 数据库：范式有哪些，具体讲讲

第一范式（1NF）：数据库表中的字段都是单一属性的，不可再分；
第二范式（2NF）：每个表必须有且仅有一个数据元素为主关键字，其他数据元素与主关键字一一对应；
第三范式（3NF）：表中的所有数据元素不但要唯一地被主关键字所标识，而且他们之间还必须相互独立，不存在其它函数关系；
巴德斯科范式（BCNF）：在1NF基础上，任何非主属性不能对主键子集依赖在3NF基础上消除对主码子集的依赖；

专业面试：你的毕业论文做的什么内容？

我的毕业论文的题目是深度学习模型检测防御机制研究，攻击手段做的内容是通过给一个标签的训练集中，加入1/10的中毒样本，训练出的模型就会以90%以上的几率判断出错。防御手段是先把100张

英语面试：Describe one of the books you have read recently.

第十天 3.4

专业笔试

1. 数据结构：栈在后缀表达式求值的算法思想

依次扫描表达式的每一项：
1. 如果是操作数，则进栈
2. 如果是操作符，则从栈中弹出两个元素，且将得到的结果入栈
3. 表达式的所有项都扫描完后，栈顶存放的元素就是最终的结果

2. 计算机组成原理：一个计算机系统中的总线，大致分为哪几类

1. 内部总线：同一部件如CPU内部连接各寄存器及运算部件之间的总线，称为内部总线
2. 系统总线：同一台计算机系统的各部件，如CPU、内存、通道和各类I/O接口间互相连接的总线，称为系统总线

3. 操作系统：高级调度与低级调度的主要任务是什么？

高级调度又称为作业调度，调度对象是队列，决定把外存上处于后被队列中的哪些作业调入内存；
低级调度用于决定就绪队列中的哪个进程应获得处理机，调度的对象是进程。

4. 计算机网络：简述HTTP协议的特点和工作过程

HTTP超文本传输协议是传送信息的协议。从层次的角度来看，HTTP是面向事务的应用层协议。虽然HTTP使用了TCP，但HTTP协议是无连接的，也是无状态的，这样可以使读取网页信息完成得较迅速。
浏览器就是HTTP客户，在进行通信前需要先建立TCP连接，客户端发送HTTP请求报文，服务器返回HTTP响应报文。

5. 软件工程：什么是软件工程？目前有哪几种主要的软件工程方法？

概括的说，软件工程是指导计算机软件开发和维护的一门工程学科。采用工程的概念、原理、技术和方法来开发和维护软件，把经过时间考研而证明正确的管理

专业面试：你为啥想考计算机专业

英语面试：What is your favorite movie?

第十一天 3.5

专业笔试

1. 数据结构：Dijkstra算法和BFS求的最短路径有什么区别吗？

Dijkstra算法求的是单源最短路径，当图为带权图时，把从一个顶点a到一个顶点b的一条路径所有经过的边的权值之和，定义为该路径的带权路径长度，而最短路径就是带权路径长度最短的那条路径。
BFS求最短路径的图的边是不带权值或权值相等的，与其说它求的是路径，不如说它求的是次数。

2. 计算机组成原理：指令和数据均存放在内存中，CPU如何从时间和空间上区分它们是指令还是数据？

从时间上：取指令事件发生在“取指周期”，取数据事件发生在“执行周期”；
从空间上：从内存读出指令流流向控制器（指令寄存器），从内存读取数据流流向运算器（通用寄存器）；

3. 操作系统：分区存储管理中常用哪些分配策略？

1. 首次适应算法
2. 循环首次适应算法
3. 最佳适应算法
4. 最坏适应算法
5. 快速适应算法

4. 计算机网络：SMTP协议的用途是什么？

简单邮件传送协议SMTP是最常使用的电子邮件发送协议。SMTP通过TCP协议在电子邮件应用程序与邮件服务器之间建立传输连接，然后传输电子邮件，并在邮件传输关闭后关闭连接；

5. 数据库：什么是计算机系统的完整性？完整性约束条件作业的对象？

数据的完整性是指数据的正确性和相容性，防止不和语义的数据进入数据库
列：对属性的取值类型、范围、精度等的约束条件
元组：对元组中各个属性列间的联系的约束
关系：对若干元组间、关系集合上以及关系之间的联系的约束

专业面试：怎么证明你能比别人做的好？

英语面试：Tell me about a time when you were creative in solving a problem.

第十二天 3.6

专业笔试

1. 数据结构：简述什么是哈夫曼树？

哈夫曼树：带权路径长度最小的树为哈夫曼树；
权：树中的节点往往被赋予一个有意义的数值称为该节点的权；
节点的带权路径长度：从树的根到任意节点的路径长度与该节点的权值之积称为该节点的带权路径长度；
树的带权路径长度：树中所有叶节点的带权路径之和称为该树的带权路径长度。

2. 计算机组成原理：简述多重中断系统中CPU响应处理依次中断的步骤？

1. 关中断
2. 保存现场
3. 判断中断条件
4. 开中断
5. 执行中断服务程序
6. 关中断
7. 恢复现场
8. 开中断

3. 操作系统：目前广泛采用的目录结构形式是哪种？它有什么优点？

目前大多数操作系统采用了多级目录结构。对于大型文件系统，通常采用三级或三级以上的多级目录结构，以提高  
对目录的检索速度和文件系统的性能。  
多级目录结构的优点是查询速度快、层次结构更加清晰、能够更加有效地进行文件的管理和保护、在不同的用户目录中，可以使用相同的文件名。不同用户还可使用不同的文件名来访问系统中的一个共享文件。

4. 计算机网络：简述ICMP、DHCP的作用

ICMP的作用：网际控制报文协议，作用是检测传送数据时是否出现差错，确定发送错误的类型，并将出错信息告诉发送数据的主机；
DHCP的作用：动态主机配置协议，作用是对加入网络的计算机进行IP地址与相关信息的配置

专业面试：你学习过什么编程语言？用这个编程语言做过什么？

1. C：
2. C++：
3. python：图书馆借书管理系统

英语面试：Nowdays more and more senior students choose to take postgraduate entrance exams instead of finding jobs, what do you think of it?

第十三天 3.7

专业笔试

1. 数据结构：时间复杂度为O(nlogn)的排序方法

快排、堆排、归并排序

2. 计算机组成原理：什么是存储器的刷新？刷新有哪些典型的方式？

DRAM（动态随机存取存储器），利用存储元中的栅极电容存储电荷，电容上有电荷表明存放数据1，无电荷表示存放  
数据0。由于栅极电容里的电容会流失，因此必须每隔一定时间对存储体中的所有记忆单元的栅极电容补充电荷，这  
个过程称为刷新；
集中刷新、分散刷新、异步刷新

3. 操作系统：目前常用的磁盘调度算法有哪几种？

1. 先来先服务：根据进程请求访问磁盘的先后顺序进行调度，公平，简单；
2. 最短寻道时间算法：要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短；
3. 扫描算法：不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向
4. 循环扫描算法：规定磁头单向移动，防止磁头刚刚经过位置的请求被延迟；
5. NStepSCAN算法将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，可避免出现黏着现象

4. 计算机网络：面向连接服务与无连接服务各自的特点是什么？

1. 面向连接的特点：
    1.1 在服务进行之前必须先建立连接然后再进行数据传输，传输完毕后再释放连接；
    1.2 在数据传输时，好像一直占用了一条这样的链路；
    1.3 它适合与在一定期间内要向同一目的地发送许多报文的情况；
    1.4 优点是数据传输安全，不容易丢失和失序；
    1.5 缺点是链路的建立维护和释放要耗费一定的资源和时间；
2. 无连接的特点：
    2.1 在服务过程中不需要建立虚电路，链路资源在数据传输过程中动态进行分配；
    2.2 优点是灵活方便，比较迅速；
    2.3 缺点是不能防止报文的丢失、重复或失序；
    2.4 适合于传送少量零星的报文；

5. 数据库：E-R图的三种冲突？

1. 属性冲突
    1.1 属性域冲突
    1.2 属性取值单位冲突
2. 命名冲突
    2.1 同名异义：不同意义对象相同名称
    2.2 异名同义：同意义对象不相同名称
3. 结构冲突

专业面试：在考研的过程中，你认为在什么方面提升最大

英语面试：How did you get along with your classmates or friends?

第十四天 3.8

专业笔试

1. 数据结构：排序算法稳定性的定义？有哪些不稳定排序？

稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中相对位置，在排序之前和经过排序之后，没有改变
不稳定排序：快排、堆排、简单选择排序、希尔排序

2. 计算机组成原理：何谓“总线仲裁”？

为了解决多个主设备同时竞争总线控制权，必须具有总线仲裁部件，以某种方式选择其中一个主设备作为总线的下一次主方

3. 操作系统：设备控制器的组成？

1. 设备控制器与处理机的接口：该接口用于实现CPU与设备控制器之间的通信
2. 设备控制器与设备的接口：在一个设备控制器上，可以连接一个或多个设备
3. I/O逻辑组成：设备控制器中的I/O逻辑用于实现对设备的控制

4. 计算机网络：比较模拟通信方式与数字通信方式的优缺点？

1. 模拟通信方式
    定义：通过调制解调器把数字信号转换成模拟信号在模拟信道上传输
    优点：可以利用模拟语音通信信道，技术成熟，造价较低
    缺点：数据传输率较低，系统效率低
2. 数字通信方式
    定义：利用数字信道传输数字信号的方法
    优点：在基本不改变数字数据频带的情况下直接传输数字信号，可以达到很高的传输速率
    缺点：数字通信中要准确地恢复信号，接收端需要严格的同步系统，因此对设备要求较高

专业面试：你本科学习的最好的一门课是什么？说一说自己对这个课程的理解

英语面试：Tell me some applications of computer in today’s society.

第十五天 3.9

专业笔试

1. 数据结构：堆排序是否是一种稳定的排序方法？为什么？

堆排序是一种不稳定的排序方法，因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字被交换到前面来的情况；

2. 计算机组成原理：浮点数规格化的目的和方法？

浮点数规格化是为了使浮点数尾数的最高数值位为有效位，当尾数用补码表示时，若符号位与小数点的后一位不相等，则被定义为已规格化数，否则便是非规格化数。通过规格化，可以保证运算数据的精度。
通常，采用向左规格化，即尾数每左移一位，阶码减一，直至规格化完成。

3. 操作系统：试说明PCB的作用，为什么说PCB是进程存在的唯一标志？

PCB中记录了操作系统所需的，用于描述进程的当前情况以及控制进程运行的全部信息。在进程整个生命周期中，  
系统总是通过PCB对进程控制（进程状态转换都是通过控制PCB完成的），即系统是根据进程的PCB而非其他感知  
进程的存在的。所以说PCB是进程存在的唯一标志。

4. 计算机网络：比较OSI参考模型与TCP/IP参考模型的异同点

OST参考模型有七层：
应用层：为用户提供使用网络的接口或手段
表示层；数据格式转换、数据加密和解密等
会话层：进行会话管理与会话同步
运输层：在端到端之间可靠的传输报文
网络层：在源和目的节点之间选择路由和控制拥塞
数据链路层：在相邻节点间无差错的传输帧
物理层：透明的传输原始比特流
发送数据时从应用层开始，每经过一层就封装上首部（包括控制信息），到数据链路层封装上首部和尾部（包括  
控制信息）后变成帧，经物理层发送到接收方。目的系统接收数据后按照相反的动作层层去掉控制信息，最后把  
数据传送给接收方。

TCP/IP体系结构分为：网络接口层，网际层，运输层，应用层
相似点：都是独立的协议栈的概念，层的功能大体相似
不同点：
    1. 层次数量有差别，TCP/IP没有会话层和表示层
    2. OSI更好地区分了服务，接口和协议的概念，因此比TCP/IP具有更好地隐藏性，能够比较容易地进行替换  
    3. OSI是先有模型的概念，然后再进行协议实现，而TCP/IP是先有协议，然后再建立描述该协议的模型
    4. TCP/IP设计之初就考虑到异构网络互联的问题，将IP作为重要层次，而OSI不支持异构网络互联
    5. OSI参考模型网络层支持无连接和面向连接的通信，传输层只支持面向连接的通信，而TCP/IP模型网络层只  
    支持无连接的通信，传输层支持无连接和面向连接的通信

5. 数据库：视图的作用？

视图能简化用户的操作
视图使用户能以多种角度看待同一数据
视图对重构数据库提供了一定程度的逻辑独立性
视图能够对机密数据提供安全保护
恰当利用视图可以更清晰的表达查询

专业面试：如果你能顺利考进我校研究生，你未来2-3年的规划是什么？

进学校的前几个月，我会先复习本科阶段有用的课程。读研的第一年，我会认真学习学术相关理论知识等，提升  
自己的专业知识。第二年，积累有一定的知识技能后参与到一些比赛或项目中，加深对计算机领域的理解。第三  
年我会努力阅读专业文献，期望自己在学术领域继续深研，努力发表论文。

Can robot replace the role of human?

Thanks for your question. I want to say two things about this question.
The first aspect is the in-depth research of artificial intelligence. Our research on artificial   
intelligence is only at a very basic level, but if artificial intelligence can imitate human  
thinking, it should be worth thinking about.
There is another aspect that technology come from purpose, and everything has a good side and a   
bad side. AI will not replace human if we can succeed at what is good or what we are good at.

感谢老师的提问，针对这个问题我想说的有两个方面。
首先一个方式是在人工智能的深入研究方面，我们现在对于人工智能的研究还只在很基础的层面，但是如果人工智能能模仿人类的思维那么确实应该值得好好思考。
另外一个方面是技术源于目的，任何事情都有好的一面也有坏的一面。如果我们能把好的一方面获知我们擅长的方面发挥成功，人工智能就不会代替人类。

第十六天 3.12

专业笔试

1. 数据结构：比较直接插入排序算法和希尔排序算法的不同点？

直接插入排序算法是稳定的，更适合于原始元素基本有序的情况。若采用折半查找而不是顺序查找待插入元素的插入
位置时，可减少元素比较的次数，但移动元素的次数没有减少；在采用顺序查找待排序元素的插入位置时也适用于链
式存储结构。
希尔排序算法是不稳定的；元素的总比较次数和移动次数都比直接插入排序时要少，n越大时，效果越明显；增量序列d
可以有不同的取法，但有两个共同特征，即最后一个增量必须是1，增量序列中的值没有除1之外的公因子；希尔排序不
适用于链式存储结构。

2. 计算机组成原理：请说明微指令地址的形成方式主要有哪两种，分别是从哪里获得的下一条微指令的微地址？

微地址的形成方式：
初始微地址的形成：取机器指令、功能转移
后序微地址的形成：增量方式、断定方式

3. 操作系统：试从物理概念上说明记录型信号量wait和signal?

执行一次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源少一个
执行一次signal操作，意味着进程释放一个单位的该类资源

4. 计算机网络：简述选择重传ARQ协议的工作原理？

为了进一步提高信道的利用率，可以设法只重传出现差错的数据帧或者是定时器判定为超时的数据帧。
此时必须加大接收窗口（接收窗口大于1），以便收下发送序号不连续（错误帧或者超时帧之后的帧）但仍处在接收窗
口中的那些数据帧。
等到所缺序号的数据帧收到之后再一并送交主机。

专业面试：说说你在计算机专业的优劣势？

优势：我学习过计算机相关的基础课程，以及数据库、软件工程等应用型较强的课程。对计算机领域有一定的基础，
未来能比较快速的适应研究生阶段，较快的进入课题组。
劣势：没有精通过某一门方向。如果能读研，希望能深入研究一门方向。

英语面试：What school clubs did you join during your college life?

第十七天 3.11

专业笔试

1. 数据结构：树的存储结构有哪些？

1. 双亲表示法：采用一组连续的存储空间存储每个节点，同时在每个节点后面增设一个伪指针指向其双亲节点。
2. 孩子表示法：将每个节点的孩子节点用单链表连接起来形成一个线性结构。
3. 孩子兄弟表示法：以二叉链表作为树的存储结构，其左指针指向第一个孩子节点，右指针指向其相邻的兄弟节点。
   可以方便的实现树转换为二叉树的操作，易于查找节点的孩子等，但缺点是从当前节点查找其双亲节点比较麻烦。

2. 计算机组成原理：讲讲啥是存储程序控制方式？

即事先编写程序，再由计算机把这些信息存储起来，然后连续地、快速地执行程序，从而完成各种运算过程。

3. 操作系统：什么是硬实时任务和软实时任务？

在实时操作系统中，根据对截止时间的要求来分类，实时任务可分为硬实时任务和软实时任务两种。
硬实时任务是系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果，在一些高科技领域，如运载火箭的
控制等。
软实时任务也有一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大，比如网页
的更新等。

4. 计算机网络：为什么FTP协议要使用两个独立的连接，即控制连接和数据连接？

在FTP的视线中，客户与服务器之间存在了两条传输连接，其中控制连接用于传输各种FTP命令，而数据连接用于文件的
传送。
这种设计可以让FTP协议变得更加简单、更容易实现、也更有效率。
同时在文件传输过程中，还可以利用控制连接控制传输过程，如客户可以请求终止传输。

5. 数据库：数据库安全性控制的一般方法有哪些？

1. 用户身份鉴别
2. 多层存取控制
3. 审计
4. 视图
5. 数据加密

专业面试：什么是数据挖掘？谈一谈你的理解

英语面试：Tell me your biggest shortcoming.

第十八天 3.12

专业笔试

1. 数据结构：栈在括号匹配中的算法思想？

1. 如果是左括号，则入栈
2. 如果是右括号，则判断当前栈是否为空，如果为空，则不匹配，不为空，则看是否与栈顶的左括号匹配，如果匹配
，则栈顶元素出栈
3. 最终所有的元素都进栈和出栈完毕，检查栈是否为空，如果不为空，则说明还有多余的左括号没有匹配，因此括号
匹配失败，如果为空，则括号匹配成功。

2. 计算机组成原理：简述CPU的主要功能？

1. 指令控制：程序的顺序控制，称为指令控制；
2. 操作控制：CPU管理并产生由内存取出的每条指令的操作信号，把各种操作信号送往响应部件，从而控制这些部件按
指令的要求进行动作；
3. 时间控制：对各种操作实施空间上的控制，称为时间控制；
4. 数据加工：对数据进行算数运算和逻辑运算处理，完成数据的加工处理；

3. 操作系统：内存管理有哪些主要功能？它们的主要任务是什么？

1. 内存分配：为每道程序分配内存空间，提高存储器的利用率；
2. 内存保护：确保每道用户程序都只在自己的内存空间内进行；
3. 地址映射：将逻辑地址转换为内存中的物理地址；
4. 内存扩充：借助虚拟存储技术，从逻辑上去扩充内存容量，让更多的用户程序并发执行；

4. 计算机网络：Internet域名系统的主要用途是什么？它的交互过程由哪三种实体组成？

Internet域名系统就是因特网使用的命名系统，用来把便于人们使用的域名转换为IP地址。
它的交互过程由主机、本地域名服务器和根域名服务器共同完成。

专业面试：什么是机器学习？讲讲你所接触过的一些机器学习算法。你本科学的数学会有哪些会用到机器学习中？

英语面试：When faced with great pressure, what will you do?

第十九天 3.13

专业笔试

1. 数据结构：贪心算法和动态规划以及分治法的区别？

1. 贪心算法：就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，
从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。
2. 动态规划：是把问题分解为子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规
化解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优
的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下往上，一步一步找到全
局最优解。（各子问题重叠）
3. 分治法：将原问题划分成n个规模较小而结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果
，就得到原问题的解。（各子问题独立）

2. 计算机组成原理：在计算机系统结构中，什么是编译？什么是解释？

1. 编译型语言写的程序在执行之前，需要一个专门的编译过程，把程序编译称为机器语言的文件，比如exe文件，如
果源程序不变以后要运行的话就不用重新编译。
2. 解释则不同，解释性语言的程序不需要编译，在程序运行的时候才翻译，翻译一句执行一句，不生成目标程序，这
样解释型语言每执行一次就要翻译一次，效率比较低。

3. 操作系统：简述银行家算法

主要思想是避免系统进入不安全状态，在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有
，则先试行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则拒绝分配上述
，资源。这样就保证系统始终处于安全状态，从而避免死锁现象的发生。

4. 计算机网络：动态路由算法有哪些？

1. 距离-向量算法：如RIP算法
2. 链路状态路由算法：如OSPF算法
3. 自治系统内部所使用的路由选择协议称为内部网关协议IGP
4. 自治系统之间所使用的路由选择协议称为外部网关协议BGP，BGP

专业面试：大数据和机器学习之间有什么联系？

英语面试：Do you think English ability is important in academic research?

第二十天 3.14

专业笔试

1. 数据结构：有哪些哈希函数的构造方法？

1. 直接定址法：H(key) = a * key + b;
2. 除留余数法：H(key) = key % p;
3. 数字分析法：选出分布均匀的几位作为散列的地址
4. 平方取中法：取关键字平方中间几位作为散列地址

2. 计算机组成原理：在计算机中，为什么要使用二进制来表示数据？

1. 从可行性来说，能够表示0、1两种状态的电子元件很多，如电平的高低，使用二进制电子器件具有实现的可行性。
2. 从运算的简易性来说：二进制数的运算简单
3. 从逻辑上来说：二进制的0和1正好和逻辑代数的假和真对应，用二进制表示逻辑很自然。

3. 操作系统：SPOOLing技术的特点？

1. 将独占设备改造为共享设备：为进程在输入井和输出井中为进程分配了一个存储区和建立一张I/O请求表；
2. 提高了I/O速度，缓和了CPU与低速I/O设备不匹配的矛盾；
3. 实现了虚拟设备功能，多个进程同时使用一个独享设备，对每一个进程而言，都认为自己独占这一设备。

4. 计算机网络：为什么要进行流量控制？

限制发送方的发送速率，防止因发送方发送数据过快而接收方接收不过来而产生数据丢弃的现象

专业面试：是否有接触过区块链？谈一谈你对区块链的理解

英语面试：Do you like taking online classes during epidemic time?

Thanks for your question. I like the teaching mode. Online class is very convient. It eliminates the
time and space limitation. Besides, it can also develop the self-learning ability, which is benefit to
the future academic study. Although it is quite different from the traditional teaching mode, I do 
believe it could be resolved in the nearly future.

第二十一天 3.15

专业笔试

1. 数据结构：如何由遍历序列构造一颗二叉树？

1. 由二叉树的先序序列和中序序列可以唯一地确定一颗二叉树
2. 由二叉树的后序序列和中序序列可以唯一地确定一颗二叉树
3. 由二叉树的层序序列和中序序列也可以唯一地确定一颗二叉树

2. 计算机组成原理：向量中断、中断向量、向量地址三个概念是什么关系？

1. 中断向量：每个中断源都有对应的处理程序，这个处理程序称为中断服务程序，其入口地址叫做中断向量
2. 向量地址：中断向量表或中断向量跳转表中每个表项所在的内存地址或表项的索引值称为向量地址，中断向量的地
址
3. 向量中断：指一种识别中断源的技术或方式。为了获得向量地址

3. 操作系统：操作系统的功能？

1. 操作系统是运行在计算机之上的，管理计算机软件和硬件资源的软件系统
2. 为用户使用计算机硬件系统的接口

4. 计算机网络：主机间的通信方式？

1. 客户-服务器（C/S）方式
2. 对等（P2P）方式

专业面试：谈谈你对元宇宙的了解？

英语面试：Do you think it’s useful to plan your time?

Yes. I think its useful to plan my time. If we want to accomplish a big goal, we need to make a long 
term plan, so as to achieve small goals step by step, and finally achieve final success.

---

二、操作系统面试题

1. 什么是操作系统？

操作系统本质上是一个运行在计算机上的软件程序，用于管理计算机的硬件和软件资源；
操作系统屏蔽了硬件层的复杂性。比如操作系统把磁盘抽象成文件，提供了open()、read()、write()等系统调用，  
用户可以通过管理文件的方式来去间接的管理磁盘；

2. 什么是系统调用

首先区分用户态和内核态：
用户态：用户态运行的进程可直接读取用户程序的数据；
内核态：内核态的进程几乎可以访问计算机的任何资源，不受限制；
当用户程序需要使用操作系统内核提供的功能时，需要发出系统调用，向操作系统提出服务请求，并由操作系统代为完成。
这些系统调用按功能大致可分为以下几类：
1. 设备管理。完成设备的请求和释放，以及设备启动等功能；
2. 文件管理。完成文件的读、写、创建及删除等功能；
3. 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能；
4. 进程通信。完成进程之间的消息传递或信号传递等功能；
5. 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能；

3. 进程和线程的区别？

进程：程序的一次执行过程，是一个动态的概念
线程：线程是轻量级的进程
区别：
1. 引入线程前，进程是资源分配和调度的基本单位；引入进程后，进程是资源分配的基本单位，线程是调度的基本单位；
2. 同一进程中的线程共享进程的虚拟地址空间，不同进程中的线程，可以访问的虚拟地址空间一定不同；
3. 线程间切换的开销小于进程间切换的开销；

4. 为什么线程间切换的开销小于进程间切换的开销？

查快表的速度比查普通页表快的多
快表是进程运行过程中动态更新的
每个进程的快表不同，线程共享快表
切换进程后，块表失效，需要重新动态更新，这就是开销的大头

5. 进程间通信方式有哪些

1. 低级通信：信号量通信，使用PV原语，控制任务执行先后顺序
2. 高级通信：数据量较大
    1. 共享内存
    2. 消息队列
    3. 管道：管道通信原则：读写互斥、读完再写、写完再读、两个管道才能全双工通信
3. socket套接字

6. 调度算法有哪些？

1. 先来先服务（FCFS）：非抢占式的调度算法，按照发出请求的顺序进行调度；
2. 短进程优先（SRTN）：可抢占式的调度算法，调度程序总选择剩余运行时间最短的进程运行；
3. 高响应比优先调度算法：能够实现短作业优先+长作业不会饿死；
4. 时间片轮转：假设将时间片设置为1ms，每个进程执行1ms，计时器就会发出时钟中断，如此反复，直到每个进程都执行完毕；
5. 优先级调度：为每个进程设置优先级，优先级高的进程优先获得调度上CPU的机会，分为静态优先级和动态优先级两种；
6. 多级反馈队列调度算法：
    - 设置多个就绪队列：不同队列优先级不同，时间片长短也不同
        - 第一级队列优先级最高，后面的队列优先级降低
        - 第一级队列时间片最短，后面的队列时间片增长

    - 新进程先上第一级队列，如果没执行完，继续上第二级队列执行。如果最后一级队列没有执行完，就按时间片轮转继续执行，直到进程执行完毕！
    - 只有当优先级更高的队列没有进程时，才会转去更低优先级的队列执行，并且，如果有新进程到来，它将进入更高优先级的队列，并抢占CPU。

7. 同步机制应遵循的规则有哪些？

1. 空闲让进：当无进程处理临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源；
2. 忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问；
3. 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态；
4. 让权等待：当进程不能进入自己的临界区时，应立即释放处理及，以免进程陷入“忙等”状态；
其中 1-3 是必须遵守的原则，让权等待不是必须遵守。

8. 什么叫死锁？

一个进程集合里的每个进程都在等待对方手里的资源，就叫死锁

9. 死锁的必要条件有哪些？如果条件不满足，还会产生死锁吗？

1. 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的；
2. 请求和保持条件：已经得到了某个资源的进程可以再请求新的资源；
3. 不可抢占条件：已经分配个某个进程的资源不能强制性被抢占，它只能被占有它的进程显示地释放；
4. 环路等待条件：死锁发生时，系统中一定有两个或两个以上的进程组成一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源；
以上四个条件必须满足，才会产生死锁，只要一个条件被破坏，就不会产生死锁，这也是死锁预防的思路。

10. 处理死锁的方式有哪些？

1. 鸵鸟策略：忽略该问题；
2. 死锁预防：破坏引起死锁的四个必要条件之一，防止死锁的产生；
3. 死锁避免：对资源进行安全分配，动态地避免死锁；
4. 死锁检测并解除：允许死锁的发生，并检测死锁是否发生，一旦死锁，就接触死锁；

11. 死锁预防的方法有哪些？

1. 破坏互斥条件：使用SPOLLING技术；
2. 破坏请求和保持条件：一次性分配给进程所有需要的资源，如果资源不满足，就不分配；
3. 破坏不可抢占条件：将资源变为可抢占，也可以使用SPOLLING技术；
4. 破坏环路等待条件：给资源编号，只允许进程按照升序或者降序申请资源；

12. 什么叫安全状态？什么是安全序列？如何判定系统当前是否处于安全状态？

安全状态是指系统能够按照某种进程顺序（P1, P2, ..., Pn）来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成，称（P1, P2, ..., Pn）为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

13. 系统在不安全状态和死锁的区别？

进入不安全状态，不一定会发生死锁，只有发生死锁的可能；
反之，只要系统处于安全状态，便一定可以避免进入死锁状态。

14. 死锁发生了怎么解除？

1. 系统重启
2. 撤销所有死锁进程
3. 逐一撤销死锁进程
4. 退回检查点

15. 内存管理主要是干什么的？

操作系统的内存管理主要负责内存的分配与回收（malloc函数：申请内存，free函数：释放内存），另外地址转换也就是将逻辑地址转换成相应的物理地址等功能也是操作系统内存管理做的事情。

16. 请求分页管理方式的地址转换过程是怎样的？

逻辑地址->物理地址的核心操作是页号->页框号
逻辑地址：页号 + 页内地址
物理地址：页框号 + 页内地址

与基本分页不同的地方：整个地址转换过程
1. 可能因为状态位为0而需要进行缺页中断处理
2. 可能因为页框满而需要页面置换
3. 页面置换需要涉及到页面置换算法

17. 快表有什么用？

可以加快虚拟地址到物理地址的转换速度。

18. 快表用到了什么原理？

局部性原理，具体来说是应用了时间局部性原理。
将经常访问到的页表项放到了快表里

19. 能具体说说时间局部性吗？除了时间局部性，空间局部性了解吗？

局部性原理是指CPU的访问在一段时间内局限于程序文件的几个部分，可以将其细分为时间局部性和空间局部性
1. 时间局部性：当前指令很可能在接下来继续被CPU访问使用（循环结构）
2. 空间局部性：当前指令临近指令很可能在接下来被CPU访问使用（顺序结构）

20. 操作系统还有什么应用了时间局部性原理的吗？

页面置换算法应用了时间局部性原理
1. 最佳置换算法
2. 先进先出置换算法（贝拉迪异常）
3. 最近最久未使用算法
4. 改进型CLOCK算法

21. Belady异常和操作系统抖动

Belady异常是指分配给进程的页框增多，缺页次数不减反增的现象
抖动是指刚调入的页面马上被调出，刚调出的页面马上又调入

---

三、数据结构面试题

1. 逻辑结构和物理结构的区别

数据的逻辑结构是从具体问题抽象出来的数学模型，与数据的存储无关，是独立于计算机的
数据的物理结构是数据对象在计算机中的存储表示称为数据的存储结构

2. 算法是什么？

算法是解决某类问题而规定的一个有限长的序列
特性有五条：
    1. 有穷性
    2. 确定性
    3. 可行性
    4. 输入
    5. 输出

3. 顺序表和链表的区别？

1. 顺序表需要存放在内存中的连续空间，而链表不需要
2. 顺序表的存储密度高，而链表的存储密度较低（链表需要存放next指针）
3. 顺序表支持随机存储，链表不支持
4. 有序的顺序表支持二分查找，而链表不支持（链表不支持随机存取）

4. 栈是什么，有哪些应用？

栈是只允许在一端（栈顶）进行插入和删除的线性表
栈的特性是后进先出
栈的经典应用：括号匹配、中缀表达式转后缀表达式、后缀表达式计算、实现递归（函数调用）

5. 循环队列有哪些判满的方法？

front：指向队头元素
rear：指向队尾元素的后一个位置
入队：rear = (rear + 1) % MaxSize
出队：front = (front + 1) % MaxSize
队空：front == rear
队满：1. size == MaxSize
      2. (rear + 1) % MaxSize == front

6. 队列有哪些应用？

1. 树的层序遍历
2. 图的广度优先遍历
3. 操作系统中进程调用算法采用先来先服务（FCFS），则不同状态的进程排成一个队列，如就绪队列，阻塞队列等
4. 操作系统中使用SPOOLING技术实现虚拟打印机，提交的任务将排成一个队列

7. 二叉树和树的区别是什么？

1. 二叉树的每个节点至多有两颗子树
2. 二叉树的子树有左右之分，其次序不能任意颠倒

8. 满二叉树是什么？

1. 每层都含有最多的节点
2. 高度为h，总结点数为 2^h-1
3. 若对节点从1开始编号，则编号为i的节点有双亲，双亲的编号为i/2下取整
4. 若有左孩子，则左孩子的编号为2i，若有右孩子，则右孩子的编号为2i+1

9. 完全二叉树是什么？

1. 可以想象为按照从上到下，从左到右的顺序排列节点，但是最后一层没有排满的二叉树
2. 若i <= n/2下取整，则i为分支节点，否则为叶子节点
3. 双亲和左右孩子编号同满二叉树

10. 二叉树有哪些存储方式

1. 顺序存储方式：使用一组地址连续的存储单元来存储数据元素
2. 链式存储结构：在节点中增加指针域，指向左孩子、右孩子（两个指针域）或左孩子、右孩子及父母（三个指针域）

11. 描述下二叉树的遍历过程

先序遍历：
    1. 访问根节点 2. 递归遍历左子树 3. 递归遍历右子树
中序遍历：
    1. 递归遍历左子树 2.访问根节点  3. 递归遍历右子树
后序遍历：
    1. 递归遍历左子树 2.递归遍历右子树  3. 访问根节点
层次遍历：
    按照从上到下、从左到右的次序对二叉树的节点进行访问
    层次遍历可借助队列来模拟实现

12. 为什么要引入线索二叉树？

1. 有些空指针资源没有被利用
2. 可以加快查找节点前驱和后继的速度

13. 中序线索二叉树的前驱与后继怎么查找？

前驱：ltag = 0：左子树中最右下节点
      ltag = 1：p->lchild
后继：rtag = 0：右子树中最左下节点
      rtag = 1：p->rchild

14. 树有哪些存储结构？

1. 孩子兄弟表示法
    每个节点包括三部分：节点值、左指针指向第一个孩子、右指针指向下一个兄弟节点

树和森林都可以通过孩子兄弟表示法转成二叉树

15. 树、二叉树及森林的遍历有什么对应关系？

先根遍历 = 先序遍历 = 先序遍历
后根遍历 = 中序遍历 = 后序遍历

16. 哈夫曼编码是什么？怎么获得哈夫曼编码？

前缀编码：没有一个编码是另一个编码的前缀
由哈夫曼树可以导出哈夫曼编码，它是一种可用于数据压缩的前缀编码，使用哈夫曼编码，可以使数据编码后的  
长度最短。
每次选取频率序列中最小的两个节点，向上构造一个新节点，并把新节点值加入到频率序列中，再重复执行，最  
后就会形成一颗哈夫曼树，规定向左为0，向右为1，则每个节点都有一个唯一的前缀编码

17. 并查集是什么？主要有哪些操作？

并查集是一种维护集合的数据结构
支持的操作：
    1. 合并union()：合并两个集合
    2. 查找find()：判断两个元素是否在一个集合

18. 完全图是什么？

无向完全图：
    有n(n - 1)/2条边的无向图
    即每一个顶点和其他顶点都有边相连的无向图
有向完全图：
     有n(n - 1)条边的有向图
     即每一个顶点到其他所有顶点都有一个“箭头”指向的有向图

19. 连通分量和强连通分量是什么？

连通：
    在 无向图 中，若从顶点v到顶点w有路径存在，则称v和w是连通的
强连通：
    在 有向图 中，如果顶点v到顶点w有路径，w到v也有路径，则称v和w是强联通的
连通图/强连通图：
    在无向图/有向图中， 任何一对顶点 都是联通/强联通的
连通分量/强连通分量：
    无向图/有向图中的 极大连通子图 称为该图的连通分量/强连通分量

20. 介绍图的邻接矩阵和邻接表的存储方式

邻接矩阵是用矩阵来表示顶点之间的连接关系。对于矩阵A，aij就代表顶点vi和顶点vj的连接情况。

邻接表是图的一种链式存储结构。邻接表分为两部分：表头节点表和边表。表头节点表存放各顶点的信息，边表  
存放每个顶点所连接的边的信息。

21. 介绍图的广度优先遍历

思想：一层一层走。它遍历图的方式类似于“水波纹”的扩散。
需要使用队列来实现。

22. 介绍图的深度优先遍历

思想：一次走到底，走不通了才回头找其他路
使用递归实现，底层需要用到栈

23. 图的最小生成树是什么？

带权连通图的最小生成树包含图的所有顶点，并且边的权值之和最小
对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图
若给它增加一条边，则图中会形成一条回路

24. 获取图的最小生成树的算法有哪些？

Prim算法：
    从一个顶点出发，找离这个顶点距离最小的顶点及它的边，把它加到原来的那个顶点形成的集合中，然后再找  
    距离这个集合内顶点距离最短的顶点，把响应的顶点和边再加入进去，如此重复，指导获得一个最小生成树
Kruskal算法：
    首先把每个顶点看成一个集合，按照权值从小到大，每次都选取权值最小的边，如果这条边能连通两个集合，我们就选择这条边，使这两个顶点连通起来，如此重复，直到获得一个最小生成树。

25. 获取图的最短路径的算法有哪些？

Dijkstra算法：解决单源最短路径问题
Floyd算法：解决多源最短路径问题 
    选择距离当前集合最短的一个顶点，加入到集合中，然后看加入了这个顶点后能否更新到其他顶点的  
    最短路径，如此重复

26. 拓扑排序？

拓扑排序是对AOV网顶点进行排序的算法。如果将AOV看作一个活动的执行依赖图，拓扑排序就是对这个图中活动进行  
安排，使得每个事件都能依次运行的一种算法。

27. 关键路径？

关键路径就是AOE网中从源点到汇点的最长路径，它决定了AOE网所代表的工程的完成时间。

28. 二叉排序树是什么？

二叉排序树（二叉查找树）或着是一颗空树，或者是一颗具有下列特性的二叉树：
1. 若左子树非空，则左子树上所有节点的值均小于根节点的值
2. 若右子树非空，则右子树上所有节点的值均大于根节点的值
3. 左右子树分别也是一颗二叉排序树

左子树节点值 < 根节点值 < 右子树节点值，中序遍历得到一个递增的有序序列

29. 平衡二叉树是什么？

平衡二叉树：任意节点的左右子树高度差的绝对值不超过1的二叉排序树
平衡因子：节点左子树与右子树的高度差为该节点的平衡因子
为什么要引入平衡二叉树：因为二叉排序树在极端情况下会退化成一颗单支树，为了优化查询速度

30. 散列表的构造方法有哪些？

1. 直接定址法：H(key) = a * key + b;
2. 除留余数法：H(key) = key % p;
3. 数字分析法：选取分布均匀部分当作散列地址
4. 平方取中法：取关键字的平方值的中间几位作为散列地址

31. 散列表解决冲突的方法有哪些？

1. 开放定址法：指可存放新表项的空闲地址即向它的同义词表开放，有向它的非同义词表开放
    1.1 线性探测法：每次的增量是1
    1.2 二次探测法：增量序列：0^2, 1^2, -1^2, 2^2, -2^2 ... k^2, -k^2
    1.3 双散列法：使用两个散列函数
    1.4 伪随机序列法：增量为随机数

2. 拉链法
    把所有的同义词放在一个线性链表中
    适合经常进行插入和删除的情况

32. 快速排序的思想是什么？

每次选取一个基准值。
以基准值将待排序列划分为两部分，基准值左边都是小于自身的元素，右边都是大于自身的元素。
这样一次划分就确定了基准值最终的位置。
之后再对左右部分递归地执行此过程，直到所有的元素都在最终的位置即可。
时间复杂度：平均：O(nlogn)，最坏：O(n^2)（基本有序）    空间复杂度：递归占用的栈空间

33. 归并排序的思想是什么？

将一个序列从中间分为左右两部分，然后对左右两部分递归地执行该操作，最后每一个部分都是长度为1的序列。
这时候按照有序数组合并的方法，将长度为1的序列按照当初被划分的两两合并成长度为2的序列
然后长度为2的序列再次执行此过程，直到合并为一个完整的有序序列。
时间复杂度：O(nlogn)    空间复杂度：O(n) + 递归占用的栈空间

34. 堆排序的思想是什么？

堆是一种特殊的完全二叉树。分为大根堆和小根堆。以大根堆为例，其每个节点的值都大于自身孩子节点的值。
所以大根堆的堆顶，也就是根，是最大值。

堆排序的思想就是先根据待排序的序列建成一个堆，然后不断地取堆顶元素（头尾交换），也就是取最值，即可完成堆
排序。
但是每次取完最值会破坏堆的完整性，就需要对堆进行调整，使其再次符合堆的特性，以便继续取值，直到排序成功。

35. 冒泡排序的思想是什么？

每趟都从第一个元素开始，和后面的一个元素比较大小。
如果本位置较大，则和后面一个元素交换。
交换之后再和新的后一个元素执行同样的操作。
这样就会将一个最大值“冒泡”到最后。
这个过程执行一趟就会产生一个最小值，我们只要执行n-1趟，就可以将整个序列排序。

36. 稳定的排序算法有哪些？

归并、基数、插入、冒泡

37. 什么是外部排序？

对大文件的排序不能全部在内存中进行，需要将待排序的记录存储在外存，要排序时再把数据一部分一部分地调入内存
进行排序。
排序过程需要多次进行内存和外存之间的交换。
由于访问磁盘的时间远远大于访问内存的时间，所以外部排序的消耗主要来自访问磁盘的时间（一次访问磁盘就产生一
次I/O操作）

38. 排序算法对比

三、计算机网络面试题

1. 什么是计算机网络

是一个将分散的、具有独立功能的计算机系统，通过通信设备与线路连接起来，由功能完善的软件实现资源共享和信息传递的作用

2. 比较OSI参考模型与TCP/IP参考模型的异同点