2005年软件设计师试题分析与解答

2005上半年软件设计师级上午试题分析与解答

试题（1）、（2）

在计算机中，最适合进行数字加减运算的数字编码是 （1） ，最适合表示浮点数阶码的数字编码是 （2） 。

（1）A．原码 ．反码 ．补码 ．移码

（2）A．原码  ．反码 ．补码 ．移码

试题（1）、（2）分析

在计算机的CPU中，通常只设置硬件加法器。只有补码能够将减法转化为加法，故用硬件加法器可以较方便地进行数字加减法。

由于正数的移码大于负数的移码，利用这一特点，移码被广泛用来表示浮点数阶码的数字编码，这可以用比较阶码的大小来实现真值大小的比较。

参

（1）C  （2）D  

试题（3）

如果主存容量为16M字节，且按字节编址，表示该主存地址至少应需要 （3） 位。

（3）A．16 ．20 ．24 ．32

试题（3）分析

用二进制编码表示地址，16M字节地址最少需要24位。

参

（3）C

试题（4）～（6）

操作数所处的位置，可以决定指令的寻址方式。操作数包含在指令中，寻址方式为 （4） ；操作数在寄存器中，寻址方式为 （5） ；操作数的地址在寄存器中，寻址方式为 （6） 。

（4）A．立即寻址  ．直接寻址

 ．寄存器寻址  ．寄存器间接寻址 

（5）A．立即寻址  ．相对寻址

 ．寄存器寻址  ．寄存器间接寻址 

（6）A．相对寻址  ．直接寻址

 ．寄存器寻址  ．寄存器间接寻址 

试题（4）～（6）分析

操作数包含在指令中的寻址方式为立即寻址；操作数在寄存器中的寻址方式为寄存器寻址；操作数的地址在寄存器中的寻址方式为寄存器间接寻址。

参

（4）A  （5）C  （6）D

试题（7）

三个可靠度R均为0.8的部件串联构成一个系统，如下图所示：

则该系统的可靠度为 （7） 。

（7）A．0.240 ．0.512 ．0.800 ．0.992

试题（7）分析

本题中由三个部件串联构成系统，三个部件中任何一个部件失效就足以使系统失效。串联系统的可靠度RS=R×R×R=0.8×0.8×0.8=0.512。

参

（7）B

试题（8）

在计算机系统中，构成虚拟存储器 （8） 。

（8）A．只需要一定的硬件资源便可实现 ．只需要一定的软件即可实现

 ．既需要软件也需要硬件方可实现 ．既不需要软件也不需要硬件

试题（8）分析

在计算机系统中，构成虚拟存储器，既需要硬件，如大容量的外部存储器（硬磁盘）及一定容量的主存储器，同时还需要必要的管理软件，能够对虚拟存储器进行管理。只有这样才能实现虚拟存储器。

参

（8）C

试题（9）

某公司使用包过滤防火墙控制进出公司局域网的数据，在不考虑使用代理服务器的情况下，下面描述错误的是“该防火墙能够  （9）  ”。

（9）A．使公司员工只能访问Internet上与其有业务联系的公司的IP地址

 ．仅允许HTTP协议通过

 ．使员工不能直接访问FTP服务端口号为21的FTP服务

 ．仅允许公司中具有某些特定IP地址的计算机可以访问外部网络

试题（9）分析

考点：考查包过滤防火墙的基础知识，尤其是它所工作的协议栈层次。

包过滤防火墙通常直接转发报文，它对用户完全透明，速度较快。包过滤防火墙一般有一个包检查模块（通常称为包过滤器），数据包过滤可以根据数据包中的各项信息来控制站点与站点、站点与网络、网络与网络之间的相互访问，但无法控制传输数据的内容，因为内容是应用层数据，而包过滤器处在传输层和网络层。无论是源IP地址还是目的IP地址，都是网络层的IP地址，都在包过滤防火墙的控制范围内，因此，通过配置目的IP和源IP，可以实现A和D。默认情况下，FTP协议开放的端口号是21，它是传输层的TCP协议的端口号。因此，虽然FTP是应用层协议，但是通过包过滤防火墙TCP端口号，可以实现C。HTTP协议是超文本传输协议，它是应用层协议，包过滤防火墙无法实现对应用层协议的，所以无法实现B。

参

（9）B

试题（10）、（11）

