1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 9及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【说明】 某供销系统接受顾客的订货单。当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采货单；当某配件的库存量大于或等于订购量时，或者收到供应商的送货单并更新了库存后，向顾客发出提货单。该系统还可随时向总经理提供销售和库存情况表。 该供销系统的分层数据流图中部分数据流和文件的组成如下： 【文件】 配件库存 =配件名 +规格 +数量 +允许的最低率库存量 【数据流】 订货单配 件号 +配件名 +规格 +数量 +顾客名 +地址 提供单 =订货单 +金额 采
2、货单配件号 +配件名 +规格 +数量 +供应商名十地址 送货单 =配件号 +配件名 +规格 +数量 +金额 假定顶层图是正确的， “供应商 ”文件已由其他系统生成。 【数据流图】 假定题中提供的顶层图是正确的，请回答下列问题： 1 指出哪张图中缺少了哪些文件。 2 指出在哪些图中遗漏了哪些数据流。回答时请用如下形式之一： XX图中遗漏了 XX加工 (或文件 )流向 XX加工 (或文件 )的 XX数据流。或 XX加工 XX遗漏了输入 (或输出 )数据流 XX。 3 【流程图 】 3 上面程序的功能是什么 ? 4 若数组 a输入的数为 (10,8,15,2,7,13,4，请写出 a的前三次输出结果
3、。 5 【说明】 某公司要开发一个销售管理系统，该系统的主要功能是：处理客户和销售员送来的订单；工厂是根据订货安排生产的，交出货物同时开出发票，收到客户付款后，根据发票存根进行应收款处理。每张订单由订单号，若干头信息和订单细节组成。一张订单可定购多种产品，工厂对大宗订货给予优惠。每种产品都规定了不同订货数量的折扣。 根据 上述要求公司的销售部王经理写下了以下数据表结构： 客户： (客户号，客户名，地址，电话 ) 订单： (订单号，客户号，产品号，订货数，订货日期，交货日期，金额 ) 应收账款： (客户号，订单号，发票号，应收金额，支付日期，支付金额，当前余额 ) 产品描述： (产品号，产品名，
4、单价，重量 ) 折扣规则： (产品号，订货量，折扣 ) 5 上表中带下划线的为主码。请为还没有确定主码或是主码不合理的数据表选定最合适的主码。 6 上面的关系模式中还有不是第二范式的，请将其转为第二范式。并确定新数据表的主码。 7 【说明】 中国教育科研网受理了许多用 户 (高校和研究机构 )中请在指定 IP上开设网络访问业务。网络访问包括国内流量和国际流量。教育科研网管理中心保存了网络访问用户档案和网络访问业务档案。【流程图】 下面的流程图描述了该系统的数据处理过程。该系统每天对原始的计费数据进行分类排序，并确定每个网络访问记录的访问类型 (本地 /国内 /国际 )，冉根据流量费用单价文件，
5、算出每个记录应收取的费用。因此，形成的日计费文件中增加了两个数据项：访问类型和话费。该系统每日对日计费文件进行累计 (按 IP地址和访问类型，对该类型的费用进行累计，得到该 p地址该访问类型的当月费用 总计 )，形成月计费文件。月计费文件经过出账处理形成流量费用账单文件。流量费用账单文件的记录格式为： 7 (1)请说明流程图中的文件 F0、 F1分别是哪个文件。 (2)处理 1和处理 5分别按照哪些数据项进行分类 ? 8 处理 4能发现哪些错误 (不需考虑设备故障错误 )? 9 说明处理 6的功能。 10 阅读以下说明，将应填入 (n)处的字句写在答卷纸的对应栏内。【说明】 下面的程序为堆排序
6、程序，其中函数 adjust(i,n)是把以 Ri(1i i/2 )为根的二叉树调整成堆的函数，假定 Ri的左 、右子树已经是堆，程序中的，是在主函数中说明的结构数组，它含有要排序的 n个记录。 【程序】 Void adjust(i， n) Int i， n； iht k,j; element extr; extr=ri; k=i; j=2*i; while (j =n ) if (j n) if (extr. key rj.key) rk=rj; k=j; (2); else (3); rk=extr; /*让 i从 i/2 逐步减到 1, 反复调用函数 adjust, 便完成建立初始堆的过
7、程。 */ void heapsort (r,n) list r; int n; int i,1; element extr; for (i=n/2;i =1;- -i) (4); /* 建立初始堆 */ for (k-n;k =2;k- -) extr=r1; r1=rk; rk=extr; (5); 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 9答案与解析 一、必答题（共 4道大题，每道大 题 15分） 1 【正确答案】 0层中的 “采购清单 ”不必画出。 2 【正确答案】 0层图中遗漏了 1加工的 “提货单 ”数据流。 加工 1子图中遗漏了 “配件库存 ”文件到 1.3加
8、工的数据流。 加工 1子图中 1.1加工遗漏了 “不合格订货单 ”输出数据流。 加工 1子图中 1.4加工遗漏了 “提货单 ”输出数据流。 加工 1子图中 1.5加工遗漏了 “到货通知 ”输入数据流。 加工 2子图中 2.4加工遗漏了 “送货通知 ”输出数据流。 【试题解析】 流程图试题的解答较其他类型的试题要直观一些，但要求考生必须特别仔细，白密一疏也会导致严 重的失分。 首先阅读试题说明，明确供销系统的基本结构。基本结构如顶层图所示，供销系统与顾客、供应商和总经理之间交换数据。供销系统接受顾客的定货单，反馈不合法的定货单，并在适当的时机向顾客发出提货单；供销系统向供应商发出采购单，接受送货
9、单，并反馈不合法的送货单；在以上购销操作的基础上，该系统接受并返回总经理的销售及库存情况表。 问题 1要求指出哪张图中的哪些文件是不必画出的。这是一个难度较高的要求。首先， 它要求仔细研究每一张图，确认每张图中每个文件是不必须画出：其次所谓不必画出，其含义是该文件画出 也不会导致该流程图发生错误，但不画出该文件将使整个流程图的层次结构更科学、更清晰。一般来说，如果一个元素 (如数据流等 )只用于一个加工，那么它就不必在其上层流程图中画出。但试题说明中只假定了顶层图的正确性，对于其他流程图，我们首先要确定它们是否完整、是否正确。 对照试题说明，顶层图简单明了，甚至没有涉及文件，因此我们可以跳过顶
10、层图不予考虑，直接研究 0层图。 0层图中涉及到 3个文件，即配件库存、缺货订单和采购清单。这里缺货订单和配件库存都在销售和采购两个加上中使用，只有采购清单只用于采购加工的似乎应该判断采 购清单是不必画的，但由于试题不保证顶层图以外各加工子图的正确性，难道就此确定在 0层图采购清单文件不必画出吗 ?不，在各个加工子图中，有可能发生文件、数据流、加工的遗漏或错画，影响我们在此处的判断。因此，只有通过仔细研究以上 3个文件在各个加工子图中应用才能验证我们的判断。 首先看配件库存文件。在加工 1子图中，配件库存文件经过加工 1.4更新库存而修改，然后还要为加工 1.1和加工 1.2提供数据支持。在加
11、工 1.1中，通过检查订货单订购的配件在配件库存中是否有记录来确定该配件是否属于经销范围，然后以此来确定订货单 是否合法。其次，还要在加工 1.2中根据比较合法订货单的数量与库存数量，以此确定是否需要发出采购请求。再提交，在发出提货单后，如果库存量低于允许的最低库存量，也要发出采购清单。可以看出，在该加工图中，未发现对配件库存文件的不适当的使用。在加工 2子图中，在加工 2.4核对送货单后要更新库存文件，然后加工 2.3计算增量提供数据支持，计算出需要采购配件的数量。应该说这里对配件库存文件的使用是正确的。因此，我们可以确定配件库存文件在加工 1和加工 2中都有应用，画在 0层图中是合适的。
12、缺货订单文件在试题说明中没有提到 ，具体的应用需要应从阅读中体会。 0层图中显示该文件被加工 1和加工 2使用，且在两个加工中也都有所有应用。现在的作务就是确定两个加工中对该文件的使用是正确的。在加工 1中缺货订单的数据来自加工 1.2和加工 1.4，在加工 1.2中，接受合法的订货单后，如果订货单上数量大于配件库存文件的数量，将产生缺货订单文件。在加工 1.4中，在有货订单送达后，需要文出提货单，然后更新库存。如果库存量低于允许的最低库存量，应该将缺货信息反映到缺货订单中。在加工 2中，缺货订单为加工 2.3提供部分数据支技， 在计算配件增量以明确需要增加的配件的清单时，需要参照缺货订单。结
13、合以上对使用缺化订单文件的分析，可以认为该文件在加工 1和加工 2中的应用都是正确的。因此将该文件画在 0层图中是有必要的。 再来看采购清单。 0层图显示该文件只应用于加上 2。采购清单如果就应用在加工 1中，最有可能的地方是加工 1.2及其后的采购请求数据流，但在这里采购清单是有必要的吗 ?从加工 2中可以看出，采购清单是按供应商对采购单进行汇总来产生的，对采购单进行汇总，显然已经属于加工 2的工作，不应在加工 1中予以反映。由此可以断定，在加工 1中不应该有 采购清单文件。所以在 0层图中画采购清单是不合适的。 以上考察了 0层图、加工 1子图和加工 2子图中缺货订单、配件库存及采购清单的
14、使用，下面研究加工 1中的销售历史文件。如果没有该文件支持，加工 1.3是无法制作销售及库存情况表的：而且该文件由加工 1.4更新库存产生，其输入数据流和输出数据流均在加工 1中，在加工 1中使用该文件是合适的。问题 2要求指出哪些图中遗漏了哪些元素。一般来说，这类题目的解答首先要考虑各层次图的数据平衡，其次要考虑加工的输入数据流和输出数据流要平衡，即保证加工的输出数据流都有其对应的输入的数 据流。所谓数据平衡，就是在多层次数据流程图中，父图和子图的数据流必须保持一致。比如说，在父图中某加工有 2个输入数据流和 1个输出数据流，那么在该加工的子图中的输入 /输出数据流必须在数目上和内容上与父图
15、保持一致。 3 【正确答案】 此程序是一个排序程序。它将数组 a中的数值进行从小到大的排序。 4 【正确答案】 输出的其实就是排序的前三趟中间结果。 第 1趟： 8,2,10,7,15,4,13 第 2趟： 2,7,8,4,10,13,15 第 3趟： 2,4,7,8,10,13,15 【试题解析】 此排序方法称 为奇偶交换排序。 排序过程为：第 1趟对所有的奇数 i，将 Ri与 Ri+1进行比较，若 RiRi+1)，则将两者交换；第 2趟对所有偶数 i，将 Ri与 Ri+1进行比较，若 Ri Ri+1，则将两者交换：以后重复上述两趟过程，以此类推直到整个序列有序为止。只要看懂了程序流程图两个
16、问题都比较容易回答。 5 【正确答案】 客户： (客户号，客户名，地址，电话 ) 订单： (订单号，客户号，产品号，订货数，订货日期，交货日期，金额 ) 应收账款： (客户号，订单号，发票号，应收金额，支付日期，支付 金额，当前余额 ) 产品描述： (产品号，产品名，单价，重量 ) 折扣规则： (产品号，订货量，折扣 ) 6 【正确答案】 将数据表：订单： (订单号，客户号，产品号，订货数，订货日期，交货日期，金额 ) 拆分为： 订单： (订单号，客户号，订货项数 (可有可无 )，订货日期，交货日期 ) 订单细则： (订单号，产品号，订货数，金额 ) 【试题解析】 这一题主要考查考生对数据表的
17、结构的设计能力。这一步在 MIS系统的开发中是至关重要的一步，因为数据表的结构是否合理直接影响到整个系统的性能。 原题中的订单表，不符合第二范 式，因为其中含有部分依赖关系 (订单号，产品号 )-订货日期， (订单号，产品号 )-，交货日期， (由于一张订单有可能订了多种产品，但因为是同一订单所以这几种产品的订货日期，交货日期只要订单号就可以确定了 )。 7 【正确答案】 F0是网络访问业务档案， F1是网络访问用户档案。 (2)处理 1： IP地址。 处理 5：用户编码。 8 【正确答案】 处理 4可能发现的错误有： (1)根据月计费文件中的 IP地址，在业务档案中找不到相应的用户编码。 (
18、2)在月计费文件中，某 地址有国内流量的费用，但在业务档案中 ，国内流量许可标志却不许可。 (3)在月计费文件中，某 p地址有国际流量的费用，但在业务档案中，国际流量许可标志却不许可。 9 【正确答案】 处理 6的功能是对流量账单文件中的每个记录，根据用户编码查询用户档案，找到相应的用户名和用户地址，形成缴费通知单。 【试题解析】 本题给出的流程图是网络流量计费管理的处理流程，用来生成缴费通知单。 系统的数据源是记录在管理中心的服务器上的原始计费数据，这些数据在处理之前需要先进行分类，以提高系统的效率。原始计费数据记录的是每次网络访问流量的数据，缴费通知单 是针对每个用户的，因此在处理 1中应
19、该按照 P地址进行分类。 F0是在处理 4(出账 )中用未生成流量账单文件所要用到的 “网络访问业务档案 ”。由试题的说明可知，月计费文件中含有各种类型的费用，所以处理 4(出账 )的功能是将网络访问费用从月计费文件中分离出来，并进行数据的验证。根据以上分析得知 P0应该是网络访问业务档案。 F1是在处理 6中生成缴费通知单所要用到的 “用户档案 ”。因为用户编码是用户在系统中的惟一标识，所以应该先将账单文件按照用户编码分类，再根据 P1用户档案，得到用户名和用户地址，产生缴费通知单。 因此 P1应该是网络访问用户档案。 10 【正确答案】 (1)j+ (2)j*=2或 j=k*2 (3)j=
20、n+1或 break (4)adjust(i,n) (5)adjust(1,k-1) 【试题解析】 函数 adjust(i,n)是把以 Ri(1i i/2 )为根的二叉树调整成堆的函数，假定 Ri的左、右子树已经是堆，程序中的 r是在主函数中说明的结构数组，它含有要排序的 n个记录。 Void adjust(i,n) Int i,n； int k,j; element extr; extr=ri; k=i; j=2*i; while(j =n) if(j n) if(extr.key rj.key) rk=rj; k=j; j*=2; else j=n+1; rk=extr; /* 让 i从
21、i/2 逐步减到 1, 反复调用函数 adjust, 便完成建立初始堆的过程。堆排序程序 heapsort 如下 */ void heapsort(r,n) list r; int n; int i,l; element extr; for (i=n/2;i = 1 ;-i) adjust(i,n); /*建立初始堆 */ for(k=n;k =2;k-) extr=r1; r1=rk; rk=extr; adjust(1,k-1); 函数 heapsoff的第一个 for循环建立初始化。没待排序的 n个记录组成 棵深度为 h的完全二叉树，因此有 2h-1 n2h+1-1，即 2hn 2h+1
22、。完全二叉树的第 i层 (设根结点的层次为 0)上最多有 2i个结点， 对每个非叶结点，都要调用过程adjust，同时可能移动结点 (向下移动 )，第 i层上的结点可能要移动的最大距离为h-i，若设向下移动一层花费的时间为 c，则第 i层 2i个结点调整的时间最多为c*(h-i)*2i建立初始堆的全部时间应是： 令 j=h-1，则 i=h-j，所以有： 对第二个 for循环，调用 adjust函数 n-1次，每次总是由根向下调整，调整的最大距离为 log2n(实际上，调整的距离是逐渐变小的 )，所以总的时间不多于 c*(n-1)log2n O(log2n)堆排序总的时间为： O(n)+O(nlog2n)=O(max(n,n log2n)=O(n log2n) 算法需要的存储空间是存储 n个记录的数组以及少量暂存单元。 堆排序算法是不稳定的。
