首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 计算机考试 > 软件考试 > 计算机软件水平 >

09年下半年软件设计师考试考前秋点兵

2010-10-25 
读书人IT频道reader8.com/exam/jisuanji/  1.关系模式、函数依赖、范式  有关系模式R(A,B,C,D),函数依赖集F{A-B, B-C, C-D, D-A},请问这个关系模式最高能达到第几范式?  大家晓得1NF、2NF、3NF、BCNF,部分依赖,传递依
读书人IT频道reader8.com/exam/jisuanji/   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)__。
  

  供选择的答案:
  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,具体的对应比较关系如下表所示。
  码距求解示意表  

D3D2D1D0
对应位 编码的比较1100
1010

  因为两个码字在D1和D2两位上编码不同,所以码距为2。
  同理,1111与0000的码距为4。
  一个编码系统的码距就是整个编码系统中任意两个码字的的最小距离就是该编码系统的码距,例如,一个编码系统只有四个编码分别为:0000,0011,1100,1111。此编码系统中0000与0011的码距为2,是此编码系统的最小码距,所以此编码系统的码距为2。
  有些书上称码距为海明码距或汉明距,这让一些同学产生了误解,误认为海明码距就是海明编码的码距,这种概念是错误的。海明码距就是码距,它和海明编码没有必然联系。

读书人IT频道reader8.com/exam/jisuanji/
热点排行