[网络协议]#软件设计师 #软考 #高频知识点总结 #上午题常考知识点 #下午题分析总结

一、软件工程

• 【敏捷方法】

  • 极限编程XP（轻量高效低风险柔性可预测）
    • 四大价值观：沟通，简单，反馈，勇气。
    • 五大原则：快速反馈，简单性假设，逐步修改，提倡更改，优质工作。
    • 十二个最佳实践：计划游戏，小型发布，隐喻，简单设计，测试先行，重构，结对编程，集体代码所有制，持续集成，每周工作40小时，现场客户，编码标准。
  • 水晶法（每一个项目需要一个不同的策略约定和方法）。
  • 并列争球法（Scrum，30天一个小冲刺）
    • 开发流程：Product Backlog(产品待办事项) → Sprint Backlog(Sprint待办事项) → Sprint(冲刺迭代) → Release(发布)
  • 自适应软件开发（ASD，6个基本原则）
  • 敏捷统一过程（AUP，大型上连续，小型上迭代）。

• 【概要设计和详细设计】

  • 概要设计：确定软件系统的结构，进行模块划分，确定每个模块的功能、接口以及模块间的调用关系。
  • 详细设计：算法设计，对模块内的数据结构设计，数据库物理设计，说明书，评审。

• 【各种开发模式适用的场合】

  • 瀑布模型：非常明确的需求，严格的文档，评审。
  • 喷泉模型：面向对象。
  • 快速原型：需求不够明确，项目不是很大，“抛弃”式开发。
  • 演化模型：渐进式开发。
  • 螺旋模型：引入风险评估，大中型开发，融合了瀑布模型和演化模型。
  • 统一过程：用例驱动，架构为中心和受控的迭代式增量开发。
    • 四个阶段：初始阶段，精化阶段，构建阶段，提交阶段。

• 【软件质量模型的6大特性】

  特性	说明	评价指标
  功能性		适合性、准确性、互用性、依从性、安全性
  可靠性	产品在规定的条件下，在规定的时间内完成规定功能的能力	成熟性、容错性、易恢复性
  易用性	在指定使用条件下，产品被理解、 学习、使用和吸引用户的能力	易理解性、易学性、易操作性
  效率性	在规定条件下，相对于所用资源的数量，软件产品可提供适当性能的能力	时间特性、资源特性
  软件维护性	“四规”， 在规定条件下，规定的时间内，使用规定的工具或方法修复规定功能的能力	可理解性、可测试性、稳定性、可修改性
  软件可移植性	从一种环境迁移到另一种环境的能力	适应性、易安装性、一致性、易替换性

  由于功能性比较抽象，所以最好是用排除法解题，如果题目所描述的情况不在可靠性、易用性、效率性、维护性、可移植性中那么属于功能性。

• Gantt图不能清晰的描述各任务之间的依赖关系。

  Pert图不能清晰的描述各个任务之间的并行情况。

• 【CMMI成熟度模型】

  阶段式模型

  【记忆口诀】初级程序员，可重复写程序，现已定义了管理策略的来优化程序设计。

  等级	名称	核心
  1	初级	混乱不可预测
  2	可重复级	建立基本的项目管理和实践来跟踪项目费用、进度和功能特性
  3	已定义级	使用标准开发过程（或方法论）构建（或集成）系统
  4	已管理级	管理层寻求更主动地应对系统的开发问题。重点关注产品和过程质量。
  5	优化级	连续地监督和改进标准化的系统开发过程

  连续式模型

  等级	名称	说明
  CLO	未完成的	过程域未执行或未得到CL1中定义的所有目标。
  CL1	已执行的	其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标。
  CL2	已管理的	其共性目标是集中于已管理的过程的制度化。根据组织级政策规定过程的运作将使用哪个过程，项目遵循已文档化的计划和过程描述，所有正在工作的人都有权使用足够的资源，所有工作任务和工作产品都被监控、控制、和评审。
  CL3	已定义级的	其共性目标集中于已定义的过程的制度化。过程是按照组织的裁剪指南从组织的标准过程中裁剪得到的，还必须收集过程资产和过程的度量，并用于将来对过程的改进。
  CL4	定量管理的	其共性目标集中于可定量管理的过程的制度化。使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的质量目标作为管理准则。
  CL5	优化的	使用量化(统计学)手段改变和优化过程域，以满足客户的改变和持续改进计划中的过程域的功效。

• 【维护类别】

  维护类别	说明
  正确性维护	为了识别和纠正软件错误、改正软件性能上的缺陷、排除实施中的误使用，进行的诊断和改正错误的过程。
  适应性维护	在使用过程中，外部环境（新的硬、软件配置）、数据环境（数据库、数据格式、数据输入/输出方式、数据存储介质）可能发生变化。为使软件适应这种变化，而去修改软件的过程。
  完善性维护	在软件的使用过程中，用户往往会对软件提出新的功能与性能要求。为了满足这些要求，需要修改或再开发软件，以扩充软件功能、增强软件性能、改进加工效率、提高软件的可维护性。
  预防性维护	指预先提高软件的可维护性、可靠性等，为以后进一步改进软件打下良好基础。

• 【结构化开发】

  类别	说明
  体系结构设计	定义软件系统各主要部件之间的关系。
  数据设计	基于E-R图确定软件涉及的文件系统的结构及数据库的表结构。
  接口设计（人机界面设计）	软件内部，软件和操作系统间以及软件和人之间如何通信。
  过程设计	系统结构部件转换成软件的过程描述。确定软件各个组成部分内的算法及内部数据结构，并选定某种过程的表达形式来描述各种算法。

• 【成本估算模型】

  	说明
  Putnam 模型	一种动态多变量模型，它是假设在软件开发的整个生存期中工作量的分布。
  COCOMO 模型	结构性成本模型，是最精确、最易于使用的成本估算模型之一。又分为以下三类：↓
  基本 COCOMO 模型	一个静态单变量模型，它是对整个软件系统进行估算。
  中级 COCOMO 模型	一个静态多变量模型。它将软件系统模型分为系统和部件两个层次，系统由部件构成，它 把软件开发所需人力（成本）看作是程序大小和一系列“成本驱动属性”的函数。
  详细 COCOMO 模型	它将软件系统模型分为系统、子系统和模块 3 个层次，它除包括中级模型所考虑的因素外， 还考虑了在需求分析、软件设计等每一步的成本驱动属性的影响。

• 【软件测试】软件测试的目的是为了发现尽可能多的缺陷，而不是为了证明软件的正确性。

• 【文档】

  类别	具体文档
  系统开发人员与系统分析人员在系统规划和系统分析阶段的沟通	总体规划和开发合同
  系统开发人员与项目管理人员在项目期内进行沟通的文档	系统开发计划，包括工作任务分解表、PERT图、甘特图和预算分配表等。
  系统开发人员与系统测试人员沟通的文档	测试计划

• C/S(Client/Server)：客户端服务器架构。

  B/S(Browser/Server)：浏览器服务器架构。

• 【内聚/耦合】

  划分模块其中的一个准则就是高内聚低耦合。

  内聚(从弱到强)	说明 (内聚是模块功能强度的度量)
  偶然内聚/巧合内聚	指一个模块内的各处理元素之间没有任何联系。
  逻辑内聚	指模块内执行若干个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。
  时间内聚	把需要同时执行的动作组合在一起形成的模块。
  过程内聚	指一个模块完成多个任务，这些任务必须按指定的次序执行。
  通信内聚	指模块内的所有处理元素都在同一数据结构上操作，或者各处理使用相同的输入数据或产生相同的输出数据。
  顺序内聚	指一个模块中的各个处理元素都密切相关于同一各功能且必须顺序执行，前一个功能元素的输出就是下一个功能的输入。
  功能内聚	指模块内的所有元素共同作用完成一个功能，缺一不可。

  耦合(从弱到强)	说明 (耦合是对模块间关联程度的度量)
  内容耦合	内容重叠
  公共耦合	访问同一公共区域.
  外部耦合	访问同一外部变量，与公共耦合不同的是，一个是区域，一个是变量。
  控制耦合	A模块控制B模块
  印记耦合	传递的信息是子结构（结构体、对象等）。
  数据耦合	通过数据参数（注意是参数，不是区域也不是子结构！）联系。
  非直接耦合	不直接联系。

