哈工深（CS）

欢迎参加2024年哈尔滨工业大学（深圳）计算机科学与技术学院2024年推免生（含直博生）复试！本次复试将于9月8日（周五）在深圳校区线下举行，请提前做好出行计划。复试分为机试和面试两个环节，后续活动安排将通过钉钉告知，请添加钉钉好友。

一、材料准备

请携带提交PDF材料时的原件作为备查，内容见下：

（1）居民身份证；

（2）本科学生证原件；

（3）个人简历

（4）所在院（系）或学校教务处盖章的截至报名时的成绩单或成绩排名；

（5）所在院（系）或学校教务处盖章的成绩排名证明；

（6）英语四、六级原件或托福、雅思成绩单等外语能力水平证明原件；

（7）学术成果发表情况（已发表论文，其中代表性论文1篇，应提供全文，其他已发表论文提供期刊目录、论文首页复印件；若未正式发表，附录用通知证明；若无则可不提交）；

（8）其他证明材料（本科期间各类获奖证书等）。

二、机试

机试将于9月8日（周五）9：30-11：10线上进行，主要考核范围包括C语言程序设计、数据库系统、数据结构、离散数学、计算机网络、操作系统等专业知识点。考试时长100分钟，满分150分。有选择题和判断题两种题型，考试地点考前告知。

三、面试

面试将于9月8日（周五）下午开始，综合考察考生基本素质、综合分析与语言表达能力、综合运用知识解决问题的能力、创新能力。分为自我介绍（准备PPT，5分钟）、专业测试（5分钟）和专家问答（5-10分钟）三个环节，考核时长不超过20分钟/人，满分100分。直博生在PPT个人自述中需要准备读博期间设想等。

注意事项

如确定参加我院预推免请及时添加钉钉；如不能按时参加，请回复“姓名+学校+不参加哈工大深圳预推免”，并简述原因。请在9月3日17:00前确认是否参加。

如部分原件无法在审核阶段提供，请提前联系学院说明具体原因并在核验时告知工作人员，并在规定时间内提交，否则将视为审查不合格，失去拟录取资格。

《哈尔滨工业大学（深圳）计算机科学与技术学院2024年推免生（含直博生）接收工作细则》已经在学院官网首页-招生栏目公示，请各位仔细查看：http://cs.hitsz.edu.cn/info/1029/6813.htm

请各位同学在复试期间全天保持通讯畅通。

哈尔滨工业大学（深圳）
计算机科学与技术学院

专业课

C语言程序设计

JVM 是 Java 虚拟机（Java Virtual Machine）的缩写，它是Java编程语言的核心组成部分之一。JVM的主要作用是执行Java字节码（Bytecode），这是一种中间代码，由Java编译器生成，而不是直接执行原生机器代码。以下是JVM的一些关键特点和功能：

跨平台性：JVM使得Java具有跨平台性，因为它可以在不同操作系统上运行，只要针对相应平台的JVM可用。这意味着开发人员可以编写一次Java代码，然后在多个平台上运行，而不需要重新编写代码。
字节码解释和编译：JVM可以解释执行Java字节码，也可以将字节码即时编译为本地机器代码，以提高执行速度。
内存管理：JVM负责Java程序的内存管理，包括自动内存分配和垃圾回收。这有助于开发人员避免内存泄漏和手动内存管理的复杂性。
安全性：JVM提供了一定程度的安全性，通过安全管理器和类加载器来控制Java程序的访问权限，以防止恶意代码执行。
类加载和动态类生成：JVM负责将Java类加载到内存中，并支持动态生成和加载类。这使得Java程序可以在运行时创建新的类和对象。
多线程支持：JVM支持多线程编程，开发人员可以创建并发程序，充分利用多核处理器和多线程执行。

总之，JVM是Java语言的关键组件，它提供了一个虚拟的执行环境，使得Java程序可以在不同的平台上运行，并提供了许多高级特性，如内存管理、安全性和多线程支持，以帮助开发人员编写强大、安全、跨平台的应用程序。

先来看看编译型语言定义：
编译型语言首先是将源代码编译生成机器指令，再由机器运行机器码(二进制)。也就是在运行之前，代码已经被翻译位机器码了。

再来看看解释型语言的定义：
解释型语言的源代码不是直接翻译成机器指令，而是先翻译成中间代码，再由解释器对中间代码进行解释运行。也就是到机器码需要两个步骤，运行前先到中间码，运行时再编译成机器码。

再来看看脚本型语言的定义：
脚本语言又被称为扩建的语言，或者动态语言，用来控制软件应用程序，脚本通常以文本保存，只在被调用时进行解释。也就是处于软件的运行阶段，不参与编译，动态的解释并运行。

数据库系统

数据库三级模式：外模式、模式和内模式

模式又称概念模式或逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。

理解： ① 一个数据库只有一个模式； ② 是数据库数据在逻辑级上的视图； ③ 数据库模式以某一种数据模型为基础； ④ 定义模式时不仅要定义数据的逻辑结构（如数据记录由哪些数据项构成，数据项的名字、类型、取值范围等），而且要定义与数据有关的安全性、完整性要求，定义这些数据之间的联系。

外模式定义：也称子模式（Subschema）或用户模式，是数据库用户（包括应用程序员和最终用户）能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。

理解： ① 一个数据库可以有多个外模式； ② 外模式就是用户视图； ③ 外模式是保证数据安全性的一个有力措施。

内模式定义：也称存储模式（Storage Schema），它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式（例如，记录的存储方式是顺序存储、按照B树结构存储还是按hash方法存储；索引按照什么方式组织；数据是否压缩存储，是否加密；数据的存储记录结构有何规定）。

