专业课

数据结构与算法

数据结构

数据结构	时间复杂度	空间复杂度	功能及特点
数组	访问： $O(1)$ ；插入/删除： $O(n)$	$O(n)$	连续存储相同类型元素，支持随机访问，插入/删除需移动元素。
链表	访问： $O(n)$ ；插入/删除： $O(1)$	$O(n)$	动态存储元素，通过指针连接，插入/删除效率高，不支持随机访问。
栈	入栈/出栈： $O(1)$	$O(n)$	后进先出（LIFO）结构，支持push/pop/peek操作，常用于递归、表达式求值。
队列	入队/出队： $O(1)$	$O(n)$	先进先出（FIFO）结构，支持enqueue/dequeue操作，常用于任务调度、BFS。
哈希表	插入/查找/删除： $O(1)$ ，最坏 $O(n)$	$O(n)$	通过哈希函数映射键值对，冲突处理方式有链地址法、开放寻址法。
二叉搜索树	插入/查找/删除： $O(\log n)$ ，最坏 $O(n)$	$O(n)$	左子树节点值 < 根节点值 < 右子树节点值，支持高效排序和搜索。
堆	插入/删除： $O(\log n)$ ；获取最值： $O(1)$	$O(n)$	完全二叉树，分为最大堆/最小堆，常用于优先队列、Top-K问题。
并查集	合并/查询：近似 $O(1)$	$O(n)$	支持快速合并和查询集合操作，用于处理不相交集合的合并与查询问题（如连通性）。

排序

排序算法	时间复杂度	稳定性
冒泡排序	$O(n^2)$	稳定
选择排序	$O(n^2)$	不稳定
插入排序	$O(n^2)$	稳定
希尔排序	$O(n^{1.3})$	不稳定
归并排序	$O(n\log n)$	稳定
快速排序	$O(n\log n)（平均）$	不稳定
堆排序	$O(n\log n)$	不稳定
桶排序	$O(n+a_{max})$	稳定
基数排序	$O(n*k)$	稳定

归并排序

MergeSort is a typical application of Divide and Conquer. It is an effective algorithm with a n logn time complexity and it is stable but not in place. Merge sort is a good choice for external sort. The basic step of the algorithm is to merge the ordered subsequences into a complete ordered sequence.If two ordered subsequences are merged into one, it is called two-way merge.

中文翻译

归并排序（MergeSort）是分治法（Divide and Conquer）的经典应用案例。作为一种高效的排序算法，它的时间复杂度为 nlogn，不仅具备稳定性 —— 即相等元素的相对顺序在排序后保持不变，同时它并非原地排序算法，在执行过程中需要额外的存储空间。

快速排序

Quicksort is an unstable sorting algorithm. it is still a commonly used algorithm for sorting. Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively.

中文翻译

快速排序是一种不稳定排序算法，至今仍是常用的排序算法之一。它是一种分治算法，其工作原理是从数组中选择一个 “基准” 元素，然后将其他元素划分到两个子数组中，划分依据是这些元素小于还是大于基准元素。因此，它有时也被称为分区交换排序。随后，子数组会被递归地排序。

Q: 寻找序列中的第k大值

算法	时间复杂度	实现过程
排序后取第k个元素	$O(n\log n)$	1. 对数组进行全排序（如快速排序、归并排序） 2. 直接取排序后数组的第 $k$ 大元素
快速排序	$O(n)$	1. 基于快速排序的分治思想，选择一个基准元素 2. 将数组分为「大于基准」「等于基准」「小于基准」三部分3. 根据k与基准位置的关系，递归处理对应子数组4. 当基准位置等于目标位置时返回结果
堆排序	$O(n\log k)$	1. 维护一个大小为k的小顶堆 2. 遍历数组，若元素大于堆顶则入堆，否则跳过 3. 堆满时弹出堆顶（保证堆中是当前最大的k个元素）4. 遍历结束后，堆顶即为第k大元素

字符串

字符串配对：哈希 Hash

