Simpread 2022 南大 cs 夏令营笔试面试准备

本文由简悦 SimpRead 转码，原文地址 zhuanlan.zhihu.com

碎碎念：为了准备南大的笔试面试，之前在网上翻了很多经验贴，受益颇多，许愿如果上岸一定要把自己归纳整理的资料拿出来共享，现在来还愿了，希望能有帮助。

以下是根据 21 年笔试题准备的复习材料，不普遍适用于 22 年（22 年题更多面更广，但感觉重点类似，比如数据结构的各种排序肯定要弄熟）。uu 们可以当做一个测试题，仅供参考。

开放日笔试¶

题型¶

两个小时，两百多道选择题？（记不清了反正挺多的）个人建议是不用着急全部写完，也不要过于纠结某一道题，尽可能拿分才是上策。

内容¶

笔试内容为 408（好像还带点离散之类的数学问题），但不是传统意义上的 408，操作系统考题偏向 linux 应用，跟我学的不太一样，建议看南大 jyy 老师的网课（虽然我没来得及看）。每个人的题不一样，各种课程方向的占比也不一样，我很幸运是作为我复习的最少的地计网，我抽到的题中占比也是比较少的，数据结构占大头。

题目¶

以下是我翻了去年南大出的题 + 自己认为可能会考的考点，不清楚正确答案，仅供参考

1.1 计算机网络¶

发 qq 邮件用的协议是什么？
传统 IP 地址有 ABC 三类，下面属于 B 类的形式的是? 【考察 IP 地址含义】

TCP 连接中，A 发送给 B 大小分别为 300、500 字节的数据包，已知 A 的发送序号为 200，问：B 接受两个数据包后，要通知 A 已经收到，该信息的序号? 【答：1000】
CIDR: 无类别域间路由选择

IP 地址 ::= {<网络前缀>， < 主机号 >} / 网络前缀所占位数

e.g. 128.14.35.7/20

【答：D】

数据报校验的协议位于的层次?
拥堵窗口【C】

以太网，传输速率 100Mbps，信号传播速度 200000km/s，如果最小数据帧的长度增大 90bits，则 1. 电缆的最大长度能够增加多少？2. 信道利用率是上升还是下降？
（最小帧长 / 数据传输速率）* 信号传播速度 = 2 * 最大传输距离；即此处电缆的最大长度能够增加 90km；
帧长变大，a 变小，信道利用率上升。

以太网速度快的原因

串行通信简单，非常适合长距离传输。

串行通信由于控制简单、抗干扰能力强、成本低等特点，得到了广泛的应用。

1.2 数据结构¶

m 叉树，度为 Ni 的结点有 i 个 (i=1,2,…m)，问度为 0 的结点有多少个？

度：某个节点的子节点个数，那么度为 0 的结点即叶子结点

n 个元素的散列表查找的复杂度是多少？（理想情况）

【复杂度为 O(1)】数组支持按照下标随机访问，同哈希表一样

p.s. 如果是在哈希表中查找：哈希表是通过计算元素的哈希值来定位元素位置的，只需计算一次即可，其时间复杂度为 O(1)。因此，与元素数量 n 无关。

选择小于散列表长度的最大素数

入栈顺序为：1 2 3 4 … n；出栈顺序为：p1 p2 p3 p4 … pn，如果 p1=n，则 pi=？【C】

A.i B.n-i C．n-i+1 D. 不确定

根据栈的运算原理，n 必定是最后入栈的，输入顺序必定是 1，2，3，...，n，则出栈的序列是 n，n-1，n-2，...，1

二叉树有 n 个结点，查找一个元素最坏的复杂度？【B】

A.O(log(n)) B.O(n) C.O(n^2) D.O(1)

p.s.

如果题目是二叉排序树（可能题目有误）, 则;

