k带图灵机的空间复杂性S（n）是指（）A、k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数B、k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和C、k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数D、k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数

对总例数为N的k个处理组的完全随机设计方差分析，其组间的自由度为

A、N-1

B、N-2

C、k-1

D、k-2

E、N-k

一棵共有n个结点的树，其中所有分支结点的度均为众，则该树中叶子结点的个数为(50)。

A．[n×(k-1)+1]K

B．n×(k-1)k

C．[n×(k+1)+1)k

D．n×(k+1)k

假定输入28，那么程序运行的结果是【 】。

include＜iostream.h＞

void main() {

int n, i，k=0;

cout＜＜“请输入整数”；

cin＞＞n； for(i=1；i＜n；i++)

if(n%i= =0) k=k+i；

if(n= =k)cout＜＜n＜＜“是完数\n”；

else cout＜＜n＜＜“不是完数\n”；

}

有以下程序段,且变量已正确定义和赋值

for（s=1.0,k=1;k<=n;k++） s=s+1.0/（k*（k+1））;

printf（"s=%f\n\n",s）;

请填空,使下面程序段的功能为完全相同

s=1.0;k=1;

while（_[10]_______）{ s=s+1.0/（k*（k+1））; _[11]_______;}

printf（"s=%f\n\n",s）;

A、(n(k+1)-1)/k

B、(n(k+1)+1)/k

C、(n(k-1)+1)/k

D、(n(k-1)-1)/k

下列程序的功能是：输出10到100之间的所有回文素数。所谓回文素数是指，如果一个数是素数，则该数反序后形成的数也是素数。例如，13是素数，13反序形成得到数为31，31也是素数，则称13为回文素数。

Private Sub Command1 2_Click（ ）

Dim k As Integer，m As Integer，n AsInteger

For k=10 T0 100

If prim(k)Then

m=__________

n=0

Do While m>0

N=n*10+Im Mod l0

M=m/10

Loop

If prim(n)Then

MsgBox k&“，”&n

End If

End If

Next k

End Sub

Public Function prim(n As Integer)As Boolean

Dim j As Integer

For j=2 To n／2

If n Mod J=0 Then

prim=__________

Exit Function

End If

Next j

prim=True

Exit Function

End Function

横线处应填写的内容是（ ）。

A.k Fake

B.k True

C.m False

D.n True

试题四（共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上处理。