北邮复试笔试复习

Posted on | Post modified: | In | Visitors:
Words count in article: 4,656 | Reading time ≈ 16分钟

这是我自己复习的时候做的笔记，需要的同学可以简单浏览，最主要的还是多去做真题。

第一门：软件工程

导学：软件开发过程:6点

  • 做什么：需求分析
  • 怎么做：系统设计
  • 具体做：系统开发
  • 检查对不对：测试人员
  • 让用户用：工程实施人员
  • 维护系统：系统维护人员

软件工程概述

软件的定义：软件=程序+数据+文档

软件的分类

  1. 系统软件：操作系统、设备驱动程序、通信处理程序
  2. 中间件软件：各种中间件，应用服务器
  3. 应用软件：特定领域内开发，为特定目的服务的一类软件

软件工程三要素

  1. 方法：如何做的技术
  2. 工具：软件支撑环境
  3. 过程：综合软件工程的方法和工具

八条一般原理

1.抽象 2.信息隐藏 3.模块化 4.局部化 5.确定性 6.一致性 7.完备性 8.可验证性

软件生命周期模型

  • 瀑布模型：阶段性顺序串行
  • 原型方法：通过小型原型软件添枝加叶
  • 演化模型：综合瀑布模型和原型方法，两次开发。
  • 增量模型：建立原型然后增量更新
  • 螺旋模型：引入了明确的风险管理的四个象限（制定计划、风险分析、实施工程、客户评价）
  • 喷泉模型：佛系开发，无章法。
  • 构建组装模型：模块化组件开发
  • 快速应用开发模型：快速增量型开发
  • 统一过程模型：博采众家之长

  • 敏捷模型：一种态度，非方法论

    极限编程：最新理论成果

    • 小版本高速迭代
    • 简单设计
    • 结对编程
    • 代码共有

系统需求分析和可行性分析

系统需求分析和可行性分析的目的：明确系统是否值得做，避免投资损失。

  • 需求规格说明书：软件验收的依据（不包括可行性研究）；软件要做什么的共同理解；软件设计的依据

可行性分析：经济、技术、法律、实施

技术可行性分析：开发风险、资源可用性、技术条件

软件需求分析

需求分析的操作性原则

  • 问题的信息域必须被表示和理解，即数据模型(ER图)
  • 软件将完成的工程必须被定义，即功能模型(数据流图)
  • 软件的行为必须被表示，即行为模型(状态迁移图)

结构化需求分析

数据建模：实体关系图（ER图）把用户的数据要求表达出来所建立的概念性的模型

  • 第一范式：每个属性值都是不可在分的最小数据单位（详细至极）
  • 第二范式：非主属性完全依赖于关键字（非主属性开始拆分出去）
  • 第三范式：非主属性相互独立，消除函数依赖（关系通过外键连接，形成多个关系集合）

软件设计

总体设计包括：处理方式设计；数据结构设计；可靠性设计：

模块化：

  • 模块的三个基本属性：功能、逻辑、状态
  • 度量准则：模块间的耦合和模块间的内聚
    • 内聚:模块功能强度的度量：最低为巧合内聚，最高为功能内聚
    • 耦合：模块之间的相对独立性
      • 最好使用数据耦合
      • 完全不用内容耦合
      • 少用控制耦合

结构化设计方法

  • 扇入：是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程度高。
  • 扇出: 是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高。

用例图–功能需求模型– 用例模型–领域模型–识别系统–系统操作契约

面向对象基本思想：一切都看成是对象

面向对象 = 对象 + 类 + 继承 + 通信

  • 对象：类的实例
  • 类：
  • 关联和链
  • 继承/泛华
  • 聚合

几种经典的面向对象的分析和设计方法

  • OOA/OOD（面向对象分析、面向对象设计）：概念清晰，简单易学
  • Booch方法：四个主图（实体）和两个辅图（状态）
  • 对象建模技术（OMT）
  • 面向对象软件工程方法（OOSE）

统一建模语言UML（类似于状态图）

  • 静态图：
    • 用例图
    • 类图
    • 对象图
    • 构件图
    • 部署图
  • 动态图：
    • 顺序图
    • 协作图
    • 状态图
    • 活动图

面向对象分析

综述

用例图->功能需求模型->用例模型->领域模型->识别系统操作->建立系统操作契约

  1. 用例建模
  2. 创建领域类型
  3. 绘制系统顺序图
  4. 创建系统操作契约

