一桌宴席的所有凉菜上齐后，热菜共有7个，其中，3个川菜：K、L、M；3个粤菜：Q、N、P；一个鲁菜：X。每次只上一个热菜，上菜的顺序必须符合下列条件： （1）不能连续上川菜，也不能连续上粤菜； （2）除非第三个上Q，否则P不能在Q之前上。 （3）P必须在X之前上。 （4）M必须在K之前上，K必须在N之前上。 如果第三个上M，以下哪一项陈述可能真（）A第五个上XB第一个上QC第六个上LD第四个上K

某部队为了协助开展反恐斗争，从一组7个人——J、K、L、M、N、P和Q中恰好选出4个参加反恐演习。对参加人员的选择必须遵循以下条件。

(1) 要么J被选，要么K被选，但两人不能同时被选。

(2) 要么N被选，要么P被选，但两人不能同时被选。

(3) 若N被选时，L肯定被选。

(4) Q被选时，K肯定被选。

下面哪4个人可能被选择去参加反恐演习?

A．J、K、M、P

B．J、L、N、Q

C．J、M、N、Q

D．K、M、P、Q

如果一棵二叉树结点的前序序列是M、N、P、Q，后序序列是Q、P、N、M，则该二叉树结点的对称序序列（ ）。A．必为M、Q、P、NB．必为M、N、Q、PC．必为Q、N、P、MD．不能确定

设有关键码序为（Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E），采用二路归并排序法进行排序，下面哪一个序列是第二趟归并后的结果？

A．G,Q,M,Z,A,N,B,P,H,X,S,Y,L,T,E,K

B．G,M,Q,Z,A,B,N,P,H,S,X,Y,E,K,L,T

C．G,M,Q,A,N,B,P,X,H,Y,S,T,L,K,E,Z

D．A,B,G,M,N,P,Q,Z,E,H,K,L,S,T,X,Y

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

以下程序运行后的输出结果【 】。

struct NODE

{int k；

struct NODE *link；

}；

main()

{structNODEm[5]，*p=m,*q=m+4；

int i=0；

while(p!=q){

p-＞k=++i；p++；

q-＞k=i++；q-；

}

q-＞k=i；

for(i=0；i＜5；i++)printf("%d",m[i].k)；

printf("\n")；

}

设有关键码序列(Q，C，M，Z，A，N，B，P，X，H，Y，S，T，L，K，E)，采用二路归并排序法进行排序，下面哪—个序列是第二趟归并后的结果?

A．C，Q，M，Z，A，N，B，P，H，X，S，Y，L，T，E，K

B．C，M，Q，Z，A，B，N，P，H，S，X，Y，E，K，L，T

C．C，M，Q，A，N，B，P，X，H，Y，S，T，L，K，E，Z

D．A，B，C，M，N，P，Q，Z，E，H，K，L，S，T，X，Y

设有关键码序列(Q，G，M，Z，A，N，B，P，X，H，Y，S，I，T，K，E)，采用二路归并排序法进行排序，第二趟归并后的结果是

A．G，Q，M，Z，A，N，B，P，H，X，S，Y，L，丁，E，K

B．G，M，Q，Z，A，B，N，P，H，S，X，Y，E，K，L，T

C．G，M，Q，A，N，B，P，X，H，Y，S，T，L，K，E，Z

D．A，B，G，M，N，P，Q，Z，E，H，K，L，S，T，X，Y

下列每题给出的四个选项中，只有一个选项符合题目要求。

从一组7个人——J,K,L,M,N,P和Q中恰好选出4个去参加某外交官的退休宴会。对出席人员的选择必须遵循以下条件：

要么J被选，要么K被选，但两人不能同时被选；

要么N被选，要么P被选，但两人不能同时被选；

若N被选时，L肯定被选；

Q被选时，K肯定被选。

下面哪4个人可能被选择去参加退休宴会?

A．J,K,M,P

B．J,L,N,Q

C．J,M,N,Q

D．K,M,P,Q