考研复试 算法设计与分析 综合面试之专业综合考核

若线性表需要频繁查找，很少进行插入和删除操作，宜采用何种存储结构？

顺序存储结构。

若线性表需要频繁插入和删除，宜采用何种存储结构？

链式存储结构（或答单链表）。

对比数组，链表，二叉排序树的优劣和应用场景

访问效率上，数组是随机访问，时间复杂度为$O(1)$，链表是顺序访问，时间复杂度为$O(n)$，二叉排序树是二分查找，时间复杂度为$O(\log n)$。
插入和删除效率上，数组需要移动元素，时间复杂度为$O(n)$，链表只需要修改指针，时间复杂度为$O(1)$，二叉排序树平均时间复杂度为$O(\log n)$。
扩展性上，数组扩展性较差，需要预先分配空间，链表和二叉排序树扩展性较好，可以动态分配空间。

应用场景：

• 数组：适用于需要频繁访问的场景。
• 链表：适用于需要频繁插入和删除的场景。
• 二叉排序树：适用于既需要频繁查找，又需要频繁插入和删除的场景。

栈和队列的相同点和不同点

相同点：

• 都是线性结构
• 都是操作受限的线性表
• 插入操作都在表尾

不同点：

• 删除操作的位置不同：栈在表尾进行，队列在表头进行
• 栈是后进先出（LIFO），队列是先进先出（FIFO）

如何区分循环队列是队空还是队满？

方法一：牺牲一个存储单元。 队空：$front = rear$，队满：$front = (rear + 1) \% maxsize$。

方法二：增加一个计数变量$size$。 队空：$size = 0$，队满：$size = maxsize$。

树的表示法有哪些？

双亲表示法、孩子表示法、孩子兄弟表示法

二叉树，完全二叉树，二叉排序树，平衡二叉树的特点

• 二叉树：
  每个节点最多有两个子节点的树结构，即每个节点的度最大为2。
• 完全二叉树：
  除了最后一层，其他层的节点数都达到最大的二叉树，最后一层的节点都集中在左边。
• 二叉排序树：
  左子树的节点值小于根节点，右子树的节点值大于根节点的二叉树，并且左右子树也分别为二叉排序树。
• 平衡二叉树：
  每个节点的左右子树的高度差不超过1的二叉树，并且左右子树也为平衡二叉树。

为什么会引入线索二叉树？它有什么优势？

在普通二叉树中，许多指针（左孩子、右孩子）实际上是空指针，利用这些空指针存储前驱、后继信息，可以在不使用额外存储空间的情况下实现高效遍历。

什么是带权路径长度？什么是哈夫曼树？哈夫曼树的构造过程？

带权路径长度WPL指的是树中所有叶子节点的权值 × 其到根节点的路径长度之和。
哈夫曼树是带权路径长度最短的二叉树。

哈夫曼树的构造过程：

1. 将所有的权值视为单独的节点，形成一个森林。
2. 每次从森林中选取两个具有最小权值的节点，作为新二叉树的左右子节点，并将它们的权值之和作为新树的根节点权值。
3. 重复步骤2，直到森林中只剩下一棵树，这棵树就是哈夫曼树。

图的存储方式

邻接矩阵、邻接表、十字链表、邻接多重表

深度优先和广度优先搜索的算法思想

深度优先搜索：从起点开始，沿着一条路径一直走到底，然后回溯，继续沿着另一条路径走到底，直到所有路径都被探索完。

广度优先搜索：把起点加入队列，依次访问队列中的顶点，所有未访问过的邻接点进行扩散，直到队列为空。

什么是关键路径

AOE网是一种带权有向无环图，其中顶点表示事件，边表示活动，边上的权值表示活动所需的时间。
在AOE网中，从起点到终点所经过的总时间最长的一条路径称为关键路径。它决定了整个工程的最短完成时间。

列举一些哈希函数的构造方法

直接定址法、除留余数法

直接定址法： 哈希函数为关键字的线性函数，即 $H(key) = key$ 或 $H(key) = a * key + b$，其中a和b为常数。

除留余数法： 哈希函数为关键字除以某个质数p的余数，即 $H(key) = key \% p$。

