●试题一
阅读以下说明和流程图(如图1所示),回答问题1至问题4,将答案写在答卷的对应栏内。
【说明】
本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式
(A-(B*C+D)*E)/(F+G))
的后缀表示为
ABC*D+E*-FG+/
为了方便,假定变量名为单个英文字母,运算符只有+、-、*、/(均为双目运算符,左结合),并假定所提供的算术表达是非空且语法是正确的。另外,中缀表示形式中无空格符,但整个算术表达式以空格符结束。流程图中使用的符号的意义如下:
数组IN[]存储中缀表达式;
数组POLISH[]存储其后缀表达式;
数组S[]是一个后进先出栈;
函数PRIOR(CHAR)返回符号CHAR的优先级,各符号的优先级见表2:
【问题1】
填充流程图中①的判断条件。
【问题2】
写出子程序A的功能,并顺序写出实现该功能的操作
【问题3】
写出子程序B的功能,并顺序写出实现该功能的操作。
【问题4】
中缀表达式
(A+B-C*D)*(E-F)/G
经该流程图处理后的输出是什么?
【流程图】
图1
第1题
●试题四
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。
【说明】
下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是连通网的最小生成树。该算法的基本思想是:为使生成树上总的权值之和达到最小,则应使每一条边上的权值尽可能地小,自然应从权值最小的边选起,直至选出n-1条互不构成回路的权值最小边为止。
图5算法流程图
【算法】
/*对图定义一种新的表示方法,以一维数组存放图中所有边,并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/
typedef struct{
VertexType vex1;
VertexType vex2;
VRType weight;
}EdgeType;
typedef ElemType EdgeType;
typedef struct{//有向网的定义
VertexType vexs[MAX_VERTEX_NUM];//顶点信息
EdgeType edge[MAX_EDGE_NUM];//边的信息
int vexnum,arcnum;//图中顶点的数目和边的数目
}ELGraph;
void MiniSpanTree_Kruskal(ELGraph G,SqList& MSTree){
//G.edge 中依权值从小到大存放有向网中各边
//生成树的边存放在顺序表MSTree中
MFSetF;
InitSet(F,G.vexnum);//将森林F初始化为n棵树的集合
InitList(MSTree,G.vexnum);//初始化生成树为空树
i=0;k=1;
while(k< (1) ){
e=G.edge[i];//取第i条权值最小的边
/*函数fix_mfset返回边的顶点所在树的树根代号,如果边的两个顶点所在树的树根相同,则说明它们已落在同一棵树上。*/
rl=fix_mfset(F,LocateVex(e.vex1));
r2= (2) //返回两个顶点所在树的树根
if(r1 (3) r2){//选定生成树上第k条边
if(ListInsert(MSTree,k,e){ (4) ;//插入生成树
mix_mfset(E,rl,r2);//将两棵树归并为一棵树
}
(5) ;//继续考察下一条权值最小边
}
DestroySet(F);
}
第2题
●试题二
阅读下列说明、流程图和算法,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A[i],并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如下:
【流程图】
图3流程图
【算法说明】
将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
【算法】
void sort (int A[], int 1,int H){
if ( L<H){
k=p(A,L,R);//p()返回基准数在数组A中的下标
sort( (4) );//小于基准数的元素排序
sort( (5) );//大于基准数的元素排序
}
}
第3题
试题一(共15 分)
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。
【说明】
某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求,欲构建数据管理中间件,其主要功能如下:
(1)数据管理员可通过中间件进行用户管理、操作管理和权限管理。用户管理维护用户信息,用户信息(用户名、密码)存储在用户表中;操作管理维护数据实体的标准操作及其所属的后端数据库信息,标准操作和后端数据库信息存放在操作表中;权限管理维护权限表,该表存储用户可执行的操作信息。
(2)中间件验证前端应用提供的用户信息。若验证不通过,返回非法用户信息;若验证通过,中间件将等待前端应用提交操作请求。
(3)前端应用提交操作请求后,中间件先对请求进行格式检查。如果格式不正确,返回格式错误信息;如果格式正确,则进行权限验证 (验证用户是否有权执行请求的操作),若用户无权执行该操作,则返回权限不足信息,否则进行连接管理。
(4)连接管理连接相应的后台数据库并提交操作。连接管理先检查是否存在空闲的数据库连接,如果不存在,新建连接;如果存在,则重用连接。
(5)后端数据库执行操作并将结果传给中间件,中间件对收到的操作结果进行处理后,将其返回给前端应用。
现采用结构化方法对系统进行分析与设计,获得如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。
【问题1】(3 分)
使用说明中的词语,给出图1-1中的实体E1~E3的名称。
【问题2】(3 分)
使用说明中的词语,给出图1-2中的数据存储D1~D3的名称。
【问题3】(6 分)
给出图1-2中加工P 的名称及其输入、输出流。
除加工P 的输入与输出流外,图1-2还缺失了两条数据流,请给出这两条数据流的起点和终点。
注:名称使用说明中的词汇,起点和终点均使用图1-2中的符号或词汇。
【问题4】(3 分)
在绘制数据流图时,需要注意加工的绘制。请给出三种在绘制加工的输入、输出时可
能出现的错误。
第4题
【问题2】(7分)
考虑表4-1的实例,假设有3个物品,背包容量为22。图4-1中是根据上述算法构造的搜索树,其中结点的编号表示了搜索树生成的顺序,边上的数字1/0分别表示选择/不选择对应物品。除了根结点之外,每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值,右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解,应该选择物品 (5) ,获得的价值为 (6) 。
对于表4-1的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为 (7) ,而用了上述回溯法,搜索树的结点数为 (8) 。
第5题
试题二(共15 分)
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。
【说明】
某学校拟开发一套实验管理系统,对各课程的实验安排情况进行管理。
【需求分析】
一个实验室可进行多种类型不同的实验。由于实验室和实验员资源有限,需根据学生人数分批次安排实验室和实验员。一门课程可以为多个班级开设,每个班级每学期可以开设多门课程。一门课程的一种实验可以根据人数、实验室的可容纳人数和实验类型,分批次开设在多个实验室的不同时间段。一个实验室的一次实验可以分配多个实验员负责辅导实验,实验员给出学生的每次实验成绩。
(1)课程信息包括:课程编号、课程名称、实验学时、授课学期和开课的班级等信息;实验信息记录该课程的实验进度信息,包括:实验名、实验类型、学时、安排周次等信息,如表2-1所示。
【概念模型设计】
根据需求阶段收集的信息,设计的实体联系图(不完整)如图2-1所示。
【逻辑结构设计】
根据概念模型设计阶段完成的实体联系图,得出如下关系模式(不完整):
课程(课程编号,课程名称,授课院系,实验学时)
班级(班级号,专业,所属系)
开课情况( (1) ,授课学期)
实验( (2) ,实验类型,难度,学时,安排周次)
实验计划( (3) ,实验时间,人数)
实验员( (4) ,级别)
实验室(实验室编号,地点,开放时间,可容纳人数,实验类型)
学生( (5) ,姓名,年龄,性别)
实验成绩( (6) ,实验成绩,评分实验员)
【问题1】(6 分)
补充图2-1中的联系和联系的类型。
【问题2】(6 分)
根据图2-1,将逻辑结构设计阶段生成的关系模式中的空(1)~(6)补充完整并用下划线指出这六个关系模式的主键。
【问题3】(3分)
如果需要记录课程的授课教师,新增加“授课教师”实体。请对图 2-1 进行修改,画出修改后的实体间联系和联系的类型。
第6题
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某灯具厂商欲生产一个灯具遥控器,该遥控器具有7个可编程的插槽,每个插槽都
有开关按钮,对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌
灯具的开关,现采用Command(命令)模式实现该遥控器的软件部分。command模式
的类图如图6-1所示。
【Java代码】
}
第7题
阅读下列说明和c++代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某灯具厂商欲生产一个灯具遥控器,该遥控器具有7个可编程的插槽,每个插槽都
有开关按钮,对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌
灯具的开关,现采用Command(命令)模式实现该遥控器的软件部分。Command模式
的类图如图5-1所示。
【c++代码】
}
第8题
阅读下列说明和C代码,回答问题l至问题3.将解答写在答题纸的对应栏内。
【说明】
计算一个整数数组a的最长递增子序列长度的方法描述如下:
假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长
递增子序列的长度,则数组a的最长递增子序列的长度为器;其中b[i]满足最优子结构,可递归定义为:
【c代码】
下面是算法的c语言实现。
(1)常量和变量说明
a:长度为n的整数数组,待求其最长递增子序列
b:长度为n的数组,b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长度,
其中0≤i<n
len:最长递增子序列的长度
i.j:循环变量
temp,临时变量
(2)C程序
include <stdio . h>
int maxL (int *b. int n) {
int i. temp =0;
For(i = 0; i < n; i++){
if (b[i] > temp )
Temp= b[i];
}
Return temp;
【问题l】(8分)
根据说明和C代码,填充C代码中的空(1)~(4)。
【问题2】(4分)
根据说明和C代码,算法采用了(5)设计策略,时间复杂度为(6)(用O符号表示)。
【问题3】(3分)
已知数组a={3,10,5,15,6,8},根据说明和C代码,给出数组b的元素值。
第9题
阅读下列说明和图,回答问题1至问题3.将解答填入答题纸的对应栏内。
【说明】
某公司欲开发一个管理选民信息的软件系统。系统的基本需求描述如下:
(1)每个人(Person)可以是一个合法选民(Eligible)或者无效的选民(Ineligible)。
(2)每个合法选民必须通过该系统对其投票所在区域(即选区,Riding)进行注册
(Registration)。每个合法选民仅能注册一个选区。
(3)选民所属选区由其居住地址(Address)决定。假设每个人只有一个地址,地址
可以是镇( Town)或者城市(City)。
(4)某些选区可能包含多个镇,而某些较大的城市也可能包含多个选区。
现采用面向对象方法对该系统进行分析与设计,得到如图3-1所示的初始类图。
【问题1】(8分)
根据说明中的描述,给出图3-1中C1-C4所对应的类名(类名使用说明中给出的
英文词汇)。
【问题2】(3分)
根据说明中的描述,给出图3-1中Ml-M6处的多重度
【问题3】(4分)
现对该系统提出了以下新需求:
(l)某些人拥有在多个选区投票的权利,因此需要注册多个选区:
(2)对于满足(1)的选民,需要划定其“主要居住地”,以确定他们应该在哪个
选区进行投票。
为了满足上述需求,需要对图3-1所示的类图进行哪些修改?请用100字以内
文字说明。
第10题
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内,
【说明】
某集团公司在全国不同城市拥有多个大型超市,为了有效管理各个超市的业务工
作,需要构建一个超市信息管理系统。
【需求分析结果】
(l)超市信息包括:超市名称、地址、经理和电话,其中超市名称唯一确定超市关
系的每一个元组。每个超市只有一名经理。
(2)超市设有计划部、财务部、销售部等多个部门,每个部门只有一名部门经理,
有多名员工,每个员工只属于一个部门。部门信息包括:超市名称、部门名称、部门经
理和联系电话。超市名称、部门名称唯一确定部门关系的每一个元组。
(3)员工信息包括:员工号、姓名、超市名称、部门名称、职位、联系方式和工资。
其中,职位信息包括:经理、部门经理、业务员等。员工号唯一确定员工关系的每一个
元组。
(4)商品信息包括:商品号、商品名称、型号、单价和数量。商品号唯一确定商品
关系的每一个元组。一名业务员可以负责超市内多种商品的配给,一种商品可以由多名
业务员配给。
【概念模型设计】
根据需求分析阶段收集的信息,设计的实体联系图和关系模式(不完整)如下:
【关系模式设计】
超市(超市名称,经理,地址,电话)
部门((a) ,部门经理,联系电话)
员工((b) .姓名,联系方式,职位,工资)
商品(商品号,商品名称,型号,单价,数量)
配给((c) ,配给时间,配给数量,业务员)
【问题1】(4分)
根据问题描述,补充四个联系,完善图2-1的实体联系囝。联系名可用联系1、联
系2、联系3和联系4代替,联系的类型分为1:1、l:n和m:n(或1:1、1:*和*:*)。
【问题2】(7分)
(1)根据实体联系图,将关系模式中的空(a)~(c)补充完整:
(2)给出部门和配给关系模式的主键和外键。
【问题3】(4分)
(l)超市关系的地址可以进一步分为邮编、省、市、街道,那么该属性是属于简单
属性还是复合属性?请用100字以内文字说明。
(2)假设超市需要增设一个经理的职位,那么超市与经理之间的联系类型应修改为
(d) ,超市关系应修改为 (e) 。
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!