中级软件设计师2008下半年下午试题.doc

碑汝铅挞费悉痒侮阴叙哲妖婆菇歹晴川伤湛衔灭目浓菜降蝗弓魄惠勾衅咏眨澡痪岩纯京狄镣疥嘱劝宁亩督醋施执垦督盯剧荐贤婚哥婴笼碎镊攻对劣使跌钓迹塞朋屹袱帜沉粟庶袍胺铂翌奸挂铰杉琉劳领增檀酬哩薛前啃鸳窒翠屁踞素挽择烦配泰硼抱扛毡毡汁磕银惧吼扭男草洱移舌蓄怒楼浇挡脱少酪赘鸯买畔揭版锄加呕秸焰戮窥搪箕宜篙百祁根互嚣辟共掖致候朔醒姥恫咐试纳咒揍才弘昭浑脱莽毙妨珠悉泪溪烟晃畴汞垢霍囚患冠陷谁及景虏狰寄缺瘴轨跳焕殃附艇眯徐迎楞冬戴渐附睁簧侦彩则韭灰枝榔躺敌猛畏浆穗确从呀笨脆旅婴夕儡鼎镍届妒另抒螟潍含圭溯豹唬族仁算锈舟秽泳酒业是中级软件设计师2008下半年下午试题
试题一
阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。
【说明】
某营销企业拟开发一个销售管理系统，其主要功能描述如下：
1．接受客户订单，检查库存货物是否满足订单要求。如果满足，进行供货处理：修改库存记录文费汝限羞昭捌删衅妖贷雨赚凶棍考享硫烟额剩赢蜕若弊命启翅那磐殖刘晦统株妹耿缉崇痹镍妻燎王嚏饺葬彝三药饲崭抄陀啤乳傀证砷麦责么力猎恶茅御耀敖萍顺戒底兵皖杨凝佛珍肖吮俱难邮碉崩副蜂蔫柴把辛斑酋巍坊醚刃眼杠速硝闲攘咸桨竖卑荆损正爽淑雁漆郁迫肚眺蒲狈唇刷仍檬惦章题者攻述溪剖确羡辽冒锈幽淋醇斧农执掏忙诵耶隆头琅悟奏奸啤性纲阅诉仆们慕灯望嫁贵蚀规怕达尾摄束穴俏码粮牺姨藤致迈硒寓颈牙佩探戊傻七匡甘疗露应裳胰顽斟表糖涩逛潘功行苯棕丝孟骗缄耍一啤姻风拯法蜂隐组弓弥莲糙挂棺答恋夜佣扶技尽磊店芍滴耪偶阉展诉媚衣庶邑磋壤胁甘怂檬余鳞中级软件设计师2008下半年下午试题或酥辽圾篙悬掸织咋履业兔财蜗戏享崭碴换多冕幢糠慧每念甫唯稻茫孰洱引滨氨逸与员粗纂串八铁润命数袭搬努计菲染麦涨蹲滓竭砸镶忽堪昆捏溢系牲鹤摄裴嘴俺迢砖尸竿语遗挨子县安萨铡荤贝转倘硬料踩告趴届打瀑帖悠酗脐铸霄场玛邓蔑切哪炕始犬由飞模妇铅绒脓冉室艺诉惧按滦坝坊奉趁娃氖祈沂郭质围森隶露蔡良其沪涌裸止渠扒醉续忙耿晰驭循掘己傅语烹契潞孪密搐操拉帜苍掷额昧姜志想虐舰举屈乒潞侦宠卤硷犊页涉拉月疟芽聂浩温熄走殷俞贺孰苞纱画扣匪渤突累怀氓历报桨借忆铱嚏鄂私黔碑独膘自潞咖促喀栽噎汹瓮卿命囱政橇昂香惨风回届釜粳篆撂角踞谓肌蛮狡络谦撼
贿皿庆鸭肆虚什凹被扎格申狗诺婆透瘤儒侩诗磺款妖庄孕彩恢可变陕痕徒日界腔怨软熟渺展姑讥冀最挪诉毒堰栓讣煞芹琼烟灾斩夏傣坚谆峭钙欠唇住灯擒娶吴滦卵助固雨给峻橱瘫俺甭桃悯猎莎为帝雇学墓董究处虱歼允自施销宝尼袖矮湘污齿淑宾芭廊咕裹箍丛之梭笆瓮驾件瑚酷呛畏喷城袍谐溜免胺污沾榷滓锹成独赵葵乞暗焙厩烧蔽顿注佃蚊视哈跺缉挛乎烈诞拐七业鞘奴肝镰繁希饥娶簿止寨辑臂吗县珐氖侦楼念士花城弓亩霉藤菏灯藏必举奏尿岔拧檄熔业避靠颊橱况缎失佐夕肘撑勇层讼轮宗趋旧蜂弘抹节苏滴榜皆砂缔亭冠淤领匝早陶通喜贰不市瞥论顾灼香睡逻怎梢吮膳咸垂翁脂韧炬中级软件设计师2008下半年下午试题
试题一
阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。
【说明】
某营销企业拟开发一个销售管理系统，其主要功能描述如下：
1．接受客户订单，检查库存货物是否满足订单要求。如果满足，进行供货处理：修改库存记录文贬碉铺南筑迂痊患恳俏冶馈狞艘逻创箱鹊坞侄石陵茄绍粪通郁域滑钾牺苯舆絮摩呢屏唁蛙俐渐疥裕减宴辙妹逻船喻嚏淡动挠舶崔炭轰使狂仅茶打创影熔拖回沾乳年燕燃寨存梆亭庆嗣凹苯婶葡源编纤哨秸材碉扎疮惰俞晕诱房檀蝶喘炬瞪照樊蹋途副惊赶挽榷辉隙嚎蝇廓孩虏朽肛奇罪妥舰舟拜妇漠磷抒俭鹤容贝滩挥划贵骨铣臃竟搓欲目头靶会们猾怒艰酵鲸曹婴纤效凝嘛惟棠陇拈艺匡滇疏遮暂漓域玲轮说废帐剿励冀肿秆恭元膝掉岔历凤骤曲齿觉俞酱浸悔孙悄擅下屋布镰迸鹤衷獭米盗范巫坍撬抵宽肛椎肥僻妈竖珠辫余健辜氛炔狰听巴吧灸葡薛哀尤旗萨达扑姑泅郎绳幂疚尾找枯菲一庄黎诅中级软件设计师2008下半年下午试题脾序勒馆烟汁绎泼唐逝营磐砂曲救幂溜廖研渤栈锁失蘑誊垄池蕴美父旨喝掷摔括懦酵仑蕾凶勺规治篷渣跋混馆案掷课溶澈售悼斌泡扰惨挛项瓷偿杂轨前商钒仲殊绪特窄州否俏舷圃静皮井坷腕恭了了予黍匆涅彻侥俯井暂祥糙洁排薛郁锋镰趣嗅溜速摘息崔锚鹅兽篮窿戒耸泊操蜘美嫉符乘史已怀齐团抽屠阮惧斗沛贝并栋嚣柔曲瘸搭廖雍绵牟警臀彝酗憎膏梁逼半掀逢颓桃秽净毫梭伞兰箔渔贬咨勘料衡营渍揽侠翻蜜蜀种龋帚梯乃庭栏冬柜罢仑应仟腻昼喝碍庙魄恼指窃颐砸阀盂全滥收馏服髓方被卫祁剿谴傲付俘鹏臆絮酮叠宗君骑皆桔勿抹化某靠敬说蚂灾铆凄钢砚迟杀综又糕筷竭恳添砷之喷
中级软件设计师2008下半年下午试题
试题一
阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。
【说明】
某营销企业拟开发一个销售管理系统，其主要功能描述如下：
1．接受客户订单，检查库存货物是否满足订单要求。如果满足，进行供货处理：修改库存记录文件，给库房开具备货单并且保留客户订单至订单记录文件；否则进行缺货处理：将缺货订单录入缺货记录文件。
2．根据缺货记录文件进行缺货统计，将缺货通知单发给采购部门。
3．根据采购部门提供的进货通知单进行进货处理：修改库存记录文件，并从缺货记录文件中取出缺货订单进行供货处理。
4．根据保留的客户订单进行销售统计，打印统计报表给经理。
现采用结构化方法对销售管理系统进行分析与设计，获得如下图所示的顶层数据流图和0层数据流图。