理解： ① 一个数据库只有一个内模式； ② 一个表可能由多个文件组成，如：数据文件、索引文件。它是数据库管理系统(DBMS)对数据库中数据进行有效组织和管理的方法其目的有： ① 为了减少数据冗余，实现数据共享； ② 为了提高存取效率，改善性能。

在数据库的三级模式结构中，描述数据库中全体数据的全局逻辑结构和特征的是（）。

A. 外模式 B. 内模式 C. 存储模式 D. 模式

作为关系数据系统，最小应具备的关系运算是 选择、投影、连接 。

在where语句的条件表达式中，与零个或多个字符匹配的通配符是（）。

A. * B. ? C. % D. _

从数据流图构造E-R图时，选择实体一般应先考虑数据流图中的（）。

A. 数据项 B. 数据流 C. 数据处理 D. 数据存储

什么是数据（data）和数据库（database）?

数据是数据库中存储的基本对象，数据库是长期存储在计算机内、有组织、可共享的大量数据集合。

DBMS对数据的控制功能主要体现在

数据安全性保护
数据完整性检查
数据库故障恢复
并发控制

数据库系统的核心是数据库管理系统DBMS

DBMS中实现事务持久性的是恢复管理子系统

应用数据库的主要目的是为了共享数据

数据库管理员DBA 的职责是

数据库管理员DBA的职责是完整性约束说明和数据库安全

决定数据库中的信息内容和结构
决定数据库的存储结构和存取策略
定义数据的安全性要求和完整性约束条件
监控数据库的使用和运行
数据库的改进和重组、重构

https://blog.csdn.net/weixin_42888110/article/details/122841612

常用的数据模型（逻辑模型）：

层次模型：用树型结构表示实体类型及实体间联系。
网状模型：允许一个以上的结点无双亲；一个结点可以有多于一个的双亲；用图结构表示实体类型及实体间联系。
关系模型：以二维表格结构来表示实体类型及实体间联系

数据模型应包括哪三个部分？试分别解释之。

数据模型包含数据结构，数据操纵，数据的完整性约束条件三个部分。

数据结构：描述数据库的组成对象以及对象之间的联系。
数据操作：是指对数据库中的各种对象（型）的实例（值）允许执行的操作的集合·，包括操作及有关的操作规则。
数据的完整性约束条件是一组完整性规则。

数据库系统结构为三级模式两级映像结构，对保证数据的独立性起到至关重要的作用。

数据库系统可以概括为三级模式和二级映像，三级模式分别为外模式、模式和内模式，二级映像为外模式/模式映像和模式/内模式映像。模式是数据库整体逻辑结构的描述，一个数据库对应一个模式；外模式是数据库与外部应用程序对应的局部逻辑描述，一个数据库可以有多个外模式；内模式是数据库内部与存储及物理环境相关的逻辑描述，一个数据库对应一个内模式

数据库的独立性分为物理独立性和逻辑独立性。逻辑独立性是指外部的应用程序不会因为数据库逻辑结构的改变而改变，是由外模式/模式映像支持的；物理独立性是指外部应用程序不必因为数据库内部存储结构的改变而改变，是由模式/内模式映像所支持。

E-R图提供了表示实体型、属性和联系的方法

实体型用矩形表示
属性用椭圆形表示
联系用菱形表示

存取控制

常用的存取控制方法：索引、hash、聚簇

存取控制：自主存取控制（DAC），强制存取控制（MAC）

实现强制存取控制时要首先实现自主存取控制

用户权限是由两个要素组成的：数据库对象和操作类型

SQL中的视图是由基本表或视图产生的虚表，其结构和数据是建立在对表的查询的基础上的。

数据库中实际存放的是视图的定义

视图上不能定义新的表

基本表有对应的物理存储，视图没有对应的物理存储

第一范式1NF：所有属性不可再分，即数据项不可分

第二范式2NF：消除关系模式中非主属性对码的部分函数依赖

第三范式3NF：在2NF基础上，消除关系模式中非主属性对码的传递函数依赖

BC范式BCNF：在3NF基础上，消除关系模式中主属性对码的部分依赖和传递依赖。

第四范式4NF：限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。

什么是事务（Transaction），事务和程序的区别？

事务是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。

事务的特性（ACID）：

原子性 A：事务是数据库逻辑工作单位，事务中包括的诸操作要么都做，要么都不做（最根本）
**一致性 C：**事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态
**隔离性 I：**一个事务的执行不能被其他事务干扰，即一个事务内部操作及使用的数据对其他并发事务是隔离的
持久性 D：一个事务一旦提交，它对数据库中的数据的改变就应该是永久的
数据库故障可分为
- 事务故障：算数溢出、死锁等
- 介质故障：由于磁盘损坏或外存信息丢失所产生的故障
- 系统故障：是指造成系统停止运转的任何事件，使得系统要重新启动(会造成内存数据丢失)
数据库并发操作通常会带来的问题
- 丢失修改
- 不可重复读
- 读“脏”数据
锁是什么？

事务是并发控制的基本单位，锁是实现事务的关键，锁可以保证事务的完整性和并发性。

视图建立后，在数据字典中存放的是（）。

A. 查询语句 B. 视图的定义 C. 组成视图的表内容 D. 产生视图的表定义

由全码组成的关系模式，最高可以达到的模式为（）。

A. 4NF B. 2NF C. 3NF D. BCNF

BCNF是3NF的改进形式

一个满足BCNF的关系模式的条件:

1.所有非主属性对每一个码都是完全函数依赖。

