阅读下列算法说明和流程图1，回答问题1至问题3，将解答填入答题纸的对应栏内。

【算法说明】

某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(占用)。客房是以房间(不是床位)为单位出租的。

本算法根据几个散客的要求预订一间空房。程序的输入为：人数M，房间等级要求R(R=0表示任意等级都可以)。程序的输出为：所有可供选择的房间号。

流程图1描述了该算法。

【问题1】

假设当前该旅馆各个房间的情况见表3。

当输入M=4，R=0时，该算法的输出是什么？

【问题2】

如果等级为r的房间每人每天的住宿费为RATE(r),RATE为数组。为使该算法在输出每个候选的房间号RM(J)后，再输出这批散客每天所需的总住宿费DAYRENT(J)，流程图1的β所指框中的最后处应增加什么处理？

【问题3】

如果限制该算法最多输出K个可供选择的房间号，则在流程图1的α所指的判断框应改成什么处理？

【流程图1】(如图2所示)

图2

●试题七

【说明】

下面是一个Applet程序，其功能是从3~100之间（包括3和100）每隔0.5秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。

程序运行结果如图4所示。

import java.awt.*;

import java.applet.Applet;

/*

*/

                                                                                         图 4

 public class ex2_7 extends Applet {

public Color color2_7 = Color.black;

private int n2_7 = 3;

public myPrime  thPrime2_7;

public void init() {

thPrime2_7 = new myPrime(this);

thPrime2_7.start();

}

public void paint(Graphics g) {

g.setColor(color2_7);

g.drawstring((1) ,50, 50);

}

public int getInt(){

return n2_7;

}

public void setInt(int i){

n2_7=i;

}

}

class myPrime extends Thread {

ex2_7 obj2_7;

myPrime (ex2_7 o) {

this.obj2_7 = o;

}

public boolean isPrime(int n) {

boolean bPrime = true;

int i=2;

if(（2）)

return false;

while(i

if (（3）)

bPrime = false;

i++;

}  

return bPrime;

}

public void run() {

int i;

for (i = 3;（4）; i++) {

if (isPrime(i))

obj2_7.color2_7 = Color.gray;

else

obj2_7.color2_7 = Color.green;

（5）;

obj2_7.repaint();

try {

sleep(500);

} catch (InterruptedException ie) {

}        

}

}

}

ex2_7.html

   code="ex2_7.class" width=800 height=400 >

●试题六

阅读下列程序说明和C++代码，将应填入(n)处的字句写在答卷的对应栏内。

【说明】

①为类Circle增加一个构造函数，该函数有一个参数，并在构造时将该参数值赋给成员radius。将该函数实现为一个非内联函数，并且使用参数列表的方式将类成员赋值。

②为类Circle增加一个成员函数print()，使得可以输出有关圆的信息，比如下列程序

Circle c;

   C．SetRadius (5) ;

   C．Print();

将输出：The circle has radius of 5!

③完成友元函数void CompareR(Circle *c1,Circle *c2)的定义，在屏幕中输出c1与c2比较radius大小结果，要求使用if-else结构完成。

输出结果如下：

The circle has radus of 5!

The circle has radius of 10!

c1

源程序文件test7_3.cpp清单如下：

#include

class Circle{

public:

Circle():radius (5) {}

 (1) 

void SetRadius(int r) { radius=r; }

int GetRadius() { return radius; }  

 (2) 

friend void CompareR(Circle *c1,Circle *c2);

private:

int radius;

};

void CompareR(Circle *c1,Circle *c2)

{

 (3) 

cout<<"c1>c2"<

else

if ((c1->GetRadius())==(c2->GetRadius()))

cout<<"c1=c2"<

else

if ((c1->GetRadius())<(c2->GetRadius()))

cout<<"c1

}

void main()

{

Circle c1;

c1.SetRadius (5) ;

c1.Print();

Circle c2 (10) ;

c2.Print();

CompareR(&c1,&c2);

}

请补充函数fun()，该函数可以统计一个长度为n的字符串在另一个字符串中出现的次数。例如，假定输入的字符串为：asd ascasdfg asd as asd mlosd,子字符串为asd，则应输出4。

注意：部分源程序给出如下。

请勿改动主函数main和其他函数中的任何内容，仅在函数fun()的横线上填入所编写的若干表达式或语句。

试题程序：

#include

#include

#include

int fun(char *str,char *substr)

{

int n;

char *p,*r;

 (1) ;

while(*str)

{

p=str;

r=substr;

while(*r)

if( (2) )

{

r++;

p++;

}

else

break;

if( (3) )

n++;

str++;

}

return n;

}

main()

{

char str［81］,substr［3］;

int n;

clrscr();

printf("输入主字符串：");

gets(str);

printf("输入子字符串:");

gets(substr);

puts(str);

puts(substr);

n=fun(str,substr);

printf("n=%d＼n",n);

}

●试题五

阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【预备知识】

①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图3所示的最优二叉树和相应的结构数组Ht(数组元素Ht［0］不用)(见表5)。

                                           图3最优二叉树

                                            表5 结构数组Ht

结构数组Ht的类型定义如下：

#define MAXLEAFNUM 20