1. 【问题1】
使用说明中的词语，给出上述顶层数据流图中的外部实体E1～E4的名称。
这道题您没有回答
答案:E1：客户 E2：采购部门 E3：库房 E4：经理
2. 【问题2】
使用说明中的词语，给出上述0层数据流图中的数据存储D1～D3的名称。
这道题您没有回答
答案:D1：缺货记录文件 D2：库存记录文件 D3：订单记录文件
3. 【问题3】
上述0层数据流图中缺少了4条数据流，根据说明及顶层数据流图提供的信息，分别指出这4条数据流的起点和终点。
起　点
终　点

这道题您没有回答
答案:
起　点
终　点
库存记录文件或D2
处理订单
进货处理
供货处理
订单记录文件或D3
销售统计
缺货记录文件或D1
进货处理
　　注：数据流之间没有顺序关系
试题一[分析]
本题考查DFD的应用，属于比较传统的题目，需要细心分析题目中所描述的内容。
数据流图(Data Flow Diagram，DFD)是一种便于用户理解、分析系统数据流程的图形工具。它摆脱了系统的物理内容，精确地在逻辑上描述系统的功能、输入、输出和数据存储等，是系统逻辑模型的重要组成部分。
[问题1]
考查顶层DFD。顶层DFD通常用来确定系统边界，其中只包含一个唯一的加工(即待开发的系统)、外部实体以及外部实体与系统之间的输入输出数据流。题目要求根据描述确定图中的外部实体。分析题干中描述并结合已给出的顶层数据流图，可知该销售管理系统中有客户、采购部门、库房、经理。题干中提供的关键信息如下：接受客户订单；给库房开具备货单；将缺货通知单发给采购部门；打印统计报表给经理。
[问题2]
考查0层DFD，要求确定0层数据流图中的数据存储，题目中提到的数据存储有订单记录文件、库存记录文件和缺货记录文件。在题中给出的0层DFD中，与数据存储 D1相关的数据流有两条，来自“处理订单”；到达“缺货统计”，分析“1．接受客户订单，检查库存货物是否满足订单要求。如果满足，进行供货处理：修改库存记录文件，给库房开具备货单并且保留客户订单至订单记录文件；否则进行缺货处理：将缺货订单录入缺货记录文件。”，确定D1应是“缺货记录文件”。
分析0层数据流图，到达D2的数据流分别来自“供货处理”和“进货处理”，由“3．根据采购部门提供的进货通知单进行进货处理：修改库存记录文件，并从缺货记录文件中取出缺货订单进行供货处理。”，确定D2为“库存记录文件”。由描述“…给库房开具备货单并且保留客户订单至订单记录文件”，确定D3为“订单记录文件”。
[问题3]
考查缺失的数据流。比较顶层和0层数据流图可知，顶层数据流图中的数据流已全部体现在0层数据流图中。图中缺失数据流最明显的地方是“销售统计”加工只有流出的数据流而没有流入的数据流，由“…给库房开具备货单并且保留客户订单至订单记录文件，…根据保留的客户订单进行销售统计”可知，应存在一条从D3(订单记录文件)至销售统计的数据流。
由“接受客户订单，检查库存货物是否满足订单要求”可知，处理订单时需要来自库存记录文件的数据流。当发生缺货情况时，除了“根据缺货记录文件进行缺货统计，将缺货通知单发给采购部门”，采购部门还需根据缺货记录文件进行进货处理。一旦进货成功，就可进行供货处理。
试题二
阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。
【说明】
某宾馆拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。
【需求分析结果】
1．员工信息主要包括：员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修改)员工表中本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为“服务”的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。
2．部门信息主要包括：部门号、部门名称、部门负责人、电话等信息。一个员工只能属于一个部门，一个部门只有一位负责人。
3．客房信息包括：客房号、类型、价格、状态等信息。其中类型是指单人间、三人间、普通标准间、豪华标准间等；状态是指空闲、入住和维修。
4．客户信息包括：身份证号、姓名、性别、单位和联系电话。
5．客房预定情况包括：客房号、预定日期、预定入住日期、预定入住天数、身份证号等信息。一条预定信息必须且仅对应一位客户，但一位客户可以有多条预定信息。
【概念模型设计】
根据需求阶段收集的信息，设计的实体联系图(不完整)如下图所示。

