●试题一

阅读下列说明以及图示(如图1所示)，回答问题1～3。

【说明】

某大学准备开发一个学生课程注册系统，学生可以使用该系统查询新学期将开设的课程和讲课教师情况，选择自己要学习的课程进行登记注册，并可以查询成绩单；教师可以使用该系统查询新学期将开设的课程和选课学生情况，并可以登记成绩单；注册管理员使用该系统进行注册管理，包括维护教师信息、学生信息和课程信息等。

在每个学期的开始，学生可以获得该学期的课程目录表，课程目录表列出每门课程的所有信息，诸如基本信息、教师、开课系和选课条件等。

新学期开始前两周为选课注册时间，在此期间学生可以选课注册，并且允许改变或取消注册申请，开学两周后注册管理员负责关闭课程注册。每个学生可以选择不超过4门课程，同时指定2门侯选课程以备主选课程未选上。每门课程最多不能超过10人，最少不能低于3人，低于3人选课的课程将被取消。一旦学生的注册过程完毕，注册系统将有关信息提交收费系统以便学生付费。如果在实际注册过程中名额已满，系统将通知学生在提交课程表之前予以更改。

在学期结束时，学生可以存取系统查看电子成绩单。由于学生成绩属于敏感信息，系统必须提供必要的安全措施以防非法存取。

【用例图】

图1学生课程注册系统的用例图

【协作图】

图2创建课程登记表的协作图

【时序图】

图3创建课程登记表的时序图

注释1：学生打算注册新的课程。

注释2：一张这学期可选择的课程列表。

注释3：显示一张为学生选课用的空白登记表。

【问题1】

在UML中，用例代表一个完整的功能，如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征，并指出用例图中 (1) ～ (3) 处表示的内容。

【问题2】

协作图与时序图是同构的，二者表示的都是同样的系统交互活动，只是各自的侧重点不同而已。根据题目提供的信息，指出协作图中 (4) ～ (8) 处表示的内容。

【问题3】

UML采用5个互联的视图来描述软件系统的体系结构，即用例视图(Use-case View)、设计视图(Design View)、进程视图(Process View)、实现视图(Implementation View)和展开视图(Deployment View)。系统模型中每一个视图的内容是由一些图来描述的，UML中包含用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图等9种图。对整个系统而言，其功能由用例图描述，静态结构由类图和对象图描述，动态行为由状态图、时序图、协作图和活动图描述，而物理架构则是由组件图和分布图描述。请分别指出用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图的作用。

●试题七

【说明】

下面是一个Applet程序，其功能是通过一个按钮控制一个窗口的创建，显示与隐藏，并且以按钮文字作为提示，可以随着窗口的状态改变，即如果窗口出现，则按钮文字为"Hide myFrm"，提示用户点击按钮，则隐藏窗口，反之亦然。请将横线处语句补充完整。

程序运行结果如图5所示：

图5

import javA．awt.*;

import javA．applet.*;

/*

*/

public class ex8_7 extends Applet{

private Frame. frm;

private Button showBtn;

public void init(){

showBtn = new Button( "Show Frame" );

 (1) ;

}

public boolean action( Event e, Object o ){

if( e.target == showBtn ){

if( (2) ){

 (3) ;

frm.dispose();

 (4) ;

showBtn.setLabel("Show myFrm");

}

else{

frm = new Frame( "myFrm" );

frm.resize( 200, 150 );

frm.setBackground( Color.gray );

 (5) ;

showBtn.setLabel("Hide myFrm");

}

}

return true;

}

}

ex8_7.html

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

●试题五

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

【程序说明】

本程序先从文件读入各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。

【程序】

＃include

typedef struct idnode {

int id;

struct idnode * next;

} IdNode;

typedef struct marknode {

int mark;

IdNode *head;

struct marknode *left, *right;

} MarkNode;

char fname［］="sp07.dat";

main()

{ int id, mark;

MarkNode *root=null;

FILE *fp=fopen(fname,"r");

if(!fp) {

printf("file%s open error.＼n", fname);

exit(0);

}

while (!feop(fp)) {

fscanf(fp,"%d%d", &id, &mark);

btree(&root, id, mark);

}

fclose(fp);

print(root);

}

btree(MarkNod**mpptr, int id, int mark)

{ IdNode *ip;

MarkNode *mp=*mpptr;

if (1) {

if (mark==p->mark) addIdNODE ( (2) , id);

else if (mark>mp->mark) btree (&mp->left, id, mark);

else btree(&mp->right, id, mark);

}else

{ mp=(marknode *) malloc(sizeo (marknode));

mp->mark=mark;

mp->left=mp->right=NULL;

 (3) 

addIdNode(&mp->head, id);

 (4) ;

}

}

