设有向图 G = （V，E），顶点集 V = { V0，V1，V2，V3}，边集 E = {
解析： 共有 5 种可能：
考点：图的遍历 图的遍历（深度、广度）
计算机组成原理
某机共有 52 个微操作控制信号，构成 5 个相斥类的微命令组，各组分别包含 5、8、2、15、22 个微命令。已知可判定的外部条件有两个，微指令字长 28 位。
1） 按水平型微指令格式设计微指令，要求微指令的下地址字段直接给出后继微指令地址。
2） 指出控制存储器的容量。
解析：1） 根据 5 个互斥类的微命令组，各组分别包含 5、8、2、15、22个微命令，考虑到每组必须增加一种不发命令的情况，条件测试字段应包含一种不转移的情况，则 5 个控制字段分别需给出6、9、3、16、23 种状态，对应 3、4、2、4、5位（共18位），条件测试字段取 2 位。根据微指令字长为 28 位，下地址字段取 28 - 18 - 2 = 8位。
2） 根据后继地址字段为 8 位，微指令字长为 28 位，得出控制存储器的容量为 28 × 28位。
考点：微指令格式设计 微命令 微指令 微操作 微程序
操作系统
系统中有 3 个不同的临界资源 R1，R2和 R3，被 4 个进程 P1，P2，P3，P4共享。各进程对资源的需求为：P1 申请 R1 和 R2 ，P2 申请 R2 和R3 ，P3 申请 R1 和 R3，P4 申请 R2。若系统出现死锁，则处于死锁状态的进程数至少是【3】。
解析：关于临界资源分配的一道题
考点：死锁的四个必要条件和解决办法
计算机网络
在下列情况下，计算传送 1000KB 文件所需要的总时间，即从开始传送时起直到文件的最后一位到达目的地为止的时间。假定往返时间 RTT 为 100ms，一个分组是 1KB 数据，在开始传送整个文件数据之前进行的起始握手过程需要 2RTT 的时间。
1） 带宽是 1.5Mb/s，数据分组可连续发送。
2） 带宽是 1.5Mb/s，但在发送完每个数据分组后，必须等待一个 RTT（等待来自接收方的确认）才能发送下一个数据分组。
3） 假设带宽是无限大的值，即我们取发送时间为 0，并在等待每个 RTT 后可以发送多达20个分组。
解析：提示：如果题目没有说考虑排队时延，那么处理时延也无须考虑。
1） 由提示可知，总时延 = 发送时延+传播时延+握手时延，其中握手时延是题目增加的。两个起始的 RTT（握手）= 100×2 = 200ms，传播时间 = RTT / 2 = 100 / 2 = 50ms，1KB = 8bit × 1024 = 8192 bit，发送时间 = 1000KB / (1.5Mb/s) = 5.46s，所以总时间 = 0.2 + 5.46 + 0.05 = 5.71s。
2） 在上一小题答案的基础上再增加 999 个RTT，总时间为 5.71 + 999×0.1 = 105.61s。
注意：1）中的发送时间是所有分组的发送时间之和。
3） 由于发送时延为 0，只需计算传播时延。由于每个分组为 1KB，所以大小为 1000KB 的文件应分成 1000个分组。由于每个 RTT 后可发送20个分组，所以共需 1000/20=50次，50-1=49个RTT，最后一个分组到达目的地仅需 0.5RTT（注意，在本次等待的 RTT 中一定包含了上次传输的传输时延，所以不要认为还需要另外计算传输时延），总时间为 2RTT（握手时间）+ 49RTT + 0.5RTT = 51.5RTT=5.15s。
编程题
[2021统考真题] 已知无向连通图 G 由顶点集 V 和边集 E 组成，|E| > 0，当 G 中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为 |E| 的路径（称为 EL 路径)。设图 G 采用邻接矩阵存储，类型定义如下：
typedef struct{ // 图的定义
int numVertices,numEdges; // 图中实际的顶点数和边数
char VerticesList(MAXV); // 顶点表。为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
请设计算法 int IsExistEL (MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则返回 0。要求：
1） 给出算法的基本设计思想。
2） 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3） 说明你所设计算法的时间复杂度和空间复杂度。
解析： 1） 算法的基本设计思想
对于采用邻接矩阵存储的无向图，在邻接矩阵的每一行（列）中，非零元素的个数为本行(列)对应顶点的度。可以依次计算连通图 G 中各顶点的度，并记录度为奇数的顶点个数，若个数为 0 或2，则返回 1，否则返回 0 即可。
2）算法实现
int IsExistEL(MGraph G){
//采用邻接矩阵存储,判断图是否存在 EL 路径
int degree, i, j, count = 0;
for(i = 0; i < G.numVertices; i++){
degree = 0;
for(j = 0; j < G.numVertices; j++)
degree += G.Edge[i][j]; // 依次计算各个顶点的度
if(degree %2 != 0)
count++; // 对度为奇数的顶点计数
}
if(count == 0 || count==2)
return 1;
else
return 0;
}
3）时间复杂度和空间复杂度
算法需要遍历整个邻接矩阵，所以时间复杂度是 O（n2），空间复杂度是O（1）。