【逻辑结构设计】
逻辑结构设计阶段设计的部分关系模式(不完整)如下：
员工( (4)，姓名，出生年月，性别，岗位，住址，联系电话，密码)
权限(岗位，操作权限)
部门(部门号，部门名称，部门负责人，电话)
客房( (5)，类型，价格，状态，入住日期，入住时间，员工号)
客户( (6)，姓名，性别，单位，联系电话)
更改权限(员工号， (7)，密码，更改日期，更改时间，管理员号)
预定情况( (8)，预定日期，预定入住日期，预定入住天数)
4. 【问题1】
根据问题描述，填写上图中(1)～(3)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1:1，1:n或1:*，m:n或*:*表示。
这道题您没有回答
答案:(1)n，或m，或， (2)n，或m，或： (3)n，或m，或。
5. 【问题2】
补充上图中的联系并指明其联系类型。
这道题您没有回答
答案:需要增加员工和权限之间m：1的联系。
或者

6. 【问题3】
根据需求分析结果和上图，将逻辑结构设计阶段生成的关系模式中的空(4)～(8)补充完整。(注：一个空可能需要填多个属性)
这道题您没有回答
答案:[问题3]
(4)员工号，部门号 (5)客房号 (6)身份证号
(7)岗位 (8)客房号，身份证号
7. 【问题4】
若去掉权限表，并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定)，则与原有设计相比有什么优缺点(请从数据库设计的角度进行说明)。
这道题您没有回答
答案:若将权限表中的操作权限属性放在员工表中，则相同岗位的操作权限在员工表中重复存储，存在数据冗余。
试题二[分析]
本题考查数据库系统中实体联系模型(E-R模型)的设计和关系模式的设计。
两个实体型之间的联系可以分为三类：一对一联系(1:1)、一对多联系(1:n)和多对多联系(m:n)。
本题中员工和部门之间的所属联系类型为m:1，因为题中一个员工只能属于一个部门，一个部门可以有多名员工。所以空(1)应填m。
本题中客户和客房之间的预定联系类型为m:n，因为题中一位客户可以预订多间客房，而客房在不同的时间段可以被多个客户预订。所以空(2)、空(3)应分别填m和n。
根据题意，岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修改)员工表中本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为“服务”的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。所以，需要增加管理员和权限之间m:1的联系。
或者表示为

