复试 - Hexo

规划篇

面试篇

英语面

Teacher_1	Student
自我介绍2min	稍微超时被打断
英文说出软工开发步骤	初中口语，漏了一个

专业面

T1

Teacher_1	Student
`软件工程`
软件开发过程	√
系统设计要做什么	教材里没看到，打太极2min被怼
用到什么模型	一开始跑题了，被引导后答出
`数据库`
数据库发展历史	sorry
数据库范式最高等级	√
既然你知道5NF，说说定义	sorry，只学到BCNF
那说说BCNF定义	√
数据库模型	一开始跑题了，被引导后答出
网状模型和关系模型哪个快，原因	网状，原因答错
`思政`
社会主义核心价值观	您能提示第一个词吗（老师们笑）
那你给毛概一个定义	√

T2

Teacher_2 `C++`	Student
两个200万长度的数字相加	√
C++构造函数和析构函数	√

T3

Teacher_3 `项目`	Student
说说做过工程量最大的项目	√

复习篇

大数据&云计算

Hadoop

一个能够对大量数据进行分布式处理的软件框架

核心技术：

HDFS：存储服务，众多存储数据片段的服务器组成
MapReduce：编程模型，基于集群的高性能并行计算

特性：

高效、高可靠、高扩展、低成本、多平台、多语言

HDFS

计算机集群结构：交换机相连，包含多个计算机节点的多个机架组成

HDFS体系结构：主从结构，一个名称节点 + 若干数据节点

名称节点：管理命名空间，记录各块所在数据节点的位置
数据节点：负责数据存储和读取，自身数据保存在本地Linux系统中

HDFS缺点：大量小文件、低延迟数据访问、多用户写入文件

HDFS存储原理：

冗余数据保存：加速、可靠
数据存取策略：
- 存：(每个副本依次)上传的数据节点、不同机架节点、同机架节点
- 读：名称节点->数据节点，Api获取机架ID
数据错误与恢复：名称节点出错、数据节点、数据

HBase

一个高可靠、高性能、面相列、可伸缩的分布式数据库，存储非/半结构化的松散数据，目标处理大表

优点：实时处理、扩展性、处理非/半结构化

特点：数据存储为未经解释的字符串、仅插删查、列存储、性能伸缩性好

功能组件：

库函数：链接到每个客户端
Master主服务器：维护HBase表分区信息、Region服务器列表
Region服务器：维护自己的Region，处理客户读写请求

Hbase三层结构：Zookeeper文件 -> -ROOT-表 ->.META.表 (->用户数据表)

MapReduce

策略：分而治之，将数据集分片由Map任务并行处理

框架：主(JobTracker) 从(TaskTracker)架构

体系结构：Client、JobTracker、TaskTracker、Task Scheduler

核心函数：Map、Reduce

JAVA OOP

设计模式分类

创建型：工厂方法模式、抽象工厂、单例、建造者、原型

结构型：桥接模式、组合模式

行为型：观察者、访问者模式

设计模式六大原则

开闭原则：对扩展开放，对修改关闭

里氏代换原则：任何基类可以出现的地方，子类一定可以出现

依赖倒换原则：依赖抽象而非具体

接口隔离原则：多个隔离接口好于一个

最少知道原则：实体尽量少发生作用

合成复用原则：多用合成聚合

密码学

对密码系统四种攻击

唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击

数字签名

原理：

原始报文经散列算法生成报文摘要，经发送方私钥加密成数字签名，一同发给接收方
接收方同算法将原始报文生成报文摘要，再用发送方公钥解密附件里的数字签名，比对

功能：防止否认抵赖、篡改

混合加密

A用对称密钥加密数据，并用B的公钥加密自己的对称密钥形成数字信封，一起传过去；B逆操作

PKI

公钥基础设施是以公开密钥技术为基础，以数据的机密性、完整性和不可抵赖性为安全目的而构建的认证、授权、加密等的综合设施。

认证机构：数字证书申请签发
数字证书库：存储已签发的数字证书和公钥
密钥备份恢复系统：恢复解密密钥
证书作废系统
应用接口：应用与PKI交互

对公钥的管理：数字证书机制

VPN

