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