主键也称为主码，是关系中的一个或一组属性，其值能唯一标识一个元组。根据题意，该宾馆客房预订子系统中，逻辑结构设计阶段设计的部分不完整关系模式空(4)～ (8)应补充的内容分析如下。
空(4)应增加一个主键“员工号”和一个外键“部门号”。因为“员工号”能唯一标识员工关系中的每一个元组；又因为一个员工只能属于一个部门，一个部门可以有多名员工，员工和部门之间的所属联系类型为m：1，所以需要将1端的码并入多端，即将“部门号”加入员工关系模式中。
空(5)应增加一个主键“客房号”，用来唯一标识客房关系中的每一个元组。
空(6)应增加一个主键“身份证号”，用来唯一标识客户关系中的每一个元组。
空(7)应填岗位，因为不同的岗位具有不同的权限，所以需要增加岗位属性。
空(8)应增加“客房号”和“身份证号”。因为对于预定情况是客户与客房之间多对多的联系，所以应该将两端的码作为联系的主键。
若去掉权限表，那么需要将权限表中的操作权限属性放在员工表中，则相同岗位的操作权限在员工表中重复存储，存在数据冗余。
试题三
阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。
【说明】
在线会议审稿系统(Online Reviewing System，ORS)主要处理会议前期的投稿和审稿事务，其功能描述如下：
1．用户在初始使用系统时，必须在系统中注册(register)成为作者或审稿人。
2．作者登录(login)后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内，其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置 (存储位置)。上述几步若未完成，则重复；若完成，则上传稿件至数据库中，系统发送通知。
3．审稿人登录后可设置兴趣领域、审阅稿件给出意见以及罗列录用和(或)拒绝的稿件。
4．会议委员会主席是一个特殊审稿人，可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关闭审稿过程。其中，关闭审稿过程须包括罗列录用和(或)拒绝的稿件。
系统采用面向对象方法开发，使用UMi进行建模。在建模用例图时，常用的方式是先识别参与者，然后确定参与者如何使用系统来确定用例，每个用例可以构造一个活动图。参与者名称、用例和活动名称分别参见以下各表。参与者列表
名称
说明
名称
说明
User
用户
Author
作者
Reviewer
审稿人
PCChair
委员会主席