将物理不同地点的网络通过Internet连接成的逻辑上的虚拟子网，被特定企业拥有，只有授权用户才能使用，数据传输经过了加密认证

技术：隧道技术、加密技术和密钥管理技术、身份认证和访问控制技术

项目

负载均衡

把高并发的流量分摊在其后的服务器集群上；

DNS轮询
CDN(内容分发网络)：发布机制同步到大量的缓存节点，并在DNS服务器上进行扩展，找到最近的缓存节点提供服务
软件负载均衡：nginx

负载均衡算法：哈希轮询随机权重

SpringCloud

Nacos：服务注册中心，保存服务所在机器和端口号
Ribbon：负载均衡，从一个服务的多台机器中选择一台
OpenFeign：基于fegin的动态代理机制，根据注解和选择机器拼接Url地址，发起请求
Sentinel：熔断降级，实现了不同的服务调度隔离，避免服务雪崩的问题
Gateway：如果前端后端调用后台系统，统一走网关进入，由网关转发请求给对应的服务

Elasticsearch

集成ES，添加IK中文分词插件
创建文章的索引仓库，先进行ik分词，分词后的词语在ES中做类似搜索引擎的搜索，利用在索引库检索标题和内容，搜出来的文章返回给前端。

计网

物理层
数据链路层(PPP、HDLC、CSMA/CD)
网络层(IP、ARP/RARP、ICMP)
传输层(TCP、UDP)
会话层
表示层
应用层(telnet、FTP、SMTP、DNS、DHCP、HTTP)

信道划分介质访问控制

FDM：将多路基带信号调到不同频率载波上，再叠加形一个复合信号

TDM：信道分成若干时间片，轮流分配（异步时分多路复用）

WDM：光纤传播不同波长光信号

CDM：用一组包含互相正交的码字的码组携带多路信号，共享频率和时间、抗干扰

CSMA/CA

适用于无线局域网802.11

过程：

发送第一个数据帧且信道空闲，等待DIFS后发送
否则执行退避算法，信道空闲时倒计时
倒计时为0时发送并等待确认，无论续/重发都要执行退避算法

预约：源站广播RTS，基站收到后广播CTS帧，许可源站并在规定时间内抑制其他站

PPP协议

拨号建立专线点对点传输，面向字节串行线路，全双工

组成：LCP(建立管理数据链路) NCP(允许多种网络层协议为网络层逻辑连接) PPP封装

只保证无差错接收，不可靠，无确认序号机制

路由算法

距离向量

所有节点定期将路由表发送给相邻节点(目的地、代价)，无则添加，近则更新

路由信息协议(RIP)：最多15跳，规模小；慢收敛；掩码必须同

链路状态

原理：每个节点有完全的网络拓扑信息，主动测试邻接节点状态，定期泛洪法向所有路由器发送信息(相邻的所有路由器链路状态)

优点：各节点使用相同原始状态数据独立计算路径，不依赖中间节点、规模伸展性

开放最短路径优先(OSPF)：收敛快；变化时才发；灵活设置不同代价

CIDR

在变长子码基础上，消除ABC类网络划分的IP地址划分方法

将网络前缀都相同的连续IP地址组成CIDR地址块，构成超网，网络前缀长度灵活，减少路由器之间路由选择信息交换

组播

一次发送单个分组到达同一个组地址的多个主机

过程：主机通过IGMP协议加入组播组；通知本地网络路由器关于要接收发送给某个组播组的分组的愿望；通过扩展路由器选择转发

特点：最大努力交付，无差错报文，仅能目的地址，硬件地址映射不唯一需IP层过滤

IGMP：使路由器知道组播成员信息

主机向组播地址发送IGMP报文，路由器接收后将组成员关系转发给其他组路由器
路由器定期探寻本局域网主机，若无响应则不转发给其他

移动IP

满足移动节点以固定IP实现不同网段间漫游

功能实体：移动节点、本地代理、外部代理

过程：

本地时依旧TCP/IP
移到外地网络后，移动节点向本地代理注册当前位置
此后本地代理将收到的信息通过隧道送到转交地址并复原交付
回到本地网时，向本地代理注销转交地址

路由器

一种具有多个输入输出端口的专用计算机，连接异构网络并完成路由转发

过程：源目的主机在同一网络，直接交付；否则按转发表给下一个路由

