软件设计师笔记

软件设计师笔记－12008-06-05 20:141. SIMD单指令流多数据流 一个控制部分，多个处理器，多个主存模块，各处理器以同步执行同一条指令，代表有并行处理机，阵列处理机，超级向量处理机，矩阵运算。

2. 运算器和控制器组成中央处理器。运算器由ALU、累加器、寄存器、多路转换器、数据总线组成；控制器由程序计数器、指令寄存器、指令译码器、状态/条件寄存器、时序发生器、微操作信号发生器组成。

3. 总线数据传输率＝时钟频率/每个总线包含的时钟周期数×每个总线周期传送的字节数

每秒指令数＝时钟频率/每个总线包含的时钟周期数/指令平均占用总线周期数。

4. 立即寻址：直接给出操作数，而非地址，ADD AX, 100；直接寻址：直接给出操作数地址，ADD AX, [100]或所在寄存器号（寄存器寻址, ADD AX, BX）；间接寻址：给出的是操作数地址的地址, ADD AX, [DX]/[[100]]；变址寻址：给出的地址需与特定的地址值累加从而得出操作数地址, ADD AX, [DI+100]，相对寻址：PC加上偏移量，ADD AX, *100。

5. 移位指令：算术移位（左移则在空位补0，右移则补符号位）、逻辑移位（左移右移都补0）

6. RISC编译后产生的机器指令数增多了，但是指令所需的周期数和每个周期的时间都减少了，以硬布线逻辑控制为主。

7. 多处理系统MIMD，需专门并行指令来控制并发执行，需要专门的同步措施。并行处理机和采用流水线结构的单机系统都是SIMD系统，但是区别是，并行处理机采用资源重复技术，后者采用的是时间重叠技术。

8. Cache，相联存取，根据内容而非地址来选择读写点。依据的是程序的局部性原理。淘汰算法：随机淘汰、FIFO、LRU。写操作方法：写直达（同时写主存和Cache）、写回（写Cache不马上写主存）、标记法。

9. 格式化容量＝每道扇区数×扇区容量×总磁道数；非格式化容量＝位密度×pi×最内圈直径×总磁道数；平均数据传输速率＝每道扇区数×扇区容量×盘片转数。

10. RAID0：无冗余无校验；RAID1：镜像模式；RAID2：纠错海明码；RAID3：位交叉奇偶校验；RAID4：块交叉奇偶校验；RAID5：无独立校验的奇偶校验。

11. 常见的I/O总线类型：IDE（最常用的磁盘接口），EIDE，ESDI，Ultra DMA，SCSI（用雏菊链的方式连接多个I/O设备）。系统总线：ISA，EISA，VESA，PCI，AGP，USB，IEEE1394，PCMCIA，MCA。

12. 进程的五态模型：运行，就绪，阻塞，挂起。

13. 死锁的必要条件：互斥条件、保持和等待条件、不剥夺条件、环路等待条件。解决死锁的策略：死锁预防（破坏其必要条件）、死锁避免（银行家算

法）、死锁检测、死锁解除（与死锁检测结合使用，采用剥夺方式）。

14. 存储分配算法：最佳适应法（最接近作业的自由区）、首次适应法（第一个可用的自由区）、最差适应法（选择最大的自由区）、循环首次适应法。

15. 程序设计语言分类：命令式/过程式（FORTRAN/C/PASCAL），函数式（Lisp/ML），面向对象（C++/SmallTalk/Java/C#），逻辑程序设计（Prolog）。

16. 解释型（接受所输入的用程序语言编写的源程序，然后直接解释执行，如Basic，现在的Java/C#也是一种半解释型的语言），翻译型（汇编和编译两类）

17. 编译的主要过程：词法分析(识别一个个单词符号)，语法分析，语义分析（雪是红的，语法正确，语义不正确），中间代码生成、代码优化、目标代码生成。

18. 以太网常用传输介质：10Base-T中T表示双绞线，100Base-TX采用的是5类的UTP（非屏蔽双绞线，100m），1000Base-SX（多模光纤）

19. 组网技术：X.25(面向连接，虚拟电路，分组，64Kbps，链路标准LAPB)，帧中继（没有专门定义物理层接口，只做检错、不重传、只有拥塞控制，链路标准LAP-D），ISDN（N-ISDN 基速率接口2B＋D 主速率接口，30B＋2D/23B+1D），ATM（信元53B 统计时分复用模式 150Mb/s 5种业务类型：CBR固定比特率，RT-VBR实时变化比特率， NRT-VBR非实时变化比特率，ABR有效比特率，UBR不定比特率（无连接）），ADSL（上行512K～1M，下行1～8M，接入方式：专线接入和虚拟拨号）

20. TCP支持的应用协议：Telnet（23）、FTP（21）、SMTP（25），HTTP（80） DNS（53）。UDP支持的应用协议：DNS（53）、SNMP（161）、TFTP（69）。

21. 对称密钥加密技术典型算法是DES和IDEA算法。DES密钥长度为56位，对64位的数据块进行加密，攻击DES的主要技术是穷举，为了提高安全性，就出现了使用112位密钥对数据进行三次加密的算法，称为3DES。采用DES的一个著名的网络安全系统是Kerberos。IDEA算法：其明文和密文都是64位，密钥长度是128位。（2）非对称密钥加密系统，其特点是加密和解密使用不同的密钥。典型算法是RSA，其安全性基于大数分解的困难性，可以用于数字签名。

22. 认证技术：Hash函数和信息摘要，又称散列函数，单向的Hash函数用于产生信息摘要，常见的算法是MD5（输入512位，输出128位）和SHA（安全散列算法，输入512，输出160），数字签名技术可以解决否认、伪造、篡改和冒充问题即数据的完整性和不可抵赖性。一般采用公钥算法。数字证书采用公钥体制，一般使用X.509国际标准，还有一种PGP，用来提供数字证书，用来证明通信双方的真实身份。keberros并非为每一个服务器构造

一个身份认证协议，而是提供一个中心认证服务器，提供用户到服务器以及服务器到用户的认证服务，其核心是利用了DES加密技术。为了防止重放攻击，它使用了一次性的Ticket和时间戳。

23. 实现VPN的关键技术是隧道技术、加解密技术、密钥管理技术和身份认证技术。VPN的关键技术是隧道技术，它是一种数据封装协议，也就是将一种协议封装在另一种协议中传输，从而实现被封装协议对封装协议的透明性。根据其工作的层次可分为以下两类：a. 二层隧道技术：包括PPP基础上的PPTP（点到点隧道协议）和L2F（二层转发协议）、L2TP（二层隧道协议）b. 三次隧道技术：主要代表是IPSec（IP层安全协议，它是IPv4和IPv6的安全标准）、移动IP协议和虚拟隧道协议（VTP）