• 【白盒测试】

  注意题目中需要满足什么类别的覆盖，否则盲目做，就会错错错… …

  覆盖分类	说明
  语句覆盖	设计出来的测试用例要保证程序中的每一个语句至少被执行一次。
  判定覆盖（分支覆盖）	设计的测试用例要保证让被测试程序中的每一个分支都至少执行一次。
  条件覆盖	设计的测试用例能使每个判定中的每一个条件都获得可能的取值，即每个条件至少有一次真值、有一次假值。
  判定条件覆盖	设计的测试用例可以使得判断中每个条件所有的可能取值至少执行一次（条件覆盖），同时每个判断本身所有的结果也要至少执行一次（判定覆盖）。
  组合覆盖（条件组合覆盖）	设计的测试用例应该使得每个判定中的各个条件的各种可能组合都至少出现一次。
  路径覆盖	设计的测试用例可以覆盖程序中所有可能的执行路径。

• 【逆向工程】逆向工程产品设计可以认为是一个从产品到设计的过程。简单地说，逆向工程产品设计就是根据已经存在的产品，反向推出产品设计数据（包括各类设计图或数据模型）的过程。这个过程一般是在软件交付使用之后进行，所以是在原软件生命周期的软件维护阶段进行。

• 【McCabe度量法】VG=m-n+2

  • m：有向弧数。

    注意，什么叫有向弧？！！！

    程序图是退化的程序流程图。也就是说，把程序流程图的每一个处理符号都退化成一个结点，原来连接不同处理符号的流线变成连接不同结点的有向弧，这样得到的有向图就叫做程序图。

  • n：节点数

• 【模块的分类】：

  • 传入模块：从下属模块取得数据，经处理再将其传送给上级模块。
  • 传出模块：从上级模块取得数据，经处理再将其传送给下属模块。
  • 变换模块：从上级模块取得数据，进行特定的处理，转换成其他形式，再传送给上级模块。

• 【数据流图】是结构化分析的工具，结构化方法就是采用自顶向下逐层分解的思想进行分析建模的。随着分解层次的增加，抽象的级别也越来越低，即越来越接近问题的解。数据流图建模应遵循：自顶向下、从抽象到具体的原则。

• 模块结构图由模块、调用、数据、控制信息和转接符号5种基本符号组成。

• 人机交互“黄金三原则”包括：用户操纵控制、减少用户的记忆负担、保持界面的一致性。

二、计网

• 【OSI七成模型口诀】：鹰标会的传人，王树武（应表会传网数物）

• 各种服务占用的端口号？

  • FTP：21
  • Telnet：23
  • SSH：22
  • POP3：110，SMTP：25
  • MySQL：3306
  • HTTP：80，HTTPS：443
  • DNS：53
  • SNMP：161

• IP地址划分？

  全0代表网络地址，全1代表组播地址。

• 127.0.0.1是回送地址，指本地机，一般用来测试使用。

• TCP/IP 协议族的层次模型和协议
  

• OSI/RM模型
  

• 【域名查询记录】：先HOSTS表，再本地DNS缓存，然后再查找本地DNS服务器，再根域名服务器、顶级域名服务器、权限域名服务器。

• 【有效数据速率】在异步通信中，每个字符包含 1 位起始位、7位数据位和2位终止位，若每秒钟传送500个字符，则有效数据速率为3500b/s

  每个字符的位数为1+7+2=10，每秒传输500个字符，故每秒传输的位数为10×500=5000，即码元速率为5000波特

  每个字符中的有效数据占7位

  5000 * （7/10）=3500

  因此每秒的有效数据为3500bit，则有效数据速率为3500b/s。

• 【动态路由选择算法（自适应路由选择算法）】：依靠当前网络的状态信息进行决策，从而使路由选择结果在一定程度上适应网络拓扑结构和通信量的变化，需要依据网络信息经常更新路由。

• HTTPS是基于SSL(Secure Sockets Layer 安全套接层)的。

• 【TCP与UDP区别】

  TCP	UDP
  TCP面向连接（如打电话要先拨号建立连接）	UDP是无连接的，即发送数据之前不需要建立连接
  TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达	UDP尽最大努力交付，即不保证可靠交付
  TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流	UDP是面向报文的；UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）
  每一条TCP连接只能是点到点的	UDP支持一对一，一对多，多对一和多对多的交互通信；
  TCP首部开销20字节	UDP的首部开销小，只有8个字节
  TCP的逻辑通信信道是全双工的可靠信道	UDP则是不可靠信道，整体来看UDP开销较小

• TCP和UDP协议均提供了端口寻址的能力。

• 【IPv4和IPv6的过渡期间，主要采用三种基本技术】

  1. 双协议栈：主机同时运行IPv4和IPv6两套协议栈，同时支持两套协议。
  2. 隧道技术：这种机制用来在IPv4网络之上连接IPv6的站点，站点可以是一台主机，也可以是多个主机。隧道技术将IPv6的分组封装到IPv4的分组中，封装后的IPv4分组将通过IPv4的路由体系传输，分组报头的“协议”域设置为41，指示这个分组的负载是一个IPv6的分组，以便在适当的地方恢复出被封装的IPv6分组并传送给目的站点。即可以使得两个IPv6结点可以通过现有的IPv4网络进行通信。
  3. NAT-PT(翻译技术) ：利用转换网关来在IPv4和IPv6网络之间转换IP报头的地址，同时根据协议不同对分组做相应的语义翻译，从而使纯IPv4和纯IPv6站点之间能够透明通信。

• 【POP3协议】：POP3协议采用的是C/S结构，同时该协议基于传输层TCP协议，所以客户端软件与POP3服务器会建立可靠的连接——TCP连接。

• 【变长子网的可用主机数计算】：2ⁿ-2（n为表示主机的位数）

• 【中国自主研发的3G通信标准】：TD-SCDMA

• DNS：域名服务器。

  DHCP：动态主机配置协议（Dynamic host configuration protocol）

三、计组

• 总线复用方式可以减少总线中信号线的数量，提高总线的利用率。

• 相联存储器按内容访问。

• 在程序的执行过程中，Cache与主存的地址映像需要专门的硬件自动完成，使用硬件来处理具有更高的转换速率。

• 数据流图是结构化分析模型需求分析阶段得到的结果，描述了系统的功能，在进行接口设计时，应以它为依据。

• 在程序运行过程中，CPU需要将指令从内存中取出来并加以分析和执行，CPU依据指令周期的不同阶段来区分在内存中以二进制编码形式存放的指令和数据。

• 【海明校验码】（校验位k，数据位m）：2^k-1 >= m+k

• 【可靠度公式】

  串联：P₁ * P₂

  并联：1-(1-P₁) * (1-P₂)

• H结尾、0x开头	16进制
  D结尾	10进制
  O结尾	8进制
  B结尾	2进制

• 【流水线】

  完成指令的时间 = 1条指令执行时间 + （指令条数 - 1）*周期。

  吞吐率(TP) = 指令数 / 完成指令的时间。

• 【无条件转移汇编指令】：让程序运行路径发生改变的的汇编指令。

• 【硬盘格式化容量】：面数*（磁道数/面）*（扇区数/道）*（字节数/扇区）

• 【原码、反码、补码和移码】：# 原码、反码、补码和移码详解 # 原码、反码、补码和移码的“由来”

  在计算机系统中常采用补码来表示和运算数据，原因是采用补码可以简化计算机运算部件的设计。

• MTBF为平均失效间隔时间，则可用性用MTBF/(1+MTBF)表示。（可用性是指在给定的时间点上，一个系统能够正确运作的概率）

  MTTF为平均无故障时间，则可靠性可用MTTF/(1+MTTF)表示。（可靠性是指系统在给定的时间间隔内、给定条件下无失效运作的概率）

• 【输入输出的编制方式】

  编址方式	说明
  独立编址	外设接口地址和主存地址是分开的	输入输出的操作是通过专门的I/O指令来操作的
  统一编址	外设接口地址和主存地址在一个公共的空间内	输入输出的操作是通过访存指令来操作的