两个公司希望通过Internet进行安全通信，保证从信息源到目的地之间的数据传输以密文形式出现，而且公司不希望由于在传输节点使用特殊的安全单元而增加开支，最合适的加密方式是 （10） ，使用的会话密钥算法应该是 （11） 。

（10）A．链路加密 B．节点加密 ．端-端加密 ．混合加密

（11）A．RSA ．RC-5 ．MD5 ．ECC

试题（10）、（11）分析

考点：考查信息的传输加密中有关链路加密、节点加密和端–端加密的特性，同时，也考查对常用密码算法特点及其使用范围的掌握情况。

链路加密只对两个节点之间（不含信息源和目的地两个端点本身）的通信信道线路上所传输的信息进行加密保护，但是在传输过程中经过每个节点时，节点中的数据是明文。节点加密的加解密都在节点中进行，即每个节点里装有加解密保护装置，用于完成一个密钥向另一个密钥的转换。节点中虽然不会出现明文，但是需要在经过的每个节点加装保护装置，这不仅不方便使用，而且会增加开支。端-端加密为系统提供从信息源到目的地传送数据的加密保护，不需要在通信节点上增加额外的安全单元，而且能够保证数据自始至终以密文形式出现，即使在节点中也是密文。

RC-5是对称密码，加解密都使用相同的密钥，加密效率高，适合于加密大量的数据。RSA和ECC是非对称密码，加解密使用不同的密钥（公钥和私钥），它们对计算资源的消耗较大，适合于加密非常少量的数据，例如加密会话密钥。MD5可以用于生成数字摘要。

参

（10）C  （11）B

试题（12）

我国著作权法中， （12）  系指同一概念。

（12）A．出版权与版权 ．著作权与版权  

 ．作者权与专有权 ．发行权与版权

试题（12）分析

我国著作权法第五十六条中指出：“本法所称的著作权即版权。”

参

（12）B

试题（13）

由我国信息产业部批准发布，在信息产业部门范围内统一使用的标准，称为 （13） 。

（13）A．地方标准 ．部门标准 ．行业标准 ．企业标准

试题（13）分析

根据标准制定的机构和标准适用的范围有所不同，标准可分为国际标准、国家标准、行业标准、企业（机构）标准及项目（课题）标准。由有关行政主管部门制定并报标准化行政主管部门备案的标准，称为行业标准。我国信息产业部属我国行政主管部门，其批准发布标准在信息行业范围内为行业统一的标准。

参

（13）C

试题（14）

某软件设计师自行将他人使用C程序语言开发的控制程序转换为机器语言形式的控制程序，并固化在芯片中，该软件设计师的行为 （14） 。

（14）A．不构成侵权，因为新的控制程序与原控制程序使用的程序设计语言不同

 ．不构成侵权，因为对原控制程序进行了转换与固化，其使用和表现形式不同

 ．不构成侵权，将一种程序语言编写的源程序转换为另一种程序语言形式，

   属于一种“翻译”行为

 ．构成侵权，因为他不享有原软件作品的著作权

试题（14）分析

计算机软件著作权的客体是指著作权法保护的计算机软件著作权的范围（受保护的对象）。著作权法保护的计算机软件是指计算机程序（源程序和目标程序）及其有关文档（程序设计说明书、流程图、用户手册等）。该设计师自行（未经许可）使用他人使用C程序语言开发的软件的行为属于侵权行为。

参

（14）D

试题（15）、（16）

数据存储在磁盘上的排列方式会影响I/O服务的总时间。假设每磁道划分成10个物理块，每块存放1个逻辑记录。逻辑记录R1，R2，…，R10存放在同一个磁道上，记录的安排顺序如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10
逻辑记录	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10

假定磁盘的旋转速度为20ms/周，磁头当前处在R1的开始处。若系统顺序处理这些记录，使用单缓冲区，每个记录处理时间为4ms，则处理这10个记录的最长时间为 （15） ；若对信息存储进行优化分布后，处理10个记录的最少时间为

 （16） 。

（15）A．180ms     B．200ms    C．204ms    D．220ms

（16）A．40ms      B．60ms     C．100ms     D．160ms

试题（15）、（16）分析

系统读记录的时间为20/10=2ms。对第一种情况：系统读出并处理记录R1之后，将转到记录R4的开始处，所以为了读出记录R2，磁盘必须再转一圈，需要2ms（读记录）加20ms（转一圈）的时间。这样，处理10个记录的总时间应为处理前9个记录（即R1，R2，…，R9）的总时间再加上读R10和处理时间（9×22ms+ 6ms=204ms）。