addIdNode(IdNode **ipp, int id)

{IdNode *ip=*ipp;

if ( (5) )addIdNode ( (6) ), id;

else{

ip=(IdNode *)malloc(sizeof(IdNode));

sp->id=id;

ip->next=NULL;

 (7) 

}

}

print(MarkNode *mp)

{ IdNode *ip, *ip0;

if (mp){

print (mp->left);

printf("%6d:＼t",mp->mark);

ip=mp->head;

while(ip){

printf("%6d",ip->id);

ip0=ip;

ip=ip->next;

free(ip0);

}

printf("＼n");printf(mp->right);free(mp);

}

}

●试题六

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

【说明】

本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值;c为二维数组，存储有向网中每一对顶点间的最短路径长度;kay为二维数组，存储最短路径，kay［i］［j］=k表示顶点i到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有：

Input():输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a［i］［j］取弧上的权值，否则a［i］［j］的值取NoEdge。

AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。

OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。

outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。

Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1，C2，…，Cn,其中C0是已知的带权邻接矩阵，a,Ck(i,j)(0≤i,j＜n)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n,有Ck(i,j)=C0(i,j)=a［i］［j］。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。

【C++代码】

#include

＃define NoEdge 10000 //当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示

void Make2DArray(int * * &x,int rows,int cols);

class AdjacencyWDigraph{

private

int n;//有向网中的顶点数目

int**a;//存储顶点间弧上的权值

int**c;//存储计算出的最短路径长度

int**kay;//存储求出的最短路径

pubic:

int Vertices()const {return n;}

void AllPairs();

void Input();//输入有向网的顶点数、各条弧及权值，建立邻接矩阵a

void OutShortestPath(int i,int j);//计算顶点i到j的最短路径(试卷中未列出)

~AdjacencyWDigraph();//析构函数(试卷中未列出)

private:

void outputPath(int i,int j);

};

void AdjacencyWDigraph::AllPairs()

{int i,j,k,t1,t2,t3;

for(i=1;i＜=n;k++)

for(j=1;j＜=n;++j)

{c［i］［j］= (1) ;kay［i］［j］=0;}

for(k=1;k＜=n;k++)

for(i=1;i＜=n;i++){

if(i==k) continue;

t1=c［i］［k］;

for(j=1;j＜=n;j++){

if(j==k||j==i)continue;

t2=c［k］［j］;t3=c［i］［j］;

if(t1!=NoEdge && t2!=NoEdge &&(t3==NoEdge||t1+t2＜t3))

{c［i］［j］= (2) ；kay［i］［j］= (3) ;}

}//for

}//for

}

void AdjacencyWDigraph:: outputPath(int i,int j)

{//输出顶点i到j的最短路径上的顶点

if(i==j)return;

if(kay［i］［j］==0)cout＜＜j＜＜′′;

else { outputPath(i, (4) ); outputPath( (5) );}

}

void Adjacency WDigraph::Input()

{int i,j,u,v,w,E;

cout＜＜″输入网中顶点个数：″;cin＞＞n;

cout＜＜″输入网中弧的个数:″;cin＞＞E;

Make2DArray(a,n+1,n+1);

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

for(j=1;j＜=n;j++)a［i］［j］=NoEdge;

for(i=1;i＜=n;i++)a［i］［i］=0;

Make2DArray(c,n+1,n+1);

Make2DArray(kay,n+1,n+1);

for(i=1;i＜=E;i++){

cout＜＜″输入弧的信息(起点终点权值)：″；cin＞＞u＞＞v＞＞w;a［u］［v］=w;

}

}

void Make2DArray(int**&x,int rows,int cols)