• 【输入输出设备的控制方式】

  控制方式	说明	特点
  程序查询方式	CPU 定时查询外设的状态，发现外设就绪， 就开始和外设进行输入输出操作和处理	速度最慢，当输入/输出控制器和外设交换数据时，CPU 必须等待
  中断方式	1、当 CPU 执行到 I/O 请求时，向输入输出控制器发出相应的指令后，CPU 并不等待，而是继续执行其他操作，由输入输出控制器和外设进行通信 2、当数据从寄存器写到外设或从外设写入寄存器完毕后，输入输出控 制器向 CPU 发出中断请求，CPU 响应中断，并进行相应的处理。	中断方式是以字(节)为单位进行I/O的，每当完成一个字(节)的I/O 时，控制 器便要向CPU 请求一次中断。
  DMA	内存和 I/O 设备间传送一个数据块的过程中，不需要 CPU 的任何干涉，是 一种快速传递大量数据常用的技术。	为了实现在主机与控制器之间成块数据的直接交换，必须在 DMA 控制器中设置如下四类寄存器：命令/状态寄存器(CR)、内存地址寄存器(MAR)、数据寄存器(DR)、数据计数器(DC)。
  通道方式	通道方式是 DMA 方式的发展，它可进一步减少 CPU 的干预，即把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。

• 计算机系统的主存主要是由DRAM（动态随机存取存储器）构成的。

  补充： SRAM: 静态随机存取存储器； Cache: 高速缓存； EEPROM: 电可擦可编程只读存储器。

• 	RISC（精简指令）	CISC（复杂指令）
  指令	数量少，使用频率接近，定长格式	数量多，使用频率差别大，可变长格式
  寻址方式	支持方式少	支持方式多
  实现方式	增加了通用寄存器；硬布线逻辑控制为主；适合采用流水线	微程序控制技术

• 【主存编址计算】

  存储器地址是存储器中存储单元的编号。存储器是由大量存储单元组成，需要用编号区别每个单元：编号=地址。

  • 按字节编址：每个存储单元存储一个字节（即1B=8bit）

  • 计算机字长为32位，按字编址：每个存储单元存储一个字（即32bit=4B）

  eg：计算机字长为32位，按字编址（即1个字32个位，4个字节），则总容量为2GB的内存可规划的单元地址数量为？

  ? 2GB/32bit=2GB/4B=0.5G=512M。

  注意：区别M和MB！！！

  ? M为数量单位。1024=1K，1024K=1M

  ? MB指容量大小。1024B=1KB，1024KB=1MB.

• 【冗余技术】冗余是指在正常系统运行所需的基础上加上一定数量的资源，包括信息、时间、硬件、和软件。冗余是容错技术的基础，通过冗余资源的加入，可以使系统的可靠性得到较大的提高。主要的冗余技术有结构冗余（硬件冗余和软件冗余）、信息冗余、时间冗余和冗余附加四种。

  冗余附加技术包括：冗余备份程序的存储及调用，实现错误检测和错误恢复的程序，实现容错软件所需的固化程序。

• 【CPU的组成】

  CPU的运算器只能完成运算，而控制器用于控制整个CPU的工作。

  控制器	说明
  程序计数器(PC，Program Counter)	初始化存放从内存中提取程序的第一条指令地址的指令地址寄存器。由于多数情 况程序是顺序执行的，所以程序计数器设计有自动加 1 的装置，用来存放下一条指令的地址。当出现转移指令时，需要重新程序计数器。
  地址寄存器(AR，Address Register)	用来保存当前 CPU 所访问的内存单元的地址。
  指令寄存器(IR，Instruction Register)	用来保存当前正在执行的一条指令，它的位数取决于指令字长的位数。此寄存器对于程序人员来说是“透明”的，不能直接控制它。这里的“透明”(Transparency)是计算机学科中常用的个专业术语，表示实际存在，但在某个角度看好像没有。
  状态条件寄存器(PSW，Program Status Word)	存放各种条件内容，如运算结果进位标志，中断和系统工作状态信息等
  时序产生器	每条机器指令的操作过程是由指令操作流程图严格规定的，各条机器指令的指令周期中包含的机器周 期数各不相同，每个机器周期包含的时钟周期也不一定相同，所以指令周期、机器周期和时钟周期等时序信号就由时序产生 器根据操作流程规定产生，从而进行时序控制。
  操作控制器	在时序信号的控制下，各条机器指令在各个机器周期的各个时钟周期中应产生哪些微操作控制信号， 由指令操作流程图作出严格规定，操作控制器就根据指令流程图的安排，在各个时钟周期中中产生相应的微操作控制信号， 有效完成指令的操作过程。

  运算器	说明
  算术逻辑单元（ALU，Arithmetic Logical Unit）	进行算术逻辑运算。
  数据缓冲寄存器（DR，Data Register）	用来暂时存放由读出或写入的一条指令或数据字。
  累加寄存器(AC)	一个通用寄存器，为逻辑和算术运算提供一个工作区，用来为 ALU 执行算术逻辑运算提供数据并 暂存运算结果。

• 【程序的局限性】

  1. 时间局部性是指如果程序中的某条指令一旦被执行，则不久的将来该指令可能再次被执行；
  2. 空间局部性是指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。

• 【浮点数】两个浮点数相加运算，首先进行对阶，阶码小的向阶码大的对齐。

四、程序设计语言

• 中间代码生成和代码优化不是每个编译器必须要做的工作。代码优化和机器无关。

• 【中间代码】是源程序的一种内部表示，或称中间语言。中间代码的作用是可使编译程序的结构在逻辑上更为简单明确，特别是可使目标代码的优化比较容易实现。中间语言有多种形式，常见的有逆波兰记号、四元式、三元式、树、后缀和三地址码。

• 源程序→词法分析→语法分析→语义分析→中间代码生成→代码优化→目标代码生成→目标程序。

• 栈：由编译器自动分配和释放，存放运行时函数分配的局部变量、函数参数、返回数据/地址等；

  堆：由程序员自动分配，如果没有释放，可能会由OS回收。

• 反编译只能得到和源程序功能上等价的汇编程序，不能得到源程序。

• 【上下文无关文法】：形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。

  由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。

• 有限自动机是进行词法分析的工具。

• 【符号表】：符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。

  编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。

  【补充】哈希表：也叫散列表，是根据关键码值（Key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

  动态查找表：动态查找表的表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

五、数据结构

• 什么情况下使用哪种排序？

  • 如果数据规模小，那么使用插入排序或者选择排序。
  • 如果数据基本有序，那么插入、冒泡都很好。
  • 如果数据规模大，那么使用快速排序、堆排序、归并排序都很好。

• 二叉树：叶子节点 = 度为2的节点 + 1；

• 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O (n²)。

• 【互异的非平凡子串】：非空且不等同于本身的所有子串。

  eg：abc互异的非平凡子串为：ab、bc、a、b、c。