只是说二叉排序树不一定是二叉平衡树，如果所有的元素有序排列，正好成一根深度为 n 的树，此时最差的时间复杂度就是从根节点到最后一个叶子节点为 n。如果是平衡树，则时间复杂度为 O(log(n))。

N 个结点的二叉搜索树，高度是 [log2(N)]+1。[] 表示取整。

如下：

只有 1 个根节点的二叉搜索树，高度为 1。log2(1)=0,0+1=1;

2，3 个结点的二叉搜索树，高度为 2。log2(2)=1，1+1=2；

4，5，6，7 个结点的二叉搜索树，高度为 3。log2(7) < 3，log2(7) 取整 + 1 为 3。

邻接矩阵

【C】

AOV 中求解拓扑排序，分为 abc 三个步骤。a. 把_为 0 结点都入栈 b. 如果栈非空， pop 栈顶元素 Vj，查看它的直接后继 Vk，删除 Vk 的出边，然后重新统计_为 0 的结点，继续入栈 c. 如果栈为空… 【入度 / 前驱结点】

AOV(Activity on Vertex) 网：在一个表示工程的有向图中，用顶点表示活动，用有向弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，简称 AOV 网。 [有向无环图]

基本思想：

（1）从 AOV 网中选择一个没有前驱的结点并输出。

（2）从 AOV 网中删去该结点，并且删去该结点连接的弧。

（3）重复上述操作，直至所有结点全部被输出，或 AOV 网中不再存在没有前驱的结点。

希尔排序，增量依次为 3，2，1，问前两次排完后的结果?

对于每一轮所取得增量，我们可以使用如下的规则（这也是希尔排序的创造者希尔本人所建议的）：

第一轮的增量为数列的长度 / 2.

第二轮的增量为第一轮的增量 / 2.

第三轮的增量为第二轮的增量 / 2.

归并排序

核心思想：分治

给定一张图，通过某种遍历方法，得到一个生成树，问采用了哪种遍历方法？

广度遍历、深度遍历…

1.3 计算机组成¶

流水线结构中，branch 指令发生跳转，需要插入多少个空操作（bubble）或者阻塞多少个周期？
交通卡上显示余额 42949672.76 元，显示错误，问实际最有可能是多少？【-0.2 元】

卡内余额是一个 int 型整数，4 字节，32 比特，即 2^32 = 4294967296。

若以无符号数考虑，其值为 0 ~ 4294967296，余额范围 0 ~ 42949672.96。

若以有符号数考虑，其值为 - 2147483648 ~ 2147483648。

最小单位考虑到分，则有符号数表示余额范围：-21474836.48 ~ 21474836.48。

4294967276 = 0xFFFF FFEC，因为负数在存储时采用补码形式，恢复其原码：

0xEC = 0b1110 1100，首先减 1 = 0b1110 1011，然后取反 = 0b0001 0100 = 20（十进制），符号位还是 1，表示负数。

所以应是 - 20，然后还要考虑元角分，因此是 - 0.2 元。

CPU 访问内存，以下哪种不可能发生？记得 cd 选项为：

c，TLP 命中，但发生缺页； d，cache 没有命中，但没有发生缺页

【C】快表命中，页肯定命中，不可能发生缺页。

主存地址线 32 位，按字节编址。cache 块大小 64Byte，cache 的数据容量是 64Kbyte，cache 采用写回，cache 和主存采取直接映射，问 cache 容量多大？
指令取到指令寄存器开始后，POP X2; DIV X2,X1; AND X1,X2; MOV X1 0(X2)，这四种哪一个不会发生异常？
execve 函数

1.4 操作系统¶

主要考 linux 的系统调用，命令什么的

哪个 C 函数不需要经过系统调用【time】

printf

time

strptime

malloc

内核态用户态
特权指令：只能由操作系统内核部分使用，不允许用户直接使用的指令。【如，进程管理（可软中断）I/O 指令、置终端屏蔽 jincluding 指令、清内存、建存储保护、设置时钟指令（这几种记好，属于内核态）。
非特权指令：所有程序均可直接使用。
x86-64 架构中，32 位虚拟地址空间，4kB 页面大小，采用的页表级数是几？【两级页表】

