题目内容
（请给出正确答案）
算法设计:对于给定的维修程序时间表,计算最优时间表.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.n表示仪器的工作时间单位,k是维修程序数.在接下来的k行中,每行有2个表示维修程序的整数s和t,该维修程序从第s个时间单位开始,持续t个时间单位.
结果输出:将计算出的最短维修时间输出到文件output.txt.
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:一台精密仪器的工作时间为n个时间单位.与仪器工作时…”相关的问题
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi ，重量为wi（vi，和wi为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，
，且总重量不超过背包容量，即
，其中，xi∈{0,1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品 放入背包。
【问题1】（8分）
用回溯法求解此0-1背包问题，请填充下面伪代码中（1）~（4）处空缺。
回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）函数，其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下：
W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。
变量说明如下：
cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X）
1 cw ← cp ← 0
2 （1）
3 fp ← -1
4 while true
5 while k≤n and cw＋w[k]≤W do
6 （2）
7 cp ← cp＋v[k]
8 Y[k]← 1
9 k ← k+1
10 if k＞n then
11 if fp＜cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 （3）
20 if k＝0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 （4）
试题四（共15分）
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间（所有作业被处理的时间之和）最少。
算法步骤：
（1）确定候选解上界为R短的单台处理机处理所有作业的完成时间m，
（2）用p（x,y,k）=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间 内处理完成，则p（x,y,k）=p（x-ak,y,k-1）||p（x,y-bk,k-1）（表示逻辑或操作）。
（3）得到最短处理时问为min（max（x，y））。
【C代码】
下面是该算法的C语言实现。
（1）常量和变量说明
n: 作业数
m: 候选解上界
a: 数组，长度为n，记录n个作业在A上的处理时间，下标从0开始
b: 数组，长度为n，记录n个作业在B上的处理时间，下标从0开始
k: 循环变量
p: 三维数组，长度为（m+1）*（m+1）*（n+1）
temp: 临时变量
max: 最短处理时间
（2）C代码
include＜stdio.h＞
int n, m;
int a[60], b[60], p[100][100][60];
void read(){ /*输入n、a、b，求出m，代码略*/}
void schedule(){ /*求解过程*/
int x,y,k;
for（x=0；x＜=m；x++）{
for(y=0；y＜m；y++）{
（1）
for（k=1；k＜n；k++）
p[x][y][k]=0；
}
}
for（k=1；k＜n；k++）{
for（x=0；x＜=m；x++）{
for（y=0；y＜=m；y++）{
if（x - a[k-1]＞=0） （2） ；
if（（3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);
}
}
}
}
void write(){ /*确定最优解并输出*/
int x，y，temp，max=m;
for（x=0；x＜=m；x++）{
for（y=0;y＜=m;y++）{
if(（4） ）{
temp=（5） ；
if（temp＜ max）max = temp;
}
}
}
printf("\n%d\n"，max）,
}
void main(){read();schedule();write();}
【问题1】 （9分）
根据以上说明和C代码，填充C代码中的空（1）～（5）。
【问题2】（2分）
根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。
【问题3】（4分）
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1,x2,x3,x4,x5,x6）表示，其中若第i个作业在A上赴理，则xi=l，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。
A.该公司留购的仪器，不需重新办理“法检”和自动进口许可管理手续
B.该公司留购的仪器，应重新办理“法检”报检手续
C.该公司留购的仪器，应重新办理自动进口许可管理手续
D.该公司应向海关办理进口报关手续，海关以留购价格为基础估价征税
A.该公司留购的仪器，不需重新办理“法检”和自动进口许可管理手续
B.该公司留购的仪器，应重新办理“法检”报检手续
C.该公司留购的仪器，应重新办理自动进口许可管理手续
D.该公司应向海关办理进口报关手续，海关以留购价格为基础估价征税
试题三（15 分）
阅读下列说明，回答问题1 至问题4，将解答填入答题纸的对应栏内。
[说明]
软件系统几乎都是用事件触发来控制流程的，事件触发时的情景便形成了场景，而
同一事件不同的触发顺序和处理结果就形成事件流。场景法就是通过用例场景描述业务
操作流程，从用例开始到结束遍历应用流程上所有基本流（基本事件）和备选流（分支
事件）。下面是对某IC 卡加油机应用系统的基本流和备选流的描述。
[问题1]（5 分）
使用场景法设计测试案例，指出场景涉及到的基本流和备选流，基本流用字母A 表
示，备选流用题干中描述的相应字母表示。
[问题2]（4 分）
场景中的每一个场景都需要确定测试用例，一般采用矩阵来确定和管理测试用例。
如下表所示是一种通用格式，其中行代表各个测试用例，列代表测试用例的信息。本例
中的测试用例包含测试用例ID、场景/条件、测试用例中涉及的所有数据元素和预期结
果等项目。首先确定执行用例场景所需的数据元素（本例中包括账号、是否黑名单卡、
输入油量、账面金额、加油机油量），然后构建矩阵，最后要确定包含执行场景所需的
适当条件的测试用例。在下面的矩阵中，V 表示有效数据元素，I 表示无效数据元素，
n/a 表示不适用，例如C01 表示“成功加油”基本流。请按上述规定为其它应用场景设
计用例矩阵。
测试用例表
[问题3]（3 分）
假如每升油4 元人民币，用户的账户金额为1000 元，加油机内油量足够，那么在
A4 输入油量的过程中，请运用边界值分析方法为A4 选取合适的输入数据（即油量，单
位：升）。
[问题 4]（3 分）
假设本系统开发人员在开发过程中通过测试发现了20 个错误，独立的测试组通过
上述测试用例发现了100 个软件错误，系统在上线后，用户反馈了30 个错误，请计算
缺陷探测率（DDP）。
A.进口转关货物申报单
B.进口货物中转通知书
C.进口货物报关单
D.原产地证书
试题四（15分）
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
某工程计算中要完成多个矩阵相乘（链乘）的计算任务。
两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算Am*n*Bn*p，需要m*n*p次乘法运算。
矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵A110*100，A2100*5，A35*50三个矩阵相乘为例，若按（A1*A2）*A3计算，则需要进行10*100*5+10*5*50=7500次乘法运算；若按A1*（A2*A3）计算，则需要进行100*5*50+10*100*50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。
矩阵链乘问题可描述为：给定n个矩阵＜A1,A2,….An＞，矩阵Ai的维数为pi-1*Pi，其中i = 1,2,….n。确定一种乘法顺序，使得这n个矩阵相乘时进行乘法的运算次数最少。
由于可能的计算顺序数量非常庞大，对较大的n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若A1*A2*…*An的一个最优计算顺序从第k个矩阵处断开，即分为A1*A2*….Ak和Ak+1*Ak+2*…*An两个子问题，则该最优解应该包含A1*A2*…*Ak的一个最优计算顺序和Ak+1*Ak+2*…An的一个最优计算顺序。据此构造递归式，
其中，cost[i][j]表示Ai+1*Ai+2*...Aj+1的最优计算的计算代价。最终需要求解cost[0][n-1]。
【C代码】
算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算3个矩阵、4个矩阵、…、n个矩阵相乘的最小计算量及最优计算顺序。下面是算法的C语言实现。
（1）主要变量说明
n：矩阵数
seq[]：矩阵维数序列
cost[][]：二维数组，长度为n*n，其中元素cost[i][j]表示Ai+1*Ai+2*…Aj+1的最优计算的计算代价
trace[][]：二维数组，长度为n*n，其中元素trace[i][j]表示Ai+1*Ai+2*Aj+1的最优计算对应的划分位置，即k
（2）函数cmm
define N 100
intcost[N][N];
inttrace[N][N];
int cmm(int n,int seq[]){
int tempCost;
int tempTrace;
int i,j,k,p;
int temp;
for(i=0;i＜n;i++){ cost[i][i] =0;}
for(p=1;p＜n;p++){
for(i=0; （1） ;i++){
（2）;
tempCost = -1;
for(k = i;k＜j;k++){
temp = （3） ;
if(tempCost==-1||tempCost＞temp){
tempCost = temp;
（4） ；
}
}
cost[i][j] = tempCost;
trace[i][j] = tempTrace;
}
}
return cost[0][n-1];
}
【问题1】（8分）
根据以上说明和C代码，填充C代码中的空（1）~（4）。
【问题2】（4分）
根据以上说明和C代码，该问题采用了 （5） 算法设计策略，时间复杂度 （6） 。（用O符号表示）
【问题3】（3分）
考虑实例n=6，各个矩阵的维数：A1为5*10，A2为10*3，A3为3*12，A4为12*5，A5为5*50，A6为50*6，即维数序列为5,10,3,12,5,50,6。则根据上述C代码得到的一个最优计算顺序为 （7） （用加括号方式表示计算顺序），所需要的乘法运算次数为 （8） 。
A.优先选取重量最小的物品
B.优先选取效益最大的物品
C.优先选取单位重量效益最大的物品
D.没有任何准则
下列关于Windows 2003系统WWW服务器配置与访问的描述中，正确的是______。
A) Web站点必须配置静态的IP地址
B) 在一台服务器上只能构建一个网站
C) 访问Web站点时必须使用站点的域名
D) 建立web站点时必须为该站点指定一个主目录
●试题三
阅读以下说明，回答问题1至问题5，将解答填入答题纸对应的解答栏内。
［说明］
在一台计算机上安装完成Windows 2000服务器及相应的服务组件。
［问题1］
安装Windows服务器时，通常将分区格式化为NTFS格式，NTFS的主要优点有哪三个方面？
［问题2］
Windows 2000默认的超级用户名是什么？
［问题3］
如果发现操作系统存在安全漏洞，应该如何解决？
［问题4］
为什么要关闭那些不需要的服务和不用的端口？
［问题5］
局域网的IP地址范围限定在192.168.10.33~192.168.10.47之间，子网掩码应设置为多少？
阅读以下技术说明，根据要求回答问题1～问题4。
[说明]
某汽车停车场欲建立一个信息系统，已经调查到的需求如下。
1．在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器等，其示意图见如图3-21所示。
.jpg)
2．当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过入口后，入口处的传感器通知系统发出命令，栏杆自动放下。
3．在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。
4．当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。
5．系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示“车位已满”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。
根据上述描述，采用面向对象方法对其进行分析与设计，得到如表3-11所示的类/用例/状态列表，如图3-22所示的用例图，如图3-23所示的初始类图以及如图3-24所示的描述入口自动栏杆行为的UML状态图。
1.jpg)
根据说明中的描述，使用表3-11给出的用例名称，给出图3-22中U1、U2和U3所对应的用例。