• 【图】

  无向完全图：限定任何一条边的两个顶点都不相同，则有 n 个顶点的无向图至多有 n（n-1)／2 条边，这样的无向图称为无向完全图(图中每两个顶点之间都有无向边。

  有向完全图：图中每两个顶点之间都有有向边。

  连通图：如果对于图中任意两个顶点 V_i、V_j都是连通的（有路径），则称 G 是连通图。

  强连通图： 有向图 G 中，若对于 V(G)中任意两个不同的 顶点 Vi和 Vj，都存在从 Vi到 Vj及从 Vj到 Vi的路径，则称 G 是强连通图。

六、数据库原理

• 怎样判断达到了哪一个规范化程度？

  • 第一范式：元组中每一个元素均不可再分。
  • 第二范式：没有部份依赖(AB→C，A→C，B→C，则C部分依赖于AB)。
  • 第三范式：没有传递依赖(A→B，B→C，但是C得不到B，B得不到A，则C传递依赖于A)。

• 【判断函数依赖集中的冗余项】

  1. 先看有没有函数依赖（A→B，B→C，A→C），如果存在，则A→C为冗余项。

  2. 看选项。如果从函数依赖集去除 选项A（例如：A→B），从剩下的关系中看 如果A的闭包中不包含B，则该关系不冗余；如果包含B则该关系冗余。

     eg：如果去除A→C，从剩下的关系中看 A的闭包为{A，B，C}，包含C，所以该关系冗余。

     【闭包】：例如： f={a->b,b->c,a->d,e->f} 由a可直接得到b和d，间接得到c，则a的闭包就是{a,b,c,d}

• 【封锁协议】

  • 共享锁（S锁）：又称读锁，若事务T对数据对象A加上S锁（则在T释放A上的S锁之前不能对 A 做任何的修改），其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。

  • 排他锁（X锁）：又称写锁。若事务T对数据对象A加上X锁（则只允许T对A进行读取和修改），其他事务不能再对A加任何锁，直到T释放A上的锁。

• 【三级模式】

  1. 模式（概念模式）：是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。一个数据库 只有一个概念模式。
  2. 外模式（子模式/用户模式）：是数据库用户(包括程序员和最终端用户)能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图。一个数据库可以有多个外模式。 但一个应用只能使用一个外模式 。
  3. 内模式：是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。一个数据库只有一个内模式 。

  所以，对表创建索引改变的是数据库的内模式。

• 【题目】：设关系模式R（U，F），其中：U= {A，B，C，D，E } ，F={A→B，DE→B，CB→E，E→A，B→D}。（ ）为关系模式R的候选关键字。分解（ ）是无损连接，并保持函数依赖的。

  问题1选项

  A.AB B.DE C.DB D.CE

  问题2选项

  A.ρ={ R1（AC），R2（ED）,R3（B）} B.ρ={ R1（AC），R2（E）,R3（DB）}

  C.ρ={ R1（AC），R2（ED）,R3（AB）} D.ρ={ R1（ABC），R2（ED）,R3（ACE）}

  答案解析

• 数据文件包含数据和对象，例如表、索引、存储过程和视图。 日志文件包含恢复数据库中的所有事务所需的信息。

  为了保证数据库中数据的安全可靠和正确有效，系统在进行事务处理时，对数据的插入、删除或修改的全部有关内容先写入日志文件；当系统正常运行时，按一定的时间间隔，把数据库缓冲区内容写入数据文件；当发生故障时，根据现场数据内容及相关文件来恢复系统的状态。

七、多媒体应用基础

• 人耳能听到的声音频率范围？人声音的频率范围？

  人耳：20HZ - 20KHZ

  人声：300HZ - 3400KHZ

• 频率越大音调越高，震动的幅度越大音高就越高。

• 	说明
  矢量图形	用一系列计算机指令来描述和记录一幅图的内容。编辑矢量图的软件通常称为绘图软件，如适于绘制机械图、电路图的AutoCAD软件等。
  位图图像	指用像素点来描述的图。	占用空间较大，处理侧重于获取和复制，显示速度快

• 数字语音的采样频率定义为 8kHz，这是因为语音信号定义的频率最高值为4kHz。

  尼奎斯特取样定理：如果取样速率大于模拟信号最高频率的2倍，则可以用得到的样本中恢复原来的模拟信号。

• 使用图像扫描仪以300DPI的分辨率扫描一幅3×4英寸的图片，可以得到（ 300×3×300×4=900*1200 ）像素的数字图像。

  300DPI：每英寸有300个像素点。

• 计算机获取/处理模拟视频信息的过程、声音信号数字化过程中首先要进行A/D转换。

  视频信息是指活动的、连续的图像序列。一幅图像称为一帧，帧是构成视频信息的基本单位。

• CIF=352×288像素。

• “媒体”：指存储信息的载体 或者 存储信息的实体。

• 媒体可以分为：

  1. 感觉媒体（直接作用于人的感觉器官的媒体。如：声音、图像等）
  2. 表示媒体（指传输感觉媒体的中介媒体，及用于数据交换的编码。如：图像编码、文本编码、声音编码等）
  3. 表现媒体（指实现信息输入和输出的媒体。如：键盘、鼠标、话筒、显示器、打印机、喇叭等）
  4. 存储媒体（如：硬盘、光盘等）
  5. 传输媒体（如：光缆、电缆、电磁波等）

• Xara3D软件：主要用于动画编辑和处理。

  EditPro软件：主要用于音频播放、音频编辑、音频录制和声音素材库4个功能。

• 图像数据量=图像的总像素×图像深度(b)

  图像深度：指存储每个象素所用的位数。

  如果是RGB表示，则还得×3，因为RGB中每一个像素都由R、G、B三个分量表示。

• DPI是描述的图像分辨率的单位，表示每英寸多少像素点。

• 图元是描述矢量图的基本组成单位。

• 饱和度是指颜色的纯度。

• VCD使用了MPEG-1标准作为其音、视频信息压缩编码方案。

  DVD使用了MPEG-2标准作为其音、视频信息压缩编码方案。

• MPEG-1、MPEG-2、MPEG-4：主要针对音、视频编码技术；

  MPEG-7：多媒体内容描述接口标准；

  MPEG-21：多媒体应用框架便准。

• 音乐合成技术主要有：调频（FM）音乐合成、波形表（WaveTable）音乐合成两种方式。后者合成的音乐，音质更好。

八、操作系统原理

• 【PV操作】：P - ，V +

• 【位示图】：在外存建立一张位示图，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取 0 和 1 表示空闲和被占用。特点，位示图的大小由磁盘空间决定，描述能力强，容易找到一组相邻接的空闲块。

• 若系统正在将目录文件修改的结果写回磁盘时系统发生崩溃，则对系统的影响相对较大。

• 分页系统的逻辑地址结构为

  页号	页内地址

  分页式存储管理：

  • 分页原理：将一个进程的逻辑地址空间划分成若干大小相等的区域，称为页。将主存空间划分成与页相同大小的若干物理块，称为块或页框。

  计算机的页面大小为4k，则页内地址的位数为12位，因为4k = 2¹²。

• 【多级索引分配】：某文件系统采用多级索引结构。若磁盘块的大小为1K字节，每个块号占3字节，那么采用二级索引时的文件最大长度为（ ）K字节。

  磁盘块大小为 1K=2¹⁰B，每个块号占3B

  所以，每个磁盘块可以存 2¹⁰/3 个块号，

  又，采用二级索引，所以一级索引（主索引）中的每一个块号指向一个磁盘块，而磁盘块中存储的每一个块号最终指向一个大小为 1K 的磁盘块

  

  即：采用二级索引时文件的最大长度为：[(2¹⁰/3)×(2¹⁰/3)×2¹⁰]÷2¹⁰≈116508

• 【某文件管理系统采用位示图（bitmap）记录磁盘的使用情况。如果系统的字长为32位，磁盘物理块的大小为4MB，物理块依次编号为：0、1、2、…,位示图字依次编号为：0、1、2、…,那么16385号物理块的使用情况在位示图中的第（ ）个字中描述；如果磁盘的容量为1000GB，那么位示图需要（ ）个字来表示。】

  解：位示图：每一位对应文件存储器上的一个物理块，取 0 和 1 表示空闲和被占用；

  系统的字长为32位，所以一个字可以表示32个物理块；

  16385号物理块，即第16385+1个物理块，即在（16385+1）/32=512.0625≈513个字中描述；

  磁盘容量为1000GB，即可以存储1000GB/4MB=1000×2⁸个物理块，即需要1000×2⁸÷32=8000个字描述。

• 【分析按什么样的序列执行，系统状态是安全的】

  1. 目标就是不产生死锁；
  2. 弄清目前 每个进程对每个资源还需要多少个；
  3. 根据目前 系统中每个资源剩余的个数 进行判断每个进程的先后执行顺序。

• 【相对路径/绝对路径/全文件名】：

  • 相对路径：相对于当前目录的路径，用.和..来区分当前目录和上一级目录，不会带上当前目录名。
  • 绝对路径：从根目录开始到目标文件或目录的一条路径，不会带上目标文件或目录的名字。
  • 全文件名：从根目录到目标文件的或目录的一条路径，带上目标文件或目录的名字。

• 【嵌入式操作系统的特点】：

  1. 微型化，从性能和成本角度考虑，希望占用的资源和系统代码量少；
  2. 可定制，从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用的需求；
  3. 实时性，嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高；
  4. 可靠性，系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施；
  5. 易移植性，为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。

九、面向对象

• 【设计模式的图】：弄清每一个设计模式的用处，见下午题中的第三点。

• 动态绑定是实现多态的基础。

• 多态由继承机制来支持。

• 高层模块不应该依赖于底层模块就.

• 对象由对象名、属性名、方法组成。

• 采用面向对象方法进行软件开发，分析阶段，架构师主要关注系统的行为，即系统应该做什么。

• 【UML图】

  UML图通常对系统的词汇、简单的协作、逻辑数据库模式进行建模。

  1. 类图（class diagram）。类图描述一组类、接口、协作和它们之间的关系。在OO系统的建模中，最常见的图就是类图。类图给出了系统的静态设计视图，活动类的类图给出了系统的静态进程视图。
  2. 对象图（object diagram）。对象图描述一组对象及它们之间的关系。对象图描述了在类图中所建立的事物实例的静态快照。和类图一样，这些图给出系统的静态设计视图或静态进程视图，但它们是从真实案例或原型案例的角度建立的。即对象图通常对对象快照建模。
  3. 构件图（component diagram）。构件图描述一个封装的类和它的接口、端口，以及由内嵌的构件和连接件构成的内部结构。构件图用于表示系统的静态设计实现视图。对于由小的部件构建大的系统来说，构件图是很重要的。构件图是类图的变体。
  4. 组合结构图（composite structure diagram）。组合结构图描述结构化类（例如，构件或类）的内部结构，包括结构化类与系统其余部分的交互点。组合结构图用于画出结构化类的内部内容。
  5. 用例图（use case diagram）。用例图描述一组用例、参与者及它们之间的关系。用例图给出系统的静态用例视图。这些图在对系统的行为进行组织和建模时是非常重要的。
  6. 顺序图（sequence diagram，序列图）。顺序图是一种交互图（interaction diagram），交互图展现了一种交互，它由一组对象或参与者以及它们之间可能发送的消息构成。交互图专注于系统的动态视图。顺序图是强调消息的时间次序的交互图。
  7. 通信图（communication diagram）。通信图也是一种交互图，它强调收发消息的对象或参与者的结构组织。顺序图和通信图表达了类似的基本概念，但它们所强调的概念不同，顺序图强调的是时序，通信图强调的是对象之间的组织结构（关系）。在UML 1.X版本中，通信图称为协作图（collaboration diagram）。
  8. 定时图（timing diagram，计时图）。定时图也是一种交互图，它强调消息跨越不同对象或参与者的实际时间，而不仅仅只是关心消息的相对顺序。
  9. 状态图（state diagram）。状态图描述一个状态机，它由状态、转移、事件和活动组成。状态图给出了对象的动态视图。它对于接口、类或协作的行为建模尤为重要，而且它强调事件导致的对象行为，这非常有助于对反应式系统建模。
  10. 活动图（activity diagram）。活动图将进程或其他计算结构展示为计算内部一步步的控制流和数据流。活动图专注于系统的动态视图。它对系统的功能建模和业务流程建模特别重要，并强调对象间的控制流程。
  11. 部署图（deployment diagram）。部署图描述对运行时的处理节点及在其中生存的构件的配置。部署图给出了架构的静态部署视图，通常一个节点包含一个或多个部署图。
  12. 制品图（artifact diagram）。制品图描述计算机中一个系统的物理结构。制品包括文件、数据库和类似的物理比特集合。制品图通常与部署图一起使用。制品也给出了它们实现的类和构件。
  13. 包图（package diagram）。包图描述由模型本身分解而成的组织单元，以及它们之间的依赖关系。
  14. 交互概览图（interaction overview diagram）。交互概览图是活动图和顺序图的混合物。

• 【类间的关系】：依赖 < 关联 < 聚合 < 组合 < 继承。

• Jackson是一种面向数据结构的开发方法。

• 继承是父类和子类之间共享数据的一种关系。

• 【多态】

  1. 参数多态（属于静态多态。应用比较广泛的一种多态，被称为最纯的多态）
  2. 包含多态（属于动态多态。在许多语言中都存在，最常见的例子就是子类型化，即一个类型是另外一个类型的子类型。）
  3. 过载多态（属于静态多态。同一个名字在不同的上下文中所代表的含义不同。典型的例子是运算符重载和函数重载。）
  4. 强制多态（属于动态多态。在发生不同类型的数据进行混合运算时，编译程序一般都会进行强制多态。程序员也可以显示地进行强制多态的操作。）

• 【类与类之间的关系】

  1. 泛化 / 继承（─?）
  2. 实现（┄?）
  3. 依赖（?）
  4. 关联（→）
  5. 聚合（?→）
  6. 组合（?→）

• 面向对象分析过程中，从给定需求描述中选择名词短语来识别对象。

• 对象的状态标识了该对象的所有属性（通常是静态的）以及每个属性的当前值（通常是动态的）。

十、网络安全

• 【常见对称加密算法】：DES、AES、IDEA、RC-5。

  对大量明文进行加密，考虑效率问题，一般采用对称加密。

• 【病毒】

  • 【木马程序】

    木马程序传播方式：

    1. 通过邮件附件、程序下载等形式传播；
    2. 通过伪装网页登录过程，骗取用户信息进而传播；
    3. 通过攻击系统安全漏洞传播木马，大量黑客使用专门的黑客工具来传播木马。

    木马程序的危害：

    • 木马程序危害在于多数有恶意企图，例如占用系统资源，降低电脑效能，危害本机信息安全（盗取QQ账号、游戏账号甚至银行账号），将本机作为工具来攻击其他设备等；

    常见的木马程序：

    • 特洛伊木马：典型现象为有未知程序尝试建立连接。

    木马程序的客户端运行在攻击者的机器上。

  • 【蠕虫病毒】

    常见蠕虫病毒：

    • 震网（Stuxnet）：它的复杂程度远超一般电脑黑客的能力。这种震网（Stuxnet）病毒于2010年6月首次被检测出来，是第一个专门定向攻击真实世界中基础（能源）设施的“蠕虫”病毒，比如核电站，水坝，国家电网。

  • 【引导区病毒】

    危害：破坏的是引导盘、文件目录等

  • 【宏病毒破】

    危害：坏的是OFFICE文件相关

• 【Sniffer】：是用于拦截通过网络传输的TCP/IP/UDP/ICMP等数据包的一款工具，可用于分析网络应用协议，用于网络编程的调试、监控通过网络传输的数据、检测木马程序等。

• 【数字证书】认证用户的身份

• 【数字签名】

  数字签名一般使用非对称加密算法。

  数字签名（A→B）的作用：

  B 可以验证消息确实来源于 A(消息使用 A 的私钥加密)；

  A 以后不能否认发送过消息；

  B 不能编造或改变消息 。

  数字签名的缺陷：

  不能确认接收方的身份，也不能保证接收方一定能收到数据。

  常用的数字签名算法：

  RSA、DSS、Hash

• 【公钥、私钥】：在公钥体系中，交换私钥是无论什么情况下都绝对不允许发生的情况。

• 假定用户A、B 分别在I1和I2两个 CA 处取得了各自的证书，I1、I2互换公钥是 A、B 互信的必要条件。

• 入侵检测技术有：特征检测、统计检测、专家系统、文件完整性检查、模型检测、简单匹配等。

• 防火墙	说明
  包过滤防火墙	包过滤防火墙工作在网络协议IP层，它只对包的源IP地址、源端口号、目标IP地址、目标端口号进行处理，因此速度比较快，能够处理的并发连接比较多，缺点是对应用层的攻击无能为力（包过滤防火墙一般有一个包检查块（通常称为包过滤器），数据包过滤可以根据数据包头中的各项信息来控制站点与站点、站点与网络、网络与网络之间的相互访问，但无法控制传输数据的内容，因为内容是应用层数据，而包过滤器处在网络层和数据链路层之间），包过滤成本与它的安全性能没有因果关系，而应用程序和用户对于包过滤的过程并不需要了解，因此该技术对应用和用户是透明的。
  应用级网关防火墙	应用代理网关防火墙彻底隔断内网与外网的直接通信，内网用户对外网的访问变成防火墙对外网的访问，然后再由防火墙转发给内网用户。所有的通信都必须经应用层代理软件转发，它可对应用层的通信数据流进行监控和过滤。
  代理服务器防火墙	代理服务器防火墙将收到的IP包还原成高层协议的通讯数据，比如http连接信息，因此能够对基于高层协议的攻击进行拦截。缺点是处理速度比较慢，能够处理的并发数比较少，所以不能提高网络整体性能，而代理对于用户认证可以设置。
  数据库防火墙	数据库防火墙技术是针对关系型数据库保护需求应运而生的一种数据库安全主动防御技术，数据库防火墙部署于应用服务器和数据库之间。
  Web防火墙	Web防火墙是入侵检测系统，入侵防御系统的一种。从广义上来说，Web应用防火墙就是应用级的网站安全综合解决方案，与我们所讲到的防火墙概念有一定区别。

• 【MIME】是一个互联网标准，扩展了电子邮件标准，使其能够支持，与安全无关。与安全电子邮件相关的是S/MIME安全多用途互联网邮件扩展协议。

  SSL和HTTPS涉及到邮件传输过程的安全

  PGP（全称：Pretty Good Privacy，优良保密协议），是一套用于信息加密、验证的应用程序，可用于加密电子邮件内容。

十一、法律法规

• 目前根据我国法律法规的规定必须使用注册商标的是烟草类商品。
• 法律法规不受著作权的保护。
• 著作权是自作品完成之时就开始保护。

十二、算法

• 【四种算法】：见下午题中的算法。

• 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于贪心策略的算法。

• 时间复杂度是指程序运行从开始到结束所需要的时间；

  空间复杂度是指程序运行从开始到结束所需的辅助存储量。

• 【矩阵乘法】：动态规划法、时间复杂度：O(n³)

• 折半查找最多与 [log₂ⁿ]+1 个元素进行比较。

• 长度为n的哈希表的散列函数为：H(key)=Key mod p，若采用线性探测法解决冲突，则p的值一般为不大于n且接近n的质数。

• Prim算法从扩展顶点开始，每次总是”贪心的“选择与当前顶点集合中距离最短的顶点，而Kruscal 算法从扩展边开始，每次总是”贪心的“选择剩余的边中最小权重的边，所以两个算法都是基于贪心策略进行的。

  Prim 算法的时间复杂度为O(n²)，其中n 为图的顶点数，该算法的计算时间与图中的边数无关，因此该算法适合于求边稠密的图的最小生成树；

  Kruscal 算法的时间复杂度为O(mlg^m) ，其中m为图的边数，该算法的计算时间与图中的顶点数无关，因此该算法适合于求边稀疏的图的最小生成树。

  但若事先没有关于图的拓扑特征信息时，无法判断两者的优劣。由于一个图的最小生成树可能有多棵， 因此不能保证用这两种算法得到的是同一棵最小生成树。

  边越多，图就越稠密。

十三、翻译

十四、下午题

最后一题记得涂选项，选择Java/C！！！

【建议】

• 由于算法题难度较高，建议算法题最后做。
• 前面三题和最后一题尽量不要出现错误。

1. 数据流图

• 缺省数据流（一分一个）【考査父图与子图的平衡问题】
• 补充数据存储【数据存储一般叫做xx表或xx文件】
• 加工向数据库或其他发送的数据流一定是一个动作
• 每个加工必有输入和输出
• 每个存储必须要有写入和读取。（一个不产生任何输出流的文件是没有意义的）
• 有上交文档的，著作权都属于公司

【数据流图的改错】：

• 数据流与错误的加工相连接
• 数据流方向错误
• 删除多余数据流

【简答题】：

• 在绘制数据流图的加工时，可能出现的输入、输出错误：
  只有输入而无输出/黑洞
  只有输出而无输入/奇迹
  输入的数据流无法通过加工产生输出流/灰洞
  输入的数据流与输出的数据流名称相同

• 说明实体之间可否有数据流，并解释其原因
  实体之间不可以有数据流，因为数据流的起点和终点中必须有一个是加工。

• 如果采用“第三方Email系统”，那么需要进行哪些修改？用150字以内文字加以说明
  图1-1中：增加外部实体“第三方Email系统”，将所有发送给客户的消息数据流，终点均修改至“第三方Email系统”。
  图1-2中：增加外部实体“第三方Email系统”，增加加工“发送邮件”，将临时预订/预订/变更确认信息终点均修改至“发送邮件”加工，并增加从D2到“发送邮件”加工的数据流“电子邮件地址”，再从发送邮件加工引出数据流（临时预订/预订/变更确认信息)终点为第三方Email系统

