admin 管理员组

文章数量: 1086019

408（持续更新）

数据结构

时间复杂度

线性表：

具有随即存储特性，查找时间复杂度为O（1）

单链表：尾插法

增加尾指针，申请空间，插入

栈及其应用

1.根据限定条件判断合法性：

根据输入序列判断，是否有可能的输出序列

2.最小容量：

题目：设栈S和队列Q，其状态为空，元素a1，a2，a3，a4，a5，a6依次入栈，出栈的元素则进入队列Q，若6个元素出列顺序是a2 ，a3 ，a4 ，a6， a5， a1，则栈的容量至少是（）。

3

3.表达式求值***

4.中缀表达式转换为后缀表达式过程

2*（9+6/3-5）+4转化为后缀表达式2 9 6 3 / +5 - * 4

5.数制转换?

6.括号匹配?

7.表达式求值（中后）?

8.递归调用?

循环队列（两种情况

1.判断Q.rear==Q.front

2.(Q.rear+1)%maxsize ==Q.front

输入输出受限的双端队列

输出受限：可在一端插入删除，另一端仅可以插入

输入受限：反之

 

树

树的高度 log2(n)+1

1.节点数等于所有节点度+1

2.度为m的树中，第i层至多有

计算机网络：

1.基本概念（分层结构）

逻辑功能上分为资源子网和通信子网，通信子网对应物理层，数据链路层，网络层。

物理组成上：硬件，软件，协议

广域网、局域网区别：覆盖范围不同；协议和网络技术不同。广域网采用点对点技术，局域网广播技术

·mtu：最大传输单元，

mss:Tcp给IP层的最大分段大小

 

2.物理层传输介质：

双绞线：胶合目的：减少两根导线的电磁干烧

IEEE802.3：规定采用同轴电缆作为介质，不能超过500M

3.ISO与TCP/ip模型区别

iso:应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

TCP/ip：应用层、传输层、网际层、数据链路层、物理层

网际层：仅支持无连接，网络层：支持无连接和面向连接

TCP传输层：支持无连接和面向连接

iSO：仅支持面向连接

4.曼彻斯特编码:跃变为1?

不会

曼彻斯特编码:1前高后低 0 前低后高

 

4B/5B encoding不会

目标：如何在解决基线漂移和时钟漂移的同时，使编码效率尽量高一些 思想：在比特流中插入额外的比特而打破一连串的 0 或 1 方法：用 5 个比特来编码 4 个比特的数据，然后再传给接收方 5 比特代码由以下方式选定：每个代码最多有一个前导 0，并且末尾最多有 2 个 0 这样在连续传送时，在传输过程中任何一段 5 比特代码，连续的 0 最多有 3 个. 最后使用 NRZI 编码进行传输，就解决了问题 4B/5B 编码的效率为 80%

5.奈奎斯特定理、香农定理:

有关传输速率上限的两个定理（注：带宽——频率范围） Nyquist 定理： D(比特率) = 2 f(带宽) log2 N(电压种数) 无噪音情况下的最大传输速率 Shannon 定理： C(比特率) = B log2 (1 + S(信号) / N(噪声)) 引入信噪比 = 10 * lg (S/N)

码元串书速率(波特率):

信息传输速率(比特率):美妙传送的二进制位数

比特率 = 波特率* log2电平数(相位数)

6.电路交换\报文交换\分组交换

电路交换:整个报文的比特流连续的从源点直达终点,好像在一个管道中传送

报文交换:整个报文先传送到相邻节点,全部存储下来后查找转发表, 转发到下一个节点

分组交换: 单个分组(整个报文段的一部分)传送到相邻节点,存储下来查找转发表, 转发到下一个节点 (灵活性最好,时延小)

牛客错题

物理层：集线器，转发器

数据链路层：网桥

网络层:路由器，网关

CSMA/CD适用于有线网络，而CSMA/CA则广泛应用于无线局域网（具体原因请见王道2017版单科书P90）。其他选项关于CSMA/CD的描述都是正确的。

7.物理层接口与物理层设备????

 

(每块网卡出厂就有全球唯一的mac地址)

路由器:隔离广播域(网络层设备)

交换器、网桥（链路层设备），路由器可以隔离冲突域

集线器(Hub)、中继器都不能隔离 （中继器放大数字信号，放大器放大模拟信号）

网卡实现主要功能在物理层、数据链路层