哈希表处理冲突的方法

开放定址法、拉链法
开放定址法包括：线性探测法、平方探测法、再散列法等

各种排序算法思想（默认按从小到大排）

快速排序： 选择一个基准元素，将数组分成两部分，一部分小于基准元素，一部分大于基准元素，然后递归地对两部分进行排序。

归并排序： 将数组分成两部分，分别进行排序，然后合并成一个有序数组。

插入排序： 类似扑克牌，每次从无序部分选择一个元素，插入到有序部分的合适位置。

希尔排序： 将数组按照一定的间隔进行分组，对每个小组进行插入排序，然后逐步缩小间隔，直到整个数组有序。

选择排序： 每次选择最小的元素，放到已排序部分的末尾。

冒泡排序： 比较数组中每对相邻元素，如果顺序不对，则交换位置。一直到数组结尾，称为一趟排序。 重复这个过程，直到数组有序。 如果一趟排序没有发生交换，则说明数组已经有序，可以提前结束。

堆排序：

1. 将数组构建成一个堆
2. 将堆顶元素与最后一个元素交换
3. 调整堆
4. 重复交换和调整，直到整个数组有序

哪些排序算法是稳定的？哪些是不稳定的？

稳定的排序算法：插入排序、冒泡排序、归并排序、基数排序

不稳定的排序算法：希尔排序、选择排序、堆排序、快速排序

口诀：选艾希，堆攻速（选择排序、希尔排序、堆排序、快速排序）
参考资料：BOK25数据结构精讲课——排序 8-5 排序小结

冯诺依曼机的主要特点

1. 五大部件：运算器、控制器、存储器、输入设备、输出设备。
2. 指令和数据均用二进制表示，以同等地位存储在存储器中。
3. 指令由操作码和地址码组成。
4. 指令在存储器中顺序存储。

什么是翻译，什么是解释

翻译：将编写的程序全部翻译成另一种语言，然后再执行。
解释：将编写的程序的一条语句翻译执行后，再翻译下一条语句，翻译一句执行一句。

三级存储体系的构成，并对比Cache-主存和主存-辅存层次之间的区别

Cache-主存-辅存

Cache-主存：解决CPU和主存速度不匹配的问题；
主存-辅存：解决存储系统的容量问题。

容量上，Cache最小，主存其次，辅存最大。
速度上，Cache最快，主存其次，辅存最慢。
传输单位上，Cache-主存层次以块为单位，主存-辅存层次是页或段。

什么是MAR，什么是MDR

MAR：存储器地址寄存器。
MDR：存储器数据寄存器。
存储器的最大容量由MAR和MDR的位数共同决定。

什么是Cache

高速缓冲存储器，位于CPU和主存之间，由SRAM组成。

Cache替换算法

1. 随机替换（Random）
2. 先进先出（FIFO）
3. 最近最少使用（LRU）

Cache和主存的映射方式

1. 直接映射：主存中的块只能装入Cache中的唯一位置。
2. 全相联映射：主存中的块可以装入Cache中的任意位置。
3. 组相联映射：将Cache分成若干大小相同的组，组间采用直接映射，组内采用全相联映射。

分页和分段存储管理的区别

分段： 进程的地址空间分成若干个段，每个段的大小可以不同。段的长度可以不连续，段与段之间可以不连续。

分页： 进程的地址空间分成若干个页，每个页的大小相同。页的长度必须连续，页与页之间必须连续。

什么是虚拟存储器

虚拟存储器从逻辑上对主存进行扩充，使得程序可以使用比物理内存更大的空间。

什么是局部性原理（时间局部性和空间局部性）

时间局部性： 如果某个数据最近被访问过，那么它在不久的将来可能会再次被访问。 即，某些数据在短时间内可能被多次访问。 常见于循环结构。

空间局部性： 如果某个数据最近被访问过，那么它附近的数据项在不久的将来也可能被访问。 即，程序访问的内存地址往往是连续的。 常见于顺序结构如数组。

大端模式和小端模式

举例：0x12345678

地址从低到高： 大端模式：0x12 0x34 0x56 0x78 符合人类阅读习惯 小端模式：0x78 0x56 0x34 0x12 符合机器阅读习惯

