软件设计师易错题分析总结

admin 管理员组

文章数量: 1086019

问题

1. 系统可靠性如何计算？计算公式？

   串联系统计算：R总=R1 * R2;

   并联系统计算：R总=1-（1-R）^ n；

   N模混联系统：先将整个系统划分为多个部分串联R1、R2…等，再计算R1、R2内部的并联可靠性，带入原公式。

2. 内存字节编址，计算字节占用。

   地址相减计算存储单元个数？例如：地址从A0000H到CFFFFH（H为16进制后缀，其余位计算）

   存储区域总容量=存储单元个数×存储单元内容

   总容量=单位芯片容量×片数

3. 后缀表达式（逆波兰式）

   使用二叉树的后续遍历进行解题。

4. McCabe 度量计算该 程序图的环路复杂性

   M-N+2

5. 0-1 背包、矩阵链乘、最长公共子序列、邻分（分数）背包分别适合什么算法进行解题？

   0-1 背包、最长公共子序列、矩阵链乘适合动态规划

   邻分（分数）背包适合贪心算法

6. 校验方法与校验位

   1、奇偶校验：掌握校验原则等相关概念，只检奇数位错，不能纠错。

   2、循环校验码CRC：可查错，不可纠错，运用模二除法计算校验码。

   3、海明校验：要求掌握相关概念，可查错，可纠错；要求掌握海明校验码校验位计算：2 ^ r>=r+m-1。

   校验位放在2 ^ r，信息位放在其余位置上。

   校验位计算方法：二进制计算位号，位号有的数字进行异或操作。

7. 内聚类型

   耦合类型

   非直接耦合:两个模块之间没有直接关系，它们之间的联系完全是通过主模块的控制和调用来实现的。
   数据耦合:一个模块访问另一个模块时，彼此之间是通过简单数据参数（不是控制参数、公共数据结构或外部变量)来交换输入、输出信息的。
   标记耦合︰一组模块通过参数表传递记录信息，就是标记耦合。这个记录是某一数据结构的子结构，而不是简单变量。其实传递的是这个数据结构的地址;
   控制耦合:如果一个模块通过传送开关、标志、名字等控制信息，明显地控制选择另一模块的功能，就是控制耦合。
   外部耦合:一组模块都访问同一全局简单变量而不是同一全局数据结构，而且不是通过参数表传递该全局变量的信息，则称之为外部耦合。公共耦合:若一组模块都访问同一个公共数据环境，则它们之间的耦合就称为公共耦合。公共的数据环境可以是全局数据结构、共享的通信区、内存的公共覆盖区等。
   内容耦合:如果发生下列情形，两个模块之间就发生了内容耦合
   (1)一个模块直接访问另一个模块的内部数据;
   (2)一个模块不通过正常入口转到另—模块内部;
   (3）两个模块有一部分程序代码重叠(只可能出现在汇编语言中);
   学员服务
   (4)一个模块有多个入口。

8. 词法分析、语法分析、语义分析等的区别（程序设计语言）

   在词法分析阶段，其任务是从左到右逐个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号)。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符组合在一起才表示某一含义。词法分析过程依据的是语言的词法规则，即描述"单词"分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定"是对单词的检查。
   语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如"表达式""语句“和程序"等。语法规则就是各类语法单位的构成规则。
   语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语言错误，并收集类型信息供后面的代码生成阶段使用。

9. 有限自动机

10. ISO/IEC 9126 软件质量模型

11. 维护类型

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

12. 阶段划分编译器

    词法分析:从左到右逐个扫描源程序中的字符，识别其中如关键字(或称保留字)、标识符、常数、运算符以及分隔符（标点符号和括号)等。
    语法分析:根据语法规则将单词符号分解成各类语法单位，并分析源程序是否存在语法上的错误。包括:语言结构出错、…end if不匹配，缺少分号、括号不匹配、表达式缺少操作数等。本题属于语法分析阶段的作用。
    语义分析:进行类型分析和检查，主要检测源程序是否存在静态语义错误。包括:运算符和运算类型不符合，如取余时用浮点数。

13. 海明校验码

    海明不等式:校验码个数为K，2的K次方个校验信息，1个校验信息用来指出F没有错误"”，满足m+K+1<=2 ^ k。所以32位的数据位，需要6位校验码。

14. 密码加密（对称、非对称），数字签名

15. 结构化分析方法，保持保持父图与子图之间的平衡

    保持父图与子图之间的平衡:父图中某个加工的输入输出数据流必须与其子图的输入输出数据流在数量上和名字上相同。父图的一个输入(或输出）数据流对应于子图中几个输入(或输出）数据流，而子图中组成的这些数据流的数据项全体正好是父图中的这一个数据流。

16. DNS协议，域名服务器访问机制

17. 十大排序算法和常用算法的时间复杂度

总结

做题技巧

1. 有关公式选择的，可以找一个特殊的例子进行代入，代入进去符合条件的就是正确的选项。

数据结构与算法

二叉树

二叉树遍历

先序遍历：根节点、左子树、右子树

中序遍历：左子树、根节点、右子树

后序遍历：左子树、右子树、根节点

常用算法

1、分治法特征:对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)则直接解决;否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
2、动态规划法:在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每—步都经过筛选，以每一步都是最优解来保证全局是最优解。本题情景没有列出所有的可能解进行筛选，因此，本题不属于动态规划法。
3、回溯法:回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回—步重新选择。这种走不通就退回再走的技术就是回溯法。本题情景没有探索和回退的过程，因此，本题不属于回溯法。
4、贪心法:总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

计算机网络

网络安全

1. 与网络安全有关的协议

   MIME它是一个互联网标准，扩展了电子邮件标准，使其能够支持，与安全无关。与安全电子邮件相关的是SIMIME安全多用途互联网邮件扩展协议。
   SSL和HTTPS涉及到邮件传输过程的安全，PGP(全称:Pretty Good Privacy，优良保密协议)），是一套用于信息加密、验证的应用程序，可用于加密电子邮件内容。

2. 本题考查的是HTTP的连接过程。
   ②在浏览器中输入URL，并按下回车键;
   ①浏览器向DNS服务器发出域名解析请求并获得结果;④根据目的IP地址和端口号，与服务器建立TCP连接;⑤浏览器向服务器发送数据请求;
   ③服务器将网页数据发送给浏览器;

   ⑦通信完成，断开TCP连接;
   ⑥浏览器解析收到的数据并显示;
   —般情况下，一旦Web服务器向浏览器发送了请求数据，它就要关闭TCP连接。

网络信息安全

加密解密

1. 公开密钥加密，又叫做非对称加密，常用的有RSA、背包算法、DSA数字签名、ECIES等

   私钥加密，对称加密，常用DES、AES、RC2等

防火墙

1. 包过滤防火墙:包过滤防火墙一般有一个包检查块（通常称为包过滤器)，数据包锅里可以根据数据包头中的各项信息来控制站点与站点、站点与网络、网络与网络之间的相互访问，但无法控制传输数据的内容，因为内容是应用层数据，而包过滤器处在网络层和数据链路层之间，不符合本题要求。
2. 应用级网关防火墙:应用代理网关防火墙彻底隔断内网与外网的直接通信，内网用户对外网的访问变成防火墙对外网的访问，然后再由防火墙转发给内网用户。所有的通信都必须经应用层代理软件转发，它可对应用层的通信数据流进行监控和过滤。
3. 数据库防火墙:数据库防火墙技术是针对关系型数据库保护需求应运而生的一种数据库安全主动防御技术，数据库防火墙部署于应用服务器和数据库之间，不符合本题要求。
4. WEB防火墙: web防火墙是入侵检测系统，入侵防御系统的一种。从广义上来说，Web应用防火墙就是应用级的网站安全综合解决方案，与我们所讲到的防火墙概念有一定区别，不符合本题要求。