面向对象设计

模型的层次化

面向对象设计原则

  1. 单一职责原则(SRP)：就一个类而言，应该仅有一个引起它变化的原因
  2. 开闭原则：软件实体应该是可以扩展但是不可以修改的。
  3. 里氏替换原则：子类可以替换父类并出现在父类能够出现的任何地方。
  4. 依赖倒置原则：高层模块不应该依赖于底层模块，二者都应该依赖于抽象；抽象不应该依赖于细节，细节应该依赖于抽象。
  5. 接口隔离原则:采用多个接口好于采用一个接口来涵盖多个业务方法
  6. 组合/聚合复用原则：在一个新对象里面使用一些已有对象，使之成为新对象的一部分。（达到复用目的）
  7. 迪米特法则（最少知识法则）：一个对象应当尽可能少的了解其他对象。

设计用例实现方案

软件实现

  • 程序设计语言与集成开发环境
  • 程序设计方法
    • 结构化程序设计方法：自顶向下，逐步求精
      • 三种基本控制结构：顺序、选择、重复
    • 面向对象程序设计方法
  • 程序设计风格
  • 程序效率

    指程序执行速度和占用的内存存储空间

软件测试

  • 软件测试基础：发现错误而非证明软件正确
  • 软件的正确性：软件产品达到预期的功能
  • 软件测试不包括对代码进行调试

    软件测试方法与技术

  • 静态测试
  • 动态测试
    • 黑盒测试：单纯从外部
      • 等价类划分
      • 边界值分析
      • 错误推测法
      • 因果图
    • 白盒测试：证明内部操作和内部工作流程
      • 基本路径测试：最强
      • 语句覆盖：最弱
      • 判断覆盖
      • 条件覆盖
      • 判断-条件覆盖
      • 条件组合覆盖

软件测试过程

  • 单元测试：白盒为主，黑盒测试为辅
  • 集成测试：测试所有模块组成的系统
  • 确认测试：验证软件的有效性

  • 系统测试：不同实际运行环境下测试

    • 恢复测试
    • 压力测试
    • 性能测试
    • 安全测试

  • 何时停止测试：一定测试时间内出故障的次数。

非重点

面向对象的测试方法

程序的静态分析方法

软件调试方法

软件测试工具

软件的可靠性

第二门：编译原理

编译概述

  1. 编译、解释和翻译的概念
  • 编译：把源程序转换成等价的目标程序的过程(高->低)
  • 解释：解释执行源程序，不生成目标程序（python）
  • 翻译：将用某种语言编写的程序转换成另一种语言形式的程序的程序（高->高、低->低）
  1. 编译的阶段、任务、典型结构
    1. 分析阶段:
      • 词法分析：从左到右一个字符一个字符地读入源程序
      • 语法分析：将单词序列组合成各类语法短语
      • 语义分析:对结构上正确的源程序进行上下文有关性质的审查
    2. 综合阶段：得到与源程序等价的目标程序
      • 中间代码生成：一种易于产生、翻译的抽象机器程序（三地址码等）
      • 代码优化
      • 目标代码生成：把中间代码变换成依赖具体机器的目标代码
    3. 符号表的管理
    4. 错误诊断和处理
  2. 编译程序的伙伴工具&遍
    • 预处理器：第一遍找出所有标识符。
    • 汇编程序：第二遍将操作码翻译为机器代码
    • 连接装配程序

词法分析

词法分析器的作用

词法分析期的作用：扫描源程序的字符流识别出单词符号

记号、模式

记号：某一类单词符号的编码。（标识符为id,数字为num）
模式：某一类单词符号的构词规则。

词法分析器的状态转换图

语法分析

语法分析程序:输入记号序列输出语法分析树

chomsky文法：

  • 0型文法：无限制文法（图灵机识别）
  • 1型文法：上下文有关文法（线性界限自动机识别）
  • 2型文法：上下文无关文法（下推自动机接受）
  • 3型文法：正规文法（有限状态自动机）

推导与归约

最右推导为规范推导，最左规约为规范规约