2.所有的主属性对每一个不包含它的码,也是完全函数依赖。

3.没有任何属性完全函数依赖于非码的任何一组属性。

1NF:列不可分

2NF：消除部分依赖

3NF：消除传递依赖

在合并E-R图时需解决的属性冲突包括属性（域）冲突和属性取值单位冲突。

事务遵守（两段锁协议）是可串行化调度的充分条件。

两段锁协议（考）：
是指所有事务必须分两个阶段对数据项加锁和解锁:

    1)在对任何数据进行速、写操作之前，事务首先要申请并获得对该数据的封锁，
    2)在释放一个封锁之后，事务不再获得任何其他封锁。
    “两段”锁的含义事务分为两个阶段:

    第一阶段是获得封锁，也称为扩展阶段：

    在这阶段，事务可以申请获得任何数据项上的任何类型的锁，但不能释放任何锁， 

     第二阶段是释放封锁，也称为收缩阶段。

    在这阶段，事务可以释放任何数据项上的任何类型的锁，但不能再申请任何锁

事务对数据库数据进行更新操作时，必须首先获得对该数据集合的（排他）锁。

（系统故障）是指造成系统停止运转的任何事件，使得系统要重新启动。

应用数据库的主要目的是为了（共享）。

模式：数据的逻辑结构和关系的描述
内模式：数据物理接哦古和储蓄方式的描述
外模式：子模式或者用户模式，是用户可预见的局部数据的逻辑结构和特征的描述，是模式的逻辑子集

数据抽象的内容是（）。

A. 选择、投影、连接 B. 分类、概括、聚集

C. 调查、分析、设计 D. 超类、子类、消息

数据结构

哈希表（Hash Table），也称为散列表，是一种数据结构，用于存储键-值对（key-value pairs）。哈希表通过将键映射到一个固定大小的数组索引来实现高效的数据检索和插入操作。

哈希表的基本原理包括以下几个关键概念：

哈希函数（Hash Function）：哈希表使用哈希函数将键转换为数组索引。这个函数接受一个键作为输入，并返回一个与该键相关的索引。理想情况下，哈希函数应该将键均匀地映射到数组中的位置。
数组（Array）：哈希表内部维护一个固定大小的数组，通常称为哈希表的桶（buckets）或槽（slots）。
冲突处理（Collision Resolution）：由于哈希函数的限制，不同的键可能映射到相同的数组索引，导致冲突。哈希表必须具备解决冲突的机制，常见的方法包括链式哈希和开放地址法。
检索和插入：要在哈希表中检索值，首先使用哈希函数计算键的索引，然后在该索引处查找值。要插入值，同样需要计算索引，然后将键值对存储在索引处。

哈希表的主要优点是其快速的检索性能。因为哈希函数通常能够在常数时间内计算索引，所以在理想情况下，检索操作的时间复杂度是O(1)。然而，冲突处理可能会影响性能，因此哈希函数的设计和冲突解决策略的选择非常重要。

哈希表在计算机科学中广泛应用，例如在编程语言中的关联数组、数据库索引、缓存实现等领域。它提供了一种高效的方法来存储和检索大量数据。

含n个叶结点的哈夫曼树，其总结点个数为 2n-1

具有5个记录的序列，采用直接选择排序方法进行排序，需要进行的比较次数是（ A ）。
A.10

广义表A=（a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值是（ C ）

A.（g)
B.(d)
C.d
D.c

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( 33 )。在线性表的链式存储结构中，能从当前结点出发访问任一点的存储结构是（ D ）。

A.单链表
B.双向链表
C.循环链表
D.B和C

下列关于无向连通图特性的叙述中，正确的是
Ⅰ.所有顶点的度之和为偶数
Ⅱ.边数大于顶点个数
Ⅲ.至少有一个顶点的度为1
只有Ⅰ
只有Ⅱ
Ⅰ和Ⅱ
Ⅰ和Ⅲ

下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。

A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆

排序二叉树的左边<中间<右边

中序遍历二叉树可以得到一个有序序列。

对于n个结点的二叉树，其高度为不确定。（如果是完全二叉树，则是[log2n]+1）

如果有n个结点用二叉树来存储，那么二叉树的最小深度为：log2(n+1).

一颗有124个叶子结点的完全二叉树，最多有248个结点。

分析：设第7层叶子结点x个，第6层叶子结点y个，则

x/2+y=64

x+y=124

解得x=120,y=4 。则总的结点个数为120+27 -1=247。

下面是重点，为什么最多的话是可以加一的：然后在第6层最后四个叶子结点中的第一叶子结点下加一个结点，不但不影响叶子结点个数，也使得总结点数多一，为248。

https://blog.csdn.net/wangdd_199326/article/details/73733142

N个顶点的连通图用邻接矩阵表示时，该矩阵至少有___2(n-1)___个非零元素。

19、文件系统采用索引结构是为了节省存储空间。（　　）

20、倒排文件的目的是为了多关键字查找。（　　）

21、二维以上的数组其实是一种特殊的广义表。（　　）

22、稀疏矩阵压缩存储后，必会失去随机存取功能。（　　）

23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（　　）

24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（　　）

25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（　　）

26、归并排序辅助存储为O（1）。（　　）

27、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。

（　　）

28、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（　　）

19、【答案】×

20、【答案】√

21、【答案】√

22、【答案】√

23、【答案】√

24、【答案】√

25、【答案】×

26、【答案】×

27、【答案】√

28、【答案】×

离散数学

假设集合A，以及基于A上的关系R