如何成为优秀软件设计师收藏2008-08-25 16:081. 人远比技术重要

你开发软件是为了供别人使用，没有人使用的软件只是没有意义的数据的集合而已。许多在软件方面很有成就的行家在他们事业的初期却表现平平，因为他们那时侯将主要精力都集中在技术上。显然，构件（components），EJB（Enterprise Java Beans）和代理（agent）是很有趣的东西。但是对于用户来说，如果你设计的软件很难使用或者不能满足他们的需求，后台用再好的技术也于事无补。多花点时间到软件需求和设计一个使用户能很容易理解的界面上。

2. 理解你要实现的东西

好的软件设计人员把大多数时间花费在建立系统模型上，偶尔写一些源代码，但那只不过是为了验证设计过程中所遇到的问题。这将使他们的设计方案更加可行。

3. 谦虚是必须的品格

你不可能知道一切，你甚至要很努力才能获得足够用的知识。软件开发是一项复杂而艰巨的工作，因为软件开发所用到的工具和技术是在不断更新的。而且，一个人也不可能了解软件开发的所有过程。在日常生活中你每天接触到的新鲜事物可能不会太多。但是对于从事软件开发的人来说，每天可以学习很多新东西（如果愿意的话）。

4. 需求就是需求

如果你没有任何需求，你就不要动手开发任何软件。成功的软件取决于时间（在用户要求的时间内完成）、预算和是否满足用户的需求。如果你不能确切知道用户需要的是什么，或者软件的需求定义，那么你的工程注定会失败。

5. 需求其实很少改变，改变的是你对需求的理解

Object ToolSmiths公司的Doug Smith常喜欢说：“分析是一门科学，设计是一门艺术”。他的意思是说在众多的“正确”分析模型中只存在一个最“正确”分析模型可以完全满足解决某个具体问题的需要（我理解的意思是

需求分析需要一丝不苟、精确的完成,而设计的时候反而可以发挥创造力和想象力 - 译者注）。

如果需求经常改动，很可能是你没有作好需求分析，并不是需求真的改变了。

你可以抱怨用户不能告诉你他们想得到什么，但是不要忘记，收集需求信息是你工作。

你可以说是新来的开发人员把事情搞得一团糟，但是，你应该确定在工程的第一天就告诉他们应该做什么和怎样去做。

如果你觉得公司不让你与用户充分接触，那只能说明公司的管理层并不是真正支持你的项目。

你可以抱怨公司有关软件工程的管理制度不合理，但你必须了解大多同行公司是怎么做的。

你可以借口说你们的竞争对手的成功是因为他们有了一个新的理念，但是为什么你没先想到呢？

需求真正改变的情况很少，但是没有做好需求分析工作的理由却很多。

6. 经常阅读

在这个每日都在发生变化的产业中，你不可能在已取得的成就上陶醉太久。

每个月至少读2、3本专业杂志或者1本专业书籍。保持不落伍需要付出很多的时间和金钱，但会使你成为一个很有实力的竞争者。

7. 降低软件模块间的耦合度

高耦合度的系统是很难维护的。一处的修改引起另一处甚至更多处的变动。

你可以通过以下方法降低程序的耦合度：隐藏实现细节，强制构件接口定义，不使用公用数据结构，不让应用程序直接操作数据库（我的经验法则是：当应用程序员在写SQL代码的时候，你的程序的耦合度就已经很高了）。

耦合度低的软件可以很容易被重用、维护和扩充。

8. 提高软件的内聚性

如果一个软件的模块只实现一个功能，那么该模块具有高内聚性。高内聚性的软件更容易维护和改进。

判断一个模块是否有高的内聚性，看一看你是否能够用一个简单的句子描述它的功能就行了。如果你用了一段话或者你需要使用类似“和”、“或”等连词，则说明你需要将该模块细化。

只有高内聚性的模块才可能被重用。

9. 考虑软件的移植性

移植是软件开发中一项具体而又实际的工作，不要相信某些软件工具的广告宣传（比如java 的宣传口号write once run many ? 译者注）。

即使仅仅对软件进行常规升级，也要把这看得和向另一个操作系统或数据库移植一样重要。

记得从16位Windows移植到32位windows的“乐趣”吗 ？当你使用了某个操作系统的特性，如它的进程间通信(IPC)策略，或用某数据库专有语言写了存储过程。你的软件和那个特定的产品结合度就已经很高了。

好的软件设计者把那些特有的实现细节打包隐藏起来，所以，当那些特性该变的时候，你的仅

仅需要更新那个包就可以了。

10. 接受变化

这是一句老话了：唯一不变的只有变化。

你应该将所有系统将可能发生的变化以及潜在需求记录下来,以便将来能够实现（参见“Architecting for Change”，Thinking Objectively, May 1999）

通过在建模期间考虑这些假设的情况，你就有可能开发出足够强壮且容易维护的软件。设计强壮的软件是你最基本的目标。

11. 不要低估对软件规模的需求

Internet 带给我们的最大的教训是你必须在软件开发的最初阶段就考虑软件规模的可扩充性。

今天只有100人的部门使用的应用程序，明天可能会被有好几万人的组织使用，下月，通过因特网可能会有几百万人使用它。

在软件设计的初期，根据在用例模型中定义的必须支持的基本事务处理，确定软件的基本功能。然后，在建造系统的时候再逐步加入比较常用的功能。

在设计的开始考虑软件的规模需求，避免在用户群突然增大的情况下，重写软件。

12. 性能仅仅是很多设计因素之一

关注软件设计中的一个重要因素--性能，这好象也是用户最关心的事情。一个性能不佳的软件将不可避免被重写。

但是你的设计还必须具有可靠性，可用性，便携性和可扩展性。你应该在工程开始就应该定义并区分好这些因素，以便在工作中恰当使用。性能可以是，也可以不是优先级最高的因素，我的观点是，给每个设计因素应有的考虑。

13. 管理接口

“UML User Guide”（Grady Booch，Ivar Jacobson和Jim Rumbaugh ,Addison Wesley, 1999）中指出，你应该在开发阶段的早期就定义软件模块之间的接口。这有助于你的开发人员全面理解软件的设计结构并取得一致意见，让各模块开发小组相对独立的工作。一旦模块的接口确定之后，模块怎样实现就不是很重要了。从根本上说，如果你不能够定义你的模块“从外部看上去会是什么样子”，你肯定也不清楚模块内要实现什么。

14. 走近路需要更长的时间

在软件开发中没有捷径可以走。

缩短你的在需求分析上花的时间，结果只能是开发出来的软件不能满足用户的需求，必须被重写。

在软件建模上每节省一周，在将来的编码阶段可能会多花几周时间，因为你在全面思考之前就动手写程序。

你为了节省一天的测试时间而漏掉了一个bug，在将来的维护阶段，可能需要花几周甚至几个月的时间去修复。与其如此，还不如重新安排一下项目计划。