A.自顶向下分析方法:从树根到叶子来建立分析树

  1. 要进行确定分析，则文法必须无左递归和回溯

    • 消除左递归：避免死循环
    • 消除回溯：提取公共左因子，判断是否为LL(1)文法；提高分析效率

  2. LL(k)文法：

    • 最左推导
    • 从左到右扫描源程序
    • 每次向前查看k个字符。

  3. 预测分析法：预测分析表的构造，反序入栈；

B.自底向上分析方法：从树叶到树根来分析树

  1. 可规约串在规范归约分析法中是句柄，在算符优先分析法中是最左素短语；

  2. 算符优先分析法

    • First集和Follow集
    • 短语：不同层的语法树中叶子节点组成的符号串
    • 直接（素）短语：不同层的语法树中节点不在包含其他节点有子树
    • 句柄：最左直接短语
    • 句型：叶子节点大集合

  3. LR（k）分析技术:

    • 上下文无关文法：G(V,sigma,R,S)[非终结符，终结符，开始变量，规则/产生式]
    • L表示自左至右扫描输入符号串
    • R表示最右推导的逆过程
    • k表示输入符号的个数
  4. LR(0)分析
    • 指明对活前缀的识别状态，分为归约、移进、待约和接受项目
    • 没有移进规约冲突和归约归约冲突则是LR（0）文法
  5. SLR（1）分析法
    • 在LR(0)分析法的基础上向前查看一个输入符号，避免无脑归约
  6. LR(1)分析法
    归约仅在输入符号是搜索符时进行

语法制导翻译技术

输入符号串->分析树->依赖图->语义规则的计算顺序->计算结果

  1. 语义分析的任务：静态语义审查，执行真正的翻译（生成中间代码和目标代码）
  2. 常见中间代码：逆波兰式、三元式、四元式

语法制导定义

  • S-属性定义
  • L-属性定义（继承属性应满足的限制条件）

翻译方案

  • 构造S-属性定义的翻译方案（语义动作放在产生式右尾）
  • 构造L-属性定义的翻译方案（语义动作插入产生式之中）

语义分析

  1. 语义分析的概念
  • 编译的一个重要任务、检查语义的合法性
  • 符号表的建立和管理
  • 语义检查
  1. 符号表
  • 操作：检索、插入、定位、重定位

第三门：数据库原理

绪论

四个基本概念

  • 数据：数据库中存储的基本对象
  • 数据库：长期存储、有组织、可共享的大量数据集合
  • 数据库管理系统：用户与操作系统之间的数据管理软件
  • 数据库系统：包含数据库管理系统和数据库。

数据模型 = 数据结构 + 数据操作 + 完整性约束条件

  • 概念模型
  • 逻辑模型和物理模型

常用数据模型

  • 格式化模型
    • 层次模型（树）
    • 网状模型（图）
  • 关系模型（表）
  • 面向对象模型
  • 对象关系模型

数据库系统结构

  • 单用户DBS
  • 主从式DBS
  • C/S结构DBS
  • 分布式DBS

数据库系统的三级模式结构：（1:1:n）

  • 模式：数据库中全体数据的逻辑结构和特征的描述(一个数据库只有一个模式)
  • 外模式：数据库用户使用的局部数据的模式（一个数据库只有一个外模式）
  • 内模式：数据物理结构和存储方式的描述

关系数据库

关系数据结构及形式化定义

  • 域：相同数据类型的值的集合
  • 笛卡尔积：多个域中的交集。
  • 关系：二维表
  • 属性：二维表的一列
  • 码：能唯一标识一个元组的属性组
    • 候选码：能唯一标识一个元组的属性组，且不含多余属性
    • 主码：多个候选码之一
    • 主属性：主码的属性
    • 外码：不是表一主码，是表二的主码

关系数据理论

关系模式的形式化定义

R(U, D, DOM, F) // R:关系名 U:属性名集合 D:属性来自的域 DOM:属性向域的映象集合 F:属性间数据的依赖关系集合

函数依赖

  • 函数依赖：x可以唯一确定y
  • 完全函数依赖：x1或者x2不可以唯一确定y,但是（x1,x2）可以完全确定y
  • 部分函数依赖：x1,x2其中之一可以唯一确定y；

范式

  • 1NF:关系模式的所有属性都是不可分的基本数据项
  • 2NF:每一个非主属性完全函数依赖于码（消去了非主属性对主码的部分依赖）
  • 3NF:每一个非主属性既不部分依赖于码也不传递依赖于码（消去了非主属性对主码的传递依赖）
  • 4NF:消除了任何属性对码的传递依赖与部分依赖