功能：

路由选择：根据协议构造路由表，和相邻路由器交换信息并更新维护
分组转发：根据转发表选择输出端口

TCP

可靠传输：序号 + 超时 + 重传

流量控制：滑动窗口 = 拥塞窗口 + 发送窗口

拥塞控制：慢开始、拥塞避免、快重传、快恢复

FTP

采用CS模式使得用户远程访问服务器文件，在异构网络任意计算机间传送文件

两个TCP连接：

控制21：始终打开，监听连接/传送请求
数据20：

HTTP

规定了浏览器服务器请求响应的格式规则，面相事务应用层协议

过程：

服务器进程不断监听
建立TCP连接，浏览器发送http请求报文
服务器通过http响应报文返回web信息
浏览器解释页面，TCP释放

编译原理

编译程序的五个阶段

词法分析：正则式和有限自动机，生成记号流
语法分析：上下文无关文法，分析是否符合语言语法结构，生成语法树
语义分析和中间代码产生：四元式、逆波兰式，分析语义并收集符号属性
代码优化
目标代码生成：绝对、可重定位、汇编指令代码

概念

编译前端：与源语言有关，三个分析、中间代码产生、中间代码优化、符号表建立

编译后端：与目标机有关，目标代码生成、错误处理、机器代码优化、符号表访问

正则表达式：特定运算符、对象按特定规则构成的表达式，描述词法规则

有限自动机：描述输入串被识别的过程，用状态图描述(一起始多接收)，输出为接收/拒绝，构造词法分析程序

文法

0型：图灵机

1型：上下文有关文法，线性界限自动机

2型：上下文无关文法，非确定下推自动机

3型：正则文法，有限自动机

语法分析

自上而下：

递归下降
LL：从文法开始符号出发自上而下地为输入串建立语法树

需先消除左递归(转右递归)、避免回溯(提取公共左因子？)

FIRST：候选 α 可以推导出的串的第一个终结符

FOLLOW：判断能不能将非终结符推导为 ε

自下而上：

LR：一种移进规约的自底向上分析法，不断规约句柄，本质规范规约

构造复杂执行快，及时准确发现错

Action：对于当前输入符号，移进规约接收出错

Goto：面对某符号时，新的栈顶状态

软件工程

软件生存周期

从开发软件概念起，软件使用以后，直到失去使用价值消亡为止的过程

软件定义、软件开发、软件维护

可行性分析、需求分析、软件设计、编码、软件测试、软件维护

软件开发的模型

瀑布模型

各阶段组织模式如瀑布逐级下落，完成上一阶段才能下一阶段，前阶段输出=后阶段输入

特点：阶段性、线性不可回溯、开发不灵活有风险

开发过程：计划 - 需求分析 - 设计 - 编码 - 测试 - 运行和维护

快速原型模型

快速建立反映客户主要需求的系统，让用户试用并提出意见，从而书写规格说明文档

特点：能够实现线性开发，满足客户需求

增量模型

模块化，分批完成这些增量组件(分析设计编码测试)，将整个产品分批次提交给用户

特点：用户及时了解、开发顺序灵活

螺旋模型

结合瀑布、快速原型模型，将风险分析扩展到各阶段

统一软件开发过程模型

(Rational Unified Process)是一个基于UML的面向对象开发模型。解决了螺旋模型可操作性问题，是一种重量级过程，适用于大型团体开发大型项目。

特征：迭代增量开发、用例驱动、软件体系结构为中心

敏捷模型

轻量级软件工程方法，更强调变化的必然性，通过沟通及合理机制有效响应变化

避免了传统开发过程复杂、文档繁琐，强调过程简洁、成员交流、用户反馈

极限编程(XP)：敏捷模型的典型应用，强调用户需求和团队工作，适用于需求模糊易改变、人数<10、开发地点集中。项目计划阶段：建立简洁的用户故事；设计体系架构时：采用CRC卡促进共同努力；测试方面：开发人员向用户证明代码正确而非用户找

需求分析

业务需求：客户对系统、产品高层次的目标要求
用户需求：用户使用产品必须完成的任务
功能需求：开发人员必须实现的软件功能，以便用户完成任务
非功能性需求：系统展现给用户的行为和执行的操作，产品须遵循的标准和约束