struct node{

char ch;/*当前结点表示的字符，对于非叶子结点，此域不用*/

int weight;/*当前结点的权值*/

int parent;/*当前结点的父结点的下标，为0时表示无父结点*/

int lchild,rchild;

/*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/

}Ht［2*MAXLEAFNUM］;

②用′0′或′1′标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用′0′(′1′)标识该分支(示例如图3所示)。

③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由′0′、′1′组成的一个序列，称此序列为该叶子结点的前缀编码。例如图3所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。

【函数5．1说明】

函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。

在构造过程中，将Ht［p］．weight域用作被遍历结点的遍历状态标志。

【函数5．1】

char**Hc；

void LeafCode(int root,int n)

{/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/

int i,p=root,cdlen=0;char code［20］;

Hc=(char**)malloc((n+1)*sizeof(char*));/*申请字符指针数组*/

for(i=1;i＜=p;++i)

Ht［i］．weight=0;/*遍历最优二叉树时用作被遍历结点的状态标志*/

while(p){/*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/

if(Ht［p］．weight==0){/*向左*/

Ht［p］．weight=1;

if (Ht［p］．lchild !=0) { p=Ht［p］．lchild; code［cdlen++］=′0′;}

else if (Ht［p］．rchild==0) {/*若是叶子结点，则保存其前缀编码*/

Hc［p］=(char*)malloc((cdlen+1)*sizeof(char));

 (1) ;strcpy(He［p］，code);

}

}

else if (Ht［p］．weight==1){/*向右*/

Ht［p］．weight=2;

if(Ht［p］．rchild !=0){p=Ht［p］．rchild;code［cdlen++］=′1′;}

}

else{/*Ht［p］．weight==2,回退*/

Ht［p］．weight=0;

p= (2) ; (3) ;/*退回父结点*/

}

}/*while结束*/

}

【函数5．2说明】

函数void Decode(char*buff,int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列并输出。其中形参root为最优二叉树的根结点下标;形参buff指向前缀编码序列。

【函数5．2】

void Decode(char*buff,int root)

{ int pre=root,p;

while(*buff!=′＼0′){

p=root;

while(p!=0){/*存在下标为p的结点*/

pre=p;

if( (4) )p=Ht［p］．lchild;/*进入左子树*/

else p=Ht［p］．rchild;/*进入右子树*/

buff++;/*指向前缀编码序列的下一个字符*/

｝

 (5) ;

printf(″%c″,Ht［pre］．ch);

}

}

●试题三

对于教学数据库的三个基本表S(S#，SNAME，AGE，SEX)，SLLS#,C#，GRADE)，C(C#，CNAME，TEACHER)。现根据查询条件填充下面SQL语句空白的部分。

1.检索LIU老师所授课程的课程号和课程名。

2.检索至少选修LIU老师所授课程中一门课程的女学生姓名。

3.检索WANG同学不学的课程的课程名。

4.检索全部学生都选修的课程的课程号与课程名。

5.检索选修课程包含LIU老师所授课程的学生学号。

【说明】

1.SELECT  (1) FROM C WHERE TEACHER=′LIU′

2.SELECT S.SNAME FROM S,SC

WHERE S.S#=S

C．S# AND S.SEX=′F′AND S

C．C#= (2) 

(SELECTC# FROM C WHERE TEACHER=′LIU′)

3.SELECT CNAME FROM C

WHERE C#<> (3) ( SELECTS

C．C# FROM S,SC WHERE S.S#=S

C．S# AND S.SNAME=′WANG′)

4.由题知，该问题是在表C中找课程号和课程名，要求这门课被全部学生所选。

SELECT C#,CNAME

FROM C

WHERE NOT EXISTS

(SELECT*

FROMS

WHERE NOT EXISTS

(SELECT *

FROMS

 WHERE NOT EXISTS

(SELECT*

FROM SC

WHERE  (4) 

5.SELECT DISTINCT S#

FROM SC

WHERE  (5) 

(SELECT C#

FROM C

 WHERE TEACHER=′LIU′)

●试题二

对文法G[S]：S→a|∧|(T)；T→T，S｜S；回答问题1～问题3。

【问题1】

对文法G进行改写，然后对每个非终结符写出不带回溯的递归子程序。

【问题2】

经改写后的文法是否是LL (1) 的?指出它的预测分析表中 (1) ～ (3) 处的内容。

【问题3】

说明输入串(a，a)#是否为G的句子。

阅读下列算法说明和流程图1，回答问题1至问题3，将解答填入答题纸的对应栏内。

【算法说明】

某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(占用)。客房是以房间(不是床位)为单位出租的。

本算法根据几个散客的要求预订一间空房。程序的输入为：人数M，房间等级要求R(R=0表示任意等级都可以)。程序的输出为：所有可供选择的房间号。

流程图1描述了该算法。

【问题1】

假设当前该旅馆各个房间的情况见表3。

当输入M=4，R=0时，该算法的输出是什么？

【问题2】

如果等级为r的房间每人每天的住宿费为RATE(r),RATE为数组。为使该算法在输出每个候选的房间号RM(J)后，再输出这批散客每天所需的总住宿费DAYRENT(J)，流程图1的β所指框中的最后处应增加什么处理？

【问题3】

如果限制该算法最多输出K个可供选择的房间号，则在流程图1的α所指的判断框应改成什么处理？

【流程图1】(如图2所示)

图2