自反：如果a是A的元素，那么<a,a>是R的元素
反自反：如果a是A的元素，那么<a,a>不是R的元素
对称：如果<a,b>是R的元素，那么<b,a>是R的元素
反对称：如果<a,b>，<b,a>是R的元素，那么a,b相等
传递：如果<a,b>，<b,c>是R的元素，那么<a,c>是R的元素
PS：

互斥：R中只有r1和r2，r1是R的元素，则r2不是R的元素。

1.自反性：

关系图，每个顶点都有环，则矩阵中表示(a, a)[即：有从该点自身到自身的有向边]

关系矩阵，n阶矩阵，主对角线元素全为1.

2.对称性：

关系图：如果两个顶点之间有边，则一定是一对方向相反的边

（注意：这是蕴含式，如果前件不成立，两点之间连边都没有，同样满足对称性）

关系矩阵：存在关系（a,b）且存在关系（b,a）,即：矩阵为对称矩阵

3.传递性：

关系图：如果顶点a到b有边，b到c有边，则a到c有边

（同样注意：蕴含式，如果前件不成立，即不满足"a到b有边，且b到c有边"，也满足传递性）

关系矩阵：如果存在关系（a,b）且（b,c）,则存在关系（a,c）

若集合A的元素个数为10，则其幂集的元素个数（ 1024 ）

设A={a,b,c},B={1,2},作f:A→B,则不同的函数个数为

f(a)值有2种选法
f(b)值有2种选法
f©值有2种选法
所以f(a),f(b),f©有2³=8种取值排列
一个排列就对应一个函数
所以8个

若P，Q，为二命题，P—>Q 真值为F当且仅当_____ P真Q假 _____ 。

2、设X={1,2,3,4}，R={<1,2>,<2,4>,< 3,3>},则
r( R )={<1,1>,<1,2>,<2,2>,<2,4>,< 3,3>,<4,4>} _
s( R )={<1,2>,<2,1>,<2,4>,< 3,3>,<4,2>}___
t( R )= {<1,2>,<1,4>,<2,4>,< 3,3>} ____

r( R )表示自反闭包
s( R )表示对称闭包
t( R )表示传递闭包
n阶无向完全图每个结点v的度数d(v) = n-1_

欧拉路径：图 G 上有一条经过所有顶点、所有边的简单路径（边不重复，点可以重复）

欧拉回路：图 G上有一条经过所有顶点、所有边的简单回路（边不重复，点可以重复）

欧拉图：有欧拉回路的连通无向图

欧拉有向图：有欧拉回路的连通有向图

设 G 是连通无向图。G 是欧拉图，当且仅当 G 的结点都为偶结点。

设G=（a）是15阶循环群，（1）求G的所有生成元（2）求出G的所有子群

设G=是15阶循环群,
则G={a,a^2,…,a^14,a^15=1}.
其中凡是与15互素的i,
a^i都是G的生成元.
因此:
(1)
G的所有生成元为a,
a^2,
a^4,
a^7,
a^8,
a^11,
a^13,
a^14.
(2)
G的所有子群为
15阶 =G;
5阶子群<a^3>={a^3,a^6,a^9,a^12,a^15=1};
3阶子群<a^5>={a^5,a^10,a^15=1};
单位子群1.
其中5阶子群和3阶子群是非平凡子群,
15阶的和1阶的(单位子群)是平凡子群.

可结合是指一个运算满足结合律：(A*B)*C=A*(B*C)

计算机网络

ARP（Address Resolution Protocol），地址解析协议，是根据IP地址获取物理地址的一个TCP/IP协议。

与10.110.12.29 mask 255.255.255.224 属于同一网段的主机IP 地址是（）

A、10.110.12.0 B、10.110.12.30

C、10.110.12.31 D、10.110.12.32

10.110.12.29 = 00001010 . 01101110 . 00001100 . 00011101

255.255.255.224 = 11111111 . 11111111 . 11111111 . 11100000 mask

10.110.12.0 = 00001010 . 01101110 . 00001100 . 00000000（后五位全0）

10.110.12.30 = 00001010 . 01101110 . 00001100 . 00011110

10.110.12.31 = 00001010 . 01101110 . 00001100 . 00011111（后五位全1）

10.110.12.32 = 00001010 . 01101110 . 00001100 . 00100000（不在同一网段）

224.0.0.0–224.0.0.255组播地址

路由选择协议位于（）。

A、物理层 B、数据链路层 C、网络层 D、应用层

路由选择协议是计算机网络中的一种协议，用于决定数据包在网络中的传输路径。它是为了实现数据包从源节点到目的节点的有效传输而设计的。

在互联网中，有几种常见的路由选择协议，包括：

链路状态路由选择协议（Link State Routing Protocol）：这种协议基于网络中每个节点的拓扑信息，通过交换链路状态信息来计算最短路径。其中最著名的是OSPF（Open Shortest Path First）协议。

距离向量路由选择协议（Distance Vector Routing Protocol）：这种协议基于每个节点对其邻居节点的距离估计，通过交换距离向量信息来选择路径。其中最著名的是RIP（Routing Information Protocol）协议。

路径向量路由选择协议（Path Vector Routing Protocol）：这种协议在距离向量协议的基础上增加了路径信息，以避免出现环路和避免特定的路由问题。BGP（Border Gateway Protocol）是最常见的路径向量协议，用于互联网中的自治系统之间的路由选择。

这些协议使用不同的算法和策略来选择最佳路径，以提高网络的性能、可靠性和可扩展性。它们在网络中起着至关重要的作用，确保数据包能够快速、准确地到达目的地。

