当前位置：文档库 › 第七章图

第七章图

?????????

?????

?????=01

000000010010100000

010*********

Edge 第7章图

8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n -1)/2。【解答】【证明】

在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n -1

条边与其他n -1个顶点相连，总计n 个顶点有n(n -1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n -1)/2条边。

8-2 右边的有向图是强连通的吗？请列出所有的简单路径。【解答】

判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶

点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。

所谓简单路径是指该路径上没有重复的顶点。

从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A →D →B →C →F 。

从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。

从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。

从顶点E 出发，到其他各个顶点的简单路径无。从顶点F 出发，到其他各个顶点的简单路径有F →E 。

8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】

(1) 邻接矩阵

1个顶点的无向完全图

2个顶点的无向完全图

3个顶点的无向完全图 4个顶点的无向完全图

5个顶点的无向完全图

(2) 邻接表 (3) 邻接多重表（十字链表）

8-4 用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？【解答】

一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002 = 1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。

8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？【解答】

用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。

8-6 有n 个顶点的无向连通图至少有多少条边？有n 个顶点的有向强连通图至少有多少条边？试举例说明。【解答】

12345

0 1 2 3 4 5

（出边表）

（入边表）

12345data fin fout (A, B) (A, D) (B, C)

(B, E) (C, F) (D, B) (D, E) (F, E)

①

②③

④⑤或

①

②③

④⑤

①

②③

④⑤

①

②③

④⑤

n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如：

特例情况是当n = 1时，此时至少有0条边。

8-7对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？

【解答】

用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中A[i][j] 不为零，说明顶点i与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数，就可得到顶点i的度数。

8-8对于如右图所示的有向图，试写出：

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；

