设A为有向图的邻接矩阵，定义：。试证明：矩阵A”的第i行第j列元素的值等于从顶点i到j的长度为n的

设为简单有向图G的邻接矩阵,证明A³的对角线元素表示经过结点v1的“三角形”的个数,即以v为一个结点的G的子图k₃的个数.

设图G是一个有向图，设顶点值为字符型，边上权值为浮点型，其十字链表的存储表示定义如下：（1)实

设图G是一个有向图，设顶点值为字符型，边上权值为浮点型，其十字链表的存储表示定义如下：

(1)实现图的构造函数Graphmu1.输人-系列顶点和边，建立带权有向图的十字链表。

(2)编写一个算法，基丁图G的十字链表表示求该图的强连通分量，试分析算法的时间复杂度。

(3)以图846为例，画出它的十字链表，第一次深度优先搜索得到的finished数组及最后得到的强连通分量。

对于邻接矩阵A的简单有向图G,它的距离矩阵定义如下:

确定由图7-14所示的有向图的距离矩阵,并指出dij=1是什么意义？

个表示有向图的邻接矩阵中非零元素都集中在下三角部分，其逆拓扑有序序列一定存在;反之，如果一个有向图的拓扑有序序列存在，在其邻接矩阵中非零元素不一定集中在上三角部分。试说明理由并举例.

在有向图中的一个欧拉画路（Eulercircuit)是这样的一个环：其上的每一条边被访问一次且仅被访问

一次。

(l)试证明一个有向图存在欧拉回路的充要条件是该图必须是强连通的且每一个顶点有相同的人度与出度;

(2)设图中的顶点数为n，试描述有向图的数据结构并编写一个时间复杂性为O(n)的算法，在有向图中查找一条欧拉回路(如果它存在).

设图有n个顶点和e条边，采用邻接矩阵时，遍历图时的顶点所需时间为（①)，采用邻接表时遍历图的顶点所需时间为（②)，

A、O(n)

B、O(n²)

C、O(e)

D、O(n×e)

电路如图题3.4.6所示，设运放是理想的，二极管的导通压降为0.7V。（1)试证明，即该电路为绝对值运算

电路。

(2)v_N是振幅为2V的正弦波时，绘出v_N和v₀的波形，并标出幅值。(3)v_N为正弦波时，v₀的波形与图题3.4.3的v_L波形相同，但与图题3.4.3电路相比，本题电路有什么优缺点？

对于一个无向图（a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶

点序列和按广度优先搜索遍历得到的顶点序列。

的最短路径。