避免走捷径，只做一次但要做对（do it once by doing it right）。

15. 别信赖任何人

产品和服务销售公司不是你的朋友，你的大部分员工和高层管理人员也不是。

大部分产品供应商

希望把你牢牢绑在他们的产品上，可能是操作系统，数据库或者某个开发工具。

大部分的顾问和承包商只关心你的钱并不是你的工程（停止向他们付款，看一看他们会在周围呆多长时间）。

大部分程序员认为他们自己比其他人更优秀，他们可能抛弃你设计的模型而用自己认为更好的。

只有良好的沟通才能解决这些问题。

要明确的是，不要只依靠一家产品或服务提供商，即使你的公司（或组织）已经在建模、文档和过程等方面向那个公司投入了很多钱。

16. 证明你的设计在实践中可行

在设计的时候应当先建立一个技术原型， 或者称为“端到端”原型。以证明你的设计是能够工作的。

你应该在开发工作的早期做这些事情，因为，如果软件的设计方案是不可行的，在编码实现阶段无论采取什么措施都于事无补。技术原型将证明你的设计的可行性，从而，你的设计将更容易获得支持。

17. 应用已知的模式

目前，我们有大量现成的分析和设计模式以及问题的解决方案可以使用。

一般来说，好的模型设计和开发人员，都会避免重新设计已经成熟的并被广泛应用的东西。收藏了许多开发模式的信息。

18. 研究每个模型的长处和弱点

目前有很多种类的模型可以使用,如下图所示。用例捕获的是系统行为需求，数据模型则描述支持一个系统运行所需要的数据构成。你可能会试图在用例中加入实际数据描述，但是，这对开发者不是非常有用。同样，数据模型对描述软件需求来说是无用的。每个模型在你建模过程中有其相应的位置，但是，你需要明白在什么地方，什么时候使用它们。

19. 在现有任务中应用多个模型

当你收集需求的时候，考虑使用用例模型，用户界面模型和领域级的类模型。

当你设计软件的时候，应该考虑制作类模型，顺序图、状态图、协作图和最终的软件实际物理模型。

程序设计人员应该慢慢意识到，仅仅使用一个模型而实现的软件要么不能够很好地满足用户的需求，要么很难扩展。

20. 教育你的听众

你花了很大力气建立一个很成熟的系统模型，而你的听众却不能理解它们，甚至更糟－连为什么要先建立模型都不知道。那么你的工作是毫无意义的。

教给你开发人员基本的建模知识；否则，他们会只看看你画的漂亮图表，然后继续编写不规范的程序。

另外， 你还需要告诉你的用户一些需求建模的基础知识。给他们解释你的用例(uses case)和用户界面模型，以使他们能够明白你要表达地东西。当每个人都能使用一个通用的设计语言的时候（比如UML-译者注），你的团队才能实现真正的

合作。

21. 带工具的傻瓜还是傻瓜

你给我CAD/CAM工具，请我设计一座桥。但是，如果那座桥建成的话，我肯定不想当第一个从桥上过的人，因为我对建筑一窍不通。

使用一个很优秀的CASE工具并不能使你成为一个建模专家，只能使你成为一个优秀CASE工具的使用者。成为一个优秀的建模专家需要多年的积累，不会是一周针对某个价值几千美元工具的培训。一个优秀的CASE工具是很重要，但你必须学习使用它，并能够使用它设计它支持的模型。

22. 理解完整的过程

好的设计人员应该理解整个软件过程，尽管他们可能不是精通全部实现细节。

软件开发是一个很复杂的过程，还记得《object-oriented software process》第36页的内容吗？除了编程、建模、测试等你擅长工作外，还有很多工作要做。 好的设计者需要考虑全局。必须从长远考虑如何使软件满足用户需要，如何提供维护和技术支持等。

23. 常做测试，早做测试

如果测试对你的软件来说是无所谓的，那么你的软件多半也没什么必要被开发出来。

建立一个技术原型供技术评审使用，以检验你的软件模型。

在软件生命周期中，越晚发现的错误越难修改，修改成本越昂贵。尽可能早的做测试是很值得的。

24. 把你的工作归档

不值得归档的工作往往也不值得做。归档你的设想，以及根据设想做出的决定；归档软件模型中很重要但不很明显的部分。 给每个模型一些概要描述以使别人很快明白模型所表达的内容。

25. 技术会变，基本原理不会

如果有人说“使用某种开发语言、某个工具或某某技术，我们就不需要再做需求分析，建模，编码或测试”。不要相信，这只说明他还缺乏经验。抛开技术和人的因素，实际上软件开发的基本原理自20世纪70年代以来就没有改变过。你必须还定义需求，建模，编码，测试，配置，面对风险，发布产品，管理工作人员等等。

软件建模技术是需要多年的实际工作才能完全掌握的。好在你可以从我的建议开始，完善你们自己的软件开发经验。

经典IPC问题之

--------理发师理发问题

Company： Bluefox

Author： Y.c.Lee

Document No.Code：[1**********]

Date： 2006-2-8

描述：

理发店里有一个理发师，一把椅子和n把供等待理发的顾客坐的椅子。如果没有顾客上门，理发师就在理发椅上睡觉。

执行过程：

当有个顾客来的时候，他必须先叫醒理发师，如果理发师在理发时，有其他顾客到来，若顾客座位上有空座，他们

就坐下，如果没有就离开。

抽象建模：

Hairdresser

---------------------（Procedure events）--------------------

| |

Working(); sleeping();

Customer

----------------------(Procedure events)---------------------------

| | |

Weekhp() Leave() Waiting()

|

信号量| Work_Seat=0

| | full=0

初始化| Wati_Seat |

| |empty=10

程序实例：

// Customer process procedure

Customer()

{

If ( ! Work_Seat )

{

Weakup(); work_seat++;

}

Else if ( ! wait_seat.empty )

{

Leave();

}

Else

{

Wait();

Full++;

Empty--;

}

}

Hairdressor()

{

If ( work_seat)

{

Working();

Work_seat--;

}

Else

Sleeping();

}

}

经典IPC问题之

--------哲学家进餐问题

描述：

五个哲学家围坐在一个圆桌旁，每个哲学家面前都有一盘通心面，相邻的两个盘子之间有一支筷子（叉子）。

执行过程：

Eating（） and Thinking()。

当一个哲学家觉得饿了，他就试图两次取他面前的筷子，每次一支，不分次序，如果成功获得两把筷子，他就开始吃饭，吃完后放下筷子继续思考。

抽象建模：

方案一：

设Array[]数组存放5把筷子编号1～5;

P ( Array[(i-1]%5] )

P( Array[i%5] )

Eating();

V( Array[i%5] )

V( Array[(i-1%5 )] )

