2008上半年软件设计师上、下午真题word版

1 / 12

2008上半年软件设计师上午试题 ● 在计算机体系结构中,CPU 内部包括程序计数器 PC、存储器数据寄存器 MDR、指令寄存器IR 和存储器地址寄存器MAR 等。若CPU 要执行的指令为: MOV R0, #100(即将数值100传送到寄存器R0中),则CPU 首先要完成的操作是(1)。 (1)A.100→R0 B. 100→MDR C. PC→MAR D. PC→IR

● 现有四级指令流水线,分别完成取指、取数、运算、传送结果四步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns,则流水线的操作周期应设计为(2)ns。 (2)A. 6 B. 8 C. 9 D. 10

● 内存按字节编址,地址从90000H 到CFFFFH,若用存储容量为16K×8bit的存储器芯片构成该内存,至少需要 (3) 片。 (3)A. 2 B. 4 C. 8 D. 16

● CPU 中的数据总线宽度会影响 (4) 。

(4)A. 内存容量的大小 B. 系统的运算速度 C. 指令系统的指令数量 D. 寄存器的宽度

● 利用高速通信网络将多台高性能工作站或微型机互连构成机群系统,其系统结构形式属于 (5) 计算机。

(5)A. 单指令流单数据流(SISD) B. 多指令流单数据流(MISD) C. 单指令流多数据流(SIMD) D. 多指令流多数据流(MIMD) ● 内存采用段式存储管理有许多优点,但― (6) ‖不是其优点。

(6)A. 分段是信息的逻辑单位,用户不可见 B. 各段程序的修改互不影响 C. 地址变换速度快、内存碎片少 D. 便于多道程序共享主存的某些段

● 如果希望别的计算机不能通过ping命令测试服务器的连通情况,可以(7)。如果希望通过默认的Telnet端口连接服务器,则下面对防火墙配置正确的是(8)。

(7)A. 删除服务器中的ping.exe文件 B. 删除服务器中的cmd.exe文件 C. 关闭服务器中ICMP 端口 D. 关闭服务器中的Net Logon服务 (8)A. B.

C. D.

●某银行为用户提供网上服务,允许用户通过浏览器管理自己的银行账户信息。为保障通信的安全性,该Web服务器可选的协议是(9)。 (9)A. POP B. SNMP C. HTTP D. HTTPS ● 关于软件著作权产生的时间,表述正确的是 (10) 。

(10)A. 自软件首次公开发表时 B. 自开发者有开发意图时

C. 自软件得到国家著作权行政管理部门认可时 D. 自软件完成创作之日起

● 李某大学毕业后在学赛网销售部门工作,后由于该公司软件开发部门人手较紧,李某被暂调到该公司软件开发部开发新产品,2周后,李某开发出一种新软件。该软件著作权应归 (11) 所有。

(11)A. 李某 B. 学赛网 C. 李某和学赛网 D. 软件开发部

● 一幅灰度图像,若每个像素有8位像素深度,则最大灰度数目为 (12) 。 (12)A. 128 B. 256 C. 512 D. 1024

● 当图像分辨率为800×600,屏幕分辨率为640×480时,(13) 。

2 / 12

(13)A. 屏幕上显示一幅图像的64%左右 B. 图像正好占满屏幕 C. 屏幕上显示一幅完整的图像 D. 图像只占屏幕的一部分 ● 若视频图像每帧的数据量为6.4MB,帧速率为30帧/秒,则显示10秒的视频信息,其原始数据量为(14) MB。 (14)A. 64 B. 192 C. 640 D. 1920

●(15)是一种面向数据流的开发方法,其基本思想是软件功能的分解和抽象。

(15)A. 结构化开发方法 B. Jackson系统开发方法 C. Booch 方法 D. UML(统一建模语言)

● 采用UML进行软件设计时,可用(16) 关系表示两类事物之间存在的特殊/一般关系,用聚集关系表示事物之间存在的整体/部分关系。 (16)A. 依赖 B. 聚集 C. 泛化 D. 实现

