11.22 - 每日一题 - 408

每日一句：Not every effort there is a harvest, but each time the harvest must be hard, which is not a fair irreversible propositions. 不是每一次努力都有收获。但是，每一次收获都必须努力，这是一个不公平的不可逆转的命题。

数据结构

1 下列关于图结构的存储的说法中，正确的是____

A.  无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵
B.  带权的有向图和无向图，可以使用邻接表存储，但不可以用邻接矩阵存储
C.一个有向图的邻接表和逆邻接表中结点的个数可能不等
D.图用邻接矩阵存储时，存储空间大小只与图中顶点个数有关，而与图的边数无关（不考虑邻接矩阵压缩存储的情况下）
1
2
3
4

答案：D

解析：对于A，无向图的邻接矩阵一定对称的说法是正确的，但有向图的邻接矩阵也可能对称，这时有向图中的弧是对称出现的，即对于图中的任意两个顶点u和v，若存在，则也存在。
对于B，邻接矩阵也可以在存储上完全映射带权的图结构，因此可以作为存储结构的一种选择。
对于C，邻接表是将顶点的出边作为存储对象，逆邻接表则是将顶点的入边作为存储对象。就有向图的任何一条边来说，它是一个顶点的入边，同时必然是另一个顶点的出边，所以图中顶点的总入度和总出度完全一致，反映到结点数目上也一定相等。
对于D，设图中的顶点数是n，用邻接矩阵存储图时，有两个存储部分。一个是存储顶点信息的顶点顺序表，它的大小只与n有关；另一个是存储关系（即边）信息的邻接矩阵，它将所有顶点间的邻接关系体现出来，即使两个顶点不邻接也明确表示，它的存储规模是nXn。综上所述，邻接矩阵存储空间和图的边数无关。

拓展：
逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵：
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

特点：
无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+…+(n-1)=n(n-1)/2个单元。
无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。

计算机网络

2 假设在没有发生拥塞的情况下，在一条往返时间RTT为10ms的线路上采用慢启动拥塞控制策略。如果接收窗口的大小为24KB，最大报文段MSS为2KB。那么，需要______ms发送方才能发送第一个完全窗口。

A. 30

B. 40

C. 50

D. 60
1
2
3
4
5
6
7

答案：B

解析：“慢启动”是TCP协议用于拥塞控制的一种策略，考虑了2个潜在的问题，即网络容量与接收端容量。为此，TCP协议要求每个发送端维护2个窗口，即反映接收端当前接收能力的通知窗口与反映当前网络容量的拥塞窗口，两个窗口中的较小值为发送端的发送窗口。“慢启动”策略的具体做法是：在连接建立时，拥塞窗口的大小值初始化为该连接所用的最大报文段的长度值，此后拥塞窗口保持指数规律即成倍增长，直到出现报文段传输超时或达到所设定的窗口门限值。在本题中，按照“慢启动”策略，发送窗口的初始值为拥塞窗口的初始值即报文段最大长度2KB，然后依次增大到4KB、8KB、16KB，然后是接收窗口的大小24KB，即达到第一个完全窗口。因此，达到第一个完全窗口所需的时间为4XRTT，即40ms。

拓展：
TCP的拥塞控制算法：慢启动、拥塞避免、快重传、快恢复详细介绍，请查看
https://blog.csdn.net/qq_40459977/article/details/123079343

操作系统

3 在设备控制器中用于实现对设备控制功能的是______ 。

A CPU

B 设备控制器与 CPU 的接口

C I/O 逻辑

D 设备控制器与设备的接口
1
2
3
4
5
6
7

答案：C

解析：大多数设备控制器由 3 部分组成：

① 设备控制器与 CPU 的接口，用于实现设备控制器与 CPU 之间的通信；

② 设备控制器与设备的接口，用于实现设备控制器与设备之间的信息交换。

③ I/O 逻辑，实现对设备的控制并通过一组控制线与 CPU 交互。

计算机组成原理

4 现有四级指令流水线，分别完成取指、取数、运算、传送结果四步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns。则流水线的操作周期应设计为______

A. 6ns

B. 8ns

C. 9ns

D. 10ns
1
2
3
4
5
6
7

答案：D
解析：如果流水线每步操作时间不一样，应选最慢的一步的操作时间作为操作周期。