可以实现相邻两个哲学家进餐竞争，但如果在极端情况下，5个哲学家同时拿起一边的筷子，去等另一个筷子时，便会出现死锁，处于饥饿状态。

方案二：

If ( I %2==1 )

{

P(Array[ I %5 ] ) ;

P(Array[ (i-1)%5] ) ;

Eating();

V(Array[ (i-1)%5] ) ;

V(Array[ I %5 ] ) ;

}

Else

{

P(Array[ (i-1)%5] ) ;

P(Array[ I %5 ] ) ;

Eating();

V(Array[ (i-1)%5] ) ;

V(Array[ I %5 ] ) ;

}

软件设计师考试笔记

********************初等部分***************************

关于数据的校验，海明码校验

区位码：将国际码，即ASCII码的码位图分成94个区，每个区分94个位，得

到

区位图，形成的就是区位码。将区位码的区号和位号分别加上160，然后用十六

进制表示就是机内码，即国际码。

设汉字以16*16的点阵输出，则每个汉字所占的空间数为16bit*16bit=32B

两级汉字6763个字符和一些特殊字符要占用更大的存储空间。

磁盘的存储容量=柱面数*磁道数*每道扇区数*每扇区字节数

寻道时间：磁头移动到目标磁道所需的时间

等待时间：找到目标扇区所需时间

数据传输率：找到地址后，单位时间内写入或读取的字节数

磁盘的磁道是一些由中心到边缘的同心圆，所以越中心位密度越大。

Cache通常由较快的静态半导体存储器制成。

读写机制：写通法，写回法，标记法。

淘汰算法：随机淘汰，先进先出算法，最近最少使用算法。

命中率为=Cache的存取次数/Cache和内存加在一起的存取次数

CPU的存储时间=Cache的存取周期*Cache命中率+主存存储周期*命中主存率

注：不命中Cache就会命中主存

囊都文字

总线带宽=（总线位宽/8）*总线工作频率

还要看一个总线周期包含N个时针周期，相应

总线的工作频率=总线时针频率/N

一个机器周期包括4个时钟周期，而执行一个条指令需要三个机器周期。

MIPS代表的是每秒执行的指令数。

进程调度方式：非剥夺方式，剥夺方式。

进程调度算法：先来先服务，优先级调度算法，轮转法，多级反馈调度。

多级反馈就是时间片轮和优先级算法的结合与发展。

进程之间的通信：

同步是指在异步环境中，各进程通过消息发送而进行相互合作，相互等待，使各进程按一定的速度执行。

互斥是为了保证某一临界资源在某一时刻只能被一个进程访问。

临界区的管理原则：有空即进，无空则等，有限等待和让权等待。

进程的控制：

支持功能：中断处理，时钟管理，原语操作。

资源管理功能：进程管理，存储器管理和设备管理。

页面调度算法：先进先出，WIN NT系统使用，最优算法，最近最少使用，最近未用转换算法。

作业调度算法：

单道批量处理：先来先服务，短作业优先，响应比高者优先。

多道批量处理：优先级调度，均衡调度算法。

响应比=（估计运行时间+等待时间）/估计运行时间

内存储器的管理

地址重定位是指将逻辑地址转换为物理地址的过程。

分为静态和动态重定位，即在程序运行前或后完成逻辑地址到物理地址的转换。

分区存储管理：有固定和可变分区存储管理。

分区的保护采用上下界寄存器保护法或基址加限长寄予存器保护法。

并发进程和系统核心

进程是一个静态定义和动态运行相结合的要领具有动态性和并发性。

进程是由程序块，进程控制块PCB和数据块

组成的，程序块是进程的任务，数据块包括数据和工作区，二者构成进程的实体。

PCB进程控制块是进程存在的惟一标志，包括：描述信息，控制信息，资源管理信息和CPU的现场保护信息。

信号量的PV操作，信号量是为了解决进程的同步和互斥而引进的，它是一种核心的数据结构，P表示信号减一，V表示信号加一。且PV操作总是成对出现的。

进程的死锁是指两个以上的进程互相要求对方已经占有的资源导致无法继续运行下去的现象。

进程死锁的四个条件：互斥条件，保持和等待条件，不剥夺条件和环路等待。

处理死锁：不理睬，破坏死锁的四个条件之一，精心地分配资源动态地回避死锁

检测并能解除死锁。

通道技术：专门用于数据传输工作，分为字节多路通道，数组选择通道和数组多路通道。

DMA技术：直接主存存取，是数据直接在IO设备和主存之间的直接成块传送。

缓冲技术：提高外部设备的利用率，分为硬件和软件缓冲。

中断和通道技术使CPU与外设之间的并行操作成为可能，缓冲则解决CPU的高速与外设的低速而实现速度上的匹配。

假脱机技术：简称SPOOLing，它利用多道程序技术，采用一组程序或进程模拟一组输入输出处理操作。如虚拟设备和多窗口技术均是采用假脱机技术。

文件管理：

文件设备块上空闲块的管理方法有三种，索引法，链接法和位图法。

文件控制块FCB是文件存在的惟一标志，其中包含相应文件的基本属性信息

文件控制块的有序集合就是文件目录。

文件安全管理包括系统级，用户级，目录级和文件级的保护。

作业控制：

分为脱机和连机控制两种方式。

一个作业从提交到完成，要经历提交，收容，执行和完成四个状态。

处理机调度通常分为三级，低级，中级和高级调度。

高级调度又称作业调度，任务是为作业建立进程，分配资源。

中级调度又称交换调度，它决定进程在内，外存之间调入调出。

低级调度又叫进程调度，它决定处理机在就绪进程间的分配。

作业的预输入和作业的结果输出由称为假脱机的处理程序专门完成。假脱机处理程序将作业从输入设备输入到称为输入井的处存空间中，输入井中的作业处于后备状态，称它们为后备作业，假脱机处理程序使作业由提交状态变为后备状态。

动态重定位技术可以在执行代码时临时计算出内存地址，装入内存的程序可以在内存或外存中移动。实现虚拟存储技术。

单道程序系统中，主存区域的用户空间全由一个作业进程占用，常不对内存地址进行保护，易引起冲突而使系统瘫痪。

设备分类方法:

按工作特性分，存储设备，输入输出设备。

资

源分配看，独占设备，共享设备和虚拟设备

使用特性分，存储设备，输入输出设备，终端设备以及脱机设备。

从属关系，系统设备和用户设备。

按信息组织方式，字符设备和块设备。块设备如磁盘和磁带。

文件逻辑结构分为两种结构：流式文件和记录式结构两种。

物理结构分为顺序，链接，索引结构三种。

作业已等待的时间/需要执行的时间=响应比

完成时间-到达时间=周转时间

有关数据库应重点加强***************************************

多媒体三个基本特征：集成性，实时性，交互性。