对于第二种情况，若对信息进行分布优化的结果如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10
逻辑记录	R1	R8	R5	R2	R9	R6	R3	R10	R7	R4

从上表可以看出，当读出记录R1并处理结束后，磁头刚好转至R2记录的开始处，立即就可以读出并处理，因此处理10个记录的总时间为：

10×（2ms（读记录）+4ms（处理记录））=10×6ms=60ms

参

（15）C  （16）B

试题（17）

页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K，地址变换过程如下图所示，图中逻辑地址用十进制表示。

图中有效地址经过变换后，十进制物理地址a应为 （17） 。

（17）A．33220 ．84 ．4548 ．2500

试题（17）分析

本题考查的是页式存储管理中的地址变换知识。在页式存储管理中，有效地址除页的大小，取整为页号，取余为页内地址。本题页面的大小为4K，有效地址84除4096，取整为2，取余为452。我们先查页表得物理块号8，因此a的有效地址为8×4096+452= 33220。

参

（17）A  

试题（18）

下列叙述中，与提高软件可移植性相关的是 （18） 。

（18）A．选择时间效率高的算法

 ．尽可能减少注释

 ．选择空间效率高的算法

     D．尽量用高级语言编写系统中对效率要求不高的部分

试题（18）分析

软件可移植性是指与软件可从某一环境移植到另一环境的能力有关的一组属性。高级语言具有较好的可移植性，所以可以尽量用高级语言编写系统中对效率要求不高的部分。减少注释、选择时间/空间效率高的算法都不能提高软件的可移植性。

参

（18）D

试题（19）、（20）

在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统代替旧系统的策略称为 （19） ；在新系统全部正式运行前，一部分一部分地代替旧系统的策略称为 （20） 。

（19）A．直接转换    B．位置转换    C．分段转换    D．并行转换

（20）A．直接转换    B．位置转换    C．分段转换    D．并行转换

试题（19）、（20）分析

新系统试运行成功之后，就可以在新系统和旧系统之间互相转换。新旧系统之间的转换方式有直接转换、并行转换和分段转换。

直接转换。直接转换就是在确定新系统运行无误时，立刻启用新系统，终止旧系统运行。这种方式对人员、设备费用很节省。这种方式一般适用于一些处理过程不太复杂，数据不太重要的场合。

并行转换。这种转换方式是新旧系统并行工作一段时间，经过一段时间的考验以后，新系统正式替代旧系统。对于较复杂的大型系统，它提供了一个与旧系统运行结果进行比较的机会，可以对新旧两个系统的时间要求、出错次数和工作效率给以公正的评价。当然由于与旧系统并行工作，消除了尚未认识新系统之前的紧张和不安。在银行、财务和一些企业的核心系统中，这是一种经常使用的转换方式。它的主要特点是安全、可靠，但费用和工作量都很大，因为在相当长时间内系统要两套班子并行工作。

分段转换。分段转换又称逐步转换、向导转换、试点过渡法等。这种转换方式实际上是以上两种转换方式的结合。在新系统全部正式运行前，一部分一部分地代替旧系统。那些在转换过程中还没有正式运行的部分，可以在一个模拟环境中继续试运行。这种方式既保证了可靠性，又不至于费用太大。但是这种分段转换要求子系统之间有一定的性，对系统的设计和实现都有一定的要求，否则就无法实现这种分段转换的设想。

参

（19）D  （20）C

试题（21）、（22）

下列要素中，不属于DFD的是 （21） 。当使用DFD对一个工资系统进行建模时，

 （22） 可以被认定为外部实体。

（21）A．加工    B．数据流    C．数据存储    D．联系

（22）A．接收工资单的银行 ．工资系统源代码程序

 ．工资单  ．工资数据库的维护

试题（21）、（22）分析

数据流图或称数据流程图（Data Flow Diagram，DFD）是一种便于用户理解、分析系统数据流程的图形工具。它摆脱了系统的物理内容，精确地在逻辑上描述系统的功能、输入、输出和数据存储等，是系统逻辑模型的重要组成部分。

DFD由数据流、加工、数据存储和外部实体4个要素构成。外部实体是指存在于软件系统之外的人员或组织，它指出系统所需数据的发源地和系统所产生数据的归宿地。因此选项B、C、D都不符合外部实体的定义。

参

（21）D  （22）A

试题（23）、（24）

