2005年上半年软件设计师上午及下午试题及答案

2005 年上半年软件设计师上午试题(欢迎访问软件考 试网 ) 在计算机中，最适合进行数字加减运算的数字编码是_(1)_，最 适合表示浮点数阶码的数字编码是_(2)_。 （1）A原码 B反码 C补码 D移码 （2）A原码 B反码 C补码 D移码 如果主存容量为 16M 字节，且按字节编址，表示该主存地址至少应需要 _(3)_位。(欢迎访问软件考试网 ) （3）A16 B20 C24 D32 操作数所处的位置，可以决定指令的寻址方式。操作数包含在指令中， 寻址方式为_(4)_；操作数在寄存器中，寻址方式为_(5)_；操作 数的地址在寄存器中，寻址方式为_(6)_。(欢迎访问软件考试网 ) （4）A立即寻址 B直接寻址 C寄存器寻址 D寄存器 间接寻址 （5）A立即寻址 B相对寻址 C寄存器寻址 D寄存器 间接寻址 （6）A相对寻址 B直接寻址 C寄存器寻址 D寄存器 间接寻址 三个可靠度 R 均为 0.8 的部件串联构成一个系统，如下图所示： (欢迎 访问软件考试网 ) 则该系统的可靠度为_(7)_。(欢迎访问软件考试网 ) （7）A0.240 B0.512 C0.800 D0.992 在计算机系统中，构成虚拟存储器_(8)_。(欢迎访问软件考试网 ) （8）A只需要一定的硬件资源便可实现 B只需要一定的软件即可实 现 C既需要软件也需要硬件方可实现 D既不需要软件也不需要硬 件 某公司使用包过滤防火墙控制进出公司局域网的数据，在不考虑使用代 理服务器的情况下，下面描述错误的是“该防火墙能够_(9)_”。(欢迎访 问软件考试网 ) （9）A使公司员工只能访问 Internet 上与其有业务联系的公司的 IP 地 址 B仅允许 HTTP 协议通过 C使员工不能直接访问 FTP 服务器端口号为 21 的 FTP 地址 D仅允许公司中具有某些特定 IP 地址的计算机可以访问外部网络 两个公司希望通过 Internet 进行安全通信，保证从信息源到目的地之间 的数据传输以密文形式出现，而且公司不希望由于在中间节点使用特殊的安全 单元增加开支，最合适的加密方式是_(10)_,使用的会话密钥算法应该是 _(11)_。 （10）A链路加密 B节点加密 C端端加密 D混 合加密 （11）ARSA BRC-5 CMD5 DECC 我国著作权法中，_(12)_系指同一概念。(欢迎访问软件考试网 ) （12）A出版权与版权 B著作权与版权 C作者权与专有权 D发 行权与版权 由我国信息产业部批准发布，在信息产业部门范围内统一使用的标准， 称为_(13)_。 （13）A地方标准 B部门标准 C行业标准 D企 业标准 某软件设计师自行将他人使用 C 程序语言开发的控制程序转换为机器语 言形式的控制程序，并固化在芯片中，该软件设计师的行为_(14)_。(欢 迎访问软件考试网 ) （14）A不构成侵权，因为新的控制程序与原控制程序使用的程序设计语 言不同 B不构成侵权，因为对原控制程序进行了转换与固化，其使用和表 现形式不同 C不构成侵权，将一种程序语言编写的源程序转换为另一种程序语 言形式，属于一种“翻译”行为 D构成侵权，因为他不享有原软件作品的著作权 数据存储在磁盘上的排列方式会影响 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）A180ms B200ms C204ms D220ms （16）A40ms B60ms C100ms D160ms 页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的 大小为 4K，地址变换过程如下图所示，图中逻辑地址用十进制表示。 (欢迎访 问软件考试网 ) 图中有效地址经过变换后，十进制物理地址 a 应为_(17)_。(欢迎访 问软件考试网 ) （17）A33220 B8644 C4548 D2500 下列叙述中，与提高软件可移植性相关的是_(18)_ （18）A选择时间效率高的算法 B尽可能减少注释 C选择空间效率高的算法 D尽量用高级语言编写 系统中对效率要求不高的部分 在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统 代替旧系统的策略称为_(19)_；在新系统全部正式运行前，一部分一部分 地代替旧系统的策略称为_(20)_。(欢迎访问软件考试网 ) （19）A直接转换 B位置转换 C分段转换 D并行转换 （20）A直接转换 B位置转换 C分段转换 D并行转换 下列要素中，不属于 DFD 的是_(21)_。当使用 DFD 对一个工资 系统进行建模时，_(22)_可以被认定为外部实体。 （21）A加工 B数据流 C数据存储 D联系 （22）A接收工资单的银行 B工资系统源代码程序 C工资单 D工资数据库的维护。 在系统验收测试中，_(23)_是在一个模拟的环境下使用模拟数 据运行系统；_(24)_是在一个实际环境中使用真实数据运行系统。(欢 迎访问软件考试网 ) （23）A验证测试 B审计测试 C确认测试 D模块测试 （24）A验证测试 B审计测试 C确认测试 D模块测试 采用瀑布模型进行系统开发的过程中，每个阶段都会产生不同的文档。 以下关于产生这些文档的描述中，正确的是_(25)_。(欢迎访问软件考 试网 ) （25）A外部设计评审报告在概要设计阶段产生 B.集成测评计划在程序设计阶段产生 C.系统计划和需求说明在详细设计阶段产生 D.在进行编码的同时，独立的设计单元测试计划 在一个单 CPU 的计算机系统中，有两台外部设备 R1、R2 和三个进程 P1、P2、P3。系统采用可剥夺式优先级的进程调度方案，且所有进程可以并行 使用 I/O 设备，三个进程的优先级、使用设备的先后顺序和占用设备的间如下 表所示： 进程 优先级 使用设备的先后顺序和占用设备时间 P1 高 R2(30ms)CPU(10ms) R1(30ms) CPU(10ms) P2 中 R1(20ms)CPU(30ms) R2(40ms) P3 低 CPU (40ms)R1(10ms) 假设操作系统的开销忽略不计，三个进程从投入运行到全部完成，CPU 的 利用率约为_(26)_% ；R2 的利用率约为_(27)_% （设备的利用 率指该设备的使用时间与进程组全部完成所占用时间的比率）。 （26）A60 B.67 C.78 D.90 （27）A70 B.78 C.80 D.89 某一确定性有限自动机（DFA）的状态转换图如下图所示，令 d=0|1|2|9,则以下字符串中，不能被该 DFA 接受的是_(28)_，与该 DFA 等价的正规式是_(29)_。（其中， 表示空字符）(欢迎访问软件 考试网 ) 3875 1.2E+5 -123. .576E10 （28）A、 B. 、 C. 、 D. 、 （29）A（-d|d）d*E(-d|d)d*|(-d|d)d*.d*(|E(-d|d)d*) B.-(d|d)dd*(.|)d*(|E(-d|d)d*) C.(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(|E(-|E(-|d)d*) D.(-d|d)dd*E(-d|d)d*|(-d|d)dd*.d*(|E(-dd*|dd*) 对于以下编号为、的正规式，正确的说法是_(30) _。(欢迎访问软件考试网 ) (aa*|ab)*b (a|b)*b (a|b)* |aa)*b (30) A.正规式、等价 B.正规式、等价 C. 正规式、等价 D.正规式、互不等价 在 UML 提供的图中，_(31)_用于描述系统与外部系统及用户之 间的交互；_(32)_用于按时间顺序描述对象间的交互。 (31) A.用例图 B.类图 C.对象图 D.部署图 (32) A.网络图 B.状态图 C.协作图 D.序列图 某数据库中有供应商关系 S 和零件关系 P，其中：供应商关系模式 S（Sno，Sname，Szip，City）中的属性分别表示：供应商代码、供应商名、邮 编、供应商所在城市；零件号、零件名、颜色、重量、产地。要求一个供应商 可以供应多种零件，而一种零件可以由多个供应商供应。请将下面的 SQL 语句 空缺部分补充完整。(欢迎访问软件考试网 ) CREATE TABLE SP（Sno CHAR(5), Pno CHAR(6), Status CHAR(8), Qty NUMERIC(9), _(33)_ (Sno,Pno), _(34)_ (Sno), _(35)_ (Pno); 查询供应了“红“色零件的供应商号、零件号和数量（Qty）的元组演算表达 式为： t|( u)( v)( w)(_(36)_ u1=v1 v2 =w1 w3=红 _(37)_) (33)A.FOREIGN KEY B.PRIMARY KEY C.FOREIGN KEY(Sno)REFERENCES S D.FOREIGN KEY(Pno) REFERENCES P (34)A.FOREIGN KEY B. PRIMARY KEY C.FOREIGN KEY(Sno)REFERENCES S D.FOREIGN KEY(Pno) REFERENCES P (35)A.FOREIGN KEY B. PRIMARY KEY C.FOREIGN KEY(Sno)REFERENCES S D.FOREIGN KEY(Pno) REFERENCES P (36)A.S(u) SP(v) P(w) B. SP(u) S(v) P(w) C. P(u) SP(v) S(w) D. S(u) P(v) SP(w) (37)A.t1=u1 t2=w2 t3=v4 B. t1=v1 t2=u2 t3=u4 C. t1=w1 t2=u2 t3=v4 D. t1=u1 t2=v2 t3=v4 循环链表的主要优点是_(38)_。(欢迎访问软件考试网 ) （38）A.不再需要头指针了 B. 已知某个结点的位置后，能很容易找到它的直接前驱结点 C.在进行删除操作后，能保证链表不断开 D.从表中任一结点出发都能遍历整个链表 表达式 a*(b+c)-d 的后缀表达形式为_(39)_。(欢迎访问软件考 试网 ) （39）A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd 若二叉树的先序遍历序列为 ABDECF，中序遍历序列 DBEAFC，则其后序 遍历序列为_(40)_。 （40）A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 无向图中一个顶点的度是指图中_(41)_。(欢迎访问软件考试网 ) （41）A.通过该顶点的简单路径数 B.通过该顶点的回路数 C.与该顶点相邻接的顶点数 D.与该顶点连通的顶点数 利用逐点插入建立序列（50,72,43,85,75,20,35,45,65,30）对应的二 叉排序树以后，查找元素 30 要进行_(42)_次元素间的比较。(欢迎访问 软件考试网 ) （42）A. 4 B.5 C. 6 D.7 已知 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 D.类 P 的对象既不能访问 F1，也不能访问 F2 （44）A.类 Q 的对象可以访问 F1、F2、和 F3 B.类 Q 的对象可以访问 F2 和 F3，但不能访问 F1 C.类 Q 的成员可以访问 F2 和 F3，但不能访问 F1 D.类 Q 的成员不能访问 F1、F2 和 F3 在关于类的实例化的描述中，正确的是_(45)_。(欢迎访问软件 考试网 ) （45）A.同一个类的对象具有不同的静态数据成员值 B.不同的类的对象具有相同的静态数据成员值 C.同一个类的对象具有不同的对象自身引用（this）值 D.同一个类的对象具有不同的对象自身引用（this）值 在某信息系统中，存在如下的业务陈述：一个客户提交 0 个或多个订 单 一个订单由一个且仅由一个客户提交。系统中存在两个类：“客户“类和“ 订单“类。对应每个“订单“类的实例，存在_(46)_“客户“类的实例；对应每 个“客户“类的实例，存在_(47)_个“订单“类的实例；(欢迎访问软件考试 网 ) （46）A.0 个 B.1 个 C.1 个或多个 D.0 个或多个 （47）A.0 个 B.1 个 C.1 个或多个 D.0 个或多个 在常用的描述二叉排序树的存储结构中，关键字值最大的结点_(48) _。(欢迎访问软件考试网 ) （48）A.左指针一定为空 B.右指针一定为空 C.左右指针均为空 D.左右指针均不为空 一个具有 n(n0)个顶点的连通无向图至少有_(49)_条边。(欢 迎访问软件考试网 ) （49）A.n+1 B.n C.n/2 D.n-1 由权值为 9，2，5，7 的四个叶子构造一棵哈夫曼树，该树的带权路径 长度为_(50)_ 。 （50）A.23 B.37 C.44 D.46 在最好和最坏情况下的时间复杂度均为 O（nlogn）且稳定的排序方法 是_(51)_。 （51）A.基数排序 B.快速排序 C.堆排序 D.归并排序 已知一个线性表（38，25，74，63，52，48），假定采用散列函数 h(key)=key%7 计算散列地址，并散列存储在散列表 A06中，若采用线性探 测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 _(52)_ 。 （52）A.1.5 B.1.7 C.2.0 D.2.3 为在状态空间树中_(53)_，可以利用 LC-检索（Least Cost Search） 快速找到一个答案结点。在进行 LC-检索时，为避免算法过分偏向于 作纵深检查，应该_(54)_。(欢迎访问软件考试网 ) （53）A.找出任一个答案结点 B.找出所有的答案结点 C.找出最优的答案结点 D.进行遍历 （54）A.使用精确的成本函数 c(.)来作 LC-检索(欢迎访问软件考试网 ) B.使用广度优先检索 C.使用深度优先检索 D.在成本估计函数 (.)中考虑根结点到当前结点的成本(距离) 以比较为基础的排序算法在最坏情况下的计算时间下界为_(55) _。(欢迎访问软件考试网 ) （55）AO(n) BO(n 2) CO(logn) DO(nlogn) 利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=共有 n 个结点，结点编号 1n，设 C 是 G 的成本邻接矩阵，用 Dk(i,j)即为图 G 中结点 i 到 j 并且不经 过编号比 k 还大的结点的最短路径的长度（D n(i,j)即为图 G 中结点 i 到 j 的最 短路径长度），则求解该问题的递推关系式为_(56)_。(欢迎访问软件考试 网 ) （56）AD k(i,j)=Dk-1(i,j)+C(i,j) BD k(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j) CD k (i,j)=Dk-1(i,k)+Dk-1(k,j) DD k(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j) PC 机处理人耳能听得到的音频信号，其频率范围是_(57)_。(欢迎 访问软件考试网 ) （57）A803400Hz B3003400Hz C2020kHz D2044.1kHz 电视系统采用的颜色空间中，其亮度信号和色度信号是相分离的。下列 颜色空间中,_(58)_不属于电视系统的颜色空间。 （58）AYUV BYIQ CYcbCr DHSL 双层双面的只读 DVD 盘片的存储容量可以达到_(59)_。(欢迎访 问软件考试网 ) （59）A4.7GB B8.5GB C17GB D6.6GB 静态图像压缩标准 JPEG2000 中使用的是_(60)_算法。(欢迎访 问软件考试网 ) （60）AK-L 变换 B离散正弦变换 C离散余弦变换 D离散小波变换 一个局域网中某台主机的 IP 地址为 2，使用 22 位作为 网络地址，那么该局域网的子网掩码为_(61)_，最多可以连接的主机数 为_(62)_。(欢迎访问软件考试网 ) （61) A B C D （62) A254 B512 C1022 D1024 以下选项中，可以用于 Internet 信息服务器远程管理的是_(63) _。(欢迎访问软件考试网 ) (63) ATelnet BRAS CFTP DSMTP 在 TCP/IP 网络中，为各种公共服务保留的端口号范围是_(64) _。(欢迎访问软件考试网 ) (64) A1255 B11023 C11024 D165535 在以下网络应用中，要求带宽最高的应用是_(65)_。(欢迎访问软 件考试网 ) (65) A可视电话 B数字电视 C拨号上网 D收发邮件 DOM is a platform-and language-_(66)_API that allows programs and scripts to dynamically access and update the content, structure and style of WWW documents ( currently,definitions for HTML and XML documents are part of the specification ).The document can be further processed and the results of that processing can be incoporporated back into the presented _(67)_.DOM is a _(68)_-based API to documents ,which requires the whole document to be represented in _(69)_while processing it .A simpler alternative to DOM is the event based SAX,which can be used to process very large _(70)_documents that do not fit info the memory available for processing. （66）Aspecific Bneutral Ccontained Drelated （67）Atext Bimage Cpage Dgraphic （68）Atable Btree Ccontrol Devent （69）Adocument Bprocessor Cdisc Dmemory （70）AXML BHTML Cscript Dweb Melissa and Love Letter made use of the trust that exists between friends or colleagues. Imagine receiving an _(71)_from a friend who asks you to open it. This is what happens with Melissa and several other similar email _(72)_.Upon running ,such worms usually proceed to send themselves out to email addresses from the victims address book, previous emails, web pages_(73)_.(欢迎访问软件考试网 ) As administrators seek to block dangerous email attachments through the recognition of well- known _(74)_,virus writers use other extensions to circumvent such protection. Executable (.exe) files are renamed to .bat and .cmd plus a whole list of other extensions and will still run and successfully infect target users. Frequently ,hackers try to penetrate networks by sending an attachment that looks like a flash movie ,which, while displaying some cute animation ,simultaneously runs commands in the background to steal your passwords and give the _(75)_access to your network.(欢迎访问软件 考试网 ) （71）Aattachment Bpacket Cdatagram Dmessage （72）Avirtual B virus Cworms Dbacteria （73）Amemory B caches Cports D registers （74）Anames Bcookies Csoftware Dextensions （75）Acracker B user C customer Dclient 2005 年上半年软件设计师下午试题 试题一至试题四是必答题 试题一（15 分）(欢迎访问软件考试网 ) 阅读以下说明和数据流图，回答问题 1 至问题 3，将解答题纸的对应栏内。 说明(欢迎访问软件考试网 ) 学生住宿服务系统帮助学生在就学的城市内找以所需的住房，系统对出租 的房屋信息、房主信息、需要租房的学生信息以及学生和房主的会面住处进行 管理和维护。 房主信息包括姓名、地址、电话号码以及系统分配的唯一身份标识（ID） 和密码；房屋信息包括房屋地址、类型（单间/套间）、适合住宿的人数、房租、 房主的 ID 以及现在是否可以出租（例如由于装修原因，需等到装修后才可出租 或者房屋已被租出）。每当房房屋信息发生变化时，房主须通知系统，系统将 更新房到文件以便学生能够获得准确的可租用房屋信息，房主向系统中加入可 租用的房屋信息时，需交纳一定的费用，由系统自动给出费用信息。房主可随 时更新房屋的各种属性。 学生可通过系统查询现有的可租用的房屋，但必须先在系统中注册。学生 信息包括姓名、现住址、电话号码、出生日期、性别以及系统分配的唯一身份 标识（ID）和密码。若学生希望租用某房屋，则需要发出租房请求，请求中包 含房屋的详细信息，系统将安排学生与房主会面的时间和地点，并将会面信息 通知学生和房主，会面信息包括会面时间、地点以及会面双方的基本信息，系 统将记录会面信息。 学生住宿服务系统的顶层图如图 1-1 所示；学生住宿服务系统的第 0 层 DFD 图如图 1-2 所示，其中，加工 3 的细化图如图 1-3 所示。 问题 1（6 分）(欢迎访问软件考试网 ) （1）数据流图 1-1 缺少了一条数据流（在图 1-2 中也未给出该数据流）， 请给出此数据流的起点和终点，并采用说明中的词汇给出此数据流名。 （2）数据流图 1-2 中缺少了与“查询房屋“加工相关的数据流，请指出此数 据流的起点和终点。 问题 2（4 分）(欢迎访问软件考试网 ) “安排会面“加工除需要写入会面文件外，还需要访问哪些文件？ 问题 3（5 分）(欢迎访问软件考试网 ) 请补齐下列数据字典条目： 登录信息=学生 ID+密码 注册信息= 数据流图 1-1 (欢迎访问软件考试网 ) 数据流图 1-2(欢迎访问软件考试网 ) 数据流图 1-3 (欢迎访问软件考试网 ) 试题二（15 分）(欢迎访问软件考试网 ) 阅读以下说明和表，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。 说明(欢迎访问软件考试网 ) 某公司信息管理系统的需求分析和部分关系模式的结果描述如下： 1. 公司有多个部门，每个部门有一名负责人、一间办公室、一部电话、多 名职员，每个职员最多数一个部门，负责人也是公司一名职员。 2. 公司职员的工资大于等于 1000 元且最小等于 8000。 3. 数据库的部分关系模式设计如下： 职员（职员号，职工姓名，月工资。部门号、办公室，电话） 部门（部门号，部门名，负责人代码，任职时间） 4.“职员“和“部门“的关系示例分别如表 2-1 和表 2-2 所示 表 2-1 (欢迎访问软件考试网 ) “职员“关系 职员号 职员姓名 月工资 部门号 办公室 电话 60801 汪俊华 1000 1 A 座 201 6883122 60802 杨晓军 3200 1 A 座 201 6883122 60803 王晓华 4300 2 B 座 202 6883123 60804 邢彦军 2800 2 B 座 202 6883123 60805 吕靖原 5300 3 A 座 301 6883124 60806 芦文峰 3200 3 A 座 301 6883124 60807 牟雪松 2800 3 A 座 301 6883124 60808 高亚南 1200 4 B 座 302 6883125 60810 周黎 3200 4 B 座 302 6883125 60820 姚应磊 1200 4 B 座 302 6883125 60821 程文驰 3200 5 B 座 303 6883126 60836 许俊坤 0 Nu11 表 2-2 (欢迎访问软件考试网 ) “部门“关系 部门号 部门名 负责人代码 任职时间 1 财务部 60802 2001-8-5 2 市场部 60803 2002-6-3 3 研发部 60805 2002-6-3 4 生产部 1 60810 2003-8-1 5 生产部 2 60821 2004-6-3 问题 1（4 分）(欢迎访问软件考试网 ) 根据上述说明，请给出 （1）“职员“关系模式的主键和外键。 （2）“部门“关系模式的主键和外键。 问题 2（4 分）(欢迎访问软件考试网 ) （1）用 SQL 定义“职员“关系模式，请在空缺处填入正确的内容。 Create Table 职员（职员号 CHAR（5）_(a)_ ， 职员姓名 CHAR（8）， 月工资 NUMBER（4）， 部门号 CHAR（1）， 办公室 CHAR（20） 电话 CHAR（8）， _(b)_ （部门号）， CHECK（月工资=1000 AND 月工资=8000）； （2）针对人数大于等于 2 的部门创建视图 D_View（Dept， D_num，D_Totals，D_Avgpay），其中，Dept 为部门号，D num 为部门人数， D_Totals 为部门人数，D_Avgpay 为平均工资，请在空缺处填入正确的内容。 Create View D_View（Dept，D_num，D_Totals，D_AvgPay）As (Select 部门号，_(c)_ from 职员 _(d)_ count（*）=2 WHERE 部门号 IS NOT NULL）： 问题 3（3 分）(欢迎访问软件考试网 ) 对于表 2-1、表 2-2 所示的“职员“和“部门“关系，请指出下列各行是否可 以插入“职员“关系，为什么？ 1 60811 芦 峰 800 1 A 座 201 6883122 2 60802 李晓啸 3500 2 B 座 202 6883123 3 60812 高亚南 2600 问题 4（4 分）(欢迎访问软件考试网 ) 原来的“职员“关系模式存在什么问题？在不增加新关系模式的前提下，请 给出修出改后的“职员“和“关系模式“。 试题三（15 分）(欢迎访问软件考试网 ) 阅读以下说明和流程图，从供选择的答案中选出应填入流程图 _(n)_ 处 的字句写在答题纸的对应栏内。 说明(欢迎访问软件考试网 ) 一个印刷电路板的布线区域可分成 nm 个方格，如图 3-1（a）所示，现 在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能 沿水平或垂直方向布线，如图 3-1（b）中虚线所示。为了避免线路相交，应将 已布过线的方格作成封锁标记，其他线路不允许穿过被封锁的方格。 图 3-1 (欢迎访问软件考试网 ) 设给定印刷电路板的起始方格 x 与目的方格 y 尚未布线，求这两个方格间 最短布线方案的基本思路是：从起始方格 x 开始，先考查距离起始方格距离为 k 的某一个可达方格就是目标方格 y 时为止，或者由于不存在从 x 到 y 的布线 方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右四个方格之 间的距离为 1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可 达方格的位置。表 3-1 给出了沿这四个方向前进 1 步时相对于当前方格的相对 偏移量。 表 3-1 (欢迎访问软件考试网 ) 搜索顺序 i 方向 行偏移量 列偏移量 0 上 -1 0 1 右 0 1 2 上 -1 0 3 左 0 -1 例如，设印刷电路板的布线区域可划分为一个 68 的方格阵列，如图 3- 2（a）所示，其中阴影表示已封锁方格。从起始方格 x( 位置3，2，标记为 0)出 发，按照下、右、上、左的方向依次考查，所标记的可达方格如图 3-2（a）所 示，目标方格为 y( 位置4，7，标记为 10)，相应的最短布线路径如图 3-2(b) 虚线所示。 图 3-2 (欢迎访问软件考试网 ) 图 3-3 和图 3-4 所示的流程图即利用上述思想路，在电路板方格阵列中进 行标记，图中使用的主要符号如表 3-2 所示。在图 3-4 中，设置电路板初始格 局即将可布线方格置为数值-1、已布线方格（即封锁方格）置为-9。设置方格 阵列“围墙“的目的是省略方格位置的边界条件判定，方法是在四周附加格，并 将其标记为-9（与封锁标记相同）。 表 3-2 (欢迎访问软件考试网 ) 符号 含义 Grid 全局二维数组 GridN+2,M+2,表示电路板 方格阵列，初始时数组元素 Gridi,jr 的值为-1 表示当前方格可布线，为-9 表 示前方格不可布线。 Offset 一维数组 offset4:offseti(0i3) 的分量为 r（行偏移量）和 c(列偏移量)， 按照表 3-1 的内容设置其值。 Startpos、E ndpos、Curp os、T 分别表示起始方格、目标方格、当前方格 和临时方格，其位置用分量度 row 和 col 确定。 Q.insert(s) 将方格 s 的位置信息加入队列 Q.delete() 删除非空队列的队头元素，并返回该元素。 Q.empty() 若队列 Q 为空，则返回 true;否则返回false。 图 3-3 (欢迎访问软件考试网 ) 图 3-4 (欢迎访问软件考试网 ) 供选择的答案(欢迎访问软件考试网 ) a Foundtrue b Found = true c T = EndPos d Q.insert(T) e T Q.delete() f CurPos = EndPos g i4 h CurPos Q.delete() i GridT.row,T.col = -1 j GridT.row,T.col-1 试题四（15 分）(欢迎访问软件考试网 ) 阅读以下说明和 C 程序，将应填入_(n)_ 处的字句写在答题纸对应栏内。 说明(欢迎访问软件考试网 ) 假设需要将 N 个任务分配给 N 个工人同时去完成，每个人都能承担这 N 个 任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案， 在该方案中，为每个人分配 1 个不同的任务。 程序中，N 个任务从 0 开始依次编号，N 个工人也从 0 开始依次编号，主要 的变量说明如下： cij:将任务 i 分配给工人 j 的费用； taski:值为 0 表示任务 i 未分配，值为 j 表示任务 i 分配给工人 j； workerk:值为 0 表示工人 k 未分配任务，值为 1 表示工人 k 已分配任务； mincost:最小总费用。 C 程序(欢迎访问软件考试网 ) include define N 8 /*N 表示任务数和工人数*/ int cNN； unsigned int mincost = 65535； /*设置的初始值，大于可能的费用*/ int taskN，tempN，workerN； void plan(int k,unsigned int cost) int i； if（ _(1)_ public Circle () pxc = new _(3)_; public void display() pxc. _(4)_; 代码 6-2(欢迎访问软件考试网 ) public class Factory public _(5)_ getShapeInstance(int type) /生成特定类实例 Switch(type) case 0：return new point()； case 1：return new Rectangle()； case 2：return new Line()； case 3：return new Circle()； default：return null； ； public class App public static void main(String argv) if(argv.length !=1) System.out.println(“error parameters!“)； return； int type=(new Integer(argv0).intValue()； Factory factory=new Factory()； if(s=null) System.out.println(“Error get instance!“)； Return； s.display()； return； 试题七（15 分钟）(欢迎访问软件考试网 ) 阅读以下说明和 Visual Basic 代码，将应填入 _(n)_ 处的字名写在答 题纸的对应栏内。 说明(欢迎访问软件考试网 ) 某绘图系统定义了一个抽象类 IShape, 现有三个类 CPoint，CLine 和 CCircle,它们都具有 IShape 界面。相应的类图关系如图 7-1 所示。 已知某第三方库已经提供了 XCircle 类，且完全满足 CCircle 图元显示时 所需的功能。化码 7-1 是抽象类 IShape 类模块内容,代码 7-2 实现了类 CCircle 的 IShape 界面，并使用了 XCircle 提供的显示功能。 XCircle 提供的显示功能方法接口为 displayIt。 图 7-1 (欢迎访问软件考试网 ) 代码 7-1(欢迎访问软件考试网 ) Public Color As Long Sub draw() 方法体不包括可执行语句 End Sub Sub move(stepx As Single，stepy As Single) 方法体不包括可执行语句 End Sub 代码 7-2(欢迎访问软件考试网 ) _(1)_ Private color As Long 其他定义省略 Private ridged As _(2)_ Private Sub Class_Initialize() Set bridged= _(3)_ End Sub Private Property _(4)_ ()As Long IShape_Color=color End Property Private Property _(5)_ (ByVal newColor As Long) Color=newColor End Property Private Sub IShape_draw() 使用 XCircle 提供的显示功能 _(6)_ End Sub Private Sub IShape_move (stepx As Single，stepy As Single) 省略描述 End Sub 200