试题三(共15分)
阅读以下说明和C函数,回答问题 l和问题 2,将解答填入答题纸的对应栏内。
【说明】
对于具有n个元素的整型数组a,需要进行的处理是删除a中所有的值为 0的数组元素,并将a中所有的非 O元素按照原顺序连续地存储在数组空间的前端。下面分别用函数CompactArr_v1 和CompactArr v2来实现上述处理要求,函数的返回值为非零元素的个数。 函数CompactArr_vl(int a[],int n)的处理思路是:先申请一个与数组a的大小相同的动态数组空间,然后顺序扫描数组a的每一个元素,将遇到的非O元素依次复制到动态数组空间中,最后再将动态数组中的元素传回数组a中。
函数CompactArr_v2(int a[],int n)的处理思路是:利用下标i(初值为 0)顺序扫描数组a的每一个元素,下标k(初值为0)表示数组 a中连续存储的非0元素的下标。扫描时,每遇到一个数组元素,i就增 1,而遇到非 0元素并将其前移后k才增 1。
【问题1】 (12分)
请根据说明中函数CompactArr_v1的处理思路填补空缺(1)~(3),根据CompactArr_v2的处理
思路填补空缺(4)。
【问题2】(3分)
请说明函数CompactArr vl存在的缺点。
试题四(共15分)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{S1,S2,...,Sn},且有si≤C(1≤i≤ n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物。
下面分别采用最先适宜策略和最优适宜策略来求解该问题。
最先适宜策略(firstfit)首先将所有的集装箱初始化为空,对于所有货物,按照所给的次序,每次将一个货物装入第一个能容纳它的集装箱中。
最优适宜策略(bestfit)与最先适宜策略类似,不同的是,总是把货物装到能容纳它且目前剩余容量最小的集装箱,使得该箱子装入货物后闲置空间最小。
【C代码】
下面是这两个算法的C语言核心代码。
(1)变量说明
n:货物数
C:集装箱容量
s:数组,长度为n,其中每个元素表示货物的体积,下标从0开始
b:数组,长度为n,b[i]表示第i+1个集装箱当前已经装入货物的体积,下标从0开始
i,j:循环变量
k:所需的集装箱数
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
m:当前所需要的集装箱数
temp:临时变量
(2)函数firstfit
int firstfit(){
inti,j;
k=0:
for(i=0;i<n;i++){
b[i]=0;
}
for(i=0;i<n;i++){
(1);
while(C-b[j]<s[i]){
j++;
}
(2);
k=k>(j+1)?k:(j+1);
}
returnk;
}
(3)函数bestfit
int bestfit() {
int i,j,min,m,temp;
k=0;
for(i=0;i<n;i++){
b[i]=0;
}
For (i=0;i<n;i++){
min=C;
m=k+l;
for(j=O;j< k+l;j++){
temp=C- b[j] - s[i];
if(temp>0&&temp< min){
(3) ;
m=j,
}
}
(4);
k=k>(m+1)?k:(m+1);
}
return k;
}
【问题1】(8分)
根据【说明】和【C代码】,填充C代码中的空(1)~(4)。
【问题2】(4分)
根据【说明】和【C代码】,该问题在最先适宜和最优适宜策略下分别采用了(5) 和(6)算法设计策略,时间复杂度分别为 (7) 和 (8)(用O符号表示)。
【问题3】(3分)
考虑实例n= 10,C= 10,各个货物的体积为{4,2,7,3,5,4,2,3,6,2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况,这两种求解策略能否确保得到最优解?(11) (能或否)
试题四(共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上处理。
阅读下列说明和算法,回答问题1和问题2。
【说明】
算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号,则给出相应的提示信息,如下所示:
文件 提示信息
(1+2)
abc) 缺少对应左括号:第2行,第4列
((def)gx) 缺少对应左括号:第3行,第10列
(((h)
ij)(k
(1ml) 缺少对应右括号:第5行,第4列;第4行,第1列
在算法2-1中,stack为一整数栈。算法中各函数的说明见表4。
【算法2-1】将栈stack 置空,置EOF为false ch < - nextch(); while(not EOF) k < - kind(CH); if(k== (1) ) push((2) );push((3) ); elseif(k== (4) ) if(not empty()) pop() ;pop(); else 显示错误信息(缺少对应左括号或右括号); 显示行号row;显示列号col; endif endif ch < - nextch(); endwhile if(not empty()) 显示错误信息(缺少对应左括号或右括号); while(not empty()) row < - pop() ; col <- pop(); 显示行号row; 显示列号col; endwhile endif 为了识别更多种类的括号,对算法2-1加以改进后得到算法2-2。算法2-2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后,函数kind(char ch)的参数及其对应的返回值见表5。
【算法2-2】
将栈stack置空,置EOF为false
ch< -nextch();
while(not EOF)
k <-kind(ch);
if(k >0)
if(判断条件1 )
push((5));push((6));push((7));
elseif(判断条件2 and 判断条件3 )
pop() ;pop() ;pop();
else
显示行号row; 显示列号col;
endif
endif
ch < - nextch();
endwhile
if(not empty() )
显示错误信息(缺少对应左括号或右括号);
while(not empty() )
pop(); row←pop(); col←pop();
显示行号row;显示列号col;
endwhile
endif
请将【算法2-1】和【算法2-2】中(1)~(7)处补充完整。
在窗体上有一个名称为Check1的复选框数组(含4个复选框),还有一个名称为Textl的文本框,初始内容为空。程序运行时,单击任何复选框,则把所有选中的复选框后面的文字罗列在文本框中(见图)。下面能实现此功能的事件过程是? A. Private Sub Check1_click(Index As Integer) Text1.Text = "" For k = 0 To 3 If Check1(k).Value = 1 Then Text1.Text = Text1.Text & Check1(k).Caption & " "?'双引号中是空格 End If Next k End Sub B. Private Sub Check1_Click(Index As Integer) For k = 0 To 3 If Check1(k).Value = 1 Then Text1.Text = Text1.Text & Check1(k).Caption & " " '双引号中是空格 End If Next k End Sub C. Private Sub Check1_Click(Index As Integer) Text1.Text = "" For k = 0 To 3 If Check1(Index).Value = 1 Then Text1.Text = Text1.Text & Check1(Index).Caption & " " '双引号中是空格 End If Next k End Sub D. Private Sub Check1_Click(Index As Integer) Text1.Text = "" For k = 0 To 3 If Check1(k).Value = 1 Then Text1.Text = Text1.Text & Check1(k).Caption & " " '双引号中是空格 Exit For End If Next k End Sub?
某人为计算n!(0<n<=12)编写了下面的函数过程:
Private Function fun(n As Integer)As Long
Dim P As Long
P=1
For k=n-1 To 2 Step-1
P=P*k
Next k
fun=P
EndFunction
在调试时发现该函数过程产生的结果是错误的,程序需要修改。下面的修改方案中有3种是正确的,错误的方案是
A.把P=1改为P=n
B.把For k=n-1 To 2 Step-1改为For k=1 To n-l
C.把For k=n-1 T02 Step-1改为Fork=1 To n
D.把For k=n-1 To 2 Step-l改为FOr k=2 To n