转眼间，推迟了的2008下半年国家计算机软考就要在明后两天拉开帷幕了，本站为您整理了一些资料，让您最后磨一磨刀，祝您考个好成绩！

1.关系模式、函数依赖、范式

　　有关系模式R(A，B，C，D)，函数依赖集F{A->B, B->C, C->D, D->A}，请问这个关系模式最高能达到第几范式?

　　大家晓得1NF、2NF、3NF、BCNF，部分依赖，传递依赖，那是可以用耳熟能详来形容，但这个题你未必能答对或者疑虑重重。

　　首先，我来明确什么是主属性，任何一个候选码中的任一属性都是主属性。根据函数依赖集F{A->B, B->C, C->D, D->A}，显然我们能得出任何一个属性都能推导出整个属性组，因此A是候选码，B是候选码，C是候选码，D也是候选码。这样，A、B、C、D都是主属性。

　　根据3NF的定义我们知道，这个关系模式至少是3NF，因为它没有非主属性，何谈是否存在非主属性对码的传递依赖，当然也不用谈非主属性对码的部分依赖。

　　我们知道，在3NF的基础上消除主属性对码(注意，这里指所有的候选码)的部分依赖和传递依赖就能成为BCNF，那么该关系模式是否存在主属性传递依赖于码呢?(对于该关系模式肯定不存在主属性对码的部分依赖，因为所有的码都是单个属性)有!而且是太多了，随便举一个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。因此不属于传递依赖。但是它是成立的，只是不符合传递依赖的定义罢了。在该关系模式中，A、B实际上是相互决定的，即A<-->B。

　　分析到此，传递依赖的精髓浮出水面，它是区分2NF和3NF的利器，也是区分3NF和BCNF的利器。

　　2.PV操作

　　操作系统中的PV操作，是很多朋友头痛的问题，往往是望而却步，不击鼓，反而鸣金。针对大家理解存在的问题，我以软设2004年11月试题26来说说这个PV操作。

　　进程PA不断的向管道写数据，进程PB从管道中读数据并加工处理，如下图所示。如果采用PV操作来实现进程PA和PB的管道通信，并且保证这两个进程并发执行的正确性，则至少需要__(26)__。

　　

　　供选择的答案：

　　(26)A.1个信号量，信号量的初值是0

　　B.2个信号量，信号量的初值是0、1

　　C.3个信号量，信号量的初值是0、0、1

　　D.4个信号量，信号量的初值是0、0、1、1

有参考书上的原分析如下：

　　这是一个典型的生产者-消费者的问题，其中进程PA和PB分别为生产者与消费者，管道为临界区。我们的程序应该设置1个同步信号量，为1时说明管道已满拒绝PA再写入数据，为0时说明管道为空拒绝PB再读出数据，管道初始是没有数据的，所以初始值为0，(特例情况即管道的大小为1个单位);程序还需要1个互斥信号量，来保证程序只有一个进程访问管道，初始值为1。因此选择B。

　　事实上这个分析是错误的，但是答案是正确，为什么?

　　首先来明白什么是互斥信号量。互斥信号量是一个可以处于两态之一的变量：解锁态和加锁态。在该题中，即表示：PA、PB中任何一个在对管道进行读或写时，剩下的那个进程必须等待，而不能一起进行读写，只有当其中一个操作之后才可以让另一个对管道操作。而互斥信号量的使用如下：

　　// mutext是互斥信号量进程A：

// mutext是互斥信号量进程A：

{

......

P(mutext)；

临界区；

V(mutext)；

.....

}



进程B：

{

......

P(mutext)；

临界区；

V(mutext)；

.....

}

　　再回到那个题目，如果按照该题的原分析，使用一个同步信号量一个互斥信号量，不管你如何调整语句顺序，都不能使PA、PB正常并发执行。

正确的分析如下：

　　在这里，因为只有两个进程，所以不必要设置互斥访问信号量，只需要设置两个同步信号量即可(两个同步信号量即可保证这两个进程对管道的互斥访问)：empty，表示空管道个数，初值显然为1;full，表示满管道个数，初值显然为0。

　　其进程语句如下：


PA进程：
while (true)
{
P(empty)；
写数据到管道；//进入临界写读数据
V(full)；
}
PB进程：
while(true)
{
P(full)；
从管道读数据；//进入临界区读数据
V(empty)
}

　　现在如果PA企图要连续两次写数据，第一次写完之后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);”，而是直接从临界区“写数据到管道;”开始继续执行。