结构化分析

面向数据流的需求分析方法，基于分解抽象建立系统逻辑模型

E-R图：数据模型，实体+联系+属性
数据流图：数据流联系的功能组合，建立逻辑模型
数据字典：数据流图中各个图元的具体内容
状态转换图：行为模型

UML

用例图：包含(提取共同行为)、扩展(增强行为)、泛化(一般特殊)

类图：关联、依赖(引发改变)、泛化(父类子类)、实现(类和接口)

软件测试

原则：考虑不同用户、不同人员参与测试(杀虫剂效应)，开发测试组分开，尽早测试，回归测试

黑盒：已知功能设计规格，测试每个实现的功能是否符合要求。在接口处，不考虑内部逻辑

不正确、遗漏功能？
正确输入输出？
性能？初始化、终止性错误？

白盒：已知产品内部工作过程，测试证明每种内部操作是否符合设计规格要求。对程序逻辑路径测试

对所有执行路径测试一遍
逻辑判定用真假测试一遍
循环边界执行循环体

数据库

基本概念

1. 触发器

特殊的存储过程，通过事件触发执行。可以强化约束，维护数据完整性、一致性。

2. 存储过程

预编译的SQL语句，允许模块化设计，创建一次调用多次。通过命令对象、外部程序调用

优点：预编译效率高、重复使用减少开发量、权限控制安全、从数据库中直接调用减少网络通讯

缺点：移植性差

3. 视图

基于SQL语句的结果集的可视化的表。视图就像一个真实的表，包含行和列，字段是来自真实的表中的字段，可以向视图添加SQL语句/数据。

视图是虚表,它在存储时只存储视图的定义,而没有存储对应的数据
视图只在刚刚打开的一瞬间,通过定义从基表中搜集数据,并展现给用户

优点：

简化操作：对复杂聚合函数直接创建视图
安全性：虚拟的数据集合，且用户不能随意更改
合并分离的数据：如将分公司数据合并一个表格里

缺点：性能差（转化基本表查询）、修改限制

4. 游标

一种数据访问机制。对查询的结果集进行查询，将其看成结果集的指针，可以根据需要来回滚动，浏览需要的数据

表的连接方式

内连接：用比较运算符比较要连接的列的值的连接，不匹配的行不会被显示

左/右外连接：以一种表为基表，基表的所有行列都会显示，外表如果不匹配则列值都为NULL

全外连接：所有表的行列都会显示，条件不匹配的为NULL

自然连接：特殊的等值连接，它要求比较的分量是相同属性组，并在结果中去掉重复的属性列

交叉连接：不带WHERE 子句，返回被连接的两表所有行的笛卡尔积

三级模式和两级映像

外模式：也称用户模式或者子模式,是用户与数据库的接口。数据库的设计者把程序员用的上的接口给出来，程序员不需要关心数据库的结构，这就是外模式（视图）

概念模式：也称模式。是数据的逻辑结构和特征的描述，是所有用户的公共数据视图（SQL建表语句建出来的东西）

内模式：也称存储模式。是数据物理结构和存储方式的描述，是数据在数据库内部的组织方式。

外模式/模式映像：定义之间的对应关系，保证数据逻辑独立性，如修改表结构无需更改外模式(应用程序)

模式/内模式映像：定义逻辑/存储结构对应关系(唯一)，物理独立性。

数据库模型种类

层次模型：1:n，树形结构表示实体间的联系

网状模型：m:n，用指针来确定网状连接关系

关系模型：用表格结构表达实体集，用外键表示实体间联系
优点：严格的数学概念基础；结构简单清晰，易懂易用；存取路径对用户透明，数据独立/安全性好，简化数据库开发工作
缺点：查询效率不如非关系数据模型

数据库恢复实现方式

建立冗余数据：

数据转储：静态、动态、海量、增量
登记日志文件

各类故障恢复策略

事务故障：事务未完成
利用日志文件撤销：反向扫描，作逆修改

系统故障：①未完成事务的更新写入DS ②已提交事务更新还在缓冲区
撤销未完成，重做已完成：正向扫描撤销/重做队列，反向撤销，正向重做

介质故障：硬盘数据破坏
重装数据库，重做已完成事务

