|
|
问题：
请教：2011年11月软考软件设计师-下午试题（标准参考答案版）第4大题第1小题如何解答？
【题目描述】
试题四（共15分）
阅读下列说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。
采用回溯法来求解该问题：
首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{l，2，…，m}，将解空间用树形结构表示。
接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(C11)是否超过上限(cc)，重量(W11)是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(C11+C21)是否超过上限(cc)，重量（W11+W21）是否比当前已知的解（最小重量）大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。
【C代码】
下面是该算法的C语言实现。
(1)变量说明
n：机器的部件数
m:供应商数
cc:价格上限
w[][]：二维数组，w[j]表示第j个供应商供应的第i个部件的重量
c[][]：二维数组，c[j]表示第j个供应商供应的第i个部件的价格
best1W:满足价格上限约束条件的最小机器重量
bestC:最小重量机器的价格
bestX[]．最优解，一维数组，bestX表示第i个部件来自哪个供应商
cw:搜索过程中机器的重量
cp：搜索过程中机器的价格
x[]：搜索过程中产生的解，x表示第i个部件来自哪个供应商
i：当前考虑的部件，从0到n-l
j：循环变量
(2)函数backtrack
Int n=3；
Int m=3；
int cc=4：
int w[3][3]={{1,2,3},{3,2,1}，{2,2,2}};
int c[3][3]={{1,2,3},{3,2,1},{2,2,2}};
int bestW=8；
int bestC=0；
int bestX[3]={0，0，0}；
int cw=0；
int cp=0；
int x[3]={0，0，0}；
int backtrack(int i){
int j=0；
int found=0；
if(i＞n-1){/*得到问题解*/
bestW= cw;
bestC= cp;
for(j=0；j＜n；j++){
(1)____；
}
return 1；
}
if(cp＜=cc){/*有解*/
found=1；
}
for(j=0； (2)____;j++){
/*第i个部件从第j个供应商购买*/
(3) ；
cw=cw+w[j]；
cp=cp+c[j]；
if(cp＜=cc && (4) {/*深度搜索，扩展当前结点*/
if(backtrack(i+1)){found=1;}
}
/*回溯*/
cw= cw -w[j]；
(5) ；
}
return found;
}
从下列的2道试题（试题五和试题六）中任选1道解答。
如果解答的试题数超过1道，则题号小的1道解答有效。
【我提交的答案】：
【参考答案分析】：
(1) bestX[j]=x[j]
(2)j＜m
(3)x=j
(4)cw＜ bestW
(5) cp= cp - c[j]
【我的疑问】（如下，请求专家帮助解答）
cw＜ bestW
不是应该是cw＜ =bestW
更多“请教：2011年11月软考软件设计师-下午试题（标准参考答案版）第4大题第1小题如何解答？”相关的问题
第1题
请教：2007年嵌入式系统设计师上午试卷第1大题第49小题如何解答？
【题目描述】
| 【我提交的答案】： D | 【参考答案与解析】：
正确答案：C |
答案分析：
【我的疑问】（如下，请求专家帮助解答）
第2题
请教：2010年下半年软考嵌入式系统设计师－下午试题（标准参考答案版）第1大题如何解答？
【题目描述】
试题一 （共15 分）
阅读以下关于某嵌入式系统设计方案的叙述，回答问题 1 至问题3，将答案填入答题纸的对应栏内。
【说明 】
通常计算机按其体系结构分为冯·诺依曼（Von neumann）结构和哈佛（Harvard）结构。冯·诺伊曼结构，也称普林斯顿结构，是一种将程序指令存储器和数据存储器合并在一起的存储器结构。哈佛结构是一种将程序指令存储和数据存储分开的存储器结构。复杂系统的不同处理器可采用不同类型体系结构。
某嵌入式系统由数据处理模块、信号处理模块和光纤网络交换模块组成，如图 1-1所示。其中数据处理模块的主处理器选用 PPC7447，内部集成了二级 CACHE，并有SDAM存储器、FLASH、NvRAM、实时时钟、FC(Fabric Channel)通信接口、以太网接口和 RS232 接口；信号处理模块采用 DSP TMS320C6000，并有 FC 通信接口、RS232
接口，用于SPM与外部数据通信；光纤网络交换模块提供FC 协议交换能力，主要由控制单元和交换单元两部分组成。
本嵌入式系统的数据处理模块主要接收外部命令、控制系统运行、与系统其它模块通讯；信号处理模块主要进行图形图像处理，需要较大的运算量和较高的运算速度。
【 问题1】（6 分）
回答下列问题，将答案填写在答题纸对应的栏目中。
本嵌入式系统的数据处理模块采用 （1） 体系结构，信号处理模块采用 （2） 体系结构。
在设计中断时，中断触发方式一般分为沿中断和电平中断。沿中断利用 （3） 或 （4） 作为中断触发信号, 电平中断利用 （5） 或 （6） 作为中断触发信号。
【 问题2 】（5 分）
在设计数据处理模块 DPM 时，假设某桥芯片内部集成一路递增定时器，定时器位宽为32位，最高位为控制使能位，输入时钟为25MHz。请回答下面三个问题，将答案填写在答题纸对应的栏目中（给出表达式即可）。
（1）该定时器最长定时时间是多少（单位ns）？
（2）设置10ms定时时间，则定时器的初值为多少？
（3）若改为一路递减定时器，设置10ms定时时间，则定时器的初值为多少？
【 问题 3】（ 4分）
嵌入式系统底层FC通讯驱动对大数据采用DMA数据传输。图1-2是未完成的DMA数据传输工作流程图，请从下面①～⑧中选择正确的答案，完成该图，将答案填写在答题纸的对应栏中。
备选答案：
① 字计数器计数
②DMA 发送中断
③DMA 响应
④ DMA 接收4个字节
⑤ 发送内存地址
⑥ 再次修改内存地址
⑦ 传送结束
⑧ 继续传送
【我提交的答案】：冯.诺伊曼结构，哈佛结构
【参考答案分析】：
试题一（共15分）
【问题1】（6分，每空1分）
（1） 冯.诺依曼 或Von neumann
（2） 哈佛 或Harvard
（3）～（4）：答案次序无关。答案为：上升沿、下降沿
（5）～（6）：答案次序无关。答案为：高电平、低电平
【问题2】（5分）
（1）40*231或85899345920 （1分）
（2）10*106/40或250000 （2分）
（3）231-10*106/40或2147233648 （2分）
【问题3】（4分，每空1分）
（1）DMA响应，或③
（2）发送内存地址，或⑤
（3）字计数器计数，或①
（4）传送结束，或⑦
【我的疑问】（如下，请求专家帮助解答）
递增定时器和递减定时器是如果触发的 ？
第3题
请教：2009年上半年软件设计师上午试卷第1大题第2小题如何解答？
【题目描述】
| 【我提交的答案】： C | 【参考答案与解析】：
正确答案：B |
答案分析：
【我的疑问】（如下，请求专家帮助解答）
不会izuo
第4题
网页制作
在dw中怎样制作1234类动画
第5题
系统架构师设计师考试 试题分类精解与题型练习 操作系统试题 第一题
进程P2优先级中，使用资源R3（40ms）->CPU（30ms）->R2（20ms）
在分析（3）中为什么P2只使用10msCPU就释放？
第6题
IT领域里的创意设计具体是做什么？
第7题
IDE中如何显示行号？
使用silicon lab IDE，如何在源代码窗口中显示行号啊？
第8题
请教：2010年下半年计算机二级C语言考试模拟试卷四第1大题第31小题如何解答？
【题目描述】
| 【我提交的答案】：C | 【参考答案与解析】：
正确答案：B |
答案分析：
【我的疑问】（如下，请求专家帮助解答）
为什么k数组中原来的0没有被包括在内
第9题
请教：2011年全国计算机等级考试二级VB全真模拟试卷(1)第1大题第5小题如何解答？
【题目描述】
第 5 题</STRONG>
| 【我提交的答案】：A | 【参考答案与解析】：
正确答案：C |
答案分析：
【我的疑问】（如下，请求专家帮助解答）
就是a和x的值是上次的，还是最开始的，搞不清
第10题
请教：2008年下半年《系统分析师》上午试题(参考答案版)第1大题第43小题如何解答？
【题目描述】
● 如图，某大型企业的厂区 A（有空气污染）与生活区 B 拟建于一条大河的两侧，其坐标表示大致为（单位：公里） ：厂区位于点A(0，3)，生活区位于点B(2.5，0)，河的两岸分别为直线Y=1与Y=1.5。为方便企业职工在厂区与生活区之间来往，还需要在该条河上建一座垂直于两岸的桥。为使企业职工通过该桥往来厂区与生活区之间的距离最短，桥应建在坐标X= （58） 处。
（58）
A. 1
B. 1.25
C. 1.5
D. 2
| 【我提交的答案】： B | 【参考答案与解析】：
正确答案：C |
答案分析：
【我的疑问】（如下，请求专家帮助解答）
专家您好，我算出来的是B 1.25麻烦您给解释下，多谢！ |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有帐号？立即注册
x
|
发表于 2022-5-13 15:17:19
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
QQ登录