什么是 CISC 和 RISC

CISC：复杂指令集计算机，指令系统复杂，指令数量多且长度不固定。
RISC：精简指令集计算机，指令系统简单，指令数量少且长度固定。

寻址方式（立即寻址/直接寻址/间接寻址/寄存器寻址/寄存器间接寻址/相对寻址/基址寻址/变址寻址）

立即寻址：地址字段即为操作数。
直接寻址：地址字段为操作数的真实地址。
间接寻址：地址字段为操作数地址的地址。
寄存器寻址：地址字段为操作数所在寄存器编号。
寄存器间接寻址：地址字段为寄存器编号，该寄存器存储的是操作数所在存储单元的地址。

相对寻址：操作数地址=PC+偏移量
基址寻址：操作数地址=基址寄存器+偏移量，基址寄存器在程序执行过程中不变，偏移量可变。
变址寻址：操作数地址=变址寄存器+偏移量，变址寄存器在程序执行过程中可变，偏移量不变。

什么是指令流水线，五段式流水线的各阶段

将一个任务分解为几个不同的子阶段，每个阶段在不同的功能部件上并行执行，以便同一时刻能够同时执行多个任务，进而提高系统性能。

五段式流水线：

• 取指(IF)：从存储器中取出指令。
• 译码(ID)：对指令进行译码。
• 执行(EX)：执行指令。
• 访存(M)：访问存储器。
• 写回(WB)：将结果写回存储器。

什么是流水线冒险

实际执行过程中，由于某些原因，流水线无法正确按顺序执行后续指令，导致流水线阻塞或停顿。

结构冒险：多条指令在同一时刻争用同一资源。
数据冒险：后续指令需要用到前面指令的计算结果。
控制冒险：遇到跳转指令使PC发生跳转，导致流水线清空。

总线的两大特征

分时和共享。

分时：同一时刻只允许一个部件使用总线。
共享：总线上可以挂多个部件，都通过该总线进行数据传输。

总线的分类（记一个按传输信息分类）

数据总线、地址总线和控制总线。

数据总线：双向传输，用于各部件之间传输数据。
地址总线：单向传输，用于指明数据总线上传输信息的源地址和目的地址。
控制总线：双向传输，用于协调各部件按序执行。

突发传输

只需一个首地址，就可连续传输多个数据块，提高数据传输效率。

同步定时方式

系统采用一个统一的时钟信号来协调发送方和接受方之间的操作。在一个总线周期内，发送方和接受方完成一次数据传输。

异步定时方式

系统没有统一的时钟信号，传送双方通过“握手”机制实现定时控制。可分为不互锁、半互锁和全互锁三种方式。

主机与外围设备之间信息传送的控制方式

1. 程序查询方式
2. 程序中断方式
3. 直接存储器存取（DMA）方式
4. 通道方式

什么是操作系统

操作系统是计算机中最基本的系统软件，是用户与计算机硬件之间的桥梁。
它管理整个计算机系统的硬件和软件资源，同时为用户和其他应用程序提供接口。

操作系统的特征

• 并发：两个或多个事件在同一时间间隔内发生。
• 共享：系统中的资源可以被多个并发执行的进程共同使用。
• 虚拟：把一个物理上的实体变成多个逻辑上的对应物。
• 异步：程序的执行不是连续的，而是走走停停，以不可预知的速度向前推进。

什么是原语？

原语是一种特殊的程序，处于操作系统的底层。
原语具有原子性，要么一气呵成全部完成，要么不执行，执行过程不可被中断 。

什么是中断和异常，有何区别

中断又称外中断，是指CPU执行指令以外发生了事件，例如IO请求等。
异常又称内中断，是指CPU执行指令期间出现了问题，例如溢出、地址越界、除0错等。

进程与线程的区别

进程是资源分配的基本单位，有独立的地址空间，切换开销大。
线程是CPU调度的基本单位，共享进程的地址空间，切换开销小。

进程的生命周期（进程的五种状态）

创建态、就绪态、运行态、阻塞态、终止态。

