试分别举出实例说明,在对包含n个元素的序列做起泡排序的过程中,可能发生以下情况:a)任何元素都无需移动(从而内循环仅执行一轮即可终止算法)。b)某元素会一度(朝着远离其最终位置的方向)逆向移动;c)某元素的初始位置与其最终位置相邻,甚至已经处于最终位置,却需要参与n-1次交换;d)所有元素都需要参与n-1次交换。
● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 (矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该矩阵的元素数目为 (60) ,其中非零元素数目为 (61) 。
A.N
B.E
C.2E
D.N+E
(60)
A.N
B.E
C.2E
D.N+E
试题四(共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,将解答写在答题纸的对应栏内。
【说明】
某工程计算中要完成多个矩阵相乘(链乘)的计算任务。
两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数,计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法,计算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) 。
阅读以下说明和C++ 程序,将应填入(n)处的字句写在对应栏内。
[说明]
试从含有n个int 型数的数组中删去若干个成分,使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。
[C++ 程序]
include<stdio.h>
define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a [N];
define n sizeofb/sizeofb[0]
void main ()
{
kit k,i,j;
(1)
(2)
for (i=1;i<n; i++ )
{
for (j=k;(3); j--);
(4); /*长为 j+1 的子序列的终元素存储在 a[j+1]*/
if ((5)k++; /*最长不减子序列长 k 增1*/
}
printf ("K = %d\n ",k );
}
(1)试举出一个个体域及两种解释,分别证明第4题之(1)、(2)的逆不能成立.
(2)证明下列推理无效.
(1)试证明下面的算法Primality能以80%以上的正确率判定给定的整数n是否为素数.另一方面,举出整数n的一个例子,表明算法对此整数n总是给出错误的解答,进而说明该算法不是一个蒙特卡罗算法.
(2)试找出,上述算法Primality中可用于替换整数30030的另一个整数(可使用大整数),使得用此整数代替30030后,算法的正确率提高到85%以上.
阅读以下说明和流程图,将应填入(n)处的字句写在对应栏内。
【说明】
在一个矩阵中,如果其零元素的个数远远多于其非零元素的个数时,称这样的矩阵为稀疏矩阵。稀疏矩阵通常采用三元组数组表示。每个非零元素用一个三元组来表示,即非零元素的行号、列号和它的值。然后按某种顺序将全部非零元素的三元组存于一个数组中。例如,对于以下二维数组:
int x[3][4]={{1,0,0,0},{0,5,0,0),{0,0,7,2}};
可用以下数组a来表示:
int a[][3]={{3,4,4},{0,0,1},{1,1,5),{2,2,7},{2,3,2}};
其中三元数组a的第1行元素的值分别存储稀疏矩阵×的行数、列数和非零元素的个数。
下面的流程图描述了稀疏矩阵转换的过程。
【流程图】
试题四(共15分)
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
【说明】
已知两个整数数组A和B中分别存放了长度为m和n的两个非递减有序序列,函数Adjustment(A,B,m,n)的功能是合并两个非递减序列,并将序列的前m个整数存入A中,其余元素依序存入B中。
合并过程如下:从数组A的第一个元素开始处理。用数组B的最小元素B[0]与数组A的当前元素比较,若A的元素较小,则继续考查A的下一个元素;否则,先将A的最大元素暂存入temp,然后移动A中的元素挪出空闲单元并将B[0]插入数组A,最后将暂存在temp中的数据插入数组B的适当位置(保持B的有序性)。如此重复,直到A中所有元素都不大于B中所有元素为止。
【C函数】
void Adjustment(int A[],int B[],int m,int n)
{ /*数组A有m个元素,数组B有n个元素*/
inti,k,temp;
for(i=0;i<m;i++)
{
if(A[i]<=B[0]) continue,
temp= (1) ;/*将A中的最大元素备份至temp*/
/*从后往前依次考查A的元素,移动A的元素并将来自B的最小元素插入A中*/
for(k= m-1; (2) ;k--)
A[k]=A[k-1];
A[i]=(3) ;
/*将备份在temp的数据插入数组B的适当位置*/
for(k=1; (4) &&k<n;k++)
B[k_1]=B[k];
B[k-1]= (5) ;
}
}
inciude<stdio.h> inciude<stdlib.h> define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } for(i=0;i<n1;i++){ left[i]=arr[p+i]; } left[i]=MAX; for(i=0; i<n2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; (1) ; k++) { if(left[i]> right[j]) { (2) ; j++; }else { arr[k]=left[i]; i++; } } } void mergeSort(int arr[],int begin,int end){ int mid; if((3) ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); (4) ; merge(arr,begin,mid,end); } }
【问题1】 根据以上说明和C代码,填充1-4。 【问题2】 根据题干说明和以上C代码,算法采用了(5)算法设计策略。 分析时间复杂度时,列出其递归式位(6),解出渐进时间复杂度为(7)(用O符号表示)。空间复杂度为(8)(用O符号表示)。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并,根据上述C代码,则元素之间比较次数为(9)。