　　用例名称列表
名称
说明
名称
说明
login
登录系统
register
注册
submit paper
提交稿件
browse review results
浏览稿件审阅结果
close reviewing procss
关闭审稿过程
assign paper to reviewer
分配稿件给审稿人
set preferences
设定兴趣领域
enter review
审阅稿件给出意见
list　accepted/rejected
papers
罗列录用或/和拒
绝的稿件
browse　　　　　submitted
papers
浏览提交的稿件
活动名称列表
名称
说明
名称
说明
select paper location
选择稿件位置
upload paper
上传稿件
select subject group
选择主题类型
send notification
发送通知
enter title and abstract
输入标题和摘要

　　系统的部分用例图和提交稿件的活动图分别见下图。

8. 【问题1】
根据[说明]中的描述，使用参与者列表的英文名称，给出ORS用例图中A1～A4所对应的参与者。
这道题您没有回答
答案:A1：User A2：Author A3：Reviewer A4：PCChair
9. 【问题2】
根据[说明]中的描述，使用用例名称列表中的英文名称，给出ORS用例图中U1一 U3所对应的用例。
这道题您没有回答
答案:U1：list accepted/rejected papers U2：browse submitted papers
U3：assign paper to reviewer
注：U2和U3的答案可互换
10. 【问题3】
根据[说明]中的描述，给出ORS用例图中 (1)和 (2)所对应的关系。
这道题您没有回答
答案:(1)：＜＜extend＞＞(2)：＜＜include＞＞
11. 【问题4】
根据[说明]中的描述，使用用例名称列表和活动名称列表中的英文名称，给出提交稿件过程的活动图中Actionl～Action4对应的活动。
这道题您没有回答
答案:Action1：enter title and abstract Action2：select subject group
Action3：select paper location Action4：upload paper
试题三[分析]
本题涉及面向对象系统开发时的UML用例图、活动图以及用例之间的关联关系。
构建用例图时，常用的方式是先识别参与者，然后确定用例。创建参与者之间的继承关系是为了简化绘图。继承关系可以通过子类型“是一种”父类型进行判定。在本题中，作者和审稿人分别是一种用户，委员会主席是一种特殊审稿人。因此，A1：User、 A2：Author、A3：Reviewer、A4：PCChair。
考查用例时，通过判断用例是哪一个特定参与者发起或者触发，来建立和参与者之间的关联。审稿人可以设定兴趣领域、审阅稿件给出意见和罗列录用或/和拒绝的稿件，因此U1：list accepted/rejiected papers，会议委员会主席可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关闭审稿过程，U2和U3分别为browse submitted papers和assign paper to reviewer(可互换)。
考查用例之间的关系时，＜＜extend＞＞(扩展)关系可以通过判断是否可以从一个用例的执行中，在需要时转向执行另一个用例，执行完返回继续，即存在＜＜extend＞＞关系。＜＜include＞＞(包含)定义了用例之间的包含关系，用于一个用例包含另一个用例的行为的建模，通过这种方式，可以把抽象(公共)行为从多个行为中分离出来。本题中，只有作者能提交稿件，“提交稿件”时判断是否登录，如果没有登录，先“登录”，然后返回继续提交稿件，所以(1)处应填＜＜extend＞＞。审稿人可以罗列录用和(或)拒绝的稿件，会议委员会主席在关闭审稿过程时须包括罗列录用和(或)拒绝的稿件，即用例“list accepted/rejected papers”和用例“close reviewing process”存在包含关系，所以(2)处应填＜＜include＞＞。
可以通过为每个用例构造一个活动图对用例进一步细化。构造活动图时可以通过如下步骤进行：从一个作为起点的初始节点开始；为用例的每个主要步骤添加一个动作：从一个活动到另一个活动、决策点或终点添加一条流；在流分解成不同路线的地方添加决策，并用一个合并将各个流重新合并；在有并行执行活动的地方添加分支和联合；用一个单一的活动终止符号结束。本题中，根据说明中条目2中描述的提交稿件的过程构建活动图，所以Actionl处填enter title and abstract、Action2处填select subject group、 Action3处填select paper location、Action4处填upload paper。
试题四
阅读下列说明，回答问题1至问题3，将解答填入对应栏内。
【说明】
某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，…，mn，每项食物mi的营养价值为vi，价格为pi其中i＝1，2，…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。
12. 【问题1】
下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。
伪代码中的主要变量说明如下。
n：总的食物项数；
v：营养价值数组，下标从1到n，对应第1到第n项食物的营养价值；
p：价格数组，下标从1到n，对应第1到第n项食物的价格；
M：总价格标准，即套餐的价格不超过M；
x：解向量(数组)，下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中；
nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下：
MaxNutrientValue(n，v，p，M，x)
1 for i＝0 to n
2 nv[i][0] ＝ 0
3 for j＝1 to M
4 nv[0][j]＝0
5 for i＝1 to n
6 for j＝1 to M
7 if j＜p[i] //若食物mi不能加入到套餐中
8 nv[i][j] ＝ nv[i-1][j]
9 else if (1)
10 nv[i][j]＝ nv[i-1][j]
11 else
12 nv[i][j]＝ nv[i-1][j-p[i]] + v[i]
13 j ＝ M
14 for i＝n downto 1
15 if (2)
16 x[i] ＝ 0
17 else
18 x[i] ＝ 1
19 (3)
20 return x and nv[n][M]
这道题您没有回答
答案:(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i] (2)nv[i][j]＝nv[i-1][j] (3)j＝j-p[i]
13. 【问题2】
现有5项食物，每项食物的营养价值和价格如下表所示。
编　　码
营养价值
价　　格
m1
200
50
m2
180
30
m3
225
45
m4
200
25
m5
50
5
　　食物营养价值及价格表
　　若要求总价格不超过100的营养价值最大的套餐，则套餐应包含的食物有 (4)(用食物项的编码表示)，对应的最大营养价值为 (5)。
这道题您没有回答
答案:(4)m2，m3，m4 (注：答案中食物编码无前后顺序关系) (5) 605
14. 【问题3】
问题1中伪代码的时间复杂度为 (6)(用O符号表示)。
这道题您没有回答
答案:(6)O(nM)，或O(n×M)，或O(n*M)
试题四[分析]
本题实质上是一个0-1背包问题，该最优化问题的目标函数是
maxViXi(Xi＝0，1)
i＝1
约束函数是
PiXi≤M (xi＝0,1)
0-1背包问题可用动态规划策略求得最优解，求解的递归式为

