下半年软件设计师上下午.docx

在输入输出控制方法中,采用(1)可以使得设备与主存间的数据块传送无需CPU干预。(1)A. 程序控制输入输出B. 中断C.DMAD. 总线控制若某计算机采用8位整数补码表示数据,则运算(2)将产生溢出。(2)A. -127+1B. -127-1C. 127+1D. 127-1若内存容量为4GB,字长为32,则(3)。(3)A. 地址总线和数据总线的宽度都为32B. 地址总线的宽度为30,数据总线的宽度为32C. 地址总线的宽度为30,数据总线的宽度为8D. 地址总线的宽度为32,数据总线的宽度为8设用2K4位的存储器芯片组成16K8位的存储器(地址单元为0000H3FFFH,每个芯片的地址空间连续),则地址单元0B1FH所在芯片的最小地址编号为(4)。(4)A. 0000HB.0800HC.2000HD.2800 H编写汇编语言程序时,下列寄存器中程序员可访问的是(5)。(5)A. 程序计数器(PC)B. 指令寄存器(IR)C. 存储器数据寄存器(MDR)D. 存储器地址寄存器(MAR)正常情况下,操作系统对保存有大量有用数据的硬盘进行(6)操作时,不会清除有用数据。(6)A. 磁盘分区和格式化B.磁盘格式化和碎片整理C.磁盘清理和碎片整理D.磁盘分区和磁盘清理如果使用大量的连接请求攻击计算机,使得所有可用的系统资源都被消耗殆尽,最终计算机无法再处理合法用户的请求,这种手段属于(7)攻击。(7)A. 拒绝服务B. 口令入侵C. 网络监听D. IP 欺骗ARP 攻击造成网络无法跨网段通信的原因是(8)。(8)A. 发送大量ARP 报文造成网络拥塞B. 伪造网关ARP 报文使得数据包无法发送到网关C. ARP 攻击破坏了网络的物理连通性D. ARP 攻击破坏了网关设备下列选项中,防范网络监听最有效的方法是(9)。(9)A. 安装防火墙 B. 采用无线网络传输 C. 数据加密 D. 漏洞扫描软件商标权的权利人是指(10)。(10)A. 软件商标设计人B. 软件商标制作人C. 软件商标使用人D. 软件注册商标所有人利用(11)可以对软件的技术信息、经营信息提供保护。(11)A. 著作权B. 专利权C. 商业秘密权D.商标权李某在某软件公司兼职,为完成该公司交给的工作,做出了一项涉及计算机程序的发明。李某认为该发明是自己利用业余时间完成的,可以个人名义申请专利。关于此项发明的专利申请权应归属(12)。(12)A. 李某B. 李某所在单位C. 李某兼职的软件公司D. 李某和软件公司约定的一方一幅彩色图像(RGB),分辨率为256512,每一种颜色用8bit表示,则该彩色图像的数据量为(13)bit。(13)A.2565128B.25651238C.2565123/8D.2565123 10000张分辨率为1024768 的真彩(32位)图片刻录到DVD光盘上,假设每张光盘可以存放4GB的信息,则需要(14)张光盘。(14)A. 7B. 8C. 70D. 71某项目组拟开发一个大规模系统,且具备了相关领域及类似规模系统的开发经验。下列过程模型中,(15)最适合开发此项目。(15)A. 原型模型B. 瀑布模型C.V模型D. 螺旋模型使用 PERT图进行进度安排,不能清晰地描述(16),但可以给出哪些任务完成后才能开始另一些任务。下面PERT图所示工程从A到K 的关键路径是(17),(图中省略了任务的开始和结束时刻)。(16)A. 每个任务从何时开始B. 每个任务到何时结束C. 各任务之间的并行情况D. 各任务之间的依赖关系(17)A. ABEGHIKB. ABEGHJKC. ACEGHIKD. ACEGHJK敏捷开发方法XP 是一种轻量级、高效、低风险、柔性、可预测的、科学的软件开发方法,其特性包含在12 个最佳实践中。系统的设计要能够尽可能早交付,属于(18)最佳实践。(18)A. 隐喻B. 重构C. 小型发布D. 持续集成在软件开发过程中进行风险分析时,(19)活动的目的是辅助项目组建立处理风险的策略,有效的策略应考虑风险避免、风险监控、风险管理及意外事件计划。(19)A. 风险识别B. 风险预测C. 风险评估D. 风险控制以下关于变量和常量的叙述中,错误的是(20)。(20)A. 变量的取值在程序运行过程中可以改变,常量则不行B. 变量具有类型属性,常量则没有C. 变量具有对应的存储单元,常量则没有D. 可以对变量赋值,不能对常量赋值编译程序分析源程序的阶段依次是(21)。(21)A. 词法分析、语法分析、语义分析B. 语法分析、词法分析、语义分析C. 语义分析、语法分析、词法分析D. 语义分析、词法分析、语法分析下图所示的有限自动机中,0是初始状态,3是终止状态,该自动机可以识别(22)。(22)A. ababB. aaaaC. bbbbD. abba进程P1、P2、P3、P4 和P5 的前趋图如下:若用PV操作控制进程P1P5并发执行的过程,则需要设置6 个信号量S1、S2、S3、S4、S5 和S6,且信号量S1S6的初值都等于零。下图中a 和b 处应分别填写(23);c 和d处应分别填写(24),e 和f处应分别填写(25)。(23)A. P(S1)P(S2)和P(S3)P(S4)B. P(S1)V(S2) 和P(S2)V(S1) C. V(S1)V(S2) 和V(S3)V(S4)D. P(S1)P(S2)和V(S1)V(S2)(24)A. P(S1)P(S2)和V(S3)V(S4)B. P(S1)P(S3) 和V(S5)V(S6) C. V(S1)V(S2) 和P(S3)P(S4)D. P(S1)V(S3) 和P(S2)V(S4)(25)A. P(S3)P(S4)和V(S5)V(S6)B. V(S5)V(S6) 和P(S5)P(S6)C. P(S2)P(S5) 和P(S4)P(S6)D. P(S4)V(S5) 和P(S5)V(S6)某磁盘磁头从一个磁道移至另一个磁道需要 10ms。文件在磁盘上非连续存放,逻辑上相邻数据块的平均移动距离为 10 个磁道,每块的旋转延迟时间及传输时间分别为100ms 和2ms,则读取一个100 块的文件需要(26)ms 时间。(26)A. 10200B. 11000C. 11200D. 20200某文件系统采用多级索引结构,若磁盘块的大小为512字节,每个块号需占3字节,那么根索引采用一级索引时的文件最大长度为(27)K字节;采用二级索引时的文件最大长度为(28)K字节。冗余技术通常分为4 类,其中(29)按照工作方法可以分为静态、动态和混合冗余。(29)A. 时间冗余B. 信息冗余C. 结构冗余D. 冗余附加技术以下关于过程改进的叙述中,错误的是(30)。(30)A. 过程能力成熟度模型基于这样的理念: 改进过程将改进产品,尤其是软件产品B. 软件过程改进框架包括评估、计划、改进和监控四个部分C. 软件过程改进不是一次性的,需要反复进行D. 在评估后要把发现的问题转化为软件过程改进计划软件复杂性度量的参数不包括(31)。(31)A. 软件的规模B. 开发小组的规模C. 软件的难度D. 软件的结构根据McCabe 度量法,以下程序图的复杂性度量值为(32)。(32)A.4B.5C.6D.7软件系统的可维护性评价指标不包括(33)。(33)A. 可理解性B. 可测试性C. 可扩展性D. 可修改性以下关于软件系统文档的叙述中,错误的是(34)。(34)A. 软件系统文档既包括有一定格式要求的规范文档,又包括系统建设过程中的各种来往文件、会议纪要、会计单据等资料形成的不规范文档B. 软件系统文档可以提高软件开发的可见度C. 软件系统文档不能提高软件开发效率D. 软件系统文档便于用户理解软件的功能、性能等各项指标以下关于软件测试的叙述中,正确的是(35)。(35)A. 软件测试不仅能表明软件中存在错误,也能说明软件中不存在错误B. 软件测试活动应从编码阶段开始C. 一个成功的测试能发现至今未发现的错误D. 在一个被测程序段中,若已发现的错误越多,则残存的错误数越少不属于黑盒测试技术的是(36)。(36)A. 错误猜测B. 逻辑覆盖C. 边界值分析D. 等价类划分开-闭原则(Open-ClosedPrinciple,OCP)是面向对象的可复用设计的基石。开-闭原则是指一个软件实体应当对(37)开放,对(38)关闭;里氏代换原则(Liskov Substitution Principle,LSP)是指任何(39)可以出现的地方,(40)一定可以出现。依赖倒转原则(Dependence InversionPrinciple, DIP)就是要依赖于(41),而不依赖于(42),或者说要针对接口编程,不要针对实现编程。(37)A.修改B.扩展C.分析D.设计(38)A.修改B.扩展C.分析D.设计(39)A.变量B.常量C.基类对象D.子类对象(40)A.变量B.常量C.基类对象D.子类对象(41)A.程序设计语言B.建模语言C.实现D.抽象(42)A.程序设计语言B.建模语言C.实现D.抽象(43)是一种很强的”拥有”关系,”部分”和”整体”的生命周期通常一样。整体对象完全支配其组成部分,包括它们的创建和销毁等;(44)同样表示”拥有”关系,但有时候”部分”对象可以在不同的”整体”对象之间共享,并且”部分”对象的生命周期也可以与”整体”对象不同,甚至”部分”对象可以脱离”整体”对象而单独存在。上述两种关系都是(45)关系的特殊种类。(43)A.聚合 B. 组合 C. 继承 D. 关联(44)A.聚合 B. 组合 C. 继承 D. 关联(45)A.聚合 B. 组合 C. 继承 D. 关联下面的UML类图描绘的是(46)设计模式。关于该设计模式的叙述中,错误的是(47)。(46)A. 桥接B. 策略C. 抽象工厂D. 观察者(47)A. 该设计模式中的Observer需要维护至少一个Subject对象B. 该设计模式中的ConcreteObserver可以绕过Subject及其子类的封装C. 该设计模式中一个Subject对象需要维护多个Observer对象D. 该设计模式中Subject需要通知Observer对象其自身的状态变化下图所示为两个有限自动机M1 和M2(A是初态、C是终态) ,(48)。(48)A.M1 和M2都是确定的有限自动机B.M1和M2 都是不确定的有限自动机C.M1是确定的有限自动机,M2是不确定的有限自动机D.M1 是不确定的有限自动机,M2 是确定的有限自动机以下关于可视化程序设计的叙述中,错误的是(49)。(49)A. 可视化程序设计使开发应用程序无需编写程序代码B. 可视化程序设计基于面向对象的思想,引入了控件和事件驱动C. 在可视化程序设计中,构造应用程序界面就像搭积木D. 在可视化程序设计中,采用解释方式可随时查看程序的运行效果以下关于汇编语言的叙述中,错误的是(50)。(50)A. 汇编语言源程序中的指令语句将被翻译成机器代码B. 汇编程序先将源程序中的伪指令翻译成机器代码,然后再翻译指令语句C. 汇编程序以汇编语言源程序为输入,以机器语言表示的目标程序为输出D. 汇编语言的指令语句必须具有操作码字段,可以没有操作数字段在某企业的营销管理系统设计阶段,属性”员工”在考勤管理子系统中被称为”员工”,而在档案管理子系统中被称为”职工”,这类冲突称为(51)冲突。(51)A. 语义B. 结构C. 属性D. 命名设有学生实体 Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中”家庭住址”记录了邮编、省、市、街道信息;”家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体 Students 中的”家庭住址”是一个(52)属性;为使数据库模式设计更合理,对于关系模式 Students (53)。(52)A. 简单B. 多值C.复合D. 派生(53)A. 可以不作任何处理,因为该关系模式达到了3NFB. 只允许记录一个亲属的姓名、与学生的关系以及联系电话的信息C. 需要对关系模式Students 增加若干组家庭成员、关系及联系电话字段D. 应该将家庭成员、关系及联系电话加上学生号,设计成为一个独立的实体设有关系模式 R(课程,教师,学生,成绩,时间,教室),其中函数依赖集 F 如下:F课程教师,(学生,课程)成绩,(时间,教室)课程,(时间,教师)教室,(时间,学生)教室关系模式R的一个主键是(54),R规范化程度最高达到(55)。若将关系模式R分解为3个关系模式R1(课程,教师)、R2(学生,课程,成绩)、R3(学生,时间,教室,课程),其中R2 的规范化程度最高达到(56)。(54)A.(学生,课程)B.(时间,教室)C.(时间,教师)D.(时间,学生)(55)A.1NFB.2NFC.3NFD.BCNF(56)A.2NFB.3NFC.BCNFD.4NF设循环队列 Q 的定义中有 rear 和 len 两个域变量,其中 rear 表示队尾元素的指针,len 表示队列的长度,如下图所示(队列长度为 3,队头元素为 e)。设队列的存储空间容量为 M,则队头元素的指针为(57)。(57)A.(Q.rear+Q.len-1)B.(Q.rear+Q.len-1+M)%M C.(Q.rear-Q.len+1)D.(Q.rear-Q.len+1+M)%M下面关于哈夫曼树的叙述中,正确的是(58)。(58)A. 哈夫曼树一定是完全二叉树B. 哈夫曼树一定是平衡二叉树C. 哈夫曼树中权值最小的两个结点互为兄弟结点D. 哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点(59)是右图的合法拓扑序列。(59)A. 6 5 4 3 21B. 1 2 34 5 6C. 5 6 3 4 21D. 5 6 4 21 3某一维数组中依次存放了数据元素15,23,38,47,55,62,88,95,102,123,采用折半(二分)法查找元素95 时,依次与(60)进行了比较。(60)A. 62, 88, 95B. 62, 95C. 55, 88, 95D. 55, 95已知一棵度为3的树(一个结点的度是指其子树的数目,树的度是指该树中所有结点的度的最大值)中有5个度为1的结点,4个度为2的结点,2个度为3的结点,那么,该树中的叶子结点数目为(61)。(61)A.10B.9C.8D.7某算法的时间复杂度可用递归式表示,用表示该算法渐进时间复杂度的紧致界,则正确的是(62)。用动态规划策略求解矩阵连乘问题M1*M2*M3*M4,其中M1(20*5)、M2(5*35)、M3(35*4)和M4(4*25),则最优的计算次序为(63)。下面C程序段中count+语句执行的次数为(64)。for(inti=1;i=11;i*=2)for(intj=1;j=i;j+)count+;(64)A. 15B. 16C. 31D. 32(65)不能保证求得0-1 背包问题的最优解。(65)A. 分支限界法B. 贪心算法C. 回溯法D.动态规划策略公钥体系中,私钥用于(66),公钥用于(67)。(66)A. 解密和签名 B. 加密和签名 C. 解密和认证 D. 加密和认证(67)A. 解密和签名 B. 加密和签名 C. 解密和认证 D. 加密和认证HTTP 协议中,用于读取一个网页的操作方法为(68)。(68)A. READB. GETC. HEADD. POST帧中继作为一种远程接入方式有许多优点,下面的选项中错误的是(69)。(69)A. 帧中继比X.25的通信开销少,传输速度更快B. 帧中继与DDN相比,能以更灵活的方式支持突发式通信C. 帧中继比异步传输模式能提供更高的数据速率D. 租用帧中继虚电路比租用DDN专线的费用低HTML文档中标记的align属性用于定义(70)。(70)A. 对齐方式B. 背景颜色C. 边线粗细D. 单元格边距Peopleareindulginginanillusionwhenevertheyfindthemselves explainingata cocktail(鸡尾酒)party,say,thattheyareincomputers,orintelecommunications,orinelectronicfundstransfer.Theimplication isthattheyarepartofthehigh-tech world.Just betweenus,theyusuallyarent.Theresearcherswhomadefundamentalbreakthroughsinthoseareasare inahigh-techbusiness. The restof us are (71)oftheir work. We use computers andothernewtechnologycomponentstodevelopourproductsortoorganizeouraffairs.Because wego aboutthiswork in teamsandprojectsandothertightlyknitworkinggroups(紧密联系在一起的工作小组),wearemostlyinthehumancommunicationbusiness.Oursuccessesstemfrom goodhumaninteractionsbyallparticipantsintheeffort,andourfailuresstem from poor humaninteractions.Themainreason wetendto focuson the (72)ratherthanthe humansideofthe workisnotbecause itsmore (73), butbecause its easierto do. Gettingthenewdisk drive installed is positivelytrivialcomparedto figuring outwhyHoraceis inabluefunk(恐惧)orwhy Susanisdissatisfied with the company afteronly afewmonths.Human interactionsarecomplicated and neververycrisp(干脆的,干净利落的)andcleanintheireffects,buttheymattermorethananyother aspectofthe work.Ifyou find yourself concentrating on the (74)ratherthan the (75),yourelikethe vaudevillecharacter(杂耍人物)wholoseshiskeysonadarkstreetandlooksforthemontheadjacent streetbecause, as heexplains, The light is better there!.(71)A.creatorsB.innovatorsC.appliersD.inventors(72)A.technicalB.classicalC.sociaD.societal(73)A.trivialB.crucialC.minorD.insignificant(74)A.technologyB.sociologyC.physiologyD.astronomy(75)A.technologyB.sociologyC.physiologyD.astronomy2010 年下半年软件设计师 下午试卷试题一(共15分)阅读以下说明和图,回答问题1 至问题3,将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统,用于处理客户通过电话、传真、邮件或 Web站点所下订单。其主要功能如下:(1)增加客户记录。将新客户信息添加到客户文件,并分配一个客户号以备后续使用。(2)查询商品信息。接收客户提交商品信息请求,从商品文件中查询商品的价格和可订购数量等商品信息,返回给客户。(3)增加订单记录。根据客户的订购请求及该客户记录的相关信息,产生订单并添加到订单文件中。(4)产生配货单。根据订单记录产生配货单,并将配货单发送给仓库进行备货;备好货后,发送备货就绪通知。如果现货不足,则需向供应商订货。(5)准备发货单。从订单文件中获取订单记录,从客户文件中获取客户记录,并产生发货单。(6)发货。当收到仓库发送的备货就绪通知后,根据发货单给客户发货;产生装运单并发送给客户。(7)创建客户账单。根据订单文件中的订单记录和客户文件中的客户记录,产生并发送客户账单,同时更新商品文件中的商品数量和订单文件中的订单状态。(8)产生应收账户。根据客户记录和订单文件中的订单信息,产生并发送给财务部门应收账户报表。现采用结构化方法对订单处理系统进行分析与设计,获得如图1-1所示的顶层数据流图和图1-2 所示0层数据流图。图1-1 顶层数据流图【问题 1】(3 分)使用说明中的词语,给出图1-1 中的实体E1E3 的名称。【问题 2】(3 分)使用说明中的词语,给出图1-2 中的数据存储D1D3的名称。【问题 3】(9 分)(1)给出图1-2 中处理(加工)P1 和P2 的名称及其相应的输入、输出流。(2)除加工P1和P2的输入输出流外,图1-2还缺失了1条数据流,请给出其起点和终点。注:名称使用说明中的词汇,起点和终点均使用图1-2 中的符号或词汇。试题二(共15分)阅读以下说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某公司拟开发一套小区物业收费管理系统。初步的需求分析结果如下:(1)业主信息主要包括:业主编号,姓名,房号,房屋面积,工作单位,联系电话等。房号可唯一标识一条业主信息,且一个房号仅对应一套房屋;一个业主可以有一套或多套的房屋。(2)部门信息主要包括:部门号,部门名称,部门负责人,部门电话等;一个员工只能属于一个部门,一个部门只有一位负责人。(3)员工信息主要包括:员工号,姓名,出生年月,性别,住址,联系电话,所在部门号,职务和密码等。根据职务不同员工可以有不同的权限,职务为”经理”的员工具有更改(添加、删除和修改)员工表中本部门员工信息的操作权限;职务为”收费”的员工只具有收费的操作权限。(4)收费信息包括:房号,业主编号,收费日期,收费类型,数量,收费金额,员工号等。收费类型包括物业费、卫生费、水费和电费,并按月收取,收费标准如表 2-1 所示。其中:物业费=房屋面积(平方米)每平米单价,卫生费=套房数量(套)每套房单价,水费=用水数量(吨)每吨水单价,电费=用电数量(度)每度电单价。(5)收费完毕应为业主生成收费单,收费单示例如表2-2 所示。【概念模型设计】根据需求阶段收集的信息,设计的实体联系图(不完整)如图 2-1 所示。图 2-1 中收费员和经理是员工的子实体。【逻辑结构设计】根据概念模型设计阶段完成的实体联系图,得出如下关系模式(不完整):业主(1) ,姓名,房屋面积,工作单位,联系电话)员工(2),姓名,出生年月,性别,住址,联系电话,职务,密码)部门(3),部门名称,部门电话)权限(职务,操作权限)收费标准(4)收费信息(5),收费类型,收费金额,员工号)【问题 1】(8 分)根据图2-1,将逻辑结构设计阶段生成的关系模式中的空(1)(5)补充完整,然后给出各关系模式的主键和外键。【问题 2】(5 分)填写图 2-1 中(a)(f)处联系的类型(注:一方用1表示,多方用m或n或*表示),并补充完整图2-1 中的实体、联系和联系的类型。【问题 3】(2 分)业主关系属于第几范式?请说明存在的问题。试题三(共15分)阅读下列说明和图,回答问题1 至问题3,将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方,通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下:(1)注册。顾客在买药之前,必须先在网上药店注册。注册过程中需填写顾客资料以及付款方式(信用卡或者支付宝账户)。此外顾客必须与药店签订一份授权协议书,授权药店可以向其医生确认处方的真伪。(2)登录。已经注册的顾客可以登录到网上药房购买药品。如果是没有注册的顾客,系统将拒绝其登录。(3)录入及提交处方。登录成功后,顾客按照”处方录入界面”显示的信息,填写开具处方的医生的信息以及处方上的药品信息。填写完成后,提交该处方。(4)验证处方。对于已经提交的处方(系统将其状态设置为”处方已提交”),其验证过程为:核实医生信息。如果医生信息不正确,该处方的状态被设置为”医生信息无效”, 并取消这个处方的购买请求;如果医生信息是正确的,系统给该医生发送处方确认请求, 并将处方状态修改为”审核中”。如果医生回复处方无效,系统取消处方,并将处方状态设置为”无效处方”。如果医生没有在7 天内给出确认答复,系统也会取消处方,并将处方状态设置为”无法审核”。如果医生在7 天内给出了确认答复,该处方的状态被修改为”准许付款”。系统取消所有未通过验证的处方,并自动发送一封电子邮件给顾客,通知顾客处方被取消以及取消的原因。(5)对于通过验证的处方,系统自动计算药品的价格并邮寄药品给已经付款的顾客。该网上药店采用面向对象方法开发,使用UML进行建模。系统的类图如图3-1 所示。【问题1】(8分)根据说明中的描述,给出图3-1 中缺少的C1C5 所对应的类名以及(1)(6)处所对应的多重度。【问题2】(4分)图3-2 给出了”处方”的部分状态图。根据说明中的描述,给出图3-2中缺少的S1S4 所对应的状态名以及(7)(10)处所对应的迁移(transition)名。【问题 3】(3 分)图 3-1 中的符号”“和”“在 UML 中分别表示类和对象之间的哪两种关系?两者之间的区别是什么?试题四(共15分)阅读下列说明和C代码,回答问题1 至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列a1,a2,an,当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素,则称为小顶堆。堆常用完全二叉树表示,图4-1 是一个大顶堆的例子。堆数据结构常用于优先队列中,以维护由一组元素构成的集合。对应于两类堆结构, 优先队列也有最大优先队列和最小优先队列,其中最大优先队列采用大顶堆,最小优先队列采用小顶堆。以下考虑最大优先队列。假设现已建好大顶堆A,且已经实现了调整堆的函数heapify(A,n, index)。下面将C代码中需要完善的三个函数说明如下:(1)heapMaximum(A):返回大顶堆A中的最大元素。(2)heapExtractMax(A):去掉并返回大顶堆A的最大元素,将最后一个元素”提前” 到堆顶位置,并将剩余元素调整成大顶堆。(3)maxHeapInsert(A,key):把元素key插入到大顶堆A的最后位置,再将A调整成大顶堆。优先队列采用顺序存储方式,其存储结构定义如下:#define PARENT(i) i/2typedefstructarrayint*int_array; /优先队列的存储空间首地址intarray_size;/优先队列的长度intcapacity; /优先队列存储空间的容量ARRAY;【C代码】(1)函数heapMaximumintheapMaximum(ARRAY*A)return (1) ;(2)函数heapExtractMaxintheapExtractMax(ARRAY*A)intmax;max =A-int_array0; (2) ;A-array_size -;heapify(A,A-array_size,0); /将剩余元素调整成大顶堆return max;(3)函数maxHeapInsertintmaxHeapInsert(ARRAY*A,intkey)int i,*p;if(A-array_size =A-capacity) /存储空间的容量不够时扩充空间p=(int*)realloc(A-int_array, A-capacity *2*sizeof(int);if(!p) return-1;A-int_array=p;A-capacity=2 *A-capacity;A-array_size +;i= (3);while (i0 & (4) )A-int_arrayi=A-int_arrayPARENT(i);i=PARENT(i); (5) ;return0;【问题 1】(10 分)根据以上说明和C代码,填充C代码中的空(1)(5)。【问题 2】(3 分)根据以上 C 代码,函数 heapMaximum、heapExtractMax 和 maxHeapInsert 的时间复杂度的紧致上界分别为(6)、(7)和(8) (用 O 符号表示)。【问题 3】(2 分)若将元素10插入到堆A =15,13,9,5, 12,8, 7,4,0,6,2,1中,调用maxHeapInsert函数进行操作,则新插入的元素在堆A中第(9)个位置(从1 开始)。试题五(共15分)阅读下列说明和C+代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图5-1 所示,现采用组合(Composition)设计模式来构造该公司的组织结构,得到如图5-2 所示的类图。其中Company为抽象类,定义了在组织结构图上添加(Add)和删除(Delete)分司/办事处或者部门的方法接口。类ConcreteCompany 表示具体的分公司或者办事处,分公司或办事处下可以设置不同的部门。类HRDepartment和FinanceDepartment分别表示人力资源部和财务部。【C+代码】#include #include #include using namespace std;class Company / 抽象类protected:string name;public:Company(string name) (1) =name; (2) ; / 增加子公司、办事处或部门 (3) ; / 删除子公司、办事处或部门;class ConcreteCompany:public Companyprivate:listchildren; / 存储子公司、办事处或部门public:ConcreteCompany(string name):Company(name) void Add(Company* c) (5) .push_back(c); voidDelete(Company*c) (6) .remove(c);class HRDepartment:public Companypublic:HRDepartment(string name):Company(name) / 其它代码省略;class FinanceDepartment:public Companypublic:FinanceDepartment(string name):Company(name) / 其它代码省略;void main()ConcreteCompany *root=newComcreteCompany(北京总公司);root-Add(newHRDepartment(总公司人力资源部);root-Add(newFinanceDepartment(总公司财务部);ConcreteCompany*comp =newConcreteCompany(上海分公司);comp-Add(newHRDepartment(上海分公司人力资源部);comp-Add(newFinanceDepartment(上海分公司财务部); (7) ;ConcreteCompany*comp1 =newConcreteCompany(南京办事处); comp1-Add(newHRDepartment(南京办事处人力资源部); comp1-Add(newFinanceDepartment(南京办事处财务部); (8) ; /其它代码省略