题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
更多“试分别举出实例说明，在对包含n个元素的序列做起泡排序的过程中…”相关的问题
● 设一个包含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行元素的值分别存储稀疏矩阵×的行数、列数和非零元素的个数。
下面的流程图描述了稀疏矩阵转换的过程。
【流程图】
.jpg)
试题四（共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）。