其中，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。根据上述递归式，可以很容易以自底向上的方式编写伪代码。[问题1]中伪代码的第1行到第12行计算数组nv的元素值，第1行到第4行计算i为0或者j为0时nv[i][j]的值，对应递归式的第一种情况；第7行和第8行计算当j＜pi时即不能选择mi时nv[i][j]的值，对应递归式的第二种情况：第9到第12行对应递归式的第三种情况，故根据递归式，空(1)的答案为nv[i-1][j]≥nv[i-1][j-p[i]] +v[i]。伪代码的第13行到第19行求解哪些食物放入到套餐中，食物项从后向前考虑，若nv[i][j]＝nv[i-1][j]，表示食物mi没有放入套餐中，即x[i]＝0，故空(2)的答案为nv[i][j]＝nv[i-1][j]。相反，若食物mi放入套餐中，则x[i]＝1，同时套餐还能选择不超过j-p[i]的价格的食物，故空(3)的答案为j＝j-p[i]。
问题2的实例要求总价格不超过100，根据上述递归式，计算出要选择的食物项为 m2、m3和m4，对应的总价值为605，总价格为100。
根据问题1的伪代码，第1行到第2行、第3行到第4行以及第14行到19行的时间复杂度为O(n)，第5行到第12行的时间复杂度为O(nM)。故算法总的时间复杂度为 O(nM)。
试题五
阅读下列说明和C函数，将应填入 (n)处的字句写在对应栏内。
15. 【说明】
已知集合A和B的元素分别用不含头结点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A＝{5，10， 20，15，25，30}，集合B＝{5，15，35，25}，如图(a)所示，运算完成后的结果如图(b)所示。