• 创建 → 就绪：进程被创建，资源已分配，插入就绪队列等待 CPU 调度
• 就绪 → 运行：进程被调度程序选中，获得 CPU
• 运行 → 就绪：进程时间片到，让出 CPU 给其他进程
• 运行 → 阻塞：进程等待 I/O 或其他资源
• 阻塞 → 就绪：I/O 完成，进程可继续执行
• 运行 → 终止：进程执行完毕或发生错误

记一个：阻塞态不能直接转换为运行态，需要先转换为就绪态。

进程的调度算法

• 先来先服务（FCFS）：按照进程到达的顺序来调度。
• 短作业优先（SJF）：选择估计运行时间最短的进程来执行。
• 高响应比优先（HRRN）：根据等待时间与服务时间之间的比值来选择下一个要执行的进程。
• 时间片轮转（RR）：每个进程在CPU上运行一个时间片，时间片轮转调度算法使得每个进程在一定时间内都能被执行。

什么是临界资源和临界区

临界资源是指在同一时刻只允许一个进程使用的资源。对临界资源的访问，必须互斥地进行。
临界区是指访问临界资源的代码段。

什么是死锁，死锁产生的条件，处理方法

死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象。

死锁产生的条件：

1. 互斥使用：一个资源只能被一个进程使用。
2. 请求与保持：进程至少已经持有一个资源，但在等待获取额外资源时，不释放已占有的资源。
3. 不可抢占（不可剥夺）：进程已获得的资源，在未使用完之前，不能强行剥夺。
4. 循环等待：资源分配图中存在环路。

处理方法： 死锁预防、死锁避免、死锁检测。

饥饿和死锁有什么区别

饥饿是进程长时间等待得不到调度，并不代表发生了死锁。
出现饥饿的进程可以是就绪态，死锁状态的进程一定是阻塞态。

内存管理的主要功能

内存的分配和回收

• 地址转换：将逻辑地址转换为物理地址
• 内存扩充：利用虚拟技术从逻辑上扩充内存
• 存储保护：让各个进程在各自存储空间内运行，互不干扰

内存的连续分配管理方式

单一连续分配、固定分区分配、动态分区分配

动态分区分配的四种算法？

• 首次适应：按地址递增的顺序排列空闲分区，从头开始找第一个能满足大小的空闲分区。
• 临近适应：按地址递增的顺序排列空闲分区，从上一次查找结束的位置开始找第一个能满足大小的空闲分区。
• 最佳适应：按容量递增的顺序排列空闲分区，从头开始找第一个能满足大小的空闲分区。
• 最坏适应：按容量递减的顺序排列空闲分区，从头开始找第一个能满足大小的空闲分区。

内存的非连续分配管理方式

分页、分段、段页式

页面置换算法

• 最佳置换（OPT）：暂时无法实现
• 先进先出（FIFO）
• 最近最久未使用（LRU）
• 时钟置换（CLOCK）

地址转换过程（虚拟地址转换为物理地址）

背景知识：

1. 快表是硬件机构，位于CPU和主存之间；页表位于主存；页表中部分常用页表项缓存在TLB中。
2. 快表中没有保存所有的虚页对应的页表项，所以快表不命中就要去查慢表（页表）
3. 页表中一定有所有虚页对应的页表项，一定能命中，只是有些页表项有效位为0，即它对应的页不在内存中，需要从外存中调入。

1. CPU首先查找TLB。如果命中，直接形成物理地址；否则，进入页表查找过程。
2. CPU接着查找页表。如果页表项有效位为1，则形成物理地址，并加载到TLB中；如果有效位为0，发生缺页中断，进入外存查找过程。
3. CPU接着查找外存，从外存中找到缺页，调入到内存，修改页表，更新TLB。

参考资料：BOK25操作系统基础班 3-3 虚拟存储器(OS)

操作系统如何管理文件/什么是文件系统

操作系统通过文件系统来对文件进行统一管理。

1. 管理磁盘空间分配，包括连续分配、链接分配、索引分配。
2. 管理文件控制块FCB、索引节点inode及文件目录结构。
3. 管理文件的打开、读写、关闭等操作，提供统一的系统调用接口。

区分硬链接和软链接