核心思想：通过哈希函数将字符串映射为固定长度的哈希值，利用哈希值快速判断两个字符串是否相等。
实现过程：
1. 预计算目标字符串的哈希值（通常结合前缀哈希和滚动哈希，如BKDRHash、SHA等）。
2. 对需匹配的字符串计算哈希值，与目标哈希值比对。
3. 若哈希值相同，可进一步验证原字符串（避免哈希冲突），从而实现 $O(1)$ 级别的快速配对。
适用场景：字符串查重、字典匹配、缓存键值映射等。
具体实现

字符串前缀匹配：KMP算法

核心思想：通过预处理模式串生成「部分匹配表（next数组）」，避免主串与模式串匹配失败时的重复比较，优化时间复杂度。
实现过程：
1. 构建next数组：记录模式串中每个位置的最长相同前缀后缀长度。
2. 主串与模式串匹配：当字符不匹配时，根据next数组将模式串回退至合适位置，而非从头开始。
3. 重复匹配直至找到所有匹配位置或遍历结束，整体时间复杂度为 $O(n+m)$ （ $n$ 为主串长度， $m$ 为模式串长度）。
适用场景：文本搜索、关键词匹配、DNA序列比对等。
具体实现

最长回文子串：马拉车Manacher

核心思想：通过预处理（插入特殊字符统一奇偶数长度回文）和维护「中心扩展边界」，高效寻找最长回文子串，避免重复计算。
实现过程：
1. 预处理字符串：在每个字符间插入特殊符号（如#），将偶数长度回文转为奇数长度处理。
2. 维护数组p：记录每个位置为中心的最长回文半径，同时跟踪当前回文的中心C和右边界R。
3. 遍历字符串时，利用对称性质（若当前位置在R内，可通过C的对称点快速获取p的初始值），减少扩展次数，整体时间复杂度为 $O(n)$ （ $n$ 为原字符串长度）。
适用场景：最长回文子串查找、回文相关的字符串问题优化。
具体实现

操作系统

Q: 进程和线程的区别

根本区别：进程是资源分配最小单位，线程是程序执行的最小单位。
地址空间：进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段；线程没有独立的地址空间，同一进程的线程共享本进程的地址空间。
资源拥有：进程之间的资源是独立的；同一进程内的线程共享本进程的资源。
执行过程：每个独立的进程有一个程序运行的入口、顺序执行序列和程序入口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。线程是处理机调度的基本单位，但是进程不是。由于程序执行的过程其实是执行具体的线程，那么处理机处理的也是程序相应的线程，所以处理机调度的基本单位是线程。
系统开销 ：进程执行开销大，线程执行开销小

数据库

英语

个人经历

自我介绍

Dear teachers, good afternoon!

My name is Hekaiyu, and I am studying at the University of Science and Technology Beijing, majoring in Artificial Intelligence.

During my undergraduate study, I studied hard, with a weighted score of 93.549, ranking first in my major, and won many scholarships, such as the National Scholarship.

As for my research experience, I’ve participated in a project about the large language model. We used the logit lens to observe the semantic pivots during the model’s inference process.

I also took part in International Collegiate Programming Contest and won the bronze medal. In the process of competing and training, my algorithmic capability has been greatly improved.

If I am lucky enough to be admitted, I will work hard and actively participate in the academic research of the tutor’s team.

This is my introduction. Thank you for listening.

中文翻译

尊敬的各位老师，下午好！

我叫何开煜，就读于北京科技大学人工智能专业。

本科期间，我学习勤奋，加权成绩为 93.549 分 ,排名专业第一，还获得了多项奖学金，包括国家奖学金等。

在科研经历方面，我参与了一个大型语言模型项目。我们利用 Logit Lens 技术观察模型推理过程中的语义枢轴。

我还参加了国际大学生程序设计竞赛，并获得了铜牌。在竞赛和训练过程中，我的算法能力得到了显著提升。

如果我有幸被录取，能够跟着各位老师学习，我定会刻苦努力，积极参与导师的团队进行学术研究。

以上是我的个人简介，感谢各位老师的聆听。

研究生期间的计划

In the first stage of research, I study professional courses hard and earnestly, read a lot of literature, and continue to enrich myself. I think these can help me understand the development of this field more comprehensively, and it can also make me enter the status of a graduate student faster. The second stage of research is to complete the related topics assigned by the instructor. In the third stage of research, take the initiative to complete the topics that interest me, and prepare for my further studies in the future.

