2002年度系统设计师（高级程序员）下午试题

试题一

阅读以下说明和流程图1，回答问题1至问题3，将解答填入答题纸的对应栏内。
[说明] 

某城市电信局受理了许多用户申请在指定电话上开设长话业务。长话包括国内长途和国际长途。电信局保存了长话用户档案和长话业务档案。

长话用户档案的记录格式为：

长话业务档案的记录格式为：

电话用户每次通话的计费数据都自动地记录在电信局程控交换机的磁带上。计费数据的记录格式为：

该电信局为了用计算机自动处理长话收费以提高工作效率，开发了长话计费管理系统。该系统每月能为每个长话用户打印出长话缴费通知单。长话缴费通知单的记录格式为：

流程图 1 描述了该系统的数据处理过程。

该系统每天对原始的计费数据进行分类排序，并确定每个通话记录的通话类型(市话/国内长途/国际长途)，再根据话费单价文件，算出每个通话记录应收取的话费。因此，形成的日计费文件中，增加了两个数据项：通话类型和话费。该系统每日对日计费文件进行累计（按电话号码和通话类型，对该类型的话费进行累计，得到该电话号码该通话类型的当月话费总计），形成月计费文件。

月计费文件经过长话出帐处理形成长话帐单文件。长话帐单文件的记录格式为：

[流程图1]

[问题1]

(1)请说明流程图1中的文件 F0、F1 分别是哪个文件。

(2)处理 1 和处理 5 分别按照哪些数据项进行分类?
[问题2]

处理 4 能发现哪些错误(不需考虑设备故障错误)?
[问题3]

说明处理 6 的功能。

试题二

阅读下列说明和有关的图表，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
[说明]

A 公司决定为该市车站开发自动售票系统，系统的要求如下：

1、乘客能按以下三步操作购票：选定目的地；投入钱币；获得一张票；

2、当且仅当乘客选定目的地后，系统才接收投钱；每次投入的钱只购买一张票；

3、只要投入的钱不少于所需的票价，且票库中有所要求的票，则应尽快出票；

4、如需找钱，则在出票的同时应退还多余的钱；

5、如果乘客投入的钱不够票价，或者票库中没有所要求的票时，系统将全额退钱，并允许乘客另选目的地，继续购票；

6、出票前乘客可以按“取消”按钮取消购票，系统将全额退出该乘客投入的钱，并允许乘客另选目的地，继续购票；

7、出票结束（包括退还多余的钱）后，系统应保存销售记录，并等待乘客购票。

该系统还要求快速响应和操作同步，所以它应是一个实时系统。为此，A 公司在该系统的数据流程图中附加了过程控制部分，形成转换图。在该图中，控制流(事件流)用虚线表示，数据流用实线表示。图中的数据流并没有画全，需要考生填补。转换图如下：

对售票全过程进行的控制可以用系统内部各个状态之间的迁移来描述，从而形成状态迁移图。在状态迁移图中，用双线框表示状态，用有向边表示状态的迁移。引起状态迁移的事件以及由该事件引起的动作，在有向边旁用“”形式注明。状态迁移图如下：

状态迁移图

该公司还制作了一个过程启动表，用以表明状态迁移图中的4个动作与转换图中的4个过程之间的“启动”关系，即说明哪个动作将启动哪个过程。用1表示启动，用0表示不启动。启动的过程将根据获得的输入数据产生输出数据，未启动的过程则不会产生输出数据。

该表中没有列出的过程，其执行与否与事件无关。过程启动表如下：

[问题1]

转换图中缺少哪三条数据流?请指明每条数据流的名称、起点和终点。
[问题2]

在状态迁移图中，a，b，c 分别表示什么事件？请用转换图中给出的事件名解答。
[问题3]

在过程启动表中，d，e 处应填什么?请分别用 4 位二进制码表示。

试题三

阅读以下说明和流程图 3，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
[说明]