● 某项目制定的开发计划中定义了三个任务,其中任务 A 首先开始,且需要 3 周完成,任务B 必须在任务A 启动1 周后开始,且需要2 周完成,任务C 必须在任务A 完成后才能开始,且需要2周完成。该项目的进度安排可用下面的甘特图(17)来描述。

● 风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。―建立风险条目检查表‖是(18) 时的活动,―描述风险的结果‖是(19)时的活动。

(18)(19)A.风险识别 B.风险预测 C.风险评估 D.风险控制

● 编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段,其中,(20) 并不是每种编译器都必需的。

(20)A. 词法分析和语法分析 B. 语义分析和中间代码生成 C. 中间代码生成和代码优化 D. 代码优化和目标代码生成 ● 已知某文法G[S]:S→0S0 S→1,从S推导出的符号串可用 (21) (n≥0) 描述。 (21)A.(010)n B. 0n10n C. 1n D. 01n0 ● 下列叙述中错误的是 (22) 。

(22)A. 面向对象程序设计语言可支持过程化的程序设计 B. 给定算法的时间复杂性与实现该算法所采用的程序设计语言无关

C.与汇编语言相比,采用脚本语言编程可获得更高的运行效率 D.面向对象程序设计语言不支持对一个对象的成员变量进行直接访问 ● 某火车票销售系统有 n 个售票点,该系统为每个售票点创建一个进程Pi (i=1,2,Λ,n)。假设Hj (j=1,2,Λ,m)单元存放某日某车次的剩余票数,Temp 为Pi 进程的临时工作单元,x为某用户的订票张数。初始化时系统应将信号量S赋值为(23)。Pi 进程的工作流程如下,若用 P操作和V操作实现进程间的同步与互斥,则图中a、b和c应分别填入(24) 。

(23)A. 0 B. 1 C. 2 D. 3

(24)A. P(S)、V(S) 和V(S) B. P(S)、P(S) 和V(S) C. V(S)、P(S) 和P(S) D. V(S)、V(S) 和P(S)

● 在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,―/‖表示路径中的分隔符,―/‖在路径之首时表示根目录。图中, (25) 。假设当前目录是A2,若进程A以如下两种方式打开文件f2:

方式① fd1=open(″ (26) /f2″,o_RDONLY); 方式② fd1=open(″/A2/C3/f2″,o_RDONLY); 那么,采用方式①的工作效率比方式②的工作效率高。

(25)A. 根目录中文件f1与子目录C1、C2和C3中文件f1一定相同 B. 子目录C1中文件f2与子目录C3中文件f2一定相同

C. 子目录C1中文件f2与子目录C3中文件f2一定不同 D. 子目录C1中文件f2与子目录C3中文件f2是可能相同也可能不相同

3 / 12

(26)A. /A2/C3 B. A2/C3 C. C3 D. f2 ● 在某计算机中,假设某程序的6个页面如下图所示,其中某指令―COPY A TO B‖跨两个页面,且源地址A 和目标地址B 所涉及的区域也跨两个页面。若地址为 A 和 B 的操作数均不在内存,计算机执行该COPY 指令时,系统将产生 (27) 次缺页中断;若系统产生三次缺页中断,那么该程序应有 (28) 个页面在内存。

(27)A. 2 B. 3 C. 4 D. 5 (28)A. 2 B. 3 C. 4 D. 5

● 极限编程(eXtreme Programming)是一种轻量级软件开发方法, (29)不是它强调的准则。

(29)A. 持续的交流和沟通 B. 用最简单的设计实现用户需求 C. 用测试驱动开发 D. 关注用户反馈 ● 学赛网采用的软件开发过程通过了CMM2认证,表明该公司 (30) 。

(30)A. 开发项目成效不稳定,管理混乱 B. 对软件过程和产品质量建立了定量的质量目标