MAC（介质访问控制）指的是数据链路层中的一个子层。它主要负责控制多个设备在共享的物理介质上进行数据传输的访问权限。为什么称之为介质访问控制子层呢？这是因为MAC子层的主要功能是管理和控制设备对物理介质的访问。

传输层：报文段或用户数据报

网络层：数据报

数据链路层：帧

物理层：比特

DHCP是（ Dynamic Host Configuration Protocol ）英语单词的缩写。

以下关于ICMP协议的说法中，正确的是（）。

A．由MAC地址求对应的IP地址
B．在公网IP地址与私网IP地址之间进行转换
C．向源主机发送传输错误报告
D．向主机分配动态IP地址

a是ARP协议

b是NAT

d是DHCP

操作系统

https://blog.csdn.net/qq_44005101/article/details/125208902

LRU（Least Recently Used）算法是一种用于管理缓存的策略，它的目标是在有限的缓存空间内保留最近最常使用的数据，而淘汰最不常使用的数据。LRU算法基于时间局部性的原理，认为最近被访问的数据有更高的概率在未来被再次访问。

LRU算法的基本思想是维护一个数据结构（通常使用双向链表或有序字典），其中存储了缓存中的数据项，并按照它们的访问时间顺序排列。具体操作如下：

当数据被访问时，如果数据已经在缓存中，将该数据项移到链表头部（或有序字典的最前面），表示它是最近使用的数据。
当需要将新数据添加到缓存中时，如果缓存未满，直接将新数据插入到链表头部（或有序字典的最前面）。如果缓存已满，需要淘汰链表尾部（或有序字典的最后面）的数据，因为它们是最近最少使用的数据。

这样，LRU算法保持了缓存中数据项的有序性，最近使用的数据位于链表头部，最不常使用的数据位于链表尾部。当缓存满时，淘汰链表尾部的数据项，从而为新数据腾出空间。

LRU算法的优点是它可以在常数时间内完成数据的插入、查找和删除操作。但它也有缺点，即需要维护一个额外的数据结构来记录数据的访问顺序，且在某些场景下可能会导致性能问题，因为每次访问都需要更新数据结构。

总的来说，LRU算法是一种经典的缓存替换策略，通常用于数据库管理系统、文件系统缓存、Web服务器和各种应用中，以提高数据访问的效率。

如果分时操作系统的时间片一定，那么（），则响应时间越长。
用户数越少
用户数越多
内存越小
内存越大

链接：https://www.nowcoder.com/questionTerminal/6d49a315f0f84a6db0ee2a1f82685f65
来源：牛客网

首先要理解分时操作系统时间片是一个什么样的概念。其实对于cpu而言，每次只能允许一个作业在其上运行。什么多道程序设计以及并发的执行，这些其本质都是：宏观上并行，微观上串行。对于分时操作系统而言，假设有3个作业需要用的cpu。那么出现一种约定，三个作业分别在cpu上执行10ms。A-B-C-A…此顺序执行，指导执行完毕。对于A-B-C-A,不难发现当A再次执行需要等20ms。当作业数目较多时比如：A-B-C-D-E-F-H-A,那么再次执行A，时间等待将更多。因为结论：用户越多，时间越多

下列各项工作步骤中，()不是创建进程所必需的步骤。
建立一个PCB
作业调度程序为进程分配CPU
为进程分配内存等资源
将PCB链入进程就绪队列

创建进程步骤：
1,申请空白PCB（进程控制块）；
2,为新进程分派资源；
3,初始化PCB；
4,将新进程插入就绪队列；

进程申请CPU得不到满足时，其状态变为就绪状态

若系统中只有用户级线程，则处理机调度单位是()。
线程
进程
程序
作业

如果系统只有用户态线程，则线程对操作系统是不可见的，操作系统只能调度进程；

如果系统中有内核态线程，则操作系统可以按线程进行调度；

一个进程是( )。

A.由协处理机执行的一个程序

B.一个独立的程序+数据集

C.PCB结构与程序和数据的组合

D.一个独立的程序

所谓进程，是指一个程序在一个数据集上的一次运行，所以一个程序在不同数据集合上运行，乃至一个程序在同样数据集合上的多次运行都是不同的进程。

一个进程包括控制结构和执行结构；控制结构是进程控制块PCB，执行结构包括程序以及需要操纵的数据集合。

计算机操作系统之进程控制块PCB
1.进程控制块的作用
进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。PCB中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息。进程控制块的作用，是使一个在多道程序环境下不能独立进行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。或者说，操作系统是根据PCB来对并发执行的进程进行控制和管理。
2.进程控制块中的内容
在进程控制块中，主要包括4个方面内容。
（1）进程标识符信息。进程标识符用于惟一地标识一个进程。一个进程，通常有以下两个标识符：外部标识符，内部标识符。
（2）处理机状态信息。处理机状态信息主要是由处理机各种寄存器中的内容所组成。
（3）进程一调度信息。在PCB中还存放了一些与进程调度和进程对换有关的信息，包括：进程状态、进程优先级、进程调度所需要的其他信息、事件。
（4）进程控制信息。进程控制信息包括：程序和数据的地址、进程同步和通信机制、资源清单、链接指针。
3.PCB的组织方式
在一个系统中，通常可拥有数十个、数百个乃至数千个PCB，为能对它们进行有效管理，应该用适当的方式将它们组织起来，目前，常见的组织方式有两种，链接方式和索引方式。

在下面的叙述中正确的是( )。

A.线程是比进程更小的能独立运行的基本单位

B.引入线程可提高程序并发执行的程度，可进一步提高系统效率