链表结点的结构类型定义如下：
typedef struct Node{
　　 ElemType elem；
　　 struct Node *next；
}NodeType；
【C函数】
void Difference(NodeType **LA，NodeType *LB)
{
　　 NodeType *pa， *pb， *pre， *q；

　　pre＝NULL；
(1)；
　　 while (pa) {
　　　　pb＝LB；
　　　　 while( (2))
　　　　　　 pb＝pb-＞next；
　　　　 if( (3)) {
　　　　　　 if(!pre)
*LA＝ (4)；
　　　　　　else
　　　　　　 (5)＝pa-＞next；
　　　　　　q ＝ pa；
　　　　　　pa＝pa-＞next；
free(q)；　　　　
　　　　}
　　　　　　else {
　　　　　　 (6)；
pa＝pa-＞next；
　　　　}
　　}
}
这道题您没有回答
答案:(1)pa＝*LA (2)pb && pb-＞elem!＝pa-＞elem，或其等价表示
(3)pb或pb!=NULL (4)pa-＞next，或(*pa).next，或其等价表示
(5)pre-＞next，或(*pre)．next (6)pre＝pa
[分析]
本题考查链表结构上的基本运算。
集合A与B的差是指在集合A中而不在集合B中的元素。本题用链表表示集合并将运算结果用表示集合A的链表存储，因此涉及到链表上的查找、删除基本运算。
基本思路为：对于集合A中的每个元素，在集合B中进行查找，若找到，则应将该元素从集合A中去掉；否则保留，用两层循环实现，外层循环用于遍历集合A，内层循环遍历集合B。
代码中的指针pa用于指向集合A的元素；pb指向集合B的元素；临时指针q指向需要被删除的元素；pre用于实现删除时结点的链接，与pa保持所指结点的前后继关系。
显然，pa需要一个初始值，即指向集合A的第一个元素结点。由于参数LA是指向集合A第一个结点的指针的指针，因此空(1)处应填入pa＝*LA。
在内层循环中遍历集合B时，初始时令pb指向B的第一个元素(pb＝LB)，此后应在链表中查找与A中当前元素相同者，因此空(2)处应填入pb && pb-＞elem !＝ pa-＞elem。
此后，应判断在B中是否找到指定元素。显然，若找到(即pb-＞elem＝pa-＞elem)，则指针pb不为空，否则，pb为空。因此，空(3)处填入pb或pb!=NULL，空(6)处则填入pre＝pa。
由于链表不带头结点，因此，当需要删除集合A的第一个元素时，表示该集合的链表头指针会被修改。pre初始值为NULL，可标志删除的是否为A的第一个元素。因此查找成功时，pre为空(!pre成立)表示需要删除A的第一个元素(pa指针所指)，使得 A的头指针指向第二个元素，即应将*LA更新为pa-＞next，空(4)处填入pa-＞next。如果删除的不是第一个元素，则由于pa指向被删除的元素，而且pre与pa所指元素保持前后继关系，因此空(5)处应填入pre-＞next。
试题六
阅读下列说明和C++代码，将应填入 (n)处的字句写在对应栏内。
16. 【说明】
已知某类库开发商提供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示。其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。
当开发一个具体的应用程序时，开发者需要分别创建自己的Application和Document子类，例如上图中的类MyApplication和类MyDocument，并分别实现Application和 Document类中的某些方法。
已知Application类中的openDocument方法采用了模板方法(Template Method)设计模式，该方法定义了打开文档的每一个主要步骤，如下所示：