(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；

【解答】

(1) 以顶点①为根的深度优先生成树（不唯一）：②③④⑤⑥

(2) 以顶点②为根的广度优先生成树：

8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为void Graph::DFS ( const int v, int visited [ ], TreeNode * t ) 其中，指针t指向生成森林上具有图顶点v信息的根结点。（提示：在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。）

【解答】

为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这个算法，以建立生成森林。

te mplate void Graph :: DFS_Tree ( const int v, int visited [ ], TreeNode *t ) {

//从图的顶点v出发, 深度优先遍历图, 建立以t (已在上层算法中建立)为根的生成树。

Visited[v] = 1; int first = 1; TreeNode * p, * q;

int w = GetFirstNeighbor ( v );//取第一个邻接顶点

while ( w != -1 ) {//若邻接顶点存在

if ( vosited[w] == 0 ) { //且该邻接结点未访问过

p = new TreeNode ( GetValue (w) );//建立新的生成树结点

if ( first == 1 ) //若根*t还未链入任一子女

{ t->setFirstChild ( p );first = 0; }//新结点*p成为根*t的第一个子女

else q->setNextSibling ( p );//否则新结点*p成为*q的下一个兄弟

q = p;//指针q总指示兄弟链最后一个结点

DFS_Tree ( w, visited, q );//从*q向下建立子树

}

w = GetNextNeighbor ( v, w );//取顶点v排在邻接顶点w的下一个邻接顶点}

}

下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。

template void Graph :: DFS_Forest ( Tree& T ) {

//从图的顶点v出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林T。

T.root = NULL; int n =NumberOfVertices ( ); //顶点个数

TreeNode * p, * q;

int * visited = new int [ n ];//建立访问标记数组

for ( int v = 0; v < n; v++ ) visited[v] = 0;

for ( v = 0; v < n; v++ ) //逐个顶点检测

if ( visited[v] == 0 ) {//若尚未访问过

p = new TreeNode ( GetValue ( v ) );//建立新结点*p

if ( T.root == NULL ) T.root = p;//原来是空的生成森林, 新结点成为根

else q-> setNextSibling ( p );//否则新结点*p成为*q的下一个兄弟

q = p;

DFS_Tree ( v, visited, p );//建立以*p为根的生成树

}

8-10 用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？

【解答】

在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有的顶点访问一次，所以时间代价是O(n+e)。

8-11 右图是一个连通图，请画出

(1) 以顶点①为根的深度优先生成树；

(2) 如果有关节点，请找出所有的关节点。

(3)如果想把该连通图变成重连通图，至少在图中加几条边？如何加？

【解答】

(1) 以顶点①为根的深度优先生成树：⑩①②

③④

⑥

⑦

⑧

⑨

(2) 关节点为 ①,②,③,⑦,⑧

(3) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从③的子孙结点⑩到③的祖先结点①引一条边，从②

的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为重连通图。

8-12试证明在一个有n 个顶点的完全图中，生成树的数目至少有2n-1-1。【证明】略

8-13 编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal 求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。【解答】求解过程的第一步是对所有的边，按其权值大小建堆：

①

② ③

④ ⑤

⑥

⑩

① ②

③

④

⑥ ⑦ ⑧

⑨

⑩

① ②

③

④

⑤

⑥ ⑦

⑧

⑨

加(1, 2), (1, 3),

(2,3)

加(2, 4)

加(3, 4)

加(3, 5) 加(3, 6)

加(5, 6)

求解过程中并查集与堆的变化：

最后得到的生成树如下

完整的程序如下:

#include

template class MinHeap { public: enum { MaxHeapSize = 50 };

MinHeap ( int Maxsize = MaxHeapSize ); MinHeap ( Type Array[ ], int n ); void Insert ( const Type &ele ); void RemoveMin ( Type &Min );

void Output ();

private: void FilterDown ( int start , int end ); void FilterUp ( int end ); Type *pHeap ; int HMaxSize ;

int CurrentSize ; };

class UFSets { public:

3 1 -6 3 3 5 1 3 11 3 5 7

2 4 9

2 3 10

3 6 8 ①

② ③

④ ⑤

⑥

③ ④

选(3,4,5)

③ ④ ⑤ ⑥

选(5,6,6)

③ ④ ⑤ ⑥

选(1,2,7)

① ② ③ ④ ⑤

⑥

选(3,5,7) ① ② 1 3 11

2 4 9 2

3 10

3 6 8

③ ④ ⑤

⑥ 选(3,6,8), 在同一连通分量上, 不加 ① ② 1 3 11

2 3 10 2 4 9

③ ④ ⑤

⑥ 选(2,4,9), 结束

① ②

1 3 11

2 3 10

0 1 2 3 4 5 6

并查集的存储表示

enum { MaxUnionSize = 50 };

UFSets ( int MaxSize = MaxUnionSize );

~UFSets () { delete [ ] m_pParent; }

void Union ( int Root1, int Root2 );

int Find ( int x );

private:

int m_iSize;

int *m_pParent;

};

class Graph {

public:

enum { MaxVerticesNum = 50 };

Graph( int Vertices = 0) { CurrentVertices = Vertices; InitGraph(); } void InitGraph ();

void Kruskal ();

int GetVerticesNum () { return CurrentVertices; }

private:

int Edge[MaxVerticesNum][MaxVerticesNum];

int CurrentVertices;

};

class GraphEdge {

public:

int head, tail;

int cost;

int operator <= ( GraphEdge &ed );

};

GraphEdge :: operator <= ( GraphEdge &ed ) {

return this->cost <= ed.cost;

}

UFSets :: UFSets ( int MaxSize ) {

m_iSize = MaxSize;

m_pParent = new int[m_iSize];

for ( int i = 0; i < m_iSize; i++ ) m_pParent[i] = -1;

}

void UFSets :: Union ( int Root1, int Root2 ) {

m_pParent[Root2] = Root1;

}

int UFSets :: Find ( int x ) {

while ( m_pParent[x] >= 0 ) x = m_pParent[x];

return x;

}

template MinHeap :: MinHeap ( int Maxsize ) { HMaxSize = Maxsize;

pHeap = new Type[HMaxSize];

CurrentSize = -1;

}

template MinHeap :: MinHeap ( Type Array[], int n ) { HMaxSize = ( n < MaxHeapSize ) ? MaxHeapSize : n;

pHeap = new Type[HMaxSize];

for ( int i = 0; i < n; i++ ) pHeap[i] = Array[i];

CurrentSize = n-1;

int iPos = ( CurrentSize - 1 ) / 2;

while ( iPos >= 0 ) {

FilterDown ( iPos, CurrentSize );

iPos--;

}

template void MinHeap :: FilterDown ( int start, int end ) { int i = start, j = 2 * start + 1;

Type Temp = pHeap[i];

while ( j <= end ) {

if ( j < end && pHeap[j+1] <= pHeap[j] ) j++;

if ( Temp <= pHeap[j] ) break;

pHeap[i] = pHeap[j];

i = j; j = 2 * j + 1;

}

pHeap[i] = Temp;

}

template void MinHeap :: FilterUp ( int end ) { int i = end, j = ( end - 1 ) / 2;

Type Temp = pHeap[i];

while ( i > 0 ) {

if ( pHeap[j] <= Temp ) break;

pHeap[i] = pHeap[j];

i = j; j = ( j - 1 ) / 2;

}

pHeap[i] = Temp;

}

template void MinHeap :: Insert ( const Type &ele ) {

CurrentSize++;

if ( CurrentSize == HMaxSize ) return;

pHeap[CurrentSize] = ele;

FilterUp ( CurrentSize );

}

template void MinHeap :: RemoveMin ( Type &Min ) {

if ( CurrentSize < 0 )return;

Min = pHeap[0];

pHeap[0] = pHeap[CurrentSize--];

FilterDown ( 0, CurrentSize );

}

template void MinHeap :: Output ( ) {

for ( int i = 0; i <= CurrentSize; i++ ) cout << pHeap[i] << " ";

cout << endl;

}

void Graph :: InitGraph( ) {

Edge[0][0] = -1;Edge[0][1] = 28;Edge[0][2] = -1;Edge[0][3] = -1;Edge[0][4] = -1;Edge[0][5] = 10;

Edge[0][6] = -1;

Edge[1][1] = -1;Edge[1][2] = 16;Edge[1][3] = -1;Edge[1][4] = -1;Edge[1][5] = -1;Edge[1][6] = 14;

Edge[2][2] = -1; Edge[2][3] = 12;Edge[2][4] = -1; Edge[2][5] = -1;Edge[2][6] = -1;

Edge[3][3] = -1;Edge[3][4] = 22;Edge[3][5] = -1;Edge[3][6] = 18;

Edge[4][4] = -1;Edge[4][5] = 25; Edge[4][6] = 24;

Edge[5][5] = -1;Edge[5][6] = -1;

Edge[6][6] = -1;

for ( int i = 1; i < 6; i++ )

for ( int j = 0; j < i; j ++ ) Edge[i][j] = Edge[j][i];

}

void Graph :: Kruskal( ) {

GraphEdge e;

int VerticesNum = GetVerticesNum ( );

int i, j, count;

MinHeap heap ( VerticesNum *VerticesNum );

UFSets set ( VerticesNum );

for ( i = 0; i < VerticesNum; i++ )

for ( j = i + 1; j < VerticesNum; j++ )

if ( Edge[i][j] > 0 ) { e.head = i ; e.tail = j ; e.cost = Edge[i][j]; heap.Insert ( e );

}

count = 1;

while ( count < VerticesNum ) { heap.RemoveMin ( e ); i = set.Find ( e.head ); j = set.Find ( e.tail ); if ( i != j ) { set.Union ( i, j ); count++;

cout << "( " << e.head << ", " << e.tail << ", " <<

e.cost << " )" << endl;

}

} }

8-14 利用Dijkstra 算法的思想，设计一个求最小生成树的算法。【解答】

计算连通网络的最小生成树的Dijkstra 算法可描述如下：将连通网络中所有的边以方便的次序逐步加入到初始为空的生成树的边集合T 中。每次选择并加入一条边时，需要判断它是否会与先前加入T 的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。下面以邻接矩阵作为连通网络的存储表示，并以并查集作为判断是否出现回路的工具，分析算法的

执行过程。

①

②

⑤ ④

③

⑥ 18 14

16 26

11 9

?????

?--

----------∞∞--∞-∞∞=02601118060

199502114160Edge ① ② ③ ④ ⑤ ⑥

①

②③④⑤⑥

① ②

⑤

④

③

⑥

14 16

① ② ⑤ ⑥

并查集, 表明4个结点在同一连通分量上

①

②

⑤

④

③

⑥

①

② ⑤ ⑥

? ③ ④ ① ②

⑤

④

③

⑥ 14 16

①

② ⑤

⑥ 5

③

19 9

①

②

⑤

④

③

⑥

①

② ⑤

⑥

③ ④ 6

最终得到的最小生成树为

算法的思路如下：

① 并查集初始化：将所有顶点置为只有一个顶点的连通分量； ② 检查所有的边：

ⅰ）若边的两个端点i 与j 不在同一连通分量上(i 与j 在并查集中不同根)，则连通之(合并)； ⅱ) 若边的两个端点i 与j 在同一连通分量上(i 与j 在并查集中同根)，则

— 在并查集中寻找离i 与j 最近的共同祖先结点 — 分别从i 与j 向上检测具有最大权值的边

— 在并查集上删除具有最大权值的边，加入新的边。

下面给出实现算法：

const int MaxNum = 10000; void Graph :: Dijkstra ( ) { GraphEdge e ;

int VerticesNum = GetVerticesNum ( ); int i , j , p, q, k ;

int disJoint[VerticesNum];

//并查集

for ( i = 0; i < VerticesNum ; i++ ) disJoint[i] = -1; //并查集初始化 for ( i = 0; i < VerticesNum -1; i++ )

//检查所有的边

for ( j = i + 1; j < VerticesNum ; j++ ) if ( Edge[i][j] < MaxNum ) {

//边存在

p = i ; q = j ;

//判结点i 与j 是否在同一连通分量上

while ( disJoint[p] >= 0 ) p = disJoint[p]; while ( disJoint[q] >= 0 ) p = disJoint[q]; if ( p != q ) disJoint[j] = i ; // i 与j 不在同一连通分量上, 连通之 } else {

// i 与j 在同一连通分量上

p = i ;

//寻找离结点i 与j 最近的祖先结点

while ( disJoint[p] >= 0 ) {

//每变动一个p, 就对q 到根的路径检测一遍

q = j ;

while ( disJoint[q] >= 0 && disJoint[q] == disJoint[p] )

q = disJoint[q];

if ( disJoint[q] == disJoint[p] ) break;

else p = disJoint[p];

}

k = disJoint[p];

//结点k 是i 和j 的最近的共同祖先 p = i ; q = disJoint[p]; max = -MaxNum ; //从i 到k 找权值最大的边(s1, s2)

while ( q <= k ) { if ( Edge[q][p] > max ) { max = Edge[q][p]; s1 = p ; s2 = q ; }

p =q ; q = disJoint[p];

①

②

⑤

④

③

⑥

}

p = j;q = disJoint[p];max = -MaxNum; //从j到k找权值最大的边(t1, t2)

while ( q <= k ) {

if ( Edge[q][p] > max ) { max = Edge[q][p]; t1 = p; t2 = q; }

p =q;q = disJoint[p];

}

max = Edge[i][j];k1 = i;k2 = j;

if ( max < Edge[s1][s2] ) { max = Edge[s1][s2]; k1 = s1; k2 = s2; }

if ( max < Edge[t1][t2] ) { max = Edge[t1][t2]; k1 = t1; k2 = t2; }

if ( max != Edge[i][j] ) { //当Edge[i][j] == max时边不改

if ( disJoint[k1] == k2 ) disJoint[k1] = -1;

else disJoint[k2] = -1; //删除权值最大的边

disJoint[j] = i; //加入新的边

Edge[j][i] = - Edge[j][i];

}

8-15以右图为例，按Dijkstra算法计算得到的从顶点①(A)到其它各个顶点的最短路径和最短路径长度。【解答】

8-16 在以下假设下，重写Dijkstra算法：

(1) 用邻接表表示带权有向图G，其中每个边结点有3个域：邻接顶点vertex，边上的权值length 和边链表的链接指针link。

(2) 用集合T = V(G) - S代替S (已找到最短路径的顶点集合)，利用链表来表示集合T。

试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。

【解答】

(1)用邻接表表示的带权有向图的类定义：

const int DefaultSize = 10; //缺省顶点个数

class Graph; //图的前视类定义

struct Edge { //边的定义

friend class Graph;

int vertex; //边的另一顶点位置

float length; //边上的权值

Edge *link; //下一条边链指针

Edge ( ) { }//构造函数

Edge ( int num, float wh ) : vertex (num), length (wh), link (NULL) { }//构造函数

int operator < ( const Edge & E ) const { return length != E.length;}//判边上权值小否

}

struct Vertex { //顶点的定义

friend class Graph;

char data; //顶点的名字

Edge *adj; //边链表的头指针

}

class Graph { //图的类定义

private:

Vertex *NodeTable; //顶点表(各边链表的头结点)

int NumVertices; //当前顶点个数

int NumEdges; //当前边数

int GetVertexPos ( const Type vertex ); //给出顶点vertex在图中的位置

public:

Graph ( int sz ); //构造函数

~Graph ( ); //析构函数

int NumberOfVertices ( ) { return NumVertices;} //返回图的顶点数

int NumberOfEdges ( ) { return NumEdges;} //返回图的边数

char GetValue ( int i ) //取位置为i的顶点中的值

{ return i >= 0 && i < NumVertices ? NodeTable[i].data : … ?;}

float GetWeight ( int v1, int v2 );//返回边(v1, v2)上的权值

int GetFirstNeighbor ( int v ); //取顶点v的第一个邻接顶点

int GetNextNeighbor ( int v, int w ); //取顶点v的邻接顶点w的下一个邻接顶点

}

(2) 用集合T = V(G) - S代替S (已找到最短路径的顶点集合)，利用链表来表示集合T。

集合T用有序链表表示，数据域为顶点序号，链表T中的顶点都是未找到最短路径的顶点。另外设置一个数组S，其作用是记录已找到的顶点0到其他各顶点的最短路径path及最短路径长度len。

算法的主要思路是：

①对数组S及链表T初始化，记录顶点0到各个顶点的初始最短路径及其长度；

②扫描链表T，寻找链表T中各个顶点到顶点0的当前最短路径中长度最小者，记为u；

③在邻接表中扫描第u个顶点的出边表，确定每一边的邻接顶点号k。

若顶点k的最短路径没有选中过，比较绕过顶点u到顶点k的路径长度和原来顶点0到顶点k 的最短路径长度，取其小者作为从顶点0到顶点k的新的最短路径。

④重复执行②、③步，直到图中所有顶点的最短路径长度都已选定为止。

算法的实现如下：

const float MaxNum = 10000000;

typedef struct info {//辅助数组元素: 各顶点最短路径信息

int pre;//在最短路径上前一顶点的顶点序号

float len;//当前最短路径长度

}

info S [NumVertices];//辅助数组: 最短路径数组

List T;//未选定最短路径顶点链表

①

②

③

④

⑤

int i, k, u ; ListNode * p ; T. MakeEmpty ();

for ( i = 1; i < NumVertices ; i++ ) { S[i].pre = 0; S[i].len = MaxNum ; //辅助数组初始化 T.Locate ( i ); T.Insert( i );

//形成有序链表T

}

p = NodeTable[0].adj ; while ( p != NULL )

{ S[p ->vertex].len = p ->length ; p = p ->link ; } while (1) { T.First ();

//循环检测链表T

if ( ! T.NextNotNull( ) ) break;

//链表仅剩一个顶点, 跳出循环, 算法结束 float min = MaxNum ; u = 0; while ( T.NotNull( ) ) {

//链表不空, 还有剩余顶点未确定最短路径 i = T.GetData( );

//取剩余顶点号

if ( S[i].len < min ) { min = S[i].len ; u = i ; } //比较, 寻找最短路径长度结点u

T.next ( );

}

p = NodeTable[u].adj ; while ( p != NULL ) { //比较绕过顶点u 到其他顶点k 的路径长度

k = p ->vertex ;

//顶点k 在链表T 中表示该顶点未最终选定最短路径

if ( T.Find(k) != NULL && S[u].len + p ->length < S[k].len )

{ s[k].len = S[u].len + p ->length ; S[k].pre = u ; }

//修改

p = p ->link ;

}

T.Find(u); T.Remove();

//在链表T 中删除顶点u

}

8-17 试证明：对于一个无向图G = (V , E)，若G 中各顶点的度均大于或等于2，则G 中必有回路。【解答】

反证法：对于一个无向图G=（V ，E ），若G 中各顶点的度均大于或等于2，则G 中没有回路。此时从某一个顶点出发，应能按拓扑有序的顺序遍历图中所有顶点。但当遍历到该顶点的另一邻接顶点时，又可能回到该顶点，没有回路的假设不成立。

8-18 设有一个有向图存储在邻接表中。试设计一个算法，按深度优先搜索策略对其进行拓扑排序。并以右图为例检验你的算法的正确性。【解答】 (1) 利用题8-16定义的邻接表结构。

增加两个辅助数组和一个工作变量：

? 记录各顶点入度 int indegree[NumVertices]。 ? 记录各顶点访问顺序 int visited[NumVertices]，初始时让visited[i] = 0, i = 1, 2, , NumVertices 。

? 访问计数int count ，初始时为0。

(2) 拓扑排序算法

void Graph :: dfs ( int visited[ ], int indegree[ ], int v, int& count ) {

count++; visited[v] = count;

cout << NodeTable[v].data << endl;

Edge *p = NodeTable[v].adj;

while ( p != NULL ) {

int w = p->vertex;

indegree[w]--;

if ( visited[w] == 0 && indegree[w] == 0 ) dfs ( visited, indegree, w, count );

p = p->link;

}

主程序

int i, j; Edge *p; float w;

cin >> NumVertices;

int * visited = new int[NumVertices+1];

int * indegree = new int[NumVertices+1];

for ( i = 1; i <= NumVertices; i++ ) {

NodeTable[i].adj = NULL; cin >> NodeTable[i].data; cout << endl;

visited[i] = 0; indegree[i] = 0;

}

int count = 0;

cin >> i >> j >> w; cout << endl;

while ( i != 0 && j != 0 ) {

p = new Edge ( j, w );

if ( p == NULL ) { cout << “存储分配失败！” << endl; exit(1); }

indegree[j]++;

p->link = NodeTable[i].adj;NodeTable[i].adj = p;

NumEdges++;

cin >> i >> j >> w; cout << endl;

}

for (i = 1; i <= NumVertices; i++ )

if ( visited[i] == 0 && indegree[i] == 0 )dfs ( visited, indegree, i, count );

if (count < NumVertices ) cout<< “排序失败!” << endl;

else cout<< “排序成功!” << endl;

delete [ ] visited; delete [ ] indegree;

8-19试对右图所示的AOE网络，解答下列问

题。

(1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间Ve[i]和最

迟开始时间Vl[i]。

(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。

(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提

前完成。

【解答】

按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。

此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>

8-20 若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。

(1) 如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥，将把图分割成两个连通分量。

(2) 编写一个时间复杂度为O(n+e)的使用邻接表表示的算法，判断连通图G中是否有桥，若有。输出这样的桥。

【解答】

(1) 反证法（略）

(2)借助于求重连通分量的算法。如果一条边的两个端点满足下列条件之一，即为桥：

①两个端点都是关节点；

②一个端点是关节点，另一端点是整个图的开始点；

③一个端点是关节点，另一端点是整个图的完成点。

数据结构第七章图练习及答案

1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。【解析】解题关键是弄清拓扑排序的步骤（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下（1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立 e(i)=ve(j) l(i)=vl(k)-dut() （4）找出e(i)-l(i)=0的活动既是关键活动。【答案】

关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）

第7章图习题及答案

第7章图一、选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（） A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B 3．连通分量指的是（） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图【答案】B 4．n个结点的完全有向图含有边的数目（） A）n*n B）n（n+1）C）n/2 D）n*（n-1）【答案】D 5．关键路径是（） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径【答案】A 6．有向图中一个顶点的度是该顶点的（） A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（）边结点。 A） e B） 2e C） e-1 D） 2(e-1)

【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（） A）栈 B）队列 C）二叉树 D）树【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（） A）栈 B）队列 C）二叉树 D）树【答案】A 10．存储无向图的邻接矩阵一定是一个（） A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A） O(n) B） O(n+e) C） O(n2) D） O(n3) 【答案】B 13．下列关于AOE网的叙述中，不正确的是（） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B 14．具有10个顶点的无向图至少有多少条边才能保证连通（） A） 9 B）10 C） 11 D） 12 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A） e B）2e C） n2-e D）n2-2e 【答案】D 16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表

第七章图

第七章图一、选择题 1．图中有关路径的定义是（ A ） A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ B ）条边。】 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（ D ）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A)。 A．5 B．6 C．8 D．9 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A )。 A．逆拓扑有序 B．拓扑有序 C．无序的 10．下面结构中最适于表示稀疏无向图的是（ C ），适于表示稀疏有向图的是（ BDE ）。 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 11．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网 12．从邻接阵矩可以看出，该图共有（B）个顶点；如果是有向图该图共有（B）条弧；如果是无向图，则共有（D）条边。 ①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（ C ）的第i行第j列的元素是否为零即可。 A．mA B．A C．A m D．Am-1 15.下列说法不正确的是（ C ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ D ） a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A．5个 B．4个 C．3个 D．2个 18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(C)，而进行广度优先遍历得到的顶点序列是（C）。 ①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确 ②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确 19．下面哪一方法可以判断出一个有向图是否有环（AB）： A．深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 20.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为( B )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 21.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ C），下面步骤重复n-1次: a：（ A）；b：（ B）；最后：（A）。（1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边（2）．A.选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大

图形设计试题及答案

计算机图形学试题及答案完整版一、名词解释将图形描述转换成用像素矩阵表示的过程称为扫描转换。 1.图形: 。 2.像素图: 。 3.参数图: 。 4.扫描线: 。 5.构造实体几何表示法: 。 6.投影: 。 7.参数向量方程: 。 8.自由曲线: 。 9.曲线拟合: 。 10.曲线插值: 。 11.区域填充: 。 12.扫描转换: 。二、填空 1.图形软件的建立方法包括提供图形程序包、与采用专用高级语言。 2.直线的属性包括线型、与颜色。 3.颜色通常用红、绿与蓝三原色的含量来表示。对于不具有彩色功能的显示系统,颜色显示为。 4.平面图形在内存中有两种表示方法,即与矢量表示法。 5.字符作为图形有与矢量字符之分。

6.区域的表示有与边界表示两种形式。 7.区域的内点表示法枚举区域内的所有像素,通过来实现内点表示。 8.区域的边界表示法枚举区域边界上的所有像素,通过给赋予同一属性值来实现边界表示。 9.区域填充有与扫描转换填充。 10.区域填充属性包括填充式样、与填充图案。 11.对于图形,通常就是以点变换为基础,把图形的一系列顶点作几何变换后,连接新的顶点序列即可产生新的变换后的图形。 12.裁剪的基本目的就是判断图形元素就是否部分或全部落在之内。 13.字符裁剪方法包括、单个字符裁剪与字符串裁剪。 14.图形变换就是指将图形的几何信息经过产生新的图形。 15.从平面上点的齐次坐标,经齐次坐标变换,最后转换为平面上点的坐标,这一变换过程称为。 16.实体的表面具有、有界性、非自交性与闭合性。 17.集合的内点就是集合中的点,在该点的内的所有点都就是集合中的元素。 18.空间一点的任意邻域内既有集合中的点,又有集合外的点,则称该点为集合的。 19.内点组成的集合称为集合的。 20.边界点组成的集合称为集合的。 21.任意一个实体可以表示为的并集。 22.集合与它的边界的并集称集合的。

天正建筑绘制立面图

第13章天正建筑绘制立面图【学习提示】设计好一套工程的各层平面图后，需要绘制立面图表达建筑物的立面设计细节，立剖面的图形表达和平面图有很大的区别，立剖面表现的是建筑三维模型的一个投影视图，受三维模型细节和视线方向建筑物遮挡的影响，天正立面图形是通过平面图构件中的三维信息进行消隐获得的纯粹二维图形，除了符号与尺寸标注对象以及门窗阳台图块是天正自定义对象外，其他图形构成元素都是AutoCAD 的基本对象。【本章重点】天正建筑绘制立面图的思路和方法。【作图步骤】建筑立面图的绘制一般步骤如下：（1）创建楼层表（2）生成立面图（3）修改深化立面图（4）立面标注（5）立面填充 13.1 创建楼层表由于楼层表在上一章已经学习并创建好了，所以这里就直接打开楼层表面板，检查相应楼层的“层高”或者“文件”等是否有误。由于在生成立面过程中，需要制定出现在立面图中的轴线，所以先打开任意一个平面图，这里打开“首层平面图”。 13.2 生成立面图建立了楼层表后，如果在“楼层”面板中单击按钮，或者执行【SWZH 】命令，就可以根据弹出的“楼层组合”对话框进行相应设置后，生成三维模型。本例不需要创建三维模型，只需要生成相应的立面和剖面即可。单击“楼层”面板中单击按钮，或者执行【JZLM 】命令，根据命令提示行的要求进行如下操作：命令: TBudElev 请输入立面方向或 [正立面(F)/背立面(B)/左立面(L)/右立面(R)]<退出>: B （输入B ）请选择要出现在立面图上的轴线:找到1 个（点击轴线11）请选择要出现在立面图上的轴线:找到 1 个，总计2个（点击轴线1）提示：一般是选择同立面方向上的开间或进深轴线，选轴号无效。

第七章图

第七章图一、选择题 1．图中有关路径的定义是（）。 A ．由顶点和相邻顶点序偶构成的边所形成的序列 B ．由不同顶点所形成的序列 C ．由不同边所形成的序列 D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 E ．n 2 3．一个n 个顶点的连通无向图，其边的个数至少为（）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（）条边。 A ．n-l B ．n C ．n+l D ．2n 5．n 个结点的完全有向图含有边的数目（）。【中山大学 1998 二、9 （2分）】 A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学 2001 二、3 （2分）】 A ．1/2 B ．2 C ．1 D ．4 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 11．下列哪一种图的邻接矩阵是对称矩阵？（） A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12．从邻接矩阵 ????? ?????=01 101 010A 可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 13．当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（）。【南京理工大学1998一、4(2分）】 A ． ∑=n i j i A 1 ] ,[ B ． [] ∑=n 1 j j ,i A C ． ∑=n i i j A 1 ] ,[ D ． ∑=n i j i A 1 ],[+ [] ∑=n 1 j i ,j A 14．用相邻矩阵A 表示图，判定任意两个顶点Vi 和Vj 之间是否有长度为m 的路径相连，则只要检查（）的第i 行第j 列的元素是否为零即可。 A ．mA B ．A C ．A m D ．Am-1 15. 下列说法不正确的是（）。 A ．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C ．图的深度遍历不适用于有向图 B ．遍历的基本算法有两种：深度遍历和广度遍历 D ．图的深度遍历是一个递归过程 16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),

图习题及标准答案

————————————————————————————————作者：————————————————————————————————日期：

第7章图单元测试(答案)

第七章图姓名：学号：一、选择题 1．设无向简单图的顶点个数为n ，则该图最多有（ B ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．n 2 2．一个n 个顶点的连通无向图，其边的个数至少为（ A ）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； 3．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A ．1/2 B ．2 C ．1 D ．4 4．下列哪一种图的邻接矩阵是对称矩阵？（） A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 5．下列有关图的遍历的说法中，不正确的是（）。 A ．用邻接表存储的图的深度优先搜索的时间复杂度为O(n ＋e) B ．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征，需要采用队列结构来实现 C ．非连通图不能用深度优先搜索法 D ．图的遍历要求每一顶点访问且仅被防问一次 6. 求解最短路径的Floyd 算法的时间复杂度为( )。 A ．O （n ） B. O （n+c ） C. O （n 2） D. O （n 3） 7. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A. O(n) B. O(n ＋e) C. O （n 2） D. O （n 3） 8.右图所示的无向网的最小生成树的权为( )。 A ．11 B ． 9 C ．14 D ．12 9. 关键路径是AOE 网中（）。 A ．从源点到汇点的最长路径 B ．从源点到汇点的最短路径 C ．最长回路 D ．最短回路 10．下列关于AOE 网的叙述中，不正确的是（）。 A ．关键活动不按期完成就会影响整个工程的完成时间 B ．任何一个关键活动提前完成，那么整个工程将会提前完成 C ．所有的关键活动提前完成，那么整个工程将会提前完成 D ．某些关键活动提前完成，那么整个工程将会提前完成二、判断题 1. 有e 条边的无向图，在邻接表中有e 个结点。（ × ） 2. 强连通图的各顶点间均可达。（ √ ） 42

数据结构第7章图习题

第7章图一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量

电气识图全套试题及答案

《电气识图》一、判断题 1．图纸是表示信息的一种技术文件，必须有一定的格式和共同遵守的规定。（√） 2．A1号电气平面图的幅面尺寸为420×594。（×） 3．标题栏（又名图标）的格式，在我国有统一的格式。（×） 4．在电气平面图中点划线可表示为信号线或控制线。 (√) 5．弱电平面图中—H 2—表示二根电话线。（×） 6．在电气平面图中O ?O ?O ＋＋＋＋是表示接地装置。（×） 7．建筑物垂直方向的定位轴线标号应选用拉丁字母由上往下注写.。（×） 8．室内开关的安装高度一般选用绝对标高表示。（×） 9．图形符号的方位可根据图面布置的需要旋转或成鏡像放置。（√） 10．GB7159中基本文字符号不得超过三个字母。（×） 11．建筑电气工程图是用投影法绘制的图。（×） 12．电气系统图表示了电气元件的连接关系和接线方式。（×） 13．电气工程图是表示信息的一种技术文件，各设计院都有自己的格式和规定。（×） 14．电气设备器件的种类代号可由字母和数字组成，其字母是选用26个拉丁字母。（×） 15．电气工程图的幅面尺寸分六类，为A0~A5。（×） 16．辅助文字符号不能超过三个字母，其中I 、O 、J 不用。（×） 17．电气平面图是采用位置布局法来绘制的。（√） 18．电气系统图即能用功能布局法绘制，又可用位置布局法绘出。（√） 19．电气平面图中电气设备和线路都是按比例绘出的。（×） 20．TN －S 系统中工作零线和保护零线共用一根导线。（×） 21．SCB －1250－10/表示三相干式电力变压器器，1250KVA ，一次绕组电压为 10KV ，二次绕组电压为。（√） 22．对一次设备进行监视，测量，保护与控制的设备称为二次设备。（√） 23．TMY-4(100×10)表示为硬铜母线，4根，宽为100mm ，厚度为10mm 。（√）

第7章图练习题及答案

第七章图一、单选题（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的倍。 A ．1/2 B. 1 C. 2 D. 4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有条边。 A ．14 B. 28 C. 56 D. 112 （ A ）一个n 个顶点的连通无向图，其边的个数至少为（）。 A ．n-1 B ．n C ．n+1 D ．nlogn ；（ C ）5. 有8个结点的有向完全图有条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A ．栈 B. 队列 C. 树 D. 图（ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 8. 下面关于求关键路径的说法不正确的是（ C ）。 A ．求关键路径是以拓扑排序为基础的 B ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C ．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D ．关键活动一定位于关键路径上 9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是（ D ） A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 ?????????? ????????????01000111011000 01011010110011 001000110010011011110

PS考试试题及答案

Photoshop试题及答案（一）一、填空题 1.在Photoshop中一个文件最终需要印刷，其分辨率应设置在_________像素/英寸，图像色彩方式为_________；一个文件最终需要在网络上观看，其分辨率应设置在_________像素/英寸，图像色彩方式为_________。 2.选择工具配合_________键盘按键可进行选择裁切，配合_________键盘按键可进行选择复制。 3.在Photoshop中文字工具包含：_________、_________，其中在创建文字的同时创建一个新图层的是_________。 4.在使用色阶命令调整图像时，选择_________通道是调整图像的明暗，选择_________通道是调整图像的色彩。例如一个RGB图像在选择_________通道时可以通过调整增加图像中的黄色。 5.Photoshop 6.0新增工具形状工具可以以三种的类型出现：_________、_________、_________。 6.Photoshop图像新建对话框中包含以下五种色彩模式：_________、_________、_________、_________、_________。二、选择题

1.以下命令中可以选择像素的是（）。 A) 套索工具 B) 魔棒工具 C) 色彩范围 D) 羽化 2.以下键盘快捷方式中可以改变图像大小的是（）。 A) Ctrl+T B) Ctrl+Alt C) Ctrl+S D) Ctrl+V 3.在Photoshop中可以改变图像色彩的命令是：（）。 A) 曲线调整 B) 颜色分配表 C) 变化调整 D) 色彩范围 4.在编辑一个渐变色彩时，可以被编辑的部分是（）。 A) 前景色 B) 位置 C) 色彩 D) 不透明度 5.路径工具的作用主要有（）。 A) 改变路径内图像的形状 B) 在路径中填充色彩 C) 将路径转为选择区域 D) 使着色工具沿着路径画线 6.下列不支持无损压缩的文件格式是( )。 A) PNG B) JPEG C) TIFF D) PSD