l、工作流（WorkFlow）的概念起源于生产组织和办公自动化领域，提出的目的是通过将工作分解成定义良好的任务、角色，按照一定的规则和过程来执行这些任务并对它们进行监控，达到提高工作效率、降低生产成本、提高企业生产经营管理水平和企业竞争力的目标。工作流包括两个方面：(1)由人或程序进行的任务或行为(即工作)；(2)这些任务或行为之间的关系(即流程)。

2、工作流的基本元素包括：

(1)工作流对象：在系统中流动的文档、表单、事件或消息。工作流对象有相应的起始点和终止点。工作流对象激发了一个工作流。

(2)角色：产生行为或接受行为的人或机构/部门。

(3)路由：在工作流中，工作流对象的起始点，中间点和终止点。工作流对象会在各个角色之间流动。

(4)规则：决定工作流对象路由的原则或条件。

3、某公司向客户交付系统产品后，由技术支持部门负责向客户提供技术服务。该技术支持部门的业务流程如下：

(1)当该技术支持部门接到一个客户问询电话时，由客户服务代表（CSR）接听该电话。

客户服务代表根据客户问询内容产生一份服务请求文件，并开始解决客户提出的问题。

(2)若客户服务代表解决了客户提出的问题，这份服务请求文件被标记为“已解决”。

(3)如果客户服务代表在2个小时内未能解决这个问题，客户服务代表将服务请求文件转交给技术支持代表(TSR)处理。

(4)如果技术支持代表也无法解决这个问题，他/她邀请助理工程师（ENGR）来一起处理这个问题。

(5)若助理工程师解决了这个问题，该服务请求文件被标记为“已解决”。

(6)若技术支持代表和助理工程师认为，是由于系统的错误引起的问题，则告知客户该问题目前无法解决；并把服务请求文件转交给本公司的工程部门处理。

(7)对已经解决的服务请求，每个月底进行一次归档(放入归档数据库)。

[问题1]

为了描述该技术支持部门的业务流程，首先需要确定工作流的各个基本元素。请按下表写出工作流对象以及对应的起始点、终止点和该工作流中的所有角色。

[问题2]

(1)请按下表写出描述该技术支持部门的工作流的路由和规则；

(2)流程图3描述了该技术支持部门的工作流程，请写出其中各个规则的含义。
[问题3]

通常，描述一组活动及其它们之间相互连接关系的模型称为过程模型。如本题描述该技术支持部门的业务流程的模型就是一个过程模型。请说明过程模型与工作流模型的主要区别及应用场合。
[流程图3]

试题四

在 COMET 型计算机上可以使用试卷上所附的 CASL 汇编语言。阅读程序说明和 CASL 程序，将应填入__(n)__处的字句，写在答题纸的对应栏内。
[程序说明]

本程序将 80 个 ASCII 编码的数字字符转换成 BCD 码(二十进制码)，并将每四个 BCD 码压缩在一个字中。见下面图示。

程序中约定原始数字字符存放在 SJ 开始的连续存区中，转换和压缩结果存放在 YS 开始的连续存区中。

[程序]

试题五

阅读下列程序说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。
[程序 5.1 说明]

“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N 件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于 S 。

如下程序均能求得“背包问题”的一组解，其中程序 5.1 是“背包问题”的递归解法，而程序 5.2 是“背包问题”的非递归解法。
[程序 5.1]
#include<stdio.h>
#define N 7
#define S 15
int w[N+1] = {0，1，4，3，4，5，2，7}；
int knap ( int S， int n)
{ if(S == 0) return 1；

if ( s<O || ( s>O && n<1 )) return 0；

if ( __(1)__ ) ) {

printf( "4d"，w[n] )；return 1；

} return __(2)__ ；
}
main() {

if ( knap(S，N) ) printf( "OK!\n" )；

else printf( "N0!\n" )；
}