C.线程的引入增加了程序执行时时空开销

D.一个进程一定包含多个线程

选B，A线程不能独立运行，线程需要进程所获得的资源。
C引入线程机制降低了时空的开销。
D一个进程至少包含一个主线程（线程数量大于等于1）。

线程是独立调度的基本单位，进程是拥有资源的基本单位。

下面关于线程的叙述中，正确的是( )。

A.不论是系统支持线程还是用户级线程，其切换都需要内核的支持

B.线程是资源的分配单位，进程是调度和分配的单位

C.不管系统中是否有线程，进程都是拥有资源的独立单位

D.在引入线程的系统中，进程仍是资源分配和调度分派的基本单位

临界资源是互斥共享资源

为了实现银行家算法，在系统中必须设置这样四个数据结构：

1）Available向量：系统中可利用的资源数目

2）Max矩阵：每个进程对每种资源的最大需求

3）Allocation矩阵：每个进程已分配的各类资源的数目

4）Need矩阵：每个进程还需要的各类资源数

其中三个矩阵间存在下述关系：

Need[i,j] = Max[i,j] - allocation[i, j]

下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。

A.非强占式静态优先权法

B.强占式静态优先权法

C.时间片轮转调度算法

D.非强占式动态优先权法

在下列选项中，属于预防死锁的方法是（）。

A.剥夺资源法 B.资源分配图简化法

C.资源随意分配 D.银行家算法

链接：https://www.nowcoder.com/questionTerminal/b8ade2458fe94e59827f8adbf58efe2c
来源：牛客网

预防死锁。
这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。

避免死锁。
该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

检测死锁。
这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。

解除死锁。
这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

银行家算法是用来避免死锁的,该方法将系统的状态分为安全和不安全,只要系统处于安全状态,便可避免死锁的发生。

死锁预防：静态分配策略、层次分配策略、剥夺调度

死锁避免：银行家算法

死锁检测：进程-资源分配图
死锁恢复：结束进程并重启系统、撤销进程、剥夺资源

死锁的条件：

互斥
请求和保持
不可剥夺
循环等待

作业从后备作业到被调度程序选中的时间称为（）。

A.周转时间 B.响应时间

C.等待调度时间 D.运行时间

分页存储管理的存储保护是通过（）完成的。

A.页表（页表寄存器） B.快表

C.存储键 D.索引动态重定

即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护

存储管理方法中，（）用户可采用覆盖技术。

A.单一连续区 B.可变分区存储管理

C.段式存储管理 D.段页式存储管理

段的逻辑地址形式是段号10位，段内地址20位，内存1MB，辅存10GB。那么虚拟存储器最大实际容量可能是（）。

A.1024KB B.1024MB C.10GB D.10GB+1MB

虚拟存储器最大实际容量= min(计算机地址，内存+辅存)。计算机地址= 2^ 10* 2^20=1024M

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!

LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!

链接：https://www.nowcoder.com/questionTerminal/362aebddf7c74088851a6853b4c429b0
来源：牛客网

页表项（页描述子）中各个位的作用：

页号
块号（页框号）
中断位：用于判断该页是不是在内存中，如果是0，表示该页面不在内存中，会引起一个缺页中断
保护位（存取控制位）：用于指出该页允许什么类型的访问，如果用一位来标识的话：1表示只读，0表示读写
修改位（脏位）：用于页面的换出，如果某个页面被修改过（即为脏），在淘汰该页时，必须将其写回磁盘，反之，可以直接丢弃该页
访问位：不论是读还是写（get or set），系统都会设置该页的访问位，它的值用来帮助操作系统在发生缺页中断时选择要被淘汰的页，即用于页面置换
高速缓存禁止位（辅存地址位）：对于那些映射到设备寄存器而不是常规内存的页面有用，假设操作系统正在循环等待某个I/O设备对其指令进行响应，保证硬件不断的从设备中读取数据而不是访问一个旧的高速缓存中的副本是非常重要的。即用于页面调入。

虚拟存储有3个最主要的特征：

多次性：是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
对换性（交换性）：是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。
虚拟性：是指从逻辑上扩充内存的容量，使用户所看到的的内存容量，远大于实际的内存容量。

最重要的性质是多次性。

采用（）不会产生内部碎片。

A.分页式存储管理 B.分段式存储管理

C.固定分区式存储管理 D.段页式存储管理

在内存管理中，内部碎片是已经被分配出去的内存空间大于请求的内存空间。外部碎片是指还没有分配出去，但是由于太小而无法分配给申请空间的新进程的内存空间空闲块。固定分区存在内存碎片，可变式分区会存在外部碎片；页式虚拟存储系统存在内部碎片；段式虚拟存储系统存在外部碎片；为了有效利用内存，使内存产生更少的碎片，要对内存进行分页，内存以页为单位，最后一页往往装不满，于是形成了内部碎片。为了共享要分段，在段的换入换出时形成外部碎片；

在内存管理中，内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。外部碎片是指还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。

段式存储管理会出现外部碎片。

ICMP（Internet Control Message Protocol）Internet控制报文协议。它是TCP/IP协议簇的一个子协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用

并行技术是多处理器(CPU)或多处机并行处理任务的技术，为了解决复杂的计算问题，提高计算速度，一般采用这种技术。如现在我们所称的多核技术、众核技术、大规模并行机等等。
通道技术是一种任务(分区或进程)之间通信的一种技术。
缓冲技术也称Spooling技术，Spooling的意思是外部设备同时联机操作，又称为假脱机输入/输出操作，是操作系统中采用的一项将独占设备改造成共享设备的技术。Spooling系统的组成包括三部分：输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程。为了解决CPU输出数据的速度远远高于打印机的打印速度这一矛盾，在操作系统中一般采用Spooling技术。
虚存(VM)技术能从逻辑上对内存进行扩充，达到扩充内存的效果，具有请求调入和置换功能。