32 的逻辑地址，分成两部分。前部分是代表虚拟的页号，后部分代表的是虚拟页偏移量。如果页面是 4KB 的话，那么这个后部分虚拟页偏移量占了 12 位，(1kB 是 2^10 次方 = 1024，4kB 是 2^12 次方) 那么前面就是 32-12=20 位。这 20 位就是页表中所有的页表项的和。

页表项是不可分割的，20 ÷ 12 = 1 余 8，采用两级页表合适。

p.s.

页表大小为 1MB（ 2^32 / 2¹²⁼²20）

如果每个页表项占 4B 的话。那么这个页表就占了 4MB 的空间

整数除零后会发送什么信号？有选项是：SIGILL、SIGFPE

除以零产生异常信号【SIGFPE】

（p.s.

SIGBUS / SIGEMT/ SIGIOT 指示一个实现定义的硬件故障, 非法地址，包括内存地址对齐出错。

SIGFPE(floating-point exception)，此信号表示一个算术运算异常，例如除以 0，浮点溢出等。

SIGILL(illegal instruction), 此信号指示进程已执行一条非法硬件指令。

SIGHUP：hang up 挂断

SIGTRAP：由断点指令或其他 trap 指令产生。

SIGPIPE：管道破裂。

SIGSEGV：试图访问未分配给自己的内存, 或试图往没有写权限的内存地址写数据.。

SIGPROF 当 setitimer(2) 函数设置的梗概统计间隔时间已经超过时产生此信号

SIGQUIT 当用户在终端上按退出键（一般采用 Ctrl - \）时，产生此信号，并送至前台进程组中的所有进程（见图 9 - 8）。此信号不仅终止前台进程组（如 SIGINT 所做的那样），同时产生一个 core 文件。

SIGINFO 这是一种 4 . 3 + BSD 信号，当用户按状态键（一般采用 Ctrl - T）时，终端驱动程序产生此信号并送至前台进程组中的每一个进程。此信号通常造成在终端上显示前台进程组中各进程的状态信息。

SIGINT 当用户按中断键（一般采用 DELETE 或 Ctrl - C）时，终端驱动程序产生此信号并送至前台进程组中的每一个进程。当一个进程在运行时失控，特别是它正在屏幕上产生大量不需要的输出时，常用此信号终止它。

Linux…ELF 在 gdb 执行 start 后，第一条指令位于？有选项是：ELF 指向的入口地址

【开始调试, 停在 main 函数第一行语句前面等待命令】