软件工程

1. 内聚类型

   过程内聚。如果一个模块内部的处理成分是相关的，而且这些处理必须以特定的次序执行，则称为过程内聚。
   时间内聚。如果一个模块完成的功能必须在同一时间内执行(如系统初始化)，但这些功能只是因为时间因素关联在一起，则称为时间内聚。
   顺序内聚。如果一个模块的各个成分和同一个功能密切相关，而且一个成分的输出作为另一个成分的输入，则称为顺序内聚。本题描述的是C选项。
   逻辑内聚。几个逻辑上相关的功能被放在同一模块中，则称为逻辑内聚。如一个模块读取各种不同类型外设的输入。尽管逻辑内聚比偶然内聚合理一些，但逻辑内聚的模块各成分在功能上并无关系，即使局部功能的修改有时也会影响全局，因此这类模块的修改也比较困难。

2. ISO/IEC 9126软件质量模型，该模型的质量特性和质量子特性如下（不全）:

   功能性(适合性、准确性、互用性、依从性、安全性);
   可靠性（成熟性、容错性、易恢复性);
   易使用性(易理解性、易学性、易操作性);效率(时间特性、资源特性);
   可维护性(易分析性、易改变性、稳定性、易测试性);可移植性(适应性、易安装性、—致性、易替换性)。

3. 耦合类型（不全）

   数据耦合:一个模块访问另一个模块时，彼此之间是通过简单数据参数(不是控制参数、公共数据结构或外部变量)来交换输入、输出信息的。
   公共耦合:若一组模块都访问同一个公共数据环境，则它们之间的耦台就称为公共耦合。公共的数据环境可以是全局数据结构、共享的通信区、内存的公共覆盖区等。
   外部耦合:一组模块都访问同一全局简单变量而不是同一全局数据结构，而且不是通过参数表传递该全局变量的信息，则称之为外部耦合。

   标记耦合∶一组模块通过参数表传递记录信息，就是标记耦合。这个记录是某一数据结构的子结构，而不是简单变量。本题描述的是标记耦合。

4. **人机交互“黄金三原则"**包括:用户操纵控制、减少用户的记忆负担、保持界面的一致性。
   用户操纵控制:以不强迫用户进入不必要或不希望的动作的方式来定义交互模式;提供灵活的交互;允许中断和撒销用户交互;当技能级别增长时可以使交互流线化并允许定制交互;使用户与内部技术细节隔离开来;设计应运行用户与出现在屏幕上的对象直接交互。
   减轻用户的记忆负担:减少对短期记忆的要求;建立有意义的默认;定义直观的快捷方式;界面的视觉布局应该基于真实世界的象征;以不断进展的方式揭示信息。
   保持界面一致:允许用户将当前任务放入有意义的环境中;在应用系统家族中保持一致;如果过去的交互模型已经建立起了用户期望，除非有不得已的理由，否则不要改变它。

操作系统

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

数据库

1. 事务的ACID特性:
   1、原子性(Atomicity) :事务是原子的，要么做，要么都不做。
   2、一致性(Consistency):事务执行的结果必须保证数据库从一个—致性状态变到另一个—致性状态。
   3、隔离性(solation):事务相互隔离。当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程，对其他事物都是不可见的。
   4、持久性(Durability):一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也永久有效。

