重要提示：
请勿将账号共享给其他人使用，违者账号将被封禁！
题目内容
（请给出正确答案）
●试题二
阅读下列说明和算法，回答问题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();rowpop();colpop();
显示行号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和问题2，将解答填入答题纸的对应栏内。 【说明】 算法2－1”相关的问题
第1题
●试题六
【说明】
下面是一个Applet程序，其功能是建立一个图形用户界面的窗口，包括一个文本显示区和一个按钮，点击按钮，可以在文本区已有的文本基础上追加显示10条"Welcome to China"信息，并且文本区由滚动条控制文本的上下滚动。
程序运行结果如图4所示。
import javax.swing.*;
import javA．awt.*;
import javA．awt.event.*;
/*
<applet code="ex5_6.class" width=800 height=400 >
</applet>
图4
*/
public class ex5_6 extends JApplet {
JButton jb = new JButton("Add Text");
JTextPane jtp = new JTextPane();
public void init() {
jb.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e){
for(int i = 1; i < 10; i++)
(1) + "Welcome to China!＼n");
}
});
Container cp = (2) ;
cp.add(new JScrollPane(jtp));
cp.add( (3) );
}
public static void main(String［］ args) {
ex5_6 obj5_6=new ex5_6();
String str = obj5_6.getClass().toString();
if(str.indexOf("class") !=-1)
str = str.substring (6) ;
JFrame. frm = new JFrame(str);
frm.addWindowListener(new (4) {
public void windowClosing(WindowEvent we) {
System.exit(0);
}
});
(5) .add(ex5_6);
frm.setSize(300, 400);
frm.setVisible(true);
}
}
ex5_6.html
<HTML>
<HEAD>
<TITLE>ex5_6</TITLE>
</HEAD>
<BODY>
<applet code="ex5_6.class" width=800 height=400 >
</applet>
</BODY>
</HTML>
第2题
●试题二
阅读以下说明和流程图(如图2所示)，回答问题1和问题2，将答案写在答卷的对应栏内。
【说明】
本流程图实现从成绩文件生成学生成绩一览表。
某中学某年级的学生成绩数据(分数)登录在成绩文件F0中，其记录格式见表2：
由该成绩文件生成见表3的学生成绩一览表。生成的学生成绩一览表按学号升序排列。表中的名次是指该生相应课程在年级中的名次。
流程图中的顺序文件F0是学生成绩文件，F0文件经处理1处理后产生顺序文件F，然后经过处理2至处理4对文件F进行处理和更新。在处理5中，仅对文件F的纪录进行学生成绩一览表的编排输出，不进行排序和增加名次等处理。
【问题1】
流程图中文件F的纪录格式设定为见表4形式：
其中的①、②应定义为何种数据项？
【问题2】
简述处理2、处理3和处理4作何种处理，若有排序处理则需指明排序的键及序(升序或降序)。
【流程图】
图 3
第3题
试题四（共15分）
阅读下列说明和C代码，回答问题1至问题 3，将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下：
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1 是一个大顶堆的例子。
堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大顶堆A，且已经实现了调整堆的函数heapify(A, n, index)。
下面将C代码中需要完善的三个函数说明如下：
（1）heapMaximum(A)：返回大顶堆A中的最大元素。
（2）heapExtractMax(A)：去掉并返回大顶堆 A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。
（3）maxHeapInsert(A, key)：把元素key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。
优先队列采用顺序存储方式，其存储结构定义如下：
define PARENT(i) i/2
typedef struct array{
int *int_array; //优先队列的存储空间首地址
int array_size; //优先队列的长度
int capacity; //优先队列存储空间的容量
} ARRAY;
【C代码】
（1）函数heapMaximum
int heapMaximum(ARRAY *A){ return （1） ; }
（2）函数heapExtractMax
int heapExtractMax(ARRAY *A){
int max;
max = A->int_array[0];
（2） ;
A->array_size --;
heapify(A,A->array_size,0); //将剩余元素调整成大顶堆
return max;
}
（3）函数maxHeapInsert
int maxHeapInsert(ARRAY *A,int key){
int i,*p;
if (A->array_size == A->capacity) { //存储空间的容量不够时扩充空间
p = (int*)realloc(A->int_array, A->capacity *2 * sizeof(int));
if (!p) return -1;
A->int_array = p;
A->capacity = 2 * A->capacity;
}
A->array_size ++;
i = （3） ;
while (i > 0 && （4） ){
A->int_array[i] = A->int_array[PARENT(i)];
i = PARENT(i);
}
（5） ;
return 0;
}
【问题 1】（10分）
根据以上说明和C代码，填充C代码中的空（1）～（5）。
【问题 2】（3分）
根据以上C代码，函数heapMaximum、heapExtractMax和 maxHeapInsert的时间复杂度的紧致上界分别为 （6） 、 （7） 和 （8） （用O 符号表示）。
【问题 3】（2分）
若将元素10插入到堆A =〈15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1〉中，调用 maxHeapInsert函数进行操作，则新插入的元素在堆A中第 （9） 个位置（从 1 开始）。
第4题
●试题二
阅读以下说明和流程图，回答问题1和问题2，将答案写在答卷的对应栏内。
【说明】
某供销系统接受顾客的订货单，当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采购单；当某配件的库存量大于或等于定购粮食，或者收到供应商的送货单并更新了库存后，向顾客发出提货单。该系统还可随时向总经理提供销售和库存情况表。该供销系统的分层数据流图中部分数据流和文件的组成如下：
文件
配件库存=配件号+配件名+规格+数量+允许的最低库存量
数据流
订货单=配件号+配件名+规格+数量+顾客名+地址
提货单=订货单+金额
采购单=配件号+配件名+规格+数量+供应商名+地址
送货单=配件号+配件名+规格+数量+金额
假定顶层图(如图6所示)是正确的，"供应商"文件已由其他系统生成。
【问题1】
指出哪张图中的哪些文件可不必画出。
【问题2】
指出在哪些图中遗漏了哪些数据流。回答时使用如下形式之一：
(1) XX图中遗漏了XX加工(或文件)流向XX加工(或文件)的XX数据流；
(2) XX图中XX加工遗漏了XX输入(或输出)数据流。
【流程图】
顶层图
图6
0层图
图7
加工1子图
图8
加工2子图
图9
第5题
试题六（共 15 分）
阅读下列说明和 C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批 5 万元以下（不包括 5 万元）的采购单，副董事长可以审批 5 万元至 10 万元（不包括 10 万元）的采购单，董事长可以审批 10 万元至 50 万元（不包括 50万元）的采购单，50 万元及以上的采购单就需要开会讨论决定。 采用责任链设计模式（Chain of Responsibility）对上述过程进行设计后得到的类图如图 6-1 所示
[C++代码]
include <string>
include <iostream>
using namespace std;
class PurchaseRequest {
public:
double Amount; // 一个采购的金额
int Number; // 采购单编号
string Purpose; // 采购目的
};
class Approver { // 审批者类
public:
Approver(){ successor = NULL; }
virtual void ProcessRequest(PurchaseRequest aRequest){
if (successor != NULL){ successor-> （1） ; }
}
void SetSuccessor(Approver *aSuccesssor){ successor = aSuccesssor; }
private:
（2） successor;
};
class Congress : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest){
if(aRequest.Amount >= 500000){ /* 决定是否审批的代码省略 */ }
else （3） ProcessRequest(aRequest);
}
};
class Director : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest){ /* 此处代码省略 */ }
};
class President : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest){ /* 此处代码省略 */ }
};
class VicePresident : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest){ /* 此处代码省略 */ }
};
void main(){
Congress Meeting; VicePresident Sam; Director Larry ; President Tammy;
// 构造责任链
Meeting.SetSuccessor(NULL); Sam.SetSuccessor( （4） );
Tammy.SetSuccessor( （5） ); Larry.SetSuccessor( （6） );
PurchaseRequest aRequest; // 构造一采购审批请求
cin >> aRequest.Amount; // 输入采购请求的金额
（7） .ProcessRequest(aRequest); // 开始审批
return ;
}
第6题
试题四(共15 分)
阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
某机器上需要处理 n 个作业 job1, job2, …, jobn，其中：
(1) 每个作业jobi(1≤i≤n)的编号为 i， jobi有一个收益值 p[i]和最后期限值 d[i]；
(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，
一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3) job1～jobn 的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；
(4) 如果作业jobi在其期限之内完成，则获得收益 p[i]；如果在其期限之后完成，
则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图 4-1 是基于贪
心策略求解该问题的流程图。
(1) 整型数组 J[]有 n 个存储单元，变量 k 表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号， 数组 J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。
(2) 为了方便于在数组 J 中加入作业，增加一个虚拟作业 job0，并令d[0] = 0， J[0] = 0。
(3) 算法大致思想：先将作业 job1 的编号 1 放入 J[1]，然后，依次对每个作业 jobi (2≤i≤n)进行判定，看其能否插入到数组 J 中，若能，则将其编号插入到数组 J 的适当位置，并保证 J 中作业按其最后期限非递减排列，否则不插入。 jobi能插入数组 J 的充要条件是：jobi 和数组 J 中已有作业均能在其期限之内完成。
(4) 流程图中的主要变量说明如下：
i：循环控制变量，表示作业的编号；
k：表示在期限内完成的作业数；
r：若jobi能插入数组 J，则其在数组 J 中的位置为 r+1；
q：循环控制变量，用于移动数组 J 中的元素。
【问题 1】 （9 分）
请填充图4-1 中的空缺(1)、(2)和(3)处。
【问题 2】(4 分)
假设有 6 个作业 job1, job2, …, job6；
完成作业的收益数组 p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)；
每个作业的处理期限数组 d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。
请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4)
（按作业处理的顺序给出） ，得到的总收益为 (5) 。
【问题 3】(2 分)
对于本题的作业处理问题， 用图 4-1的贪心算法策略， 能否求得最高收益？ (6) 。
用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。
第7题
试题三（共 15 分）
阅读下列说明和 UML 图，回答问题 1 至问题4，将解答填入答题纸的对应栏内。
【说明】
某企业为了方便员工用餐，为餐厅开发了一个订餐系统（COS：Cafeteria Orderin
System），企业员工可通过企业内联网使用该系统。
企业的任何员工都可以查看菜单和今日特价。
系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录）、注册工资支
付、预约规律的订餐，在特殊情况下可以覆盖预订。
餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资
支付的顾客生成付费请求并发送给工资系统。
菜单管理员是餐厅特定员工，可以管理菜单。
送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注
册工资支付的顾客，由送餐员收取现金后记录）。
顾客订餐过程如下：
1. 顾客请求查看菜单；
2. 系统显示菜单和今日特价；
3. 顾客选菜；
4. 系统显示订单和价格；
5. 顾客确认订单；
6. 系统显示可送餐时间；
7. 顾客指定送餐时间、地点和支付方式；
8. 系统确认接受订单，然后发送 Email 给顾客以确认订餐，同时发送相关订餐信息通
知给餐厅员工。
系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图 3-1和图 3-2 所示。
【问题 1】（2 分）
根据【说明】中的描述，给出图 3-1中 A1 和 A2所对应的参与者。
【问题 2】（8 分）
根据【说明】中的描述，给出图 3-1中缺少的四个用例及其所对应的参与者。
【问题 3】（4 分）
根据【说明】中的描述，给出图 3-2中（1）～（4）处对应的活动名称或图形符号。
【问题 4】（1 分）
指出图 3-1 中员工和顾客之间是什么关系，并解释该关系的内涵。
第8题
试题二（15 分）
阅读下列说明，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。
【说明】
某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。
1．对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质（个人、单位） 、折扣率、联系人、联系电话等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜色等信息。一个客户至少有一台车。客户及车辆信息如表 2-1 所示。
2．记录维修车辆的故障信息。包括：维修类型（普通、加急） 、作业分类（大、中、小修） 、结算方式（自付、三包、索赔）等信息。维修厂的员工分为：维修员和业务员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。如表 2-2 所示。
3．维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表 2-3所示。
4．客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。 根据需求阶段收集的信息，设计的实体联系图（图 2-1）和关系模式（不完整）如下所
示。图 2-1 中业务员和维修工是员工的子实体。
【逻辑结构设计】
客户( (5) ，折扣率，联系人，联系电话)
车辆(车牌号，客户编号，车型，颜色，车辆类别)
委托书( (6) ，维修类型，作业分类，结算方式，进厂时间，
预计完工时间，登记日期，故障描述，总费用)
维修项目(维修项目编号，维修项目，单价)
派工单( (7) ，工时)
员工( (8) ，工种，员工类型，级别)
【问题 1】 （4 分）
根据问题描述，填写图 2-1 中(1)～(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用 1 : 1，1 : n 或 1 : *，m : n 或 * : *表示。
【问题 2】 （4 分）
补充图 2-1 中的联系并指明其联系类型。联系名可为：联系 1，联系 2，…。
【问题 3】 （4 分）
根据图 2-1 和说明，将逻辑结构设计阶段生成的关系模式中的空(5)～(8)补充完整。
【问题 4】 （3 分）
根据问题描述，写出客户、委托书和派工单这三个关系的主键。
第9题
●试题二
对文法G[S]：S→a|∧|(T)；T→T，S｜S；回答问题1～问题3。
【问题1】
对文法G进行改写，然后对每个非终结符写出不带回溯的递归子程序。
【问题2】
经改写后的文法是否是LL (1) 的?指出它的预测分析表中 (1) ～ (3) 处的内容。
【问题3】
说明输入串(a，a)是否为G的句子。
第10题
试题三（共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）设计模式，请说明该模式的内涵。
客服
TOP
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“上学吧”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