(p.s.

ELF 的全称：Executable and Linkable Format，即 ” 可执行、可链接格式 “

gdb，一种调试工具，以下是 gdb 启动程序的三种方式：run start starti

run -- Start debugged program. 开始执行程序，如果没有设置断点，不会停下。
start -- Start the debugged program stopping at the beginning of the main procedure. 开始执行程序，在 main 函数处会停下来
starti -- Start the debugged program stopping at the first instruction. 开始执行程序，在第一条指令处会停下来

操作系统中, 什么是块设备？【B】

A、键盘 B、磁盘 C、显示器 D、打印机

块设备是 I/O 设备中的一类，是将信息存储在固定大小的块中，每个块都有自己的地址，还可以在设备的任意位置读取一定长度的数据，例如硬盘，U 盘，SD 卡等。

显示器是什么设备【计算机的 I/O 设备：输出设备】
操作系统的并行和并发
进程 progress 和线程 thread

进程：是进程实体运行的过程，它是系统进行资源分配和调度的一个独立单位。

线程：是操作系统能够进行运算调度的最小单位，是被包含在进程之中的，是进程中的实际运作单位。

磁盘调度算法
FCFS 先来先服务 First Come First Service
SSTF 最短寻道时间 Shortest Seek Time First 选择寻找时间最短的访问者调度【会产生 "饥饿现象"】
电梯调度算法（SCAN）

磁道编号是从外到里的，即由内到外磁道号越来越小。从当前所在磁道号，从外向里运动，再从里向外运动，或反之。这样就避免了饥饿现象，由于这种移臂调度规律颇似电梯的运动，因而称为电梯算法。

循环扫描算法（CSCAN）

为了减少这种延迟，规定磁头单向读 / 写运动写运动 (如只能由内向外)，完成读写后，立即返到最小 / 大磁道号的位置 (构成循环 )，再进行扫描。即 CSCAN 算法。

页面置换算法
FIFO[first in first out] 先进先出页面置换算法
最优算法
LRU
第二机会 / 时钟算法
操作系统死锁的必要条件（下面有一个不成立就不会产生死锁）

互斥；占有并等待；非抢占；循环等待

解决 race condition 的 4 个必要不充分条件
中断分为内中断和外中断。

内中断（也称异常、例外、陷入）信号来源是 CPU 内部，与当前执行的指令有关；

外中断（狭义的中断）信号的来源是 CPU 外部，与当前执行的指令无关。

面试¶

南大传统，英语 + 中文提问

英语¶

自我介绍
描述你的家乡
相比其他人你的优势
为什么想来南京 / 南大
用英文介绍自己最喜欢的一门课程 2 分钟
英文介绍快排、冒泡、归并、希尔、DFS....（我怀疑类似的算法都有可能考到，建议多准备一点）
介绍二叉搜索树及时间复杂度
用英语解释 “死锁”

中文¶

2.1 编程语言相关¶

C、C++、Python 和 java

①语言类型：C、 C++、 java 、python 都是强类型的语言；

②面向过程与面向对象：C 语言是面向过程的，C++（半面向对象半面向过程）、JAVA、python 都是面向对象的。

③编译型和解释型语言：

高级语言也分为编译型语言和解释型语言。主要区别在于，前者源程序编译后即可在该平台运行，后者是先用解释器对源程序逐行解释成特定平台的机器码，再在运行期间才编译。所以前者运行速度快，后者跨平台性好。

C、C++、Objective 等都属于编译型语言，Python 等属于解释型语言。

关于 java：Java 和其他的语言不太一样。因为 java 针对不同的平台有不同的 JVM，实现了跨平台。所以 Java 语言有一次编译到处运行的说法。

面向对象和面向过程
面向对象三大特征，及每一特征的介绍与实现【封装、继承、多态...】
静态 / 动态语言

动态类型语言：动态性语言是指在运行期间才去做数据类型检查的语言，也就是说动态类型语言编程时，永远不用给任何变量指定数据类型，该语言会在第一次赋值给变量时，在内部将数据类型记录下来。Python 和 Ruby 就是一种典型的动态类型语言，其他的各种脚本语言如 VBScript 也多少属于动态类型语言。

静态类型语言：静态类型语言与动态类则刚好相反，它的数据类型在编译期间检查，也就是说在写程序时要声明所有变量的数据类型，C/C++ 是静态类型语言的典型代表，其他静态语言还有 C#、Java 等。

JVM

Java Virtual Machine, Java 虚拟机，是用来解析和运行 Java 程序的。

Java 语言的一个非常重要的特点就是与平台的无关性。而使用 Java 虚拟机是实现这一特点的关键。一般的高级语言如果要在不同的平台上运行，至少需要编译成不同的目标代码。而引入 Java 语言虚拟机后，Java 语言在不同平台上运行时不需要重新编译。Java 虚拟机屏蔽了与具体操作系统平台相关的信息，使得 Java 程序只需生成在 Java 虚拟机上运行的目标代码（字节码），就可以在多种平台上不加修改地运行。

指针和引用有什么区别？

"指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名，引用不改变指向"

1、引用不可以为空，但指针可以为空。

2、引用不可以改变指向，对一个对象 "至死不渝"；但是指针可以改变指向，而指向其它对象。

3、引用的大小是所指向的变量的大小，因为引用只是一个别名而已；指针是指针本身的大小，4 个字节。

4、引用比指针使用起来形式上更漂亮，使用引用指向的内容时可以之间用引用变量名，而不像指针一样要使用 *；定义引用的时候也不用像指针一样使用 & 取址。

5、引用比指针更安全。由于不存在空引用，并且引用一旦被初始化为指向一个对象，它就不能被改变为另一个对象的引用，因此引用很安全。对于指针来说，它可以随时指向别的对象，并且可以不被初始化，或为 NULL，所以不安全。const 指针虽然不能改变指向，但仍然存在空指针，并且有可能产生野指针（即多个指针指向一块内存，free 掉一个指针之后，别的指针就成了野指针）。

多继承和相关知识
虚基类

2.2 数据结构¶

【各种排序】

并查集

在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

（p.s. 路径压缩优化）

最小生成树算法及应用 (类似于在一个城市建一个通信网这种比较贴合实际的问题)

prim（解决稠密图），kruskal（解决稀疏图）算法等等… 都是基于贪心算法实现

【了解这两种算法的核心思想】

二叉搜索树是什么，怎么定义？搜索的时间复杂度是多少？
Huffman 树怎么实现和时间复杂度？
大量数据，如何选取最大的 50 个？

top k 问题：在⼀堆数据⾥⾯找到前 K 大（当然也可以是前 K 小）的数。

对于很大量的数据，如何判断链表是否有环？

用快慢指针。快指针：从头开始移动，每次移动两个距离；慢指针：从头开始移动，每次移动一个距离；

2.3 操作系统¶

读者写者问题要求设计算法

①允许多个读者可以同时对文件执行读操作;

②只允许一个写者往文件中写信息;

③任一写者在完成写操作之前不允许其他读者或写者工作;

④写者执行写操作前，应让已有的读者和写者全部退出。

核心思想：设置计数器 count 用来记录当前正在访问文件的读进程数。

需要一气呵成的时候，应该用互斥信号量。

操作系统的并行和并发
数据库和操作系统文件系统的区别
分页的作用，好处，原因，与分段的区别

2.4 计网¶

【各分层的功能作用】

IPv6 出现的动力是什么，以及报文头哪些字段发生了变化？
计算机网络为什么要分层？

实例¶

【搜集的其他人的经历】

首先第一个老师让我用英文介绍一个算法，我介绍的是快排。之后老师让说一下时间复杂度和最坏情况，之后又给我了一个问题让我实现算法，问题其实是 Huffman 树怎么实现和时间复杂度。第二个老师问的是编程语言相关的，让我说一下 C++ 和 Java 区别，JVM 的优点，多继承和相关知识等等。第三个老师问了几个操作系统专业题，比如读者写者问题要求设计算法。
南大特别喜欢问编译原理和一些计算机底层的知识，我能想起来的就是 C 语言和 Python 的区别，静态动态 balabala 的，我答得也乱七八糟的。还问了数据结构的并查集相关知识，我只知道个大概。
一个老师问最小生成树算法 (Prim 和 Kruskal 的主要思想), 接着老师问你知不知道为什么 Prim 是正确的；然后另外一个老师问最小生成树的应用 (类似于在一个城市建一个通信网这种比较贴合实际的问题)
先是 Krustra 算法英文介绍；然后中文问 Krustra 算法的数据结构？几个优化过程？
np 和 p 问题了解吗？我说我不了解，常用是 java 语言。问我，java 类加载机制是什么?
离散数学你最清楚什么内容？我说是最短路径，说一下 Dijkstra 算法和 Bellman-fold 算法的区别？为什么 Bellman-fold 算法能够解决负权？