综合处理文本，图形，图像，音频和视频等多媒体信息，使它们建立逻辑连接，

集成为一个交互式的系统。

信号的获取，压缩编码解码技术，实时处理技术和特技，输出技术。

声音的三个指标：音量即响度，单调和音色。

音频信号的获取方式有三种，波形，MIDI，CD音频。

音频信号的数字化，最常用的编码方法是脉冲编码调制技术PCM，PCM分为采样，量化

和编码三个步骤。

数据传输率=采样频率*量化位数*声道数

人的听觉带宽一般为20HZ-20KHZ

数字音频的采样频率为44.1KHZ

任何颜色有仅加入白光会引起饱和度的变化，通常把色调和饱和度称为色度。

饱和度讲某种色彩的颜色深度。

亮度是讲眼睛看上去的明暗程度。

色调是人眼所产生的色彩感觉。

三原色，即红绿蓝，它们的混合可形成任何的颜色，所以说它们是三基色。

256色=2的8次方，则一个256色的每个象素点就要用一个字节八位来表示。

分辨率就是表示有X*Y个象素点表示一个静态的画面。

位图是以象素点的形式表示的

适量图是按数学方式描述出来的几何性质。

VOD系统包括：视频服务器，编码器/路由器，用户请求计算机和记账计算机，机顶盒。

网络七层模型：

物理层

数据链路层

网络层

运输层，叫传输层好听点

会话层

表示层

应用层

衡量网络安全性的五个基本指标是:真实性，保密性，完整性，可用性，实用性和占有性。

常用的网络安全措施有：标志与验证机制，网络访问控制机制，加密机制，信息完整性机制

认证和审计机制。

网络的信息安全技术有：访问控制与目录管理，数据加密技术，身份验证与鉴别。

防火墙是建立在内外网络边界上的过滤封锁机制，认为内部网络是可信的，外面则不可信。

防火墙可分为：过滤防火墙，应用代理防火墙和状态监测防火墙。

防火墙的体系结构：过滤路由器，双宿主主机，屏蔽主机网关和被雪困住屏蔽子网。

网络按交换方式分为线路交换和报文交换，都属于存储转发交换方式。

其中分组交换又分为虚电路交换和数据报，一个

面向连接，一个面向非连接。

ADSL称为非对称数字用户线。有两种方式接入：Modem虚拟拨号和ADSL专线设备。

ISDN称为综合业务数字网，双称一线通。

1000BaseLX是指千兆以太网，它使用单模光纤作为传输介质。

网卡有一个生产时就决定了的六字节MAC地址，并写入到网卡。物理层

机器连入网络后，使用ARP协议可以实现IP地址到MAC地址的动态映射。

中继器是一个转发或重发器。物理层

集线器相当于多端口的网桥。物理层

网桥是在数据链路层把网段相互连接起来。数据链路层

交换机相当于多个网桥。网络层

网关是协议转换器，用来连接不同协议的网络。第四层以上

局域网模型中：数据链路层分为逻辑链路控制子层和网络接口访问控制子层。

ARP协议是一种地址解析协议，它存在于网际层中。

传输层的协议有TCP和UDP两种。

网络协议有三要素：语义，语法和定时也称为记时，包括速度匹配和排序等。

PPP协议叫Point To Point点对点协议，支持动态分配。

N-ISDN为普通用户提供基本速率接口，是2B+D链路，B信道通常用于传送数据，

带宽是64kb/s，D信道用于传送控制信号，带宽是16kb/s。

在特定情况下D信道也可以传送用户数据，所以N-ISDN速度可达144kb/s。

N-ISDN为商业用户提供基群速率接口，是30B+D链路。

因此总通信速率达到2.048Mb/s。

DSL称为数字用户线路Digital Subscriber Line。

程序设计语言的定义一般包括：语法，语义和语用。

一个汇编语句通常划为四个区：标号区，操作码区，操作数区和注解区。

软件开发模型主要有：瀑布模型，演化模型，螺旋模型，喷泉模型和智能模型。

演化模型是在快速开发一个原型的基础上，逐步演化成最终的系统。

螺旋模型则综合了瀑布模型和演化模型的优点并增加了风险分析。

软件工程中描述生命周期的瀑布模型一般包括：计划，需求分析，软件设计，

编码测试及维护几个阶段。

软件设计阶段通常又可以分为概要设计和详细设计两步。

软件工程技术应该遵循分解，一致性，确定性及抽象和信息隐蔽的原则。

软件计划阶段应该依次完成系统定义，软件计划和需求分析的任务。

可行性研究包括：技术可行性，经济可行性，法律可行性以及社会可行性。

软件开发环境对软件产品的开发提供了支持，包括：

软件开发工具可细分为，需求分析工具，设计工具和编码与排错工具。

集成软件开发环境：数据集成，界面集成，控制集成，过程集成和平台集成。

在数据流图中，箭头表示数据流，圆圈表示加工，用方框表示源/宿

用双横线上的进入及离开箭头表示数据存储。

模块独立性要追求低耦合，按耦合

度从低到高可分为：

非直接耦合，两模块任何一个都不信赖另一模块

数据耦合，利用参数表在模块间传递数据

标记耦合，当一个数据的一部分借助于模块接口被传递

控制耦合，传递的信息中包含用于控制模块命令逻辑的控制信息

外部耦合，当模块与软件以外的环境有关时就发生

公共耦合，多个模块引用同一全局数据区的模式

内容耦合，直接访问另一模块的内部数据，或不通过正常入口转到另一个模块内部

或一个模块有多个入口。

模块的内聚性由低到高分为七种类型：

偶然，逻辑，瞬时，过程，通信，信息，功能内聚。

软件语言主要包括：需求定义语言，功能性语言，设计语言，程序设计语言和文档语言。

程序设计语言基本成份有四种：数据成分，运算成分，控制成分和传输成分。

我国已建立的各种标准有：基础标准，开发标准，文档标准，管理标准。

软件的维护分为以下几种：校正性维护，适应性维护，完善性维护，预防性维护。

较全面地评价一个软件质量应从以下几方面入手：

易维护性，可靠性，效率和易理解性（即可读性），易移植性，正确性。规范性。

软件可靠性是指程序在给定的时间间隔内，按照规格说明书的规定成功地实现其功能的概率

堆和栈的区别：

栈是程序的代码区，在内存中地址向低地址扩展，是连续的

堆向高地址扩展，不是连续的。堆的效率慢，易产生碎片。

*******************初等部分结束****************************

码距是指有一个编码系统中任意两个合法编码之间至少有多少个二进制位不同，

码距为一的编码是不能发现错误的。

冗余校验：冗余校验码合法码字集的压码距为2D+1，则它能发现2D错位，并能纠正D位错。

8421码是非冗余的，因此不能检错，查错。