• 实际的证券交易通常是在证券交易中心完成的，因此，该平台的“证券交易”功能需将交易信息传递给证券交易中心。针对这个功能需求，需要对图1-1和图1-2进行哪些修改，请用200字以内的文字加以说明。

  图1增加外部实体“证券交易中心”，增加“证券交易平台”到“证券交易中心”，数据流：交易信息。
  图2增加外部实体“证券交易中心”，增加“证券交易（在线）”到“证券交易中心”，数据流：交易信息。
  图2增加“证券交易（电话）”到“证券交易中心”，数据流：交易信息 。

• 简要说明面向数据结构设计方法的基本思想及其适用场合
  面向数据结构的设计方法（如Jackson方法）就是用数据结构作为程序设计的基础，最终目标是得出对程序处理过程的描述，适合在详细设计时使用。即在完成了软件结构设计之后，可以使用面向数据结构的方法来设计每个模块的处理过程，常用于规模不大的数据处理系统。使用面向数据结构的设计方法，当然首先需要分析确定数据结构，并且用适当的工具清晰地描述数据结构。

• 简要说明程序流程图的适用场合与作用
  程序流程图通常在进行详细设计时使用，用来描述程序的逻辑结构

• 用 200 字以内文字，说明建模图 1-1 和图 1-2 时如何保持数据流图平衡
  父图中某个加工的输入输出数据流必须与其子图的输入输出数据流在数量上和名字上相同。父图的一个输入（或输出）数据流对应于子图中几个输入（或输出）数据流，而子图中组成的这些数据流的数据项全体正好是父图中的这一个数据流