{int i,j;

x=new int*［rows+1］;

for(i=0;i＜rows+1;i++)x［i］=new int［cols+1］;

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

for(j=1;j＜=cols;j++＝x［i］［j］=0;

}

●试题四

阅读下列函数说明，将应填入(n)处的字句写在答卷纸的对应栏内。

【函数1说明】

函数compare(SqList A，SqList B)的功能是：设A=(al，…，am)和B=(bl，…，bn)均为顺序表，"比较"，两个顺序表A和B的大小。设A'和B'分别为A和B中除去最大共同前缀后的子表(例如，A=(y，x，x，z，x，z)，B=(y，x，x，z，y，x，x，z)，则两者中最大的共同前缀为(y，x，x，z)，在两表中除去最大共同前缀后的子表分别为A′=(x，z)和B′=(y，x，x，z))。若A′=B′=空表，则A=B；若A′=空表，而B′≠空表，或者两者均不为空表，且A′的首元小于B'的首元，则A否则A>B。

提示：算法的基本思想为：若相等，则j+l，之后继续比较后继元素；否则即可得出比较结果。显然，j的初值应为0，循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有3种可能出现的情况需要区分。

【函数1】

int compare(SqListA，SqList B)

{

//若A，则返回-1；若A=B，则返回0:若A>B，则返回1

j=0；

while(i< (1) ＆＆j<

   B．length)

if(A．elem[j]<

   B．elem[j])return(-1)；

else if(A．elem[j]>

   B．elem[j])return (1) ；

else (2) ；

if(A．length==

   B．length)return(0)；

else if(A．length<

   B．length)return(-1)；

else return (1) ；

}//compare

//函数1的时间复杂度是 (3) 。

【函数2说明】

函数exchange_L(SLink&L，int m)的功能是：用尽可能少的辅助空间将单链表中前m个结点和后n个结点的互换。即将单链表(a1，a2…，am，b1，b2，…，bn)改变成(b1，b2，…，bn，a1，a2，…，am)。

【函数2】

void exchange_L(SLink &L，int m)

{

if( (4) &&L->next)//链表不空且m!=0

{

P=L->next；k=1;

while(k

{

P= (5) ；++k；

}

if( (6) &&p->next)//n!=0时才需要修改指针

{

ha=L->next；//以指针ha记a1结点的位置

L->next=p->next；//将b1结点链接在头结点之后

p->next=NULL；//设am的后继为空

q= (7) ；//令q指向b1结点

while(q->next)q= (8) ；//查找bn结点

q->next= (9) ；//将a1结点链接到bn结点之后

}

}

}

//函数2的时间复杂度是 (10) 。

●试题三

阅读下列说明，回答问题1～问题3，将解答填入答题纸的对应栏内。

【说明】

某超市的销售业务由一个销售业务管理系统进行管理，该系统每完成一次交易都需要提供顾客发票，其格式见表6所示。

  对于这样一个销售业务管理系统，分别给出了以下两种关系数据库的设计(下划线表示主关键字)

设计一：

顾客Customer(顾客代码Cno，姓名name，住址address，联系电话phone)

收银员Salesman(收银员代码Sno，身份证号idno，姓名name，住址address，联系电话phone)

商品Merchandise(商品代码Mno，商品名称Mname，价格price)

发票Invoice(发票号码Ino，交易日期Idate，顾客代码Cno，收银员代码Sno，商品代码Mno，单价unitprice，数量amount)

设计二：

顾客Customer(顾客代码Cno，姓名name，住址address，联系电话phone)

收银员Salesman(收银员代码Sno，身份证号idno，姓名name，住址address，联系电话phone)

商品Merchandise(商品代码Mno，商品名称Mname，价格price)

发票Ivoice(发票号码Ino，交易日期Idate，顾客代码Cno，收银员代码Sno)

发票明细Invoicedetail(发票号码Ino，商品代码Mno，单价unitprice，数量amount)

【问题1】

设计一的关系模式Invoice最高满足第几范式?为什么?设计一和设计二哪个更加合理?为什么?

【问题2】

根据设计二中关系模式，以下SQL语句是用于"建立2005年1月期间每张发票的发票号，交易日期，交易商品件数和交易总金额的视图"的不完整语句，请填补其中的空缺。

CREATE VIEW Invoice -total (1) 

SELECT Invoice.Ino，Idate， (2) ， (3) 

FROM Invoice，Invoicedetail

WHERE (4) AND

Idate BETWEEN′2005-01-01′AND′2005-01-31′

GROUPBY (5) ；

【问题3】

根据设计二中关系模式，以下SQL语句是用于"查询从未售出的商品信息"的不完整语句，请填补其中的空缺。

SELECT Mno，Mname，price

FROM Merchandise (1) 

WHERE (2) 

(SELECT (3) 

FROM Invoicedetail

WHERE A．Mno=Invoicedetail.Mno)；

【问题4】

设计二中关系Merchandise中由属性price表示商品价格，关系Invoicedetail中的属性unitprice也表示商品价格。两个是否有必要同时存在?为什么?

●试题二

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

【说明】

算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示：

文件提示信息

(1+2)

abc)缺少对应左括号：第2行，第4列

((def)gx)缺少对应左括号：第3行，第10列

(((h)

ij)(k

(1ml)缺少对应右括号：第5行，第4列;第4行，第1列

在算法2-1中，stack为一整数栈。算法中各函数的说明见表4。

【算法2-1】

将栈stack置空，置EOF为false

ch＜-nextch();

while(not EOF)

k＜-kind(CH);

if(k== (1) )

push( (2) );push( (3) );

elseif(k== (4) )

if(not empty())

pop();pop()；

else

显示错误信息(缺少对应左括号或右括号);

显示行号row;显示列号col;

endif

endif

ch＜-nextch();

endwhile

if(not empty())

显示错误信息(缺少对应左括号或右括号);

while(not empty())

row＜-pop();col＜-pop();

显示行号row;显示列号co1;

endwhile

endif

为了识别更多种类的括号，对算法2-1加以改进后得到算法2-2。算法2-2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(char ch)的参数及其对应的返回值见表5。

【算法2-2】

将栈stack置空，置EOF为false

ch＜-nextch();

while(not EOF)

k＜-kind(ch);

if(k＞0)

if(判断条件1)

push( (5) );push( (6) );push( (7) )；

elseif(判断条件2and判断条件3)

pop();pop();pop();

else

显示错误信息(缺少对应左括号或右括号)；

显示行号row;显示列号col;

endif

endif

ch＜-nextch();

endwhile

if(not empty())

显示错误信息(缺少对应左括号或右括号);

while(not empty())

pop();rowpop();colpop();

显示行号row;显示列号col;

endwhile

endif

【问题1】

请将【算法2-1】和【算法2-2】中 (1) ~ (7) 处补充完整。

【问题2】

请从下面的选项中选择相应的判断逻辑填补【算法2-2】中的"判断条件1"至"判断条件3"。注意，若"判断条件2"的逻辑判断结果为假，就无需对"判断条件3"进行判断。

(a)字符是括号

(b)字符是左括号

(c)字符是右括号

(d)栈空

(e)栈不空

(f)栈顶元素表示的是与当前字符匹配的左括号

(g)栈顶元素表示的是与当前字符匹配的右括号

●试题一

阅读下列说明以及图示(如图1所示)，回答问题1～3。

【说明】

某大学准备开发一个学生课程注册系统，学生可以使用该系统查询新学期将开设的课程和讲课教师情况，选择自己要学习的课程进行登记注册，并可以查询成绩单；教师可以使用该系统查询新学期将开设的课程和选课学生情况，并可以登记成绩单；注册管理员使用该系统进行注册管理，包括维护教师信息、学生信息和课程信息等。

在每个学期的开始，学生可以获得该学期的课程目录表，课程目录表列出每门课程的所有信息，诸如基本信息、教师、开课系和选课条件等。

新学期开始前两周为选课注册时间，在此期间学生可以选课注册，并且允许改变或取消注册申请，开学两周后注册管理员负责关闭课程注册。每个学生可以选择不超过4门课程，同时指定2门侯选课程以备主选课程未选上。每门课程最多不能超过10人，最少不能低于3人，低于3人选课的课程将被取消。一旦学生的注册过程完毕，注册系统将有关信息提交收费系统以便学生付费。如果在实际注册过程中名额已满，系统将通知学生在提交课程表之前予以更改。

在学期结束时，学生可以存取系统查看电子成绩单。由于学生成绩属于敏感信息，系统必须提供必要的安全措施以防非法存取。

【用例图】

图1学生课程注册系统的用例图

【协作图】

图2创建课程登记表的协作图

【时序图】

图3创建课程登记表的时序图

注释1：学生打算注册新的课程。

注释2：一张这学期可选择的课程列表。

注释3：显示一张为学生选课用的空白登记表。

【问题1】

在UML中，用例代表一个完整的功能，如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征，并指出用例图中 (1) ～ (3) 处表示的内容。

【问题2】

协作图与时序图是同构的，二者表示的都是同样的系统交互活动，只是各自的侧重点不同而已。根据题目提供的信息，指出协作图中 (4) ～ (8) 处表示的内容。

【问题3】

UML采用5个互联的视图来描述软件系统的体系结构，即用例视图(Use-case View)、设计视图(Design View)、进程视图(Process View)、实现视图(Implementation View)和展开视图(Deployment View)。系统模型中每一个视图的内容是由一些图来描述的，UML中包含用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图等9种图。对整个系统而言，其功能由用例图描述，静态结构由类图和对象图描述，动态行为由状态图、时序图、协作图和活动图描述，而物理架构则是由组件图和分布图描述。请分别指出用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图的作用。