前言
今天是模拟面试系列第三天，为大家精心准备了 4 道专业课面试题，2 道综合面试题，2 道英语口语题，2 道算法上机题。
涵盖复试中常见的考察点，助你从容应对考官提问！
一、专业面试
1、串的模式匹配算法？KMP 思想？
串的模式匹配算法是指在一个主串（文本串）中查找子串（模式串）出现的位置。
常见的模式匹配算法包括：暴力匹配算法（Brute Force）、KMP 算法、Boyer-Moore 算法和 Rabin-Karp 算法等。
KMP 算法通过预处理模式串，构造一个称为 “前缀函数” 或 next 数组的辅助工具，记录模式串中每个位置的最长相同前缀和后缀长度。当匹配失败时，利用 next 数组快速调整模式串的匹配位置，而无需回退主串指针。这种方法的时间复杂度为 O ( n + m ) O(n+m) O(n+m)，显著优于暴力匹配算法。
2、简述 CPU 的主要功能
CPU 是计算机的核心部件，负责执行指令和处理数据，其主要功能包括从内存中取出指令并解析、控制其他硬件部件协同工作、执行算术和逻辑运算、管理数据在寄存器和内存之间的传输，以及响应外部设备或程序发出的中断请求。
作为计算机的 “大脑”，CPU 通过指令控制、操作控制、数据处理、存储管理和中断处理等功能，协调整个系统的运行，确保计算机能够高效完成各种任务。
3、什么是 ER 图？有哪些部分组成？
ER 图（实体 - 关系图）是一种用于数据库设计的图形化工具，用于描述现实世界中的实体及其相互关系，是构建关系型数据库的基础。
ER 图由实体、属性和关系三部分组成：
- 实体：表示现实世界中的对象或概念（如学生、课程），用矩形表示；
- 属性：描述实体的特性（如学生的学号、姓名），用椭圆表示；
- 关系：表示实体之间的关联（如学生选课），用菱形表示。
此外，主键用于标识实体的唯一性，通常在 ER 图中用下划线标注。通过 ER 图，可以直观地表达数据库的结构，为后续的数据库实现提供清晰的设计蓝图。
4、简述一下模拟退火算法的思想
模拟退火算法是一种基于物理退火过程的随机优化算法，用于解决复杂的组合优化问题。
其核心思想是模拟金属冷却过程中原子逐渐趋于稳定状态的过程：初始温度较高时允许接受较差解，随着温度降低逐渐收敛到最优解。
在算法中，当前解的基础上生成新解，并计算目标函数值的变化。如果新解更优，则直接接受；如果新解较差，则以一定概率接受，该概率随温度降低而减小。通过逐步降温，算法能够在搜索空间中跳出局部最优，最终找到近似全局最优解。
尽管模拟退火算法的收敛速度较慢，且对参数选择较为敏感，但其能够在复杂优化问题中有效避免陷入局部最优，具有较强的通用性和实用性。
5、你想出去找实习，但实验室不允许，你会怎么做？
首先，我会理解实验室的立场和要求。实验室可能出于科研任务的需要，希望我能够专注于当前的研究工作，这对我来说也是一种成长机会。
因此，我会先评估自己的科研任务进度，确保自己对实验室的工作负责到底。如果实习对我未来的职业发展确实非常重要，我会尝试与导师进行坦诚沟通。在沟通中，我会表达对实验室工作的重视，同时说明实习对我个人能力提升和职业规划的意义，并提出一个折中的解决方案。
例如，我可以承诺在完成关键科研任务后再开始实习，或者选择时间较为灵活的实习岗位，尽量减少对实验室工作的影响。
最重要的是，我会以积极的态度面对这个问题，在尊重导师和实验室规则的前提下，寻找双方都能接受的平衡点。
6、如果和导师发生矛盾该如何解决？
如果我和老师发生矛盾，我会首先冷静下来，避免情绪化反应。矛盾通常源于沟通不畅或对某些问题的理解存在偏差，因此我会从以下几个方面着手解决：
（1）自我反思 ：我会先审视自己的行为和态度，看看是否存在误解或不足之处。如果是我的问题，我会主动承认错误并向老师道歉。
（2）坦诚沟通 ：我会选择一个合适的时机，与老师进行面对面的沟通。在沟通中，我会以尊重和谦虚的态度表达自己的观点，同时认真倾听老师的建议和想法，努力找到问题的根源。
（3）寻求解决方案 ：在明确问题后，我会和老师一起探讨如何解决问题，尽量提出具体的改进措施。例如，如果是因为科研任务分配不均导致的矛盾，我可以主动承担更多责任；如果是因为学术意见分歧，我会尝试通过查阅文献或咨询其他专家来达成共识。
总之，我认为师生关系是建立在相互信任和合作的基础上的，任何矛盾都可以通过理性沟通和共同努力来化解。我会始终以学习和成长为目标，尊重老师的指导，同时不断提升自己的能力。"
二、英文口语
1、Tell me about a time when you faced a difficult challenge. How did you overcome it?
跟我讲讲你经历过的一次艰难挑战吧。你是如何克服它的呢？
During a group project, we faced a tight deadline and conflicting ideas. I took the lead by organizing tasks, encouraging open communication, and focusing on teamwork. We successfully completed the project on time and received positive feedback.
在一次小组项目中，我们面临紧迫的截止日期和意见分歧。我通过组织任务、鼓励开放沟通和注重团队合作来解决问题。最终我们按时完成了项目，并获得了积极的反馈。
2、Why do you want to pursue further studies in computer science?
你为什么想要在计算机科学领域继续深造呢？
I want to pursue further studies in computer science because I am passionate about solving complex problems through technology and innovation. I believe a deeper understanding of advanced concepts will allow me to contribute meaningfully to fields like artificial intelligence and data science, which have the potential to transform industries and improve lives.
我希望继续攻读计算机科学，因为我热衷于通过技术和创新解决复杂问题。我相信对高级概念的深入理解将使我能够在人工智能和数据科学等领域做出有意义的贡献，这些领域有潜力改变行业并改善生活。
三、算法上机
1、寻找数组中第 K 大的元素
代码实现
#include <bits/stdc++.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
// 快排思想
int getKth(int nums[], int low, int high, int k) {
if (low > high)
return -1;
int x = nums[low]; // 枢纽值
int L = low, H = high;
// 从大到小排序
while (low < high) {
while (low < high && nums[high] <= x) // 改为 <=
high--;
nums[low] = nums[high];
while (low < high && nums[low] >= x) // 改为 >=
low++;
nums[high] = nums[low];
}
nums[low] = x;
if (low == k - 1)
return nums[low]; // 找到第K大的元素
else if (low > k - 1)
return getKth(nums, L, low-1, k); // 在左半部分继续查找
else
return getKth(nums, low+1, H, k); // 在右半部分继续查找
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
int nums[n];
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
int ret = getKth(nums, 0, n-1, k);
printf("%d", ret);
return 0;
}
2、正整数的第 K 位
编写函数 Digit(int n, int k)，函数返回值是正整数 n 的左边起第 k 位数，若位数不够则返回 -1。
例如：Digit(31415926, 6) = 9， Digit(3141, 5) = -1。
代码实现
#include <bits/stdc++.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int Digit(int n, int k) {
int cnt = 0;
int num = n;
// 统计 n 的位数
while (num != 0) {
cnt++;
num /= 10;
}
// 若位数不够则返回 -1
if ((cnt - k) < 0)
return -1;
for (int i = 0; i < cnt - k; i++)
n /= 10;
return n % 10;
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
int ret = Digit(n, k);
printf("%d", ret);
return 0;
}