海明校验码，也是利用奇偶性来纠错。通过在数据之间插入K个校验位，扩大数据的编码

的码距。有能力检测出N位错，并能纠正1位或N位错，K必须满足2K-1

指令流：机器执行的指令序列。

数据流：由指令流调用的数据序列，包括输入数据和中间结果。

多倍性：在系统性能瓶颈部件上同时处于同一执行阶段的指令或数据的最大可能个数。

单指令流单数据流SISD

单指令流多数据流SIMD

多指令流单数据流MISD

多指令流多数据流MIMD

相联存储器的访问方式是按内容访问。

非格式化容量=最大化密度*最内圈周长*总磁道数

并行：分时同时性和并发性

资源重复，资源共享，时间重叠

列阵处理机即并行处理机，表示并发关系并可对其控制。

加密和解密三性，可逆，密钥安全，数据安全

秘密密钥加密体制DES

公开密钥加密体制RSA

专作备份用，一旦出现问题就可以巴切换称为热备份

平时做其它用，但一碰到服务器出现问题就可以马上切换过来，称做双工系统，兼职性

CRC检错编码

是一种循环冗余校验码

原理：收到一个CRC码，生成式除CRC码，余数是0则正确，

可发现并纠正一位错，可检测小于等于校验位长度的突发错。

逻辑移位，算术移位，除法移位

除法移位的方法，符号位不变，相邻位依次移入到高位，将高位溢出的一们填到最低位。

乘法向左移即可。

相对寻址方式：程序计数器的内容 加上 指令形式的地址项。

注意虚拟存储是按内容寻址的。

RISC啬了编译后的指令数，每个机器周期未变。

程序计数器PC的作用是使CPU在完成中断后能回到中断点断续以前的工作。

完成一个MOV操作，首先要做是将PC读到地址段寄存器

分时操作系统是一种多用户的系统。

WINDOWS是单用户多任务的操作系统。

动态分配资源才可能形成回路。

操作系统的特征：

并发性，从宏观上说

共享性，系统资源对于多个进程是共性的

虚拟性，将一个物理实体变成若干个逻辑上的对应物。

异步性，即程序的走走停停，但只要运行环境相同，总会得到相同的结果。

操作系统的分类

批处理，分时，实时，网络，分布式。

实时操作系统的特点

外部中断处理，在线人机对话，超负荷保护，时钟管理。

产生死锁的原因：

竞争资源，进程推进顺序不当。

产生死锁的必要条件：

互斥条件

请示和保持条件

不剥夺条件

一路等待条件

处理死锁的基本方法：

预防，避免，检测，解除

spooling系统

解决CPU和低速外设的一种脱机技术，将数据到外存中进行暂存。

前驱图是一个有向无循环图，还有间接前驱图。

虚拟存储是基于程序的局部性实现的。

内外存之间交换信息的基本单位有两种,一种是以作业为单位，称为SWAPPING技术

它要求作业的地址空间要小于或等于内存的可用空间，另一种交换技术是在作业内部做

部分住处的调入调出，通常将作业地址空间分页或分段，以交换段或页称为虚拟存储。

工作集是一个进程在定长的执行时间区间内涉及到的页面集合。

存储分配方法有如下几种：

固定分区分配，支持多道程序设计，易产生碎片。

单一连续分区分配，不支持多道程序设计，内存中仅驻留一道程序。

可重定位分获分配，采用拼接技术，克服固定分区的碎片问题，能将小分区拼接成大

分区，还能够整理存储器内各个作业的存储位置，以达到消除存储碎片和紧缩存储

空间的目的。

页式存储管理，系统将一个进程的逻辑窨分为若干大小相等的页面，把内存空间也分成

与页

面大小相同的若干个存储块，称为物理块或页框，并建立编号和映射关系，分页存

储管理分为请求分页和非请求分页存储管理。非请求的不支持虚拟存储管理。

请求式，即程序将要用到某个页才将其调入内存。

文件类型：

按用途分类，系统文件，用户文件，库文件

按文件中的数据，源文件，目标文件，可招待文件。

按存取控制属性，可执行文件，只读文件，读写文件。

按文件的逻辑结构，有结构文件也称记录式文件和无结构文件。

按文件的物理结构分，顺序文件，链接文件，索引文件。

文件系统的功能：按名存取是其特征

对文件存空间的管理

对文件目录的管理

地址映射

文件的读，写管理

文件的共享与保护。

直接文件，又称为哈希文件，记录以它们在直接的物理地址来进行直接访问。

IO设备

按住处交换的单位分，块设备和字符设备。

按设备的共享属性分，独占设备，共享设备，虚拟设备

按速度分，低中高速设备。

制备控制器是CPU和IO设备的接口，它接收从CPU发出的命令，并控制IO设备工作。

设备控制器分为控制字符和控制块设备的控制器。

设备控制器的功能：

接收和识别命令，数据交换（CPU与控制器之间，控制器与设备之间）。

设备状态的了解和报告，地址识别。

主要的设备管理技术

中断技术，通道技术，缓冲技术。

数据传输控制方式，除以上三种控制外还加程序控制方式。

螺旋模型是在瀑布模型和演化模型的基础上加上风险分析所建立的一种软件开发模型。

数据流与加工的关系。*表示想邻的一对数据流同时出现，注意入加工与出加工不同。

DFD用来描述数据流从输入到输出的变换流程，是一种面向数据流的分析方法的图形描

述工具，思想是自顶向下逐层分解，一个父图可以N个子图，但每个子图仅有一个父图。

任意两个加工之间可有0或多条名字互不相同的数据流。

信息流分为两种，变换流和事务流。DFD图可明显地分成输入，变换和输出三大部分。

事务流有一个明显的事务中心。

原型化方法特征加快需求的确定。

与结构化方法相比它更需要完整的生命周期。

衡量原形开发人员能力的重要标准是快速获取需求。

软件设计原则：抽象，模块化，信息隐蔽，模块独立。

模块之间的耦合度从低到高：

非直接，数据，标记，控制，外部，公共，内容耦合。

模块内聚由低到高：

偶然，逻辑，瞬时，过程，通信，顺序，功能内聚。

软件设计包括四个独立又相互联系的活动：

体系结构设计，接口设计，数据设计和过程设计。

将都要用到的一些代码放到一个模块内称为偶然内聚。

逻辑

上相似的成分放在一个模块中，称为逻辑内聚。

模块中所有成分的输入是另一些成分的输入，称为通信内聚。

模块中的某成分的输入是另一些成分的输入，为顺序内聚。

模块中所有成分结合起来完成一项任务，是功能性内聚。

一个模块把开关量作为参数传给另一个模块称为控制耦合

一个模块把一个数值量作为参数传递给另一模块称为数据耦合。

结构化设计方法在软件开发中用于概要设计。