在系统验收测试中， （23） 是在一个模拟的环境下使用模拟数据运行系统；

 （24） 是在一个实际环境中使用真实数据运行系统。

（23）A．验证测试  ．审计测试 ．确认测试 ．模块测试

（24）A．验证测试 ．审计测试 C．确认测试 ．模块测试

试题（23）、（24）分析

系统验收测试是最终用户使用真实数据一段时间后进行的最终系统测试，它给最终用户、管理人员和信息系统操作管理人员最后一次机会决定接收或者拒绝系统。系统验收测试是一种详细测试，涉及3个层面的验收测试：验证测试、确认测试和审计测试。

∙验证测试是在一个模拟环境下使用模拟数据运行系统，它主要寻找错误和遗漏。

∙确认测试在一个实际环境中使用真实数据运行系统。在确认测试过程中，可以测试系统性能、峰值负载处理性能、方法和程序测试、备份和恢复测试等。

∙审计测试证实系统没有错误并准备好了可以运行。

参

（23）A  （24）C

试题（25）

采用瀑布模型进行系统开发的过程中，每个阶段都会产生不同的文档。以下关于产生这些文档的描述中，正确的是 （25） 。

（25）A．外部设计评审报告在概要设计阶段产生

  B．集成测试计划在程序设计阶段产生

      C．系统计划和需求说明在详细设计阶段产生

  D．在进行编码的同时，的设计单元测试计划

试题（25）分析

在采用瀑布模型进行系统开发的过程中，每个阶段都会产生不同的文档。软件设计阶段是系统开发的核心阶段。

软件设计可以分为概要设计和详细设计。概要设计的任务是模块分解，确定软件的结构、模块的功能和模块间的接口，以及全局数据结构的设计。在概要设计阶段会产生概要设计说明书。详细设计的任务是设计每个模块的实现细节和局部数据结构，在该阶段会产生详细设计说明书。

编码阶段的任务是用某种程序设计语言为每个模块编写程序。编码阶段可以和测试结合起来，在进行编码的同时，可以地设计单元测试计划。

测试计划是测试阶段产生的文档；系统计划和需求说明分别在软件项目计划阶段和需求分析阶段产生。

参

（25）D

试题（26）、（27）

在一个单CPU的计算机系统中，有两台外部设备R1、R2和三个进程P1、P2、P3。系统采用可剥夺式优先级的进程调度方案，且所有进程可以并行使用I/O设备，三个进程的优先级、使用设备的先后顺序和占用设备时间如下表所示：

进    程	优  先  级	使用设备的先后顺序和占用设备时间
P1	高	R2（30 ms）→CPU（10 ms）→R1（30 ms）→CPU（10 ms）
P2	中	R1（20 ms）→CPU（30 ms）→R2（40 ms）
P3	低	CPU（40 ms）→R1（10 ms）

假设操作系统的开销忽略不计，三个进程从投入运行到全部完成，CPU的利用率约为 （26） %；R2的利用率约为 （27） %（设备的利用率指该设备的使用时间与进程组全部完成所占用时间的比率）。

（26）A．60  B．67      C．78 ．90

（27）A．70 B．78    C．80 ．

试题（26）、（27）分析

由于使用处理机和输入输出设备时采取可剥夺式多任务并行工作方式，所以在分析每个进程都需要多长时间完成时，可以采用优先级高的进程先分析的方法。高优先级的进程有优先获取资源的权利，因而最高优先级的进程Pl发出申请设备的请求会立即得到响应，各设备占用时间为：

在P1占用设备的基础上，P2可以在剩下的进程中优先得到资源：

在P1、P2占用设备的基础上，P3可以在剩下的空闲时间中占用资源：

从图可以看出P2在使用R1设备20ms后，要使用CPU30ms，但当其运行10ms后，P1要使用CPU，由于系统采用可剥夺方式调度，P1优先级高，所以将P2暂停，让P1先运行。同理，P3开始就使用CPU，但在运行20ms后，要让给高优先级的进程P2和P1。Pl从投入运行到完成需要80ms，而P2、P3由于等待资源，运行时间都延长为100ms。CPU在90ms～100ms共10ms时间内没有利用，所以利用率为90/100=90%，同样计算得R2的利用率为70/100=70%，R1的利用率为60%。

参

（26）D  （27）A

试题（28）、（29）

某一确定性有限自动机（DFA）的状态转换图如下图所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是 （28） ，与该DFA等价的正规式是 （29） 。（其中，ε表示空字符）

