1.
试题一(共15分)
阅读以下说明和图,回答问题1至问题3.将解答填入答题纸的对应栏内。
【说明】
某时装邮购提供商拟开发订单处理系统,用于处理客户通过电话、传真、邮件或Web站点所下订单。其主要功能如下:
(1)增加客户记录。将新客户信息添加到客户文件,并分配一个客户号以备后续使用。
(2)查询商品信息。接收客户提交商品信息请求,从商品文件中查询商品的价格和可订购数量等商品信息,返回给客户。
(3)增加订单记录。根据客户的订购请求及该客户记录的相关信息,产生订单并添加到订单文件中。
(4)产生配货单。根据订单记录产生配货单,并将配货单发送给仓库进行备货;备好货后,发送备货就绪通知。如果现货不足,则需向供应商订货。
(5)准备发货单。从订单文件中获取订单记录,从客户文件中获取客户记录,并产生发货单。
(6)发货。当收到仓库发送的备货就绪通知后,根据发货单给客户发货;产生装运单并发送给客户。
(7)创建客户账单。根据订单文件中的订单记录和客户文件中的客户记录,产生并发送客户账单,同时更新商品文件中的商品数量和订单文件中的订单状态。
(8)产生应收账户。根据客户记录和订单文件中的订单信息,产生并发送给财务部门应收账户报表。
现采用结构化方法对订单处理系统进行分析与设计,获得如图1-1所示的顶层数据流
图和图1-2所示0层数据流图。
【问题1】(3分)
使用说明中的词语,给出图1-1中的实体E1~E3的名称。
【问题2)(3分)
使用说明中的词语,给出图1-2中的数据存储D1~D3的名称。
【问题3】(9分)
(1)给出图1-2中处理(加工)P1和P2的名称及其相应的输入、输出流。
(2)除加工P1和P2的输入输出流外,图1-2还缺失了1条数据流,请给出其起点和终点。
注:名称使用说明中的词汇,起点和终点均使用图1-2中的符号或词汇。
2.
试题二(共15分)
阅读以下说明,回答问题1至问题3,将解答填入答题纸的对应栏内。
【说明】
某公司拟开发一套小区物业收费管理系统。初步的需求分析结果如下:
(1)业主信息主要包括:业主编号,姓名,房号,房屋面积,工作单位,联系电话等。房号可唯一标识一条业主信息,且一个房号仅对应一套房屋;一个业主可以有一套或多套的房屋。
(2)部门信息主要包括:部门号,部门名称,部门负责人,部门电话等;一个员工只能属于一个部门,一个部门只有一位负责人。
(3)员工信息主要包括:员工号,姓名,出生年月,性别,住址,联系电话,所在部门号,职务和密码等。根据职务不同员工可以有不同的权限,职务为“经理”的员工具有更改(添加、删除和修改)员工表中本部门员工信息的操作权限;职务为“收费”的员工只具有收费的操作权限。
(4)收费信息包括:房号,业主编号,收费日期,收费类型,数量,收费金额,员工号等。收费类型包括物业费、卫生费、水费和电费,并按月收取,收费标准如表2-1所示。其中:物业费=房屋面积(平方米)×每平米单价,卫生费=套房数量(套)×每套庆单价,水费=用水数量(吨)×每吨水单价,电费=用电数量(度)X每度电单价。
(5)收费完毕应为业主生成收费单,收费单示例如表2-2所示
【概念模型设计】
根据需求阶段收集的信息,设计的实体联系图(不完整)如图2-1所示。图2-1中收费员和经理是员工的子实体。
【逻辑结构设计】
根据概念模型设计阶段完成的实体联系图,得出如下关系模式(不完整);
业主((1),姓名,房屋面积,工作单位,联系电话)
员工((2),姓名,出生年月,性别,住址,联系电话,职务,密码)
部门((3),部门名称,部门电话)
权限(职务,操作权限)
收费标准(4)
收费信息((5),收费类型,收费金额,员工号)
【问题1】(8分)
根据图2-1,将逻辑结构设计阶段生成的关系模式中的空(1)~(5)补充完整,然后给出各关系模式的主键和外键。
【问题2】(5分)
填写图2-1中(a)~(f)处联系的类型(注:一方用1表示,多方用m或n或*表示),并补充完整图2-1中的实体、联系和联系的类型。
【问题3】(2分)
业主关系属于第几范式?请说明存在的问题。
4.
试题四(共15分)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下:
对于n个元素的关键字序列{al,a2,…,an},当且仅当满足下列关系时称其为堆。
在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素,则称
为小顶堆。堆常用完全二叉树表示,图4-1是一个大顶堆的例子。
堆数据结构常用于优先队列中,以维护由一组元素构成的集合。对应于两类堆结构,优先队列也有最大优先队列和最小优先队列,其中最大优先队列采用大顶堆,最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大顶堆A,且已经实现了调整堆的函数heapify(A,n,index)。
下面将C代码中需要完善的三个函数说明如下:
(1) heapMaximum(A):返回大顶堆A中的最大元素。
(2) heapExtractMax(A):去掉并返回大顶堆A的最大元素,将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大顶堆。
(3) maxHeaplnsert(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)函数maxHeaplnsert
int maxHeaplnsert(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和maxHeaplnsert的时间复杂度的紧致上界分别为(6)、(7)和(8)(用O符号表示)。
【问题3】(2分)
若将元素10插入到堆A=(15,13,9,5,12,8,7,4,0,6,2,1)中,调用maxHeaplnsert
函数进行操作,则新插入的元素在堆A中第(9)个位置(从1开始)。
5.
试题五(共15分)
阅读下列说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某公司的组织结构图如图5-1所示,现采用组合(Composition)设计模式来构造该公
司的组织结构,得到如图5-2所示的类图。
其中Company为抽象类,定义了在组织结构图上添加(Add)和删除(Delete)分公司/办事处或者部门的方法接口。类ConcreteCompany表示具体的分公司或者办事处,分公司或办事处下可以设置不同的部门。类HRDepartment和FinanceDepartment分别表示人力资源部和财务部。
【C++代码】
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Company{//抽象类
protected:
string name;
public:
Company(string name){(1)=name;}
(2);//增加子公司、办事处或部门
(3);//删除子公司、办事处或部门
};
class ConcreteCompany:public Company{
private:
list< (4)>children;//存储子公司、办事处或部门
public:
ConcreteCompany(string name):Company(name){}
void Add(Company* c){(5) .push back(c);}
void Delete(Company* c){(6).remove(c);}
};
class HRDepartment:public Company{
public:
HRDepartment(string name):Company(name){}//其它代码省略
};
class FinanceDepartment:public Company{
public:
FinanceDepartment(string name):Company(name){}//其它代码省略
};
void main(){
ConcreteCompany *root=new ComcreteCompany(“北京总公司”,);
root->Add(new HRDepartment(“总公司人力资源部”)):
root->Add(new FinanceDepartment(“总公司财务部”));
ConcreteCompany *comp=new ConcreteCompany(“上海分公司”);
comp->Add(new HRDepartment(“上海分公司人力资源部”));
comp->Add(new FinanceDepartment(“上海分公司财务部”));
(7);
ConcreteCompany *compl=new ConcreteCompany(“南京办事处”,):
comp l->Add(new HRDepartment(“南京办事处人力资源部”));
comp l->Add(new FinanceDepartment(“南京办事处财务部”)):
(8);//其它代码省略
}
6.
试题六(共15分)
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某公司的组织结构图如图6-1所示,现采用组合(Composition)设计模式来设计,得到如图6-2所示的类图。
其中Company为抽象类,定义了在组织结构图上添加(Add)和删除(Delete)分公司/办事处或者部门的方法接口。类ConcreteCompany表示具体的分公司或者办事处,分公司或办事处下可以设置不同的部门。类HRDepartment和FinanceDepartment分别表示人力资源部和财务部。
【Java代码】
import java.util.*:
(1) Company{
protected String name;
public Company(String name){(2)=name:}
public abstract void Add(Company c);//增加子公司、办事处或部门
public abstract void Delete(Company c);//删除子公司、办事处或部门
}
class ConcreteCompany extends Company{
private List< (3) > children=new ArrayList< (4) >();
//存储子公司、办事处或部门
public ConcreteCompany(String name){super(name);}
public void Add(Company c){(5) .add(c);}
public void Delete(Company c){(6).remove(c);}
}
class HRDepartment extends Company{
public HRDepartment(String name){super(name);}
//其它代码省略
}
class FinanceDepartment extends Company{
public FinanceDepartment(String name){super(name);}
//其它代码省略
}
public class Test{
public static void main(String[] args){
ConcreteCompany root=new ConcreteCompany(“北京总公司”):
root.Add(new HRDepartment(“总公司人力资源部”)):
root.Add(new FinanceDepartment(“总公司财务部”)):
ConcreteCompany comp=new ConcreteCompany(“上海分公司”):
comp.Add(new HRDepartment(“上海分公司人力资源部”));
comp.Add(new FinanceDepartment(“上海分公司财务部”));
(7);
ConcreteCompany comp =new ConcreteCompany(“南京办事处”);
compl.Add(new HRDepartment(“南京办事处人力资源部”)):
compl.Add(new FinanceDepartment(“南京办事处财务部”):
(8);//其它代码省略
}
}