优先数越小，优先级越大

一旦出现死锁，所有进程都不能运行. （）0

进程状态的转换是由操作系统完成的，对用户是透明的. （）1

由于现代操作系统提供了程序共享的功能，所以要求被共享的程序必须是可再入程序. （）1

执行系统调用时可以被中断. （）1

清内存指令只能在管态下执行. （）1

对文件进行读写前，要先打开文件. （）1

参与死锁的所有进程都占有资源. （）0

优先数是进程调度的重要依据，优先数大的进程首先被调度运行：（）0

引入缓冲的主要目的是提高I/0设备的利用率. （）0

参与死锁的进程至少有两个已经占有资源. （）1

多线程和多进程是两种并发执行的方式，它们有以下区别：

进程 vs. 线程：
- 进程（Process）是操作系统中的一个独立执行单元，拥有独立的内存空间和系统资源。每个进程都有自己的地址空间，数据不能直接共享。
- 线程（Thread）是进程内的一个执行单元，共享相同的内存空间和系统资源。线程之间可以更方便地共享数据。
创建与销毁开销：
- 创建和销毁进程通常比线程消耗更多的系统资源，因为进程需要独立的内存空间和系统表格。
- 线程的创建和销毁通常比进程轻量级，因为它们共享进程的资源。
通信：
- 进程之间的通信需要使用特殊的机制，如进程间通信（IPC），如管道、消息队列、套接字等。
- 线程之间可以直接共享相同进程的内存，因此通信更加容易。
并发性：
- 多进程可以在多个 CPU 上并发执行，因此适用于多核处理器。
- 多线程通常在单个进程中并发执行，因此适用于任务间需要共享数据的情况。
故障隔离：
- 进程之间更具有独立性，一个进程的崩溃不会影响其他进程。
- 线程共享相同的内存，一个线程的错误可能导致整个进程的崩溃。

杂

设计模式是一种在软件设计中常用的通用解决方案，它提供了一套经过验证的方法和最佳实践，用于解决特定类型的问题或优化软件设计。设计模式有助于提高代码的可维护性、可扩展性和可重用性，并促进团队之间的共享理解。

以下是一些常见的设计模式：

创建型模式：
- 工厂模式（Factory Pattern）：用于创建对象，将对象的创建逻辑与使用逻辑分离。
- 单例模式（Singleton Pattern）：确保一个类只有一个实例，并提供全局访问点。
- 建造者模式（Builder Pattern）：用于构建复杂对象，将构建过程与表示分离。
结构型模式：
- 适配器模式（Adapter Pattern）：允许接口不兼容的类能够一起工作。
- 装饰器模式（Decorator Pattern）：用于动态地添加或修改对象的行为。
- 组合模式（Composite Pattern）：将对象组合成树状结构以表示“部分-整体”层次结构。
行为型模式：
- 观察者模式（Observer Pattern）：定义了对象之间的一对多依赖关系，当一个对象状态发生改变时，其依赖对象会收到通知并自动更新。
- 策略模式（Strategy Pattern）：定义一系列算法，将它们封装成可互换的对象，客户端可以动态地选择使用哪个算法。
- 命令模式（Command Pattern）：将请求封装成对象，从而允许将请求参数化、队列化、分发和执行。
其他模式：
- MVC（Model-View-Controller）模式：用于构建用户界面应用程序，将应用程序分成三个部分：模型、视图和控制器。
- 享元模式（Flyweight Pattern）：用于共享大量细粒度的对象，以减少内存和提高性能。

每种设计模式都有其自身的适用场景和优缺点。选择正确的设计模式取决于问题的性质和需求。设计模式并不是一种强制性的规范，但它们提供了一些常见的模板和指导，有助于构建更健壮、可维护和可扩展的软件。

实习

导师&方向

聂礼强

方向：数据挖掘，信息检索，CV

实际情况：

聂老师组都是ap邵睿在带

组很大，貌似50+学生，10个左右的老师

现在在做多模态的大模型

邵老师像学长一样，很热情亲切。

资源够，但是人多肯定卷是不可避免的。其他不清楚。

数据挖掘

zhihu

数据挖掘(Data Mining)就是从大量的数据中，提取隐藏在其中的，事先不知道的、但潜在有用的信息的过程。数据挖掘的目标是建立一个决策模型，根据过去的行动数据来预测未来的行为。

数据挖掘利用了来自如下一些领域的思想：(1)来自统计学的抽样、估计和假设检验；(2)人工智能、模式识别和机器学习的搜索算法建模技术和学习理论。

数据挖掘也迅速地接纳了来自其他领域的思想，这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。

KDD(Knowledge Discovery from Database)

数据清理
消除噪声和不一致的数据；

数据集成
多种数据源可以组合在一起；

数据选择
从数据库中提取与分析任务相关的数据；

数据变换
通过汇总或聚集操作，把数据变换和统一成适合挖掘的形式；

数据挖掘
基本步骤，使用智能方法提取数据模式；

模式评估
根据某种兴趣度，识别代表知识的真正有趣的模式；

知识表示
使用可视化和知识表示技术，向用户提供挖掘的知识。

数据挖掘方法论

