1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 45及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和数据流图，回答问题 1至问题 3， 说明 考务处理系统具有如下功能： (1)对考生送来的报名单进行检查。 (2)对合格的报名单编好准考证号后将准考证送给考生，并将汇总后的考生名单送给阅卷。 (3)对阅卷站送来的成绩清单进行检查，并根据考试中心制订的合格标准审定合格者。 (4)制作考生通知单送给考生。 (5) 进行成绩分类统计 (按地区、年龄、文化程度、职业、考试级别等分类 )和试题难度分析，产生统计分析表。 以下是经分析得到的数据流图及部分数据字典，有些
2、地方有待填充，假定顶层数据流图是正确的。图 1-1是顶层数据流图，图1-2是第 0层数据流图，图 1-3是第 l层数据流图，其中 (A)是加工 1的子图， (B)是加工 2的子图。 图 1-1 图 1-2 图 1-3 数据字典 报名单 =地区 +序号 +姓名 +性别 +年龄 +文化程度 +职业 +考试级别 +通信地址 正式报名单 =报名单 +准考证号 准考证 =地区 +序号 +姓名 +准考证号 +考试级别 考生名单 =准考证号 +考试级别 统计分析表 =分类统 计表 +难度分析表 考生通知单 =考试级别 +准考证号 +姓名 +合格标志 +通信地址 1 根据题意，指出 0层数据流图 (图 1-2
3、)中缺失的数据流的名称，并指出该数据流的起点和终点。 2 根据题意，指出加工 1子图 (图 1-3A)中缺失的数据流的名称，并指出该数据流的起点和终点。 3 根据题意，指出加工 2子图 (图 1-3B)中缺失的数据流的名称，并指出该数据流的起点和终点。加工 2子图 (图 1-4)中有一条数据流是错误的，请指出这条数据流的起点和终点。 3 阅读下列说明和 E-R图，回答问题 1至问题 4， 说明 图 2-1是某医院组织的结构图。该医院分为多个病区，每个病区有一个唯一的编号，一个病区包括多个病房，多名医生：每位医生有一个唯一的编号，负责管辖其主治病人的所有病房；病人住院后给以一个唯一的编号，根据
4、“患何病科 ”住在相应病区的某个病房里，有且仅有一位医生担任主治医生，除主治医生外其他医生不对其负责。 现假定病区名称有 “内科 ”和 “外科 ”， “内科 ”病区又细分为多个病区，以编号区分，名称都为 “内科 ”； “外科 ”病区亦然。图 2-2是经分析得到的 E-R图。 图 2-1 图 2-2 4 实体间的联系有 “一对一 ”、 “一对多 ”和 “多对多 ”，指出图 2-2中各联系分别属于哪一种。 5 选出正确的关系代数表达式。 查询所有 “外科 ”病区和 “内科 ”病区的所有医生姓名； A Name=“外科 “ Name=“内科 “(4(Q) B Name=“外科 “ Name=“内科
5、“(4(Q) C 4(Name=“外科“ Name=“内科 “(Q) D 4(Name=“外科 “ Name=“内科 “(Q) 6 查询内科病区患胃病的病人的姓名。 A Name=“内科 “ SC=“胃病 “(2(R) B Name=“内科“ SC=“胃病 “(2(R) C 2(Name=“内科 “ SC=“胃病 “(R) D 2(Name=“内科 “ SC=“胃病 “(R) 7 层次模型不能直接表示多对多联系，为什么 ?可采用哪些方法进行多对多联系的表示。 7 阅读下列说明和图，回答问题 1至问题 2， 说明 移动电话是传统固定式电话的延伸，通过无线电网络可以与千里之外的朋友沟通而不受电话线
6、的束缚。现在的移动电话功能更全面，除了作为电话使用外，还可以发送短信，可以管理电话簿，可以下载铃声、图案。 手机由键盘、显示屏以及移动通信设 备组成，移动通信设备负责发送和接收信号，与基站进行连线。打电话的流程如下： (1) 用户拨电话号码，每按下一个数字键显示屏上显示相应数字； (2) 按 OK键进行连线，显示屏上显示 “连线中 ” ，请求连接基站，基站通过移动电话网络连接到对方手机，若有误则返回相关信息； (3) 接通后，显示屏显示 “连线成功 ”； (4) 打电话结束后，按Cancel送出断线信号，通知移动电话基站断线，基站切断连接，显示屏显示 “断线成功 ”。 该系统采用面向对象方法开
7、发，系统中的类以及类之间的关系用 UML类图表示，图 3-1是该系统的用 例图，图 3-2是该系统的类图，图 3-3描述了打电话(包括断开 )的序列图。 图 3-1 图 3-2 图 3-3 8 根据题意，用题中及类图中提供的术语指出图 3-1中的参与者 A及用例 B、 C各是什么。 9 根据题意，用题中及类图中提供的术语指出图 3-3所示的打电话序列图中的消息(A) (D)。 9 阅读下列说明和图表，回答问题 1到问题 3。 说明 在多道程序系统中，各个程序之间是并发执行的，共享系统资源。 CPU需要在各个运行的程序之间来回地切换，这样的话，要想描述这些 多道的并发活动过程就变得很困难。为此，
8、操作系统设计者提出了进程的概念。 进程是具有独立功能的程序关于某个数据集合上的一次动态执行过程，是系统进行资源分配和调度的独立单位。 10 进程在生命消亡前处于且仅处于三种基本状态之一。运行态 (Running)：进程占有 CPU，并在 CPU上运行。就绪态 (Ready)：一个进程已经具备运行条件，但由于无 CPU暂时不能运行的状态 (当调度给其 CPU时，立即可以运行 )。等待态(Blocked)：指进程因等待某种事件的发生而暂时不能运行的状态，即使 CPU空闲，该进程也 不可运行。指出如下进程状态转换图 (图 4-1)中 “状态 1” “状态 3”分别是什么状态。 图 4-1 11 如果
9、单 CPU系统中有 N个进程，运行的进程最多几个，最少几个；就绪进程最多几个，最少几个：等待进程最多几个，最少几个 ? 12 进程调度算法解决以何种次序对各就绪进程进行处理机的分配以及按何种时间比例让进程占用处理机。 常见的的调度算法有：先进先出 FIFO(按照进程进入就绪队列的的先后次序选择 )、时间片轮转 RR(进程轮流运行一个时间片 )、最高优先级 HPF(分配给具有最高优先级的就绪进程 )。 在实际系 统中，调度模式往往是几种调度算法的结合。某系统按优先级别设置若干个就绪队列，对级别较高的队列分配较小的时间片 Si(i=1， 2， ， n)，即有 S1 S2 n 。除第 n级队列是按
10、RR法调度之外，其他各级队列均按 FIFO调度。系统总是先调度级别较高的队列中的进程，仅当该队列为空时才去调度下一级队列中的进程。当执行进程用完其时间片时便被剥夺并进入下一级就绪队列。当等待进程被唤醒时，它进入其优先级相应的就绪队列，若其优先级高于执行进程，便抢占 CPU执行进程。 现有五个进程 P1、P2、 P3、 P4、 P5，它们同时依次进入 就绪队列，它们所需的 CPU时间和优先级如图 4-2所示。注意，优先数越大优先级越低。 图 4-2 在该系统中，假定不同级别的时间片为 S1=2i-1(i为优先数 )，请给出五个进程的 CPU占用序列，并注明每次占用所用的时间。 二、选答题（共 3
11、道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 12 阅读下列函数说明和 C代码，将应填入 (n)外的字句写在对应栏内。 说明 为网球比赛的选手安排比赛日程。设有 n(n=2m)位选手参加网球循环赛，循环赛 共进行n-1天，每位选手要与其他 n-1位选手赛一场，且每位选手每天赛一场，不轮空。 设 n位选手被顺序编号为 1， 2， ， n，比赛的日程表是一个 n行 n-1列的表，第 i行 j列的内容是第 i号选手第 j天的比赛对手。用分治法设计日程表，就是从其中一半选手 (2m-1位 )的比赛日程导出全体 2m选手的比赛日
12、程。从众所周知的只有两位选手的比赛日程出发，反复这个过程，直至为 n位选手安排好比赛日程为止。 如两位选手比赛日程表如下所示： 如四位选手比赛日程表如下所示：函数中使用的预定义符号如下： #define M 64 int aM+1M; 函数 voidd main() int twoml,twom,i,j,m,k; printf(“指定 n(=2的 k次幂 )位选手，请输入k： n“); scanf(“%d“, k); /*8预设两位选手的比赛日程 */ a11 =2; a21 =1; m=1; twoml=1; while ( (1) ) m+; twoml+=twoml; twom=twom
13、l*2;/*为 2m位选手安排比赛日程 */ /*填日程表的左下角 */ for(i=twoml+1; (2) ;i+) for(j=1; j 13 (1) 14 (2) 15 (3) 16 (4) 17 (5) 17 阅读以下说明和 c+代码，将应填入 (n)处的字句写在答题纸对应栏内。 说明 很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下， Singleton模式有可能出现问题，需要进行同步检查。如果对 “检查 Singleton对象是否已经创建 ”进行同步，则存在严重的瓶颈，所有的线程都必须等待检查对象是 否存在。解决方式
14、是一种称为 Double-Checked-Locking模式，其意图是将非必须的锁定优化掉，同步检查最多只发生一次，因此不会成为瓶颈。以下是 c+语言实现，能够正确编译通过。 C+代码 class USTax (1): USTax();/构造函数 public: static USTax* getInstance(); private: static USTax*instance; ; (2)=NULL; USTax*USTax:get Instance() if(instance=NULL) /进行某种同步 cout“实例暂时不存在 “ if( (3) ) cout“实例不存在，创建实例 .
15、“ instance=(4); cout“实例创建成功 “ else cout“实例已被创建了 “ else cout“实例已经存在 “ return (5); 18 (1) 19 (2) 20 (3) 21 (4) 22 (5) 22 阅读以下函数说明和 Java代码，将应填入 (n)处的字句写在对应栏内。 说明 很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下， Singleton模式有可能出现问题，需要进行同步检查。如果对 “检查 singleton对象是否已经创建 ”进行同步，则存在严重的瓶颈，所有的线程都必 须等待检查对
16、象是否存在。解决方式是一种称为 Double-Checked-Locking模式，其意图是将非必须的锁定优化掉，同步检查最多只发生一次，因此不会成为瓶颈。以下是 Java语言实现，能够正确编译通过。 Java代码 public class USTax private static USTax instance=null; (1) USTax() private (2) static void doSync() if(instance=null) System.out.println(“实例不存在，创建实例 “); instance=(3); System.out.println(“实例创建成功
17、 “); else System.out.println(“实例已被创建了 “); public static USTax getInstance() if(instance=null) System.out.println(“实例暂时不存在 “); (4);/同步控制 else System.out.println(“实例已经存在 “); return (5); 23 (1) 24 (2) 25 (3) 26 (4) 27 (5) 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 45答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 成绩清单，起点：阅卷站
18、，终点：统计成绩 【试题解析】 对于分层数据流图，一定要注意平衡原则，即父图与子图数据流一致。 仔细与顶层数据流图比对，可发现缺失了数据流 “成绩清单 ”，其起点应为 “阅卷站 ”，终点为加工 2“统计成绩 ”。 2 【正确答案】 报名单，起点：考生，终点：检查报名单 【试题解析】 方法同问题 1。可得加工 1子图 (图 1-3A)中缺失了数据流 “报名单 ”，其起点自然是 “考生 ”，终点应为加工 1.1“检查报名单 ”。 3 【正确答案】 合格标准，起点：考试中心，终点：审定合格者 ,起点：制作通知单，终点：考生名册 【试题解析】 方法同问题 1。可得加工 2子图 (图 1-3B)中缺失了
19、数据流 “合格标准 ”，其起点为 “考试中心 ”，终点为加工 2.2“审定合格者 ”。 错误数据流多半是表现在文件读出 /写入上。加工 2.3“制作通知单 ”是从 “考生名册 ”处获得考生信息，而不是写入，因此该数据流是错误的。 4 【正确答案】 QR：一对多， QS：一对多， RS：一对多 【试题解析】 关系模型中实体间的联系有：一对一、一对多和多对多。一对一是指一个实体只与另一个实体相联系，一对多是指一个实体与多个实体相联系，多对多是指多个实体与 多个实体间的联系。 在这个系统中，一个病人只在一个病区，一个病区有多个病人，因此联系 QR是一对多联系；一个病人只有一个主治医生，一个医生显然可
20、以医治多名病人，因此联系 QS是一对多联系；一名医生只属于一个病区，一个病区有多名医生，故联系 QS是一对多联系。 5 【正确答案】 C 6 【正确答案】 D 【试题解析】 基本的关系代数包括并、差、广义笛卡儿积、投影、选择，其他运算可以通过基本的关系运算导出。 关系 R与 s具有相同的关系模式，即 R与 S的结构相同，关系 R与 S的并由属于 R或属于 S的元组构成的 集合组成，记做R S，其形式定义如下： R S=t|t R t S，式中 t为元组变量。 . 并(Union)。关系 R与 S具有相同的关系模式，即 R与 S的结构相同，关系 R与 s的并由属于 R或属于 S的元组构成的集合组
21、成，记做 R S，其形式定义如下：R S=t|t R t S，式中 t为元组变量。 . 差 (Difference)。关系 R与 s具有相同的关系模式，关系 R与 S的差由属于 R但不属于 S的元组构成的集合组成，记做R-S，其形式定义如下： 。 . 广义笛卡儿积 (Extended CartesianProduct)。两个元组分别为 n目和 m目的关系 R和 S的笛卡儿积是一个n+m列的元组的集合，元组的前 n列是关系 R的一个元组，后 m列是关系 S的一个元组，记做 RS，其形式定义如下： RS=t|t= tn， tm tn R tm S。如果 R和 S中有相同的属性名，那么可在属性名前加
22、关系名作为限定，以示区别。若 R有 k1个元组， S有 k2个元组，则 R和 S的广义笛卡儿积有 k1k2个元组。 . 投影 (Projection)。投影运算是从关系垂直方向进行运算的，在关系 R中选择出若干属性列 A组成新的关系，记做 A(R)，其形式定义如下 ： A(R)=tA|t R。 . 选择 (Selection)。选择运算是从关系的水平方向进行运算的，从关系 R中选择满足给定条件的诸元组，记做 F(R)，其形式定义如下： F(R)=t|t R F(t)=True)。其中， F中的运算对象是属性名 (或列的序号 )或常数。运算符是算术比较符 (， ， =， )和逻辑运算符 ( ，
23、， )。 在此主要涉及投影和选择，根据语义， (1)中 “外科 ”与 “内科 ”应为或关系，且应先选择再投影，因为作投影运算之后，选择操作涉及的列已经不在了，故为 C； (2)中 “内科 ”和 “胃病 ”应为与关系，同样应该先选择再投影，故为 D。 7 【正确答案】 层次模型采用树型结构表示数据与数据间的联系。在层次模型中，每一个节点表示记录类型 (实体 )，记录之间的联系用节点之间的连线表示，并且根节点以外的其他节点有且仅有一个双亲节点。层次模型不能直接表示多对多联系，若要表示多对多的联系，可采用如下两种方法： . 冗余节点法 两个实体的多对多的联系转换为两个一对多的联系，该方法的优点是节点
24、清晰，允许节点改变存储位置，缺点是需要额外的存储空间，有潜在的数据不一致性。 . 虚拟节点 分解法 将冗余节点转换为虚拟节点，虚拟节点是一个指引元，指向所代替的节点，该方法的优点是减少对存储空间的浪费，避免数据不一致性，缺点是改变存储位置可能引起虚拟节点中指针的修改。 8 【正确答案】 A： “客户 ” B： “发短信 ” C： “管理电话簿 ” 【试题解析】 图 1-1给出了系统用例图，用例图 (use case diagram)展现了一组用例、参与者 (actor)以及它们之间的关系。 从说明易知参与者 A是 “用户 ”。 仔细分析，缺少的用例为 “发短信 ”和 “管理电话簿 ”，而 “发
25、短信 ”与 “无线电网络 ”相关，故用例 B为 “发短信 ”，用例 C为 “管理电话簿 ”。 9 【正确答案】 (A)“按数字键 ”(B)“连接基站 ”(C)“按断线键 ”(D)“断开连接 ” 【试题解析】 根据题意，打电话的流程如下： 用户拨电话号码，每按下一个数字键，显示屏上显示相应数字； 按 OK键进行连线，显示屏上显示 “连线中 ” ，请求连接基站，基站通过移动电话网络连接到对方于机，若有误则返回相关信息； 接通后，显示屏显示 “连线成功 ”； 打电话结束后，按 Cancel送出断线信 号，通知移动电话基站断线，基站切断连接，显示屏显示 “断线成功 ”。 对比可得， (A)为 “按数字
26、键 ”， (B)为 “连接基站 ”， (C)为 “按断线键 ”， (D)为“断开连接 ”。 10 【正确答案】 状态 1：运行态，状态 2：就绪态，状态 3：等待态。 【试题解析】 根据问题 1中对进程 3种状态的描述，易于判断状态 1：运行态，状态 2：就绪态，状态 3：等待态。 11 【正确答案】 运行进程最多 1个，最少 0个；就绪进程最多 N-1个，最少 0个；等待进程最多 N个，最少 0个。 【试题解析】 问题 1给出了三种状态的具体表现形式。对于单 CPU系统，运行的进程最多只有 1个，最少可以是 0个 (当所有进程都处于阻塞态时 )。就绪进程最多只可能有 N-1个，因为有就绪进程
27、的话，肯定有运行进程，最少 0个。等待进程最多可有 N个，最少可为 0个 (1个运行， N-1个就绪 )。 12 【正确答案】 P2(1)、 P5(2)、 P1(4)、 P3(2)、 P5(3)、 P4(1)、 P1(6)。括号内数字表示该进程还需的执行时间。 【试题解析】 根据题意，开始调度前，各个级别队列为： . 优先数 1： P2(1)，时间片 为 1单位； . 优先数 2： P5(5)，时间片为 2单位； . 优先数 3： P1(10)、 P3(2)，时间片为 4单位； . 优先数 4： P4(1)，时间片为 8单位。 根据调度策略 “系统总是先调度级别较高的队列中的进程，仅当该队列为
28、空时才去调度下一级队列中的进程；当执行进程用完其时间片时便被剥夺并进入下一级就绪队列 ”，系统先调度 P2进程，执行 1单位时间，时间片到， P2亦执行完毕，各个级别队列为： . 优先数 1：时间片为 1单位； . 优先数 2： P5(5)，时间片为 2单位； . 优先数 3： Pl(10)、 P3(2)，时间片为 4单位； . 优先数 4： P4(1)，时间片为 8单位。 系统调度 P5进程，执行 2单位时间，进程 P5还需 3单位时间，进入优先数 3队列，各个级别队列为： . 优先数 1：时间片为 1单位； . 优先数 2：时间片为 2单位； . 优先数 3： P1(10)、 P3(2)、
29、 P5(3)，时间片为 4单位； . 优先数 4： P4(1)，时间片为 8单位。 系统调度 P1进程，执行 4单位时间，进程 P1还需 6单位时间，进入优先数 4队列；继续调度 P3进程，执行 2单位时间，进程 P3执行完毕；调度进程 P5，执行3单位时间，执行完毕，各个级别队列为： . 优先数 1：时间片为 1单位； . 优先数 2：时间片为 2单位； . 优先数 3：时间片为 4单位； . 优先数 4： P4(1)、 P1(6)，时间片为 8单位。 系统调度 P4进程，执行 l单位时问，进程 P4执行完毕；继续调度 P1进程，执行 6单位时间，进程 P1执行完毕。 至此，可得五个进程的
30、CPU占用序列以及其占用时间。 P2(1)、 P5(2)、 P1(4)、P3(2)、 P5(3)、 P4(1)、 P1(6)。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 13 【正确答案】 m k 【试题解析】 题中已经说明该算法采用的是分治法， “就是从其中一半选手 (2m-1位 )的比赛日程导出全体 2m选手的比赛日程 ”，再根据注释，不难确定空 (1)应填m k。 14 【正确答案】 i =twom 【试题解析】 以下各空的判断略有难度，可通过举例法，亦即模拟执行，来生成四位选手 (k为 2
31、)的比赛日程。 空 (2)应填当前问题规模中行下标的最大值，分析得当前规模行下标最大为twom，对应四位选手为 4，故空 (2)应填 i =twom。 15 【正确答案】 twoml+1 【试题解析】 空 (3)填的右上角第一行第一列元素，对应四位选手为 a12，此值为 3，即 twoml+1，故空 (3)应填 twoml+1。 16 【正确答案】 ai+1j-1 【试题解析】 比赛日程中， A与 B比赛，那么 B与 A比赛，其时间是统一的，存在参照性，注释已说明是前一列，故列号应为 j-1；至于 行号，通过分析四位选手比赛日程，可总结出应为 i+1。故空 (4)应填 ai+1j-1。 17
32、【正确答案】 aij 【试题解析】 同空 (4)，空 (5)应为 aij。 18 【正确答案】 privam 【试题解析】 在这里希望 USTax类只有一个实例，从而需要将其构造函数设置为 plivate，以防止外部对这个类进行直接实例化。故空 (1)应填 private。 19 【正确答案】 USTax*USTax:instance 【试题解析】 空 (2)是对类 USTax的静 态成员变量 instance的初始化，应填USTax*USTax： instance。 20 【正确答案】 instance=NULL 【试题解析】 在此是 Double-Checked-Locking模式，即双检
33、查锁定模式，因此此处应该再次检查。也可以想象多线程的执行情况，线程 A和线程 B同时调用getlnstance()方法。故空 (3)应填 instance=NULL。 21 【正确答案】 new USTax 【试题解析】 空 (4)是创建一个 USTax实例，应填 new USTax。 22 【正确答案】 instance 【试题解析】 空 (5)返回引用，应填 instance。 23 【正确答案】 private 【试题解析】 在这里希望 USTax类只有一个实例，从而需要将其构造函数设置为 private，以防止外部对这个类进行直接实例化。故空 (1)应填 private。 24 【正确答案】 synchronized 【试题解析】 方法 doSync是进行同步控制，因此应声明为 synchronized，即空(2)应填 synchronized。 25 【正确答案】 new USTax() 【试题解析】 空 (3)是创建一个 USTax实例，应填 new USTax()。 26 【正确答案】 doSync() 【试题解析】 空 (4)处要进行同步控制，故此处应调用同步函数 doSync()，故空 (4)应填 doSync()。 27 【正确答案】 instance 【试题解析】 空 (5)返回引用，应填 instance。
