王道

这个也是实时更新的，更新完结之后，我会在帖子开启的部分说明 2023年12月3日 今天中午吃完午饭，放松了一个小时，由于这几年没有收入，我非常有罪恶感。然后前段时间发现也有一个木有收入的媒体人，转发一下吧。 南开 + 腾讯 + 背包客 + 自媒体 + 网络红人 —— 暂时厘定这些标签 参考 http ......

主要内容就是KMP算法 KMP 串的一些基本概念 1、子串/模式串 串中任意多个连续的字符组成的子系列叫做字串 2、主串 包含字串的串称为主串 3、模式匹配(pattern matching) 字串的定位操作称为串的模式匹配，是求子串在主串中的位置 算法 参考: https://www.bilibi ......

外部排序与内部排序 内部排序指排序期间元素全部存放在内存的排序 外部排序指排序期间元素无法同时存放在内存，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。 插入排序 直接插入排序 算法思想 每遍历到一个元素，就拿这个元素一直向左比较，直到比左边元素小或相等或者直到数组下标为0时终止 算法性 ......

1、绪论 1.1、数据结构在学什么？ 1.2、基本概念和术语 1.3、数据结构三要素 1.4、算法的基本概念 1.5、算法的空间复杂度 1.6、算法的时间复杂度 2、线性表 1 ......

1、计算机系统概述 1.1、操作系统的概念、功能 1.2、操作系统的特征 1.3、操作系统的发展与分类 1.4、操作系统的运行机制 1.5、中断和异常 1.6、系统调用 1.7、操作系统的体系结构 1.8、操作系统引导 1.9、虚拟机 2、进程管理 2.1、进程的概念、组成和特征 2.2、进程的状态 ......

图有关的概念 1、连通图、连通分量是相对于无向图说的，而强连通图、强连通分量是相对于有向图说的 2、生成树，连通图的生成树是包含图中全部顶点的一个极小连通子图。若砍去一条边，则一定变得非连通 3、极大连通子图与极小连通子图，极小连通子图就是生成树，极大连通子图就是无向图的连通分量 极大要求包含该连通 ......

基本概念 ASL 平均查找长度 在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值 顺序查找与折半查找 一般线性表的顺序查找 没啥好说的 有序表的顺序查找 树中的圆形结点表示有序线性表中存在的元素；树中的矩形结点称为失败结，点（若有n个 ......

有序树、无序树的概念 有序树和无序树,树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。 树/二叉树的性质 树的性质 常用的只有第一个 二叉树的性质 常用公式也只有这一个 二叉树的存储 一般分为顺序存储与链式存储 要求顺序存储能默写 顺序存储: typedef struc ......

错题2.2 1、题目中提到在第i个位置一般是指在下表为i的位置 2、线性表元素的序号是从1开始，而在第n+1个位置插入相当于在表尾追加。 静态链表 树的双亲表示法就是使用了这种思想吧 卡特兰数 \[\text{}\frac1{n+1}C_{2n}^{n} \]栈的数学性质：n个不同元素进栈，出栈元素 ......

顺序存储可能会参生外部碎片 这里的外部碎片与我们狭义上认为的外部碎片不太一样，在这里，他的含义是这样的: 比如我们定义了10个长度的数组，却只使用了一个，那么剩下的9个就被浪费了 各种"表" 1、顺序表:指物理地址连续存储的数据结，必须是顺序存储，属于存储结构，相应的，顺序栈，顺序队列也都是存储结构 ......

一、历年选择题考点 二、传输层提供的服务 传输层向它上面的应用层提供通信服务，它属于面向通信部分的最高层，同时也是用户功能中的最低层。 传输层的功能 传输层提供应用进程之间的逻辑通信（即端到端的通信） 它为运行在不同主机上的进程之间提供了逻辑通信（即端到端的通信），而网络层提供主机之间的逻辑通信。 ......

一、历年选择题考点 二、数据链路层的主要功能 数据链路层的最基本的功能是向该层用户提供透明的和可靠的数据传送基本服务。 数据链路层是对物理层传输原始比特流的功能的加强，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一无差错的线路。 为网络层提供服务 1、无确认的无 ......

1、计算机发展历程 1.1、什么是计算机系统 1.2、硬件的发展 1.3、各个硬件的工作原理 1.4、计算机系统的多级层次结构 1.5、计算机性能指标 2、数据的表示和运算 ......

题目：设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序：先看数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，大的在后。满足这种要求的排序方法是（ ）A.先按k1进行直接插入排序，再按k2进行简单选择排序B.先按k2进行直接插入排序，再按 ......

一、考点分布 1、选择题 2、大题 二、性能指标 速率 速率 = 数据率 = 数据传输率 = ⽐特率 单位是b/s，kb/s，Mb/s，Gb/s，Tb/s 带宽 1、带宽 <=> 某个信号具有的频带宽度。单位Hz 2、带宽 <=> 表示⽹络的通信线路传输数据的能⼒ = 单位时间内从⽹络中某信道所能所 ......

