数据库系统工程师复习资料

数据库系统工程师复习资料 答案(1)A，(4)D，(5)D，(6)D，(7)D，(9)D，（10）C，（13）B，（17）B（18）A （20）B（21）A（25）D（26）D（27）A（30）C（31）A（33）C（36）C（37）D （38）B（39）C（41）D（43）D（44）C（46）C（47）B（48）D（51）C（52）C （62）B（63）C（64）A（66）C（67）A（68）B（69）D（70）A（71）A（72）C （73）B（74）D（75）B 58 C 59 A 60 D 61 B 63 D 64 C 66 A 67 B 68 C 69 A 70 D 71 D 72 D 73 B 74 C 75 A 1．(1)primary key(col1,col2) (2)primary key(col1) primary key(col2) (3)constraint c1 primary key(col1,col2) 两个属性组合为码， 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 SQL中一般采用第一种形式。constraint 在ORACLE中用得多，表示某种约束，在这里是主键约束，在标准SQL中一般不用。 2．(1)references 表名(列名) (2)references 表名考试时该用那一种. * 用前一种，更明确指出了要引用的列。 3．一般的格式是： creat view 要创建的视图名称 as select 查询子句 [with check option]其中[]表示可选。with check option表示在执行UPDATE、INSERTER、DELETE等操作时保证更新、插入或删除的行满足视图定义中查询子句中的条件表达式。 4．各本书上不同，是因为它们基于不同的数据库软件而编写的。标准SQL似乎没有严格规定数据类型。各数据库软件的数据类型一般都很类似，比如int 只是integer前三个字母而已，一般情况下，阅卷老师都认识这些符号，所以不必过于担心。 5．求关键路径：以考点分析与真 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 详解书P117例题4为例 首先应该搞清楚概念。在AOE网络中，顶点代表事件（实际上就是该顶点的所有入边所表示的活动均已完成），弧代表活动。从源点到某顶点的最长路径长度为该顶点所代表事件的最早发生时间，该题中，从源点V1到顶点V6只有一条路径V1->V3->V6，于是事件V6的最早开始时间为2+3=5。在不推迟整个工程完成的前提下，一个事件允许的最迟发生时间称为该事件的最迟发生时间，p27提供的求它的递推式的要义有两点：一是汇点的最迟发生时间等于其最早发生时间，亦即整个工程关键路径的长度；二是某点的最迟发生时间等于关键路径长度减去从该点出发至汇点的最长路径长度。比如，从V2到V7有两条路径：V2->V5->V7、V2->V4->V5->V7,路径长度最长的是前者，长度为4+3=7，又易求得关键路径长度为10，于是事件V2的最迟发生时间为10-7=3。初学者在这个地方最易疑惑。某活动的最早开始时间等于该活动对应的弧的起点的最早开始时间。该题中，活动a6的最早开始时间等于事件V3的最早开始时间，亦即2。某活动的最迟发生时间等于该活动对应的弧的终点的最迟发生时间减去该活动持续的时间。该题中，活动a6的终点为V4，易求得其最迟发生时间为10-3-1=6，继而求得a6的最迟发生时间为6-1=5。用某活动的最迟开始时间减去该活动的最早发生时间便得到该活动的松弛时间。该题中，a6的松弛时间即为5-2=3。 6。段管理的主要优点是：可以实现动态链接。 所谓段的动态链接，是指在程序运行一开始，只将作业的主程序段调入内存，其他各段是在作业运行过程中逐步被调入内存的。 7．在一个多道程序设计系统中,不采用移动技术的可变分区方式管理主存.设用户空间为100K,主存空间采用最先适应分配算法,采用计算时间短的作业优先算法管理作业,今有如下所示的作业序列.作业名,进入输入井时间,需计算时间,主存需求量 JOB1 8.0小时 1小时 20K JOB2 8.2小时 0.6小时 60K JOB3 8.4小时 0.5小时 25K JOB4 8.6小时 0.4小时 20K 若忽略系统开销,则JOB2的开始执行时间为(),JOB3的完成时间为(),JOB4的周转时间为(). 请问:什么是最先适应分配算法,还有其他什么算法吗?最好能说得详细些.此题怎么解? 所谓最先适应分配算法,就是指使用第一次找到的那块合适的内存区域分给作业。该题并不是考最先适应分配算法，而是考察短作业优先调度算法。 （1），所谓短作业优先，是说在各作业同时到达或都在等待时，优先选择执行时间短的。 （2），作业的周转时间包括所有等待时间和自己的执行时间。 发现我们两个都犯了个错误。错误在于忽略了最先适应分配算法以及题目所说的“不可移动”分配内存。在JOB1从输入井进入内存之后，内存还剩余80K，8.2时刻JOB2赶到，申请60K内存，批准，还剩余20K，但不能立即执行，因为JOB1还没执行完。8.4时刻JOB3也赶到，申请25K内存，内存不够，不批准，让JOB3在输入井中等待。8.6时刻JOB4赶到，申请20K，刚好有20K，批准，此时内存中有三个作业JOB1、JOB2、JOB4。9时刻，JOB1执行完成，释放出20K内存，但是不满足JOB3的25K需要，所以此时JOB3被排斥在内存之外，于是下一步只能选择JOB4，执行JOB4之后也释放20K内存。此时，注意，在JOB2上面和下面各有20K内存区域，又因为分配后的内存不可移动，不能把60K移动到某一头，让这两个20K连成连续的40K空间。这导致JOB3一直被排斥在内存之外，直到JOB2执行完之后，这个时候已经是时刻10，也就是那个参考答案表中的JOB3的开始时间是10了。 8．设有一个关系模式R（A,B,C,D),F={A->B,B->C,C->D,D->A}，求R的侯选码及可达到的最高范式。 只要能推导出整个属性组U，况且没有多余元素就是候选码。在这个关系模式中，A、B、C、D都能推导出U，况且只有自身一个元素无多余元素，所有都是候选码。 因为R没有非主属性，R是3NF.但是R是否属于BCNF呢？按照BCNF的定义：如果每一个决定因素都含有码，即是BCNF，当然此题满足这个条件，从这个条件看，R是属于BCNF。 但是R又存在传递依赖（A->B->C得出A->C），好像又不是BCNF，这到底应该怎么理解？这里应该是BCNF。你所例举的传递依赖是不成立的，它不符合传递依赖的定义，你错就错在这里。 对于传递依赖X->Y->Z，要求：1，Y不是X的子集；2，Y->X不成立；3，Z不是Y的子集。 你例举的“A->B->C”，根据函数依赖集中的“B->C,C->D,D->A”及Armstrong推理系统中的传递律（注意，不是传递依赖，不要把两者搞混了），可得B->A。这显然不满足条件2。因此不属于传递依赖。但是它是成立的，只是不符合传递依赖的定义罢了。 9．有只与一个实体相当的联系吗？如果只有一个实体，还需要什么联系？ 你狭隘地理解了实体间的联系。在E-R中，可以将实体理解为一个集合。一个实体可以自己跟自己联系，比如职工实体集中有领导和被领导的联系，也就是说职工当中某一员来领导所有职工，那么“领导”这个联系两端都连接在实体“职工”上。 10．元组比较操作（a1,a2) <(b1,b2)的意义是_________。 老师，本题我觉得不理解，首先，元组中某一分量是可以用来比较的,如a1[i] < b1[j]，但是元组之间也能比较的吗？通俗点说，a1,a2,b1,b2都是表中的一行记录吧，如果有一选课关系模式（学号，课程号，成绩）。数据为（张三，‘c001',67),(李四，'c002',78)，难道这二条记录有可比性？ 当然不是你说的这种情况的操作，这种元组比较一般用于字符或者数字比较。比如比较（10，11）和（10，12），那么根据上述法则有（10，11）<（10，12）。又如（12，6）和（10，66），则有（12，6）>（10，66）。又如（a，6）和（b，1），则有（a，6）<（b，1）。优先考虑第1个，元素比较，在第一个相等的情况下才考虑第2个。 对（39）我还是不明白，如果是字符串比较“abc;234" <"bbc;234"或者"abc;324" < "abc;434"那我理解。还有（58）、（59）的试题分析，其中有A = 18？？？ “abc;234" 和"bbc;234"比较，取第1个字母a、b比较，发现a < b,于是abc;234" <"bbc;234"。 11．老师,关于六套模拟题下午第三大题中最后一小题(第9和10)的填空,是否都可以用肯定的方式?还有没有其他答案?这类题一直无法理解其真正的思路.急.请老师能否详细解答一下.解这类题有什么技巧没有?此类题做过几道,每一次都糊涂. 一般地，如果看到查询要求中有“至少”之类的，需要从反面考虑问题的，就用双重否定来表示肯定。像这种用双重否定的查询SQL语句，在月4日数据库网上课堂记录中重点详细讲了这个问题 查询至少选修了95002选修的所有课程的学生的学号解题思路是怎么样的? 查询语句为 SELECT Distinct Sno FROM SC SCX WHERE NOT EXISTS (SELECT * FROM SC SCY WHERE SCY.SNO='95002' AND NOT EXISTS (SELECT * FROM SC SCZ WHERE SCZ.SNO=SCX.SNO AND SCZ.CNO=SCY.CNO )) 我个人感觉,在第二层中 SELECT * FROM SC SCY WHERE SCY.SNO='95002' AND NOT EXISTS (SELECT * FROM SC SCZ WHERE SCZ.SNO=SCX.SNO AND SCZ.CNO=SCY.CNO ) 只有先执行了 SELECT * FROM SC SCY WHERE SCY.SNO='95002' 生成新的SCY'(其中就只包括了95002选修课程的相关信息),再在这个SCY'的基本上执行 NOT EXISTS (SELECT * FROM SC SCZ WHERE SCZ.SNO=SCX.SNO AND SCZ.CNO=SCY.CNO ) 判断,再把这个返回值送给第一层的NOT EXIST判断,这样整个查询语句才执行得通,可我总觉得有点不太对头,请老师指正 老师提示： SELECT Distinct Sno FROM SC SCX.... 中的“FROM SC SCX”，表示将表SC取一个别名SCX，其它类似。 另外，提示： 嵌套查询中，外层查询称为父查询，内层查询称为子查询。如果子查询的查询条件不依赖父查询，则称这类子查询为不相关子查询，在这种情况下，一般由外向里进行处理，即每个子查询在上一级查询处理之前求解，子查询的结果用于建立其父查询的查找条件。如果子查询的查询条件依赖父查询，则称这类子查询为相关子查询，上例就是。这种情况下，是这样处理的，首先取外层查询表中的第一个元组，根据它与内层查询相关属性值处理内层查询，若满足要求就将第一个元组放入结果表中，然后再取外层查询表的第二个元组，做类似处理。重复上述过程直到外层查询表检查完为止。 该查询可以用逻辑蕴涵来表示：查询学号为NO的学生，对所有的课程Y而言，只要学号为95002的学生选修了课程Y，则学号为NO的学生也选修了课程Y。即：用P表示谓词：学生95002选修了课程Y。用M表示谓词：学生NO选修了课程Y。那么上述查询可表示为：（△Y）P→M转换成等价形式：（△Y）P→M≡┐（〓Y（┐（P→M）））≡┐（〓Y（┐（┐P∨M）））≡┐〓Y（P∧┐M）其中假设，△表示任取，〓表示存在，∨、∧分别表示“逻辑或”、“逻辑与”，┐表示逻辑取非。这个式子表达的语义就是：不存在这样的课程Y，学生95002选修了Y，而学生NO没有选。 它的查询过程大致是这样： 从最外层查询表SCX取第1个元组，进入第2层查询，取第2层查询的查询表SCY的第1个元组，检查条件“SCY.SNO='95002' ”与： NOT EXISTS (SELECT * FROM SC SCZ WHERE SCZ.SNO=SCX.SNO AND SCZ.CNO=SCY.CNO ) 是否同时成立。假设SCY的第1个元组的SCY.SNO为'95002' ，则第1个条件成立，进入第3层即最内层查询，取查询表SCZ的第一个元组进行“SCZ.SNO=SCX.SNO AND SCZ.CNO=SCY.CNO”判断，如果不成立，则取SCZ的第2个元组再进行判断，将SCZ的所有元组都进行判断，如果SCZ的所有元组都不满足“SCZ.SNO=SCX.SNO AND SCZ.CNO=SCY.CNO”，表明此次最内层查询为空，则第2层的NOT EXISTS返回真值，否则返回假值。 如果它返回是真值，那么导致第2层查询的条件“WHERE SCY.SNO='95002' AND NOT EXISTS...”成立，于是第2层查询非空，于是最外层的NOT EXISTS返回假值，那么最外层查询表SCX的第1个元组不符合要求，不在结果表之列。 如果它返回是假值，则导致第2层查询的条件“WHERE SCY.SNO='95002' AND NOT EXISTS...”不成立，那么就要取第2层查询表SCY的第2个元组进行上述类似的操作，如果对于SCY的所有元组都不满足“WHERE SCY.SNO='95002' AND NOT EXISTS...”，表明第2层查询为空，则最外层的NOT EXISTS返回真值（否则返回假值），那么表明SCX第1个元组符合要求，将其放入最后的结果集中。如果最外层的NOT EXISTS返回假值，那么表明SCX第1个元组不符合要求，则不将其放入最后的结果集中。 然后取SCX的第2个元组，继续进行上述类似操作，直到搜索完它的所有元组为止。 这类似于三个嵌套的for循环，先执行最内层的循环，然后是第2层，最后是最外层。 12．setof表示前面的是个集合，ref表示引用。studies setof(ref(study))表示：studies 这个集合的值是从集合study取值,相当于关系模型中的外键，只是说法、写法不一样而已。 student ref(student)为什么么不用setof 在对象联系图中，我们看到从study指向student的是单箭头，因此它不是一个集合，于是只要用ref就可以了。而从student指向study的是双箭头，所以要多个setof，表示studis是个集合。 13《软件设计师考试试题分类精解》P112，例26.只有两个信号量0、1的话。执行顺序怎样？（设S为同步信号量初值为0，mutex为互斥信号量初值为1）。因为PB进程不能超前PA进程，只有等PA进程写数据后PB才能取。 PA进程： while (true) {生产一个产品 P(mutex) //申请临解资源写数据到缓冲区 V(S) //通知PB V(mutex) //释放临解资源 } PB进程： while(true) { P(mutext) P（S） // 判断是否已有数据从缓冲区读数据 V(mutex) //释放临解资源 }如果按上面:当按PA->PB->PA...的顺序推进时，执行正确；但进程执行顺序是不定的，如果按PA->PA->PB->...的顺序推进时，即PA连续执行两次或以上时，执行不正确。该如何解决？ 在这里，因为只有两个进程，所以不必要设置互斥访问信号量，只需要设置两个同步信号量即可：empty，表示空管道个数，初值显然为1；full，表示满管道个数，初值显然为0. 其过程如下： PA进程： while (true) { P(empty)； 写数据到管道； V(full)； } PB进程： while(true) { P(full)； 从管道读数据；//进入临界区读数据 V(empty) } 现在如果PA要连续两次写数据，第一次之后empty=0，第二次再执行P(empty)；使得empty=-1，于是被阻塞在临界区这个地方，将PA置入阻塞在empty的等待队列。它必须等到执行PB中的V(empty)才可以第2次写入，因为执行V(empty)之后，empty=0，表明有进程被阻塞在empty信号量上，系统查询empty信号量的等待队列，发现PA，于是调入PA执行临界区操作，注意，因为临界区在P(empty)；语句之后，继续执行PA时不能再执行“P(empty)；”，而是直接从临界区“写数据到管道；”开始继续执行。 怎样区分确定的有限状态自动机和非确定的有限自动机？一套模拟题里的分析中有。但我还是不理解。可以唯一确定一个状态是什么意思？能举例说明吗？ 所谓的唯一确定性，是指，对任何状态k，和输入的符号a,能唯一地确定下一个状态。也就是说转换函数是个单值函数。而非确定有限自动机，却不一样，对任何状态k，和输入的符号a,可能有多个下一个状态。 比如某DFA中，有两个状态1、2，1状态接受字符a，就从状态1跃迁到2，那么转换函数为f(a, 1)={2}.而在NFA（不确定自动机）中，有三个状态1、2、3，1状态接受字符a，就可以跃迁到状态2，也可以跃迁到状态3，即f(a, 1)={2, 3}。 14. 老师,电子教材中关于海明码的有一个问题:校验位:r3=I8◎I7◎I6◎I5是怎么得来的? "◎"代替异或运算符 比如r3，n=3，信息位I8 对应的第十二位12=2~3+2~2，式子右边含有2~n=2~3，类似地I7、I6、I5也含有2~n=2~3，所以r3=I8◎I7◎I6◎I5.其中~表示方幂。 r3是表示在所有校验位中排第3地那个校验位，I8表示在所有信息位中排第8的那个信息位，而I8却在整个编码中排第12位。 15. 开发部有4000台微机该公司只有若干个C 类IP地址,无AB两类那么要_____个C类网络才能组建开发部的子网.答案是16 首先要搞清楚C类地址的格式。C类地址中前3位是110，左数第4位到左数24位为网络地址，从左数第25位到最后的32位共32-25+1=8位是主机地址。2的8次方就是256，去掉两个特殊的地址（主机号全为1或0）得254，表示一个C类网络能容纳254台主机，再用4000/254... 16. 首先注意前提，关系模式是全码，既然是全码的话，如果存在主属性对码的部分依赖，那么该关系不可能是全码，如果存在主属性对码的传递依赖，那么实际上是直接依赖。 我们来举例说明，比如R（A，B，C）是全码，有主属性B对码的部分依赖即，AC->B。显然此是B是多余的，因为通过AC就可以推导出ABC，因此跟全码矛盾。 如果存在对全码的传递依赖，比如ABC->X->Y，其中X、Y是某一属性。显然X、Y是ABC的真子集，而根据Armstrong公理系统可知，任何属性组都能直接推导出自己的真子集，可见上面的ABC->X->Y并非传递依赖。 基本上是明白了，如果是全码则不存在主属性的传递依赖及部分依赖，如果不是全码，有多个候选码，判断BCNF，则需判断主属性的传递依赖及部分依赖是否存在 们将某一关系是全码等同于某一关系的属性都是主属性了。事实并非如此。由于一个关系可能有多个候选码，而包含在任一候选码中的属性都是主属性。当所有候选码的中的属性的并集等于总属性集U时，所有的属性都是主属性，但这个时候关系模式可能不是全码。可见二者并不是等价的。你回答说一定是3NF，也没有错，因为它一定是BCNF，那么必定是3NF。如果将问题改成：如果一个关系模式的属性都是主属性，那么该关系模式最高一定可达到第几范式？那么就答：3NF。 17. 数据结构多看二叉树和图，软件工程多看UML和软件测试，个人建议。 18、关系模式R（U，F），U={A,B,C,D,E}，F={A→BC,BCD→E,B→D,A→D,E→A},如何分解成BCNF,请写出详细分析过程。 U={A,B,C,D,E}，F={A→BC,BCD→E,B→D,A→D,E→A}，则R的主码为A，其中D和E传递依赖于A，故可分解为R1={A，D}，R2={A，E}和R2={A，B，C}，此时都为BCNF。 19、在复习时，建议你边看边注意总结，个人觉得像全球信心化、数据仓库、电子商务等叙述性的知识点容易出这种题型的题。下午试题一般为4道题目，第一道题为数据流程设计，第2-4道为数据库设计题，包括E-R图设计，E-R图向关系模式的转换，范式、SQL语言等知识点。 23．设关系模式R（ABCDE）上的函数依赖集F={A->BC,BCD->E,B->D,A->D,E->A},将R分解成两个关系模式：R1= (ABD),R2=(ACE),则R1 和R2的最高范式分别是：？ R2上函数依赖集为{A->E,E->A,A->C}，A、E都是候选键，亦即每个函数依赖的决定因素都是码，故为BCNF。A->E是否如下可以推出：A->BC,BCD->E所有AD->E,又A->D,所以有A->E. 21、设有关系模式 W ( C，P，S，G，T，R )，其中各属性的含义是：C——课程，P——教师，S——学生，G——成绩，T——时间，R——教室，根据语义有如下数据依赖集： D={ C→P，(S，C)→G，(T，R)→C，(T，P)→R，(T，S)→R } 关系模式 W 的一个码( 关键字 )是 ？ 如果函数X→U在R上成立，且不存在任何X的真子集X'，使得X'→U也成立，则称X是R的一个候选码。题目中有：(T，S)→R，(T，R)→C，(S，C)→G，C→P，(T，P)→R，又因为U={ C，P，S，G，T，R }，所以(T，S) →U，(T，S)为W的码。 简单地说，候选码决定了所有其它属性，标识了整个元组，同时也不含多余元素，比如上例中，(T，S，R)→U，但（T，S，R）不是候选码，因为它有多余属性R，不满足“如果函数X→U在R上成立，且不存在任何X的真子集X'，使得X'→U也成立”，因为（T，S，R）中有真子集（T，S）使得(T，S) →U。 22、“在W3中，C传递依赖于键，所以 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化程序最高达到2NF”，在W3中的关系为：（T，R）→C，（T，S）→R，没什么传递依赖吧？ 解：存在。由题目的(T,S)->R和(T,R)->C可以得到(T,S)->C，我们选取(T,S)作主码，则每一个非主属性都完全函数依赖于码，W属于2NF。接下来判断W是否属于3NF，由于(T,S)->R、(T,R)->C、(T,S)->C中已有传递函数依赖，所以W不属于3NF，所以W最高为2NF。在判断是否是3NF时，所谓的传递依赖是指非主属性对码的传递依赖。 1. 23、我每次做“关于判断一个分解是否为保持函数依赖”的时候，我都选是，我也不知道什么情况下不是，你能不能举一个不保持函数依赖的关系模式R（U，F）的例子,并说明为什么不是？谢谢 解：例如：关系模式R={A，B，C}，其FD={A->B，A->C}，把R分解为R1={A，B}，R2={B，C}，则该分解就不保持函数依赖。因为在R中的A->C丢失了。 2. 操作系统中,关于p,v 操作问题,s信号量若是负值,表示等待进程的个数.怎么理解?若s的初值为1,执行一个p 操作,s=s-1;(相当于加锁),难道还可以继续接受别的进程执行p 操作吗? 能否举一例,透彻解释一下p,v操作详细过程.谢谢! 解：例如，系统有1台打印机，首先s=1，当一个使用前，执行P操作，s=0，如果另一个进程申请使用，则执行P操作，s=-1，但这时已经没有资源，该进程必须等待，依次类推，再来一个进程申请，执行P操作，s=-2，等待。。。。 1． 设度为1的结点数为N1，设度为2的结点数为N2，设度为0的结点（叶子）数为N0，则根据二叉树的公式：N0+N2=2N2+1，即N0=N2+1。 2． SNMP的设计是基于IP之上的无连接的用户数据报 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ，即UDP/IP协议。 海明码是奇偶校验的一种扩充。它采用多位校验码的方式，在这些校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行校验位组合，可以达到发现错误，纠正错误的目的。 假设数据位有m痊，如何设定校验位k的长度才能满足纠正一位错误的要求呢？ K位的校验码可以有2^k个值。显然，其中一个值表示数据是正确的，而剩下的2^k-1个值意味着数据中存在错误，如果能够满足：2^k-1>m+k（m+k为编码后的总长度），在理论上k个校验码就可以判断是哪一位（包括信息码和校验码）出现问题。编码步骤如下： （1） 根据信息位数，确定校验位数，2^r>=k+r+1，其中，k为信息位数，r为校验位数。求出满足不等式的最小r，即为校验位数。计算机校验位公式如下： 表1-3其实可以当成一个公式来套用,如有已经编码的数据1100 1001 0111.我们只需把这些数据填充一校验公式,即可得到信息位与校验位.填充的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 是这样的,首先看数据的最低位(即右边第一位),最低位为1,把1填充在公式表的r0位置,接着取出数据的次低位数据(即右边的第2位),把它填充到r1位置,把右边第3位数填充到I1位置.依此类推,我们可以得到表1-4: 表中第二行数据为1100 0011，这就是数据1100 1001 0111的编码信息，而表格第三行是1011，这便是校验位。 注意：校验位r所在位数为2^n,其余由信息位填充；信息位下标从1开始，而校验位下标从0开始。 例如：I8对应的第十二位12=2^3+2^2,I7，对应的第十一位11=2^3+2^+2^0,I6对应的第十位10=2^3+2^1,I5对应的第九位9=2^3+2^0，一直写到I1对应的第三位。校验位r由前面位数写成2的幂之和中包含2^n的位数对应的信息位之和构成。例如：r3=I8①I7①I6①I5（其中的1代表加号）注意：其中“①”异或运算。 （3）求校验位。根据上面我们所说的计算公式可以求出校验位。（4）求海明码。 2．纠错步骤 （1）根据海明码的信息位和校验位的分布规则，找出接收到的数据的信息位以及校验位。 如有已经编码的数据1100 1001 0111，则可以根据上表得到编码的信息为：1100 0011；校验位为：1011， （2） 接收端对校验位进行验证S=r(校验)+r(接收) （3） 判断校正因子是否有错，并改正。Sn Sn-1 Sn-2……S0二进制对应的是那位就是那位出错，将其改正完成纠错。如1001为第九位，将第九位1变0（或0变1）即可。 例题1 求信息1011的海明码。 解答：（1）2^r>=4+r+1,确定校验位为3位2^3>=4+3+1. （2）列出公式表格。 7=4+2+1，6=4+2，5=4+1，3=2+1 r2=I4+I3+I2 r1=I4+I3+I1 r0=I4 +I2+I1 根据公式得r2=0,r1=0,r0=1 加入表格 则海明码为1010101 P-V操作理解析疑 （1）定义：P原语的主要操作是：（1）sem减1；（2）若sem减1后仍大于或等于零，则该进程继续执行；（3）若sem减1后小于零，则该进程被阻塞，在相应队列中排队，然后转向系统的进程调度。 V原语的主要操作是：（1）sem加1；（2）若相加结果大于零，则该进程继续执行；（3）若相加结果小于或等于零，则唤醒一阻塞在该信号量上的进程，然后再返回原进程继续执行或转进程调度。 典型理解偏差：1。以V原语的1、2步来做，Sem不就永远大于0，那进程不就一起循环执行成为死循环了？ 2．Sem大于0那就表示有临界资源可供使用，为什么不唤醒进程？ 3．Sem小于0应该是说没有临界资源可供使用，为什么还要唤醒进程？ 4．如果是互斥信号量的话，应该设置信号量Sen=1，但是当有5个进程都访问的话，最后在该信号量的链表里会有4个等待，也是说S=—4，那么第一个进程执行了V操作使S加1，释放了资源，下一个应该能够执行，但唤醒的这个进程在执行P操作时因S<0，也还是执行不了，这是怎么回事呢？ 5．Sem的绝对值表示等待的进程数，同时又表示临界资源，这到底是怎么回事？ 析疑 1。P操作对Sem减1的。P、V原语必须成对使用！从而不会造成死循环。 2．Sem大于0的确表示有临界资源可供使用，而且这个时候没有进程被阻塞在这个资源上，也就是说没有进程因为得不到这类资源而阻塞，所以没有被阻塞的进程，自然不需要唤醒。 3．V原语操作的本质在于：一个进程使用完临界资源后，释放临界资源，使Sem加强，以通知其它的进程，这个时候如果Sem<0，表明有进程阻塞在该类资源上，因此要从阻塞队列里唤醒一个进程来“转手”该类资源。比如，有2个某类资源，三个进程A、B、C、D要用该类资源，最开始Sem=2，当A进入，Sem=1，当B进入Sem=0，表明该类资源刚好用完，当C进入时Sem=—1，表明有一个进程被阻塞了，D进入，Sem=—2。当A用完该类资源时，进行V操作，Sem=—1，释放该类资源，而这时Sem<0，表明有进程阻塞在该类资源上，于是唤醒一个。 4．当一个进程阻塞了的时候，它已经执行过了P操作，并卡在临界区那个地方。当唤醒它时就立即进入它自己的临界区，并不需要执行P操作了，当执行完了临界萄程序后，就执行V操作。 5．当信号量Sem小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。S大于0时表示可用的临界次数。注意在不同情况下所表达的含义不一样。当等于0时，表示刚好用完。 � �