●试题二
对文法G[S]:S→a|∧|(T);T→T,S|S;回答问题1~问题3。
【问题1】
对文法G进行改写,然后对每个非终结符写出不带回溯的递归子程序。
【问题2】
经改写后的文法是否是LL (1) 的?指出它的预测分析表中 (1) ~ (3) 处的内容。
【问题3】
说明输入串(a,a)是否为G的句子。
第1题
试题三(共15 分)
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。
【说明】
某运输公司决定为新的售票机开发车票销售的控制软件。图 3-1 给出了售票机的面板示意图以及相关的控制部件。
售票机相关部件的作用如下所述:
(1)目的地键盘用来输入行程目的地的代码(例如,200表示总站)。
(2)乘客可以通过车票键盘选择车票种类(单程票、多次往返票和座席种类)。
(3)继续/取消键盘上的取消按钮用于取消购票过程,继续按钮允许乘客连续购买多张票。
(4)显示屏显示所有的系统输出和用户提示信息。
(5)插卡口接受MCard(现金卡),硬币口和纸币槽接受现金。
(6)打印机用于输出车票。
假设乘客总是支付恰好需要的金额而无需找零,售票机的维护工作(取回现金、放入空白车票等)由服务技术人员完成。
系统采用面向对象方法开发,使用 UML 进行建模。系统的顶层用例图和类图分别如图3-2和图3-3所示。
【问题1】(5 分)
根据说明中的描述,给出图 3-2 中 A1 和 A2 所对应的参与者,U1 所对应的用例,以及(1)、(2)处所对应的关系。
【问题2】(7 分)
根据说明中的描述,给出图3-3中缺少的C1~C4所对应的类名以及(3)~(6)处所对应的多重度。
【问题3】(3 分)
图3-3中的类图设计采用了中介者(Mediator)设计模式,请说明该模式的内涵。
第2题
●试题三
有下列关于运动会管理系统的ER图,如图10所示。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体之间的关系。假定已通过下列SQL语言建立了基本表。
CREATE TABLE ATHLETE
(ANO CHAR (6) NOT NULL,
ANAME CHAR (20) ,
ASEX CHAR (1) ,
ATEAM CHAR (20) );
CREATE TABLE ITEM
(INO CHAR (6) NOT NULL,
INAME CHAR (20) ,
ITIME CHAR (12) ,
IPLACE CHAR (20) ;
CREATE TABLE GAMES
(ANO CHAR (6) NOT NULL,
INO CHAR (6) NOT NULL,
SCORRE CHAR (10) );
为了答题的方便,图中的实体和属性同时给出了中英文两种文字,回答问题时只需写出英文名即可。
【E-R图】
图10 E-R图
【问题】
填充下列SQL程序1~4中的 (1) ~ (7) ,使它们分别完成相应的功能:
程序1:统计参加比赛时男运动员人数。
SELECT (1)
FROM ATHLETE
WHERE ASEX=′M′;
程序2:查100872号运动员参加的所有项目及其比赛时间和地点。
SELECT ITEM,INO,IN A ME,ITIME,IPLACE
FROM GAMES,ITEM
WHERE (2) ;
AND (3) ;
程序3:查参加100035项目的所有运动员名单。
SELECT ANO,ANAME,ATEAM
FROM ATHLETE
WHERE (4) ;
(SELECT (4) (5)
FROM GAMES
WHERE GAMES.ANO=ATHLETE.ANO AND INO='100035');
程序4:建立运动员成绩视图。
(6) ATHLETE-SCORE
AS SELECT ATHLETE,ANO,ANAME,ATEAM,INAME,SCORE
FORM (7) WHERE ATHLETE.ANO=GAMES.ANO AND GAMES.INO=ITEM.INO;
第3题
●试题一
阅读下列说明和数据流图,回答问题1~问题3。
【说明】
某医院收费系统的主要功能是收取病人门诊的各项费用。系统的收费功能分为3个方面:病历收费、挂号收费和根据处方单内容收取检查或药物费用。
1.病人初次来该医院看病,首先购买病历,记录病人基本情况。
2.病人看病前要挂号。根据病人的病历和门诊部门(内科、外科等),系统提供相应的挂号单和处方单,并收取费用。
3.病人根据处方单进行进一步检查或取药前需交纳各项费用。系统首先根据病人基本情况检查处方单中病历号是否正确,记录合格的处方单,并提供收据。
4.所有收费都必须依据定价表中的定价来计算,且所有收费都必须写入收费记录中。
医院收费系统的顶层图如图2所示;医院收费系统的第O层DFD图如图3所示。其中,加工1的细化图如图4所示,加工2的细化图如图5所示。
假定顶层图是正确的,"定价表"文件已由其他系统生成。
【数据流图】
图2医院收费系统的顶层图
图3医院收费系统的0层图
图4医院收费系统的加工1子图
图5医院收费系统的加工2子图
【问题1】
指出哪张图的哪些文件可以不必画出。
【问题2】
数据流图4中缺少2条数据流,请直接在图中添加。
【问题3】
数据流图5中缺少4条数据流,请直接在图中添加。
第4题
●试题六
【说明】
下面是一个Applet程序,其功能是在绘图区域中通过鼠标的移动来绘制直线,并且有清除绘图区域按钮,用来清除已经绘制的图像。
程序运行结果如图5所示。
图5
import javA.awt.*;
import javA.applet.*;
/*
<applet code=ex6_7.class width=800 height=400>
</applet>
*/
public class ex6_7 extends Applet{
private Button btn;
private boolean bDraw, bClear;
private int upX, upY,downX, downY;
public void init(){
setLayout(null);
bClear = false;
bDraw = false;
btn = new Button("clear");
btn.reshape(250, 150, 70, 30);
add(btn);
}
public void paint(Graphics g){
if(bClear){
g.clearRect(0, 0, getSize().width, getSize().height);
(1) ;
}
if(bDraw){
g.drawLine( (2) );
bDraw = false;
}
}
public void update(Graphics g){
(3) ;
}
public boolean mouseDown(Event event, int x, int y){
downX = x;
downY = y;
return true;
}
public boolean mouseUp(Event event, int x, int y){
upX = x;
upY = y;
(4) ;
repaint();
return true;
}
public boolean action(Event event, Object object){
if ( (5) ){
bClear = true;
repaint();
}
return true;
}
}
ex6_7.html
<HTML>
<HEAD>
<TITLE> ex6_7 </TITLE>
</HEAD>
<BODY>
<applet code=" ex6_7.class" width=800 height=400 >
</applet>
</BODY>
</HTML>
第5题
●试题七
【说明】
下面是一个Applet程序,其功能是从3~100之间(包括3和100)每隔0.5秒显示一个新的数字,如果数字为素数,则显示为灰色,其他为绿色。
程序运行结果如图4所示。
import java.awt.*;
import java.applet.Applet;
/*
<applet code=ex2_7.class width=800 height=400>
</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<n-1&&bPrime){
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
<HTML>
<HEAD>
<TITLE>ex2_7</TITLE>
</HEAD>
<BODY>
<applet code="ex2_7.class" width=800 height=400 >
</applet>
</BODY>
</HTML>
第6题
阅读以下预备知识、函数说明和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);
}
}
第7题
【问题 1】(8 分)
用回溯法求解此 0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数,其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出 0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
第8题
●试题一
阅读下列说明以及图示(如图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种图。对整个系统而言,其功能由用例图描述,静态结构由类图和对象图描述,动态行为由状态图、时序图、协作图和活动图描述,而物理架构则是由组件图和分布图描述。请分别指出用例图、类图、对象图、状态图、时序图、协作图、活动图、组件图、分布图的作用。
第9题
●试题三
阅读下列说明和E-R图,回答问题1~3。
【说明】
设有关于银行借贷管理系统的E-R图(如图4所示)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。为了答题的方便,图中的实体和属性同时给出了中英文说明,回答问题时只需写出英文名即可。
图4银行借贷管理系统E-R图
【问题1
根据E-R图中给出的词汇,按照"有关模式名(属性1,属性2,…)"的格式,将此E-R图转换为关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。要求其中的关系模式至少属于第三范式。
【问题2】
如下的SQL语言用于查询"在该银行中一笔贷款贷给多个(至少2个)客户的所有贷款号和发放贷款的支行名称"的不完整语句,请在空缺处填入正确的内容。
SELECT Borrow.Lno,Bname
FROM Borrow,Loan
WHERE (1)
GROUP BY Borrow.Lno
HAVING (2) ;
【问题3】
假设这个银行有若干个节点,每个节点运行一个数据库系统。假设这些节点之间惟一的交互式用电子方式相互传送款项,这样的系统是分布式数据库系统吗?为什么?
第10题
●试题一
阅读下列说明和数据流图,回答问题1~问题3。
【说明】
某考务处理系统主要功能是考生管理和成绩管理:
1.对考生送来的报名表进行检查。
2.对合格的报名表编好准考证号码后将准考证送给考生,将汇总后的考生名单送给阅卷站。
3.对阅卷站送来的成绩表进行检查,并根据考试中心指定的合格标准审定合格者。
4.填写考生通知单(内容包含该考生的准考证号、姓名、各课程成绩及最终合格/不合格标志),送给考生。
5.根据考生信息及考试成绩,按地区、年龄、文化程度和职业进行成绩分类统计及试题难度分析,产生统计分析表。
考务处理系统的顶层图如图1所示,第0层图如图2所示,加工2子图如图3所示。
【数据流图】
图1顶层图
图2 0层图
图3加工2子图
【问题1】
指出哪张图的哪些文件可以不必画出。
【问题2】
数据流图1-3中缺少3条数据流,请直接在图中添加。
【问题3】
根据系统功能和数据流图填充下列数据字典条目中的 (1) 和 (2) :
试题得分表=准考证号+{课程名+成绩}
考生名册=报名号+准考证号+姓名+通信地址+出生年份+文化程度+职业
考生通知单= (1)
报名表= (2)
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!