《2010上半年软件设计师考试真题及答案-下午卷.doc》由会员分享，可在线阅读，更多相关《2010上半年软件设计师考试真题及答案-下午卷.doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2010上半年软件设计师考试真题及答案-下午卷试题一 阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。 说明 某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求，欲构建数据管理中问件，其主要功能如下： 1数据管理员可通过中间件进行用户管理、操作管理和权限管理。用户管理维护用户信息，用户信息(用户名、密码)存储在用户表中；操作管理维护数据实体的标准操作及其所属的后端数据库信息，标准操作和后端数据库信息存放在操作表中；权限管理维护权限表，该表存储用户可执行的操作信息。 2中间件验证前端应用提供的用户信息。若验证不通过，返回非法用户信息；若验证通过，中间件将等待前端
2、应用提交操作请求。 3前端应用提交操作请求后，中间件先对请求进行格式检查。如果格式不正确，返回格式错误信息；如果格式正确，则进行权限验证(验证用户是否有权执行请求的操作)，若用户无权执行该操作，则返回权限不足信息，否则进行连接管理。 4连接管理连接相应的后台数据库并提交操作。连接管理先检查是否存在空闲的数据库连接，如果不存在，新建连接；如果存在，则重用连接。 5后端数据库执行操作并将结果传给中间件，中间件对收到的操作结果进行处理后，将其返回给前端应用。 现采用结构化方法对系统进行分析与设计，获得如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。 1、使用说明中的词语，给出图1-1中的实
3、体E1E3的名称。 2、使用说明中的词语，给出图1-2中的数据存储D1D3的名称 3、给出图1-2中加工P的名称及其输入、输出流。名称起点终点输入流P输出流P 除加工P的输入与输出流外，图1-2还缺失了两条数据流，请给出这两条数据流的起点和终点。 起点终点 注：名称使用说明中的词汇，起点和终点均使用图1-2中的符号或词汇。 4、在绘制数据流图时，需要注意加工的绘制。请给出三种在绘制加工的输入、输出时可能出现的错误。 试题二 阅读下列说明，回答问题1至问题3，将解答填入对应栏内。 说明 某学校拟开发一套实验管理系统，对各课程的实验安排情况进行管理。 需求分析 一个实验室可进行多种类型不同的实验。
4、由于实验室和实验员资源有限，需根据学生人数分批次安排实验室和实验员。一门课程可以为多个班级开设，每个班级每学期可以开设多门课程。一门课程的一种实验可以根据人数、实验室的可容纳人数和实验类型，分批次开设在多个实验室的不同时问段。一个实验室的一次实验可以分配多个实验员负责辅导实验，实验员给出学生的每次实验成绩。 (1)课程信息包括：课程编号、课程名称、实验学时、授课学期和丌课的班级等信息；实验信息记录该课程的实验进度信息，包括：实验名、实验类型、学时、安排周次等信息，如表2-1所示。 表2-1 课程及实验信息课程编号15054037课程名称数字电视原删实验学时12班级电0501，信0501，计05
5、01授课院系机械与电气工程授课学期第三学期序号实验名实验类难度学时安排周次1505403701音视频AD-DA实验验证性1231505403702音频编码实验验证性2251505403703视频编码实验演示性0.519 (2)以课程为单位制定实验安排计划信息，包括：实验地点，实验时间、实验员等信息，实验计划如表2-2所示。 表2-2 实验安排计划 课程编号15054037课程名称数字电视原理安排学期2009年秋总人数220实验编号实验名实验员实验员地点批次号人数1505403701音视频AD-DA丈验盛，陈第3周周四晚上实验三楼3101601505403701音视频AD-DA实验盛，陈第3周周
6、四晚上实验三楼3102601505403701音视频AD-DA实验吴，刘第3周周五晚上实验三楼3113601505403701音视频AD-DA实验吴第3周周五晚上实验三楼3114401505403702音频编码实验盛，刘第5周周一下午实验四楼410170 (3)由实验员给出每个学生每次实验的成绩，包括：实验名、学号、姓名、班级、实验成绩等信息，实验成绩如表2-3所示。 表2-3 实验成绩 实验员： 盛 实验名音视频AD-DA实验课程名数字电视原理学号姓名班级实验成绩030501001陈民信050187030501002刘志信050178040501001张勤计050186 (4)学生的实验课程
7、总成绩根据每次实验的成绩以及每次实验的难度来计算。 概念模型设计 根据需求阶段收集的信息，设计的实体联系图(不完整)如图2-1所示。 逻辑结构设计 根据概念模型设计阶段完成的实体联系图，得出如下关系模式(不完整)： 课程(课程编号，课程名称，授课院系，实验学时) 班级(班级号，专业，所属系) 开课情况( (1) ，授课学期) 实验( (2) ，实验类型，难度，学时，安排周次) 实验计划( (3) ，实验时间，人数) 实验员( (4) ，级别) 实验室(实验室编号，地点，开放时间，可容纳人数，实验类型) 学生( (5) ，姓名，年龄，性别) 实验成绩( (6) ，实验成绩，评分实验员) 5、补充
8、图2-1中的联系和联系的类型。 根据图2-1，将逻辑结构设计阶段生成的关系模式中的空67补充完整并用下划线指出这六个关系模式的主键。12、如果需要记录课程的授课教师，新增加“授课教师”实体。请对图2-1进行修改，画出修改后的实体问联系和联系的类型。试题三阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。 说明 某运输公司决定为新的售票机开发车票销售的控制软件。图3-1给出了售票机的面板示意图以及相关的控制部件。 售票机相关部件的作用如下所述： 13目的地键盘用来输入行程目的地的代码(例如，200表示总站)。 14乘客可以通过车票键盘选择车票种类(单程票、多次往返票和座席种类)。 15继
9、续/取消键盘上的取消按钮用于取消购票过程，继续按钮允许乘客连续购买多张票。 16显示屏显示所有的系统输出和用户提示信息。 17插卡口接受MCard(现金卡)，硬币口和纸币槽接受现金。 18打印机用于输出车票。 假设乘客总是支付恰好需要的金额而无需找零，售票机的维护工作(取回现金、放入空白车票等)由服务技术人员完成。 系统采用面向对象方法开发，使用UML进行建模。系统的顶层用例图和类图分别如图3-2和图3-3所示。 13、根据说明中的描述，给出图3-2中A1和A2所对应的参与者，U1所对应的用例，以及(1)、(2)处所对应的关系。 14、根据说明中的描述，给出图3-3中缺少的C1C4所对应的类名
10、以及(3)(6)处所对应的多重度。 15、图3-3中的类图设计采用了中介者(Mediator)设计模式，请说明该模式的内涵。 试题四 阅读下列说明和C代码，回答问题1至问题3，将解答写在对应栏内。 说明 对有向图进行拓扑排序的方法是： (1)初始时拓扑序列为空； (2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧； (3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。 函数int* TopSort(LinkedDigraphG.的功能是对有向图G中的顶点进行拓扑排序，返回
11、拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，vn，图G采用邻接表表示，其数据类型定义如下： #define MAXVNUM 50 /*最大顶点数*/ typedef struct ArcNode /*表结点类型*/ int adjvex; /*邻接顶点编号*/ struct ArcNode *nextarc; /*指示下一个邻接顶点*/ ArcNode; typedef struct AdjList /*头结点类型*/ char vdata; /*顶点的数据信息*/ ArcNode *fimstarc; /*指向邻接表的
12、第一个表结点*/ AdjList; typedef struct LinkedDigraph /*图的类型*/ int n; /*图中顶点个数*/ AdjList VheadMAXVNUM; /*所有顶点的头结点数组*/ LinkedDigraph; 例如，某有向图G如图4-1所示，其邻接表如图4-2所示。 函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示： 函数原型说明void InitQueue(Queue *Q)初始化队列(构造一个卒队列)bool IsEmpty(Queue Q)判断队列是否为空，若是则返回true，否则返回falsevo
13、id EnQueue(Queue *Q，int e)元素入队列void DeQueue(Queue *Q，int *p)元素出队列 C代码 int *TopSort(LinkedDigraphG. ArcNode *p; /*临时指针，指示表结点*/ Queue Q; /*临时队列，保存入度为0的顶点编号*/ int k=0; /*临时变量，用作数组元素的下标*/ intj=0，w=0; /*临时变量，用作顶点编号*/ int *topOrder，*inDegree; topOrder=(int *)malloc(G.n+1) *sizeof(int); /*存储拓扑序列中的顶点编号*/ in
14、Degree=(int *)malloc(G.n+1) *sizeof(int); /*存储图G中各顶点的入度*/ if(!inDegree | !topOrder) return NULL; (1) ; /*构造一个空队列*/ for(j=1; j=G.n; j+)/*初始化*/ topOrderj=0; inDegreej=0; for(j=1;j=G.n;j+) /*求图G中各顶点的入度*/ for(p=G.Vheadj.firstarc; P; P=P-nextarc) inDegreeP-adjvex+=1; for(j=1; j=G.n;j+) /*将图G中入度为0的顶点保存在队列
15、中*/ if(0=inDegreej) EnQueue(Q,j); while(!IsEmpty(Q) (2) ; /*队头顶点出队列并用w保存该顶点的编号*/ topOrderk+=w; /*将顶点w的所有邻接顶点的入度减1(模拟删除顶点w及从该顶点出发的弧的操作)*/ for(p=G.Vheadw.firstarc;P; p=p-nextarc) (3) -=1; if(0= (4) ) EnQueue(Q，P-adjvex); 1/for$/ /*while*/ free(inDegree); if( (5) ) return NULL; return topOrder; /*TopSo
16、rt*/根据以上说明和C代码，填充C代码中的空1617。21、对于图4-1所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。 设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是 22 。 若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是 23 。 试题五阅读下列说明和C
17、+弋码，将应填入 (n) 处的字句写在对应栏内。 说明 某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表5-1所示。 表5-1飞机种类起飞特征飞行特征直升机(Helicopter)垂直起飞(VerticalTakeOff)亚音速飞行(SubSonicFly)客机(AirPlane)长距离起飞(LongDistanceTakeOff)亚音速飞行(SubSonicFly)歼击机(Fighter)长距离起飞(LongDistanceTakeOff)超音速飞行(SuperSonicFly)鹞式战斗机(Harrier)垂直起飞(Ver
18、ticalTakeOff)超音速飞行(SuperSonicFly) 为支持将来模拟更多种类的飞机，采用策略设计模式(strategy)设计的类图如图5-1所示。 图5-1中，AirCraft为抽象类，描述了抽象的飞机，而类Helicopter、AirPlane、Fighter和Harrier分别描述具体的飞机种类，方法fly31和takeOff31分别表示不同飞机都具有飞行特征和起飞特征；类FlyBehavior与TakeOffBehavior为抽象类，分别用于表示抽象的飞行行为与起飞行为；类SubSonicFly与SuperSonicFly分别描述亚音速飞行和超音速飞行的行为；类Vertic
19、alTakeOff与LongDistanceTakeOff分别描述垂直起飞与长距离起飞的行为。 C+代码 #includeiostream using namespace std; class FlyBehaVior public: virtual void fly31=0; ; class SubSonicFly: public FlyBehaVior public: void fly31cout亚音速飞行!endl;) ; class SupersonicFly: public FlyBehaVior public: void fly31cout超音速飞行!endl;) ; class T
20、akeOffBehavior publie: virtual void takeOff31=0; ; class VerticalTakeOff: public TakeOffBehavior public: void takeOff31cout垂直起飞!endl ; class LongDistanceTakeOff: public TakeOffBehavior public: void takeOff31cout长距离起飞!endl; ; class AirCraft protected: 24 ; 25 ; public: void fly31 26 ; void takeoff31
21、27 ; ; ; class Helicopter: public AirCraft public: Helicopter 31 flyBehavior=new 28 ; takeoffBehavior=new 29 ; 30 if(!flyBehaVior) delete flyBehaVior; if(!takeoffBehavior) delete takeoffBehaVior; ; /其他代码省略 试题六 阅读下列说明和Java代码，将应填入(n)处的字句写在对应栏内。 说明 某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及
22、其特征如表6-1所示。 表6-1飞机种类起飞特征飞行特征直升机(Helicopter)垂直起飞(VerticalTakeOff)亚音速飞行(SubSonicFly)客机(AirPlane)长距离起飞(LongDistanceTakeOff)亚音速飞行(SubSonicFly)歼击机(Fighter)长距离起飞(LongDistanceTakeOff)超音速飞行(SuperSonicFly)鹞式战斗机(Harrier)垂直起飞(VerticalTakeOff)超音速飞行(SuperSonicFly) 为支持将来模拟更多种类的飞机，采用策略设计模式(Strategy)设计的类图如图6-1所示。 图
23、6-1中，AirCraft为抽象类，描述了抽象的飞机，而类Helicopter、AirPlane、Fighter和Harrier分别描述具体的飞机种类，方法fly38和takeOff38分别表示不同飞机都具有飞行特征和起飞特征；类FlyBehavior与TakeOffBehavior为抽象类，分别用于表示抽象的飞行行为与起飞行为；类SubSonicFly与SuperSonicFly分别描述亚音速飞行和超音速飞行的行为；类VerticalTakeOff与LongDistanceTakeOff分别描述垂直起飞与长距离起飞的行为。 Java代码 interface FlyBehavior publi
24、c void fly38; ; class SubSonicFly implements FlyBehavior public void fly38(System.out.println(业音速飞行!);) ; class SuperSonicFly implements FlyBehavior public void fly38 System.out.println(超音速飞行!); ; interface TakeOffBehavior public void takeOff38; ; class VerticalTakeOff implements TakeOffBehavior pub
25、lic void takeOff38 System.out.println(垂直起飞!); ; class LongDistanceTakeOff implements TakeOffBehavior public void takeOff38 System.out.println(长距离起飞!); ; abstract class AirCraft protected 31 ; protected 32 ; public void fly38 33 ; public void takeOff38 34 ; ; class Helicopter 35 AirCraft public Helic
26、opter38 flyBehavior=new 36 ; takeOffBehavior=new 37 ; ; /其他代码省略 答案:试题一1、E1：前端应用 E2：数据管理员 E3：后端数据库本问题考查顶层DFD。顶层DFD一般用来确定系统边界，将待开发系统看作一个加工，因此图中只有唯一的一个加工和一些外部实体，以及这两者之间的输入输出数据流。题目要求根据描述确定图中的外部实体。分析题目中的描述，并结合已经在顶层数据流图中给出的数据流进行分析。题目中有信息描述：数据管理员可通过中间件进行用户管理、操作管理和权限管理；前端应用提交操作请求；连接管理连接相应的后台数据库并提交操作。由此可知该中间
27、件系统有数据管理员、前端应用和后端数据库三个外部实体。从图1-1中数据流和实体的对应关系可知，E1为前端应用，E2为数据管理员，E3为后端数据库。2、D1：用户表 D2：操作表 D3：权限表本问题考查0层DFD中数据存储的确定。说明中描述：用户信息(用户名、密码)存储在用户表中；标准操作和后端数据库信息存放在操作表中；权限管理维护信息存放在权限表中。因此数据存储为用户表、操作表以及权限表。再根据图1-2可知D1的输入数据流从用户管理来，D2的输入数据流从操作管理来，D3的输入数据流从权限管理来，所以D1为用户表，D2为操作表，D3为权限表。3、P的名称：操作结果处理 名称起点终点输入流操作结果
28、E3P输出流处理后的操作结果PE1 缺少的数据流： 起点终点D2权限验证D3权限验证本问题考查0层DFD中缺失的加工和数据流。比较图1-1和图1-2，可知顶层DFD中的操作结果和处理后的操作结果没有在0层DFD中体现。再根据描述“后端数据库执行操作并将结果传给中问件，中间件对收到的操作结果进行处理后，将其返回给前端应用”可知，需要有操作结果处理，因此P为操作结果处理，其输入流为从后端数据库E3来的操作结果，输出结果为处理后的操作结果，并返回给前端应用E1。 考查完P及其输入输出流之后，对图1-2的内部数据流进行考查，以找出缺失的另外2条数据流。从图中可以看出D2和D3只有输入流没有输出流，这是
29、常见DFD设计时的错误，所以首先考查D2和D3的输出流。描述中有“权限验证是验证用户是否有权执行请求的操作，若用户有权执行该操作，进行连接管理；连接管理连接相应的后台数据库并提交操作；权限表存储用户可执行的操作信息”。因此，权限验证有从权限表D3来的输入数据流。而要连接后端数据库，需要数据库信息，从权限验证的输出流中包含有数据库信息可知，权限验证需要获取到数据库信息，所以还需从操作表D2来的输入流。4、在绘制数据流图的加工时，可能出现的输入、输出错误： 只有输入而无输出或者黑洞 只有输出而无输入或者奇迹 输入的数据流无法通过加工产生输出流或者灰洞 输入的数据流与输出的数据流名称相同本问题考查在
30、绘制数据流图中加工绘制时的注意事项。绘制加工时可能出现的错误有：加工的输入、输出时可能出现只有输入而无输出、只有输出而无输入、输入的数据流无法通过加工产生输出流以及输入的数据流与输出的数据流名称相同等错误。试题二5、根据题意，由“一门含实验的课程可以开设给多个班级，每个班级每学期可以开设多门含实验的课程”可知课程和班级之间的开设关系为m:n联系。由“一个实验室的一次实验可以分配多个实验员负责辅导实验”可知实验、实验室与实验员之问的安排关系为k:n:m联系。由“实验员给出学生的每次实验成绩”可知实验、学生与实验员之间的成绩关系为k:n:m联系。班级和学生之问的包含关系为1:n联系。6、课程编号，
31、班级号 7、实验编号，课程编号 8、实验编号，批次号，安排学期，实验室编号，实验员编号 9、实验员编号，实验员姓名 10、学号，班级号 11、实验编号，学号 其他关系模式主键： 课程(课程编号，课程名称，授课院系，实验学时) 班级(班级号，专业，所属系) 实验室(实验室编号，地点，开放时间，可容纳人数，实验课类型)根据题意可知课程编号是课程的主键，班级号是班级的主键。从表2-1可知，开课情况是体现课程与班级问的m:n联系，因此开课情况关系模式应该包含课程编号和班级号，并共同作为主键。一门课程包含多次实验，实验与课程之间是m:1关系，因此，根据表2-1，实验关系模式应包含实验编号和课程编号，并且
32、以实验编号为主键，以课程编号为外键。在制定试验计划时，每个班的每次实验可能按实验室被分成多个批次，每个批次的实验会有若干名实验员来辅导学生实验并打分。实验员关系模式应该记录实验员编号和实验员姓名，并以实验员编号为主键。实验室编号是实验室的主键。从表2-2可见，实验计划关系模式应记录实验编号、批次号和授课学期，并且共同作为主键。从表2-3可见，实验成绩关系模式记录每个学生的每次实验成绩，应包含学号和实验编号，并共同作为主键。12、由于授课教师负责给若干个班级开设若干门课程，因此，课程、班级和授课教师之问的开设关系是k:n:m联系。 试题三13、A1：乘客 A2：服务技术人员 U1：支付 (1)i
33、nclude (2)include本问题考查用例图。用例图用于确定系统边界，识别与系统交互的参与者，通过判断参与者发起的用例，建立和参与者之间的关联，然后再确认用例之间的关系。 本题中对售票机的描述为“乘客可以通过车票键盘选择车票种类(单程票、多次往返票和座席种类)；售票机的维护工作(取回现金、放入空白车票等)由服务技术人员完成”。由此可知，图3-1中A1为乘客，A2为服务技术人员。 对购票用例，要选择目的地和车票类型、通过插卡口进行支付才可完成购票。因此U2为支付。 在考查用例之间的关系时，购票过程可以取消，也允许乘客连续购买多张票，因此，购票时可以包含多次选择目的地和车票类型、支付，即购票
34、用例包含(关系include)选择目的地和车票类型以及支付。14、C1：键盘 C2：目的地键盘 C3：车票键盘 C4：继续/取消键盘 (3)(6)：1本问题考查类图。类图设计的重点是类的抽象和继承关系以及多重度。售票机的面板由多个控制部件组成。根据说明这些控制部件有目的地键盘、车票键盘和继续/取消键盘、显示屏、卡驱动器、硬币/纸币槽、打印机。图3-3中只有前3个部件在图中没有给出，而要填如4个类。从图中已经抽象出的硬件组件，给出了抽象的思路，从而可以把键盘抽象出来。由C1与C2、C3、C4的继承关系中C1为基类，可知C1为键盘。由C2、C3和C4给出的方法名称可知，C2为目的地键盘获取目的地代
35、码，C3为车票键盘选择产品类型，C4为继续/和取消动作。 本题中的重复度比较简单。从图3-1售票机的图示中可以看出，一个售票机只包含一个目的地键盘、一个车票键盘和一个继续/取消键盘，因此(3)(6)均为1。15、使用Mediator模式，可以使各个对象问的耦合松散，只需关心和Mediator的关系，使多对多的关系变成了一对多的关系，可以降低系统的复杂性，提高可修改扩展性。本问题考查设计模式。设计模式题目虽然比较难，但是本题题目中已经给出了所采用的设计模式为：Mediator模式，只需说明设计模式的内涵即可，也比较容易。使用Mediator模式，可以使各个对象问的耦合松散，只需关心和Mediat
36、or的关系，使多对多的关系变成了一对多的关系，可以降低系统的复杂性，提高可修改扩展性。试题四16、InitQueue(Q) 17、DeQueue(Q，w) 18、inDegreep-adjvex 或其等价形式 19、inDegreep-adjvex 或其等价形式 20、kGn 或k!=Gn 或其等价形式拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。 对AOE网进行拓扑排序的方法如下： 在AOE网中选择一个入度为零(没有前驱)的顶点且输出它； 从网中删除该顶点及其与该顶点有关的所有边；
37、 重复上述两步，直至网中不存在入度为零的顶点为止。 在拓扑排序过程中，需要将入度为0的顶点临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然，空(1)处应填入InitOueue(Q)。 进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组inDegree中，从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”，一旦发现某个顶点的入度变为0，就将其编号压入堆栈。从而将选择入度为0的顶点操作转化为令队头所代表的顶点出队。 根据注释，空(2)处应填入DeQueue(Q，w)，实现队头元素出队列的处理。 题中图采用邻接表存储结构，当指针p指向vi
38、邻接表中的结点时，p-adjvex表示vi的一个邻接顶点，删除vi至顶点p-adjvex的弧的操作实现为顶点p-adjvex的入度减1，因此，空(3)处应填入inDegreep-adjvex，当顶点p-adjvex的入度为0时，需要将其加入队列，因此空(4)处也应填入inDegreep-adjvex。 空(5)处判断是否所有顶点都加入了拓扑序列，算法中变量k用于对加入序列的顶点计数，因此，空(5)处应填入“kGn”或“k!=Gn”。21、队列方式：v1 v2 v5 v4 v3 v7 v6 或者1 2 5 4 3 7 6 栈方式：v1 v2 v5 v4 v7 v3 v6 或者1 2 5 4 7
39、3 6使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图，在使用队列的方式下： (1)开始时仅顶点v1的入度为O，因此顶点v1入队； (2)队头顶点v1出队，并进入拓扑序列，然后删除从顶点v1出发的弧后，仅使顶点v2的入度为0，因此顶点v2入队； (3)队头顶点v2出队，并进入拓扑序列，然后删除从顶点v2出发的弧后，仅使顶点v5的入度为0，因此顶点v5入队； (4)队头顶点v5出队，并进入拓扑序列，然后删除从顶点v5出发的弧后，仅使顶点v4的入度为0，因此顶点v4入队； (5)队头顶点v4出队，并进入拓扑序列，然后删除从顶点v4出发的弧后，仅使顶点v3和v7的入度为0，
40、因此顶点v3和v7依次入队； (6)队头顶点v3出队，并进入拓扑序列，然后删除从顶点v3出发的弧后，没有产生新的入度为0的顶点； (7)队头顶点v7出队，并进入拓扑序列，然后删除从顶点v7出发的弧后，使顶点v6的入度为0，因此顶点v6入队； (8)队头顶点v6出队，并进入拓扑序列，然后删除从顶点v6出发的弧后，没有产生新的入度为0的顶点，队列已空，因此结束拓扑排序过程，得到的拓扑序列为v1 V2 v5v4 v3 v7 v6。 使用栈保存入度为0的顶点时，前4步都是一样的，因为每次仅有一个元素进栈，因此出栈序列与入栈序列一致。到第5步时，v3和v7依次入栈后，出栈时的次序为v7和v3，因此得到的
41、拓扑序列为v1 v2 v5 v4 v7 v3 v6。22、O(n+e) 23、O(n2)以邻接表为存储结构时，计算各顶点入度的时问复杂度为O(e)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，(图中无环情况下)每个顶点进出队列各1次，入度减1的操作在while循环中共执行e次，所以总的时间复杂度为O(n+e)。 以邻接矩阵为存储结构时，计算各顶点入度时需要遍历整个矩阵，因此时间复杂度为O(n2)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，(图中无环情况下)每个顶点进出队列各1次，实现入度减1操作时需遍历每个顶点的行向量1遍(时问复杂度为O(n)，所以总的时间复杂度为O(n2)。 试题五24、 FlyBehavior *flyBehavior 25、 TakeOffBehavjor *=takeOffBehavior 26、 flyBehavior-fly() 27、 takeOffBehavior-takeOff()_ 28、 SubSonicFly() 29、VerticalTakeOff() 30、 Helicopter()本题目