《09年软件设计师考试考前点兵（查漏补缺）》由会员分享，可在线阅读，更多相关《09年软件设计师考试考前点兵（查漏补缺）（8页珍藏版）》请在金锄头文库上搜索。
1、0909 年软件设计师考试考前点兵（查漏补缺）年软件设计师考试考前点兵（查漏补缺）(2009-04-30 13:52:15)1.1.关系模式、函数依赖、范式关系模式、函数依赖、范式有关系模式有关系模式 R(AR(A，B B，C C，D)D)，函数依赖集，函数依赖集 FA-B,FA-B, B-C,B-C, C-D,C-D, D-AD-A，请问这个关系，请问这个关系模式最高能达到第几范式模式最高能达到第几范式? ?大家晓得 1NF、2NF、3NF、BCNF，部分依赖，传递依赖，那是可以用耳熟能详来形容，但这个题你未必能答对或者疑虑重重。首先，我来明确什么是主属性，任何一个候选码中的任一属性都是主属
2、性。根据函数依赖集 FA-B, B-C, C-D, D-A，显然我们能得出任何一个属性都能推导出整个属性组，因此 A 是候选码，B 是候选码，C 是候选码，D 也是候选码。这样，A、B、C、D 都是主属性。根据 3NF 的定义我们知道，这个关系模式至少是 3NF，因为它没有非主属性，何谈是否存在非主属性对码的传递依赖，当然也不用谈非主属性对码的部分依赖。我们知道，在 3NF 的基础上消除主属性对码(注意，这里指所有的候选码)的部分依赖和传递依赖就能成为 BCNF，那么该关系模式是否存在主属性传递依赖于码呢?(对于该关系模式肯定不存在主属性对码的部分依赖，因为所有的码都是单个属性)有!而且是太多
3、了，随便举一个 A-B, B-C ，所以有 A-B-C,有传递依赖 A-C。问题就出在这个传递依赖上问题就出在这个传递依赖上! !让我们来认真看看传递依赖的定义的精髓理解：对于传递依赖 X-Y-Z，要求：(1)Y 不是 X 的子集;(2)Y-X 不成立;(3)Z 不是 Y 的子集。其中 X、Y、Z 是 U 的属性组(注意，并非一定是单个属性)，不满足上述三个条件中任何一个都不是传递依赖!必须全部满足!刚例举的“A-B-C“，根据函数依赖集中的“B-C,C-D,D-A”及 Armstrong 推理系统中的传递律(注意，不是传递依赖，不要把两者搞混了)，可得 B-A。这显然不满足条件2。因此不属于
4、传递依赖。但是它是成立的，只是不符合传递依赖的定义罢了。在该关系模式中，A、B 实际上是相互决定的，即 AB。分析到此，传递依赖的精髓浮出水面，它是区分 2NF 和 3NF 的利器，也是区分 3NF 和BCNF 的利器。2.PV2.PV 操作操作操作系统中的 PV 操作，是很多朋友头痛的问题，往往是望而却步，不击鼓，反而鸣金。针对大家理解存在的问题，我以软设 2004 年 11 月试题 26 来说说这个 PV 操作。进程 PA 不断的向管道写数据，进程 PB 从管道中读数据并加工处理，如下图所示。如果采用 PV 操作来实现进程 PA 和 PB 的管道通信，并且保证这两个进程并发执行的正确性，则
5、至少需要_(26)_。供选择的答案：供选择的答案：(26)A.1 个信号量，信号量的初值是 0B.2 个信号量，信号量的初值是 0、1C.3 个信号量，信号量的初值是 0、0、1D.4 个信号量，信号量的初值是 0、0、1、1有参考书上的原分析如下：有参考书上的原分析如下：这是一个典型的生产者-消费者的问题，其中进程 PA 和 PB 分别为生产者与消费者，管道为临界区。我们的程序应该设置 1 个同步信号量，为 1 时说明管道已满拒绝 PA 再写入数据，为 0 时说明管道为空拒绝 PB 再读出数据，管道初始是没有数据的，所以初始值为0，(特例情况即管道的大小为 1 个单位);程序还需要 1 个互
6、斥信号量，来保证程序只有一个进程访问管道，初始值为 1。因此选择 B。事实上这个分析是错误的，但是答案是正确，为什么?首先来明白什么是互斥信号量。互斥信号量是一个可以处于两态之一的变量：解锁态和加锁态。在该题中，即表示：PA、PB 中任何一个在对管道进行读或写时，剩下的那个进程必须等待，而不能一起进行读写，只有当其中一个操作之后才可以让另一个对管道操作。而互斥信号量的使用如下：/ mutext 是互斥信号量进程 A：/ mutext 是互斥信号量进程 A：.P(mutext)；临界区；V(mutext)；.进程 B：.P(mutext)；临界区；V(mutext)；.再回到那个题目，如果按照该
7、题的原分析，使用一个同步信号量一个互斥信号量，不管你如何调整语句顺序，都不能使 PA、PB 正常并发执行。正确的分析如下：正确的分析如下：在这里，因为只有两个进程，所以不必要设置互斥访问信号量，只需要设置两个同步信号量即可(两个同步信号量即可保证这两个进程对管道的互斥访问)：empty，表示空管道个数，初值显然为 1;full，表示满管道个数，初值显然为 0。其进程语句如下：PA 进程：while (true)P(empty)；写数据到管道；/进入临界写读数据V(full)； PB 进程：while(true)P(full)； 从管道读数据；/进入临界区读数据V(empty)现在如果 PA 企
8、图要连续两次写数据，第一次写完之后 empty=0，第二次进入 PA 内再执行 P(empty);使得 empty=-1，于是 PA 被阻塞在临界区这个地方，将 PA 置入阻塞在empty 的等待队列。它必须等到执行 PB 中的 V(empty)才可以第 2 次写入，因为执行 PB 中的 V(empty)之后，empty=0，表明有进程被阻塞在 empty 信号量上，系统查询 empty 信号量的等待队列，发现 PA，于是调入 PA 执行临界区操作，注意，因为 PA 中临界区在“P(empty);”语句之后，继续执行 PA 时不能又一次执行“P(empty);”，而是直接从临界区“写数据到管道
9、;”开始继续执行。这里有两个关键点关键点：(1)两个同步量即可保证互斥访问，理由是只有两个进程PA、PB。(2)在唤醒某一个进程时是接着从临界区执行的，而不是让该进程从头开始执行。3.3.海明码海明码计算机体系结构中的海明码也是大家的一大难点。什么是海明码距?事实上，海明码距就是码距，码距就是指两个码字 C1 与 C2 之间不同的比特数。例如： 1100 与 1010 的码距为 2，具体的对应比较关系如下表所示。码距求解示意表码距求解示意表位D3D2D1D01100对应位编码的比较1010因为两个码字在 D1 和 D2 两位上编码不同，所以码距为 2。同理，1111 与 0000 的码距为 4
10、。一个编码系统的码距就是整个编码系统中任意两个码字的的最小距离就是该编码系统的码距，例如，一个编码系统只有四个编码分别为：0000，0011，1100，1111。此编码系统中 0000 与 0011 的码距为 2，是此编码系统的最小码距，所以此编码系统的码距为 2。有些书上称码距为海明码距或汉明距，这让一些同学产生了误解，误认为海明码距就是海明编码的码距，这种概念是错误的。海明码距就是码距，它和海明编码没有必然联系。来看希赛的一道模拟试题!在海明码编码方法，若冗余位(检错位)为 3 位且与错码位置的对应关系为：S2S1S0111110101011100010001000错码位置a6a5a4a3
11、a2a1a0无错则冗余位 a0 的计算公式为_(7)_。供选择的答案：供选择的答案：供选择的答案：供选择的答案：A. a0= a2 a4 a6B. a0= a1 a3 a4 C. a0= a4 a5 a3D. a0= a3 a4 a6该题应该选哪个?大家第一眼看到这个题目时，肯定会有这种疑问，是不是题目出错了，a3 和 a2 的编码弄反了，其实没有弄反，这种写法是允许的。出这个题的原因也就是想让大家清楚一个概念，即海明码的较验位不一定要在 1,2,4,8.这些位置上。比如说我们这题中的较验位就放在了最低的三位：a2,a1,a0，而不是 a3,a1,a0。 a6a5a4a3a2a1a0这一点从哪
12、里可以看出呢，从题中给出的表就可以看出来。这里告诉大家一个规则：出错位置码中只有一个”1”的，就是较验码，他的计算公式就是把含有对应位置”1”的信息位进行异或运算。如 a2 的出错码为 100。我们就把出错码包含 1*的信息码选出，这样的信息码有：a6,a5,a4，所以 a2= a6 + a5 + a4，同样，a0 的出错码是：001，我们则把含*1 的信息码找出，有 a3,a4,a6，所以 a0= a3 + a4 + a6。答案选 D。在这里，我重点指出该分析中的一句话“出这个题的原因也就是想让大家清楚一个概念，即海明码的较验位不一定要在 1,2,4,8.这些位置上。”，可见出题者的初衷就是
13、破除你的定势思维。4.4.自动机和正规式自动机和正规式编译原理中的自动机和正规式等价转化的问题，是历年常考的知识点。下面以软设2005 年 11 月试题 28 为例来讲解。某一确定有限自动机(DFA)的状态转换图如下图所示，该 DFA 接受的字符串集是_(28)_，与之等价的正规式是_(29)_。供选择的答案：供选择的答案：(28)A.以 1 开头的二进制代码串组成的集合B.以 1 结尾的二进制代码串组成的集合C.包含偶数个 0 的二进制代码串组成的集合D.包含奇数个 0 的二进制代码串组成的集合(29)A.1*0(0|1)* B.(0|1*0)*1*)*C.1*(0|1)0)* D.(1*(
14、01*0)*)*首先，我对状态图做一些说明。在状态转换图中，末端没有状态连接的“”所指向的结点为初态结点，而终态用双环圈表示，显然，该题中 q0 既是初态又是终态，那么该DFA 显然能识别空串，当处于 q0 时输入 0 便转换到 q1，而当处于 q1 时输入 0 又回到 q0，并且在 q0 或 q1 状态连续输入 n0 个 1 仍回到原状态，因此，该 DFA 识别的串是包含偶数个 0 的二进制代码串，即在偶数个 0 之间或前后可插入任意个 1 的串，如、00、010、10101、1011011、1001101101。对于正规式，首先来了解几个符号的意思：“*”号的意思，在正规式中，它表示任意自
15、我连接，比如，a*表示 n0 个 a.，而(ab)*表示 n0 个 ab 相连： ababab.;“|”表示或;“”表示连接，常省略，如 ab=ab。如果某有穷自动机所能识别的字符串集跟某正规式对应的正规集相等，则称两者等价。将有穷自动机转 M 化为与其等价的正规式 R 的步骤为：首先，在 M 的转换图上加进两个状态 x 和 y，从 x 用标有 的弧连接到 M 的所有初态结点，从 M 的所有终态结点用标有 的弧连接到 y，从而形成一个新的有穷自动机，记为M，它只有一个初态 x 和一个终态 y，显然 L(M)=L(M), L(M)表示 M 所能接受的字符串集。然后，逐步消去的所有结点，直到只剩下
16、 x 和 y 为止，在消结过程中逐步用正规式来标记弧。其消结的规则如下：最后，从 x 到 y 的弧上标记的正规式即为所构造的正规式 R。以该题为例，其转化过程为：注意到，(R1|R2)* = (R1*R2*)*，所以，(1|01*0)* = (1*(01*0)*)*，因此 29 空选D。另外可以根据 28 题的结果来排除 29 空的 A、B、C 三个选项，因为这三个选项的正规式所能表达的串中不但含有偶数个 0 而且可含有奇数个 0，范围扩大了，所以不等价。好了，上面例举的一些知识点相对软考来讲是很少的一部分，我希望这能起到抛砖引玉的效果，引导大家去积极地备战。考前不可放松，要坚持到最后一刻，真希望你在我的鼓声中一鼓作气，乘风破浪，成功到达胜利的彼岸!
