第8章交互图习题
一、简答题
1、 什么叫交互？
答:交互表示一组相关的对象在动作执行中,通过相互交互消息,完成确定的任务。
2、 什么叫生命线？
答:生命线表示参与交互的一个实体及实体集合。一条生命线表示为一个矩形框下面垂着一条虚线。
3、 消息有哪几种类型？
答:同步调用消息,异步调用消息,异步信号,应答消息,创建消息,销毁消息。
4、 交互图有哪几种形式？
答:顺序图,通信图,交互概览图,时序图。
5、 简述交互概览图的概念与作用。
答:交互概览图就是把顺序图与活动图结合起来描述交互流程与交互细节的一种交互图。其作用就是用来对复杂的交互流程与细节进行建模。
6、 交互概览图有哪两种类型？
答:以活动图为主线,以顺序图为主线
7、 什么叫时序图？
答:时序图用来描述在一个交互中,参与交互的各对象实体状态变化的时序关系。
二、填空题
1、 交互表示一组相关的(对象)为了完成某项任务,相互交换(信息)的情况。
2.顺序图强调在交互过程中,各交互的(各对象)之间消息传输的(时序)关系。
3.消息就是一种(命名)元素,它定义了在交互中,生命线之间的一种特定的(关系)。
4、 在交互事件的时序中,同一消息的(发送)事件一定先于(接收)事件。
5. 通信图也被称为(协作),用来描述参与交互的多个对象实体之间的(结构)关系。
6、 交互概览图结合了(活动图)与(顺序图)两种图。
7.交互概览图就是用来描述一个复杂的交互(流程)与交互(细节)的一种图。
8.以活动图为主线的交互概览图适合对复杂的(工作流)进行建模,而以顺序图为主线的交互概览图则适合描述顺序图中的某些(交互片断)的流程。
9、 时序图用来描述在一个(交互)中,参与交互的各对象实体状态变化的(时序)关系。
10.时序图的要素包括:生命线、(状态)、事件、(时间刻度)与时序约束。
11.时序图的两种表示法为:(一般表示法),(交错表示法)。
1 第七章 图
1． 设有一有向图为G=(V，E)。其中，V={v0, v1, v2, v3}，E={, , , , }。请画出该有向图。
2．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题∶
(1) 图中有多少条边?
(2) 任意两个顶点i和j是否有边相连?
(3) 任意一个顶点的度是多少?
3． 对于下面的带权有向图，写出其相邻矩阵表示，并画出其邻接表表示。
4． 图7.26所示的有向图是强连通的吗? 请列出所有简单路径，并给出其邻接矩阵的表示、边表分别为出边表和入边表的邻接表的表示。
5． 对于图7.27，从顶点v0出发分别画出其深度优先生成树和广度优先生成树。
6． 对于图7.28所示的网络，请分别用Prim算法和Kruskal算法构造该网络的最小生成树。
7． 用Dijstra算法求图7.29中从顶点v0到其他各顶点的最短路径，要求写出此图的关系矩阵arcs和数组Dist在算法执行过程中的变化，以及每一条最短路径。 2 8． 试应用Floyd算法求图7.30所示有向图的各对顶点之间的最短路径，并写出在执行算法过程中所得到的最短路径长度矩阵Ai序列和最短路径矩阵nextvexi序列
9． 拓扑排序的结果不是唯一的，对于图7.31中的顶点进行拓扑排序，得到不同的拓扑序列竟达52之多，试写出其中任意10个。
10． 证明∶只要适当排列顶点的次序就能使无环有向图的关系矩阵中对角线以下元素全为0。
11． 假设一棵完全二叉树A，B，…，G等七个结点，写出其邻接表和邻接矩阵。
12． 画出以顶点V1为初始源点遍历所示的有向图所得到的深度优先遍历和广度优先遍历生成森林。
13．按顺序输入顶点对：(1,2)，(1,6)，(2,6)，(1,4)，(6,4)，(1,3)，(3,4)，(6,5)，(4,5)，(1,5)，(3,5)，根据建立无向图的邻接表算法CreateDG画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的深度优先遍历序列和广度优先遍历序列。
-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- 第七章 图
7.1
解：(1) ID(1)=3 OD(1)=0
ID(2)=2 OD(2)=2
ID(3)=1 OD(3)=2
ID(4)=1 OD(4)=3
ID(5)=2 OD(5)=1
ID(6)=2 OD(6)=3
(2) 0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
(3)
(4)
(5) 有三个连通分量1、5、2346
7.7 请对下面的无向带权图， -----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；
（2）写出它的邻接表，并按克鲁期卡尔算法求其最小生成树。
解：（1）图的邻接矩阵为
-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享----
-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享----
7.9试列出题7.9图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法Topological Sort求得的是哪一个序列（注意：应先确定其存储结构）。
Status TopologicalSort(ALGraph G)
FindIndegree(G,indegree);//对各顶点求入度
InitStack(S); -----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- For(i=0;i
If(!Indegree[i])Push(S,i);//入度为0者进栈
count=0; //对输出顶点计数
第8章交互图习题
一、简答题
1. 什么叫交互
答：交互表示一组相关的对象在动作执行中，通过相互交互消息，完成确定的任务。
2. 什么叫生命线
答：生命线表示参与交互的一个实体及实体集合。一条生命线表示为一个矩形框下面垂着一条虚线。
3. 消息有哪几种类型
答：同步调用消息，异步调用消息，异步信号，应答消息，创建消息，销毁消息。
4. 交互图有哪几种形式
答：顺序图，通信图，交互概览图，时序图。
5. 简述交互概览图的概念和作用。
答：交互概览图是把顺序图和活动图结合起来描述交互流程和交互细节的一种交互图。其作用是用来对复杂的交互流程和细节进行建模。
6. 交互概览图有哪两种类型
答：以活动图为主线，以顺序图为主线
7. 什么叫时序图
答：时序图用来描述在一个交互中，参与交互的各对象实体状态变化的时序关系。
二、填空题
1. 交互表示一组相关的（对象）为了完成某项任务，相互交换（信息）的情况。
2．顺序图强调在交互过程中，各交互的（各对象）之间消息传输的（时序）关系。
3．消息是一种（命名）元素，它定义了在交互中，生命线之间的一种特定的（关系）。
4. 在交互事件的时序中，同一消息的（发送）事件一定先于（接收）事件。
5． 通信图也被称为（协作），用来描述参与交互的多个对象实体之间的（结构）关系。
6. 交互概览图结合了（活动图）和（顺序图）两种图。
7．交互概览图是用来描述一个复杂的交互（流程）和交互（细节）的一种图。
8．以活动图为主线的交互概览图适合对复杂的（工作流）进行建模，而以顺序图为主线的交互概览图则适合描述顺序图中的某些（交互片断）的流程。
9. 时序图用来描述在一个（交互）中，参与交互的各对象实体状态变化的（时序）关系。
10．时序图的要素包括：生命线、（状态）、事件、（时间刻度）和时序约束。
11．时序图的两种表示法为：（一般表示法），（交错表示法）。