硬链接：目录项只有文件名和文件的inode号，其他属性都在inode中。
软链接：软链接是一个独立的文件，其内容存储的是目标文件的路径。

磁盘调度算法

• 先来先服务（FCFS）
• 最短寻道时间优先（SSTF）
• 扫描算法（SCAN）
• 循环扫描算法（CSCAN）

什么是 SPOOLing 技术/假脱机技术

SPOOLing 技术是一种将独占设备改造为共享设备的技术。它利用磁盘作为缓冲区，让 I/O 设备和 CPU 并行工作，提高了系统的吞吐量。

OSI七层协议

物联网淑惠适用：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

TCP/IP四层协议

硬输计网：应用层（合并了最上面三层）、传输层、网际层、网络接口层（合并了最底下两层）

计算机网络协议的组成

• 语法：数据与控制信息的格式
• 语义：需要发出何种控制信息，完成何种动作以及做出何种应答
• 同步：事件的实现顺序

面向连接服务和无连接服务

• 面向连接服务：通信前双方必须建立连接，数据按序传输，可靠交付。例：TCP
• 无连接服务：通信双方不需要建立连接，数据传输不可靠。例：UDP

电路交换、报文交换、分组交换

• 电路交换：在通信前建立一条专用的物理通路，通信过程中始终占用该通路，直到通信结束后才释放。
• 报文交换：将数据作为一个整体进行存储和转发。
• 分组交换：将数据分成多个分组，每个分组独立传输，到达目的地后再重新组装。

调制和编码

调制：将数字信号转换为模拟信号
编码：将模拟信号转换为数字信号

解释CSMA/CD和CSMA/CA协议

• CSMA/CD：载波监听多路访问/碰撞检测 发送前侦听，边发送边侦听，一旦出现碰撞马上停止发送，等待一段随机时间后再发送。
• CSMA/CA：载波监听多路访问/碰撞避免 发送前先广播，告知其他结点，让其他结点在一段时间内不要发送数据，以免发生碰撞。

CSMA/CD为什么不能用于无线传输

1. 无线介质中难以检测碰撞
2. 无线介质中信号的波动范围广，检测到的不一定是碰撞，也有可能是变形的信号，检测误差大

对比 IPv4 和 IPv6，为什么要引入IPv6

• 长度和空间上：
  • IPv4：32位，最大可提供$2^{32}$个地址，地址空间有限。
  • IPv6：128位，最大可提供$2^{128}$个地址，地址空间无限。
  • 引入IPv6可以解决IPv4地址空间不足的问题。
• 表示上：
  • IPv4：点分十进制表示法
  • IPv6：冒号十六进制表示法
• 报文格式上：
  • IPv4：首部固定长度20字节，可变部分是可选的，最大长度为40字节。
  • IPv6：首部固定长度40字节，没有可变部分。

对比集线器/交换机/路由器

• 集线器：广播接收到的数据，工作在物理层，既不能隔离冲突域，也不能隔离广播域。
• 交换机：基于MAC地址转发MAC帧，工作在数据链路层，可以隔离冲突域，但不能隔离广播域。
• 路由器：基于IP地址进行路由选择和路由转发，工作在网络层，既能隔离冲突域，也能隔离广播域。

解释 TCP 和 UDP

• UDP是无连接的协议，发送数据前不需要建立连接，是不可靠传输。
• TCP是面向连接的协议，发送数据前要建立连接，提供的是可靠传输。TCP连接的建立需要三次握手，释放需要四次挥手。

三次握手：

1. 客户端发送SYN
2. 服务器发送SYN+ACK
3. 客户端发送ACK，连接建立

四次挥手：

1. 客户端发送FIN
2. 服务器发送ACK，并传送剩余数据
3. 服务器发送FIN
4. 客户端发送ACK，等待2MSL后，连接释放

列举一些应用层的协议

• HTTP：超文本传输协议，用于浏览器与服务器之间的数据传输。
• FTP：文件传输协议，用于文件的上传和下载。
• SMTP：简单邮件传输协议，用于电子邮件的传输。
• DNS：域名解析协议，用于把域名映射成为IP地址或把IP地址映射为域名。