精 软件设计师必考题总结【上午题】
软件项目活动图题目
分值：大约2分
考题内容
某软件项日的活动图如下图所示，其中顶点表示项日里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间 (天)，则完成该项目的最少时间为(15) 天。活动 BD 最多可以晚开始(16)天而不会影响整个项目的进度。
- 完成该项目的最少时间：找最长路径
本题中最长路径为最下面一条，ABDGIKL，2+5+3+6+4+2=22天
- 某活动最晚多少天开始不影响整个项目
本题中问的是BD，在关键路径上，那就是第0天，但凡晚一天都完成不了
- 在关键路径上（在关键路径上进行分析，如何分析？）
- 不在我们这个关键路径上（结合关键路径进行，完成项目的差值天数进行分析）
- 某活动从多少天开始不会影响整个项目
例如BD第2天
- 同一个人完成多个项目，最少需要多少天
最上面15天，最下面22天，到达B的时候是第2天
从BC开始：15+5=20天，这个5是BD
从BD开始：22+3=25天
所以，同一个人完成，需要25天，25天把所有的项目都过了一遍
- 找出需要完成项目活动的路径
- 在相应路径完成的天数上加上需要帮忙的天数，判断两者的天数是否大于我们这个最少完成整个项目的天数（本题中为22天），我们选择最少的那个；如果一个大于一个小于，选择大于的那一者，选择最少需要多少天，是在完成全程的项目的基础上进行选择。
- 某个活动的松弛时间是多少天
例如：H→L
上面一行A→L：15天，下面：22天，22-15=7，从第12天（H）开始做，3天完成
松弛时间：可以偷懒的时间
H→L的松弛时间：7天
- 找自身和关键路径的天数
- 用完成项目的最短时间减去该活动所在路径的最短时间，之后再自己剩余所需完成项目的时间来判断，自己还可以“摸鱼”多久。
前驱图问题
分值：大约3分
考题内容
进程 P1、P2、P3、P4、P5 的前趋图如下所示。
若用 PV 操作控制进程 P1、P2、P3、P4、P5 并发执行的过程，需要设置五个信号量 SI、S2、S3、S4 和 S5，而且信号量 S1~S5 的初值都等于零。如下的进程执行图中 和 b 处应分别填写(26) ；c和d处应分别填写(27) ；e 和处应分别填写(28)
本题解答方法：
- 前驱图所要掌握的流程信息：
- 流程路径的确定
- P和V的关系：P，进；V：出
- 技巧总结：
- 首先根据从左到右的规律结合执行信息的图，来确定S1，S2，S3等这些执行语句标识
- 根据每个活动点（P1，P2，P3等）指向他们的箭头和出去箭头的数量，来分析要填的语句类型和个数 V(S1) P(S1)等等
二叉树的问题
分值：约1~2分
考题内容
设有二叉排序树（或二叉查找树）如下图所示，建立该二叉树的关键码序列不可能是（58）。
A. 23 31 17 19 11 27 13 90 61
B. 23 17 19 31 27 90 61 11 13
C. 23 17 27 19 31 13 11 90 61
D. 23 31 90 61 27 17 19 11 13
若有一颗二叉树的高度（即层数）为h，则该二叉树（59）。
- 二叉树排序的序列
- 规律总结：首先按照，比根节点小的放左边，比根节点大的放在右边（即左小右大）。判断是否符合前边的规律和题目给出的二叉树图
B选项：17比23小，放左边；再看19，比17大，放右边；31，比前面的都大，放右边；27比31小，放左边；90比31大，放右边；61比90小，放右边；11比他们都小，放在右边；13比11大放右边。
C选项：17比23小，放左边；27比17和23都大，题目给出的是31，有矛盾。
- 如果不符合那就是不可能的序列
- 规律总结：首先按照，比根节点小的放左边，比根节点大的放在右边（即左小右大）。判断是否符合前边的规律和题目给出的二叉树图
- 节点的计算
- 在二叉树里，叶子节点树一定比度为2的节点数要多一个
- 计算第n层的节点数是多少，2（n-1）
- 计算n层二叉树的总结点数，2n-1
A：2h-1；B错误（题目没有说是满二叉树），若为最多，则正确；C：最少有h个节点，一直单下去，题目并没有说是满二叉树；D：正确
- 堆序列的判断（是否是堆序列）
- 首先确定它是大根堆还是小根堆，目的就是确定它是往下递减还是递增
- 再给出选项的堆序列中，如果根节点确定了它是大根堆，我们只要判断每个节点的分节点只要比对于的父节点小就行，全部符合就是堆序列
例如：基于满二叉树来看，32、17、28、34，那这样就是错误的，不满足堆序列
流程图的问题
考题内容
- 路径覆盖需要多少个测试用例：关键点在于判断语句，目的就是实现判断语句所有情况的全覆盖
从判断2开始有左右两个分支，判断3又有左右两个；再加上判断1的“N”，总共4条，实现了全覆盖。上图就是4条测试用例
- 语句覆盖需要多少个测试用例：关键点在于实现全部语句的覆盖，通过判断语句来进行信息筛查的过程，目的就是实现全部语句的覆盖。（上图就是两条测试用例）
基于判断语句，因为判断语句才会出现分支。判断2开始分支，2个测试用例即可实现语句全部覆盖
疑问：判断3也是两条分支，为啥不是3个呢？因为判断3的“Y”没有语句。
- 环路复杂度计算：流程线的总数 – 语句总数 + 2 = 环路复杂度
上图中流程总线：13；语句总数：11
13 – 11 + 2 = 4
数据库的关系模式
分值：约1~5分
考题内容
假设关系 R<U，F>，U={A1,A2,A3}，F={ A1A3→A2，A1A2→A3}，则关系R 的各个候选关键字中必定含有属性(53)。
(53) A.A1 B.A2 C.A3 D.A2、A3
某企业的培训关系模式 R(培训科目，培训师，学生，成绩，时间，教室)，R 的函数依赖集F={培训科目→培训师，(学生，培训科目) →成绩，(时间，教室)培训科目，(时间，培训师)→教室，(时间，学生)→教室}。关系模式 R 的主键为 (52) ，其规范化程度最高达到(53)。
(52) A.(学生，培训科目) B.(时间，教室) C.(时间，培训师) D.(时间，学生)
(53) A.1NF B.2NF C.3NF D.BCNF
考点总结
- 掌握依赖符：A→B，B依赖于A
- 懂得画图
- 范式（有依赖关系）
理解：当主键是一个复合主键（两个字段构成一个主键）的时候，题目中有符合主键，就选2FN；假设有三个表ABC，每个表中有3个成员，A中有外键（B表的主键），B又有一个C的外键，这三个表连接起来共同推出一个完整的表。这样有多个表的链接关系推出来的就叫做3FN，本题选择2FN（符合组件；时间、学生可以推出所有的关系模式）。
- 1NF：各个成员有且只有一个
- 2NF：依赖于两个或多个字段组合的符合主键
- 3NF：多个关系才能推出一个完整的关系链
- 主键、候选键、外键
- 主键：可以推出全部成员（上图中A1）
- 候选键：主键就是从候选键中选出来的，一个表可以存在多个候选键
- 外键：另一个表中的主键，放在当前这个表中
- 函数冗余依赖
F={A1→A2，A1A2→A3，A1→A4，A2→A4}
问：哪个属于冗余情况
对冗余的理解：就是没必要的，可有可无的。A1→A4
疑问：A1A2也可也推出A3，他不是单独的
没有回复内容