一、系统的页表项一般包括 ⻚号（隐含，实际不会占⽤存储空间） ⻚框号（⽤于描述逻辑⻚⾯在物理内存中的位置） 脏位（⽤于描述该⻚⾯的数据是否被修改过） 有效位 外存地址（⽤于描述该⻚⾯在外存中的存放地址） 置换算法相关的信息（不同的置换算法，需要记录的信息不同。如FIFO算法需要记录⻚⾯调⼊内存的时间 ......

一、I/O接口与I/O端口 I/O接口（设备控制器）位于CPU与设备之间，它既要与CPU通信，又要与设备通信，还要具有按CPU发来的命令去控制设备工作的功能 1、设备控制器与CPU的接口 该接口有三类信号线：数据线、地址线和控制线。数据线通常与两类寄存器相连：数据寄存器（存放从设备送来的输入数据或从 ......

### 一、文件的数据结构 #### 文件目录项/FCB 一个FCB就是一个文件目录项 FCB的有序集合称为"文件目录" FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”。 FCB主要记录⽤来记录⽂件的名字，索引节点指针以及其他⽬录项的层级关联关系 #### 索引节点 (简 ......

### 一、程序的链接与装入 #### 编译 由编译程序将用户源代码编译成若干目标模块 #### 链接 由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起，形成一个完整的装入模块。 逻辑地址形成的阶段 1、静态链接 在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模 ......

# 数据结构 ## 一. 绪论 ### 1.1 基本概念 **数据元素：**数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。 **数据类型：**是相互 ......

### 一、进程的堵塞 正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做等，进程便通过调用阻塞原语(Blo©k),使自己由运行态变为阻塞态。可见，阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU),才可能将其转为阻塞态 ......

人类自从进入文明社会以来，有了书本、有了读书人，我们的价值观就一直是崇尚智力而不是暴力，认为你有再强的力量都不如我有知识。现在是时候重新审视这个认识了。 人的肌肉力量是非常有限的，你就是一天吃五顿饭又能多长几斤肉。工程机械的力量可以很大很大，但是能做的事情很有限，毕竟文明需要的更多的是精细而不是大力 ......

### 一、操作系统为用户提供的接口 #### 命令接口 1、联机命令接口 交互式接口，比如linux的命令行终端 ⽤户发送⼀个命令，系统就执⾏⼀次，主要特点是交互性，适⽤于分时或实时系统 2、脱机命令接口 类似与linux的bash脚本、windows的bat批处理脚本 ⽤户⼀次性发送命令清单，系 ......

### 一、8bit补码加法器的实现 8bit补码加/减加法器实现：  不加多路选择器则只能进行加法操作 # ......

### 一、SSD固态硬盘基于flash闪存 ### 二、通道 #### 概念 通道是一个具有特殊功能的处理器，它有自己的指令和程序，专门负责数据输入输出的传输控制,通道受CPU的I/O指令启动、停止或改变其工作状态。 #### 功能 通道的基本功能是按I/O指令要求启动I/O设备，执行通道指令，组 ......

### 一、总线分类 #### ⽚内总线 芯⽚内部的总线 是CPU芯⽚内部寄存器与寄存器之间、寄存器与ALU之间的公共连接线 #### 系统总线 计算机系统内各功能部件（CPU、主存、I/O接⼝）之间相互连接的总线 按系统总线传输内容的不同⼜可分为3类 1、数据总线 传输各功能部件之间的数据信息，是 ......

### 易混淆性能指标 #### 机器字⻓ 计算机进⾏⼀次整数运算所能处理的⼆进制的位数，⼀般与字⻓⻓度有关 注意不是浮点数运算 #### 数据通路带宽 外部数据总线⼀次能并⾏传送信息的位数，⾮CPU内部数据总线宽度 #### MIPS MIPS：每秒执⾏多少百万条指令 MFLOPS：每秒执⾏多少百 ......

###一、指令执行周期的英文缩写 1、取值周期(FE=1) 2、间指周期(IND=1) 3、执行周期(EX=1) 4、中断周期(INT=1) ###二、微命令、微操作 微命令1使得$PC_{out}、MAR_{in}$有效。完成对应的微操作1(PC)→MAR 一个机器周期内可能包含多个微命令和微操作 ......

--> ###这一章学的有问题 首先是5.4硬布线控制器与微程序控制器学的不行，之后的5.6流水线与5.7多处理器的概念学的也不是很好 还得再完完整整的复习一遍 ###一、运算器的组成 1、算术逻辑单元(ALU) 2、暂存寄存器，或者叫锁存器，对程序员透明(用户不可见) 3、累加寄存器 4、通用寄存 ......

###一、指令寻址和数据寻址 ####1、指令寻址 顺序寻址 通过程序计数器PC+1(1个指令字长)，自动形成下一个指令的地址 ####2、指令寻址 跳跃寻址 通过转移类指令实现。跳跃的结果是当前指令修改PC值，所以下一条指令仍然通过PC给出 ####3、数据寻址 数据寻址 数据寻址是指如何在指令中 ......