① 3857  ② 1.2E+5  ③ –123.  ④ .576E10

（28）A．①、②、③ ．①、②、④ ．②、③、④ ．①、②、③、④

（29）A．(–d|d)d* E(–d|d)d* | (–d|d)d*.d*(ε| E(–d|d)d*)

 ．(–d|d)dd*(.|ε)d*(ε| E(–d|d)d*)    

 ．(–|d)dd* E(–|d)d* | (–d|d)dd*.d*(ε| E(–|d)d*) 

 ．(–d|d)dd* E(–d|d)d* | (–d|d)dd*.d*(ε| E(–dd*|dd*))  

试题（28）、（29）分析

有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机（NFA）和确定的有限自动机（DFA），并且每一个NFA都有与其等价的DFA。有穷状态自动机的物理模型如下图所示。

一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为f（A，a）=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。

有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态（题图中节点0表示初始状态）。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到相应的状态转移时为止。

根据题目中给定的自动机，识别3857、1.2E+5、–123.、.576E10的过程分别如下。

分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为 “（–d|d）d*.d*”。当数值的表示含有指数部分时，指数部分是不带符号（表示正数）或带负号的整数形式，因此该部分的正规式为“E(–d|d)d*”。

参

（28）B  （29）A

试题（30）

对于以下编号为①、②、③的正规式，正确的说法是 （30） 。

① (aa*|ab)*b  　② (a|b)*b   ③ ((a|b)*|aa)*b

（30）A．正规式①、②等价 ．正规式①、③等价

 ．正规式②、③等价 ．正规式①、②、③互不等价

试题（30）分析

根据正规式r和s的意义，两个正规式等价说明r和s代表的字符串集合相同，因此可用证明集合相等的方法判断。另外，也可构造出与每个正规式对应的自动机进行说明。但是这两个方法实施起来都很繁琐，因此可根据正规式的含义及其代数性质进行判断。

由于题目中给出的正规式①、②和③的共同之处是以字符b结尾，所以只需考虑(aa*|ab)*、(a|b)*和((a|b)*|aa)*之间的等价关系。从直观的角度理解，正规式(aa*|ab)*表示的是包含空串ε以及a开头的且每个b之后必然出现a的字符串的集合，而(a|b)*表示包含空串ε在内的所有a、b构成的字符串集合，并不b的出现方式，正规式((a|b)*|aa)*表示的字符串也不具有必须以a开头的特点，因此，正规式①与②、③的等价关系即可排除。

至于(a|b)*和((a|b)*|aa)*，很明显正规式((a|b)*|aa)*中的“aa”是画蛇添足的部分，因为(a|b)*已经包括了含有“aa”子串的所有a、b字符串，因此(a|b)*b和((a|b)*|aa)*b是等价的。

参

（30）C

试题（31）、（32）

在UML提供的图中， （31） 用于描述系统与外部系统及用户之间的交互；（32） 用于按时间顺序描述对象间的交互。

（31）A．用例图  B．类图            C．对象图  ．部署图

（32）A．网络图  B．状态图        C．协作图  ．序列图

试题（31）、（32）分析

UML提供了9种不同的模型图，用来对系统建模。

∙用例图：用例图以图形化的方式描述系统与外部系统及用户的交互。换句话说，它们以图形化的方式描述了谁将使用系统，以及用户期望以什么方式与系统 交互。

∙类图：类图描述系统的对象结构，它们显示构成系统的对象类以及这些对象类之间的关系。

∙对象图：对象图类似于类图，但并不描述对象类，它们对实际的对象实例建模——显示实例属性的当前值。

∙序列图：序列图以图形化的方式描述了在一个用例或操作执行过程中对象如何通过消息互相交互，说明了消息如何在对象之间被发送和接收以及发送的顺序。

∙协作图：协作图类似于序列图，但重点不是消息的时间顺序。它以一种网络格式表现对象之间的交互。

∙状态图：状态图用于对一个特定对象的动态行为建模，说明了一个对象的生命周期——对象可以经历的各种状态，以及引起对象从一个状态向另一个状态转换的事件。

∙活动图：活动图用于以图形化的方式描述一个业务过程或者一个用例的活动的顺序流。

∙构件图：构件图用来以图形化的方式描述系统的物理结构，它可以用来显示程序代码如何分解成模块。

∙部署图：部署图描述系统中硬件和软件的物理架构，它描述构成系统架构的软件构件、处理器和设备。

参

（31）A  （32）D

试题（33）～（37）