中文翻译

在研究的第一阶段，我努力认真地学习专业课程，阅读了大量文献，不断充实自己。我觉得这些可以帮助我更全面地了解这个领域的发展，也可以让我更快地进入研究生的状态。第二阶段的研究是完成教师分配的相关主题。在研究的第三阶段，主动完成我感兴趣的主题，为我未来的进一步学习做准备。

介绍研究项目

For my research experience, I’ve participated in a project about the interpretability of large language models.

First, to quantify the cross-lingual ability of LLMs accurately, we propose a Word-Level Cross-Lingual Translation Task and evaluate it on LLMs.

To find how LLMs learn cross-lingual ability, used the logit lens to observe the output of the model’s intermediate layers and summarize the model’s inference into two behaviors. In addition, we discover the semantic pivots from the model’s inference process and try to find them from the pretraining dataset.

Finally, we reconstruct a semantic pivot-aware pre-training dataset using documents with a high proportion of semantic pivots to improve the cross-lingual ability of models.

中文翻译

在科研方面，我参加了一个关于大型语言模型可解释性的项目。

首先，为了准确量化 LLM 的跨语言能力，我们提出了一个词级跨语言翻译任务，并在 LLM 上进行评估。

为了找出 LLM 如何学习跨语言能力，使用 logit 镜头观察模型中间层的输出，并将模型的推理总结为两种行为。此外，我们从模型的推理过程中发现语义枢轴，并尝试从预训练数据集中找到它们。

最后，我们使用语义轴比例高的文档重建了一个语义轴感知的预训练数据集，以提高模型的跨语言能力。

生活类

介绍一下你的本科学校

The University of Science and Technology Beijing, founded in 1952, is a top Double First-Class and 211 university in Haidian, Beijing. It excels in science, engineering, with strong research in metallurgy and materials. It’s among the first in China with an AI major. At USTB, not only can I feel the strong academic atmosphere, but also get along with more brilliant teachers and classmates.

中文翻译

北京科技大学 1952 年建校，是北京海淀区的顶尖双一流和 211 高校。在理工领域表现卓越，冶金和材料学科研究实力雄厚。其是全国首批建设人工智能专业的大学之一。在北京科技大学，我不仅可以感受到浓厚的学术氛围，还可以与更多才华横溢的老师和同学独处。

介绍家乡

My hometown is Fuding, a charming county-level city in Fujian Province. Known as the “Hometown of White Tea”, it boasts a long history of tea cultivation. Beyond tea, Fuding is also blessed with scenic spots, such as Mount Taimu. All in all, Fuding is a remarkable place to visit and live in.

中文翻译

我的家乡是福鼎，它是位于福建省的县级市。福鼎被誉为 “白茶之乡”，拥有悠久的种茶历史。除了茶叶，福鼎还坐拥众多风景名胜，比如太姥山。总而言之，福鼎是一个非常值得游览和居住的好地方。

爱好

In my spare time, I enjoy doing sports. My favorite sport is table tennis. It requires both skill and strategy. It’s great for hand-eye coordination, improves agility and reaction speed, and provides me a good health. What’s more, it is really an effective way of decompression for me. When I play table tennis, I immerse myself in it and have a good mood.

中文翻译

在业余时间，我喜欢做运动。我最喜欢的运动是乒乓球。它需要技巧和策略。它非常适合手眼协调，提高敏捷性和反应速度，并提供良好的心血管锻炼，而不会对关节造成过度压力。更重要的是，这对我来说真的是一种有效的解压方式。当我打乒乓球时，我会沉浸其中，心情愉悦。

你认为你本科学习中最重要的一门课是什么，为什么？

My favorite course is the algorithm and analysis. It requires us to solve complex problems using algorithms with lower time complexity. Through this course, my thinking ability and coding skills have been significantly improved. It provided a solid foundation for my future practical applications in the computer science field.

中文翻译

我最喜欢的课程是算法和分析。它要求我们使用时间复杂度较低的算法来解决复杂的问题。通过这门课程，我的思维能力和编码技能得到了显着提高。它为我未来在计算机科学领域的实际应用奠定了坚实的基础。