是一种面向数据流的设计方法。使用的图形程序结构图。

如果两矩形之间有直线相连，表示它们存在调用关系。

如何定义大小合适的模块，五个标准：

模块可分解性，模块可组装性，可理解性，连续性，模块保护。

常用的白盒测试技术

语句覆盖，判定覆盖，条件覆盖，判定条件覆盖，条件组合覆盖，路径覆盖。

黑盒测试技术

等价类划分，边界值分析，错误猜测，因果图。

测试步骤

单元测试，集成测试，确认测试。

alpha测试是由一个用户在开发者在场所进行的，开发者并对其进行指导。

beta测试是由软件的最终用户在正常使用的情况下一个或多个场所来进行的，通常

开发者不在现场。

软件集成测试最好由不属于该软件开发组的软件设计人员。

单元测试在实现阶段，测试方案应在详细设计阶段完成。

集成测试所依据的模块说明书和测试方案应在概要设计阶段完成，它能发现设计错误。

确认测试应在模拟的环境中进行强度测试的基础上进行，测试计划应在软件需求分析

阶段完成。

黑盒测试最常用边界值测试法

对于测试用例应尽可以地覆盖尚未被覆盖的有效等价类。

测试用例一次只能覆盖一个尚未被覆盖的无效等价类。

因果图是根据输入和输出之间的因果关系来设计测试用例的。

对查出来的错误修正后再次测试称为回归测试。

软件维护的分类：

改正性，适应性，完善性，预防性维护等。

可维护性是指理解，改正，改动，改进软件的难易程度。

质量认证也称为合格评定。

按谁的对象分为新产品质量认证和质量体系认证两类。

按认证的作用可以分为安全认证和合格认证。

软件可移植性是衡量软件质量的一个重要尺度。

应提高软件的设备独立性，采用表格驱动方式有助于提高设备独立性。

C语言的移植性较好。

面向对象主要特征：

封装，继承，多态。

通用多态有参数多态和包含多态两种。

特定多态有过载多态和强制多态两种。

包含多态最常见的例子就是子类型化，即一个类型是另一类型的子类型。

过载多态是同一变量用来表示不同的功能，通过上下以决定一个名所代表的功能。

可靠性，可维护性，

可移植性，可复用性是较为重要的质量特征。

为确保质量，在软件开发中必须采取有力的措施：

在开发初期制定质量保证计划，并在开发中坚持执行。

严格执行阶段评审。

开发前选定或制定开发标准或开发规范，并遵照实施。

JACKSON提出结构化程序设计，它是一种面向数据结构的设计方法，主要适应于规模

适中的数据处理系统的开发，基本步骤为：

建立数据结构，建立程序结构，列出基本操作。

在一项软件开发的过程中，一般有十四种文件.....

管理人员使用：项目开发设计，开发性研究报告，模块开发卷宗，开发进度月报

项目开发总结报告。

开发人员使用：项目开发设计，开发性研究报告，软件需求说明书，数据要求说明书

概要设计说明书，详细设计说明书，数据库设计说明书，测试计划

和测试分析报告。

维护人员使用：设计说明书，测试分析报告，模块开发卷宗。

确认测试的计划在需求分析时制订。

组装测试的计划在概要设计时制订。

单元测试是在实现阶段完成的。

在软件工程的的设计阶段常用的三种设计方法：

结构化设计SD法，JACKSON方法和PARNAS方法。分别侧重于：

模块要相对独立且功能单一，高内聚，低耦合。

由数据结构导出模块结构。

将可能引起变化的因素隐藏在某有关模块内部，使这些因素变化时的影响范围受到限制。

SD法最常用，PARNAS法只提供了重要的设计准则，没有规定出具体的工作步骤。

最强的覆盖标准是路径覆盖。

完善性维护是为了扩充软件的功能或提高原有软件的性能而进行的维护活动。

健壮性是指当系统万一遇到未预料到的情况，系统能做适当的自动处理。

风险主要的主要三概念是：关心未来，关心变化，关心选择。

项目风险关系着项目计划的成败，商业风险关系着软件的生存能力。

风险活动是建立表示风险概率的尺度，描述风险引起的后果，估计风险影响的大小。

软件的互操作性是指连接一个系统和另一个系统所需的工作量。

信息处理器利用住处系统提供的信息进行决策和选择，是信息系统服务的对象。

面向对象中类属是一种参数多态机制，它强调的是这些类的成员特征中与具体类型

无关的那些部分，而变元用来表示具体类型相关的那些部分。

面向对象可分为四个层次，由低到高是：

算法层，类层，模板层，系统层。

当用户的数据资源缺乏组织和管理时不能使用快速原型法进行开发。

●在数据压缩编码的应用中，哈夫曼（Huffman）算法可以用来构造具有__最优前缀码__的二叉树，这是一种采用了_贪心__的算法。

声音的三要素为音调、音强和音色，其

中音色是由混入基音的__泛音__决定的

多媒体应用需要对庞大的数据进行压缩，常见的压缩编码方法可分为两大类，一类是无损压缩法，另一类是有损压缩法，也称__熵压缩法__。__Huffman编码__属于无损压缩法。

◆第一代的计算机网络实际上是指以单台计算机为中心的远程联机系统，也称之为面向终端的计算机通信网络

◆第二代的计算机网络简称为计算机—计算机网络，它把一个计算机网络分成“通信子网”和“资源子网”两大部分

◆第三代网络指的是开放式标准化的网络，目前存在着两种占主导地位的网络体系结构TCP/IP和OSI体系结构

◆第四代网络是目前正在探讨与发展中的网络结构

计算机网络具备3大基本功能：

? 通信交往，即计算机用户之间的相互通信与交往

? 共享资源，包括硬件资源、软件资源、数据与信息资源

? 协同工作，即计算机之间或计算机用户之间的协同工作

数据交换一般有3中基本方式

? 电路交换

? 报文交换

? 分组交换

Internet提供的服务有：

? 远程登录telnet——TELNET协议

? 文件传输ftp——FTP协议

? 电子邮件E-mail——SNMP协议

? 网络新闻news——NNTP协议

? 以菜单方式浏览信息Gopher

? 按内容自动查找WAIS

? 全球范围的超媒体信息浏览服务WWW

Internet采用的是TCP/IP体系结构网络协议，加入Internet的任何网络都必须支持TCP/IP，即在互联网层采用IP协议，在传输层采用TCP（或UDP）协议。Internet的应用层协议很多，常见的有：

? TELNET远程登录协议

? FTP文件传输协议

? SMTP简单邮件传输协议

? DNS域名服务协议

? NSP名字服务协议

? HTTP超文本传输协议

? SNMP简单网络管理协议

数据库的三种模型：层次，网状，关系型。

数据库系统结构分为三级：

用户级，用户视图，局部视图，外模式