某数据库中有供应商关系S和零件关系P，其中，供应商关系模式S（Sno，Sname，SZip，City）中的属性分别表示：供应商代码、供应商名、邮编、供应商所在城市；零件关系模式P（Pno，Pname，Color，Weight，City）中的属性分别表示：零件号、零件名、颜色、重量、产地。要求一个供应商可以供应多种零件，而一种零件可以由多个供应商供应。请将下面的SQL语句空缺部分补充完整。

CREATE TABLE SP（Sno  CHAR（5），

    （6），

    （8），

    （9），

     （33） （Sno，Pno），

     （34） （Sno），

     （35） （Pno））；

查询供应了“红”色零件的供应商号、零件号和数量（Qty）的元组演算表达式为：

红

（33）A．FOREIGN KEY 

     B．PRIMARY KEY 

      C．FOREIGN KEY（Sno） REFERENCES S  

 ．FOREIGN KEY（Pno） REFERENCES P

（34）A．FOREIGN KEY

     B．PRIMARY KEY 

      C．FOREIGN KEY（Sno） REFERENCES S  

 ．FOREIGN KEY（Pno） REFERENCES P

（35）A．FOREIGN KEY 

     B．PRIMARY KEY 

      C．FOREIGN KEY（Sno） REFERENCES S  

 ．FOREIGN KEY（Pno） REFERENCES P

（36）A． ． 

 ． ． 

（37）A． ． 

 ． ． 

试题（33）～（37）分析

本题考查的是关系数据库SQL语言与元组演算语言的基础知识。

SQL空缺部分主要是对关系模式SP的完整性定义。根据题意要求一个供应商可以供应多个零件，而一个零件可以由多个供应商供应，这样在供应商和零件之间存在多对多的联系，为此需要为该联系创建一个关系模式，该关系模式的主码为供应商代码Sno、和零件号Pno构成。因此，空（33）应填PRIMARY KEY。

供应商代码Sno为供应商关系的主码，在SP关系中的供应商代码Sno必须参照供应商关系S，所以，空（34）应填FOREIGN KEY（Sno） REFERENCES S。

零件号Pno为零件关系的主码，在SP关系中的零件号Pno必须参照零件关系P，所以，空（35）应填FOREIGN KEY（Pno） REFERENCES P。

完整的SQL语句如下：

CREATE TABLE SP（Sno  CHAR（5），

    （6）,

    （8） ,

    （9），

    （Sno，Pno），

    （Sno） REFERENCES S（Sno），

    （Pno） REFERENCES P（Pno））；

对于空（36）的确定，我们应当先分析试题中已给出的元组演算表达式的条件部分： '红'。由于'红'，这意味着元组变量应该说明零件关系P；由于表示零件号，当，这意味着元组变量应该说明供应商与零件关系之间的联系SP；由于表示零件号，当根据题干给出的已知条件，不难看出元组变量应该说明供应商关系S。可见，空（36）应填：。

对于空（37）的确定，实际上是结果集的确定。由于试题要求查询供应了“红”色零件的供应商号、零件号和数量（Qty）的元组演算表达式，结果集有供应商号、零件号和数量，分别对应关系S的第一个分量，关系SP的第二个分量和第四个分量，所以，空（37）应填。

完整的关系代数表达式如下：

='红'

参

（33）B  （34）C  （35）D  （36）A  （37）D

试题（38）

循环链表的主要优点是（38） 。

（38）A．不再需要头指针了

 B．已知某个结点的位置后，能很容易找到它的直接前驱结点

     C．在进行删除操作后，能保证链表不断开

 ．从表中任一结点出发都能遍历整个链表

试题（38）分析

链表是用连续（或不连续）的存储单元存储数据元素，元素之间的逻辑关系用“指针”指明。链表具体分为几种形式：单向链表中结点包含一个指针，指明其直接前驱（或后继）元素结点；双向链表中结点包含两个指针，分别指明其直接前驱和直接后继元素结点；循环链表是最后结点的指针指回头结点，它可在任何位置上沿指针遍历整个链表。

参

（38）D

试题（39）

表达式a*(b+c)–d的后缀表达形式为 （39） 。

（39）A．abcd*+– B．abc+*d–     C．abc*+d–  ．– +*abcd

试题（39）分析

一个表达式可用一棵二叉树表示，其中的叶子结点表示操作数，内部结点表示操作符或中间结果，根结点表示整个表达式的值。对此二叉树分别进行前序、中序和后序遍历恰好为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。其中表达式的前缀和后缀表示均可以将表达式中的括号省去而不影响计算次序和结果。