8.HDLC的零比特填充法：5个0加个1

12MAC帧的格式

常见的mac有两种格式

1.dix etherent标准 一种是IEEE的802.3标准 两种帧的结构

16网络层的功能

主要任务:

把分组从源端 传到目的端，为分组交换网上的不同主机提供通信服务

传输单位：数据报

路由选择和分组转发

 

18.IP子网划分、CIDR

1.划分子网

划分前 ip地址为两级结构（<网络号><主机号>）

划分后ip地址为三级结构（《网络号》《子网号》《主机号》）

2子网掩码

A类：255.0.0.0

b类：255.255.0.0

C类：255.255.255.0

3.计算？？

！！！！！！

例如

 

20.ARP,DHCP,ICMP协议

一地址解析协议ARP

数据库

1.语法 desc 倒叙序

SELECT DISTINCT 列名称 FROM 表名称
返回唯一不同的 值

实例 2

以字母顺序显示公司名称（Company），并以数字顺序显示顺序号（OrderNumber）：

SELECT Company, OrderNumber FROM Orders ORDER BY Company, OrderNumber

实例 3

以逆字母顺序显示公司名称：

SELECT Company, OrderNumber FROM Orders ORDER BY Company DESC

实例 4

以逆字母顺序显示公司名称，并以数字顺序显示顺序号：

SELECT Company, OrderNumber FROM Orders ORDER BY Company DESC, OrderNumber ASC

1.INSERT INTO 语句

INSERT INTO 语句用于向表格中插入新的行。

语法

INSERT INTO 表名称 VALUES (值1, 值2,....)

我们也可以指定所要插入数据的列：

INSERT INTO table_name (列1, 列2,...) VALUES (值1, 值2,....)

2.Update 语句

Update 语句用于修改表中的数据。

语法：

UPDATE 表名称 SET 列名称 = 新值 WHERE 列名称 = 某值

3.DELETE语句

delete用于删除表中的行

delete from 表名称 Where 列名 = 值

2.高级语法/

1.SQL TOP子句

LIKE 操作符实例

例子 1

现在，我们希望从上面的 "Persons" 表中选取居住在以 "N" 开始的城市里的人：

我们可以使用下面的 SELECT 语句：

SELECT * FROM Persons
WHERE City LIKE 'N%'

 

2.group by和having使用

having是在 group by 后面使用的

牛客题目

1下面哪些字符最可能会导致sql注入?

‘

2某打车公司将驾驶里程（drivedistanced）超过5000里的司机信息转移到一张称为seniordrivers 的表中,他们的详细情况被记录在表drivers 中，正确的sql为（）

select * into seniordrivers from drivers where drivedistanced >=5000

查排第几

#含义是跳过2条取出1条数据，limit后面是从第2条开始读，读取1条信息，即读取第3条数据
select * from students order by grades desc limit  2,1

操作系统:

概述

开机后操作系统加载到RAM(内存)

批处理交互性差

现代oS两个最基本特征: 并发与共享,互为存在的条件.(虚拟 异步)

不属于多道程序设计的基本特征:顺序性(为单道程序设计特征, 多道为竞争 )

内核态 用户态

用户态:算态（目态）

用户运行一个程序，该程序创建的进程开始时运行自己的代码，处于用户态。如果要执行文件操作、网络数据发送等操作必须通过write、send等系统调用，这些系统调用会调用内核的代码。进程会切换到Ring0，然后进入3G-4G中的内核地址空间去执行内核代码来完成相应的操作。内核态的进程执行完后又会切换到Ring3，

 

内核态：

管态

PSW:程序状态寄存器

 

 

中断和异常：

中断由外因引起，异常由CPU本身原因引起

主程序调用子程序完全是软件处理过程

访管中断：

处理机调度（进程调度没看）

处理机调度层次

1高级调度

对作业调度 将作业调入内存为他们创建进程，分配必要的资源

2.低级调度

对进程调度，决定就就绪队列中的进程获得处理机

3中级调度：

对内存调度，提高内存利用率和吞吐量，作用：暂时不能运行的、进程，调至外村等待

 

作业

作业：批处理系统中，作业为基本单位

作业步：作业需要通过一系列操作的顺序才能得到结果，把其中一步称为一个作业步

作业控制块：JCB 和PCB相似 作业标识用户名称账号类型作业类型，作业专业 调度信息，资源需求

运行阶段状态：收容状态 运行状态 完成状态