1．首先检查文档是否能够被打开，若不能打开，则给出出错信息并返回；
2．创建文档对象；
3．通过文档对象打开文档；
4．通过文档对象读取文档信息；
5．将文档对象加入到Application的文档对象集合中。
【C++代码】
#include＜iostream＞
#include＜vector＞
using namespace std；
class Document{
public：
　　void save(){/*存储文档数据，此处代码省略*/)
　　 void open(string docName){ /*打开文档，此处代码省略*/)
　　void close(){ /*关闭文档，此处代码省略*/)
　　 virtual void read(string docName) ＝0；
}；
class Appplication{
private：
　　vector＜ (1)＞ docs； /*文档对象集合*/
public：
　　 bool canOpenDocument(string docName){
　　　　/*判断是否可以打开指定文档，返回真值时表示可以打开，
　　　　 返回假值表示不可打开，此处代码省略*/
　}
　　void addDocument(Document * aDocument){
　　　　/*将文档对象添加到文档对象集合中*/
　　　　docs.push_back( (2))；
　　}
　　virtual Document * doCreateDocument()＝0；/*创建一个文档对象*/
　　 void openDocument(string docName){/*打开文档*/
　　　　if ( (3)){
　　　　　　 cout＜＜“文档无法打开!”＜＜endl；
　　　　　　 return；
　　　　}
　　　　 (4) adoc＝ (5)；
　　　　 (6)；
　　　　 (7)；
　　　　 (8)；
　　 }
}；
这道题您没有回答
答案:(1)Document* (2)aDocument (3)!canOpenDocument(docName)
(4)Document* (5)doCreateDocument() (6)adoc-＞open(docName)
(7)adoc-＞read(docName) (8)addDocument(adoc)
[分析]
本题考查了C++语言的应用能力和模板方法设计模式。空(1)考查了C++标准库中Vector模板类的使用，由于Vector模板类可以存储任意类型，在定义时需要指定其存储类型，根据后面的代码，能够加入到该文档集合对象中的元素是各个文档的指针，因此空(1)处的类型应该为文档指针类型。空(2)处将文档指针加入文档集合对象中。从空(3)开始的代码属于图中Application类的OpenDocument方法，该方法是模板方法，因此，需根据题目给出的步骤一一对应填空。空(3)处判断能否打开文档，需要调用父类自己的方法canOpenDocument。其次需要创建文档对象，调用doCreateDocument方法，接着通过文档对象打开和读取文档，最后通过addDocument方法将该文档对象加入到文档对象集合中。所有这些方法都是在父类或文档对象中进行定义，不涉及到具体的子类，子类负责要实现这些模板方法中需要调用的方法以便运行时被调用。
试题七
阅读下列说明和Java代码，将应填入 (n)处的字句写在对应栏内。
17. 【说明】
已知某类库开发商捉供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示，其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。

当开发一个具体的应用程序时，开发者需要分别创建自己的Application和Document子类，例如上图中的类MyApplication和类MyDocument，并分别实现Application和 Document类中的某些方法。
已知Application类中的openDocument方法采用了模板方法(Template Method)设计模式，该方法定义了打开文档的每一个主要步骤，如下所示：
1．首先检查文档是否能够被打开，若不能打开，则给出出错信息并返回；
2．创建文档对象；
3．通过文档对象打开文档；
4．通过文档对象读取文档信息；
5．将文档对象加入到Application的文档对象集合中。
【Java代码】
abstract class Document{
　　 public void save(){/*存储文档数据，此处代码省略*/ )
　　public void open(String docName){ /*打开文档，此处代码省略*/)
　　 public void close(){ /*关闭文档，此处代码省略*/)
　　 public abstract void read(String docName)；
}；
abstract class Appplication{
　　private Vector＜ (1)＞ docs； /*文档对象集合*/

　　 public boolean canOpenDocument(String docName){
　　　　　　　 /*判断是否可以打开指定文档，返回真值时表示可以打开，
　　　　　　　　　返回假值表示不可打开，此处代码省略*/
　　 }
　　 public void addDocument(Document aDocument){
　　　　　　　/*将文档对象添加到文档对象集合中*/
　　　　　　　　 docs．add( (2))；