2003年度软件设计师下午试题

考试总分：6分

考试类型：模拟试题

作答时间：60分钟

已答人数：967

试卷答案：有

试卷介绍： 2003年度软件设计师下午试题

开始答题

试卷预览

1. 试题一阅读下列算法说明和流程图1，回答问题1至问题3，将解答填入答题纸的对应栏内。[算法说明]某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0（空闲）或l（占用）。客房是以房间（不是床位）为单位出租的。本算法根据几个散客的要求预订一间空房。程序的输入为：人数M，房间等级要求R（R=0表示任意等级都可以）。程序的输出为；所有可供选择的房间号。流程图1描述了该算法。[问题1]假设当前该旅馆各个房间的情况如下表：序号iROOMRANKNBEDSTATUS11013402102341320123042022415301160当输入M=4，R=0时，该算法的输出是什么?[问题2]如果等级为r的房间每人每天的住宿费为RATE(r)，RATE为数组。为使该算法在输出每个候选的房间号RM(J)后，再输出这批散客每天所需的总住宿费DAYRENT(J)，流程图1的β所指框中的最后处应增加什么处理?[问题3]如果限制该算法最多输出K个可供选择的房间号，则在流程图1的α所指的判断框应改成什么处理?[15分]

2. 试题二阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。[说明]甲公司的经营销售业务目前是手工处理的，随着业务量的增长，准备采用关系数据库对销售信息进行管理。经销业务的手工处理主要涉及三种表：订单、客户表和产品表。为了用计算机管理销售信息，甲公司提出应达到以下

A(1)____WHERE___

B(2)___(SELECT*FROMOrderDetailB，OrderCWHEREB．ProductNo=C.ProductNoANDB．ProductNo='1KIO'ANDC．CustomerNo=A.CustomerNo)[15分]

3. 试题三阅读下列说明和有关的图，回答问题1至问题4，将解答填入答题纸的对应栏内。[说明]某制造企业的物料出入库管理的工作流程分别叙述如下：1．出库工作流程①领料人提交领料单(每一种物料有一张领料单)；②仓库保管员根据领料计划单检验该领料单是否有效；⑨若经检验没有相应的领料计划，则通知领料人该领料单无效；④若领料单有效，仓库保管员根据领料单上的物料代码核对是否有足够的库存；⑤若没有足够的库存，仓库保管员向领料人发缺货单；⑥若有足够的库存，仓库保管员在领料单上签字，并登记出库单，修改物料主文件中的现有库存数；相应的物料出库，物料清单交领料人。2．入库工作流程①采购员提交入库申请单(每一种物料有一张入库申请单)；②仓库保管员根据采购计划单验收入库申请单；⑧若验收发现没有相应的采购计划，则仓库保管员向采购员发无效申请单：④若验收合格，则仓库保管员向检验员申请物料检验；检验员根据检验结果填写物料检验单。⑤如果物料或供货方不合格，则向采购员发出退货单；⑥如果检验合格，则仓库保管员登记入库单，修改物料主文件中的现有库存数，相应的物料入库。为便于及时了解库存情况、核查出入库情况，该企业决定将上述人工流程由计算机来实现。在设计该系统时，采用了两种方法：结构化方法和面向对象方法。图3.1给出了物料出入库系统的数据流图，图中的数据流并没有画全，需要考生填补。图3.2给出了采用面向对象方法所认定出的类。[问题1]图3.1中缺少了那些数据流?请指明每条数据流的名称、起点和终点。[问题2]给出“领料单”和“入库申请单”这两个类至少应具有的属性。[问题3]为建立功能完善的库存管理系统，除了查询、统计、报表输出功能外，还应具有哪些对提高企业效益至关重要的功能?[问题4]用面向对象方法设计的类中，有一些类的对象是需要持久存储的，这样的类一般需要映射到关系数据库模式中。请指出图3.2中哪些类需要做这样的映射。[15分]