作业调度目标

根据jcb中的信息，检查系统中的资源能否满足作业队资源的需求，并且按照一定的调度算法，从外村的后备队列中选取某些作业调入内存

常见算法：

先来先服务：FCFS 根据作业到达的先后次序来进行调度

短作业优先：SJF 作业越短，优先级越高， 长短是根据作业所要求的时间来衡量的

缺点：对长作业很不利 容易出现饥饿现象，需要知道作业的时间，

优先级调度算法：PSA 根据作业的紧迫程度 赋予作业优先级 进行调度

高响应比优先算法： HRRN

HRRN为每一个作业引入了一个动态优先权。该优先权的变化规律如下: 优 先 权 = （等待时间+要求服务时间） / 要求服务时间 == 响应时间 / 要求服务时间

进程同步和互斥

临界资源：把一次仅允许一个进程使用的资源成为临界资源

例子：打印机 变量 进程

对临界资源访问：必须互斥的进行

临界资源的访问过程分为四个部分：

进入区：在进入区检查可否进入临界区，若可以进入，应设置正在访问临界区的标志

临界区：进程中访问临界资源的那段代码

退出区：将正在访问临界区的标志珊瑚

剩余区：代码中的剩余部分

同步

称直接制约关系，为完成同一个任务的两个进程或者多个进程，因为需要再某些位置上协调他们的工作次序而等待，传递信息所产生的制约关系，进程间的直接制约就是源于他们直接的相互合作

例如：进程A进入单缓冲区向进程B提供数据，当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据松鼠缓冲区，进程B被唤醒

 

互斥

间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后 ，另一个进程在允许去访问临界资源

同步机制准则：

空闲让进，忙则等待，优先等待，让权等待（当进程不能进入临界区时，应立即释放处理器，防止进程忙等待）

实现临界区互斥的基本方法

算法一：单标志

算法二：双标志先检查

算法三：双标志后检查

经典进程同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

 

 

死锁

产生的根本原因：

两个或者两个以上的线程，因抢夺资源而产生相互等待的现象

产生的四个条件

1.互斥

2.占有且等待，占有资源不释放

3.不可抢占，其他线程不能强行抢占线程的资源

4.循环等待条件：线程T1在持有资源A1，同时在请求等待获取资源B，线程T2在持有资源B,然后在请求等待线程T1的持有资源，形成了交叉闭环申请。

处理死锁的方法有以下四种：

1.死锁预防：

思索避免：银行家算法

死锁检测

死锁解除；强行回收占有资源

破坏死锁产生的四个条件之一即可。 破坏请求与保持条件：让进程一次性申请所有的资源。（资源一次性分配） 破坏不剥夺条件：拥有部分资源的进程在申请其他资源被拒绝时，可以主动的释放它现有的资源。（破坏不可剥夺条件） 破坏循环等待条件：给资源进行编号，进程按照编号顺序获取资源，释放资源时反序释放（资源有序分配法）

 

内存管理

连续分配方式：动态分区分配

连续指为用户分配一段连续的内存空间

动态分区分配 ： 根据实际的需要动态的分配内存空间，使分区大小和作业的大小相等

分区分配中的数据结构

常用数据结构

空闲分区表：用于记录每个空闲分区的情况

每个空闲分区一个标目，分区大小，分区序号，分区始址

空闲分区链：个分区头部设置前向指针，尾部设置后向指针，使得所有空闲分区连接成双向链

为了检索方便，在分区尾部设置状态为，空闲为0 被分配出去为1

分区分配算法

 

虚拟存储管理技术之虚拟页式存储管理

页面淘汰算法：

先进先出页面淘汰算法FIFO

做法：淘汰最早进入内存的页面

认为：随着时间在内存中时间越久，访问的可能性月底

但实际上可能会把经常访问的淘汰出去

最近最久未使用页面淘汰算法LRU

做法：淘汰最长时间未被访问的页面

认为：刚刚被访问的页面，不久的将来被使用的可能就行就越大

最近最少使用页面淘汰算法LFU

做法：淘汰当前使用的最少的页面

认为：在一段时间使用的比较多的页面，在不久的将来使用的可能性就越大

最优页面淘汰算法OPT

做法：把以后不再使用的或最长时间内不会用到的页面淘汰出去

前提：已知作业运行时的页面走向

抖动：刚换出又要换入内存

本文标签： 408（持续更新）