• 说明上层的哪些数据流是由下层的哪些数据流组合而成。

  0层图中的“不合法提示”对应着1层图中的“学生信息不合法提示”、“学位考试结果不合法提示”、“无注册资格提示”。

  0层图中的“注册学生信息”对应1层图中的“选课学生标识”和“注册学生信息”。

  【解题技巧】：将补全后的数据流图进行对比，如果0层数据流和1层数据流中有些不同，那么这些地方极有可能会是出现的点，另外还要注意题干中的信息，有些打括号特别说明的位置很有可能会出现考点。

2. 关系模式和E-R图

【解题技巧】

• 一空可能不止一个属性
• 从其他关系中引用的属性全部是外键，即一个属性既可能是主键也可能是外键。
• E-R图中联系：联系的实体不单只有两个，考虑3个甚至4个
• 有时候说明不一定有全部全部的属性信息，还要根据前后自己补充
• 弱实体只与对应实体有联系

【可能会出现的题型】

• 【补全ER图】。例如，补充各个实体间的联系，注意联系是用菱形方框表示的，不要忘了写，而且还要标明是什么联系：1:1，1:n，m:n。

• 【补全关系模式（如果是1:*，则*的这一方需要1的这一方的主键或其他信息）、指明主外键】

  主外键：

  • 主键：能唯一标识一条记录的属性或属性组

  • 外键：是另外一张表中的主键

    在判断外键的时候，

    1. 如果主键是单一属性，而该属性又是其他关系模式中的主键，那么该属性不能为外键；

    2. 如果主键是一个元组，其中一个属性是其他关系模式的主键，那么该属性可以是外键。

• 【添加一个实体，或修改关系模式，或优化】