业务理解（business understanding）
从商业角度理解项目的目标和要求，接着把这些理解知识通过理论分析转化为数据挖掘可操作的问题，制定实现目标的初步规划；
数据理解（data understanding）
数据理解阶段开始于原始数据的收集，然后是熟悉数据、甄别数据质量问题、探索对数据的初步理解、发觉令人感兴趣的子集以形成对探索信息的假设；
数据准备（data preparation）
数据准备阶段指从最初原始数据中未加工的数据构造数据挖掘所需信息的活动。数据准备任务可能被实施多次，而且没有任何规定的顺序。这些任务的主要目的是从源系统根据维度分析的要求，获取所需要的信息，需要对数据进行转换、清洗、构造、整合等数据预处理工作；
建模（modeling）
在此阶段，主要是选择和应用各种建模技术。同时对它们的参数进行调优，以达到最优值。通常对同一个数据挖掘问题类型，会有多种建模技术。一些技术对数据形式有特殊的要求，常常需要重新返回到数据准备阶段；
模型评估（evaluation）
在模型部署发布前，需要从技术层面判断模型效果和检查建立模型的各个步骤，以及根据商业目标评估模型在实际商业场景中的实用性。此阶段关键目的是判断是否存在一些重要的商业问题仍未得到充分考虑；
模型部署（deployment）
模型完成后，由模型使用者（客户）根据当时背景和目标完成情况，封装满足业务系统使用需求。

数据挖掘任务

通常，数据挖掘任务分为下面两大类。

预测任务。这些任务的目标是根据其他属性的值，预测特定属性的值。被预测的属性一般称目标变量(targetvariable)或因变量(dependentvariable), 而用来做预测的属性称说明变量(explanatoryvariable)或自变量(independentvariable)。
描述任务。其目标是导出概括数据中潜在联系的模式（相关、趋势、聚类、轨迹和异常）。本质上，描述性数据挖掘任务通常是探查性的，并且常常需要后处理技术验证和解释结果。

信息检索

机试&面试

【机考系统使用说明】
1、准备开考：检查机器是否能正常开机，是否可以打开网页，接着用火狐或chrome浏览器，登陆网址检查是否可以正确打开并看到注册界面
2、9：00准时开考，到时间后仍然无法看到试卷则需要刷新页面
3、开考后进行注册，一定要输入正确的信息，统一用“手机号+姓名”
4、每人只有一次提交机会，一旦提交试卷就无法更改，所以一定要仔细检查
5、如果答题期间，界面死机，不要换机器，直接在当前机器上刷新网页即可其他注意事项请看下面使用说明，明天有问题及时联系考场老师。

【9月8日机考通知】
各位同学，2024年推免生机考将于9月8日上午9：00-10：40进行，本次设置T2-102、T2-210两个考场，具体安排见下图（这里本组负责人告诉本组考生面试地点，宇轩@王宇轩注意你们组同学拆开了，通知时候注意下）
注意事项：
1.本人携带校园卡/学生证/身份证，提前15分钟到指定教室，进入考场后先在讲台处签到，出示学生证/身份证核查，并领取草稿纸，迟到将被取消机考资格。
2.本人只允许携带校园卡/学生证/身份证、黑色签字笔进入座位，其余物品放在讲台前。考试结束后将草稿纸交还到讲台前。
3.考试时长100分钟，满分150分，及格线70分。

要求不算很高

考了很多集合的知识，数据层物理层的知识

图论+集合论+计算机网络（计算题）+操作系统（计算题）+mysql（特定是mysql，我们当时学的是sqlsever很多语法略有出入）+各种树（计算题）+排序的稳定性

detail：

完美匹配

子群

半群

载波监听

页段计算

哈夫曼编码频率

先序后序遍历

生成树

排序第n次结果

磁盘读写

数据库授权语法

寻道时间

多少个叶子多少节点

森林里面几棵树

死锁检测判断

信道利用率

范式

缺页次数

c语言几乎没考

达不到70就直接被刷了，满分150。感觉比南大题目丰富点。

没有汇编，编译。

【9月8日面试安排通知】
各位同学，本次推免面试为9月8日14：00-18：00，本组考生考场为XXX，具体事项如下：
1.每人面试时间约15分钟，流程为：自我介绍（5分钟，准备PPT）—现场抽算法题（5分钟口头简述）—专家问答（5分钟）。
2.面试14：00开始，请每组考生至少提前20分钟到场，到教室拷贝PPT。
3.拷贝好PPT后进入候考室H308签到等候，面试开始后会有引导员及时提醒各考场面试进度。
4.面试前考生须将手机等全部无关物品上交至候考室指定位置，只带本人身份证/学生证进入面试教室。面试结束后返回候考室取回，不得交头接耳，尽快离场。

抽到的算法题如上

hard模式

瞎答一通

问了时间复杂度啥的

这种没刷过最多回答个搜素算法或者dp

问了一些心理有关的问题和家庭状况

以后想做什么，有什么规划

反复在问我有没有报其他的夏令营，手上有多少个offer

结果我真被问穿了

P.S. 机试还真有被刷掉的，实惨，当时还在刮台风

我前面第二个学生就被刷了，导致我更快被面试。

力扣hard模式我是真的没有想到，有点碰运气了。

没有英文面试

个人感觉纯海王营

全程就提供了1~2瓶矿泉水+1张草稿纸

成本可以说是无限低了

真跟夏令营天差地别。

当旅游了反正。

后记：

差不多过了四五天拿到了哈工深第一批的offer

老师的offer很早就release了，但是学校的一直保留到929

最后填系统的时候，教务处果然也发得很快12：20（12：00开系统）左右就拿到了复试消息，但是拒绝给后面的人了。

哈工深cs预推免