数据结构第7章图习题

习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ②A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。 ①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b C. a,e,b,c,f,d D. a,c,f,d,e,b 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。

第7章图(2)

第七章图一、选择题 1．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的【中科院软件所1998】 2．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 3. 求解最短路径的Floyd算法的时间复杂度为( )。【合肥工业大学 1999 一、2 （2分）】 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 4．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={,,,,,,,,},G的拓扑序列是（）。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 【北京航空航天大学 2000 一、7 （2分）】 5．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。 A．存在 B．不存在【中科院计算所1998 二、6 (2分）】【中国科技大学 1998二、6（2分）】 6．一个有向无环图的拓扑排序序列（）是唯一的。【北京邮电大学 2001 一、3 （2分）】A．一定 B．不一定 7. 关键路径是事件结点网络中（）。【西安电子科技大学 2001应用一、4 （2分）】 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 8．下列关于AOE网的叙述中，不正确的是（）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成【北方交通大学 1999 一、7 （3分）】【北京工业大学 1999 一、1 (2分)】二、判断题 1．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学1998 一、13】 2. 关键路径是AOE网中从源点到终点的最长路径。（）【青岛大学 2000 四、10（1分）】

图的答案

7.1选择题 1．设无向图的顶点个数为n，则该图最多有（）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 【答案】B 2．连通分量指的是（） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图【答案】B 3．n个结点的完全有向图含有边的数目（） A）n*n B）n（n+1）C）n/2 D）n*（n-1）【答案】D 4．有e条边的无向图，若用邻接表存储，表中有（）边结点。 A）e B）2e C）e-1 D）2(e-1) 【答案】B 5．存储无向图的邻接矩阵一定是一个（） A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵【答案】C 6．具有10个顶点的无向图至少有多少条边才能保证连通（） A）9 B）10 C）11 D）12 【答案】A 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。

【答案】（1）n （2）n-1 8．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。【答案】（1）O(n2) （2）O(n2) 7.3判断题 1．图是一种非线性结构，所以只能用链式存储。（）【答案】× 2．图的最小生成树是唯一的。（）【答案】× 3．如果一个图有n个顶点和小于n-1 条边，则一定是非连通图。（）【答案】√ 4．有n-1 条边的图一定是生成树。（）【答案】× 5．用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。（）【答案】√ 6．任意一个图都是其自身的子图。（）【答案】√ 7.4应用题 1．设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={, , , , , , }，请画出该有向图并判断是否是强连通图。分析：作该题的关键是弄清楚以下两点（1）边集E中表示一条以vi为弧尾，vj为弧头的有向弧。（2）强连通图是任意两顶点间都存在路径的有向图。【答案】该有向图是强连通图，表示如下：

机械识图试题库及答案

-------------------------------------密-----------------------封-----------------------线班级___________ 考场__________ 姓名______________ 学号_________ 《机械识图》一、填空题： 1.视图包括基本视图、向视图、局部视图、斜视图 4种。（难度：A ） 2.物体向基本投影面投射所得的视图称为基本视图。（难度：A ） 3.按正投影法分别向六个基本投影面投影，可得到主视图、俯视图、左视图、右视图、仰视图、后视图六个基本视图。（难度：A ） 4.主、俯、仰、后视图，长度相等；主、左、右、后视图，高度相等；左、俯、右、仰视图，宽度相等。（难度：A ） 5.将物体的某一部分向基本投影面投射所得的视图称为局部视图。（难度：A ） 6.物体向不平行于任何基本投影面的平面投射所得的视图称为斜视图，必要时，允许将斜视图旋转配置。（难度：A ） 7．画剖视图时，不要漏画剖切面后面的可见轮廓线。（难度：A ） 8.向视图是可以自由配置的视图。向视图通常用箭头指明投射方向。（难度：A ） 9.为了在剖视图中容易分辨出机件内部的实心部分和空心部分，在剖切面剖到的实心处应画剖面符号，而孔等空心处不画，剖面线应与机件的主要轮廓或剖面区域的对称线成45度角。（难度：A ） 10.按物体被剖切范围的大小可将剖视图分为全剖视图、半剖视图和局部剖视图3种。（难度：A ） 11．将机件的部分结构用大于原图形所采用的比例画出的图形称为局部放大图。（难度：A ） 12．用两个相交的剖切面剖开机件绘图时，应先旋转后投影。（难度：A ） 13. 半剖视图中，半个视图与半个剖视图的分界线用细点划线。（难度：A ） 14. 假想用剖切面剖开机件，将处在观察者与剖切面之间的部分移去，而将其余部分向投影面投影所得到的图形称为剖视图。（难度：A ） 15.需要保留部分外形又要表达内形的不对称机件，采用局部剖视图。（难度：A ） 16. 移出断面图是画在视图之外的断面图，移出断面图的轮廓线用粗实线绘制。（难度：A ） 17. 用剖切平面局部地剖开机件所得到的剖视图称为局部剖视图。（难度：A ） 18.机械零件的常用表达方法有视图、剖视图、断面图、局部放大图及其它规定画法。（难度：A ） 19. 局部视图是将机件的局部内形向基本投影面投影所得的视图。（难度：A ） 20. 重合断面图是画在视图之内的断面图，重合断面图的轮廓线用细实线线画出。（难度：A ） 21. 六个基本视图中，仰视图与俯视图同样反映物体长、宽方向的尺寸；右视图与左视图同样反映物体高、宽方向的尺寸；后视图与主视图同样反映物体长、高方向的尺寸。（难度：A ） 22. 局部剖视图中，视图与剖视图的分界线用波浪线线，也可以用双折线线。（难度：A ） 23. 机件的内部形状已经在半剖视图中表达清楚，在另一半表达外形的视图中不必再画出细虚线。（难度：A ） 24. 剖视图标注的三要素是剖切符号、剖切线、字母。（难度：A ） 25. 剖视图只是假想地剖开机件，用以表达机件内部形状的一种方法，实际机件是完整的，因此除剖视图外的其它图形，都按完整的形状画出。（难度：A ） 26. 机件上的某些细小结构在视图中表达不清晰，或不便于标注尺寸时，采用局部放大图。 27. 局部放大图的比例数值是放大图与实际物体的比例，而不是对原图的比例。（难度：A ） 28. 对于机件的肋、轮辐及薄壁等，如按纵向剖切，这些结构都不画剖面符号，而用粗实线将它与其邻接部分分开。（难度：A ） 29.根据断面图在图中配置的图中，可分为移出断面和重合断面。（难度：A ） 30.画在视图之外的断面图称为移出断面，画在视图之内的断面图称为重合断面。（难度：A ） 31．螺纹按用途可分为四类，其中用来连接零件的螺纹为连接螺纹；用来传递动力和运动的螺纹为传动螺纹。（难度：A ） 32. 以剖视图表示内、外螺纹连接时，其旋合部分应按外螺纹的画法绘制。（难度：A ） 33. 左旋螺纹要注写 LH ,右旋螺纹不注。（难度：A ） 34.不通螺孔圆锥面尖端的锥顶角一般画成 120 度。（难度：A ） 35.螺纹相邻两牙在中径线上对应两点间的轴向距离称为螺距。（难度：A ） 36.啮合的圆柱齿轮的剖视图中，当剖切平面通过两啮合齿轮轴线时，在啮合区内，将一个齿轮的轮齿用粗实线绘制，另一个齿轮的轮齿被遮挡的部分用虚线线绘制。（难度：A ）

第七章∶图练习题

第七章：图练习题一、选择题 1、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（）条边。 A、6 B、12 C、16 D、20 5、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点 A、6 B、7 C、8 D、9 6、存储稀疏图的数据结构常用的是（）。 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。 A、n B、(n-1)2 C、(n+1)2 D、n2 8、设连通图G的顶点数为n，则G的生成树的边数为（）。 A、n-1 B、n C、2n D、2n-1 9、n个顶点的无向图的邻接表中结点总数最多有（）个。 A、2n B、n C、n/2 D、n(n-1) 10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。 A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数 12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（）（1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2

第七章 图

数据结构第七章图练习及答案

第7章 图习题及答案

第七章 图

图形设计试题及答案

天正建筑绘制立面图

第七章 图

图习题及标准答案

第7章 图单元测试(答案)

数据结构第7章 图习题

电气识图全套试题及答案

第7章 图练习题及答案

PS考试试题及答案

数据结构第7章 图习题

第7章 图(2)

图的答案

机械识图试题库及答案

第七章∶图练习题

第七章图

第7章图习题及答案

第七章图

第七章图

第7章图单元测试(答案)

数据结构第7章图习题

第7章图练习题及答案

数据结构第7章图习题

第7章图(2)