C. 建立了基本的项目级管理制度和规程,可对项目的成本、进度进行跟踪和控制 D. 可集中精力采用新技术新方法,优化软件过程 ● 某数据处理软件包括2个完全相同的数据处理部件和1个数据存储部件,且采用下图给出的容错方案。当数据处理部件的可靠性为 0.6 时,为使整个软件系统的可靠性不小于0.66,则数据存储部件的可靠性至少应为 (31)。

(31)A. 0.6 B. 0.66 C. 0.79 D. 1.0

● 在软件设计和编码过程中,采取― (32) ‖的做法将使软件更加容易理解和维护。 (32)A. 良好的程序结构,有无文档均可 B. 使用标准或规定之外的语句 C. 编写详细正确的文档,采用良好的程序结构 D. 尽量减少程序中的注释

● 软件维护成本在软件成本中占较大比重。为降低维护的难度,可采取的措施有 (33) 。 (33)A. 设计并实现没有错误的软件 B. 限制可修改的范围

C. 增加维护人员数量 D. 在开发过程中就采取有利于维护的措施,并加强维护管理

● 软件文档按照其产生和使用的范围可分为开发文档、管理文档和用户文档。其中开发文档不包括(34)。 (34)A. 软件需求说明 B. 可行性研究报告 C. 维护修改建议 D. 项目开发计划

● 软件测试是软件开发中不可缺少的活动,通常 (35) 在代码编写阶段进行。检查软件的功能是否与用户要求一致是(36) 的任务。 (35)(36)A. 验收测试 B. 系统测试 C. 单元测试 D. 集成测试

●(37)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(38)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。 (37)(38)A. 封装 B. 多态 C. 继承 D. 变异

● (39)以静态或动态的连接方式,为应用程序提供一组可使用的类。(40)除了提供可被应用程序调用的类以外,还基本实现了一个可执行的架构。

(39)(40)A. 函数库 B. 类库 C. 框架 D. 类属

● 已知某子系统为外界提供功能服务,但该子系统中存在很多粒度十分小的类,不便被外界系统直接使用,采用(41)设计模式可以定义一个高层接口,这个接口使得这一子系统更加容易使用;当不能采用生成子类的方法进行扩充时,可采用(42)设计模式动态地给一个对象添加一些额外的职责。

(41)(42)A. Facade(外观) B. Singleton(单件) C. Participant(参与者) D. Decorator(装饰) ● (43)设计模式将抽象部分与它的实现部分相分离,使它们都可以独立地变化。下图为该设计模式的类图,其中,(44)用于定义实现部分的接口。

(43)A. Singleton(单件) B. Bridge(桥接) C. Composite(组合) D. Facade(外观)

(44)A. Abstraction B. ConcreteImplementorA C. ConcreteImplementorB D. Implementor

4 / 12

● 在UML类图中,类与类之间存在依赖(Dependency)、关联(Association)、聚合(Aggregation)、组合(Composition)和继承(Inheritance)五种关系,其中,(45)关系表明类之间的相互联系最弱,(46)关系表明类之间的相互联系最强,聚合(Aggregation)的标准UML图形表示是(47)。

(45)(46)A. 依赖 B. 聚合 C. 组合 D. 继承

● 有限自动机(FA)可用于识别高级语言源程序中的记号(单词),FA 可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D 与某NFA M等价,则(48) 。

(48)A. DFA D 与NFA M的状态数一定相等 B. DFA D 与NFA M可识别的记号相同

C. NFA M能识别的正规集是DFA D 所识别正规集的真子集 D. DFA D 能识别的正规集是NFA M所识别正规集的真子集 ● 某确定性有限自动机(DFA)的状态转换图如下图所示,令 d=0|1|2|...|9,则以下字符串中,能被该DFA 接受的是 (49) 。

(49)A. 3857 B. 1.2E+5 C. -123.67 D. 0.576E10

