科大讯飞笔试复盘

选择考了一堆408，全都忘干净了

算法还没有试过acm模式，惨遭0ac

1.无向图对应最小生成树MST，有向图对应的是最短路径

最小生成树（没有环且所有边的权重之和最小）必须是无向连通图，带有权重，两大经典算法prim算法和kruskal算法

有向图的核心算法有dijkstra floyd Bellman-Ford

2.信号量 pv操作

信号量是解决进程线程同步和互斥问题

s代表着资源，p操作（wait）申请一个单位资源，将信号量s减1，如果小于0的时候就阻塞，加入等待队列，v操作是释放一个单位资源，将信号量+1，释放完资源后若s小于等于0，唤醒一个进程

常用来解决互斥问题，保证同一时刻只有一个进程访问临界区（例如共享变量）；同步问题，协调进程执行的先后顺序（例如：线程a必须先做完事，线程b才能做）。

3.动态分区分配算法，用来内存管理，其中的Best Fit（最佳适配法）

Best Fit（最佳适配法）：找最接近大小的内存块，容易产生微小内存碎片

First Fit：从头找，遇到第一个够大的就分

Worst Fit：找最大的块分

4.MSD最高位优先

相当于桶排序，按照百位十位这样的顺序一次往下排序

5.FTP：专门为文件管理的古老协议（双通道）

HTTP：专门为网页内存设计的通用协议（单通道）

FTP和HTTP都基于TCP

6.中断和互斥

中断是硬件机制，用于处理异步事件，打破了程序执行的连续性

互斥是软件/逻辑机制，用于解决并发竞争我呢提，保证同一时刻只有一个进程线程访问临界资源

在单处理器系统中，为了可实现互斥，往往需要暂时屏蔽中断

中断是指 CPU 在执行当前程序时，由于内部事件或外部事件的发生，暂时停止当前程序的执行，转而去执行一段特定的处理程序，处理完毕后返回原程序继续执行的过程，实现并发：通过时钟中断，操作系统可以强行剥夺当前进程的 CPU，实现多任务切换。

实现互斥的方法：软件方法：信号量 (Semaphore)：PV 操作。互斥锁 (Mutex)：专门用于互斥的锁。自旋锁 (Spinlock)：忙等待，不切换上下文。

在单核系统中，并发实际上是交替执行。如果没有中断，一个进程会一直运行直到自愿放弃 CPU。

问题：如果一个进程正在执行临界区代码（修改共享数据），此时发生了一个时钟中断，操作系统进行进程切换，另一个进程也去修改同一个共享数据，就会破坏互斥。

解决方案：在进入临界区前“关中断”，退出临界区后“开中断”。

原理：只要关闭了中断，当前进程就不会被时钟中断打断，也就不会发生进程切换。既然不会切换，其他进程就永远无法运行，自然也就无法进入临界区。从而实现了最简单的互斥。

7.http：80 https：443 ftp：20/21 telnet：22/23

8.Linux中df和du的命令

df (Disk Free)：看宏观。查看文件系统（分区）的整体使用情况（总容量、已用、剩余），df -h（看剩多少）

du (Disk Usage)：看微观。查看具体文件或目录占用了多少空间，找出谁占用了空间，定位大文件/大目录（看占了多少）

Linux中目录也会占用空间

9.#！/bin/bash

请使用 /bin/bash 这个解释器来执行我！

10.读写锁？stampedLock ReentrantReadWriteLock AQS

AQS：java.util.concurrent (JUC) 包的核心基础设施，它不是一个具体的锁，而是一个框架，用来构建锁和同步器（如 ReentrantLock, CountDownLatch, Semaphore 等）。

AQS 定义了一套通用的机制来管理线程的阻塞与唤醒，子类只需关注“状态是否允许通过”，具体的排队逻辑由 AQS 搞定。

状态变量 (state)：一个 volatile int 类型的变量，表示同步状态。含义由子类定义：在 ReentrantLock 中，state=0 表示无锁，state=1 表示持有锁，state>1 表示重入次数。在 CountDownLatch 中，state 表示剩余需要等待的次数。在 ReentrantReadWriteLock 中，state 的高 16 位表示读锁计数，低 16 位表示写锁计数。
FIFO 等待队列：当线程获取资源失败时，AQS 会将该线程封装成一个 Node 节点，加入到一个双向链表的等待队列中，并阻塞该线程（使用 LockSupport.park()）。当资源释放时，AQS 会唤醒队列头部的节点（或其后续节点）去尝试获取资源。