参

（39）B

试题（40）

若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为 （40） 。

（40）A．DEBAFC  B．DEFBCA    C．DEBCFA  ．DEBFCA

试题（40）分析

对于二叉树遍历序列有一个性质：包含有中序遍历序列的任意两个遍历序列可以唯一确定该二叉树。那么由题中的先序遍历序列和中序遍历序列就可以唯一确定此二叉树如下图所示，再对其进行后序遍历即可。

参

（40）D

试题（41）

无向图中一个顶点的度是指图中 （41） 。

（41）A．通过该顶点的简单路径数 B．通过该顶点的回路数

     C．与该顶点相邻接的顶点数 ．与该顶点连通的顶点数

试题（41）分析

图中顶点的度定义为与该顶点相关联的边的数目。在无向图中就是与该顶点相邻接的顶点数。而与该顶点连通的顶点数可能就非常多了。

参

（41）C

试题（42）

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行（42）次元素间的比较。

（42）A．4 ．5  ．6 ．7

试题（42）分析

利用逐点插入法建立二叉排序树是从空树开始，通过查找将每个结点作为一个叶子插入。按上述次序建立的二叉排序树如下图所示。

参

（42）B

试题（43）、（44）

已知3个类O、P和Q，类O中定义了一个私有方法F1和一个公有方法F2；类P中定义了一个公有方法F3，类P为类O的派生类；类Q为类P的派生类，它们的继承方式如下所示：

class P : public O {…};

class Q : private P {…};

在关于类P的描述中正确的是 （43） ；在关于类Q的描述中正确的是 （44） 。

（43）A．类P的对象可以访问F1，但不能访问F2

  B．类P的对象可以访问F2，但不能访问F1

      C．类P的对象既可以访问F1，也可以访问F2

  ．类P的对象既不能访问F1，也不能访问F2

（44）A．类Q的对象可以访问F1、F2和F3

 B．类Q的对象可以访问F2和F3，但不能访问F1

     C．类Q的成员可以访问F2和F3，但不能访问F1

 ．类Q的成员不能访问F1、F2和F3

试题（43）、（44）分析

继承机制是面向对象技术提供的另一种解决软件复用问题的途径，即在定义一个新的类时，先把一个或多个已有类的功能全部包含进来，然后再给出新功能的定义或对已有类的功能重新定义。

在继承关系中存在两个类：基类和派生类。继承的方式有3种：public、private和protected。在不同的继承方式下，派生类对基类成员的访问权限不同，外界对派生类成员的能见度也不同。

∙基类中成员在派生类中的访问权限

♦public继承方式：不改变基类中成员的访问权限。

♦private继承方式：派生类所继承的基类成员的访问权限都改为private。

♦protected继承方式：基类中private成员的访问权限不变，其余的都改为protected。

∙派生类所继承的基类成员的外部能见度（外界对基类成员的访问权限）

♦基类的private成员，只有基类的成员函数可以访问，派生类不能访问。

♦通过private方式继承的基类成员（非private成员），只有派生类的成员函数可以访问，外界以及派生类的派生类都不能访问。

♦通过protected方式继承的基类成员（非private成员），只有派生类以及该派生类的子类（非private方式产生的）可以访问，外界不能访问。

（43）、（44）考查的是外界（P的对象和Q的对象）对派生类中继承的基类成员的访问权限。解答此题的关键在于确定基类中成员在派生类中的访问权限，尤其是类Q，它是经过两次继承得到的，Q的直接基类是P，而P又是由O派生而来的。

先分析空（43）。首先应注意到类O中有一个私有方法F1。类的私有成员只有在本类中才能访问，因此凡是出现“可以访问F1”的选项都是错误的，这样选项A、C就可以排除了。其次，P是采用public继承方式从O派生而来，那么类O中的所有公有成员都是P的公有成员，在程序中的任何地方都可以访问一个类的公有成员。因此只有选项B是正确的。

空（44）可以在空（43）的基础上进行。通过继承，F1、F2、F3都成为类Q的成员。由空（43）已经得到：F1不可以被外界访问，因此凡是出现“可以访问F1”的选项都是错误的，这样A就被排除了。由于Q采用的是private继承方式，P中的成员都成为Q的private成员，即F2、F3都是Q的private成员。私有成员只有本类可以访问，所以Q的对象不能访问F2和F3，只有Q的成员才能访问它们。因此选项C是正确答案。