● 若有数组声明 a[0..3,0..2,1..4],设编译时为 a 分配的存储空间首地址为base_a,且每个数组元素占据一个存储单元。当元素以行为序存放(即按 a[0,0,1],a[0,0,2],a[0,0,3],a[0,0,4],a[0,1,1],a[0,1,2],…,a[3,2,4]顺序存储),则数组元素a[2,2,2]在其存储空间中相对base_a的偏移量是(50) 。

(50)A. 8 B. 12 C. 33 D. 48

● 从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写 (51) ,③处应填写 (52) 。 (51)(52)A. 外模式 / 概念模式 B. 概念模式 / 内模式 C. 外模式 / 概念模式映象 D. 概念模式 / 内模式映象

● 设有职工EMP (职工号, 姓名, 性别, 部门号, 职务, 进单位时间, 电话), 职务JOB(职务,月薪)和部门 DEPT(部门号, 部门名称, 部门电话, 负责人)实体集。一个职务可以由多个职工担任,但一个职工只能担任一个职务,并属于一个部门,部门负责人是一个职工。下图所示的a、b处的实体名分别为(53) ;图中a、b之间为 (54) 联系。

(53)A. DEPT、EMP B. EMP、DEPT C. JOB、EMP D. EMP、JOB (54)A. 1 1 B. * 1 C. 1 * D. * * ● 若关系 R、S 如下图所示,则 R 与 S 自然连接后的属性列数和元组个数分别为(55);??1,4(?3=6(RXS))=(56)。

(55)A. 4和3 B. 4和6 C. 6和3 D. 6和6

5 / 12