4. 试题五阅读以下预备知识、函数说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。[预备知识]①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合<a，b，c，d}及其权值2、7、4、5，可构造如下所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)。结构数组Ht的类型定义如下：#defineMAXLEAFNUM20structnode{charch；/*扫当前结点表示的字符，对于非叶子结点，此域不用*/intweight；/*当前结点的权值*/intparent；/*当前结点的父结点的下标，为0时表示无父结点*/intlchild，rchild；/*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/｝Ht[2*MAXLEAFNUM]；②用'0'或'1'标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用'0'('1')标识该分支(示例见上图)。③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由‘0’、‘1’组成的一个序列，称此序列为该叶子结点的前缀编码。例如上图所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。[函数5.1说明]函数voidLeafCode(introot，intn)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。在构造过程中，将Ht[p].weight域用作被遍历结点的遍历状态标志。[函数5.1]char**HC；voidLeafCode(introot，intn){/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/inti，p=root，cdlen=0;charcode[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';}elseif(Ht[p].rchild==0){/*若是叶子结点，则保存其前缀编码*/Hc[p]=(char*)malloc((cdlen+1)*sizeof(char));___(1)___;strcpy(Hc[p]，code)；}}elseif(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说明]函数voidDecode(char*buff，introot)的功能是：将前缀编码序列翻译成叶子结点的字符序列，并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。[函数5.2]voidDecode(char*buff，introot){intpre=root，p;while(*buff!='\0'){p=root;while(p!=0){/*存在下标为p的结点*/pre=p；if(__(4)___)p=Ht[p].lchild；/*进入左子树*/elsep=Ht[p].rchild：／*进入右子树*／buff++;／*指向前缀编码序列的下一个字符*／}___(5)___;printf("％c"，Ht[pre].ch);}}[15分]

A(1)___;strcpy(Hc[p]，code)；}}elseif(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=__

B(2)__;___

C(3)___;／*退回父结点*／}}／*while结束*／}[函数5.2说明]函数voidDecode(char*buff，introot)的功能是：将前缀编码序列翻译成叶子结点的字符序列，并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。[函数5.2]voidDecode(char*buff，introot){intpre=root，p;while(*buff!='\0'){p=root;while(p!=0){/*存在下标为p的结点*/pre=p；if(__

D(4)___)p=Ht[p].lchild；/*进入左子树*/elsep=Ht[p].rchild：／*进入右子树*／buff++;／*指向前缀编码序列的下一个字符*／}___

E(5)___;printf("％c"，Ht[pre].ch);}}[15分]

5. 试题四在COMET型计算机上可以使用试卷上所附的CASL汇编语言，阅读程序说明和CASL程序，把应填入___(n)___处的字句写在答卷的对应栏内。[程序4说明]本程序统计出考试成绩在80分以上(含80分)、60分到79分、低于60分的学生人数，并将统计结果存放在以CHJG为首地址的连续三个内存单元中。学生的成绩数据连续存放在以XSCH为首地址的内存空间中，以数据-1作为结束标志。[程序4]STARTBEGINXSCHDC90；……；此处的数据未完全列出；……DC-1CHJBDC80DC60CHJGDC0DC0DC0ONEDC1BEGIN___(1)___LEAGR1，0;给GR1赋初值0NEXTLDGR2，XSCH，GR1;把一个学生成绩读入GR2LEAGR0，0，GR2;把GR2的内容读入GR0JMIEXIT如果GR2中的数小于0，LEAGR2，0;给GR2赋初值0CPAGR0，CHJB;比较GR0与CHJB的大小,由于CHJB=80，所以此处所做的工作是看成绩是否大于等于80分JPZGOON;如果成绩大于等于80分则跳到GOON继续执行____(2)____LEAGR2,1,GR2;GR2+1->GR2，____(3)____CPAGR0,CHJB,GR2;当成绩小于80分时，再看成绩是不是大于等于60分JPZGOON;如果成绩大于等于60分则跳到GOON继续执行LEAGR2，1，GR2;GR2+1->GR2GOON___(4)____LDGR0,CHJG,GR2;把当前成绩对应的统计结果取出。(CHJG+0)存的是80分以上的人数，(CHJG+1)存的是60分以上的人数，(CHJG+,2)存的是60分以下的人数。___(5)____ADDGR0,ONE;把取出的统计人数加1，即把当前成绩统计进去。STGR0，CHJG，GR2;把新统计结果存入。LEAGR1，1，GR1;GR1+1->GR1;指针下移一条记录，即使得(LDGR2，XSCH，GR1)取下一个成绩。JMPNEXT;无条件转移至NEXTEXITEXITEND[15分]

A(1)___LEAGR1，0;给GR1赋初值0NEXTLDGR2，XSCH，GR1;把一个学生成绩读入GR2LEAGR0，0，GR2;把GR2的内容读入GR0JMIEXIT如果GR2中的数小于0，LEAGR2，0;给GR2赋初值0CPAGR0，CHJB;比较GR0与CHJB的大小,由于CHJB=80，所以此处所做的工作是看成绩是否大于等于80分JPZGOON;如果成绩大于等于80分则跳到GOON继续执行____