2. 分布式数据库

   分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中的每个节点具有独立处理的能力（称为场地自治)，它可以执行局部应用，同时，每个节点也能通过网络通信子系统执行全局应用。分布式数据库系统是在集中式数据库系统技术的基础上发展起来的，具有如下特点:
   (1）数据独立性。在分布式数据库系统中，数据独立性这一特性更加重要，并具有更多的内容。除了数据的逻辑独立性与物理独立性外，还有数据分布独立性(分布透明性)。
   (2)）集中与自治共享结合的控制结构。各局部的DBMS可以独立地管理局部数据库，具有自治的功能。同时，系统又设有集中控制机制，协调各局部DBMS的工作，执行全局应用。
   (3）适当增加数据冗余度。在不同的场地存储同一数据的多个副本，这样，可以提高系统的可靠性和可用性，同时也能提高系统性能。提高系统的可用性，即当系统中某个节点发生故障时，因为数据有其他副本在非故障场地上，对其他所有场地来说，数据仍然是可用的，从而保证数据的完备性。
   (4）全局的—致性、可串行性和可恢复性。

错题汇总

2019下半年总结

1. 在 cpu 内外常需设置多级高速缓存 cache，主要目的是（ ）。
   A、扩大主存的存储容量
   B、提高 cpu 访问主存数据或指令的效率
   C、扩大存储系统的存量
   D、提高 cpu 访问内外存储器的速度

   在CPU内外的高速缓存是用来解决CPU与内存之间速度、容量不匹配的问题，与外存无关，可以提高CPU访问主存数据

   B选项正确，D选项错误。
   Cache不属于主存，与主存容量无关，所以A选项错误。
   Cache容量相对于其他存储层次，量级较小，不能扩大存储系统的存量，所以C选项错误。

2. 某系统的可靠性结构框图如下图所示，假设部件 1、2、3 的可靠度分别为 0.90； 0.80；0.80（部件 2、3 为冗余系统）若要求该系统的可靠度不小于 0.85，则 进行系统设计时，部件 4 的可靠度至少应为（ ）。

3. 内存按字节编址，地址从 A0000H 到 CFFFFH 的内存，共存（ ）字节，若用存 储容量为 64k*8bit 的存储器芯片构成该内存空间，至少需要（ ）片。
   A、80k
   B、96 k
   C、160 k
   D、192 k
   A、2
   B、3
   C、5
   D、8

   地址从A000OH到CFFFFH，存储单元个数共有CFFFFH+1-A000OH=30000H，即3×164个;按字节编址，即每个存储单元存放1个字节,就是1B;该存储区域总容量=存储单元个数x存储单元内容=3x164x1B=3×216B=192KB.
   若用存储容量为64K×8bit的存储芯片构成，即单位芯片容量为64K×8bit，总容量=单位芯片容量x片数，即片数=总容量/单位芯片容量=(192KB)/(64K×8bit)=3

4. 执行指令时，将每一节指令都分解为取指、分析和执行三步，已知取指时间 t取指=5△t，分析时间 t 分析= 2△t.执行时间 t 执行= 3△t 如果按照 ，重叠的流水线方式执行指令，从头到尾执行完 500 条 指令需（ ）△t.
   A、2500
   B、2505
   C、2510
   D、2515

   流水线执行时间=流水线建立时间+(n-1) x流水线周期=5+2+3+(500-1)×5=2505。

   流水线周期值得是什么？取指时间？

5. 某电子商务网站向 CA 申请了数字证书，用户可以通过使用（ ）验证（ ） 的真伪来确定该网站的合法性。
   A、CA 的公钥
   B、CA 的签名
   C、网站的公钥
   D、网站的私钥
   A、CA 的公钥
   B、CA 的签名
   C、网站的公钥
   D、网站的私钥

   数字证书是由权威机构——CA证书授权(Certificate Authority）)中心发行的，能提供在Internet上进行身份验证的一种权威性电子文档，人们可以在因特网交往中用它来证明自己的身份和识别对方的身份。
   数字证书包含版本、序列号、签名算法标识符、签发人姓名、有效期、主体名和主体公钥信息等并附有CA的签名，用户获取网站的数字证书后通过CA的公钥验证CA的签名，从而确认数字证书的有效性，然后验证网站的真伪。

6. 某考试系统的部分功能描述如下，审核考生报名表，通过审核的考生登录系统， 系统自动为其生成一套试题，考试中心提供标准答案，问卷老师问卷，提交考 生成绩，考生查看自己的成绩。若用数据流图对该系统进行建模，则（ ）不 是外部实体。.
   A、考生
   B、考试中心
   C、问卷老师
   D、试题

   外部实体—般为组织机构、人员、第三方系统，D选项不是外部实体。

7. 将编译器的工作过程划分为词法分析，语义分析，中间代码生成，代码优化和 目标代码生成时，语法分析阶段的输入是（ ）若程序中的括号不配对，则会 在（ ）阶段检查出错误
   A、记号流
   B、字符流
   C、源程序
   D、分析树
   A、词法分析
   B、语法分析
   C、语义分析
   D、目标代码生成

   A选项记号流，词法分析的输出是记号流，也就是语法分析的输入，第一空选择A选项。
   B选项字符流，在Java中，根据处理的数据单位不同，分为字节流和字符流。字符流是由字符组成的，例如File Reader、File Wwrier,Buffered Reader、Buffered Writer、Input Stream Reader、Output Stream writer等。与本题无关。
   C选项源程序，词法分析的任务是把源程序的字符串转换成单词符号序列。
   D选项分析树，如果没有语法错误，语法分析后就能正确的构造出其语法树。括号不匹配是典型的语法错误，会在语法分析阶段检测出来。

8. 在磁盘调度管理中通常（ ）
   A、先进行旋转调度，再进行移臂调度
   B、在访问不同柱面的信息时，只需要进行旋转调度
   C、先进行移臂调度，再进行旋转调度
   D、在访问不同磁盘的信息时，只需要进行移臂调度

   磁盘调度管理中，先进行移臂调度寻找磁道，再进行旋转调度寻找扇区。

9. 假设磁盘臂位于 15 号柱面上，进程的请求序列如下表表示，如果采用最短移臂 调度算法，那么系统的响应序列应为（ ）

   A、①②③④⑤⑥
   B、⑤①②④③⑥
   C、②③④⑤①⑥
   D、④②③⑤①⑥

   最短移臂调度算法，即优先响应距离较近磁道的申请。
   1、当前磁头位于15号柱面（柱面号即磁道编号)，请求序列分别位于12号柱面(①⑤)、19号柱面(②④)、23号柱面（③)、28号柱面(⑥) ;
   2、距离15号柱面最近的应该是12号柱面(①⑤)，优先响应（①⑤)，次序不限;3、此时磁头位于12号柱面，距离最近的应该是19号柱面(②④)，次序不限;4、此时磁头位于19号柱面，距离最近的应该是23号柱面® ;
   5、此时磁头位于23号柱面，距离最近的应该是28号柱面(⑥)。满足要求的只有B选项

10. 敏捷开发方法 scrum 的步骤不包括（ ）
    A、Product Backlog
    B、Refactoring
    C、Sprint Backlog
    D、Sprint

    A选项Product Backlog 产品待办事项清单;B选项Refactoring重构，不属于scrum的步骤;C选项Sprint Backlog，Sprint待办事项清单;D选项Sprint，冲刺迭代。