参

（43）B  （44）C

试题（45）

在关于类的实例化的描述中，正确的是 （45） 。

（45）A．同一个类的对象具有不同的静态数据成员值

 B．不同的类的对象具有相同的静态数据成员值

     C．同一个类的对象具有不同的对象自身引用（this）值

 ．不同的类的对象具有相同的对象自身引用（this）值

试题（45）分析

由同一个类实例化得到的不同对象具有相同的数据成员，但数据成员的值是不同的。静态数据成员用来实现同一个类的不同对象之间的数据共享。同一个类的不同对象共享静态数据成员值，当通过一个对象改变了静态数据成员的值时，通过同类的其他对象可以看到这个修改。因此A、B关于静态数据成员的描述都是错误的。

对象自身引用（C++中称为this）是面向对象程序设计语言中特有的、十分重要的机制。每个对象都有属于自己的对象自身引用值。

参

（45）C

试题（46）、（47）

在某信息系统中，存在如下的业务陈述：①一个客户提交0个或多个订单；②一个订单由一个且仅由一个客户提交。系统中存在两个类：“客户”类和“订单”类。对应每个“订单”类的实例，存在 （46） “客户”类的实例；对应每个“客户”类的实例，存在 （47） 个“订单”类的实例。

（46）A．0个 B．1个     C．1个或多个  ．0个或多个

（47）A．0个 B．1个    C．1个或多个 D．0个或多个

试题（46）、（47）分析

认定类/对象是面向对象分析中的关键步骤。但是对象和类并不是孤立存在的，它们表示的事物相互作用，并且相互影响，以便支持业务任务。存在于一个或者多个对象/类之间的自然业务联系称为对象/类关系（object/class relationship）。

可以使用图形方式说明“客户”类和“订单”类之间的这种关系，如下图所示。其中连线表示了类之间的关系，UML称这条线为关联。图中还给出了重复度（multiplicity），即一个对象/类对应相关对象/类的一个实例关联可能的最小出现次数和最大出现次数。

由此可以得到：对应每个订单实例，都必须存在一个客户实例；对应每个客户实例，可能存在0个或多个订单实例。

参

（46）B  （47）D

试题（48）

在常用的描述二叉排序树的存储结构中，关键字值最大的结点 （48） 。

（48）A．左指针一定为空 B．右指针一定为空

     C．左右指针均为空 ．左右指针均不为空

试题（48）分析

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别是二叉排序树。所以关键字最大的结点可以有左子树，但一定没有右子树，否则该结点就不会是最大的结点。

参

（48）B

试题（49）

一个具有n（n>0）个顶点的连通无向图至少有 （49） 条边。

（49）A．n+1 B．n    C． ．n–1

试题（49）分析

在无向图中，如果从一个顶点到另一个顶点有路径，则称这两个顶点是连通的。如果对于图中任意两个顶点都是连通的，则称该无向图是连通的。所以具有n（n>0）个顶点的连通无向图至少有n–1条边。

参

（49）D

试题（50）

由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为

 （50） 。

（50）A．23 B．37    C．44 ．46

试题（50）分析

根据哈夫曼算法，由权值为9，2，5，7的四个叶子结点构造的一棵哈夫曼树如下图所示。

参

（50）C

试题（51）

在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是 （51） 。

（51）A．基数排序 B．快速排序    C．堆排序 ．归并排序

试题（51）分析

基数排序最坏的时间复杂度均为O（d（n+rd））；快速排序最好和最坏情况下的时间复杂度分别为O（n2）和O（nlogn）且不稳定；堆排序在最好和最坏情况下的时间复杂度均为O（nlogn）但不稳定；归并排序是在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法。

参

（51）D

试题（52）

已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key % 7计算散列地址，并散列存储在散列表A[0..6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 （52） 。

（52）A．1.5 B．1.7    C．2.0 ．2.3

试题（52）分析

按照散列函数h（key）= key % 7和线性探测方法解决冲突将线性表（38，25，74，63，52，48）散列存储在散列表A[0..6]中如下图所示。

 位置      0       1       2      3        4      5       6

63

48

38

25

74

52

比较次数   1       3              1        1      2       4

那么（1+3+1+1+2+4）=2.0。

参

（52）C

试题（53）、（54）

为在状态空间树中 （53） ，可以利用LC-检索（Least Cost Search）快速找到一个