• 【简答题】

  • 问（前提：邮件中有附件）：附件属于弱实体吗？请用50字以内的文字说明原因。

    答：附件属于弱实体，因为附件的存在必须以邮件的存在为前提，即附件总是依附于某邮件。

  • w关系模式是否存在规范性问题，请用100字以内文字解释你的观点（若存在问题，应说明如何修改w关系模式）。

    答：在w关系模式中，存在其他部分依赖关系/传递函数依赖，___指出依赖关系__，____指出这种依赖会出现的问题（数据冗余、插入异常、更新异常、删除异常）___。
    可以对w关系进行分解，具体如下：
    ___具体结果___

  • w关系模式的主键为全码吗？

    答：全码的概念+说明非主属性。

  • 客户关系的通信地址可以进一步分为邮编、省、市、街道，那么该属性是否属于简单属性，为什么？请用100字以内的文字说明。

    通信地址不是简单属性而是一个复合属性，因为该属性可拆分为多个属性。

【实体与实体连线中有一个圈圈】

原题解释为员工是经理的超类型，经理是员工的子类型，上网搜到的解释为允许重叠，允许有那么一个人拥有经理、员工两种身份，即一个既是员工又是经理的人。

【数据库系统术语】

1. 弱实体与强实体

   一个实体的存在必须以另一实体的存在为前提。前者就称为“弱实体”，后者称为“强实体”。

2. 关系模式的主键为全码

   关系模式的所有属性组组成该关系模式的候选码，称为全码。即所有属性都是主属性。

3. UML图和设计模式

• 状态图填写时注意根据已有状态来组织词语填写
• 特别注意掌握类图/对象图和观察者模式

3.1 UML图题型

1. 用例图

【概念】描述用户需求，从用户的角度描述系统的功能。展现了一组用例、参与者（actor）以及它们之间的关系。

【描述方式】

• 椭圆表示用例；
• 人形符号表示参与者（参与者不一定是人，也可能是系统）；

【目的】帮组开发团队以一种可视化的方式理解系统的功能需求

【考点】

• 填用例名，参与者对应的角色名
• 两个用例之间的关系。

【答题技巧】

构建用例图时，常用的方式是先识别参与者，然后确定用例以及用例之间的关系。

• 识别参与者时，考查和系统交互的人员和外部系统。（向看题目有几个，然后全部找出来，再根据判断或排除法进行填入）

• 考查用例及其和参与者之间的关系时，通过判断哪一个特定参与者发起或者触发了与系统的哪些交互，来识别用例并建立和参与者之间的关联。

• 考查用例之间的关系时，include(包含)定义了用例之间的包含关系，用于一个用例包含另一个用例的行为的建模；

  如果可以从一个用例的执行中，在需要时转向执行另一个用例，执行完返回之前的用例继续执行，用例间即存在extend(扩展)关系。

• 用例之间的继承关系：其中父类型通常是一个抽象泛化用例，具有子类型共有的属性和行为，每个具体的子类型继承它，并实现适合自己的特定的操作。

  【！！！注意！！！】例题：用例1和用例2、用例3、用例4 等用例之间的关系及内涵？

  如果用例1是其他用例的父类，则回答上面一整句即可。（例：用例1是一个抽象泛化用例，具有… … 后面照写。）

【关系】

• 包含关系<include>是用例之间的关系。

  若用例A包含用例B，则箭头指向被包含的用例B。既要执行用例A，必须先执行用例B。

• 扩展关系<extend>是用例之间的关系。

  若用例A中需要扩展用例B，则箭头指向基础用例A。既要执行用例A，不一定需要执行用例B。

• 泛化关系是参与者之间的关系。

  描述了一个参与者可以完成另一个参与者同样的任务，并可补充额外的角色功能。

• 【！！！注意！！！】例题：指出图3-1中… …和… …（两个都是参与者）之间是什么关系，并解释该关系的内涵。

  由于参与者与参与者之间一般为泛化关系，所以这里就直接写的泛化关系。

  答：泛化关系。泛化关系描述了一个参与者可以完成另一个参与者同样的任务，并可补充额外的角色功能。

2. 类图

【概念】显示系统的静态结构，表示不同的实体是如何相关联的。展现了一组对象、接口、协作和它们之间的关系。

【描述方式】三个矩形，从上往下排列，分别是名字，属性，操作

【目的】表示一个逻辑类或实现类，逻辑类通常是用户的业务所涉及的事物；实现类是程序员处理的实体

【考点】填类名，方法名，属性名、填多重度、填关系

【多重度】

[1]：表示一个集合中的一个对象对应另一个集合中的1个对象。

[0..*]：表示一个集合中的一个对象对应另一个集合中的0个或多个对象。

[1..*]：表示一个集合中的一个对象对应另一个集合中的1个或多个对象。

[*]：表示一个集合中的一个对象对应另一个集合中的多个对象。

【关系】

【可见性】

3. 对象图

【概念】展现了一组对象以及它们之间的关系。对象图是类图的实例，几乎使用与类图完全相同的标示。

4. 顺序图

【概念】顺序图是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动。

构造顺序图时遵循如下指导原则：

? 确定顺序图的范围，描述这个用例场景或一个步骤；
? 绘制参与者和接口类，如果范围包括这些内容的话；
? 沿左手边列出用例步骤；
? 对控制器类及必须在顺序中协作的每个实体类，基于它拥有的属性或已经分配给它的行为绘制框；
? 为持续类和系统类绘制框；
? 绘制所需消息，并把每条消息指到将实现响应消息的责任的类上；
? 添加活动条指示每个对象实例的生命期；
? 为清晰起见，添加所需的返回消息；
? 如果需要，为循环、可选步骤和替代步骤等添加框架。

【描述方式】横跨图的顶部，每个框表示每个类的实例或对象；类实例名称和类名称使用冒号分开

【目的】显示流程中不同对象之间的调用关系，还可以显示不同对象的不同调用。

【考点】填对象名、填消息

5. 状态图

【概念】描述对象的所有状态以及事件发生而引起的状态之间的转移

【描述方式】

• 起始点：实心圆
• 状态之间的转换：使用开箭头的线段
• 状态：圆角矩形
• 判断点：空心圆
• 一个或多个终止点：内部包含实心圆的圆

【目的】表示某个类所处的不同状态以及该类在这些状态中的转换过程

6. 活动图

【概念】描述满足用例要求所要进行的活动以及活动时间的约束关系

【描述方式】

• 起始点：实心圆
• 活动：圆角矩形
• 终止点：内部包含实心圆的圆
• 泳道：实际执行活动的对象

【目的】表示两个或多个对象之间在处理某个活动时的过程控制流程

7. 序列图

【可能会出现的题型】

• 在图中补全相应的消息

  填写返回消息时，一般返回消息的说明为 ... ...信息。

• 补充活动名称或图形符号

  菱形：判断

  细长的矩形框（类似于|）：表示对象的激活。激活是对象操作的执行，它表示一个对象直接或通过从属操作完成的过程。

  圆角方框：活动

【说明】

• evaluation：返回消息
• check()：表示对象 a1 要调用对象 john 中的 check() 操作。即Person类中需要实现该方法。

3.2 设计模式

• 设计模式最根本的目的在于复用相似问题的相同解决方案，从而提高软件在设计层次的复用度和设计的水平与质量。

• 【技巧】

  做设计模式题的时候，如果有类图（其中类的名称是英文的），一般里面的都会有相关设计模式的关键字。例如：桥接模式的Adapter等。

  如果不确定是什么类型的设计模式，那就根据题目的目的反推。创建型是 - 创建对象的机制，结构型是 - 将对象和类组成较大的结构，行为型是 - 对象间的高效沟通和职责委派。

3.2.1 创建型模式

• 创建型模式提供了创建对象的机制， 能够提升已有代码的灵活性和可复用性。

1. 工厂模式

工厂方法模式是一种创建型设计模式， 其在父类中提供一个创建对象的方法， 允许子类决定实例化对象的类型。

2. 抽象工厂模式

抽象工厂模式是一种创建型设计模式， 它能创建一系列相关的对象， 而无需指定其具体类。

3. 生成器模式