11. ISO/IEC 软件质量模型中，易使用性是指与使用所需的努力由一组规定或隐含 的用户对这样使用所作的个别评价有关的一组属性，其易使用性的子特性不包 括（ ）。
    A、易理解性
    B、易学性
    C、易分析性
    D、易操作性

    易用性的自特性包括易理解性、易学性、易操作性，其中C选项易分析性属于可维护性的子特性。

12. 以下关于 UML 状态图的叙述中，不正确的是（ ）
    A、活动可以在状态内执行，也可以在迁移时执行
    B、若事件触发一个没有特定监护条件的迁移，则对象离开当前状态
    C、迁移可以包含事件触发器，监护条件和状态
    D、事件触发迁移

    事件触发之后可以在本状态内处理，不一定会离开当前状态。所以B错误。

13. 给定关系 R（U，Fr）其中属性属 U={A，B，C，D}，函数依赖集 Fr={A→BC， B→D}关系 S（U，Fs），其中属性集 U={ACE}，函数依赖集 Fs={A→C，C→E}R 和 S 的主键分别为（ ），关于 Fr 和 Fs 的叙述，正确的是（ ）
    A、A 和 A
    B、AB 和 A
    C、A 和 AC
    D、AB 和 AC
    A、Fr 蕴含 A→B，A→C，但 Fr 不存在传递依赖
    B、Fs 蕴含 A→E，Fs 存在传递依赖，但 Fr 不存在传递依赖
    C、Fr，Fs 分别蕴含 A→D，A→E，故 Fr，Fs 都存在传递依赖
    D、Fr 蕴含 A→D，Fr 存在传递依赖，但是 Fs 不存在传递依赖

    根据题千给出的信息，对于关系R，满足A能够遍历全图，对于关系S，满足A能够遍历全图，所以R和S的主键都是A.
    并且，对于关系R，A-BC，即满足A-B且A-C，又有B-D，所以可以推导即蕴含A一D，存在传递函数依赖，对于关系S，存在A→C，C一E，所以可以推导即蕴含了A→E，存在传递函数依赖。描述正确的是C选项。

14. 给定关系 R（A，B，CD）和 S（B，C，E，F）与关系代数表达式，等价的 SQL 语句如下
    SELECT（ ） FROM R，S （ ）；
    A、 R.A，R.B，S.F
    B、 R.A，S.B，S.E
    C、R.A，S.E，S.F
    D、R.A，S.B，S.F
    A、WHERE R.B=S.B
    B、HAVING R.B=S.B
    C、WHERE R.B=S.E
    D、HAVING R.B=S.E

    本题考查的是关系代数与SQL语句的结合考查，根据查询语句的格式:SELECT [ALLIDISTINCT]<目标表达式>[，<目标表达式>]…]
    FROM<表名>[，<表名>]…
    [WHERE<条件表达式>习]
    SELECT后跟随的是结果属性列，即对R×S结果第1、5、7列的投影，对应属性R.A、S.B、S.E，第一空选择B选项;
    FROM R,S后跟随的是结果元组行的WHERE筛选条件，即对R×S结果选择第2列=第5列的元组，对应属性为R.B=S.B，第二空选择A选项.

15. 对于如下所示的有向图，其邻接矩阵是一个（ ）的矩阵，采用邻接链表存储 时顶点的表结点个数为 2，顶点 5 的表结点个数为 0，顶点 2 和 3 的表结点个数 分別为（ ）

    A、5 * 5
    B、5 * 7
    C、7 * 5
    D、7 * 7
    A、2.1
    B、2.2
    C、3.4
    D、4.3

    根据邻接矩阵的定义，行列数都为结点个数，结点数为5，因此邻居矩阵行列数均为5，即5×5的矩阵。
    根据邻接表的定义，一个顶点的表结点个数为其邻接顶点的个数，顶点2有2个邻接顶点，顶点3有2个邻接顶点。

16. 对 N 个数排序，最坏情况下时间复杂度最低的算法是（ ）排序算法

    A、插入
    B、冒泡
    C、归并
    D、快速

    其他选项在最坏情况下的时间复杂度都是o(n2)，只有C选项归并排序，在最坏情况下，时间复杂度仍然是O(nlog2n)。