关系操作

  • 查询：选择、投影、链接、除、并、交、差、笛卡尔积
  • 更新：插入、删除、修改

关系代数

  • 并：直观取并集
  • 差：直观取前者的补集
  • 交：直观取交集
  • 笛卡尔积：两者各元组的并集
  • 选择：where
  • 投影：从关系中去若干子关系组成新的关系（选多列）
  • 连接：从两个关系的笛卡尔积中选择部分元组
  • 除：获得满足关系组的属性组

关系的完整性

  • 实体完整性：属性A是基本关系R的主属性，则属性A不能取空值
  • 参照完整性：
    • 关系间的引用
    • 外码：设F是基本关系R的一个或一组属性，但不是关系R的码。如果F与基本关系S的主码Ks相对应，则称F是基本关系R的外码
    • 参照完整性规则
  • 用户定义的完整性：NOT NULL/UNIQUE/CHECK

SQL

数据查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#查询指定列
SELECT Sno,Sname
FROM Student
WHERE Sdept = 'CS'
ORDER BY Grade DESC;
#查询全部列
SELECT *
FROM Student
WHERE Sage < 20
ORDER BY Sdept ASC,Sage DESC;
#消除取值重复的行
SELECT DISTINCT Sno
FROM SC
WHERE Grade < 60;

　聚合函数：

  • where:过滤表中数据的条件；
  • group by:如何将上面过滤出的数据分组；- having:对上面已经分组的数据进行过滤的条件 ；
  • order by :按照什么样的顺序来查看返回的数据

数据库保护

授权与回收

  • 授权
1
2
3
4
#把查询Student表权限/全部权限给用户U1/所有用户
GRANT SELECT/ALL PRIBILIGES
ON TABLE Student
TO U1/PUBLIC;
  • 回收
1
2
3
4
#把用户U4修改学生学号的权限收回
REVOKE UPDATE(Sno)
ON TABLE Student
FROM U4;
  • 触发器：事件驱动

数据库恢复技术

  • 事务
    • 原子性：事务中的所有操作要么全部执行要么不执行
    • 一致性：执行事务前后数据库是一致的
    • 隔离性：每个事务都感觉不到系统中有其他事务在执行
    • 持续性：事务成功执行后对数据库的修改是永久的
  • 数据的锁定：
    • 导致数据不一致性包括：并发操作破坏了事务的隔离性
      • 丢失修改
      • 不可重复读
      • 读“脏”数据
    • 封锁
      • 排它锁（X锁）：其他事务不能读取和修改A
      • 共享锁（S锁）：其他事务只能读取A不能修改A

第四门：计算机系统结构

概念

  • 虚拟机：抽象的计算机，由软件实现，都具有指令集并使用不同的存储区域。
  • 透明性：本来存在的事物或属性，从某种角度看似乎不存在
  • 系统结构发展的影响因素：
    • 程序访存的局部性：
    • 数据访问的局部性：时间局部性&空间局部性
  • 系统结构设计中最常用的方法：大概率事件优先原理
  • 可移植性：
    • 采用系列机
    • 模拟与仿真
    • 统一高级语言

  • 提高并行性的技术途径：

    • 时间重叠
    • 资源重复
    • 资源共享

  • 流水线的性能指标

    • 吞吐率： $$P = \frac{n}{T_k}=\frac{n}{(k+n-1)\Delta T}$$
    • 加速比： $$ S = \frac{T_0}{T_k} = \frac{k*n}{k+n-1}$$
    • 效率：$$E = \frac{任务有效面积}{对应总面积}= \frac{n}{k+n-1} $$

流水线技术

  • 静态流水线（同一时间，同一种功能）&动态流水线（同一时间，不同的方式）
  • 线性流水线（串行连接，没有反馈）&非线性流水线（多加了反馈回路）

向量处理机器+互联网络+阵列机

  1. 向量处理机：在流水线处理机中，设置向量数据表示和相应的向量指令，成为向量处理机
    • 向量处理机的结构：
      • 存储器-存储器型：向量长度不受限
      • 寄存器-寄存器型：
  2. 指令级别并行：
    • Tomasulo算法：

多处理机:(后面的看不完了，请直接去刷13套题)

请zzy824喝杯咖啡
0%