1. 在 CPU 中，用（ ）给出将要执行的下一条指令在内存中的地址。
A、程序计数器
B、指令寄存器
C、主存地址寄存器
D、状态条件寄存器
2. 以下关于 RISC 和 CISC 计算机的叙述中，正确的是（ ）。
A、RISC 不采用流水线技术，CISC 采用流水线技术
B、RISC 使用复杂的指令，CISC 使用简单的指令
C、RISC 采用很少的通用寄存器，CISC 采用很多的通用寄存器
D、RISC 采用组合逻辑控制器，CISC 普遍采用微程序控制器
3. 采用 DMA 方式传送数据时，每传送一个数据都需要占用一个（ ）。
A、指令周期
B、总线周期
C、存储周期
D、机器周期
4. 以下关于闪存（Flash Memory）的叙述中，错误的是（ ）。
A、掉电后信息不会丢失，属于非易失性存储器
B、以块为单位进行删除操作
C、采用随机访问方式，常用来代替主存
D、在嵌入式系统中可以用 Flash 来代替 ROM 存储器
5. 若磁盘的转速提高一倍，则（ ）。
A、平均存取时间减半
B、平均寻道时间加倍
C、旋转等待时间减半
D、数据传输速率加倍
6. 异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。以下关于中断和异常的叙述中，正确的是（ ）。
A、“DMA 传送结束”、“除运算时除数为 0”都为中断
B、“DMA 传送结束”为中断，“除运算时除数为 0”为异常
C、“DMA 传送结束”为异常、“除运算时除数为 0”为中断
D、“DMA 传送结束”、“除运算时除数为 0”都为异常
7. 下列协议中，属于安全远程登录协议的是（ ）。
A、TLS
B、TCP
C、SSH
D、TFTP
8. 下列攻击类型中，（ ）是以被攻击对象不能继续提供服务为首要目标
A、跨站脚本
B、拒绝服务
C、信息篡改
D、口令猜测
9. 下列算法中属于非对称加密算法的是（ ）。
A、DES
B、RSA
C、AEC
D、MD5
10、SQL 是一种数据库结构化查询语言，SQL 注入攻击的首要目标是（ ）。
A、破坏 Web 服务
B、窃取用户口令等机密信息
C、攻击用户浏览器，以获得访问权限
D、获得数据库的权限
11. 通常使用（ ）为 IP 数据报文进行加密。
A、IPSec
B、PP2P
C、HTTPS
D、TLS
12. 根据《计算机软件保护条例》的规定，对软件著作权的保护不包括（ ）。
A、目标程序
B、软件文档C、源程序
D、开发软件所有的操作方法
13. 甲、乙两互联网公司于 2020 年 7 月 7 日就各自开发的库存管理软件分别申请“宏达”和“鸿达”商标注册，两个库存管理软件相似，甲第一次使用时间为 2019 年 7 月，乙第一次使用时间为2019 年 5 月，此情景下，（ ）能获准注册。
A、 “宏达”
B、“宏达”和“鸿达”均
C、由甲、乙协商哪个
D、“鸿达”
14. A 经销商擅自复制并销售 B 公司开发的 OA 软件光盘已构成侵权，C 企业在未知情形下从 A处购入 100 张并已安装使用，在 C 企业知道了所使用的软件为侵权复制的情形下，以下说法正确的是（ ）。
A、 C 企业的使用行为侵权，须承担赔偿责任
B、 C 企业的使用行为侵权，支付合理费用后可以继续使用这 100 张软件光盘
C、 C 企业的使用行为不侵权，可以继续使用这 100 张软件光盘
D、 C 企业的使用行为不侵权，不需承担任何法律责任
15. 下列关于结构化分析方法的数据字典中加工逻辑的叙述中，不正确的是（ ）。
A、 对每一个基本加工，应该有一个加工逻辑
B、 加工逻辑描述输入数据流变换位输出数据的加工规则
C、 加工逻辑必须描述实现加工的数据结构和算法
D、 结构化语言，判定树和判定表可以用来表示加工逻辑
16. 在软件设计阶段进行模块划分时，一个模块的（ ）。
A、 控制范围应该在其作用范围之内
B、 作用范围应该在其控制范围之内
C、 作用范围与控制范围互不包含
D、 作用范围与控制范围不受任何限制
17. 下面是一个软件项目活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的权重表示活动的持续时间（天），则关键路径长度为（17），在该活动图中，活动（18）晚16 天开始不会影响上班。
A、 20
B、 25
C、 27
D、 48
A、 AC
B、 BE
C、 FI
D、 HJ
19. 下列关于风险的叙述中，不正确的是（ ）。
A、风险是可能发生的事件
B、如果能预测到风险，则可以避免其发生
C、风险是可能会带来损失的事件
D、对于风险进行干预，以期减少损失
20. 算数表达式 a(b+c/d)-e 的后缀式为（ ）。
A、 a b c d/+e
B、 a b c de+/-
C、 ab+c/d-e
D、 abcd/+e-
21. 以编译方式翻译 C/C++源程序的过程中，类型检查在（ ）阶段处理
A、词法分析
B、语义分析
C、语法分析
D、目标代码生成
22. Java 语言符合的特征有（ ）和自动的垃圾回收处理
①采用即时编译
②采用静态优化编译
③对象在堆空间分配
④对象在栈空间分配
A、①③
B、①④
C、②③
D、②④
23. 云计算有多种部署模型(Deployment Models)。若云的基础设施是为某个客户单独使用而构建的，那么该部署模型属于（ ）。
A、公有云
B、私有云
C、社区云
D、混合云
24. 若计算机系统的字长为 128 位，磁盘的容量为 2048GB，物理块的大小为 8MB，假设文件管理系统采用位示图(bitmap）法记录该计算机系统磁盘的使用情况，那么位示图的大小需要（ ）个字
A、1024
B、2048
C、4096
D、8192
25. 进程 P 有 5 个页面，页号为 0-4，页面变换表及状态位、访问位和修改位的含义如下图所示，若系统给进程 P 分配了 3 个存储块，当访问的页面 3 不在内存时，应该淘汰表中页号为（ ）的页面
A、0
B、1
C、2
D、4
26. 进程 P1、P2、P3、P4、P5 和 P6 的前驱图如下所示：
若用 PV 操作控制进程 P1、P2、P3、P4、P5 和 P6 开发执行的过程，需要设置 6 个信号量 S1、S2、S3、S4、S5 和 S6，且信号量 S1~S6 的和值都等于零。下面的进程执行图中 a 和 b 处分别填写（ ），c 和 d 处应分别填写（ ），e 和 f 处应分别填写（ ）。
A、V(S1)和 P(S2)V(S3)
B、P(S1)和 P(S2)V(S3)
C、V(S1)和 V(S2)V(S3)
D、P(S1)和 V(S2)V(S3)
A、P(S2)和 P(S4)
B、V(S4)和 P(S3)
C、P(S2)和 V(S4)
D、V(S2)和 V（S4）
A、P(S4)V(S5)和 V(S6)
B、P(S4)V(S5)和 P(S6)
C、P(S4)P(S5)和 V(S6)
D、P(S4)P(S5)和 P(S6)
29. 关于螺旋模型，下列陈述中不正确的是（ ），（ ）。
A、将风险分析加入到瀑布模型中
B、将开发过程划分为几个螺旋周期，每个螺旋周期大致和瀑布模型相符
C、适合于大规模、复杂且具有高风险的项目
D、可以快速的提供一个初始版本让用户测试
A、支持用户需求的动态变化
B、要求开发人员具有风险分析能力
C、基于该模型进行软件开发，开发成本低
D、过多的迭代次数可能会增加开发成本，进而延迟提交时间
31、模块 A 通过非正常入口转入模块 B 内部，则这两个模块之间是（ ）耦合
A、数据
B、公共
C、外部
D、内容
32. 软件详细设计阶段的主要任务不包括（ ）。
A、数据结构设计
B、算法设计
C、模块之间的接口设计
D、数据库的物理设计
33. 以下关于文档的叙述中，不正确的是（ ）。
A、文档也是软件产品的一部分，没有文档的软件就不能称之为软件
B、文档只对软件维护活动有用，对开发活动意义不大
C、软件文档的编制在软件开发工作中占有突出的地位和相当大的工作量
D、高质量文档对于发挥软件产品的效益有着重要的意义
34、用白盒测试技术对下面流程图进行测试,至少采用（ ）个测试用例才可以实现路径覆盖。
A、3
B、4
C、6
D、8
35. 软件可维护性是一个系统在特定的时间间隔内可以正常进行维护活动的概率。用 MTTF 和MTTR 分别表示平均无故障时间和平均故障修复时间，则软件可维护性计算公式为（ ）。
A、MTTF/(1+MTTF)
B、1/(1+MTTF)
C、MTTR/(1+MTTR)
D、1/(1+MTTR)
36. 某搜索引擎在交付后，开发人员修改了其中的索引方法，使得用户可以更快地得到搜索结果。这种修改属于（ ）维护
A、正确性
B、适应性
C、完善性
D、预防性
37. 面向对象分析时，执行的活动顺序通常是（ ）。
A、认定对象、组织对象、描述对象的相互作用、确定对象的操作
B、认定对象、定义属性、组织对象、确定对象的操作
C、认定对象、描述对象间的相互作用、确定对象的操作、识别包
D、识别类及对象、识别关系、定义属性、确定对象的操作
38、采用面向对象方法进行系统设计时，不应该强迫客户依赖于他们不用的方法，接口属于客户，不属于它所在的类层次结构。即：依赖于抽象，不要依赖于具体，同时在抽象级别不应该有对于细节的依赖。这属于（ ）。
A、单一责任
B、开放-封闭
C、接口分离
D、里氏替换
39. 假设 Bird 和 Cat 是 Animal 的子类,Parrot 是 Bird 的子类，bird 是 Bird 的一个对象，cat 是 Cat的一个对象，parrot 是 Parrot 的一个对象。以下叙述中，不正确的是（39）。假设 Animal 类中定义接口 move(), Bird、Cat 和 Parrot 分别实现自己的 move ()，调用 move()时，不同对象收到同一消息可以产生各自不同的结果，这一现象称为（40）。
A、cat 和 bird 可看作是 Animal 的对象
B、parrot 和 bird 可看作是 Animal 的对象
C、bird 可以看作是 Parrot 的对象
D、parrot 可以看作是 Bird 的对象
A、封装
B、继承C、消息传递
D、多态
41. 当 UML 状态图用于对系统、类或用例的动态方面建模时，通常是对(41)建模。以下 UML 状态图中，假设活动的状态是 A，事件 b=0 发生并且 a>5，发生条件是 c 状态到 d 状态的转换条件的是（42），D 变为活动的状态，有关状态图的叙述中，不正确的是（43）。
A、系统的词汇
B、反应型对象
C、活动流程
D、对象快照
A、一旦状态 A 的 exit 动作完成，或如果当前执行 do 动作，则终止执行
B、一旦状态 A 和 B 的所有动作完成
C、一旦正在进行的状态 A 完成
D、一旦状态 B 的 exit 动作完成
A、动作可以在状态内执行，也可以在状态转换时执行
B、当触发转换的事件发生并且转换没有指定的监护条件时，对象将离开当前状态，并且其 do动作终止
C、when (b=5）称为时间事件D、状态由事件触发
44. 股票交易中，股票代理(Broker)根据客户发出的股票操作指示进行股票的买卖操作，设计如下所示类图。该设计采用（ ）模式将一个请求封装为一个对象，从而使得以用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤销的操作，其中，（ ）声明执行操作的接口。该模式属于（ ）模式，该模式适用于：（ ）。
A、命令（Command）B、观察者（Observer）
C、状态（State）
D、中介者（Mediator）
A、Operation
B、sellOperation/BayOperation/ViewOperation
C、Broker
D、Stock
A、结构类型
B、结构型对象
C、创建类型
D、行为型对象
A、一个对象必须通知其他对象，而它又不能假定其他对象是谁
B、抽象出特执行的动作以参数化某对象
C、一个对象的行为决定于其状态且必须在运行时刻根据状态改变行为
D、一个对象引用其他很多对象并且直接与这些对象通信，导致难以复用该对象
48. 设有描述简单算术表达的上下文无关文法如下，其中 id 表示单字母。
E→E+T|T
T→FT|F
F→id
与使用该文法描述的表达式 a+bcd 相符的语法树为（ ），下图所示有限自动机（DFA）是（ ）。
A、
B、
C、
D、暂无
A、确定的有限自动机，它能识别以 bab 结尾的
B、确定的有限自动机，他不能识别以 bab 结尾的
C、非确定的有限自动机，他能识别以 bab 结尾的
D、非确定的有限自动机，他不能识别以 bab 结尾的
50. 函数 foo、hoo 的含义如下所示，函数调用 hoo(a,x)的两个参数分别采用引用调用（call by reference）和值调用（call by value）方式传递，则函数调用 foo(5)的输出结果为（ ）。
A、2，5
B、2，15
C、13，5
D、13，15
51. 如下图如下 E-R 图中，两个实体 R1、R2 之间有一个联系 E，当 E 的类型为（ ）时必须将 E转换成—个独立的关系模式？
A、1:1
B、1:
C、：1
D、：
52. 给定关系 R (U,F)，其中 U={A,B,C,D,E,H}，F={A→B，B→DH，A→H,C→E}。关系有（ ），F 中（ ）。
A、一个候选码 A
B、2 个候选码 A、B
C、一个候选码 AC
D、两个候选码 A、C
A、不存在传递依赖，但存在冗余函数依赖
B、既不存在传递依赖,也不存在冗余函数依赖
C、存在传递依赖 A→D 和 A→H，但不存在冗余函数依赖
D、存在传递依赖 A→D 和 A→H，并且还存在冗余函数依赖
54. 某销售公司员工关系 E(工号、姓名、部门名、电话、住址)，商品关系 C(商品号、商品名、库存数)和销售关系 EC(工号、商品号、销售数、销售日期)。查询“销售部 1”在 2020 年 11 月 11日销售“HUWEI Mate40”商品的员工工号、姓名、部门名及其销售的商品名，销售数的关系代数表达式为
π1,2,3,7,8( ( ) ( ( ) ( ) ) )
A、σ3=销售部 1(E)
B、σ3=销售部 1(C)
C、σ3=‘销售部 1’(E)
D、σ3=‘销售部 1’(C)
A、π2,3(σ2=‘HUWEI Mate40 ’(C))
B、π1,2(σ2= ‘HUWEI Mate40 ’(C))
C、π2,3(σ2=‘HUWEI Mate40 ’(EC))
D、π1,2(σ2=‘HUWEI Mate40 ’(EC))
A、σ4=‘2020 年 11 月 11 日’(C)
B、σ3=‘2020 年 11 月 11 日’(C)
C、σ4=‘2020 年 11 月 11 日’(EC)
D、σ3=‘2020 年 11 月 11 日’(EC)
57. 设有栈 S 和队列 Q 初始状态为空，数据元素序列 a,b,c,d,e,f 依次通过栈 S，且多个元素从 S 出栈后立即进入队列 Q，若出队的序列是 b,d,f, e, c, a,则 S 中的元素最多时，栈底到栈顶的元素依次为（ ）。
A、a,b,c
B、a,c,d
C、a,c,e,f
D、a,d,f,e
58、当二叉数中的结点数目确定时，（ ）的高度一定是最小的。
A、二叉排序数
B、完全二叉树
C、线索二叉树
D、最优二叉树
59. （ ）是对稀疏矩阵进行压缩存储的方式。
A、二维数组和双向链表
B、三元组顺序表和十字链表
C、邻接矩阵和十字链表
D、索引顺序表和双向链表
60. 设用线性探查法解决冲突构造哈希表，且哈希函数为 H(key)=key%m，若在该哈希表中查找某关键字 e 是成功的且与多个关键字进行了比较，则（ ）。
A、这些关键字形成一个有序序列
B、这些关键字都不是 e 的同义词C、这些关键字都是 e 的同义词
D、这些关键字的第一个可以不是 e 的同义词
61. 对于一个初始无序的关键字序列，在下面的排序方法中，（ ）第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。
①直接插入排序②冒泡排序③简单选择排序④堆排序⑤快速排序⑥归并排序
A、①②③⑥
B、①②③⑤⑥
C、②③④⑤
D、③④⑤⑥
62. 对数组 A=(2,8,7,1,3,5,6,4）构建大顶堆为（ ）（用数组表示）
A、(1,2,3,4,5,6,7,8)
B、(1,2,5,4,3,7,6,8)
C、(8,4,7,2,3,5,6,1)
D、(8,7,6,5,4,3,2,1)
63. 最大尺寸和问题描述为，在 n 个整数（包含负数）的数组 A 中，求之和最大的非空连续子数组,如数组 A= (-2, 11, -4，13, -5，-2) ，其中子数组 B= (11, -4, 13)具有最大子段和 20
(11-4+13=20) 。求解该问题时,可以将数组分为两个 n/2 个整数的子数组最大子段或或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为（ ）。
A、O(nlgn)
B、O(n2)
C、O(n2lgn)
D、O(n3)
64. 在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适用（ ）算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间,则采用的是（ ）
算法策略。
A、分治
B、贪心
C、动态规则
D、回溯
A、动态规则
B、贪心
C、回溯
D、分支限界
66. IPv6 地址长度为（ ）bit。
A、16
B、32
C、64
D、128
67. 在地址栏输入 www,baidu,com，浏览器默认的应用层协议是（ ）。
A、HTTP
B、DNS
C、TCP
D、FTP
68. 使用电子邮件客户端向服务器发送邮件的协议是（ ）。
A、SMTP
B、POP3
C、IMAP4
D、MIME
69. 以下 Windows 系统中用于清除本地 DNS 缓存的命令是（ ）。
A、ipconfig/ release
B、ipconfig/ flushdns
C、ipconfig/ displaydns
D、ipconfig/ registerdns
70. 在网络系统设计时，不可能使所有设计目标都能达到最优，下列措施中最为合理的是（ ）。
A、尽量让最低建设成本目标达到最优
B、尽让最短的故障时间达到最优
C、尽量让最大的安全性目标达到最优
D、尽量让优先级较高的目标达到最优
71. Designing object -oriented software is hard,and designing（ ）object -oriented software is even
harder.You must find pertinent(相关的)objects,factor them into class at the right granularity,define
class interfaces and inheritances,and establish key relationships among them.You design should be
specific to the problem at hand but also（ ）enough to address future problems and requirements.You
also want to avoid redesign,or at least minimize it.Experienced object -oriented designers will tell
you that a reusable and flexible design is difficult if not impossible to get "right" the first time.Before
a design is finished,they usually try to reuse it several times,modifying it each time.Yet experienced object-oriented designers do make good designs.Meanwhile new designers are（ ）by the options available and tend to fall back on non-object-oriented techniques they've used before.lt takes a long time for novices to learn what good object-oriented design is all about.Experienced designers evidently know something inexperienced ones don't.What is it? One thing expert designers know not to do is solve every problem from first principles.Rather, they reuse solutions that have worked for them in the past.When they find a good（ ）.They use it againand again.Such experience is part of what makes them experts.Consequently,you'll find（ ）patterns of classes and communicating objects in many object-oriented systems.
A、runnable
B、right
C、reusable
D、pertinent
A、clear
B、general
C、personalized
D、customized
A、excited
B、shocken
C、surprised
D、overwhelmed
A、tool
B、component
C、system
D、solution
A、recurring
B、right
C、experienced
D、past
1. 数据流图
道闸控制，大概的意思：
道闸控制请求道闸控制系统，道闸控制系统会返回道闸状态，正常同行状态，如果是进场车
辆，….，更新车位空余状态。如果是离场车辆,…….更新车位空余状态。如果道闸控制系统坏了，得不到返回状态，那么通知管理员去维修。管理员收到告警信息，去维修，以利于车辆同行
问题内容：
1. 补充实体 E1-E5（5 分）
2. 补充 D1-D3（3 分）
3. 确实的数据流，起点，终点（4 分）
4. 用结构化语言描述“道闸控制”加工（3 分）
2. 阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
某社区蔬菜团购网站，为规范商品收发流程，便于查询客户订单情况，需要开发个信息系统。
请根据下述需求描述完成该系统的数据库设计。
[需求描述]
(1)记录蔬菜供应商的信息，包括供应商编号、地址和一个电话。
(2)记录社区团购点的信息，包括团购点编号、地址和一个电话。
(3)记录客户信息，包括客户姓名和一个电话。客户可以在不同的社区团购点下订单，不直接
与蔬菜供应商发生联系。(4)记录客户订单信息，包括订单编号、团购点编号、客户电话、订单内容和日期。
[概念模型设计]
根据需求阶段收集的信息，设计的实体联系图(不完整)如图 1-1 所示。
图 1-1 实体联系图
[逻辑结构设计]
根据概念模型设计阶段完成的实体联系图，得出如下关系模式(不完整)：
蔬菜供货商(供货商编号，地址，电话)
社区团购点(团购点编号，地址，电话)
供货(供货商编号，(a)）客户(姓名，客户电话)
订单(订单编号，团购点编号，订单内容，日期，（b）)
问题内容：
【问题 1】(6 分)
根据问题描述，补充图 1-1 的实体联系图。
【问题 2】 (4 分)
补充逻辑结构设计结果中的(a)、(b)两处空缺及完整性约束关系。
【问题 3】(5 分)
若社区蔬菜团购网站还兼有代收快递的业务，请增加新的“快递”实体，并给出客户实体和快递实体之间的“收取’联系，对图 1 进行补充。“快递” 关系模式包括快递编号、客户电话和日期。
3. 阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
某中医医院拟开发一套线上抓药 APP，允许患者凭借该医院医生开具的处方线上抓药，并提供免费送药上门服务。该系统的主要功能描述如下：
(1)注册。患者扫描医院提供的二维码进行注册，注册过程中，患者需提供其病历号，系统根
据病历号自动获取患者基本信息。
(2)登录。已注册的患者可以登录系统进行线上抓药，未册的患者系统拒绝其登陆。
(3)确认处方。患者登录后，可以查看医生开具的所有处方。患者选择需要抓药的处方和数量(需要抓几副药)， 同时说明是否需要煎制。选择取药方式：自行到店取药或者送药上门,若选择送药上门，患者需要提供提供收货人姓名、联系方式和收货地址。系统自动计算本次抓药的费用，患者可以使用微信或支付宝等支付方式支付费用。支付成功之后，处方被发送给药师进行药品配制。
【问题 1】 (7 分)
根据说明中的描述，给出图 3-1 中 A1~ A3 所对应的参与者名称和 U1 ~U4 处所对应的用例名称。
【问题 2】 (5 分)
根据说明中的描述，给出图 3-2 中 C1~C5 所对应的类名。
【问题 3】 (3 分)
简要解释用例之间的 include、extend 和 generalize 关系的内涵。
扫码小程序【软件设计师】完整真题在线估分4. 阅读下列说明和代码，回答问题 1 和问题 2，将解答写在答题纸的对应栏内。
【说明】
凸多边形是指多边形的任意两点的连线均落在多边形的边界或内部。相邻的点连线落在多边形边界上，称为边；不相邻的点连线落在多边形内部，称为弦。假设任意两点连线上均有权重，凸多边形最优三角剖分问题定义为：求将凸多边形划分为不相交的三角形集合，且各三角形权重之和最小的剖分方案。每个三角形的权重为三条边权重之和。
假设 N 个点的凸多边形点编号为 V1,V2,……,VN,若在 VK处将原凸多边形划分为一个三角形V1VkVN，两个子多边形 V1,V2,…,Vk和 Vk,Vk+1,…VN，得到一个最优的剖分方案，则该最优剖分方案应该包含这两个子凸边形的最优剖分方案。用 m[i][j]表示带你 Vi-1,Vi,…Vj构成的凸多边形的最优剖分方案的权重，S[i][j]记录剖分该凸多边形的 k 值。
则
其中：W(Vi-1VkVj)=Wi-1,k＋Wk,j＋Wj,i-1为三角形 Vi-1VkVj的权重，Wi-1,k,Wk,j，Wj,i-1分别为该三角形三条边的权重。求解凸多边形的最优剖分方案，即求解最小剖分的权重及对应的三角形集。
[C 代码]
＃include＜stdio.h＞
＃define N 6 //凸多边形规模
int m[N＋1] [N＋1]; //m[i][j]表示多边形 Vi-1到 Vj最优三角剖分的权值
int S[N＋1] [N＋1]； //S[i][j]记录多边形 Vi-1到 Vj最优三角剖分的 k 值
int W[N＋1] [N＋1]； //凸多边形的权重矩阵，在 main 函数中输入
/三角形的权重 a，b，c，三角形的顶点下标/
int get_ triangle_weight（int a，int b，int c）{
return W[a][b]＋W[b][c]＋W[c][a];
}
/求解最优值/
void triangle_partition(){
int i,r,k,j;
int temp;
/初始化/
for(i=1;i<=N;i++){
m[i][i]=0;
}
/自底向上计算 m，S/
for(r=2;（1）;r++){/r 为子问题规模/
for(i=1;k<=N-r+1;i++){
（2）;
m[i][j]= m[i][j]+m[i+1][j]+get_triangle_weight(i-1,i,j); /k=j/
S[i][j]=i;
for(k=j+1;k<j;k++){/计算 [i][j]的最小代价/
temp=m[i][k]+m[k+1][j]+ge_triangle_ weight(i-1,k,j);if((3)){/判断是否最小值/
m[i][j]=temp;
S[i][j]=k;
}
}
}
}
}
/输出剖分的三角形 i，j：凸多边形的起始点下标/
void print_triangle(int i,int j){
if(i==j) return;
print_triangle(i,S[i][j]);
print_ triangle((4));
print(“V%d- -V%d- -V%d\n“,i-1,S[i][j],j);
}
问题内容：
【问题 1】（8 分）
根据题干说明，填充 C 代码中的空（1）~（4）。
【问题 2】（7 分）
根据题干说明和 C 代码，该算法采用的设计策略为（5）。
算法的时间复杂度为（6），空间复杂度为（7）（用 O 表示）
6. 阅读下列说明和 Java 代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
层叠菜单是窗口风格的软件系统中经常采用的一种系统功能组织方式。层叠菜单（如图 6-1 示例）中包含的可能是一个菜单项（直接对应某个功能），也可能是一个子菜单，现在采用组合（composite）设计模式实现层叠菜单，得到如图 6-2 所示的类图
层叠菜单（如图 6-1 示例）暂缺
图 6-2 类图
问题内容：
import java.util.；
abstract class MenuComponent { // 构成层叠菜单的元素
（1） String name; // 菜单项或子菜单名称
public viod printName() { System.out.println(name); }
public （2） ;
public abstract boolean removeMenuElement(MenuComponent element);
public (3) ;
}
class MenuItem extends MenuComponent {
public MenuItem(String name) { this.name=name; }
public boolean addMenuElement(MemuComponent element) { return false; }
public boolean removeMenuElement(MenuComponent element){ return false; }
public List<MenuComponent> getElement(){ return null; }
}
class Menu extends MemuComponent {
private (4);
public Menu(String name){
this.name = name;
this.elementList = new ArrayList<MenuComponent>;
}
public boolean addMenuElement(MenuComponent element){
return elementList.add(element);
}
public boolean removeMenuElement(MenuComponent element){return elementList.remove(element);
}
public List<MenuComponent> getElement() {return elementList;}
}
class CompositeTest {
public static void main(String[] args) {
MenuComponent mainMenu = new Menu(“AB”); //此处字符不清晰，以“AB”代替原文
MenuComponent subMenu = new Menu(“Chart”);
MenuComponent element = new MenuItem(“On This Sheet”);
(5);
subMenu.addMenuElement(element);
printMenus(mainMenu);
}
private static void printMenus(MenuComponent ifile){
ifile.printName();
List<MenuComponent> children = ifile.getElement();
if(children == null) return; //打印
for(MenuComponent element; children){
printMenus(element);
}
}
}
本文内容由小幸软考社整理提供，需要电子版或其他软考备考资料请关注后在后台联系我。