　　这里有两个关键点：(1)两个同步量即可保证互斥访问，理由是只有两个进程PA、PB。(2)在唤醒某一个进程时是接着从临界区执行的，而不是让该进程从头开始执行。

3.海明码

　　计算机体系结构中的海明码也是大家的一大难点。什么是海明码距?

　　事实上，海明码距就是码距，码距就是指两个码字C1与C2之间不同的比特数。

　　例如： 1100与1010的码距为2，具体的对应比较关系如下表所示。

码距求解示意表

　　因为两个码字在D1和D2两位上编码不同，所以码距为2。

　　同理，1111与0000的码距为4。

　　一个编码系统的码距就是整个编码系统中任意两个码字的的最小距离就是该编码系统的码距，例如，一个编码系统只有四个编码分别为：0000，0011，1100，1111。此编码系统中0000与0011的码距为2，是此编码系统的最小码距，所以此编码系统的码距为2。

　　有些书上称码距为海明码距或汉明距，这让一些同学产生了误解，误认为海明码距就是海明编码的码距，这种概念是错误的。海明码距就是码距，它和海明编码没有必然联系。

　　来看一道模拟试题!

　　●在海明码编码方法，若冗余位(检错位)为3位且与错码位置的对应关系为：

　　则冗余位a0的计算公式为__(7)___。

供选择的答案：

A. a0= a2 a4 a6

B. a0= a1 a3 a4

C. a0= a4 a5 a3

D. a0= a3 a4 a6

　　该题应该选哪个?

　　大家第一眼看到这个题目时，肯定会有这种疑问，是不是题目出错了，a3和a2的编码弄反了，其实没有弄反，这种写法是允许的。出这个题的原因也就是想让大家清楚一个概念，即海明码的较验位不一定要在1,2,4,8...这些位置上。比如说我们这题中的较验位就放在了最低的三位：a2,a1,a0，而不是a3,a1,a0。　

　　这一点从哪里可以看出呢，从题中给出的表就可以看出来。这里告诉大家一个规则：出错位置码中只有一个”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...这些位置上。”，可见出题者的初衷就是破除你的定势思维。

　　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*(01*0)*)*

　　首先，我对状态图做一些说明。在状态转换图中，末端没有状态连接的“→”所指向的结点为初态结点，而终态用双环圈表示，显然，该题中q0既是初态又是终态，那么该DFA显然能识别空串，当处于q0时输入0便转换到q1，而当处于q1时输入0又回到q0，并且在q0或q1状态连续输入n≥0个1仍回到原状态，因此，该DFA识别的串是包含偶数个0的二进制代码串，即在偶数个0之间或前后可插入任意个1的串，如ε、00、010、10101、1011011、1001101101。

　　对于正规式，首先来了解几个符号的意思：“*”号的意思，在正规式中，它表示任意自我连接，比如，a*表示n≥0个a...，而(ab)*表示n≥0个ab相连： ababab...;“|”表示或;“●”表示连接，常省略，如a●b=ab。

　　如果某有穷自动机所能识别的字符串集跟某正规式对应的正规集相等，则称两者等价。将有穷自动机转M化为与其等价的正规式R的步骤为：

　　首先，在M的转换图上加进两个状态x和y，从x用标有ε的弧连接到M的所有初态结点，从M的所有终态结点用标有ε的弧连接到y，从而形成一个新的有穷自动机，记为M’，它只有一个初态x和一个终态y，显然L(M)=L(M’), L(M)表示M所能接受的字符串集。

然后，逐步消去的所有结点，直到只剩下x和y为止，在消结过程中逐步用正规式来标记弧。其消结的规则如下：

　　

　　最后，从x到y的弧上标记的正规式即为所构造的正规式R。

　　以该题为例，其转化过程为：

　　

　　注意到，(R1|R2)* = (R1*R2*)*，所以，(1|01*0)* = (1*(01*0)*)*，因此29空选D。

　　另外可以根据28题的结果来排除29空的A、B、C三个选项，因为这三个选项的正规式所能表达的串中不但含有偶数个0而且可含有奇数个0，范围扩大了，所以不等价。

　　好了，上面例举的一些知识点相对软考来讲是很少的一部分，我希望这能起到抛砖引玉的效果，引导大家去积极地备战。考前不可放松，要坚持到最后一刻，真希望你在我的鼓声中一鼓作气，乘风破浪，成功到达胜利的彼岸!

3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.net/exam/