[程序 5.2]
#include <stdio.h>
#define N 7
#define S 15
typedef struct {

int S；

int n：

int job；
} KNAPTP；
int w[N+1] = {0，1，4，3，4，5，2，7}；
int knap(int S，int n)；
main(){

if ( knap(S，N) ) printf("0K!\n" )；

else printf( "N0!\n" )；
int knap( int S，int n )
{ KNAPTP stack[100]，x；

int top， k， rep；

x.s = s； x.n = n；

x.job = 0；

top = l； stack[top] = x；

k = 0；

while ( __(3)__ )  {

x = stack[top]；

rep = l；

while ( !k && rep ) {

if( x.s＝0 ) k = 1； /*已求得一组解*/

else if ( x.S<0 || x.n<=0 ) rep = 0；

else { x.s = __(4)__ ； x.job=1；

__(5)__ = x；

}

}

if ( !k ) {

rep = 1；

while ( top >= 1 && rep) {

x = stack[top--]；

if ( x.job＝1){

x.s += w[x.n + 1]；

x.job = 2；

stack[++top] = x；

__(6)__ ；

}

}

}

}

if (k){   */输出一组解*/

while ( top >= 1 ) {

x = StaCk [ top-- ]；

if ( x.job == 1 )

printf ( "M\t，w[x.n+1] )；

}

}

return k；

}

试题六

阅读下列程序说明和 C++ 代码，将应填入__(n)__处的字句写在答卷的对应栏内。
[程序 6 说明]

本程序实现两个多项式的乘积运算。多项式的每一项由类 Item 描述，而多项式由类 List 描述。类 List 的成员函数有：

createList()：创建按指数降序链接的多项式链表，以表示多项式。

reverseList()：将多项式链表的表元链接顺序颠倒。

multiplyList( List L1，List 12 )计算多项式 L1 和多项式 L2 的乘积多项式。
[程序6]
#include <iostream．h>
class List；
class ltem {

friend class List；

private：

double quot；

int exp；

Item *next；

public：

Item( double_quot，int_exp)

{__(1)__；}

}；
class List{

private:

Item *list；

public：

List(){list：NULL；}

void reverseList()；

void multiplyList(List L1，List L2)；

void createList()；
}；
void List::createList()
{ Item *p， *U， *pre；

int exp；

double quot；

1ist = NULL；

while __(1)__ {

cout << "输入多项式中的一项(系数、指数)：" << endl；

cin >> quot >> exp：

if ( exp<0 ) break； //指数小于零，结束输入

if ( quot=0 ) continue；

p = list；

while ( __(2)__ ) { //查找插入点

pre = p；p = p->next；}

if ( p != NULL && exp ＝ p->exp ) { p->quot += quot；continue；}

u = __(3)__ ；

if (p == list)  list = u；

else pre->next = u；

u ->next = p；}
}
void List :: reverseList()
{ Item *p，*u；

if ( 1ist＝NULL ) return；

p = list ->next；list -> next = NULL；

while ( p != NULL) {

u = p -> next；p ->next = list；

list = p； p = u；}

}
void List :: multiplyList ( List L1，List L2 )
{ Item *pLl，*pL2，*u；

int k，maxExp；

double quot；

maxExp = __(4)__；

L2.reverseList()； list=NULL

for ( k = maxExp；k >= 0；k-- ){

pLl = L1.1ist；

while ( pLl != NULL && pLl -> exp > k ) pLl = pLl ->next；

pL2 = L2.1ist；

while (pL2 NULL && __(5)__ pL2 = pL2 -> next；

quot = 0.0；

while (pLl != NULL && pL2 != NULL){

if(pLl—>exp+pL2->exp’：k) {

__(6)__ ；

pLl = pLl -> next；pL2 = pL2 -> next；

} else if ( pLl -> exp + pL2 -> exp > k )  pLl = pLl -> next；

else pL2 = pL2 -> next；

}

if ( quot !=0.0 ){

u = new ltem( quot，k )；

u -> next = list；list = u；}

}

reverseList()； L2.reverseList()：
}
void main()
{ List L1，L2，L；

cout << "创建第一个多项式链表\n"； L1.createList()；

cout << "创建第二个多项式链表\n"； L2.createList()；

L.multiplyList ( L1，L2)；
}

回目录     老顽童整理校对 2003年2月