B(2)____LEAGR2,1,GR2;GR2+1->GR2，____

C(3)____CPAGR0,CHJB,GR2;当成绩小于80分时，再看成绩是不是大于等于60分JPZGOON;如果成绩大于等于60分则跳到GOON继续执行LEAGR2，1，GR2;GR2+1->GR2GOON___

D(4)____LDGR0,CHJG,GR2;把当前成绩对应的统计结果取出。(CHJG+0)存的是80分以上的人数，(CHJG+1)存的是60分以上的人数，(CHJG+,2)存的是60分以下的人数。___

E(5)____ADDGR0,ONE;把取出的统计人数加1，即把当前成绩统计进去。STGR0，CHJG，GR2;把新统计结果存入。LEAGR1，1，GR1;GR1+1->GR1;指针下移一条记录，即使得(LDGR2，XSCH，GR1)取下一个成绩。JMPNEXT;无条件转移至NEXTEXITEXITEND[15分]

6. 试题六阅读以下说明和C++代码，将应填入__(n)__处的字句写在答题纸的对应栏内。[说明]本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数；a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值；c为二维数组，存储有向网中每一对顶点间的最短路径长度；kay为二维数组，存储最短路径，kay[i][j]=k表示顶点i到达顶点j的最短路径必须经过顶点k.类中的主要成员函数有：Input():输入有向网的顶点数、各条弧及权值，建立带权邻接矩阵a。若顶点i到顶点j有弧，则a[i][j]取弧上的权值，否则a[i][j]的值取NoEdge。AllPairs()：用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。OutShortestPath(inti，intj)：计算顶点i到顶点j的最短路径。outputPath(inti，intj)：输出顶点i到顶点j的最短路径上的顶点。Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2...,Cn，其中C0是已知的带权邻接矩阵a，Ck(i，j)(0≤ij#defineNoEdge10000／／当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示voidMake2DArray(int**&x，introws，intcols);classAdjacencyWDigraph{private：intn；／／有向网中的顶点数目int**a；／／存储顶点间弧上的权值int**c；／／存储计算出的最短路径长度int**kay；／／存储求出的最短路径public：intVertices()const{returnn；}voidAllPairs()；voidInput()；／／输入有向网的顶点数、各条弧及权值，建立邻接矩阵avoidOutShortestPath(inti,intj)；／／计算顶点i到j的最短路径(试卷中未列出)~AdjacencyWDigraph()；／／析构函数(试卷中未列出)private：voidoutputPath(inti，intj);};voidAdjacencyWDigraph::AllPairs(){inti，j，k，t1，t2，t3；for(i=1；i>n;cout>E;Make2DArray(a，n+1，n+1);for(i=1;i>u>>v>>w;a[u][v]=w;}}voidMake2DArray(int**&x，introws，intcols){inti，j；x=newint*[rows+1]；for(i=0;i<rows+1;i++)x[i]=newint[cols+1];for(i=1;i<=rows;i++)for(j=1;j<=cols;j++)x[i][j]=0;}[15分]

A(1)___;kay[i][j]=0;}for(k=1;k<=n;k++)for(i=1;i<=n;i++){if(i==k)continue;t1=c[i][k];for(j=1;j<=n;j++){if(j==k||j==i)continue;t2==c[k][j];t3==c[i][j];if(t1!=NoEdge&&t2!=NoEdge&&(t3==NoEdge||t1+t2<t3)){c[i][j]=___

B(2)___;kay[i][j]=___

C(3)___;}}//for}//for}voidAdjacencyWDigraph::outputPath(inti，intj){//输出顶点i到j的最短路径上的顶点if(i==j)return;if(kay[i][j]==0)cout<<j<<’’;else{outputPath(i,___

D(4)___);outputPath(____

E(5)____);}}voidAdjacencyWDigraph::Input(){inti，j，u，v，w，E;cout>n;cout>E;Make2DArray(a，n+1，n+1);for(i=1;i>u>>v>>w;a[u][v]=w;}}voidMake2DArray(int**&x，introws，intcols){inti，j；x=newint*[rows+1]；for(i=0;i<rows+1;i++)x[i]=newint[cols+1];for(i=1;i<=rows;i++)for(j=1;j<=cols;j++)x[i][j]=0;}[15分]