计算机组成与结构
①立即寻址：操作数就包含在指令中，直接指出操作数本身，速度最快。
②直接寻址：操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址。
③寄存器寻址：操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名。
④寄存器间接寻址：操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中。
⑤间接寻址：指令中给出操作数地址的地址，指令中存放的地址的地址（访问寄存器中的地址），速度最慢。
⑥相对寻址：指令地址码给出的是一个偏移量（可正可负），操作数地址等于本条指令的地址加上该偏移量。
⑦变址寻址：操作数地址等于变址寄存器的内容加偏移量。CPU是计算机的控制中心，主要由运算器、控制器、寄存器组和内部总线等部件组成。
①运算器由算数逻辑单元（ALU）、累加寄存器（AC）、数据缓冲寄存器（DR）、状态条件寄存器（PSW）组成
②寄存器组分为专用寄存器和通用寄存器
③内部总线
④控制器由程序计数器、指令寄存器、指令译码器、时序产生器和操作控制器组成，它是发布命令的“决策机构”，完成协调和指挥整个计算机系统的操作。- 程序计数器(PC，又称为指令计数器):是专用寄存器，具有寄存信息和计数两种功能，在程序开始执行前，将程序的起始地址送入PC，该地址在程序加载到内存时确定，因此PC的初始内容即是程序第一条指令的地址。执行指令时，CPU将自动修改PC的内容，以便使其保持的总是将要执行的下一条指令的地址。由于大多数指令都是按顺序执行的，因此修改的过程通常只是简单地对PC加1。当遇到转移指令时，后继指令的地址根据当前指令的地址加上一个向前或向后转移的位移量得到，或者根据转移指令给出的直接转移的地址得到。为了保证程序指令能够连续地执行下去，CPU必须具有某些手段来确定下一条指令的地址。而程序计数器正起到这种作用，所以通常又称为指令计数器。CPU首先从程序计数器获取指令地址。
- 指令寄存器（IR）:用来保存当前正在执行的指令。当执行一条指令时，先把它从内存取到数据寄存器（DR）中，然后再传送至指令寄存器。为了执行任何给定的指令，必须对操作码进行测试，以便识别所要求的操作。指令译码器就是做这项工作的。指令寄存器中操作码字段的输出就是指令译码器的输入。操作码一经译码后，即可向操作控制器发出具体操作的特定信号。从内存或者告诉缓存读到的指令暂存在指令寄存器。为分析一条指令，操作码和地址码都应该放入指令寄存器。
- 地址寄存器（AR） 用来保存当前CPU所访问的内存单元的地址。由于在内存和CPU之间存在着操作速度上的差别，所以必须使用地址寄存器来保持地址信息，直到内存的读/写操作完成为止。
- 指令译码器（ID） 的功能是对现行指令进行分析，确定指令类型和指令所要完成的操作以及寻址方式，并将相应的控制命令发往相关部件
计算机中主存与外设间进行数据传输的输入输出控制方法有程序控制方式、中断方式、DMA（直接内存读取）等。
在程序控制方式下，由CPU执行程序控制数据的输入输出过程。
在中断方式下，外设准备好输入数据或接收数据时向CPU发出中断请求信号，若CPU决定响应该请求，则暂停正在执行的任务，转而执行中断服务程序进行数据的输入输出处理，之后再回去执行原来被中断的任务。
在DMA方式下，CPU只需向DMA控制器下达指令，让DMA控制器来处理数据的传送，数据传送完毕再把信息反馈给CPU，这样就很大程度上减轻了CPU的负担，可以大大节省系统资源。补码本身是带符号位的，补码可以简化计算机运算部件的设计，补码表示的数字中0是唯一的，不像原码有+0和-0之分，也就意味着机器字长为n位的二进制可以表示2^n个不同的数。机器字长为n，最高位为符号位，则剩余的n-1位用来表示数值，其最大值是这n-1位都为1，也就是2^(n-1)-1。+-0相同的是补码和移码,在计算机中，n位补码（表示数据位），表示范围是-2^(n)-1 ~ 2^(n-1)-1，其中最小值为认为定义，以n=8为例，其中-128的补码是人为定义的10000000
CISC （Complex Instruction Set Computer，复杂指令集计算机）:基本思想是：进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬件化，导致机器的指令系统越来越庞大而复杂。CISC计算机一般所含的指令数目至少300条以上，有的甚至超过500条。
RISC （Reduced Instruction Set Computer，精简指令集计算机）:基本思想是：通过减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周期执行，并通过优化编译提高指令的执行速度，采用硬布线控制逻辑优化编译程序。计算机系统中的CPU内部对通用寄存器的存取操作是速度最快的，其次是Cache，内存的存取速度再次，访问速度最慢的就是作为外存的硬盘。它们共同组成分级存储体系来解决存储容量、成本和速度之间的矛盾。
①全相联地址映射：主存的任意一块可以映象到Cache中的任意一块。发生块冲突概率低。
②直接相联映射：主存中一块只能映象到Cache的一个特定的块中。
③组相联的映射：各区中的某一块只能存入缓存的同组号的空间内，但组内各块地址之间则可以任意存放。两个浮点数相加，先统一阶码，然后对阶，对阶时，小阶向大阶对齐，尾数右移n位。浮点格式表示一个二进制数N的形式为N=2eXF，其中E称为阶码，F叫做尾数。在浮点表示法中，阶码通常为含符号的纯整数，尾数为含符号的纯小数。阶码即指数（常用移码表示，也有用补码的），表示范围，尾数（补码或原码标识）表示精度。
16进制地址之间共有多少存储空间：3FFFH转换成10进制=3 * 16^3+15 * 16^2+15 * 16^1+15 * 16^0减去另外的16进制转10进制，然后+1
计算机系统的存储器按所处的位置可分为内存和外存。
按构成存储器的材料可分为磁存储器、半导体存储器和光存储器。
按存储器的工作方式可分为读写存储器和只读存储器。
按访问方式可分为按地址访问的存储器和按内容访问的存储器。
按寻址方式可分为随机存储器、顺序存储器和直接存储器。
相联存储器是一种按内容访问的存储器程序的局限性表现在时间局部性和空间局部性：时间局部性是指如果程序中的某条指令一旦被执行，则不久的将来该指令可能再次被执行；空间局部性是指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。
程序员可以访问的是程序计数器，指令寄存器对程序员用户透明
总线带宽 = 时钟频率 / 时钟周期 * 总线字节。例：200MHz（时钟频率）/ 5(时钟周期）*（32位/8=4字节)
采用模二除法运算的只有循环冗余检验CRC
可寻址范围 = 内存容量 / 机器字长。内存容量32G，字长32位，可寻址范围：内存容量2GB=2 * 1024 * 1024 * 1024 * 8位，按字编址时，存储单元的个数为2 * 1024 * 1024 * 1024 * 8 / 32=512 * 1024 * 1024，即可寻址范围为512MB
①软件可靠性指的是一个系统对于给定的时间间隔内、在给定条件下无失效运作的概率。可以用MTTF / （1+MTTF）来度量，其中MTTF为平均无故障时间。
②软件可用性是指在给定的时间点上，一个软件系统能够按照规格说明正确运行的概率。可以用MTBF / （1+MTBF）来度量，其中MTBF为平均失效间隔时间。
③软件可维护性是在给定的使用条件下，在规定的时间间隔内，使用规定的过程和资源完成维护活动的概率，可以用1 / （1+MTTR）来度量，其中MTTR为平均修复时间。数据总线用于传输数据信息，地址总线用来传送地址，控制总线用来传送控制信号和时序信号。
釆用总线结构主要有以下优点：
简化系统结构，便于系统设计制造；
大大减少了连线数目，便于布线，减小体积，提髙系统的可靠性；
便于接口设计，所有与总线连接的设备均釆用类似的接口；
便于系统的扩充、更新与灵活配置，易于实现系统的模块化；
便于设备的软件设计，所有接口的软件就是对不同的口地址进行操作；
便于故障诊断和维修，同时也降低了成本。
总线是一组能为多个部件分时共享的信息传送线，用来连接多个部件并为之提供信息交换通路，通过总线复用方式可以减少总线中信号线的数量，以较少的信号线传输更多的信息。流水线 ：取指2ns，分析3ns，执行1ns，100条指令流水线执行= 3（分析时间） * 99 + 6 。顺序执行=6 * 100。
当系统中有多个中断请求时，中断系统按优先级进行排队。若在处理低级中断过程中又有高级中断申请中断，则高级中断可以打断低级中断处理，转去处理高级中断，等处理完高级中断后再返回去处理原来的低级中断，称为中断嵌套。实现中断嵌套用后进先出的栈来保护断点和现场最有效。
一个磁道移到另一个磁道需要6ms，磁道非连续存放，相邻数据快的平均距离为10个磁道，每块的延时及传输时间需要100ms和20ms，读取100快文件需要（6<转移> * 10<距离> + 100 + 20） * 100
千小时可靠度3个部件
串联的可靠度为R * R * R；
并联的可靠度为1-（1-R） * （1-R） * （1-R）；
前两个部件并联后与第三个部件串联的可靠度为（1-（1-R） * （1-R）） * R；第一个部件与后两个部件并联构成的子系统串联的可靠度为R *（1-（1-R） * （1-R））。原码补码移码反码
常见的摘要算法：CRC，MD5，SHA1，SHA256，PIPEMD。
常见的对称加密算法有：DES，三重DES、RC-5、IDEA、AES。
常见的非对称加密算法：RSA、ECC、DSA。一般公钥用于加密和签名，而私钥用于解密和认证。
数字签名算法：RSA；
利用CA的公钥验证数字证书的真实性，利用报文摘要算法生成报文的主要目的是防止报文被篡改；保证数字证书不被篡改的方法是使用CA的私钥对数字证书签名，用户通过CA的签名验证网站的真伪。
A和B使用数字证书对用户的身份进行认证，使用数字签名确保消息不可置否入侵检测技术包括专家系统、模型检测、简单匹配；漏洞扫描不是入侵检测的内容
最先获得键盘或鼠标输入信息的是中断程序
程序语言
n个成员开发小组的沟通路径*n （n-1）/ 2
在源程序中，可由用户（程序员）为变量、函数和数据类型等命名，无法给关键字（保留字）进行命名。
程序设计语言的基本成分包括数据、运算、控制和传输等。程序设计语言的控制成分包括顺序、选择和循环3种结构。
词法分析输出记号流，语法分析没有错误的话构造出语法树，括号不匹配属于语法错误
编译程序对源程序的翻译过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成，以及符号表管理和出错处理。
①源程序可以被看成是一个字符串，词法分析是编译过程的第一阶段，其任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个的“单词”符号,识别其中如关键字（或称保留字）、标识符、常数、运算符以及分隔符（标点符号和括号）等。
②语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”、“语句”、“程序”等。例如程序语句的结构是否合法，语言结构出错、if…end if不匹配，缺少分号、括号不匹配、表达式缺少操作数等。
③语义分析阶段主要检查源程序是否包含语义错误，并收集类型信息供后面的代码生成阶段使用，进行类型分析和检查，主要检测源程序是否存在静态语义错误。包括：运算符和运算类型不符合（String a + int b），取余时用浮点数等。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。
④中间代码是一种简单且含义明确的记号系统，与具体的机器无关，可以有若干种形式。可以将不同的高级程序语言翻译成同一种中间代码。由于与具体机器无关，使用中间代码有利于进行与机器无关的优化处理，以及提高编译程序的可移植性。中间代码是源程序的一种内部表示，或称中间语言。中间代码的作用是可使编译程序的结构在逻辑上更为简单明确，使用中间代码可提高编译程序的可移植性，常见的有逆波兰记号、四元式、三元式和树。目标代码生成阶段的工作与目标机器的体系结构密切相关，分配寄存器的工作在目标代码生成阶段进行语法分析方法分为两类：自上而下（自顶向下）分析法和自下而上（自底向上）分析法，递归下降分析法和预测分析法属于自上而下分析法，移进-归约分析法属于自下而上（自底向上）分析法。语法制导翻译是一种静态语义分析。
有限自动机，进行词法分析的工具
正则表达式
程序运行时的用户内存空间一般划分为代码区、静态数据区、栈区和堆区，其中栈区和堆区也称为动态数据区。全局变量的存储空间在静态数据区
变量是内存单元的抽象，用于在程序中表示数据。当变量存储的是内存单元地址时，称为指针变量，或者说指针变量指向了另一个变量。指针变量可以定义在函数或复合语句内，也可以定义在所有的函数之外，可以是全局变量，也可以是局部变量。需要区分指针变量与指针所指向的变量，无论指针变量指向何种变量，其存储空间大小都是一样的。
操作系统※
前驱图中，PV的排放：箭头的起点是V（释放）操作，箭头的终点位置是P（申请）操作，在前驱图中先分析信号量的位置，根据图中某个操作应该可以得到每个进程的信号量的位置，没有具体信息的话信号量按照从左到右，从上到下进行排放，根据排放获取答案信息
磁盘格式化容量：面数 * （磁道数/面 即每面的磁道数） * （扇区数/道 即每道的扇区数） * （字节数/扇区 即每扇区的字节数）。非格式化容量：面数 * （磁道数/面 即每面的磁道数） * 内圈周长 * 最大密度数。磁道数=外直径-内直径
不发生死锁：（进程所需资源数-1）* 并发数 + 1
McCabe环形复杂度 = e（条数）-n（节点数） + 2
磁盘调度管理中，先进行移臂调度寻找磁道，再进行旋转调度寻找扇区。
因为先来先服务是谁先请求先满足谁的请求，而最短寻找时间优先是根据当前磁臂到要请求访问磁道的距离，谁短满足谁的请求，故先来先服务和最短寻找时间优先算法可能会随时改变移动臂的运动方向
采用中断方式和DMA方式时，CPU与外设可并行工作。程序查询方式是由CPU主动查询外设的状态，在外设准备好时传输数据。
公用信号量，实现进程间的互斥，初始值为1或资源数量；
私用信号量，实现进程间的同步，初始值为0或某个正整数资源可用数为8，有3个进程竞争资源，每个进程需要i个资源，发生死锁的最小值i为4。（i=3时，进程1分配3个资源，进程2分配3个资源，进程3分配2个资源，此时不会发生死锁）
进程控制块的组织方式有链接方式和索引方式。
用户将磁盘块文件逐块从磁盘读入缓冲区，并送至用户区进行处理，采用单缓冲区花费的时间为（块读入缓冲区的时间+缓冲区送入用户区的时间） * 磁盘块 + 系统对每个磁盘块处理的时间，双缓冲区时间：快读入缓冲区的时间 * 磁盘块 + 缓冲区送入用户区的时间 + 系统对每个磁盘块处理的时间
访问一个数据块的时间应为寻道时间+（旋转延迟时间及传输时间之和）。根据题意，每块的旋转延迟时间及传输时间共需120ms，磁头从一个磁道移至另一个磁道需要6ms，但逻辑上相邻数据块的平均距离为10个磁道，即读完一个数据块到下一个数据块寻道时间需要60ms。通过上述分析，本题访问一个数据块的时间T=120ms+60ms=180ms，而读取一个100块的文件共需要18000ms
软件工程基础知识
①极限编程XP是激发开发人员创造性、使得管理负担最小的一组技术，不会使编码速度更快，不用编写测试代码，有价值观、原则、实践、行为四部分组成。价值观包括沟通、简单性、反馈、勇气
②水晶法Crystal认为每一个不同的项目都需要一套不同的策略、约定和方法论；
③并列争球法（Scrum）使用迭代的方法，其中把每30天一次的迭代成为一个冲刺，并按需求的优先级来实现产品。多个自组织和自治小组并行地递增实现产品，并通过简短的日常情况会议进行协调。①瀑布模型是将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型，适合于软件需求很明确的软件项目，难以适应变化的需求。
②V模型是瀑布模型的一种演变模型，将测试和分析与设计关联进行，加强分析与设计的验证。
③演化模型特别适用于对软件需求缺乏准确认识的情况。可以尽快投入使用并在使用过程中不断完善
④原型模型是一种演化模型，通过快速构建可运行的原型系统，然后根据运行过程中获取的用户反馈进行改进。原型的用途是获知用户的真正需求，因此原型模型可以有效地引发系统需求。不可以用来指导代码优化。
⑤螺旋模型将瀑布模型和演化模型结合起来，加入了两种模型均忽略的风险分析。
⑥喷泉模型是典型的面向对象生命周期模型，是一种以用户需求为动力，以对象作为驱动的模型。该模型克服了瀑布模型不支持软件重用和多项开发活动集成的局限性。“喷泉”一词本身体现了迭代和无间隙特性。迭代意味着模型中的开发活动常常需要重复多次，在迭代过程中不断地完善软件系统，适用于大型软件开发，包含维护周期，因此维护与开发之间没有本质区别
⑦增量模型是一种非整体开发的模型，该模型具有较大的灵活性，适合于软件需求不明确的一种模型。使用该模型开发产品，一般是尽快构造出可运行的产品，然后在该产品的基础上再增加需要的新的构建，使产品更趋于完善软件开发配置管理：软件配置标识、变更管理、版本控制、系统建立、配制审核、配置状态报告，不包括风险管理，质量控制
①风险避免即放弃或不进行可能带来损失的活动或工作。例如，为了避免洪水风险，可以把工厂建在地势较高、排水方便的地方，这是一种主动的风险控制方法，是最好的风险控制策略。
②风险监控是指在决策主体的运行过程中，对风险的发展与变化情况进行全程监督，并根据需要进行应对策略的调整。
③风险管理是指在一个肯定有风险的环境里把风险减至最低的管理过程。对于风险我们可以转移，可以规避，但不能消除。风险管理是软件项目管理的一项重要任务。在进行风险管理时，根据风险的优先级来确定风险控制策略，而优先级是根据风险暴露来确定的。
④风险暴露是一种量化风险影响的指标，等于风险影响乘以风险概率，风险影响是当风险发生时造成的损失。
⑤风险概率是风险发生的可能性。
⑥风险控制是风险管理的一个重要活动，定义风险参照水准是风险评估的一类技术，对于大多数软件项目来说成本、速度和性能是三种典型的风险参照水准软件风险一般包括不确定性和损失两个特性，其中不确定性是指风险可能发生，也可能不发生。损失是当风险确实发生时，会引起的不希望的后果和损失。救火和危机管理是对不适合但经常采用的软件风险管理策略。已知风险和未知风险是对软件风险进行分类的一种方式。员工和预算是在识别项目风险时需要识别的因素
①CL0（未完成的）：过程域未执行或未得到CL1中定义的所有目标。
②CL1（已执行的）：其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标。
③CL2（已管理的）：其共性目标是集中于已管理的过程的制度化。根据组织级政策规定过程的运作将使用哪个过程，项目遵循已文档化的计划和过程描述，所有正在工作的人都有权使用足够的资源，所有工作任务和工作产品都被监控、控制、和评审。建立基本的项目管理和实践来跟踪项目费用、进度和功能特性为可重复级的核心；
④CL3（已定义级的）：其共性目标集中于已定义的过程的制度化。过程是按照组织的裁剪指南从组织的标准过程中裁剪得到的，还必须收集过程资产和过程的度量，并用于将来对过程的改进。使用标准开发过程（或方法论）构建（或集成）系统为已定义级的核心；
⑤CL4（定量管理的）：其共性目标集中于可定量管理的过程的制度化。使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的质量目标作为管理准则。管理层寻求更主动地应对系统的开发问题为已管理级的核心；
⑥CL5（优化的）：使用量化（统计学）手段改变和优化过程域，以满足客户的改变和持续改进计划中的过程域的功效，连续地监督和改进标准化的系统开发过程为优先级的核心。概要设计将需求转化为软件的模块划分，确定模块之间的调用关系；
结构化设计方法中，概要设计阶段进行软件体系结构的设计、数据设计和接口设计；
面向对象设计方法中，概要设计阶段进行体系结构设计、初步的类设计/数据设计、结构设计；
详细设计将模块进行细化，得到详细的数据结构和算法；编码根据详细设计进行代码的编写，得到可以运行的软件，并进行单元测试
结构化设计方法中，详细设计阶段进行数据结构和算法的设计。
面向对象设计方法中，详细设计阶段进行构件设计。结构化设计和面向对象设计是两种不同的设计方法，结构化设计根据系统的数据流图进行设计，模块体现为函数、过程及子程序；面向对象设计基于面向对象的基本概念进行，模块体现为类、对象和构件等
Gantt图用水平条状图描述，它以日历为基准描述项目任务，可以清楚地表示任务的持续时间和任务之间的并行，但是不能清晰地描述各个任务之间的依赖关系。
PERT图是一种网络模型，描述一个项目的各任务之间的关系。可以明确表达任务之间的依赖关系，即哪些任务完成后才能开始另一些任务，以及如期完成整个工程的关键路径，但是不能清晰地描述各个任务之间的并行关系。软件需求包括功能需求、非功能需求和设计约束三个方面的内容。
功能需求是所开发的软件必须具备什么样的功能
非功能需求是指产品必须具备的属性或品质，如可靠性、性能、响应时间和扩展性等等，“软件产品必须能够在3秒内对用户请求作出响应”主要表述软件的响应时间，属于非功能需求
设计约束通常对解决方案的一些约束说明。里程碑（最晚多少天不影响工期）关键路径不能缩短工期
COCOMOII估算选择不包括用例数（包括对象点、功能点、代码行）
冗余附加技术是指为实现结构、信息和时间冗余技术所需的资源和技术，包括程序、指令、数据、存放和调动它们的空间和通道等。在屏蔽硬件错误的容错技术中，冗余附加技术包括：关键程序和数据的冗余及调用；检测、表决、切换、重构和复算的实现。在屏蔽软件错误的容错技术中，冗余附加技术包括：冗余备份程序的存储及调用；实现错误检测和错误恢复的程序；实现容错软件所需的固化程序
软件开发过程中，需求分析阶段的输出不包括软件体系结构图
信息库不属于配置数据库。
UP（统一过程）模型是一种以用例和风险为驱动、以架构为中心、迭代并且增量的开发过程，由UML方法和工具支持。UP过程定义了五个阶段，起始阶段、精化阶段、构建阶段、移交阶段和产生阶段。开发过程中有多次迭代，每次迭代都包含计划、分析、设计、构造、集成和测试，以及内部和外部发布，每阶段达到某个里程碑时结束。其中初启阶段的里程碑是生命周期目标，精化阶段的里程碑是生命周期架构，构建阶段的里程碑是初始运作功能，移交阶段的里程碑是产品发布。
初启阶段结束时产生一个构想文档、一个有关用例模型的调查、一个初始的业务用例、一个早期的风险评估和一个可以显示阶段和迭代的项目计划等制品
精化阶段结束时产生一个补充需求分析、一个软件架构描述和一个可执行的架构原型等制品
构建阶段结束成果是一个准备交到最终用户手中的产品，包括具有最初运作能力的在适当的平台上集成的软件产品、用户手册和对当前版本的描述
阶段结束时移交给用户产品发布版本①功能性是指与功能及其指定的性质有关的一组软件质量，功能性包含质量子特性安全性
②可靠性是指衡量在规定的一段时间内和规定条件下维护性能水平的一组软件质量，可靠性质量子特性不包括安全性。
③可维护性是指与软件维护的难易程度相关的一组软件属性
④易使用性是指与使用难易程度及规定或隐含用户对使用方式所做的评价相关的属性。
⑤可维护性质量特性是指与软件维护的难易程度相关的一组软件属性，它包含了易分析性、稳定性、易测试性和易改变性4个子特性。其中：易分析性是描述诊断缺陷或失效原因、判定待修改程度的难易程度的特性。稳定性是描述修改造成难以预料的后果的风险程度，风险程度越低，稳定性越好。易测试性是描述测试已修改软件的难易程度的特性。易改变性是描述修改、排错或适应环境变化的难易程度。
系统开发与运行
外部实体一般为组织机构、人员、第三方系统，试题、图书等不是外部实体
McCabe环形复杂度=e（条数）-n（节点数）+2
数据流图是结构化分析方法的重要模型，用于描述系统的功能、输入、输出和数据存储等。在绘制数据流图中，每条数据流的起点或者终点必须是加工，即至少有一端是加工。在分层数据流图中，必须要保持父图与子图平衡。每个加工必须既有输入数据流又有输出数据流。必须要保持数据守恒。也就是说，一个加工所有输出数据流中的数据必须能从该加工的输入数据流中直接获得，或者是通过该加工能产生的数据。
数据流图中有四个要素：
①外部实体，也称为数据源或数据汇点，表示要处理的数据的输入来源或处理结果要送往何处，不属于目标系统的一部分，通常为组织、部门、人、相关的软件系统或者硬件设备
②数据流表示数据沿箭头方向的流动
③加工是对数据对象的处理或变换
④数据存储在数据流中起到保存数据的作用，可以是数据库文件或者任何形式的数据组织。顶层数据流图描述了系统的输入与输出。对基本加工的说明有三种描述方式：结构化语言、判断表（决策表）、判断树（决策树）。基本加工逻辑描述的基本原则为：1.对数据流图的每一个基本加工，必须有一个基本加工逻辑说明。2.基本加工逻辑说明必须描述基本加工如何把输入数据流变换为输出数据流的加工规则。3.加工逻辑说明必须描述实现加工的策略而不是实现加工的细节。4.加工逻辑说明中包含的信息应是充足的，完备的，有用的，无冗余的
实体联系图也是一个常用的数据模型，用于描述数据对象及数据对象之间的关系。实体联系图有三个要素:
①实体是目标系统所需要的复合信息的表示，也称为数据对象
②属性定义数据对象的特征
③联系是不同数据对象之间的关系。在该系统中患者是一个数据对象，即实体，具有多种属性演绎推理，就是从一般性的前提出发，通过推导即“演绎”，得出具体陈述或个别结论的过程。
归纳法以一系列经验事物或知识素材为依据，寻找出其服从的基本规律或共同规律，并假设同类事物中的其他事物也服从这些规律，从而将这些规律作为预测同类事物的其他事物的基本原理的一种认知方法①数据耦合：一个模块访问另一个模块时，彼此之间是通过简单数据参数（不是控制参数、公共数据结构或外部变量）来交换输入、输出信息的。
②公共耦合：若一组模块都访问同一个公共数据环境，则它们之间的耦合就称为公共耦合。公共的数据环境可以是全局数据结构、共享的通信区、内存的公共覆盖区等。
③外部耦合：一组模块都访问同一全局简单变量而不是同一全局数据结构，而且不是通过参数表传递该全局变量的信息，则称之为外部耦合。
④标记耦合：一组模块通过参数表传递记录信息，数据结构本身传递就是标记耦合。这个记录是某一数据结构的子结构，而不是简单变量
⑤控制耦合：是指一个模块通过传送开关、标志、名字等控制信息，明显的控制另一个模块的功能
⑥内容耦合：若一个模块直接访问另一个模块的内部数据、一个模块不通过正常入口转到另一个模块内部、两个模块有一部分程序代码重叠或者一个模块有多个入口。结构化分析的输出不包括结构图！
①偶然内聚/巧合内聚：指一个模块内的各个处理元素之间没有任何联系。具有最低的内聚性，是最不好的一种内聚类型，不易修改，不易理解，不易维护，会影响到模块间的耦合关系
②逻辑内聚：指模块内执行几个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。
③时间内聚：把需要同时执行的动作组合在一起形成的模块。
④通信内聚：指模块内所有处理元素都在同一个数据结构上操作，或者指各处理使用相同的输入数据或者产生相同的输出数据。
⑤顺序内聚/过程内景：指一个模块中各个处理元素都密切相关于同一功能且必须顺序执行，前一个功能元素的输出就是下一个功能元素的输入。
⑥功能内聚：是最强的内聚，指模块内所有元素共同完成一个功能，缺一不可数据字典是指对数据的数据项、数据结构、数据流、数据存储、处理逻辑、外部实体等进行定义和描述，其目的是对数据流程图中的各个元素做出详细的说明，使用数据字典为简单的建模项目。其条目有数据流、数据项、数据存储、基本加工等，不包括外部实体
系统结构图（SC）又称为模块结构图，它是软件概要设计阶段的工具，反映系统的功能实现和模块之间的联系与通信，包括各模块之间的层次结构，即反映了系统的总体结构。SC包括模块、模块之间的调用关系、模块之间的通信和辅助控制符号等4个部分，不包括数据
单元测试主要是发现程序代码中的问题，针对详细设计和软件实现阶段的工作进行的；
集成测试验证系统模块是否能够根据系统和程序设计规格说明的描述进行工作，即模块以及模块之间的接口的测试
系统测试则是验证系统是否确实执行需求规格说明中描述的功能和非功能要求，因此测试目标在需求分析阶段就已经定义软件的可维护性是指维护人员理解、改正、改动和改进这个软件的难易程度，是软件开发阶段各个时期的关键目标。
软件系统的可维护性评价指标包括可理解性、可测试性、可修改性、可靠性、可移植性、可使用性和效率，没有可扩展性。
系统的可维护性的评价指标包括：可理解性、可测试性、可修改性。没有可移植性软件维护的类型一般有四类：
正确性维护是指改正在系统开发阶段已发生而系统测试阶段尚未发现的错误；
适应性维护是指使应用软件适应信息技术变化和管理需求变化而进行的修改
完善性维护是为扩充功能和改善性能而进行的修改
预防性维护是为了改进应用软件的可靠性和可维护性，为了适应未来变化的软硬件环境的变化，主动增加预防性的新的功能，以适应将来各类变化。白盒测试也称为结构测试，根据程序的内部结构和逻辑来设计测试用例，对程序的路径和过程进行测试，检查是否满足设计的需要。其常用的技术有逻辑覆盖、循环覆盖和基本路径测试。在逻辑覆盖中，
语句覆盖是指选择足够的测试数据使被测试程序中每条语句至少执行一次。是最弱的覆盖准则
判定覆盖是指选择足够的测试数据使被测试程序中每个判定表达式至少获得一次“真”值和“假”值。
条件覆盖是指构造一组测试用例，使得每一判定语句中每个逻辑条件的各种可能的值至少满足一次。
路径覆盖是指覆盖被测程序中所有可能的路径。可以比语句覆盖法发现更多的错误
黑盒测试也称为功能测试，在完全不考虑软件的内部结构和特性的情况下来测试软件的外部特性。在单元测试基础上，将所有模块按照设计要求组装为系统，此时进行的测试称为集成测试。
集成测试有多种策略：自底向上：从系统层次中最底层的构件开始测试，逐步向上。需要设计驱动模块来辅助测试。自顶向下：与自底向上相反，从最顶层的构件开始，逐步向下。需要设计桩模块来辅助测试。三明治：结合自底向上和自顶向下两种测试策略。该测量的优势是结合了自底向上和自顶向下的优点，如较早地验证了主要的控制构件和底层模块，并行测试程度较高等。但缺点是需要写较多的驱动模块和桩模块。一次性：对所有构件一次性测试，然后集成。软件测试的目的时发现更多的错误，而不是证明软件的正确性
仓库风格缺点包括测试困难，不能保证有好的解决方案，难以建立好的控制策略，低效，昂贵的开发工作，缺少对并行机制的支持。优点包括对可更改性和可维护性的支持，可复用的知识源，支持容错性和健壮性。
网络与多媒体基础知识
网络层-路由器,可以识别IP地址，进行数据包的转发。
数据链路-层-网桥和交换机，网桥可以识别MAC地址，进行帧转发。交换机是由硬件构成的多端口网桥。传输层和会话层主要是软件功能，都不需要专用的联网设备。
物理层-中继器、集线器，中继器作用是对接收的信号进行再生放大，以延长传输的距离。集线器作用是从一个端口接收信息并向其他端口广播出去应用层（HTTP，DNS，SSH，FTP），表示层，会话层，传输层（TCP，UDP，TLS，OSI/RM），网络层（IP协议，ARP，ICMP（封装在IP数据报中传送，不保证可靠的提交）），数据链路层（WIFI），物理层（光纤）
①表现媒体是指进行信息输入和输出的媒体，如键盘、鼠标、话筒，以及显示器、打印机等；
②表示媒体指传输感觉媒体的中介媒体，即用于数据交换的编码，如图像编码、文本编码和声音编码等；
③传输媒体指传输表示媒体的物理介质，如电缆、光缆、电磁波等；
④存储媒体指用于存储表示媒体的物理介质，如硬盘、光盘等，
⑤感觉媒体指直接作用于人的感觉器官，使人产生直接感觉的媒体，如引起听觉反应的声音，引起视觉反应的图像等图像数据量=图像的总像素X图像深度（b）,需用光盘数量的计算方式如下：
光盘数量=图像的总像素 X 图像深度/4GB（张）DNS域名查询的次序是：本地的hosts文件一>本地DNS缓存一>本地DNS服务器一>根域名服务器
如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用隧道技术，如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用翻译技术
数字签名技术是不对称加密算法的典型应用。数字签名的应用过程是：数据源发送方使用自己的私钥对数据校验和或其他与数据内容有关的变量进行加密处理，完成对数据的合法“签名”；数据接收方则利用对方的公钥来解读收到的“数字签名”，并将解读结果用于对数据完整性的检验，以确认签名的合法性。数字签名技术是在网络系统虚拟环境中确认身份的重要技术，完全可以代替现实过程中的“亲笔签字”，在技术和法律上有保证，可见数字签名是对签名真实性的保护
ARP攻击（ARP欺骗）是欺骗攻击的一种，通过伪造IP地址和MAC地址，能够在网络中产生大量的ARP通信量使网络阻塞，如果伪造网关的IP地址和MAC地址对，则所有发往网关的IP包将因为MAC地址错误而无法到达网关（ARP攻击一般会将MAC地址改为发起ARP攻击的主机地址），造成无法跨网段通信。处理ARP攻击的方法为首先断开ARP攻击主机的网络连接，然后用“arp-d”命令清除受攻击影响的ARP缓存
矢量图是根据几何特性来绘制图形，矢量可以是一个点或一条线，矢量图只能靠软件生成，文件占用内在空间较小，因为这种类型的图像文件包含独立的分离图像，可以自由无限制的重新组合。它的特点是放大后图像不会失真，和分辨率无关，适用于图形设计、文字设计和一些标志设计、版式设计等。矢量图中的图形元素称为图元。而另一类图具有代表性的图像表示形式是位图图像，该图采用像素来表示图像，用矢量图形格式表示复杂图像（如人物、风景照片），并且要求很高时，将需要花费大量的时间进行变换、着色和处理光照效果等。因此，矢量图形主要用于表示线框型的图画、工程制图和美术字等。位图图像是指用像素点来描述的图。图像适合于表现比较细腻，层次较多，色彩较丰富，包含大量细节的图像，并可直接、快速地在屏幕上显示出来。但占用存储空间较大，一般需要进行数据压缩
声音信号是模拟信号，要使声音信号数字化并传递，首先要进行A/D转换，模拟信号转数字信号
IP地址155.32.90.192/26包含了多少个主机地址？答：IPV4地址是由32个2进制位组成，/26代表前26位是网络位，剩下的6位为主机地址，32-26=6即每个网络可以有2^6-2个主机地址
A类网络主机地址数2^24个，
VLAN（虚拟局域网）允许逻辑的划分网段
一个标准的URL格式如下：协议://主机名.域名.域名后缀或IP地址:端口号/目录/文件名目录可能是多级的wb.xyz.com.cn、
DHCP协议的功能室自动分配IP地址
数据库技术
函数依赖 （部分依赖，完全依赖，传递依赖）A->B，B完全依赖与A。AB->C,C部分依赖于A和B，A->B,B->C,C传递依赖于A，A->BC，即满足A->B,A->C
E-R模型向关系模型转换时，两个以上实体之间多对多的联系应该转换为一个独立的关系模式，且该关系模式的关键字由这些实体的关键字组成，也需要重新建类，且该关系模式的关键字由这些实体的关键字组成
数据库通常采用三级模式结构，其中，视图对应外模式、基本表对应模式、存储文件对应内模式
数据库管理系统利用日志文件来进行事务故障恢复和系统故障恢复。在事务处理过程中，DBMS把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。当系统正常运行时，按一定的时间间隔，把数据库缓冲区内容写入数据文件；一旦发生故障，DBMS的恢复子系统利用日志文件撤销事务对数据库的改变，回退到事务的初始状态
排他锁又称为写锁，用于对数据进行写操作时进行锁定。如果事务T对数据A加上排他锁后，就只允许事务T读取和修改数据A，其他事务对数据A不能再加任何锁，从而也不能读取和修改数据A，直到事务T释放A上的锁
共享锁又称为读锁，用于对数据进行读操作时进行锁定。如果事务T对数据A加上了读锁后，事务T就只能读数据A但不可以修改，其他事务可以再对数据A加读锁来读取，只要数据A上有读锁，任何事务都只能再对其加读锁（读取）而不能加写锁（修改）①分片透明：是指用户不必关系数据是如何分片的，它们对数据的操作在全局关系上进行，即关系如何分片对用户是透明的，因此，当分片改变时应用程序可以不变。分片透明性是最高层次的透明性，如果用户能在全局关系一级操作，则数据如何分布，如何存储等细节自不必关系，其应用程序的编写与集中式数据库相同。
②复制透明：用户不用关心数据库在网络中各个节点的复制情况，被复制的数据的更新都由系统自动完成。在分布式数据库系统中，可以把一个场地的数据复制到其他场地存放，应用程序可以使用复制到本地的数据在本地完成分布式操作，避免通过网络传输数据，提高了系统的运行和查询效率。但是对于复制数据的更新操作，就要涉及到对所有复制数据的更新。
③位置透明：是指用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的
④局部映像透明性（逻辑透明）：最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关系局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统是非常重要的DDBS的基本特点：1.物理分布性：数据不是存储在一个场地上，而是存储在计算机网络的多个场地上。2.逻辑整体性：数据物理分布在各个场地，但逻辑上是一个整体，它们被所有用户（全局用户）共享，并由一个DDBMS统一管理。3.场地自治性：各场地上的数据由本地的DBMS管理，具有自治处理能力，完成本场地的应用（局部应用）。4.场地之间协作性：各场地虽然具有高度的自治性，但是又相互协作构成一个整体
1NF:数据库表的每一列都是不可分割的基本数据项，同一列中不能有多个数据值，不能再一列中存放多个属性，例如员工信息表，不能再信息一列中放入电话住址等信息，应单独设计成电话一列，住址一列
2NF：每个表必须有主键，其他信息与主键一一对应，通常称这种关系为函数依赖关系，即表中其他数据元素都依赖于主键，或称该数据元素唯一的被主键所标识，例如学生表（id，姓名，成绩，合格状态）合格状态不依赖于学生信息依赖于成绩，不符合第二范式
3NF：要求一个数据库表中不包含已在其他表中已包含的非主关键字信息，例如学生表（id，姓名，班级id，班级位置）班级表（id，名称，位置）通过学生表的班级id可以得到班级位置，无需在学生表中增加班级位置字段
BCNF：所有非主属性对每一个候选键都是完全函数依赖，所有的主属性对每一个不包含他的候选键，也是完全函数依赖，没有任何属性完全函数依赖于非候选键的任何一组属性①原子性（Atomicity）：事务是原子的，要么做，要么都不做。
②一致性（Consistency）：事务执行的结果必须保证数据库从一个一致性状态变到另一个一致性状态。
③隔离性隔离性（lsolation）：事务相互隔离。当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程，对其它事物都是不可见的。
④持久性（Durability）：一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也永久有效R1▷◁R2为自然联接，自然联接是一种特殊的等值联接，它要求两个关系中进行比较的分量必须是相同的属性，并且在结果集中将重复属性列去掉
派生属性：学生表中有生日和年龄字段，根据生日可以推算出年龄，所以年龄属于派生属性
简单属性：与复合属性相对的，就是简单属性
多值属性：一个人有多个电话号码，多个爱好，多个亲属，这些属于多值属性
复合属性：可以拆分的属性就是属于复合属性，例如家庭地址可以拆分为省县乡门牌号字段给定关系模式R（A1，A2，A3，A4），函数依赖F（A1A3->A2，A2->A3），将R分解为{（A1，A2）（A1，A3）}则该分解为有损连接且不保持函数依赖。能够推出所有属性且不含多余属性的属性组称为候选码。由于A1A3→A2，根据函数依赖的性质，可知属性组A1A3决定属性A1、A2、A3，但它不能成为R的候选码，因为还有一个属性A4，A1A3不能决定它。因此，R的候选码为A1A3A4。在分解p中，我们发现少了属性A4，而且把两个函数依赖都丢了，因为关系(A1，A2)没覆盖函数依赖集F中任何一个函数依赖，关系(A1，A3)亦如此，所以分解p既是有损连接又不保持函数依赖
首先判断候选码，先找入度为0的结点，本题中A1没有在函数依赖右侧出现，因此体现在图示中，即入度为0，候选码必定包含属性A1。
π1,5,7 ->（Φ2=5）即对R × S结果第1、5、7列的投影，对应属性R.A、S.B、S.E；FROM R,S后跟随的是结果元组行的WHERE筛选条件，即对R × S结果选择第2列=第5列的元组，对应属性为R.B=S.B
算法与数据结构※
①图的存储结构邻接表对每个点和每条边都要遍历一遍，时间复杂度O(n（节点）+e（边)），邻接矩阵时间复杂度O(n^2)
②无向图的邻接矩阵是一个对称矩阵，每条边会表示两次，因此矩阵中的非零元素数目为2e，有向图使用邻接矩阵存储，矩阵中的非零元素数目为e
③完全图适合采用邻接矩阵存储。
④无向连通图只保证每对结点间都有路径。
⑤顶点数为n，变数为e，对于无向图中的两个顶点u和v，若存在边（u，v），则该边为计算U的度和V的度各贡献一个值1，因此，所有顶点的度数之和为e的两倍①图的遍历是指对图中所有顶点进行访问且只访问一次的过程。因为图的任一个结点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径又回到该结点上。因此为了避免顶点的重复访问，在图的遍历过程中，必须对已访问过的顶点进行标记。
②深度优先遍历和广度优先遍历是两种遍历图的基本方法。广度优先遍历方法为：从图中某个顶点V出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有己被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直至图中所有的顶点都被访问到为止。广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。为此，引入队列来保存己访问过的顶点序列，即每当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队①完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点，去掉最后一层是满二叉树，在形态上是平衡二叉树，完全二叉树的高度h与其节点数n之间存在确定的关系
②平衡二叉树（AVL）：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树
③最优二叉树：哈夫曼树（权值最小的两个节点互为兄弟节点）二叉树的节点总数2n-1（n个权值），哈夫曼树中叶子节点的权值越小则距离树根越远，叶子节点的权值越大则距离树根越近
④满二叉树：每一层上的节点数均达到最大值二叉树遍历：前序遍历-根左右，中序遍历-左根右，后序遍历-左右根，前序遍历和后序遍历不能够造出二叉树的中序遍历序列
①归并排序：在最坏情况下，时间复杂度是O（nlogn）；空间复杂度O(n)，采用分治法
②选择排序：不稳定性。每一轮选出最小者交换到左侧，最大优势省去了多余的元素交换，时间复杂度O(n^2),空间复杂度O(1)
③插入排序：维护一个有序区，把元素一个一个插入到有序区的适当位置，直到所有元素有序为止，时间空间复杂度On、O1，最坏的情况下时间复杂度为O(n^2),空间复杂度为O(1)
④快速排序：冒泡排序演化而来，用了分治法的思想，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一端，从而把数列拆解成了两个部分,时间复杂度平均O(nlogn)最坏O(n^2)，空间复杂度O(1)
⑤鸡尾酒排序：冒泡排序的优化适合大部分元素已经有序
⑥希尔排序：直接插入排序的升级版，预处理数据使元素变成基本有序,时间复杂度O(n^1.3),空间复杂度O(1)
⑦输入数组{1，1，2，4，7，5}基本有序（从小到大），在这种情况下，插入排序算法的时间复杂度为0（n），归并排序和堆排序的时间复杂度为0（nlgn），而快速排序的时间复杂度为0（n2）
⑧ 插入排序在输入数据基本有序的情况下，是其计算时间的最好情况，复杂度为O（n），其他情况下时间复杂度为O（n2）。快速排序在输入数据有序或者逆序的情况下，是其计算时间的最坏情况，复杂度为O（n2），其他情况下时间复杂度为O（nlgn）。而归并排序和堆排序算法在所有情况下的时间复杂度均为O（nlgn）①分治法：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
②动态规划法：对于每一步的决策，列出各种可能的局部解，在依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。动态规划算法与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
③贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。例：地杰斯特拉算法、背包算法，贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
④回溯算法（试探法）：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。例：皇后问题，回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。节点的度定义为节点的子树数目
①栈和队列都是操作受限的线性表：栈仅在表尾插入和删除元素；队列仅在表头删除元素、在表尾插入元素。
②采用单循环链表表示队列：入队时初始队列为空、出队后队列变为空要进行特殊处理。入队操作和出队操作均与队列长度无关，因此其时间复杂度都为O1。
③队列是先入先出的线性表，栈是后进先出的线性表。一个线性序列经过队列结构后只能得到与原序列相同的元素序列，而经过一个栈结构后则可以得到多种元素序列。用两个栈可以模拟一个队列的入队和出队操作。若入栈和入队的序列相同，则出栈序列和出队序列可能相同，出栈序列和出队序列可能互为逆序，入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1：n（n>=1）
④使用单链表作为栈的存储结构，因为栈的操作是先进后出，因此无论是入栈还是出栈，都只对栈顶元素操作，而在单链表中用头指针作为栈顶指针，此时无论是出栈还是入栈，都只需要对头指针指向的栈顶指针操作即可，不需要遍历链表
⑤二分查找在链表结构上无法实现
⑥优先队列是一种常用的数据结构，通常用堆实现。对应于大顶堆和小顶堆，存在最大优先队列和最小优先队列。以最大优先队列为例，优先队列除了具有堆上的一些操作，如调整堆、构建堆之外，还有获得优先队列的最大元素，抽取出优先队列的最大元素，向优先队列插入一个元素和增大优先队列中某个元素的值。其中除了获得优先队列的最大元素的时间复杂度为O1之外，其他几个操作的时间复杂度均为二叉树的高度，即O（lgn）
面向对象技术
里程碑关键路是开始到结束的最长路径，代表最短周期
多对多联系需要单独转换为一个关系模式，也需要重新建类
面向对象分析主要强调理解问题是什么，不考虑问题的解决方案
面向对象设计侧重问题的解决方案，并且需要考虑实现细节问题。①开-闭原则是指一个软件实体应当对扩展开放，对修改关闭
②里氏代换原则（LSP）是指一个软件实体如果使用的是—个基类的话，那么一定适用于其子类，而且软件系统觉察不出基类对象和子类对象的区别,原则：子类可以替换父类；
③依赖倒转原则（DIP）就是要依赖于抽象，而不依赖于实现，或者说要针对接口编程，不要针对实现编程。
④单一职责原则：设计目的单一的类
⑤接口隔离原则：使用多个专门的接口比使用单一的总接口要好不同的对象在接收统一消息时可以产生完全不同的结果，这一现象称为多态，由继承机制实现。多态有参数多态、包含多态、过载多态和强制多态四类。
①参数多态：是应用比较广泛的多态，被称为最纯的多态List list;list.add(HashMap);list.add(ConcurrentHashMap)
②包含多态：在许多语言中都存在，最常见的例子就是子类型化，即一个类型是另一个类型的子类型。List list = new ArrayList;
③过载多态：是同一个名字在不同的上下文中所代表的含义不同(重载)，同一个名字在不同上下文中可代表不同的含义
④强制多态：int+double①泛化是一个类与它的一个或多个细化类之间的关系，表达一般与特殊的关系。C++使用’:’，java使用extends来表示泛化关系
②关联是类与类之间的一种结构关系。它描述了一组链，链是对象之间的连接,比依赖关系更强，不存在依赖关系的偶然性，关系也不是临时性一般是长期性,两个类之间可以有多个由不同角色标识的关联
③依赖是两个事物间的语义关系，其中一个事物（独立事物）发生变化会影响另一个事物（依赖事物）的语义，特定事物的改变有可能影响到其他事物，假设A类变化引起了B类变化，说明B类依赖于A类.若类A的方法中仅仅使用了类B的对象，那么类A依赖于类B。
④聚合关系表示整体和部分的关系，整体和部分可分开，若类A对象消失时，其他类的实例仍然存在并工作，那么就是聚合。
⑤组合是一种聚合关系，但是整体与部分不可分开，其中整体负责其部分的创建和销毁，如果整体不存在了，部分也将不存在。如果类A的部分是由类B的对象组成，并且类A控制类B的生命周期，那么类A与类B是组合关系，类A对象消失时，类B也消失，就是组合关系
⑥实现关系是用来规定接口和实现类或者构建结构的关系
做题时查看是否出现变化或者消失的字眼，出现变化的话，A变化不会影响B变化就是关联关系，A变化会影响B变化就是依赖关系，出现消失的话，A消失B也消失就是组合关系，A消失B不会消失就是聚合关系
实体类:主要负责数据和业务逻辑；
边界类（接口类）:负责和用户进行交互，即用户界面
控制类:则负责实体类和界面类的交互1.类图展现了一组对象、接口、协作和它们之间的关系。在开发软件系统时，类图用于对系统的静态设计视图建模
2.对象图展现了一组对象以及其之间的关系，描述了在类图中所建立的事物的实例的静态快照。
3.序列图是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动。对象图的对象名会有标识，关联关系一般不会出现多重度。同步消息用实心三角箭头表示
4.通信图和序列图同构，强调收发消息的对象的结构组织。
5.状态图展现了一个状态机，由状态、转换、事件和活动组成，它关注系统的动态视图，强调对象行为的事件顺序。事件触发一个没有特定监护条件的迁移，对象不一定离开当前状态
6.活动图是一种特殊的状态图，展现了在系统内从一个活动到另一个活动的流程，它专注于系统的动态视图。适合对业务流程进行进一步建模。
序列图、通信图、交互图和定时图均被称为交互图，它们用于对系统的动态方面进行建模
7.类图（Class Diadram）展现了一组对象、接口、协作和它们之间的关系。在面向对象系统的建模中，最常见的就是类图，它给出系统的静态设计视图。
8.组件图（Component Diagram）展现了一组组件之间的组织和依赖。专注于系统的静态实现视图，与类图相关，通常把组件映射为一个或多个类、接口或协作。
9.通信图（communication diagram）。通信图也是一种交互图，它强调收发消息的对象或参与者的结构组织。
10.部署图（Deploy Diagram）是用来对面向对象系统的物理方面建模的方法，展现了运行时处理结点以及其中构件（制品）的配置，部署图给出了体系结构的静态实施视图。它与构件图相关，通常一个节点包含一个或多个构件，依赖关系类似于包依赖，软件系统中软件组件和硬件组件之间的物理关系通常采用UML中的部署图。
11.对象图（Object Diagram）展现了某一时刻一组对象以及它们之间的关系。对象图描述了在类图中所建立的事物的实例的静态快照，给出系统的静态设计视图或静态进程视图。
12.用例图（Use Case Diagram）展现了一组用例、参与者（Actor）以及它们之间的关系。这个视图主要支持系统的行为，即该系统在它的周边环境的语境中所提供的外部可见服务。用例图用于对一个系统的需求进行建模，包括说明这个系统应该做什么（从系统外部的一个视点出发），而不考虑系统应该怎样做。
13.状态图可以了解到一个对象所能到达的所有状态以及对象收到的事件（消息、超时、错误、条件满足等）对对象状态的影响等
14.序列图是强调消息时间顺序的交互图；
15.时序图（Timing Diagram）关注沿着线性时间轴、生命线内部和生命线之间的条件改变。
16.交互概览图强调控制流的交互图。交互图用于对系统的动态方面进行建模。一张交互图表现的是一个交互，由一组对象和它们之间的关系组成，包含它们之间可能传递的消息。交互图表现为序列图、通信图、交互概览图和时序图，每种针对不同的目的，能适用于不同的情况。UML2.0中提供了多种图形，从静态和动态两个方面表现系统视图。静态方面有类图，对象图，序列图、通信图、交互图和定时图均被称为交互图，它们用于对系统的动态方面进行建模
UML中引入同步的概念，用同步棒–黑色粗线条表示+并发分支与会和
面向对象分析包含5个活动：认定对象、组织对象、描述对象间的相互作用、定义对象的操作、定义对象的内部信息
1.命令（Command）模式通过将请求封装为一个对象，可将不同的请求对客户进行参数化从而使使用者可以釆用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤销的操作。
2.策略（Strategy）设计模式定义一系列算法，把它们一个个封装起来，并且使它们可相互替换。这一模式使得算法可独立于它的客户而变化。
3.抽象工厂（Abstract Factory）模式提供一个创建一系列相关或相互依赖对象的接口，而无需指定他们具体的类。
4.状态（State）模式是使得一个对象在其内部状态改变时通过调用另一个类中的方法改变其行为，使这个对象看起来如同修改了它的类。
5.责任链（Chain of Responsibility）模式将多个对象的请求连成一条链，并沿着这条链传递该请求，直到有一个对象处理它为止，避免请求的发送者和接收者之间的耦合关系。是行为型对象模式
6.观察者（Observer）模式定义对象之间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。Subject（目标）知道他的观察者，Observer（观察者）为那些在目标发生改变时需获得通知的对象定义一个更新接口。ConcreteSubject（具体目标）将有关状态存入各ConcreteObserver（具体观察者）对象，当它的状态发生改变时，向它的各个观察者发出通知，ConcreteObserver（具体观察者）维护一个指向ConcreteSubject（具体目标）对象的引用，存储有关状态，实现Observer（观察者）的更新接口以使自身状态与目标的状态保持一致。
7.享元设计模式是运用共享技术来有效的支持大量细粒度的对象。
8.外观（Facade）模式为子系统中的一组接口提供一个一致的界面，Facade模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。适用于需要为一个复杂子系统提供一个简单接口的情况
9.适配器（Adapter）模式是将类的接口转换成客户希望的另外一个接口，使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。是一种结构性模式。将已有类的接口转换成和目标接口兼容
10.桥接模式将对象的抽象和其实现分离，从而可以独立地改变它们。
11.组合（Composite）模式描述了如何构造一个类层次式结构，来表示部分-整体的层次结构。
12.装饰器（Decorator）模式的意图是动态地给一个对象添加一些额外职责。在需要给某个对象而不是整个类添加一些功能时使用。这种模式对增加功能比生成子类更加灵活
13.访问者模式系统要求这些对象实施一些依赖于某具体类（Checkout）的操作时，可以使用此模式
14.迭代器模式（Iterator）：提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示。是行为型对象模式
15.解释器模式（Interpreter）：给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子。
16.生成器（Builder）模式将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。生成器模式适用于以下几种情况：①当创建复杂对象的算法应该独立于该对象的组成部分以及它们的装配方式时；②当构造过程必须允许被构造的对象有不同的表示时。工厂方法（Factory Method）定义一个用于创建对象的接口，让子类决定将哪一个类实例化，使一个类的实例化延迟到其子类。工厂方法适用于以下几种情况：①当一个类不知道它所必须创建的对象的类的时候；②当一个类希望由它的子类来指定它所创建的对象的时候；③当类将创建对象的职责委托给多个帮助子类中的某一个，并且你希望将哪一个帮助子类是代理者这一信息局部化的时候。
17.原型（Prototype）模式用原型实例指定创建对象的种类，并且通过拷贝这个原型来创建新的对象。原型模式适用于以下几种情况：①当一个系统应该独立于它的产品创建、构成和表示时；②当要实例化的类是在运行时刻指定时，例如，通过动态装载；③为了避免创建一个与产品类层次平行的工厂类层次时；④当一个类的实例只能有几个不同状态组合中的一种时，建立相应数目的原型并克隆它们可能比每次用合适的状态手工实例化该类更方便一些。
18.单例（Singleton）设计模式是一种创建型模式，其意图是保证一个类仅有一个实例，并提供一个访问这个唯一实例的全局访问点。单例模式适用于以下情况：①当类只能有一个实例而且客户可以从一个众所周知的访问点访问它时；②当这个唯一实例应该是通过子类化可扩展的，并且客户应该无须更改代码就能使用一个扩展的实例时事物：模型中的基本成员。UML中包括结构事物、行为事物、分组事物和注释事物。
①结构事物：模型中静态部分。[类Class]+[接口Interface]+[协作Collaboration]+[用例UseCase]+[活动类]+[组件Component]+[结点Node]
②行为事物：模型中的动态部分。[交互]+[状态机]
③分组事物：可以把分组事物看成是一个“盒子”，模型可以在其中被分解。目前只有一种分组事物，即包（Package）。结构事物、动作事物、甚至分组事物都有可能放在一个包中。包纯粹是概念上的，只存在于开发阶段，而组件在运行时存在。
④注释事物：注释事物是UML模型的解释部分绑定是一个把过程调用和响应调用所需要执行的代码加以结合的过程。在一般的程序设计语言中，绑定是在编译时进行的，叫做静态绑定。动态绑定则是在运行时进行的，因此，一个给定的过程调用和代码的结合直到调用发生时才进行。动态绑定是和类的继承以及多态相联系的。在运行过程中，当一个对象发送消息请求服务时，要根据接收对象的具体情况将请求的操作与实现的方法进行连接，即动态绑定
标准化和知识产权
- 著作权中的署名权、修改权、保护作品完整权的保护期不受限制。发表权保护期受时间限制。
- 商标权有可能无限期拥有的知识产权，保护期限可以延长
- 软件著作权中翻译权是指以不同于原软件作品的一种程序语言转换该作品原使用的程序语言，而重现软件作品内容的创作的产品权利。简单地说，也就是指将原软件从一种程序语言转换成另一种程序语言的权利
- 客户提供工具软件的复制品，这里侵犯了工具软件的软件著作权
下午题
数据库设计
数据流图-实体联系图
1.使用说明中的语句对图1-1中的实体E1-E4的名称
2.使用说明中的语句对图1-2中的数据存储D1-D3的名称
3.很据注明和图中术语，补齐图1-2中缺失的数据及起点和终点
4.根据说明，采用结构化语言对逻辑进行描述
结构化分析将数据和处理作为分析对象，数据的分析结果表示了现实世界中实体的属性及其之间的相互关系，而处理的结果则展现了系统对数据的加工和转换。面向数据流建模是目前仍然被广泛使用的方法之一，而DFD则是面向数据流建模中的重要工具，DFD将系统建模成输入一处理一输出的模型，即流入软件的数据对象，经由处理的转换，最后以结果数据对象的形式流出软件。在实际使用DFD进行数据流建模时，需要注意以下原则：①加工处理和数据流的正确使用，如一个加工必须既有输入又有输出；数据流只能和加工相关，即从加工流向加工、数据源流向加工或加工流向数据源。②每个数据流和数据存储都要在数据字典中有定义，数据字典将包括各层数据流图中数据元素的定义。③数据流图中最底层的加工处理必须有加工处理说明。④父图和子图必须平衡，即父图中某加工的输入输出（数据流）和分解这个加工的子图的输入输出数据流必须完全一致，这种一致性不一定要求数据流的名称和个数一一对应，但它们在数据字典中的定义必须一致，数据流或数据项既不能多也不能少。⑤加工处理说明和数据流图中加工处理涉及的元素保持一致。例如，在加丄处理说明中，输入数据流必须说明其如何使用，输出数据流说明如何产生或选取，数据存储说明如何选取、使用或修改。⑥一幅图中的图元个数控制在7+2以内。在题目所示的DFD图中，数据流DF2、DF6和DF7的输入、输出均不是加工，这与“数据流只能和加工相关，即从加工流向加工、数据源流向加工或加工流向数据源”相违背。加工P1只有输出，没有输入；加工P3只有输入没有输出，这与“一个加工必须既有输入又有输出”相违背。数据流DF4经过加工P4之后没有发生任何改变，说明该数据对加工P4是没有作用的，根据数据守恒原理，这条数据流不应与P4有关联。