并发控制技术

封锁：事务操作前，申请加锁，释放前其他事务不能更新
①写锁：不能后加锁，不能读写
②读锁：只能后加读锁，只能读

时间戳：每个事务一个唯一时间戳，按顺序提交给DBMS

死锁问题

死锁预防：一次封锁法(降并发度、难确定)，顺序封锁法(动态变化，难确定)

死锁诊断与接触：超时法(误判、不及时)，等待图法(类比资源分配图有环则锁，撤销代价最小的事务及锁，并恢复该事务数据)

封锁协议
一级：修改前加X锁，事务结束释放——防止丢失修改
二级：读前加S锁，读后释放——防止读脏数据
三级：读前加S锁，事务结束释放——防止不可重复读

非关系型数据库特点

不需预定义模式(数据模式&表结构)
无共享架构：划分后存在各本地服务器，无需网络传输，高性能
弹性可扩展：动态增删节点，无需停机
需要分区：分散在多个节点，提高并行性，防止单点失效
异步复制：基于日志，尽快写入一节点，不保证一致性
BASE模型：BA基本可用，S软状态(可一段时间异步)，E最终一致性

非规范化技术

适当降低关系模式范式，提高数据库效率，可适当数据冗余

优点：减少查询时连接、减少外键索引数量

缺点：数据冗余、影响数据库完整性、增加存储空间占用

计组 OS

系统调用

提供了用户程序和操作系统之间的接口，实现两者通信，并取得OS服务

处理步骤:

用户态转为系统态，然后由硬件和内核程序进行系统调用的一般性处理,即首先保护被中断进程的 CPU 环境,将处理机状态字 PSW、程序计数器 PC、系统调用号、用户栈指针以及通用寄存器内容等压入堆栈;再然后将用户定义的参数传送到指定的地址保存起来
分析系统调用类型,转入相应的系统调用处理子程序
子程序执行完后，恢复被中断的 CPU 现场,然后返回被中断进程

硬中断和软中断

软中断是程序运行时其他程序对它的中断;硬中断是设备对它的中断

软中断发生的时间由程序控制；而硬中断随机

硬中断的中断号由中断控制器提供的；软中断由指令直接给出

管程

定义：一组数据以及定义在数据上的操作组成的软件模块，这组操作能初始化/修改管程数据并同步进程

组成：共享结构数据说明、一组操作过程、初始化

特性：一次一个程序执行、通过管程序访问内部数据

虚拟存储器

是计算机系统内存管理的一种技术,虚拟存储器将主存或辅存的地址空间统一编址,形成一个庞大的地址空间,在这个空间内,用户可以自由编程,二不必在乎实际的主存容量和程序在主存中实际的存放位置。

优点：可以弥补物理内存大小的不足;一定程度的提高反映速度;减少对物理内存的读取从而保护内存延长内存使用寿命
缺点：占用一定的物理硬盘空间;加大了对硬盘的读写;设置不得当会影响整机稳定性与
速度。

存储器地址选择方式

线选法：低位地址线直接连到芯片，实现片内选址；高位直接输出片选信号，地址空间不连续、重叠；

译码法：低位同，高位译码器输出信号，增加电路复杂；

与外设信息交换的问题

接口电路解决：

速度：锁存器和缓冲器
信号电平：电平转换电路
信号格式：
时序不匹配：时序控制电路

I/O寻址方式

存储器映像寻址：统一编址，访存指令可访问；占用内存空间；

I/O独立编址：不占内存，程序可读性好；设立IO读取指令，并区分两种

提高访存速度措施

高速主存、双端口存储器、单体多字、多体并行

Open打开文件的过程

若已打开：进程文件打开表为a分配表项，指向系统打开表；向PCB分配fd文件描述符

未打开：读入文件目录，获取FCB并将文件读入内存；系统打开表分配表项，指向FCB，后同1

程序装入方式

源代码编译成目标模块

目标模块与库函数链接成装入模块

通过装入程序装入内存

绝对装入：编译时知道内存物理地址，只能单道程序

静态重定位：在装入时一次完成，逻辑地址+内存的起始地址=物理地址

动态重定位：装入内存的是相对地址，程序执行时依靠硬件地址变换机构得出