1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 10及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读下列说明和有关的图表，回答问题 1至问题 3。 说明 A公司决定为该市车站开发自动售票系统，系统的要求如下： 1乘客能按以下三步操作购票：选定目的地；投入钱币；获得一张票。 2当且仅当乘客选定目的地后，系统才接收投钱，每次投入的钱只购买一张票。 3只要投入的钱不少于所需的票价，且票库中有所要求的票，则应尽快出票。 4如需找钱，则在出票的同时应退还多余的钱。 5如果乘客投 入的钱不够票价，或者票库中没有所要求的票时，系统将全额退钱，并允许乘客另选目的地，继续购票。
2、6出票前乘客可以按 “取消 ”按钮取消购票，系统将全额退出该乘客投入的钱，并允许乘客另选目的地，继续购票。 7出票结束 (包括退还多余的钱 )后，系统应保存销售记录，并等待乘客购票。 该系统还要求快速响应和操作同步，所以它应是一个实时系统。为此， A公司在该系统的数据流程图中附加了过程控制部分，形成转换图。在该图中，控制流 (事件流 )用虚线表示，数据流用实线表示。图中的数据流并没有画全，需要考生填补。转换图如图1所示。对 售票全过程进行的控制可以用系统内部各个状态之间的迁移来描述，从而形成状态迁移图。在状态迁移图中，用双线框表示状态，用有向边表示状态的迁移。引起状态迁移的事件以及由该事件引起
3、的动作，在有向边旁用 “”形式注明。状态迁移图如图 2所示。 该公司还制作了一个过程启动表，用以表明状态迁移图中的 4个动作与转换图中的 4个过程之间的 “启动 ”关系，即说明哪个动作将启动哪个过程。用1表示启动，用。表示不启动。启动的过程将根据获得的输人数据产生输出数据，未启动的过程则不会产生输出数据。该表中没有列出的过程，其执行与否与事件无关。过 程启动表见表 1：1 转换图中缺少哪三条数据流 ?请指明每条数据流的名称、起点和终点。 2 在状态迁移图中， a， b， c分别表示什么事件 ?请用转换图中给出的事件名解答。 3 在过程启动表中， d， e处应填什么 ?请分别用 4位二进制码表示
4、。 4 阅读下列说明、流程图和算法，将应填 (n)处的字句写在对应栏内。 说明 下面的流程图 (如图 3所示 )用 N - S盒图形式描述了数组 A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标 端移动。当划分结束时，基准数定位于 Ai，并且数组中下标小于 i的元素的值均小于基准数，下标大于 i的元素的值均大于基准数。设数组 A的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组 (4， 2， 8， 3， 6)，以 4为基准数的划分过程如下： 流程图 算法说明 将上述划分的思想进一步用于被划分出
5、的数组的两部分，就可以对整个数组实现递增排序。设函数 int p(int A， int low， int hieh)实现了上述流程图的划分过程并返回基准数在数组 A中的下标。递归函数 void sort(int A， int L， int H)的功能是实现数组 A中元素的递增排序。 算法 void sort(int A， int L， int H) if (L H) k=p(A， L， R)； /p()返回基准数在数组 A中的下标 sort(4)； /小于基准敷的元素排序 sort(5)； /大于基准数的元素排序 5 阅读下列说明，回答问题 1至问题 4。 说明 甲公司的经营销售业务目前是手工
6、处理的，随着业务量的增长，准备采用关系数据库对销售信息进行管理。经销业务的手工处理主要涉 及三种表：订单表、客户表和产品表 (见表 2，表 3和表 4)。为了用计算机管理销售信息，甲公司提出应达到以下要求：产品的单价发生变化时，应及时修改产品表中的单价数据。客户购货计价采用订货时的单价 ?订货后，即使单价发生变化，计算用的单价也不变。 在设计数据库时，经销部的王先生建立了如图 4所示的数据模型。其中，方框表示实体，单向箭头表示 1对多的联系，双向箭头表示多对多的联系。 由于上述模型对建立关系数据库是不合适的，因此王先生又修改了数据模型，并设计了如下几个关系 (带下划线的数据项是关键项，最后一个
7、关系中没有指 出关键项 )： Customer (CustomerNo， CustomerName, Address, Phone) Product (productNo, ProductName, UnitPdce) Order (Orderno, CustomerNo, Date) OrderDetail (OrderNo, ProductNo, Quantity) 5 请按 说明 中的要求画出修改后的数据模型。 6 (1)说明 中的几个关系仍无法实现甲公司的要求，为什么 ? (2)需要在哪个关系中增加什么数据 项才能实现这个要求 ? 7 写出 OrderDetail中的关键项。 8 以下
8、 SQL语句用于查询没有订购产品代码为 “1K10”的产品的所有客户名。请填补其中的空缺。 SELECT CustomerName FROM Customer(1) WHERE(2) (SELECT*FROM OrderDetail B, Order C WHERE B. ProductNo=C.ProductNo AND B. ProductNo=1K10 AND C. CustomerNo=A. CustomerNo) 9 阅读下列算法说明和算法，将应填入 (n)的字句写在对应的栏内。 说明 下列最短路径算法的具体流程如下：首先构造一个只含 n个顶点的森林，然后依权值从小到大从连通网中选择
9、不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1条互不构成回路的权值最小边为止。 算法 /*对图定义一种新的表示方法，以一维数组存 放图中所有边，并在构建图的存储结构时将它构造为一个 “有序表 ”。以顺序表 MSTree返回生成树上各条边。 */ typedef struct VertexType vex1;VertexType vex2; VRType weight; EdgeType; typedef ElemTyp
10、e EdgeType; typedef struct /有向网的定义 VertexType vexs MAX_VERTEX_N U M ; /顶点信息 EdgeType edge MAX_EDGE_NUM; /边的信息 int vexnum, arcnum; /图中顶点的数目和边的数目 I ELGraph; void MiniSpanTree_Kruskal( ELGraph G,SqList InitSet( F, G. vexnum ); /将森林 F初始化为 N棵树的集合 InitList (MSTree, G. vexnum); /初始化生成树为空树 i=0;k=1; while(k
11、(1) e = G. edgei; /取第 i条权值最小的边 /*函数fix_mfset返回边的顶点所在树的树的根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。 */ ri = fix_mfset(F, LocateVex(e. vex1) ); r2=(2); /返回两个顶点所在树的树根 if(r1 (3) r2) /选定生成树上第 k条边 if(Listlnsert(MSTree,k,e)(4); /插入生成树 mix_mfset( E, r1,r2); /将两棵树归并为一棵树 (5); /继续考察下一条权值最小边 DestroySet (F); 软件水平考试（中级）
12、软件设计师下午（应用技术）试题模拟试卷 10答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 数据流名：目的地；起点： “接收目的地 ”；终点： “核查 ”。 数据流名：投入的钱；起点 “接收钱 ”；终点： “核查 ”。 数据流名：剩余的钱；起点 “核查 ”；终点： “退还钱 ”。 【试题解析】 转换图是在数据流程图中附加了过程控制的部分，该图描述了自动售票系统的基本行为。根据说明中给出的系统需求描述和转换图，可以看出该图没有完整的描述系统的基本行为。由于乘客选择的目的地需要经过系统的验证，确定是否是合法的目的地，因此缺少的数据流起点为 “接收目的地 ”，终点为 “核
13、查 ”。转换图中只给出了将乘客投入的钱全额退还的数据流，没有给出在其他的情况下系统核查和退钱的数据流。因此缺少两条数据流：一条数据流的起点为 “接收钱 ”，终点为 “核查 ”；另一条数据流的起点为 “核查 ”，终点为 “退还钱 ”。 2 【正确答案】 a“取消 ”操作 b核查正确 c出票结束。 【试题解析】 结合试题考查状态迁移图，状态 “正在接收投钱 ”之后什么事件能够导致 “退钱 ”，同时还要注意到该事件之后状态转移到 “等待选择目的地 ”。显然，在接受投币之后如果正常发展的话应该是出票，出票的同时退还多余的钱。所以事件 a是发生在 “接收投钱 ”之后 “出票 ”之前发生的导致退钱的事件，
14、仔细考查试题说明，事件 a应该是 “取消 ”，因为在试题的说明部分特别提到 “出票钱乘客可以按，取消，按钮取消购票，系统将全额退出乘客投入的钱，并且乘客可以另选 ”“目 的地 ”。按照上面的分析，我们可以看到在 “接收投钱 ”之后，应该是在核查正确的事件发生之后才能够出票，因此事件 b就是 “核查正确 ”；而出票之后， “接收新的目的地 ”动作的执行应该是在 “出票结束 ”事件发生之后执行的动作，因此事件 c就是 “出票结束 ”。 3 【正确答案】 d1001 e1000 【试题解析】 由于过程启动表与状态迁移图是严格对应的，因此，填充过程启动表就应该从理解状态迁移图人手。结合试题说明、转换图
15、和状态迁移图，我们可以确定，在系统中，动作 “退钱 ”除了启动过程 “退钱 ”外，还需要启动过程 “接 收目的地 ”，因为 “退钱 ”之后应该等待乘客继续买票这样就必须启动过程 “接收目的地 ”；而动作 “接收新的目的地 ”启动的过程除了 “接收目的地 ”之外还应该有过程“接收钱 ”。这样，我们就要在 d处填写 “1001”，在 e处填写 “1000”。 4 【正确答案】 (1)j-(2)i+(3)Aipivot 或 jpivot(4) A ， L， k-1或 A， L， k (5)A， k+1， H或 A， k， H 【试题解析】 题目考查快速排序算法。快速排序采用了一种分治的策略，通常称为
16、分治法。其基本思想是：将原问题分解为若干个规 模更小，但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程为：第一步，在待排序的 n个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成 2组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这 2组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的 2组元素分别进行快速排序，直到所有记录都排到相应的位置为止。 在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量pivot中，如图中的第 步所示。这样基准元素在数
17、组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如图中的第 步所示，找到一个比基准元素小的元素时为止，将其前移，如图中的第 步所示。然后再从前向后扫描，如图中的第 步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第 步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第 步所示。 由题目中给出的流程图可知，以第一个元素作为基准数，并将 Alow备份至pivot， i用于从前向后扫描的位置指示器，其初值为 low, j用于从后往前扫描的位置指示器，其初值为 high。当 i 1)从后向前扫描数组 A，在 ipivot，就继续向前扫描 (j-)；如
18、果被扫描的元素 Ai 2)这时，再从前向后扫描，在 ipivot就停止扫描，并将此元素的值赋给目前空闲着的 Aj。 3)这时又接第 (1)步，直到 ij时退出循环。退出循环时，将 pivot赋给当前的Ai(Aipivot) 。 递归函数的目的是执行一系列调用，直到到达某一点时递归终止。为了保证递归函数正常执行，应该遵守下面的规则： 1)每当一个 递归函数被调用时，程序首先应该检查基本的条件是否满足，例如，某个参数的值等于 0，如果是这种情形，函数应停止递归。 2)每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得“更简单 ”，即这些参数应该逐渐靠近上述基本条件。例如，一个正整
19、数在每次递归调用时会逐渐变小，以至最终其值到达 0。 本题中，递归函数 sort(int A， int L, int H)有 3个参数，分别表示数组 A及其下界和上界。根据流程图可知，这里的 L相当于流程图中的 i，这里的 H相当于流程图中的 j。因为 P()返回基准 数所在数组 A中的下标，也就是流程图中最后的“Aipivot” 中的 i。根据快速排序算法，在第一趟排序后找出了基准数所在数组A中的下标，然后以该基准数为界 (基准数在数组中的下标为 k)，把数组 A分成 2组，分别是 AL,k -1)和 Ak+1,H) ，最后对这 2组中的元素再使用同样的方法进行快速排序。 5 【正确答案】
20、如图 1所示。【试题解析】 订单的情况不能作为订单的属性处理而应该上升为实体，同时由于Order与 Product是多对多的关系，所以应该拆分为一个名为 OrderDetail的关 系模式。其中， Order和 OrderDetail是一对多的关系， Produce和 OrderDetail是一对多的关系。 6 【正确答案】 因为只有 product记录了单价，一旦单价发生改变，用户订单地价格就会发生改变，因此，计算一张订单将采用新的单价，不符合要求。 (2)有两种方法：一是在 Order表中加入一项表示订单地产品总价，二是在 Order表中加入产品单价，这两种方法都能满足要求。 7 【正确答
21、案】 OrderNo， ProductNo 【试题解析】 在客户订商品中，一次订货下一个订单，一 个订单可以有多种商品，即对应多个 OrderDetail，也就是说，一个订单、一种商品确定一个OrderDetail，所以关键字是 (OrderNo, produetNo)。 8 【正确答案】 A或 AS(2)NOT EXIST 【试题解析】 在 SQL语句的最后一行中出现了字符 A，而其他地方没有给出字符 A的含义，所以第一个空只能填 A，表示 Customer表的简称。子查询的含义是“定购产品代码是 1K10产品的所有客户名 ”，那么根据题意空二应该是： NOT EXIST。 9 【正确答案】
22、 (1)G. vexnum(2)fix_mfset(F, LoeateVex(e. vex2) (3)!=(4)k+。 (5)i+ 【试题解析】 本题考查的是克鲁斯卡尔 (Kruskal)算法。理解该算法的关键在于：由于生成树上不允许有问路，因此并非每一条居当前权值最小的边都可选。例如，如图 2所示的连通网 G5，在依次选中了 (e, f)， (b, c)， (e, d)和 (f, s)的 4条边之后，权值最小边为 (s, d)，由于 g和 d已经连通，若加上 (s, d)这条边将使生成树上产生回路，显然这条边不可取。同理，边 (f, d)也不可取，之后则依次取 (a, s)和(a, b)两条边加入到生成树。 那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通 ?从生成树的构造过程可见，初始态为 n个顶点分属 n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