● 已知一个线性表(16, 25, 35, 43, 51, 62, 87, 93),采用散列函数H (Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元),则构造的哈希表为(57) ,在该散列表上进行等概率成功查找的平均查找长度为 (58) (为确定记录在查找表中的位置,需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。 (57)A.

0 1 2 3 4 5 6 7 8 35 43 16 51 25 62 87 93 B.

0 1 2 3 4 5 6 7 8 35 43 16 93 25 51 62 87 C.

0 1 2 3 4 5 6 7 8 35 43 16 51 25 87 62 93 D.

0 1 2 3 4 5 6 7 8 35 43 16 51 25 87 62 93 (58)A.(5*1+2+3+6)/8 B.(5*1+2+3+6)/9 C.(8*1)/8 D.(8*1)/9 ● 若将某有序树 T 转换为二叉树 T1,则 T 中结点的后(根)序序列就是 T1 中结点的 (59) 遍历序列。例如,下图(a)所示的有序树转化为二叉树后如图(b)所示。

(59)A. 先序 B. 中序 C. 后序 D. 层序 ● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该矩阵的元素数目为 (60) ,其中非零元素数目为 (61) 。

(60)A. E2 B. N2 C. N2-E2 D. N2+E2 (61)A. N B. N+E C. E D. N–E

● 一个算法是对某类给定问题求解过程的精确描述,算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现,这句话说明算法具有(62) 特性。

(62)A. 有穷性 B. 可行性 C. 确定性 D. 健壮性 ● 斐波那契(Fibonacci)数列可以递归地定义为:

用递归算法求解F(5)时需要执行(63) 次―+‖运算,该方法采用的算法策略是 (64) 。

(63)A.5 B.6 C.7 D.8 (64)A. 动态规划 B. 分治 C. 回溯 D. 分支限界 ● 若总是以待排序列的第一个元素作为基准元素进行快速排序,那么最好情况下的时间复杂度为(65) 。

● 运行Web 浏览器的计算机与网页所在的计算机要建立(66) 连接,采用(67) 协议传输网页文件。 (66)A. UDP B. TCP C. IP D. RIP (67)A. HTTP B. HTML C. ASP D. RPC ● (68) 不属于电子邮件协议。

(68)A. POP3 B. SMTP C. IMAP D. MPLS

● 某客户端在采用ping命令检测网络连接故障时,发现可以ping通127.0.0.1及本机的IP 地址,但无法ping通同一网段内其他工作正常的计算机的IP 地址,说明该客户端的故障是 (69) 。

(69)A. TCP/IP 协议不能正常工作 B. 本机网卡不能正常工作 C. 本机网络接口故障 D. 本机DNS 服务器地址设置错误 ● 用户可以通过http://www.a.com和http://www.b.com访问在同一台服务器上(70)不同的两个Web站点。 (70)A. IP 地址 B. 端口号 C. 协议 D. 虚拟目录

● Object-oriented analysis (OOA) is a semiformal specification technique for the object-oriented paradigm. Object-oriented analysis consists of three steps. The first step is (71). It determines how the various results are computed by the product and presents this information in the form of a (72) and associated scenarios. The second is (73) , which determines the classes and their attributes,

6 / 12

then determines the interrelationships and interaction among the classes. The last step is (74) , which determines the actions performed by or to each class or subclass and presents this information in the form of (75).

(71)A. use-case modeling B. class modeling C. dynamic modeling D. behavioral modeling (72)A. collaboration diagram B. sequence diagram C. use-case diagram D. activity diagram (73)A. use-case modeling B. class modeling C. dynamic modeling D. behavioral modeling (74)A. use-case modeling B. class modeling C. dynamic modeling D. behavioral modeling (75)A. activity diagram B. component diagram C. sequence diagram D. state diagram

2008上半年软件设计师下午试题

试题一(共15分)

阅读以下说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。 【说明】

某音像制品出租商店欲开发一个音像管理信息系统,管理音像制品的租借业务。需求如下:

1. 系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户,系统会为其生成用户名和初始密码。

2. 系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。

3. 根据客户所租借的音像制品的品种,会按天收取相应的费用。音像制品的最长租借周期为一周,每位客户每次最多只能租借6件音像制品。

4. 客户租借某种音像制品的具体流程为:

(1)根据客户提供的用户名和密码,验证客户身份。

(2)若该客户是合法客户,查询音像制品信息文件,查看商店中是否还有这种音像制品。

(3)若还有该音像制品,且客户所要租借的音像制品数小于等于 6 个,就可以将该音像制品租借给客户。这时,系统给出相应的租借确认信息,生成一条新的租借记录并将其保存在租借记录文件中。

(4)系统计算租借费用,将费用信息保存在租借记录文件中并告知客户。

(5)客户付清租借费用之后,系统接收客户付款信息,将音像制品租借给该客户。

5. 当库存中某音像制品数量不能满足客户的租借请求数量时,系统可以接受客户网上预约租借某种音像制品。系统接收到预约请求后,检查库存信息,验证用户身份,创建相应的预约记录,生成预约流水号给该客户,并将信息保存在预约记录文件中。

6. 客户归还到期的音像制品,系统修改租借记录文件,并查询预约记录文件和客户信息文件,判定是否有客户预约了这些音像制品。若有,则生成预约提示信息,通知系统履行预约服务,系统查询客户信息文件和预约记录文件,通知相关客户前来租借音像制品。

图1-1顶层数据流图

【问题1】(1 分)

图1-1中只有一个外部实体E1。使用【说明】中的词语,给出E1的名称。

7 / 12

【问题2】(6 分)

使用【说明】中的词语,给出图1-2中的数据存储D1~D4的名称。 【问题3】(6 分)

数据流图 1-2 缺少了三条数据流,根据说明及数据流图 1-1 提供的信息,分别指出这三条数据流的起点和终点。

起点 终点 【问题 4】(2 分)

在进行系统分析与设计时,面向数据结构的设计方法(如 Jackson 方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。 试题二(共15分)

阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。 【说明】

某地区举行篮球比赛,需要开发一个比赛信息管理系统来记录比赛的相关信息。 【需求分析结果】

1. 登记参赛球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队,一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。 2. 安排球队的训练信息。比赛组织者为球队提供了若干个场地,供球队进行适应性训练。系统记录现有的场地信息,包括:场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地,如表2-1所示。系统记录训练场地安排的信息。

表 2-1 训练安排表 球队名称 场地名称 训练时间 解放军 一号球场 2008-06-09 14:00－18:00 解放军 一号球场 2008-06-12 09:00－12:00 解放军 二号球场 2008-06-11 14:00－18:00 山西 一号球场 2008-06-10 09:00－12:00 3. 安排比赛。该赛事聘请专职裁判,每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别等信息。系统按照一定的规则,首先分组,然后根据球队、场地和裁判情况,安排比赛(每场比赛的对阵双方分别称为甲队和乙队)。记录参赛球队名称、比赛时间、比分、比赛场地等信息,如表2-2所示。

4. 所有球员、教练和裁判可能出现重名情况。

表 2-2 比赛安排表

A组:

甲队——乙队 场地名称 比赛时间 裁判 比分 解放军——北京 一号球场 2008-06-17 15:00 李大明 天津——山西 一号球场 2008-06-17 19:00 胡学梅 B 组:

甲队——乙队 场地名称 比赛时间 裁判 比分 上海----安徽 二号球场 2008-06-17 15:00 丁鸿平 山东----辽宁 二号球场 2008-06-17 19:00 郭爱琪 【概念模型设计】 根据需求阶段收集的信息,设计的实体联系图和关系模式(不完整)如下: 1.实体联系图

2.关系模式

教练(教练编号,姓名,年龄)

队员(队员编号,姓名,年龄,身高,体重, (a) ) 球队(球队名称,代表地区,成立时间, (b) ) 场地(场地名称,场地规模,位置) 训练记录( (c) )

裁判(裁判编号,姓名,年龄,级别)

比赛记录( (d) ) 【问题1】(4 分)

根据问题描述,补充联系及其类型,完善实体联系图2-1。(联系及其类型的书写格式参照教练与球队之间的联系描述,联系名称也可使用联系1、联系2、…) 【问题2】(8 分)

8 / 12

根据实体联系图2-1,填充关系模式中的(a)、(b)、(c)和(d),并给出训练记录和比赛记录关系模式的主键和外键。 【问题3】(3 分)

如果考虑记录一些特别资深的热心球迷的情况,每个热心球迷可能支持多个球队。热心球迷包括:姓名、住址和喜欢的俱乐部等基本信息。根据这一要求修改图 2-1 的实体联系图,给出修改后的关系模式。(仅给出增加的关系模式描述) 试题三(共15分)

阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。 【说明】

某汽车停车场欲建立一个信息系统,已经调查到的需求如下:

1. 在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器,示意图如下:

2. 当汽车到达入口时,驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后,系统命令栏杆自动抬起;汽车通过入口后,入口处的传感器通知系统发出命令,栏杆自动放下。

3. 在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器,并缴纳停车费。付清停车费之后,将获得一张出场卡,用于离开停车场。

4. 当汽车到达出口时,驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的,系统命令栏杆自动抬起;汽车通过出口后,出口传感器通知系统发出命令,栏杆自动放下。若这张卡是无效的,系统不发出栏杆抬起命令而发出告警信号。

5. 系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位,系统将在入口处显示―车位已满‖信息。这时,停车卡打印机将不再出卡,只允许场内汽车出场。

根据上述描述,采用面向对象方法对其进行分析与设计,得到了表 3-1 所示的类/用例/状态列表、图 3-1 所示的用例图、图 3-2 所示的初始类图以及图 3-3 所示的描述入口自动栏杆行为的UML状态图。

9 / 12

【问题 1】(3 分)

根据说明中的描述,使用表3-1给出的用例名称,给出图3-1中U1、U2和U3所对应的用例。 【问题 2】(5 分)

根据说明中的描述,使用表3-1给出的类的名称,给出图3-2中的A~D 所对应的类。 【问题 3】(4 分)

根据说明中的描述,使用表3-1给出的状态名称,给出图3-3中S1~S4所对应的状态。 【问题 4】(3 分)

简要解释图3-1中用例U1和U3之间的extend关系的内涵。 试题四(共15分)

阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。 【说明】

快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下:

分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空) A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。 递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。 合并:快速排序在原地排序,故不需合并操作。 【问题1】(6 分)

下面是快速排序的伪代码,请填补其中的空缺。伪代码中的主要变量说明如下: A:待排序数组

p, r:数组元素下标,从p到r q:划分的位置 x:枢轴元素

i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值 j:循环控制变量,表示数组元素下标

QUICKSORT(A, p, r){

if (p < r){

q = PARTITION(A,p,r) ; QUICKSORT(A, p, q-1); QUICKSORT(A, q+1, r); } }

PARTITION(A, p, r){

x = A[r]; i = p–1;

for (j = p ; j≤r–1; j++){

if (A[j]≤x){

i = i + 1 ;

交换A[i] 和 A[j] }

}

交换 (1) 和 (2) //注:空(1)和空(2)答案可互换,但两空全部答对方可得分 return (3) }

【问题2】(5分)

(1) 假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O记号。最佳情况为 (4),平均情况为 (5) ,最坏情况为 (6) 。

(2) 假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均、最坏)

10 / 12

【问题3】(4分)

(1) 待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码—利用原有的快速排序的划分操作,请填充其中的空缺处。其中,RANDOM(i,j)表示随机取i到j之间的一个数,包括i和j。 RANDOMIZED-PARTITION(A,p,r){ i = RANDOM(p,r);

交换(8)和(9);//注:空(8)和空(9)答案可互换,但两空全部答对方可得分 return PARTITION(A,p,r); }

(2) 随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否 试题五(共15分)

阅读下列说明和C代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】

栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈,进行插入和删除操作的一端称为栈顶(Stack Top),而另一端称为栈底(Stack Bottom)。栈的基本操作包:创建栈(NewStack)、 判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。

当设计栈的存储结构时,可以采取多种方式。其中,采用链式存储结构实现的栈中各数据项不必连续存储(如图5-1)。

以下C 代码采用链式存储结构实现一个整数栈操作。 【C代码】

typedef struct List {

int data; // 栈数据

struct List* next; // 上次入栈的数据地址 }List;

typedef struct Stack {

List* pTop; // 当前栈顶指针 }Stack;

Stack* NewStack() { return (Stack*)calloc(1,sizeof(Stack)); } int IsEmpty(Stack* S){ //判断栈S是否为空栈 if((1)) return 1; return 0; }

int Top(Stack* S){ //获取栈顶数据。若栈为空,则返回机器可表示的最小整数

if( IsEmpty(S) ) return INT_MIN; return (2) ; }

void Push(Stack* S, int theData) {//将数据theData压栈 List* newNode;

newNode = (List*)calloc(1, sizeof(List)); newNode->data = theData; newNode->next = S->pTop; S->pTop = (3) ; }

void Pop(Stack* S) {//弹栈 List* lastTop;

if( IsEmpty(S) ) return; lastTop = S->pTop; S->pTop = (4) ; free(lastTop); }

#define MD(a) a<<2 int main(){ int i;

Stack* myStack;

myStack = NewStack(); Push(myStack, MD(1)); Push(myStack, MD(2)); Pop(myStack);

Push(myStack, MD(3)+1); while( !IsEmpty(myStack) ){ printf(\ Pop(myStack);

11 / 12

} return 0; }

以上程序运行时的输出结果为: (5) 试题六(共15分)

阅读下列说明和C++代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】

已知某企业欲开发一家用电器遥控系统,即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如图 6-1 所示。该遥控器共有 4 个按钮,编号分别是 0 至 3,按钮 0和 2 能够遥控打开电器 1 和电器 2,按钮 1 和 3 则能遥控关闭电器 1 和电器 2。由于遥控系统需要支持形式多样的电器,因此,该系统的设计要求具有较高的扩展性。 现假设需要控制客厅电视和卧室电灯,对该遥控系统进行设计所得类图如6-2所示。

图6-2中, 类RomoteController的方法onPressButton(int button)表示当遥控器按键按下时调用的方法,参数为按键的编

号;Command 接口中 on 和 off 方法分别用于控制电器的开与关;Light中turnLight(int degree)方法用于调整电灯灯光的强弱,参数degree值为0时表示关灯,值为100时表示开灯并且将灯光亮度调整到最大;TV 中setChannel(int channel)方法表示设置电视播放的频道,参数 channel 值为 0 时表示关闭电视,为 1 时表示开机并将频道切换为第1频道。 【C++代码】

class Light{ //电灯类 public:

void turnLight(int degree){ //调整灯光亮度,0表示关灯,100表示亮度最大}; };

class TV{ //电视机类 public:

void setChannel(int channel){//调整频道,0表示关机,1表示开机并切换到1频道}; };

class Command{ //抽象命令类 public:

virtual void on()=0;

virtual void off()=0; };

class RemoteController{ //遥控器类 protected:

Command *commands[4]; //遥控器有4个按钮,按照编号分别对应4个Command对象 public:

void onPressButton(int button){ //按钮被按下时执行命令对象中的命令

if(button % 2 == 0)commands[button]->on(); else commands[button]->off(); }

void setCommand(int button,Command * command){ (1) = command; //设置每个按钮对应的命令对象

} };

class LightCommand : public Command{ //电灯命令类 protected: Light *light; //指向要控制的电灯对象 public:

void on(){light->turnLight(100);}; void off(){light->(2);};

LightCommand(Light * light){this->light = light;}; };

class TVCommand : public Command{ //电视机命令类 protected: TV * tv; //指向要控制的电视机对象 public:

void on(){tv->(3);};

12 / 12

void off(){tv->setChannel(0);}; TVCommand(TV * tv){ this->tv = tv; };

};

void main(){

Light light; TV tv; //创建电灯和电视对象 LightCommand lightCommand(&light); TVCommand tvCommand(&tv); RemoteController remoteController;

remoteController.setCommand(0, (4)); //设置按钮0的命令对象 … //此处省略设置按钮1、按钮2和按钮3的命令对象代码 }

本题中,应用命令模式能够有效让类(5) 和类 (6) 、类 (7) 之间的耦合性降至最小 试题七(15分)

阅读下列说明和Java代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 说明及提示与上题相同。 【Java 代码】

class Light{ //电灯类

public void turnLight(int degree){ //调整灯光亮度,0表示关灯,100表示亮度最大} };

class TV{ //电视机类

public void setChannel(int channel){// 0表示关机,1表示开机并切换到1频道 } };

interface Command{ //抽象命令类 void on();

void off(); };

class RemoteController{ //遥控器类

protected Command []commands = new Command[4]; //遥控器有4个按钮,按照编号分别对应4个Command对象 public void onPressButton(int button){ //按钮被按下时执行命令对象中的命令 if(button % 2 == 0)commands[button].on(); else commands[button].off(); }

public void setCommand(int button, Command command){ (1) = command; //设置每个按钮对应的命令对象 } };

class LightCommand implements Command{ //电灯命令类 protected Light light; //指向要控制的电灯对象 public void on(){light.turnLight(100);}; public void off(){light. (2);};

public LightCommand(Light light){this.light = light;}; };

class TVCommand implements Command{ //电视机命令类 protected TV tv; //指向要控制的电视机对象 public void on(){tv. (3);};

public void off(){tv.setChannel(0);};

public TVCommand(TV tv){this.tv = tv;}; };

public class rs{

public static void main(String []args){

Light light = new Light(); TV tv = new TV();//创建电灯和电视对象 LightCommand lightCommand = new LightCommand(light); TVCommand tvCommand = new TVCommand(tv);

RemoteController remoteController = new RemoteController(); //设置按钮和命令对象 remoteController.setCommand(0, (4));

… //此处省略设置按钮1、按钮2和按钮3的命令对象代码

} }

本文来源：https://www.bwwdw.com/article/2ye3.html