概念级，全书视图，模式

物理级，存储视图，内模式

应定义相隔两层的映射关系。

存储模式的改变不能影响概念模式也改变。

实体模型和ER图，1 ：1，1 : N, N : M

实体用矩形表示，实体属性用椭圆表示，实体间的联系用棱形表示。

数据模型有两种：

概念数据模型，简称概念模型

基本数据模型，简称数据模型

数据模型通常由数据结构，数据操作和数据完整性约束三部分组成。

层次模型：有且仅有一个无双亲的根结点。

基他结点有且只有一个双亲。

网状模型：中有多个结点无双亲结点，可有多个双亲结点，允许两结点间有多种联系。

关系模型：

一个二维表就是一个关系。

在关系数据库中，二维表中的一行

称为一个记录，表的列称为字段，表格称为数据表。

在关系模型中，二维表称为关系，表中的一行称为元组，其列称为属性，属性的取值

范围称为域。

关系代数：

并运算，即两个有着相同属性的表，连接起来

差运算，即在A表中有，但B表中没有的记录。

交运算，在两个表中均有的记录。

笛卡尔积，将A表中的每一记录与B表中的每一记录组合，即将表的连接，行全排列。

投影运算，选取某些属性即列，重新排列，最后删除相同的元组。

选择运算，即将某性属性符合条件的列选择出来，可用比较运算，逻辑运算。

连接运算，在笛卡尔积中找出某些符合条件的元组。

连接有两种最常用，等值连接和自然连接，

自然连接是特殊的等值连接，它要求两个关系中进行比较的两分量必须是相同的

属性组，并且在结果中把重复的属性列去掉。在两个关系没有公共属性的情况下

自然连接就是笛卡尔积。

除法运算，除法运算可理解为笛卡尔积的逆运算。R/S

将R关系中，符合S中的任意记录的元组通通去掉，并且关于S的列全部去掉。

函数依赖与规范化

函数依赖，即X->Y，表示Y依赖于X，即一个X总能找到一个与之对应的Y。相当于X是主键

完全函数依赖f，即像上一样，Y的决定是由一个属性组合决定的。

部分函数依赖p，假设有一个属性的组合，但Y的决定只需要组合里的非全部就能决定。

传递函数依赖t,X->Y,Y->Z,则X->Z

关键字又称关键码，包含在任何一个关键字中的属性称为主属性，由完全函数依赖而来。

若在一个关系中不是关键字，但在另一个关系模式中是关键字，则它称为外部码，即外键。

规范化，即所说的各种范式，从一到四范式。

若无重复组，所有域为单纯域，所有属性不可再分则称为第一范式，1NF.

一范式的问题：插入异常，删除异常，数据冗余大，修改复杂。

第二范式，在一范式的基础上，且每个非主属性完全函数依赖于关键码。

第三范式，在二范式的基础上，且没有一个非主属性是完全函数信赖于其他的非关键字属性。

第四范式，在三范式的基础上，且没有非平凡且非函数依赖的多值依赖。

当需求不明时用原型法开发

一个二元关系是自反的,对称的和传递的则它是等价关系.

若将对称改为反对称则它是偏序关系。

奇偶校验只能发现一位或奇数位错，但不能纠正错误，一般以字节为单位加奇偶校验。

海明码是一种多重复式奇偶校验系统，信息加奇偶校验位构成，每个这种校验位在舆码字

的特定位置上，系统能分离错误位。

对偶式：将加和乘交换，1和0交换，原运算符的顺序不变。

反函数：在对偶式的

基础上，将原变量与反变量交换，即是原变量的变成反变量。

查找树中，根结点到其它结点的路径长度总和称为内部路径长度，如果使它最小，则称此

树为丰满树，对丰满树进行任何插入和删除都将使它变非丰满树。

2. 设R=ABCD,R上的F={A→C，D→C，BD→A}, 试证明ρ={AB,ACD,BCD}相对于F不是无损联接分解。

根据算法4.2

　 A B C D

AB a1 a2 b13 b14

ACD a1 b22 a3 a4

BCD b31 a2 a3 a4

A B C D

a1 a2 a3 b14

a1 b22 a3 a4

b31 a2 a3 a4

(1) 构造表 (2)根据A→C，D→C，BD→A进行处理

没有一行都是a，所以，ρ相对于F不是无损联接分解。

4.6 试分析下列分解是否具有无损联接和保持函数依赖的特点：

(1)设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。

首先，检查是否具有无损联接特点：

第1种解法--算法4.2:

　

A

B

C

AB

a1

a2

b13

AC

a1

b22

a3

A

B

C

a1

a2

b13

a1

a2

a3

(1) 构造表

(2)根据A→B进行处理

结果第二行全是a行，因此分解是无损联接分解。

第2种解法:(定理4.8)

设 R1=AB，R2=AC

　　R1∩R2=A

　　R2- R1=B

　　∵A→B,∴该分解是无损联接分解。

然后，检查分解是否保持函数依赖

　　πR1（F1）={A→B，以及按自反率推出的一些函数依赖}

　　πR2（F1）={按自反率推出的一些函数依赖}

　　F1被πR1（F1）所蕴涵，∴所以该分解保持函数依赖。

软件设计师考试复习笔记：几个必须掌握的公式

1、计算cache命中率的相关题型。

公式：Ta = hT缓＋（1－h)T主，即平均访存时间＝命中率×访问缓存时间＋（1－命中率）×访问主存时间

例题：某流水线计算机主存的读写时间100ns，有一指令和数据合一的cache，已知该cache的读写时间为10ns，取指命中率为98%,取指命中率为95％，在执行某类程序时，约有1/5指令需要存取操作数。假设指令流水线在任何时候都不堵塞，则设置cache后，每条指令的平均访存时间约为多少。

本人解题：无需取操作数情况：ta1=4/5*(0.02*100+0.98*10)＝9.44 ；取操作数情况：ta2=1/5*(0.02*100+0.98*10+0.05+100+0.95*10)=5.26 所以：平均访存时间＝ta1+ta2=9.44+5.26 = 14.7

2、计算流水线计算机的吞吐率

公式：T取指+max(T取指，T分析)+max(T取指，T分析,t执行）×（N-2)+MAX(T分析,执行)+t执行

在流水执行过程中，首先要取指，这个时间排第一，然后是看分析先完成还是取指先完成，取后完成的时间，再加上三个步骤中最长的时间乘要执行的指令数－2，要减去2是因为要把第一条跟最后一条指令单独计算。最后加最后一条指令的执行。

3、硬盘的格式化容量与非格式化容量的计算：

非格式化容量：以位密度为单位。＝最大

位密度×最内圈周长×总磁道数

格式化容量：以扇区容量为标准。＝每道扇区数×扇区容量×总磁道数

以上是第一章比较重要的公式了。