17. 采用贪心算法保证能求得最优解的问题是（ ）
    A、0-1 背包
    B、矩阵链乘
    C、最长公共子序列
    D、邻分（分数）背包

    贪心法在—般情况下—定能够得到满意解，不—定能够得到最优解。
    贪心法能够获得最优解的前提是:(1）问题具有最优子结构，即规模为n的问题的最优解与规模为n-1的问题的解相关;(2)问题具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择得到。
    邻分背包即部分背包问题具有以上性质，故可以通过贪心算法得到最优解。

18. 已知某文档包含 5 个字符。每个字符出现的频率如下表所示。采用霍夫曼编码 对该文档压缩存储，则单词“cade”的编码为（ ），文档的压缩比为（ ）

2019上半年总结

1. .DMA 控制方式是在（ ）之间直接建立数据通路进行数据的交换处理。

   A.CPU 与主存

   B.CPU 与外设

   C.主存与外设

   D.外设与外设

   直接主存存取(Direct Memory Access,DMA）是指数据在主存与IO设备间(即主存与外设之间）直接成块传送。

2. 在（ ）校验方法中,采用模 2 运算来构造校验位。

   A.水平奇偶 B.垂直奇偶 C.海明码 D.循环冗余

   采用模二除法运算的只有循环冗余检验CRC。

3. 震网（Stuxnet）病毒是一种破坏工业基础设施的恶意代码，利用系统漏洞攻击工业控制系 统，是一种危害性极大的（ ）。

   A.引导区病毒 B.宏病毒 C.木马病毒 D.蠕虫病毒

   震网(Stuxnet)，指一种蠕虫病毒。它的复杂程度远超一般电脑黑客的能力。这种震网(Stuxnet)病毒于2010年6月首次被检测出来，是第一个专门定向攻击真实世界中基础(能源）设施的"蠕虫"病毒，比如核电站，水坝，国家电网。
   A选项引导区病毒破坏的是引导盘、文件目录等，B选项宏病毒破坏的是OFFICE文件相关，C选项木马的作用一般强调控制操作。

4. 结构化设计方法中使用结构图来描述构成软件系统的模块以及这些模块之间的调用关系。结构图的基本成分不包括（ ）。

   A.模块 B.调用 C.数据 D.控制

   系统结构图（SC)）又称为模块结构图，它是软件概要设计阶段的工具，反映系统的功能实现和模块之间的联系与通信，包括各模块之间的层次结构，即反映了系统的总体结构。
   SC包括模块、模块之间的调用关系、模块之间的通信和辅助控制符号等4个部分。

5. PV 操作是操作系统提供的具有特定功能的原语。利用 PV 操作可以（ ）

   A.保证系统不发生死锁 B.实现资源的互斥使用 C.提高资源利用率 D.推迟进程使用共享资源的时间

   PV操作利用信号量机制，是一种有效的进程同步与互斥工具，可以实现资源的互斥使用，所以B选项正确。
   PV操作使用不当容易引起死锁，所以PV不能保证"系统不发生死锁"，A选项错误;
   PV操作对应进程每次只能发送一个消息，执行效率低，不能提高资源的利用率，C选项错误;
   PV操作针对的是互斥资源而不是共享盗源，D选项错误。

6. 从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器 平台上， 能针对硬件变化进行结构与功能上的配置。该要求体现了嵌入式操作系统的（ ）。

   A.可定制性 B.实时性 C.可靠性 D.易移植性

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

   (5）易移植性，为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。

7. 招聘系统要求求职的人年龄在 20 岁到 60 岁之间（含），学历为本科、硕士或者博士，专 业为计算机科学与技术、通信工程或者电子工程。其中（ ）不是好的测试用例。

   A.（20,本科，电子工程） B.（18,本科，通信工程） C.（18，大专，电子工程） D.（25，硕士，生物学）

   在设计测试用例时，一个好的无效等价类，应该只从一个角度违反规则。C选项有2个维度错误，不能直接定位到错误的位置。

8. 给定关系 R(A,B,C,D,E)和关系 S(A,C,E,F,G),对其进行自然连接运算 R S 后其结果集的属性
   列为（ ）。

   A.R.A,R.C,R.E,S.A,S.C,S.E

   B.R.A,R.B，R.C,R.D,R.E,S.F，S.G

   C.R.A,R.B,R.C，R.D，R.E，S.A，S.C，S.E

   D.R.A，R.B,R.C，R.D，R.E，S.A，S.C，S.E，S.F，S.G

   自然连接的结果以左侧R为主，右侧关系S去除重复列。因此最终结果为R的5个属性列，以及s的非重复列。答案为B选项。

9. 若事务 T1 对数据 D1 加了共享锁，事务 T2T3 分别对数据 D2 和数据 D3 加了排它锁， 则 事务（ ）。

   A.T1 对数据 D2D3 加排它锁都成功，T2T3 对数据 D1 加共享锁成功

   B.T1 对数据 D2D3 加排它锁都失败，T2T3 对数据 D1 加排它锁成功

   C.T1 对数据 D2D3 加共享锁都成功，T2T3 对数据 D1 加共享锁成功

   D.T1 对数据 D2D3 加共享锁都失败，T2T3 对数据 D1 加共享锁成功
   共享锁(S锁)∶又称读锁，若事务T对数据对象A加上S锁，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。排他锁(X锁)∶又称写锁。若事务T对数据对象A加上X锁，其他事务不能再对A加任何锁，直到T释放A上的锁。

10. 在 Windows 命令行窗口中使用（ ）命令可以查看本机 DHCP 服务是否己启用

    A.ipconfig B.ipconfig/all C.ipconfig/renew D.ipconfig/release

    ipconfig 显示简要信息，不能查看DHCP服务开启情况。

    ipconfig /all显示详细信息，可查看DHCP服务是否已启用。

    ipconfig /renew更新所有适配器。
    ipconfig /release释放所有匹配的连接。

2018下半年总结

1. CPU 在执行指令的过程中，会自动修改（ ）的内容，以使其保存的总是将要执行的下一条指 令的地址。

   A．指令寄存器 B.程序计数器 C.地址寄存器 D.指令译码器

   CPU执行指令的过程中，会自动修改PC的内容，PC是指令计数器，用来存放将要执行的下一条指令，本题选择B选项。
   对于指令寄存器（IR)存放即将执行的指令，指令译码器（ID）对指令中的操作码字段进行分析和解释，地址寄存器(AR)，不是我们常用的CPU内部部件，其作用是用来保存当前CPU所要访问的内存单元或I/O设备的地址。

2. 在微机系统中，BIOS（基本输入输出系统）保存在（ ）中。

   A．主板上的 ROM B.CPU 的寄存器 C.主板上的 RAM D.虚拟存储器

   BIOS(Basic lInput Output System)(基本输入输出系统)是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序，它可从CMOS中读写系统设置的具体信息。

   RAM和ROM的区别，或者说ROM和RAM的区别是什么呢？ROM和RAM都是一种存储技术，只是两者原理不同，RAM为随机存储，掉电不会保存数据，而ROM可以在掉电的情况下，依然保存原有的数据。ROM和RAM指的都是半导体存储器。本来的含义是：ROM是Read Only Memory的意思，也就是说这种存储器只能读，不能写。而RAM是Random Access Memory的缩写。这个词的由来是因为早期的计算机曾经使用磁鼓作为内存，而磁鼓和磁带都是典型的顺序读写设备。RAM则可以随机读写。

3. 以下关于采用一位奇校验方法的叙述中，正确的是（ ）。

   A.若所有奇数位出错，则可以检测出该错误但无法纠正错误

   B.若所有偶数位出错，则可以检测出该错误并加以纠正

   C.若有奇数个数据位出错，则可以检测出该错误但无法纠正错误

   D.若有偶数个数据位出错，则可以检测出该错误并加以纠正

   对于奇偶校验，是由若干位有效信息，再加上一个二进制位（校验位）组成校验码，其中奇校验"1的个数为奇数，而偶校验"1的个数为偶数，以此校验，如果其中传输过程中有偶数个数发生错误(即1变成0或0变成1)，则1的个数其奇偶就不会发生改变，也就无法发现错误了，只有奇数个数据位发生错误，才能发现错误。同时，奇偶校验只能查错不能纠错。因此本题选择C选项。

4. 计算机病毒的特征不包括（ ）。

   A．传染性 B.触发性 C.隐蔽性 D.自毁性

   《软件设计师教程（第5版)》P566页:计算机病毒具有隐蔽性、传染性、潜伏性、触发性和破坏性等特定。

5. 使用 Web 方式收发电子邮件时，以下描述错误的是（ ）。

   A．无须设置简单邮件传输协议 B.可以不设置帐号密码登录 C.邮件可以插入多个附件 D.未发送邮件可以保存到草稿箱

   使用WEB方式收发电子邮件时必须设置账号密码登录。

6. 有可能无限期拥有的知识产权是（ ）。

   A．著作权 B.专利权 C.商标权 D.集成电路布图设计权

   其中商标权可以通过续注延长拥有期限，而著作权、专利权和设计权的保护期限都是有限期的。

   著作权非署名权，署名权也是无限期的。就像唐诗宋词一样

7. 某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动， 边上的数字表示活动的持续时间（天），则完成该项目的最少时间为（ ）天。活动 FG 的松 驰时间为（ ）天。

   A．20 B.37 C.38 D.46

   A．9 B.10 C.18 D.26

   项目工期是AOE中最长的路径，称之为关键路径(项目最短工期)。本题最长路径为:A一D一F一H→J，长度为46天，没有比它更长的路径。
   FG活动不在关键路径上，并且FG活动所在的路径，其中最长的为ADFGJ，长度为28天，因此该活动的松弛时间为46-28=18天。

8. 某操作系统文件管理采用索引节点法。每个文件的索引节点有 8 个地址项，每个地址项大小为 4 字节，其中 5 个地址项为直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级 间接地址索引，磁盘索引块和磁盘数据块大小均为 1KB。若要访问文件的逻辑块号分别为 1 和 518，则系统应分别采用（ ）。

   A．直接地址索引和一级间接地址索引 B.直接地址索引和二级间接地址索引 C.一级间接地址索引和一级间接地址索引 D.一级间接地址索引和二级间接地址索引

   每个物理块大小为1KB，每个地址项大小为4B，因此每个物理块可以对应地址项个数为:1KB/4B=256.直接索引即索引直接指向物理块，可以表示逻辑块号范围:0~4号
   一级索引即索引节点指向的物理块用来存放地址项，可以表示256个地址项，即256个物理块，可以表示逻辑地址块号范围:5260,261516号
   二级索引即索引节点指向的物理块，存放的是一级索引的地址块地址，一共有256个地址块用来存放一级索引，每个块可以存放256个地址项，共有2562=65536个地址项，因此可以表示的逻辑块号范围:517~66052号

9. 某商场的销售系统所使用的信用卡公司信息系统的数据格式发生了更改，因此对该销售系统进 行的修改属于（ ）维护。

   A．改正性 B.适应性 C.改善性 D.预防性

   在系统运行过程中，软件需要维护的原因是多样的，根据维护的原因不同，可以将软件维护分为以下四种:
   (1）改正性维护。为了识别和纠正软件错误、改正软件性能上的缺陷、排除实施中的误使用，应当进行的诊断和改正错误的过程就称为改正性维护。
   (2）适应性维护。在使用过程中，外部环境（新的硬、软件配置)、数据环境(数据库、数据格式、数据输入/输出方式、数据存储介质)可能发生变化。为使软件适应这种变化，而去修改软件的过程就称为适应性维护。
   (3〕完善性维护。在软件的使用过程中，用户往往会对软件提出新的功能与性能要求。为了满足这些要求，需要修改或再开发软件，以扩充软件功能、增强软件性能、改进加工效率、提高软件的可维护性。这种情况下进行的维护活动称为完善性维护。
   (4）预防性维护。这是指预先提高软件的可维护性、可靠性等，为以后进一步改进软件打下良好基础。

10. 在某销售系统中，客户采用扫描二维码进行支付。若采用面向对象方法开发该销售系统，则客 户类属于（ ）类， 二维码类属于（ ）类。

    A．接口 B.实体 C.控制 D.状态

    A．接口 B.实体 C.控制 D.状态

    类可以分为三种:实体类、接口类(边界类）和控制类。实体类的对象表示现实世界中真实的实体，如人、物等。**接口类(边界类)的对象为用户提供一种与系统合作交互的方式，分为人和系统两大类，其中人的接口可以是显示屏、窗口、Web窗体、对话框、菜单、列表框、其他显示控制、条形码、二维码或者用户与系统交互的其他方法。系统接口涉及到把数据发送到其他系统，或者从其他系统接收数据。**控制类的对象用来控制活动流，充当协调者。

11. 在分布式数据库中，（ ）是指用户或应用程序不需要知道逻辑上访问的表具体如何分块存 储。

    A．逻辑透明 B.位置透明 C.分片透明 D.复制透明

    分片透明:是指用户不必关系数据是如何分片的，它们对数据的操作在全局关系上进行，即关系如何分片对用户是透明的，因此，当分片改变时应用程序可以不变。分片透明性是最高层次的透明性，如果用户能在全局关系一级操作，则数据如何分布，如何存储等细节自不必关系，其应用程序的编写与集中式数据库相同。
    复制透明:用户不用关心数据库在网络中各个节点的复制情况，被复制的数据的更新都由系统自动完成。在分布式数据库系统中，可以把-个场地的数据复制到其他场地存放，应用程序可以使用复制到本地的数据在本地完成分布式操作，避免通过网络传输数据，提高了系统的运行和查询效率。但是对于复制数据的更新操作，就要涉及到对所有复制数据的更新。
    位置透明:是指用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的
    **局部映像透明性（逻辑透明)）**是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关系局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统是非常重要的。
    本题提到不需要了解具体如何分块存储，如果描述为不需要了解物理存储或存储位置，则为位置透明，而涉及到如果分块存储，应该为分片透明。对于分布式数据库，分片是一种大局性的划分，而物理上的存储位置则更为底层，所以对于如何分块存储，强调更多的是分片而不是物理位置。

12. 使用 ADSL 接入 Internet，用户端需要安装（ ）协议。

    A．PPP B.SLIP C.PPTP D.PPPoE

    ADSL Modem上网拨号方式有3种，即专线方式(静态IP)、PPPoA和PPPoE。
    PPPoE(英语:Point-to-Point Protocol OverEthernet)，以太网上的点对点协议，是将点对点协议(PPP）封装在以太网(Ethernet)框架中的一种网络隧道协议。
    PPTP (Point-to-Point Tunneling Protocol)，即点对点隧道协议。该协议是在PPP协议的基础上开发的一种新的增强型安全协议，支持多协议虚拟专用网(VPN)，可以通过密码验证协议(PAP)、可扩展认证协议(EAP)等方法增强安全性。可以使远程用户通过拨入ISP、通过直接连接Internet或其他网络安全地访问企业网。
    SLIP(Serial Line Internet Protocol，串行线路网际协议)，该协议是Windows远程访问的一种旧工业标准，主要在Unix远程访问服务器中使用，现今仍然用于连接某些ISP。
    PPP(点到点协议）是为在同等单元之间传输数据包这样的简单链路设计的链路层协议。这种链路提供全双工操作，并按照顺序传递数据包。设计目的主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机、网桥和路由器之间简单连接的一种共通的解决方案。

13. 下列命令中，不能用于诊断 DNS 故障的是（ ）。

    A．netstat B.nslookup C.ping D.tracert

    netstat是控制台命令，是一个监控TCPIP网络的非常有用的工具，它可以显示路由表、实际的网络连接以及每一个网络接口设备的状态信息。netstat用于显示与IP、TCP、UDP和ICMP协议相关的统计数据，一般用于检验本机各端口的网络连接情况。
    nslookup是一个监测网络中DNS服务器是否能正确实现域名解析的命令行工具。
    PING命令常用于测试连通性，在此过程中可看出是直接ping的目标地址。
    nslookup、 ping、tfracert都可以加上一个主机域名作为其命令参数来诊断DNS故障，nslookup还可以看到本地DNS服务器地址。Arp命令是与arp记录有关，与DNS无关联。

2018上半年总结

1. 浮点数的表示分为阶和尾数两部分。两个浮点数相加时，需要先对阶，即（ ）(n 为阶差的绝对值)。 】

   A．将大阶向小阶对齐，同时将尾数左移 n 位

   B.将大阶向小阶对齐，同时将尾数右移 n 位

   C.将小阶向大阶对齐，同时将尾数左移 n 位

   D.将小阶向大阶对齐，同时将尾数右移 n 位

   对阶时，小数向大数看齐;对阶是通过较小数的尾数右移实现的。

2. 在安全通信中，S 将所发送的信息使用（ ）进行数字签名，T 收到该消息后可利用 （ ）验证该消息的真实性。

   A．S 的公钥 B. S 的私钥 C. T 的公钥 D. T 的私钥

   A．S 的公钥 B. S 的私钥 C. T 的公钥 D. T 的私钥

   **数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。**如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名能够验证信息的完整性。
   数字签名是个加密的过程，数字签名验证是个解密的过程。保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。

3. 在网络安全管理中,加强内防内控可采取的策略有( )。 ①控制终端接入数量 ②终端访问授权，防止合法终端越权访问 ③加强终端的安全检查与策略管理 ④加强员工上网行为管理与违规审计

   A．②③ B.②④ C.①②③④ D.②③④

   加强内防内控主要通过访问授权、安全策略、安全检查与行为审计等多种安全手段的综合应用来实现。终端接入的数量影响的是网络的规模、数据交换的性能，不是内防内控关注的重点。

4. 数据字典是结构化分析的一个重要输出。数据字典的条目不包括( )。

   A．外部实体 B.数据流 C.数据项 D.基本加工

   数据字典是指对数据的数据项、数据结构、数据流、数据存储、处理逻辑、外部实体等进行定义和描述，其目的是对数据流程图中的各个元素做出详细的说明，使用数据字典为简单的建模项目。其条目有数据流、数据项、数据存储、基本加工等。

5. ( )是一种函数式编程语言。

   A． Lisp B. Prolog C. Python D. Java/C++

   LISP是一种通用高级计算机程序语言，长期以来垄断人工智能领域的应用。LISP作为因应人工智能而设计的语言，是第一个声明式系内函数式程序设计语言，有别于命令式系内过程式的C、Fortran和面向对象的Java、C#等结构化程序设计语言。

6. 将高级语言源程序翻译为可在计算机上执行的形式有多种不同的方式，其中( )。

   A．编译方式和解释方式都生成逻辑上与源程序等价的目标程序

   B.编译方式和解释方式都不生成逻辑上与源程序等价的目标程序

   C.编译方式生成逻辑上与源程序等价的目标程序,解释方式不生成

   D.解释方式生成逻辑上与源程序等价的目标程序,编译方式不生成

   编译语言是一种以编译器来实现的编程语言。它不像直译语言一样，由解释器将代码一句一句运行，而是以编译器，先将代码编译为机器码，再加以运行。将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序，称之为编译程序。

7. 若系统在将( )文件修改的结果写回磁盘时发生崩溃,则对系统的影响相对较大。

A．目录 B.空闲块 C.用户程序 D.用户数据

系统目录就是指操作系统的主要文件存放的目录，目录中的文件直接影响到系统是否正常工作。

8. I/O 设备管理软件一般分为 4 个层次,如下图所示。图中①②③分别对应( )。

   A．设备驱动程序、虚设备管理、与设备无关的系统软件

   B.设备驱动程序、与设备无关的系统软件、虚设备管理

   C.与设备无关的系统软件、中断处理程序、设备驱动程序

   D.与设备无关的系统软件、设备驱动程序、中断处理程序

   具体层次从上往下分别为用户级IO层、设备无关I/O层、设备驱动程序、中断处理程序、硬件。

   硬件:完成具体的I/O操作。
   中断处理程序:l/O完成后唤醒

   设备驱动程序设备驱动程序:设置寄存器，检查设备状态
   设备无关I/O层:设备名解析、阻塞进程、分配缓冲区

   用户级I/O层:发出I/O调用。

9. 软件维护工具不包括( )工具。

   A．版本控制 B.配置管理 C.文档分析 D.逆向工程

   辅助软件维护过程中的活动的软件称为"软件维护工具"，它辅助维护人员对软件代码及其文档进行各种维护活动。软件维护工具主要有:1.版本控制工具;2、文档分析工具;3、开发信息库工具;、4、逆向工程工具;5、再工程工具;6、配置管理支持工具。

10. 耦合是模块之间的相对独立性(互相连接的紧密程度)的度量。耦合程度不取决( )。

    A．调用模块的方式 B.各个模块之间接口的复杂程度 C.通过接口的信息类型 D.模块提供的功能数

    耦合性也叫块间联系。指软件系统结构中各模块间相互联系紧密程度的一种度量。模块之间联系越紧密，其耦合性就越强，模块之间越独立则越差，模块间耦合的高低取决于模块间接口的复杂性，调用的方式以及传递的信息。

11. 对下图所示的程序流程图进行判定覆盖测试,则至少需要（ ）个测试用例。采用 McCabe 度量法计算其环路复杂度为（ ）。

    A．2 B.3 C.4 D.5

    A．2 B.3 C.4 D.5

    判定覆盖是设计足够多的测试用例，使得程序中的每一个判断至少获得一次"真"和一次"假"”，即使得程序流程图中的每一个真假分支至少被执行一次。根据题意，只需2个测试用例即可;根据环路复杂度的计算公式V (G)=m-n+2=11-10+2=3。

12. 语法制导翻译是一种( )方法。

A．动态语义分析 B.中间代码优化 ==C.静态语义分析== D.目标代码优化

翻译的任务:首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。其基本思想是，根据翻译的需要设置文法符号的属性，以描述语法结构的语义。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。

13. 给定关系模式 R,其中 U 为属性集,F 是 U 上的一组函数依赖,那么 Armstrong 公理系 统的伪传递律是指( )。

    A.若 X→Y,X→Z,则 X→YZ 为 F 所蕴涵

    B.若 X→Y,WY→Z,则 XW→Z 为 F 所蕴涵

    C.若 X→Y,Y→Z 为 F 所蕴涵,则 X→Z 为 F 所蕴涵

    D.若Ⅹ→Y 为 F 所蕴涵,且 Z⊆U,则 XZ→YZ 为 F 所蕴涵

    从已知的一些函数依赖，可以推导出另外一些函数依赖，这就需要一系列推理规则。函数依赖的推理规则最早出现在1974年WWAmstrong的论文里，这些规则常被称作"Armstrong公理”
    设U是关系模式R的属性集，F是R上成立的只涉及U中属性的函数依赖集。函数依赖的推理规则有以下三条;自反律:若属性集Y包含于属性集X，属性集X包含于U，则X→Y在R上成立。(此处X一Y是平凡函数依赖)增广律:若X一Y在R上成立，且属性集Z包含于属性集U，则XZ→YZ在R上成立。
    传递律:若X一Y和Y一Z在R上成立，则X一Z在R上成立。
    根据上面三条推理规则，又可推出下面三条推理规则:
    ④合并规则:若X→Y，X→Z，则X→YZ为F所蕴含;⑤伪传递规则:若X→Y, WY一Z，则XW→Z为F所蕴含;分解规则:若X→Y，Z Y，则X一Z为F所蕴含。

14. 给定关系 R(A,B,C,D,E)与 S(B,C,F,G),那么与表达式π2,4,6,7(Ơ2< 7(R▷◁S))等价的 SQL

    语句如下: SELECT( ) FROM R, S WHERE ( )；

    A． R.B，D，F，G

    B. R.B,E，S.C,F,G

    C. R.B，R.D,S.C,F

    D. R.B，R.C,S.C,F

    A． R.B=S.B OR R.C=S.C OR R.B <S.G

    B. R.B=S.B OR R.C=S.C OR R.B <S.C

    C. R.B=S.B AND R.C=S.C AND R.B <S.G

    D. R.B=S.B AND R.C=S.C AND R.B<S.C

    自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。经过自然连接后的结果属性有(A，S.B，S.C，D，E，F，G);投影运算就是从表中选择需要的属性列，第2,4.6.7列分别为(R.B，D，F，G);选择运算o2<7(RvS)的意思在RvS的结果中，选择出满足属性列2的值<属性列7的值的那些行。

    自然连接一定要考虑带先去重组合，然后在进行各种计算。

15. 某集团公司下属有多个超市,每个超市的所有销售数据最终要存入公司的数据仓库中。假 设该公司高管需要从时间、地区和商品种类三个维度来分析某家电商品的销售数据,那么最 适合采用( )来完成。

    A．Data Extraction B.OLAP C.OLTP D.ETL

    联机分析处理OLAP是一种软件技术，它使分析人员能够迅速、一致、交互地从各个方面观察信息，以达到深入理解数据的目的。

16. 对下面的二叉树进行顺序存储(用数组 MEM 表示),已知结点 A、B、C 在 MEM 中对应元素的 下标分别为 1、2、3,那么结点 D、E、F 对应的数组元素下标为( )。

    A．4、5、6 B.4、7、10 C.6、7、8 D.6、7、14

    二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点;把二叉树的所有结点安排成为一个恰当的序列，反映出节点中的逻辑关系;用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号。
    对于这些结点如果没有对应的左右孩子结点，则在对应数组位置存储为空。

17. 用哈希表存储元素时,需要进行冲突(碰撞)处理,冲突是指( )。

    A．关键字被依次映射到地址编号连续的存储位置

    B.关键字不同的元素被映射到相同的存储位置

    C.关键字相同的元素被映射到不同的存储位置

    D.关键字被映射到哈希表之外的位置

    哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表成为哈希表。其基本思想:首先在元素的关键字K和元素的位置P之间建立一个对应关系f，使得P=f(K)，其中成为哈希函数。创建哈希表时，把关键字K的元素直接存入地址为(K)的单元;查找关键字K的元素时利用哈希函数计算出该元素的存储位置P=f(K);当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1=K2，但f(K1)=f(K2)，这种现象称为hash冲突，实际中冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。

18. 对有 n 个结点、e 条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历, 时间复杂度为( )。

    A．O(n2) B.O(e2) C.O(n+e) D.O(n*e)

    在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O(n+e)。在邻接矩阵中，算法需要遍历邻接矩阵xn个点，所以时间复杂度是O(n×n)。

本文标签： 设计师 软件 易错题