1、(A)中级软件设计师下午试题-3 及答案解析(总分：106.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明考务处理系统具有如下功能：(1)对考生送来的报名单进行检查。(2)对合格的报名单编好准考证号后将准考证送给考生，并将汇总后的考生名单送给阅卷。(3)对阅卷站送来的成绩清单进行检查，并根据考试中心制订的合格标准审定合格者。(4)制作考生通知单送给考生。(5)进行成绩分类统计(按地区、年龄、文化程度、职业、考试级别等分类)和试题难度分析，产生统计分析表。以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定项层数据流图是正确的。图 1 是顶层数据流图，图
2、2 是第 0 层数据流图，图 3 是第 1 层数据流图，其中(A)是加工 1 的子图，(B)是加工 2的子图。图 1图 2（分数：15.00）(1).根据题意，指出 0 层数据流图(图 2)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：5.00）_(2).根据题意，指出加工 1 子图(图 3A)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：5.00）_(3).根据题意，指出加工 2 子图(图 3B)中缺失的数据流的名称，并指出该数据流的起点和终点。加工 2子图(图 3)中有一条数据流是错误的，请指出这条数据流的起点和终点。（分数：5.00）_二、试题二(总题数：1，分数
3、：16.00)说明图 1 是某医院组织的结构图。该医院分为多个病区，每个病区有一个唯一的编号，一个病区包括多个病房，多名医生；每位医生有一个唯一的编号，负责管辖其主治病人的所有病房；病人住院后给以一个唯一的编号，根据“患何病科”住在相应病区的某个病房里，有且仅有一位医生担任主治医生，除主治医生外其他医生不对其负责。现假定病区名称有“内科”和“外科”，“内科”病区又细分为多个病区，以编号区分，名称都为“内科”；“外科”病区亦然。图 2 是经分析得到的 E-R 图。图 1（分数：16.00）(1).实体间的联系有“一对一”、“一对多”和“多对多”，指出图 2 中各联系分别属于哪一种。（分数：4.0
4、0）_(2).选出正确的关系代数表达式。查询所有“外科”病区和“内科”病区的所有医生姓名：A Name=“外科“Name=“内科“ ( 4Q) B Name=“外科“Name=“内科“ ( 4(Q)C 4( Name=“外科“Name=“内科“ (Q) D 4( Name=“外科“Name=“内科“ (Q)（分数：4.00）A.B.C.D.(3).查询内科病区患胃病的病人的姓名。A Name=“外科“SC=“胃病“ ( 2(R) B Name=“内科“SC=“胃病“ ( 2(R)C 2( Name=“外科“SC=“胃病“ (R) D 2( Name=“内科“SC=“胃病“ (R)（分数：4.0
5、0）A.B.C.D.(4).层次模型不能直接表示多对多联系，为什么?可采用哪些方法进行多对多联系的表示。（分数：4.00）_三、试题三(总题数：1，分数：15.00)说明移动电话是传统固定式电话的延伸，通过无线电网络可以与千里之外的朋友沟通而不受电话线的束缚。现在的移动电话功能更全面，除了作为电话使用外，还可以发送短信，可以管理电话簿，可以下载铃声、图案。手机由键盘、显示屏以及移动通信设备组成，移动通信设备负责发送和接收信号，与基站进行连线。打电话的流程如下：(1)用户拨电话号码，每按下一个数字键显示屏上显示相应数字；(2)按 OK 键进行连线，显示屏上显示“连线中”，请连接基站，基站通过移动
6、电话网络连接到对方手机，若有误则返回相关信息；(3)接通后，显示屏显示“连线成功”；(4)打电话结束后，按 Cancel 送出断线信号，通知移动电话基站断线，基站切断连接，显示屏显示“断线成功”。该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML 类图表示，图 1 是该系统的用例图，图 2 是该系统的类图，图 3 描述了打电话(包括断开)的序列图。图 1图 2（分数：15.00）(1).根据题意，用题中及类图中提供的术语指出图 1 中的参与者 A 及用例 B、C 各是什么。（分数：7.50）_(2).根据题意，用题中及类图中提供的术语指出图 3 所示的打电话序列图中的消息(A)(
7、D)。（分数：7.50）_四、试题四(总题数：1，分数：15.00)说明在多道程序系统中，各个程序之间是并发执行的，共享系统资源。CPU 需要在各个运行的程序之间来回地切换，这样的话，要想描述这些多道的并发活动过程就变得很困难。为此，操作系统设计者提出了进程的概念。进程是具有独立功能的程序关于某个数据集合上的一次动态执行过程，是系统进行资源分配和调度的独立单位。（分数：15.00）(1).进程在生命周期结束前处于且仅处于三种基本状态之一。运行态(Running)：进程占有 CPU，并在 CPU上运行。就绪态(Ready)：一个进程已经具备运行条件，但由于无 CPU 暂时不能运行的状态(当调度给
8、其CPU 时，立即可以运行)。等待态(Blocked)：指进程因等待某种事件的发生而暂时不能运行的状态，即使CPU 空闲，该进程也不可运行。指出如下进程状态转换图(图 1)中“状态 1”“状态 3”分别是什么状态。*图 1（分数：5.00）_(2).如果单 CPU 系统中有 N 个进程，运行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个?（分数：5.00）_(3).进程调度算法解决以何种次序对各就绪进程进行处理机的分配以及按何种时间比例让进程占用处理机。常见的的调度算法有：先进先出 FIFO(按照进程进入就绪队列的的先后次序选择)、时间片轮转 RR(进程轮流运
9、行一个时间片)、最高优先级 HPF(分配给具有最高优先级的就绪进程)。在实际系统中，调度模式往往是几种调度算法的结合。某系统按优先级别设置若干个就绪队列，对级别较高的队列分配较小的时间片 Si(i=1, 2, , n),即有 S1S 2S n。除第 n 级队列是按 RR 法调度之外，其他各级队列均按 FIFO 调度。系统总是先调度级别较高的队列中的进程，仅当该队列为空时才去调度下一级队列中的进程。当执行进程用完其时间片时便被剥夺并进入下一级就绪队列。当等待进程被唤醒时，它进入其优先级相应的就绪队列，若其优先级高于执行进程，便抢占 CPU 执行进程。现有五个进程 P1、P2、P3、P4、P5，它
10、们同时依次进入就绪队列，它们所需的 CPU 时间和优先级如表所示。注意，优先数越大优先级越低。进程 CPU 时间 优先数P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2在该系统中，假定不同级别的时间片为 Si=2i-1(i 为优先数)，请给出五个进程的 CPU 占用序列，并注明每次占用所用的时间。（分数：5.00）_五、试题五(总题数：1，分数：15.00)1.说明所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大
11、小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。函数中使用的预定义符号如下：#define M 100typedef struct/为两端点 p1、p2 之间的距离, p1、p2 所组成边的长度*/float x;int p1, p2;tdr;typedef struct/*p1、p2 为和端点相联系的两个端点, n 为端点的度*/int n, p1, p2;tr;typedef struct /*给出两点坐标*/float x, y;tpd;typedef int t1M;int n = 10;函数float distance(tp
12、d a, tpd b);/*计算端点 a、b 之间的距离*/void sortArr(tdr aM, int m);/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表, m 为边的条数*/int isCircuit(tr rM, int i, int j);/*判断边(i, J)选入端点关系表 rM后，是否形成回路, 若形成回路返回 0*/void selected(tr rM, int i, int j);/*边(i，J)选入端点关系表 r*/void course(tr rM, t1 1 W);/*从端点关系表 r 中得出回路轨迹表*/void exchange(tdr aM,
13、int m, int b);/*调整表排序表, b 表示是否可调, 即是否有长度相同的边存在*/void travling(tpd pdM, int n, float dist, t1 locusM)/*dist 记录总路程*/tdr drM;/*距离关系表*/tr rM;/*端点关系表*/int i, j, k, h, m;/*h 表示选入端点关系表中的边数*/int b;/*标识是否有长度相等的边*/k = 0;/*计算距离关系表中各边的长度*/for(i = 1; i n; i+) for(j = i + 1; j = n; j+) k+;drk.x = _;drk.p1 = i;drk
14、.p2 = j;m = k;sortArr (dr, m);/*按距离大小从小到大排序形成排序表*/do b = i;dist = 0;k = h = 0;dok+;i = drk.p1;j = drk.p2;if(ri.n = 1) h+;dist += drk.x;else if(_) selected(r, i, j);/*最后一边选入 r 成回路，完成输出结果*/h+;dist += drk.x;while(k != n) if(h = n) /*最后一边选入构成回路, 完成输出结果*/course(r, locus);else/*找不到解, 调整 dr, 交换表中边长相同的边在表中的
15、顺序, 并将 b 置 0*/_;while(!b);（分数：15.00）填空项 1:_六、试题六(总题数：1，分数：15.00)2.说明现要编写一个画矩形的程序，目前有两个画图程序：DP1 和 DP2，DP1 用函数 draw_a_line(x1, y1, x2, y2)画一条直线，DP2 则用 drawline(x1, x2, y1, y2)画一条直线。当实例化矩形时，确定使用 DP1 还是DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。这里，“抽象部分”对应“形状”，“实现部分”对应“画图”，与一般的接口(抽象方法)与具
16、体实现不同。这种应用称为 Bridge(桥接)模式。图显示了各个类间的关系。（分数：15.00）填空项 1:_七、试题七(总题数：1，分数：15.00)3.说明现要编写一个画矩形的程序，目前有两个画图程序：DP1 和 DP2，DP1 用函数 draw_a_line(x1, y1, x2, y2)画一条直线，DP2 则用 drawline(x1, x2, y1, y2)画一条直线。当实例化矩形时，确定使用 DP1 还是DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。这里，“抽象部分”对应“形状”，“实现部分”对应“画图”，与一
17、般的接口(抽象方法)与具体实现不同。这种应用称为 Bridge(桥接)模式。图显示了各个类间的关系。（分数：15.00）填空项 1:_(A)中级软件设计师下午试题-3 答案解析(总分：106.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明考务处理系统具有如下功能：(1)对考生送来的报名单进行检查。(2)对合格的报名单编好准考证号后将准考证送给考生，并将汇总后的考生名单送给阅卷。(3)对阅卷站送来的成绩清单进行检查，并根据考试中心制订的合格标准审定合格者。(4)制作考生通知单送给考生。(5)进行成绩分类统计(按地区、年龄、文化程度、职业、考试级别等分类)和试题难度分析
18、，产生统计分析表。以下是经分析得到的数据流图及部分数据字典，有些地方有待填充，假定项层数据流图是正确的。图 1 是顶层数据流图，图 2 是第 0 层数据流图，图 3 是第 1 层数据流图，其中(A)是加工 1 的子图，(B)是加工 2的子图。图 1图 2（分数：15.00）(1).根据题意，指出 0 层数据流图(图 2)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：5.00）_正确答案：(成绩清单，起点：阅卷站，终点：统计成绩)解析：对于分层数据流图，一定要注意平衡原则，即父图与子图数据流一致。仔细与项层数据流图比对，可发现缺失了数据流“成绩清单”，其起点应为“阅卷站”，终点为加工
19、2“统计成绩”。(2).根据题意，指出加工 1 子图(图 3A)中缺失的数据流的名称，并指出该数据流的起点和终点。（分数：5.00）_正确答案：(报名单，起点：考生，终点：检查报名单)解析：方法同问题 1。可得加工 1 子图(图 3A)中缺失了数据流“报名单”，其起点自然是“考生”，终点应为加工 1.1“检查报名单”。(3).根据题意，指出加工 2 子图(图 3B)中缺失的数据流的名称，并指出该数据流的起点和终点。加工 2子图(图 3)中有一条数据流是错误的，请指出这条数据流的起点和终点。（分数：5.00）_正确答案：(合格标准，起点：考试中心，终点：审定合格者起点：制作通知单，终点：考生名册
20、)解析：方法同问题 1。可得加工 2 子图(图 3B)中缺失了数据流“合格标准”，其起点为“考试中心”，终点为加工 2.2“审定合格者”。错误数据流多半是表现在文件读出/写入上。加工 2.3“制作通知单”是从“考生名册”处获得考生信息，而不是写入，因此该数据流是错误的。二、试题二(总题数：1，分数：16.00)说明图 1 是某医院组织的结构图。该医院分为多个病区，每个病区有一个唯一的编号，一个病区包括多个病房，多名医生；每位医生有一个唯一的编号，负责管辖其主治病人的所有病房；病人住院后给以一个唯一的编号，根据“患何病科”住在相应病区的某个病房里，有且仅有一位医生担任主治医生，除主治医生外其他医
21、生不对其负责。现假定病区名称有“内科”和“外科”，“内科”病区又细分为多个病区，以编号区分，名称都为“内科”；“外科”病区亦然。图 2 是经分析得到的 E-R 图。图 1（分数：16.00）(1).实体间的联系有“一对一”、“一对多”和“多对多”，指出图 2 中各联系分别属于哪一种。（分数：4.00）_正确答案：(QR：一对多，QS：一对多，RS：一对多)解析：关系模型中实体间的联系有：一对一、一对多和多对多。一对一是指一个实体只与另一个实体相联系，一对多是指一个实体与多个实体相联系，多对多是指多个实体与多个实体间的联系。在这个系统中，一个病人只在一个病区，一个病区有多个病人，因此联系 QR
22、是一对多联系；一个病人只有一个主治医生，一个医生显然可以医治多名病人，因此联系 QS 是一对多联系：一名医生只属于一个病区，一个病区有多名医生，故联系 QS 是一对多联系。(2).选出正确的关系代数表达式。查询所有“外科”病区和“内科”病区的所有医生姓名：A Name=“外科“Name=“内科“ ( 4Q) B Name=“外科“Name=“内科“ ( 4(Q)C 4( Name=“外科“Name=“内科“ (Q) D 4( Name=“外科“Name=“内科“ (Q)（分数：4.00）A.B.C. D.解析：基本的关系代数包括并、差、广义笛卡儿积、投影、选择，其他运算可以通过基本的关系运算导
23、出。关系 R 与 S 具有相同的关系模式，即 R 与 S 的结构相同，关系 R 与 S 的并由属于 R 或属于 S 的元组构成的集合组成，记做 RS，其形式定义如下：RS=t|tRtS，式中 t 为元组变量。 并(Union)。关系 R 与 S 具有相同的关系模式，即 R 与 S 的结构相同，关系 R 与 S 的并由属于 R 或属于S 的元组构成的集合组成，记做 RS，其形式定义如下：RS=t|tRtS，式中 t 为元组变量。 差(Difference)。关系 R 与 S 具有相同的关系模式，关系 R 与 S 的差由属于 R 但不属于 S 的元组构成的集合组成，记做 R-S，其形式定义如下：R
24、S=t|tRt S。 广义笛卡儿积(Extended Cartesian Product)。两个元组分别为 n 目和 m 目的关系 R 和 S 的笛卡儿积是一个 n+m 列的元组的集合，元组的前 n 列是关系 R 的一个元组，后 m 列是关系 S 的一个元组，记做RS，其形式定义如下：RS=t|t=t n，t mt nRt mS。如果 R 和 S 中有相同的属性名，那么可在属性名前加关系名作为限定，以示区别。若 R 有 k1 个元组，S 有 k2 个元组，则 R 和 S 的广义笛卡儿积有k1k2 个元组。 投影(Projection)。投影运算是从关系垂直方向进行运算的，在关系 R 中选择出若
25、干属性列 A 组成新的关系，记做 A(R)，其形式定义如下： A(R)=fA|tR。 选择(Selection)。选择运算是从关系的水平方向进行运算的，从关系 R 中选择满足给定条件的诸元组，记做 F(R)，其形式定义如下： F(R)=t|tRF(r)=True。其中，F 中的运算对象是属性名(或列的序号)或常数。运算符是算术比较符(， ，(3).查询内科病区患胃病的病人的姓名。A Name=“外科“SC=“胃病“ ( 2(R) B Name=“内科“SC=“胃病“ ( 2(R)C 2( Name=“外科“SC=“胃病“ (R) D 2( Name=“内科“SC=“胃病“ (R)（分数：4.0
26、0）A.B.C.D. 解析：(4).层次模型不能直接表示多对多联系，为什么?可采用哪些方法进行多对多联系的表示。（分数：4.00）_正确答案：(层次模型采用树型结构表示数据与数据间的联系。在层次模型中，每一个节点表示记录类型(实体)，记录之间的联系用节点之间的连线表示，并且根节点以外的其他节点有且仅有一个双亲节点。层次模型不能直接表示多对多联系，若要表示多对多的联系，可采用如下两种方法： 冗余节点法两个实体的多对多的联系转换为两个一对多的联系，该方法的优点是节点清晰，允许节点改变存储位置，缺点是需要额外的存储空间，有潜在的数据不一致性。 虚拟节点分解法将冗余节点转换为虚拟节点，虚拟节点是一个指
27、引元，指向所代替的节点，该方法的优点是减少对存储空间的浪费，避免数据不一致性，缺点是改变存储位置可能引起虚拟节点中指针的修改。)解析：三、试题三(总题数：1，分数：15.00)说明移动电话是传统固定式电话的延伸，通过无线电网络可以与千里之外的朋友沟通而不受电话线的束缚。现在的移动电话功能更全面，除了作为电话使用外，还可以发送短信，可以管理电话簿，可以下载铃声、图案。手机由键盘、显示屏以及移动通信设备组成，移动通信设备负责发送和接收信号，与基站进行连线。打电话的流程如下：(1)用户拨电话号码，每按下一个数字键显示屏上显示相应数字；(2)按 OK 键进行连线，显示屏上显示“连线中”，请连接基站，基
28、站通过移动电话网络连接到对方手机，若有误则返回相关信息；(3)接通后，显示屏显示“连线成功”；(4)打电话结束后，按 Cancel 送出断线信号，通知移动电话基站断线，基站切断连接，显示屏显示“断线成功”。该系统采用面向对象方法开发，系统中的类以及类之间的关系用 UML 类图表示，图 1 是该系统的用例图，图 2 是该系统的类图，图 3 描述了打电话(包括断开)的序列图。图 1图 2（分数：15.00）(1).根据题意，用题中及类图中提供的术语指出图 1 中的参与者 A 及用例 B、C 各是什么。（分数：7.50）_正确答案：(A：“客户” B：“发短信” C：“管理电话簿”)解析：图给出了系
29、统用例图，用例图(use case diagram)展现了一组用例、参与者(actor)以及它们之间的关系。从说明易知参与者 A 是“用户”。仔细分析，缺少的用例为“发短信”和“管理电话簿”，而“发短信”与“无线电网络”相关，故用例 B为“发短信”，用例 C 为“管理电话簿”。(2).根据题意，用题中及类图中提供的术语指出图 3 所示的打电话序列图中的消息(A)(D)。（分数：7.50）_正确答案：(A)“按数字键”(B)“连接基站”(C)“按断线键”(D)“断开连接”)解析：根据题意，打电话的流程如下：用户拨电话号码，每按下一个数字键，显示屏上显示相应数字；按 OK 键进行连线，显示屏上显示
30、“连线中”，请求连接基站，基站通过移动电话网络连接到对方手机，若有误则返回相关信息：接通后，显示屏显示“连线成功”；打电话结束后，按 Cancel 送出断线信号，通知移动电话基站断线，基站切断连接，显示屏显示“断线成功”。对比可得，(A)为“按数字键”，(B)为“连接基站”，(C)为“按断线键”，(D)为“断开连接”。四、试题四(总题数：1，分数：15.00)说明在多道程序系统中，各个程序之间是并发执行的，共享系统资源。CPU 需要在各个运行的程序之间来回地切换，这样的话，要想描述这些多道的并发活动过程就变得很困难。为此，操作系统设计者提出了进程的概念。进程是具有独立功能的程序关于某个数据集合
31、上的一次动态执行过程，是系统进行资源分配和调度的独立单位。（分数：15.00）(1).进程在生命周期结束前处于且仅处于三种基本状态之一。运行态(Running)：进程占有 CPU，并在 CPU上运行。就绪态(Ready)：一个进程已经具备运行条件，但由于无 CPU 暂时不能运行的状态(当调度给其CPU 时，立即可以运行)。等待态(Blocked)：指进程因等待某种事件的发生而暂时不能运行的状态，即使CPU 空闲，该进程也不可运行。指出如下进程状态转换图(图 1)中“状态 1”“状态 3”分别是什么状态。*图 1（分数：5.00）_正确答案：(状态 1：运行态，状态 2：就绪态，状态 3：等待态
32、。)解析：根据问题 1 中对进程 3 种状态的描述，易于判断状态 1：运行态，状态 2：就绪态，状态 3：等待态。(2).如果单 CPU 系统中有 N 个进程，运行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个?（分数：5.00）_正确答案：(运行进程最多 1 个，最少 0 个；就绪进程最多 N-1 个，最少 0 个；等待进程最多 N 个，最少0 个。)解析：问题 1 给出了三种状态的具体表现形式。对于单 CPU 系统，运行的进程最多只有 1 个，最少可以是0 个(当所有进程都处于阻塞态时)。就绪进程最多只可能有 N-1 个，因为有就绪进程的话，肯定有运行进程
33、，最少 0 个。等待进程最多可有 N 个，最少可为 0 个(1 个运行，N-1 个就绪)。(3).进程调度算法解决以何种次序对各就绪进程进行处理机的分配以及按何种时间比例让进程占用处理机。常见的的调度算法有：先进先出 FIFO(按照进程进入就绪队列的的先后次序选择)、时间片轮转 RR(进程轮流运行一个时间片)、最高优先级 HPF(分配给具有最高优先级的就绪进程)。在实际系统中，调度模式往往是几种调度算法的结合。某系统按优先级别设置若干个就绪队列，对级别较高的队列分配较小的时间片 Si(i=1, 2, , n),即有 S1S 2S n。除第 n 级队列是按 RR 法调度之外，其他各级队列均按 F
34、IFO 调度。系统总是先调度级别较高的队列中的进程，仅当该队列为空时才去调度下一级队列中的进程。当执行进程用完其时间片时便被剥夺并进入下一级就绪队列。当等待进程被唤醒时，它进入其优先级相应的就绪队列，若其优先级高于执行进程，便抢占 CPU 执行进程。现有五个进程 P1、P2、P3、P4、P5，它们同时依次进入就绪队列，它们所需的 CPU 时间和优先级如表所示。注意，优先数越大优先级越低。进程 CPU 时间 优先数P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2在该系统中，假定不同级别的时间片为 Si=2i-1(i 为优先数)，请给出五个进程的 CPU 占用序列，并注明每次占用所用
35、的时间。（分数：5.00）_正确答案：(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 单位。根据调度策略“系统总是先调度级别较高的队列中的进程，仅当该队列为空时才去调度下一级队列中的进程；当执行进程用完其时间片时便被剥夺并进入下一级就绪队列”，系统先训度 P2 进程，执行 1 单位时间，
36、时间片到，P2 亦执行完毕，各个级别队列为： 优先数 1：时间片为 1 单位； 优先数 2：P5(5)，时间片为 2 单位； 优先数 3：P1(10)、P3(2)，时间片为 4 单位； 优先数 4：P4(1)，时间片为 8 单位。系统调度 P5 进程，执行 2 单位时间，进程 P5 还需 3 单位时间，进入优先数 3 队列，各个级别队列为： 优先数 1：时间片为 1 单位； 优先数 2：时间片为 2 单位； 优先数 3：P1(10)、P3(2)、P5(3)，时间片为 4 单位； 优先数 4：P4(1)，时间片为 8 单位。系统调度 P1 进程，执行 4 单位时间，进程 P1 还需 6 单位时间
37、，进入优先数 4 队列；继续调度 P3 进程，执行 2 单位时间，进程 P3 执行完毕；训度进程 P5，执行 3 单位时间，执行完毕，各个级别队列为： 优先数 1：时间片为 1 单位； 优先数 2：时间片为 2 单位； 优先数 3：时间片为 4 单位； 优先数 4：P4(1)、P1(6)，时间片为 8 单位。系统调度 P4 进程，执行 1 单位时间，进程 P4 执行完毕；继续调度 P1 进程，执行 6 单位时间，进程 P1 执行完毕。至此，可得五个进程的 CPU 占用序列以及其占用时间。P2(1)、P5(2)、P1(4)、P3(2)、P5(3)、P4(1)、P1(6)。五、试题五(总题数：1，
38、分数：15.00)1.说明所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。函数中使用的预定义符号如下：#define M 100typedef struct/为两端点 p1、p2 之间的距离, p1、p2 所组成边的长度*/float x;int p1, p2;tdr;typedef struct/*p1、p2 为和端点
39、相联系的两个端点, n 为端点的度*/int n, p1, p2;tr;typedef struct /*给出两点坐标*/float x, y;tpd;typedef int t1M;int n = 10;函数float distance(tpd a, tpd b);/*计算端点 a、b 之间的距离*/void sortArr(tdr aM, int m);/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表, m 为边的条数*/int isCircuit(tr rM, int i, int j);/*判断边(i, J)选入端点关系表 rM后，是否形成回路, 若形成回路返回 0*/vo
40、id selected(tr rM, int i, int j);/*边(i，J)选入端点关系表 r*/void course(tr rM, t1 1 W);/*从端点关系表 r 中得出回路轨迹表*/void exchange(tdr aM, int m, int b);/*调整表排序表, b 表示是否可调, 即是否有长度相同的边存在*/void travling(tpd pdM, int n, float dist, t1 locusM)/*dist 记录总路程*/tdr drM;/*距离关系表*/tr rM;/*端点关系表*/int i, j, k, h, m;/*h 表示选入端点关系表中
41、的边数*/int b;/*标识是否有长度相等的边*/k = 0;/*计算距离关系表中各边的长度*/for(i = 1; i n; i+) for(j = i + 1; j = n; j+) k+;drk.x = _;drk.p1 = i;drk.p2 = j;m = k;sortArr (dr, m);/*按距离大小从小到大排序形成排序表*/do b = i;dist = 0;k = h = 0;dok+;i = drk.p1;j = drk.p2;if(ri.n = 1) h+;dist += drk.x;else if(_) selected(r, i, j);/*最后一边选入 r 成回路
42、，完成输出结果*/h+;dist += drk.x;while(k != n) if(h = n) /*最后一边选入构成回路, 完成输出结果*/course(r, locus);else/*找不到解, 调整 dr, 交换表中边长相同的边在表中的顺序, 并将 b 置 0*/_;while(!b);（分数：15.00）填空项 1:_ （正确答案：distance(pdi,pdj)!isCircuit(r,i,j)selected(r,i,j)h=n-1exchange(dr,m,b)）解析：六、试题六(总题数：1，分数：15.00)2.说明现要编写一个画矩形的程序，目前有两个画图程序：DP1 和 DP2，DP1 用函数 draw_a_line(x1, y1, x2, y2)画一条直线，DP2 则用 drawline(x1, x2, y1, y2)画一条直线。当实例化矩形时，确定使用 DP1 还是DP2。为了适应变化，包括“不同类型的形状”和“不同类型的画图程序”，将抽象部分与实现部分分离，使它们可以独立地变化。这里，“抽象部分”对应“形状”，“实现部分”对应“画图”，与一般
