1、中级软件设计师下午试题-111 及答案解析(总分：32.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)【说明】某音像制品出租商店欲开发一个音像管理信息系统，管理音像制品的租借业务。需求如下：1系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户，系统会为其生成用户名和初始密码。2系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。3根据客户所租借的音像制品的品种，会按天收取相应的费用。音像制品的最长租借周期为 1 周，每位客户每次最多只能租借 6 件音像制品。4客户租借某种音像制品的具体流程如下。(1)根据客户提供的用户
2、名和密码，验证客户身份。(2)若该客户是合法客户，查询音像制品信息文件，查看商店中是否还有这种音像制品。(3)若还有该音像制品，且客户所要租借的音像制品数小于等于 6 个，就可以将该音像制品租借给客户。这时，系统给出相应的租借确认信息，生成一条新的租借记录并将其保存在租借记录文件中。(4)系统计算租借费用，将费用信息保存在租借记录文件中并告知客户。(5)客户付清租借费用之后，系统接收客户付款信息，将音像制品租借给该客户。5当库存中某音像制品数量不能满足客户的租借请求数量时，系统可以接受客户网上预约租借某种音像制品。系统接收到预约请求后，检查库存信息，验证用户身份，创建相应的预约记录，生成预约流
3、水号给该客户，并将信息保存在预约记录文件中。6客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。（分数：15.00）(1).【问题 1】图(a)中只有一个外部实体 E1。使用【说明】中的词语，给出 E1 的名称。（分数：3.75）_(2).【问题 2】使用【说明】中的词语，给出图(b)中的数据存储 D1D4 的名称。（分数：3.75）_(3).【问题 3】数据流图(b)缺少了 3 条数据流，根据说明及数据流图(a)提供
4、的信息，分别指出这 3 条数据流的起点和终点。起点 终点（分数：3.75）_(4).【问题 4】在进行系统分析与设计时，面向数据结构的设计方法(如 Jackson 方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。（分数：3.75）_二、试题二(总题数：0，分数：0.00)三、试题三(总题数：1，分数：3.00)1.图中缺少了一条关联，请指出这条关联两端所对应的类以及每一端的多重度。类 多重度（分数：3.00）_四、试题四(总题数：1，分数：15.00)阅读下列说明和 C 代码，回答下列问题。说明用两台处理机 A 和 B 处理 n 个作业。设 A 和 B 处理第 i 个作
5、业的时间分别为 ai 和 bi。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上处理时间长，而对某些作业在 B 上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n 个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。(1)确定候选解上界为 R 短的单台处理机处理所有作业的完成时间 m， （分数：15.00）(1).问题 1根据以上说明和 C 代码，填充 C 代码中的空缺处。（分数：5.00）_(2).问题 2根据以上 C 代码，算法的时间复杂度为_(用 O 符号表示)。
6、（分数：5.00）_(3).问题 3考虑 6 个作业的实例，各个作业在两台处理机上的处理时间如表所示。该实例的最优解为_，最优解的值(即最短处理时间)为_。最优解用(x1，x2，x3，x4，x5，x6)表示，其中若第 i 个作业在 A 上处理，则 xi=1，否则 xi=2。如(1，1，1，1，2，2)表示作业 1、2、3 和 4 在 A 上处理，作业 5 和 6 在 B 上处理。各个作业在两台处理机上的处理时间作业 1作业 2作业 3作业 4作业 5作业 6处理机 A2 5 7 10 5 2处理机 B3 8 4 11 3 4（分数：5.00）_五、试题五(总题数：1，分数：-1.00)2.阅读
7、下列函数说明，将应填入 (n) 处的字句写在答卷纸的对应栏内。【函数 1 说明】函数 compare(SqList A，SqList B)的功能是：设 A=(al，am)和 B=(b1，bn)均为顺序表，“比较”两个顺序表 A 和 B 的大小。设 A和 B分别为 A 和 B 中除去最大共同前缀后的子表(例如，A(y，X,X,Z,X,Z)，B=(y，x，x，z，y，x，x，2)，则两者中最大的共同前缀为(y，x，x，2)，在两表中除去最大共同前缀后的子表分别为 A=(X,Z)和 B=(y，x，x，2)。若 A=B=空表，则 A=B：若 A=空表，而 B空表，或者两者均不为空表，且 A的首元小于
8、B，的首元，则 AB；否则 AB。提示：算法的基本思想为：若相等，则 j+1，之后继续比较后继元素：否则即可得山比较结果。显然，j的初值应为 0，循环的条件是 j 不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有 3 种可能出现的情况需要区分。【函数 1】int compare(SqList A，SqList B)/若 AB，则返回-1；若 A=B，则返回 o：若 AB，则返回 1j=0；while(j (1) else if( A.elemj B.elemj ) return(i);else (2) ff (A.length = B.length) return (0)
9、;else fi(A.length B.length ) return(-1);else return(1);/compare/函数 1 的时间复杂度是 (3) 【函数 2 说明】函数 exchange_L( SLink k = 1;while( k m +k;if( (6) / 以指针 ha 记 a1 结点的位置L-next = p-next; / 将 b1结点链接在头结点之后p-next = NULL; / 设 am的后继为空q: (7) ; / 令 q 指向 b1结点while(q-next)q= (8) ; / 查的 bn结点q-next = (9) ; / 将 a1 结点链接到 bn
10、 结点之后/函数 2 的时间复杂度是 (10) 。（分数：-1.00）_中级软件设计师下午试题-111 答案解析(总分：32.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)【说明】某音像制品出租商店欲开发一个音像管理信息系统，管理音像制品的租借业务。需求如下：1系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户，系统会为其生成用户名和初始密码。2系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。3根据客户所租借的音像制品的品种，会按天收取相应的费用。音像制品的最长租借周期为 1 周，每位客户每次最多只能租借 6 件音
11、像制品。4客户租借某种音像制品的具体流程如下。(1)根据客户提供的用户名和密码，验证客户身份。(2)若该客户是合法客户，查询音像制品信息文件，查看商店中是否还有这种音像制品。(3)若还有该音像制品，且客户所要租借的音像制品数小于等于 6 个，就可以将该音像制品租借给客户。这时，系统给出相应的租借确认信息，生成一条新的租借记录并将其保存在租借记录文件中。(4)系统计算租借费用，将费用信息保存在租借记录文件中并告知客户。(5)客户付清租借费用之后，系统接收客户付款信息，将音像制品租借给该客户。5当库存中某音像制品数量不能满足客户的租借请求数量时，系统可以接受客户网上预约租借某种音像制品。系统接收到
12、预约请求后，检查库存信息，验证用户身份，创建相应的预约记录，生成预约流水号给该客户，并将信息保存在预约记录文件中。6客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。（分数：15.00）(1).【问题 1】图(a)中只有一个外部实体 E1。使用【说明】中的词语，给出 E1 的名称。（分数：3.75）_正确答案：(E1：客户)解析：(2).【问题 2】使用【说明】中的词语，给出图(b)中的数据存储 D1D4 的名称。（分
13、数：3.75）_正确答案：(D1：客户信息文件 D2：音像制品信息文件D3：租借记录文件 D4：预约记录文件)解析：(3).【问题 3】数据流图(b)缺少了 3 条数据流，根据说明及数据流图(a)提供的信息，分别指出这 3 条数据流的起点和终点。起点 终点（分数：3.75）_正确答案：(起点 终点E1 或 客户 4 或 创建新客户5 或 创建预约记录 E1 或 客户6 或 归还音像制品7 或 履行预约服务注意：3 条数据流无前后顺序区分。)解析：(4).【问题 4】在进行系统分析与设计时，面向数据结构的设计方法(如 Jackson 方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其
14、适用场合。（分数：3.75）_正确答案：(面向数据结构的设计方法以数据结构作为设计的基础，它根据输入/输出数据结构导出程序的结构。面向数据结构的设计方法用于规模不大的数据处理系统。)解析：解析 本题考查数据流图的设计和应用。根据题目说明，本系统的外部实体仅仅涉及到客户，因此系统的顶层数据流图中 E1 应该对应为客户。题目的第二个问题在于识别系统中的数据文件 D1D4，根据 0 层数据流图中的数据文件与处理之间的关系分析可以得知：D1 为创建新客户加工的输出，并且为加工 1、6 和 7 的输入，再根据题目中的描述，客户信息文件与创建客户信息、预约、归还和履行预约都相关，因此 D1 便是客户信息文
15、件。同理可分析出 D2 为音像制品信息文件、D3 为租借记录文件、D4 为预约记录文件。图(b)中缺少了 3 条数据流，我们先检查顶层数据流图和。层数据流是否一致。首先，从顶层数据流图中可以看出，与 E1 直接相关的数据流共有 9 条，而在 0 层数据流图中与 E1 直接关联的只有 7 条，因此可以直接断定，图(b)中至少缺少直接与 E1 相关的两条数据流：新客户创建请求和预约流水号。新客户创建请求通过创建新客户加工将客户的信息写入客户信息文件中，因此其起点和终点分别为：E1 和 4。同理，预约流水号的起点和终点为 5 和 E1。在说明中，客户归还到期的音像制品，系统修改租借记录文件，并查询预
16、约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。因此，在客户归还和履行预约服务之间存在着数据上的联系。面向数据结构的设计方法以数据结构作为设计的基础，它根据输入/输出数据结构导出程序的结构。面向数据结构的设计方法用于规模不大的数据处理系统。二、试题二(总题数：0，分数：0.00)三、试题三(总题数：1，分数：3.00)1.图中缺少了一条关联，请指出这条关联两端所对应的类以及每一端的多重度。类 多重度（分数：3.00）_正确答案：(类 多重度Track 或 E (1 分)
17、 01 1 分) Track 或 E (1 分) 01 (1 分) )解析：四、试题四(总题数：1，分数：15.00)阅读下列说明和 C 代码，回答下列问题。说明用两台处理机 A 和 B 处理 n 个作业。设 A 和 B 处理第 i 个作业的时间分别为 ai 和 bi。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上处理时间长，而对某些作业在 B 上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n 个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。(1)确定候选解上界
18、为 R 短的单台处理机处理所有作业的完成时间 m， （分数：15.00）(1).问题 1根据以上说明和 C 代码，填充 C 代码中的空缺处。（分数：5.00）_正确答案：(pxy0=1pxyk=px-ak-1yk-1y-bk-1=0pxyn=1 或 pxyn!=0 或 pxyn或其他等价表示形式(x=y)?x:y)解析：(2).问题 2根据以上 C 代码，算法的时间复杂度为_(用 O 符号表示)。（分数：5.00）_正确答案：(O(m 2n)解析：结合问题 1 的分析结果，根据题干所给出的 C 代码，函数 schedule 有两处三重 for 循环，时间复杂度为 O(m2n)。函数 write
19、 有一处两重 for 循环，时间复杂度为 O(m2)。因此整个算法的时间复杂度为O(m2n+m2)。由于 m2在数量级上小于 m2n，因此整个算法的时间复杂度可以表示为 O(m2n)。(3).问题 3考虑 6 个作业的实例，各个作业在两台处理机上的处理时间如表所示。该实例的最优解为_，最优解的值(即最短处理时间)为_。最优解用(x1，x2，x3，x4，x5，x6)表示，其中若第 i 个作业在 A 上处理，则 xi=1，否则 xi=2。如(1，1，1，1，2，2)表示作业 1、2、3 和 4 在 A 上处理，作业 5 和 6 在 B 上处理。各个作业在两台处理机上的处理时间作业 1作业 2作业
20、3作业 4作业 5作业 6处理机 A2 5 7 10 5 2处理机 B3 8 4 11 3 4（分数：5.00）_正确答案：(1,1,2,2,1,1)15)解析：依题意和算法，可以得到若作业 1、2、5 和 6 在处理机 A 上处理，而作业 3 和 4 在处理机 B 上处理，可以得到最优解。此时在处理机 A 上的处理时间为 2+5+5+2=14，在处理机 B 上的处理时间为 4+11=15，因此最优解的值，即最短的处理时间为 15，最优解为(1,1,2,2,1,1)。五、试题五(总题数：1，分数：-1.00)2.阅读下列函数说明，将应填入 (n) 处的字句写在答卷纸的对应栏内。【函数 1 说明
21、】函数 compare(SqList A，SqList B)的功能是：设 A=(al，am)和 B=(b1，bn)均为顺序表，“比较”两个顺序表 A 和 B 的大小。设 A和 B分别为 A 和 B 中除去最大共同前缀后的子表(例如，A(y，X,X,Z,X,Z)，B=(y，x，x，z，y，x，x，2)，则两者中最大的共同前缀为(y，x，x，2)，在两表中除去最大共同前缀后的子表分别为 A=(X,Z)和 B=(y，x，x，2)。若 A=B=空表，则 A=B：若 A=空表，而 B空表，或者两者均不为空表，且 A的首元小于 B，的首元，则 AB；否则 AB。提示：算法的基本思想为：若相等，则 j+1，
22、之后继续比较后继元素：否则即可得山比较结果。显然，j的初值应为 0，循环的条件是 j 不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有 3 种可能出现的情况需要区分。【函数 1】int compare(SqList A，SqList B)/若 AB，则返回-1；若 A=B，则返回 o：若 AB，则返回 1j=0；while(j (1) else if( A.elemj B.elemj ) return(i);else (2) ff (A.length = B.length) return (0);else fi(A.length B.length ) return(-1)
23、;else return(1);/compare/函数 1 的时间复杂度是 (3) 【函数 2 说明】函数 exchange_L( SLink k = 1;while( k m +k;if( (6) / 以指针 ha 记 a1 结点的位置L-next = p-next; / 将 b1结点链接在头结点之后p-next = NULL; / 设 am的后继为空q: (7) ; / 令 q 指向 b1结点while(q-next)q= (8) ; / 查的 bn结点q-next = (9) ; / 将 a1 结点链接到 bn 结点之后/函数 2 的时间复杂度是 (10) 。（分数：-1.00）_正确答
24、案：(A.length(2)j+(3)O(Min(A.1ength，B.1ength)(4)m(5)p-next(6) p(7)L-next(8)q-next(9) ha(10)O(ListLength(L)解析：分析 函数 1 中，算法要求对两个顺序表进行“比较”，是一种“引用型”操作，因此在算法中不应该破坏己知表。按题目中的规定，只有在两个表的长度相等，且每个对应元素都相同时才相等；否则，两个顺序表的大小主要取决于两表中除去最大公共前缀后的第一个元素。因此，比较两表的大小不应该先比较它们的长度，而应该设一个下标变量 i 同时控制两个表，即对两表中“位序相同”的元素进行比较。上述算法中只有一个 while 循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法的时间复杂度为 O(Min(A.1enZ 出，B.length)。函数 2 中，对链表来说，“插入”和“删除”仅需修改指针即可完成，并且由于前 m 个元素之间和后 n 个元素之间的链接关系都不需要改变，则算法的实际操作为：先从链表中删除(a 1，a 2，a m)，然后将(b 1，b 2，b n)链接到头结点之后，再将(a 1，a 2，a m)链接到 bn之后。算法的时间复杂度为 O(L1stlen2 出(L)。