生成器模式是一种创建型设计模式， 使你能够分步骤创建复杂对象。 该模式允许你使用相同的创建代码生成不同类型和形式的对象。该模式适用于当创建复杂对象的算法应该独立于该对象的组成部分及其装配方式时

3.2.2 结构型模式

• 结构型模式介绍如何将对象和类组装成较大的结构， 并同时保持结构的灵活和高效。

1. 适配器模式（Adapter）

适配器模式是一种结构型设计模式， 它能使接口不兼容的对象能够相互合作。

适配器模式既可以作为类结构型模式，也可以作为对象结构型模式。

• 在类适配器模式中，通过使用一个具体类将适配者适配到目标接口中；
• 在对象适配器模式中，一个适配器可以将多个不同的适配者适配到同一个目标。

将一个对象加以包装以给客户提供其希望的另外一个接口。

【优点】

• 可以让任何两个没有关联的类一起运行

2. 桥接模式（Bridge）

桥接模式是一种结构型设计模式， 可将一个大类或一系列紧密相关的类拆分为抽象和实现两个独立的层次结构， 从而能在开发时分别使用。桥接模式是比多重继承方案更好的解决方法。

3. 组合模式(Composite)

组合模式是一种结构型设计模式， 你可以使用它将对象组合成树状结构， 并且能像使用独立对象一样使用它们。

4. 装饰器模式

装饰模式是一种结构型设计模式， 允许你通过将对象放入包含行为的特殊封装对象中来为原对象绑定新的行为。

就增加对象功能来说，装饰模式比生成子类实现更为灵活。通过装饰模式，可以在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责；当需要动态地给一个对象增加功能，这些功能可以再动态地被撤销时可使用装饰模式；当不能采用生成子类的方法进行扩充时也可使用装饰模式。

【优点】

• 装饰模式可以动态的扩展一个实现类的功能

4. 代理模式

代理模式是一种结构型设计模式， 让你能够提供对象的替代品或其占位符。 代理通过提供与对象相同的接口控制着对于原对象的访问， 并允许在将请求提交给对象前后进行一些处理。

5. 外观模式

外观模式是一种结构型设计模式， 能为程序库、 框架或其他复杂类提供一个简单的接口。将一系列对象加以包装以简化其接口。

3.2.3 行为模式

• 行为模式负责对象间的高效沟通和职责委派。

1. 观察者模式（Observer）

观察者模式是一种行为设计模式， 允许你定义一种订阅机制， 可在对象事件发生时通知多个 “观察” 该对象的其他对象。

观察者模式的最主要特征是使所要交互的对象尽量松耦合。

2. 策略模式

策略模式是一种行为设计模式， 它能让你定义一系列算法， 并将每种算法分别放入独立的类中， 以使算法的对象能够相互替换。

【应用场景】：

1. 多个类只区别在表现行为不同，可以使用Strategy模式，在运行时动态选择具体要执行的行为。
2. 需要在同情况下使用不同的策略（算法）不，或者策略还可能在未来用其他方式来实现。
3. 对客户隐藏具体策略（算法）的实现细节，彼此完全独立。

3. 责任链模式

责任链模式是一种行为设计模式， 允许你将请求沿着处理者链进行发送。收到请求后， 每个处理者均可对请求进行处理， 或将其传递给链上的下个处理者。

4. 命令模式

命令模式是一种行为设计模式， 它可将请求转换为一个包含与请求相关的所有信息的独立对象。 该转换让你能根据不同的请求将方法参数化、 延迟请求执行或将其放入队列中， 且能实现可撤销操作。

5. 状态模式（State）

状态模式是一种行为设计模式， 让你能在一个对象的内部状态变化时改变其行为， 使其看上去就像改变了自身所属的类一样。

6. 访问者模式（Visitor）

访问者模式是一种行为设计模式， 它能将算法与其所作用的对象隔离开来。

在Visitor模式中，一个Visitor对象是一个多态的accept操作的参数，这个操作作用于该Visitor对象访问的对象。

3.3 考察的内容

• 第一题：读懂题目，搞定逻辑和业务流程，填补类图，填多重度等（类模型看参数及关联推断类名和关系（特殊的：聚合，泛化），切记不能随便填类名）
• 第二题：填流程图，用例图（突破口：特殊关系：泛化，组合），等
• 第三题：优化，分析，模式优化，添加功能，模式等（概念题）

4. 算法(C语言实现)

4.1 分治法

对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

【常见题型】

• 归并排序

  时间复杂度：O(nlog₂ⁿ)

  空间复杂度：O(n)

  递归式：T(n)=2T(n/2)+n

• 二分法

  时间复杂度：

  • 二分的外层如果有嵌套循环，就是nlog₂ⁿ；
    • 例如归并排序，分成两堆，第一第二堆各自再分成两堆，… …，直到不能再分后每一组进行归并排序；然后返回到上一层，再次进行归并排序，… …，直到最后形成一个有序的序列。
  • 如果只有二分没有嵌套循环，就是log₂ⁿ。
    • 例如求硬币中的假币，分成两堆，找出轻的那一堆再分，直到找到为止。

4.2 动态规划法

这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。

求解问题时，如果经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用动态规划算法。

【常见题型】

• 0-1背包

• 矩阵连乘

  讲解视频：09_动态规划之矩阵连乘_算法设计与分析_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

  时间复杂度一般为：O(n³)

【总结】

一维动态规划时间复杂度一般有O(n)和O(n²)两种，时间复杂度取决于状态转移方程。

1. 如果第i个状态的确定需要利用前i-1个状态，即dp[i]由dp[i-1],dp[i-2],…,dp[0]的取值共同决定，那么此时的时间复杂度为O(n²)。

2. 如果第i个状态只取决于第i-1个状态或者第i-2个状态或者第i-1和第i-2个状态，也就是说dp[i]的取值由dp[i-1]，或者dp[i-2]或者dp[i-1]和dp[i-2]决定，而不是取决于其之前的每一个状态，此时的时间复杂度为O(n)。

4.3 贪心算法

它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。

4.4 回溯算法（试探法）

它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。

【常见题型】

• 0-1背包

4.5 KMP算法

主串：t，长度：lt

子串：s，长度：ls

一般该算法的时间复杂度为：O(lt+ls)

5. 面向对象编程(C++/Java二选一)

考试规律

【贯穿整个学习直到最后一刻的重点】

• 几个常用的端口号
• 内聚、耦合的几种类型
• 各个设计模式的含义及内涵
• 常见的算法：分治法、回溯法、动态规划、贪心法
• 软件工程中各个令人作呕的概念
• 常见的加密算法
• 设计模式中的解题技巧
• 关系模式范式的判断。
• 常见算法的时间复杂度、空间复杂度
• 常见的设计模式的概念
• cpu中各个寄存器的作用
• 路由协议称为内部网关协议，自治系统之间的协议称为外部网关协议，以下属于外部网关 协议的是 BGP。
• 所有资源只能由授权方或以授权的方式进行修改，即信息未经授权不能进行改变的特性是 指信息的 完整性。
• 在 Windows 操作系统下，要获取某个网络开放端口所对应的应用程序信息，可以使用命令 netstat。
• 按照我国著作权法的权利保护期，以下权利中，修改权 受到永久保护。
• 结构化分析方法中，数据流图中的元素在 数据字典 中进行定义。
• 软件项目成本估算模型 COCOM01I 中，体系结构阶段模型基于源代码的行数进行估算。
• 用 C/C++语言为某个应用编写的程序，经过预处理、编译、汇编、链接后形成可执行程序。
• 进行面向对象系统设计时，针对包中的所有类对于同-类性质的变化；一个变化若对一个 包产生影响，则将对该包中的所有类产生影响，而对于其他的包不造成任何影响。这属于 共同封闭设计原则
• UML 图中， 对象图展现了某一时刻一组对象以及它们之间的关系。
• 在浏览器的地址栏中输入 xxxyftp.abc.can.cn，在该 URL 中xxxyftp是要访问的主机名。
• 采用 DHCP 动态分配 IP 地址，如果某主机开机后没有得到 DHCP 服务器的响应。则该主机 获取的 IP 地址属于网络169.254.0.0/16。