第七章 图

一、选择题

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 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。

A ．n-l

B ．n

C ．n+l

D ．2n 5．n 个结点的完全有向图含有边的数目（ ）。

A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0

B ．1

C ．n-1

D ．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

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

010

A 可以看出，该图共有（①）个顶点；如果是有向图

该图共有（②） 条弧；如果是无向图，则共有（③）条边。

①．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 的度是（ ）。

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),(e,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个序列中，符合深度优先遍历的序列有多少？（ ）

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个

第17题图 第

18题图 18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。

①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确

②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确

19．下面哪一方法可以判断出一个有向图是否有环（回路）：

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

A. O(n)

B. O(n+e)

C. O(n2)

D. O(n3)

22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；

(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ；（图用邻接矩阵表示）

(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。

上面不正确的是（）。

A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) 23．当各边上的权值( )时，BFS算法可用来解决单源最短路径问题。

A．均相等 B．均互不相等 C．不一定相等

24. 求解最短路径的Floyd算法的时间复杂度为( )。

A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）

25．已知有向图G=(V,E)，其中V={V

1,V

2

,V

3

,V

4

,V

5

,V

6

,V

7

}，

E={

1,V

2

>,

1

,V

3

>,

1

,V

4

>,

2

,V

5

>,

3

,V

5

>,

3

,V

6

>,

4

,V

6

>,

5

,V

7

>,

6

,V

7

>},G

的拓扑序列是（）。

A．V

1,V

3

,V

4

,V

6

,V

2

,V

5

,V

7

B．V

1

,V

3

,V

2

,V

6

,V

4

,V

5

,V

7

C．V

1,V

3

,V

4

,V

5

,V

2

,V

6

,V

7

D．V

1

,V

2

,V

5

,V

3

,V

4

,V

6

,V

7

27．一个有向无环图的拓扑排序序列（）是唯一的。

A．一定 B．不一定

28. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出

现的是（）。

A．G中有弧 B．G中有一条从Vi到Vj的路径

C．G中没有弧 D．G中有一条从Vj到Vi的路径

29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

A. O(n)

B. O(n＋e)

C. O(n*n)

D. O(n*n*n)

30. 关键路径是事件结点网络中（）。

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径

C．最长回路 D．最短回路

31. 下面关于求关键路径的说法不正确的是（）。

A．求关键路径是以拓扑排序为基础的

B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D．关键活动一定位于关键路径上

32．下列关于AOE网的叙述中，不正确的是（）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动提前完成，那么整个工程将会提前完成

三、填空题

3．一个连通图的______是一个极小连通子图。

7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。

8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。

10．设G为具有N个顶点的无向连通图，则G中至少有______条边。

12．如果含n个顶点的图形形成一个环，则它有______棵生成树。

17．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。

20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。【青岛大学 2002 三、8 （2分）】

21. 遍历图的过程实质上是______，breath-first search遍历图的时间复杂度(以邻接表为存储结构)____ __；depth-first search遍历图的时间复杂度

______，两者不同之处在于______，反映在数据结构上的差别是______。

23. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。

24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2分）】25. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。

28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。【厦门大学 1999 一、4】30．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______，利用Kruskal算法生成最小代价生成树其时间复杂度为______。

31．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V1，V2，．．．，Vn，用相邻矩阵A表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）．若（Vi，Vj）是边，则A（i，j）的值等于______，若（Vi，Vj）不是边，则A（i，j）的值是一个比任何边的权______，矩阵的对角线元素全为0。（2）．构造最小生成树过程中，若节点Vi已包括进生成树，就把相邻矩阵的对角线元素A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵

元素A（i，j）置成______。

（3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。【山东工业大学1998二、4(6分）】

32. 有一个用于n个顶点连通带权无向图的算法描述如下：

（1）．设集合T1与T2，初始均为空；

（2）．在连通图上任选一点加入T1；

（3）．以下步骤重复n-1次：

a.在i属于T1，j不属于T1的边中选最小权的边；

b.该边加入T2。

上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。

33. 有向图G可拓扑排序的判别条件是______。34. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。

35. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。36．求最短路径的Dijkstra算法的时间复杂度为______。

37.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权 d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。38. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。39．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为______。40．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。

41．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。42．在 AOV网中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。

43. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。

（1）．查邻接表中入度为______的顶点，并进栈；

（2）．若栈不空，则①输出栈顶元素Vj ，并退栈；②查Vj 的直接后继Vk ，对Vk 入度处理，处理方法是______；

（3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。

第7章 图 一.选择题

二.判断题

部分答案解释如下。

2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵 14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值

21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上权值之和相等 26. 是自由树，即根结点不确定

35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。

42. AOV 网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。 45. 能求出关键路径的AOE 网一定是有向无环图

46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。 48．按着定义，AOE 网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

三．填空题

1.有n 个顶点，n-1条边的无向连通图

2.有向图的极大强连通子图

3. 生成树

4. 45

5. n(n-1)/2 6 . 7. 9 8. n

9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N 16. 3 17. 2（N-1） 18. 度 出度 19. 第I 列非零元素个数 20.n 2e

21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈 22. 深度优先 23.宽度优先遍历 24.队列

25.因未给出存储结构，答案不唯一。本题按邻接表存储结构，邻接点按字典序排列。

25题（1） 25题（2）

26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 27.克鲁斯卡尔

28.边稠密边稀疏 29. O(eloge）边稀疏 30.O(n2） O(eloge)

31.(1）（V i，V j）边上的权值都大的数（2）1 负值（3）为负边

32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增负值 35.160 36.O(n2） 37. 50，经过中间顶点④ 38. 75 39.O(n+e）

40.(1）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间

41.关键路径 42.（1）某项活动以自己为先决条件（2）荒谬（3）死循环

43.（1）零（2）V k度减1，若V k入度己减到零，则V k顶点入栈（3）环

44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc

45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout

(6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j

(11)firstadj(g,v0) (12)not visited[w] (13)nextadj(g,v0,w)

46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1 (8)indegree[i]==0

47.(1)p^.link:=ch[u].head (2)ch[u].head:=p (3)top<>0 (4)j:=top (5)top:=ch[j].count

(6)t:=t^.link

48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一

的。本答案是按邻接点升序排列给出的。)

（2）①top==-1 ②top=graph[j].count ③graph[k].count==0

四.应用题

1．（1）G1最多n(n-1)/2条边，最少n-1条边 (2) G2最多n(n-1)条边，最少n条边

(3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的) 2．n-1，n 3.分块对称矩阵

4．证明：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若

边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回

路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。

5．证明：该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并

回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均

大于弧头顶点的编号，在邻接矩阵中，非零元素（A[i][j]=1）自然是落到下三角矩阵中；命题的必要条件

是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类

有向无环图顶点编号，应按顶点出度顺序编号。）

6．设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。

7．（1）n(n-1)， n

(2) 106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）

（3）使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)

未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。

8．

（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。（3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7

2，K1，K3，K4，K5，K6，K8，K9，K7

规则：开始结点为K1或K2，之后，若遇多个入度为0的

顶点，按顶点编号顺序选择。

（4）

8（4）邻接表和逆邻接表

9．（1）注：邻接矩阵下标按字母升序:abcdefghi

（2）强连通分量：（a），(d)，（h），

(b，e，i，f，c，g）

(3 ) 顶点a到顶点i的简单路径：

（a→b→e→i），(a→c→g→i)，

(a→c→b→e→i)

10．图G的具体存储结构略。

邻接矩阵表示法，有n个顶点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。

邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。

十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。

邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。

边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。

11．

已知顶点i ，找与i 相邻的顶点j 的规则如下：在顶点向量中，找到顶点i ，顺其指针找到第一个边结点（若其指针为空，则顶点i 无邻接点）。在边结点中，取出两顶点信息，若其中有j ，则找到顶点j ；否则，沿从i 发出的另一条边的指针（ilink ）找i 的下一邻接点。在这种查找过程中，若边结点中有j ，则查找成功；若最后ilink 为空，，则顶点i 无邻接点j 。

12．按各顶点的出度进行排序。n 个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n 。之后，进行调整，即若存在弧，而顶点j 的出度大于顶点i 的出度，则将把j 编号在顶点i 的编号之前。本题算法见下面算法设计第28题。 13．采用深度优先遍历算法，在执行dfs(v)时，若在退出dfs(v)前，碰到某顶点u ，其邻接点是已经访问的顶点v ，则说明v 的子孙u 有到v 的回边，即说明有环，否则，无环。（详见下面算法题13） 14．深度优先遍历序列：125967384

宽度优先遍历序列：123456789

注：（1）邻接表不唯一，这里顶点的邻接点按升序排列 （2）在邻接表确定后，深度优先和宽度优先遍历序列唯一 （3）这里的遍历，均从顶点1开始

15．（1）V 1V 2V 4V 3V 5V 6 （2）V 1V 2V 3V 4V 5V 6 16.(1)

16题（3）宽度优先生成树

（2）深度优先生成树

为节省篇幅，生成树横画，下同。

17．设从顶点1开始遍历，则深度优先生成树(1)和宽度优先生成树(2)为：

图17(1) 图

18．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。 19．（1）邻接矩阵：（6*6个元素）*2字节/元素=72字节

邻接表：表头向量6*（4+2）+边结点9*(2+2+4)*2=180字节

邻接多重表：表头向量6*

（4+2）+边结点9*（2+2+2+4+4）=162字节

邻接表占用空间较多，因为边较多，边结点又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。 （2）因未确定存储结构，从顶点1开始的DFS 树

不唯一，现列出两个： 20．未确定存储结构，其DFS 树不唯一，其中之一（按邻接点逆序排列）是 （2）关节点有3，1，8，7，2

21．（1）

（2）AFEDBC

22．设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1）

（1） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （2） 深度优先搜索序列：V1V2V4V8V5V3V6V7

23．（1）略 （2）V1V2V5V3V4V6 (4) V1V2V3V4V5V6

(6）见本章五算法设计第6题

24．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列 (1)ABGFDEC (2)EACFBDG (3)

(5)

25．在有相同权值边时生成不同的MST ，在这种情况下，用Prim 或Kruskal 也会生成不同的MST 。 26．无向连通图的生成树包含图中全部n 个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。从算法中WHILE （所剩边数>=顶点数）来看，循环到边数比顶点数少1（即n-1）停止，这符合n 个顶点的连通图的生成树有n-1条边的定义；由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树；算法中“若图不再连通，则恢复ei ”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。

27．Prim 算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal 算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）

28．（1）最小生成树的定义见上面26题

（2）最小生成树有两棵。

（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W ）形式），其中W 代表权值。

V （G ）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；

E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）}

29．V （G ）={1，2，3，4，5，6，7}

E （G ）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）} 30．V （G ）={1，2，3，4，5，6，7，8}

E （G ）={（3，8，2），（4，7，2），（3，4，3），（5，8，3），（2，5，4），（6，7，4），（1，2，5）} 注：（或将（3，4，3）换成（7，8，3））

31．设顶点集合为{1，2，3，4，5，6}，

由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中， 各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。 32．（1）邻接矩阵略

（2）

即

五.算法设计题

1.void CreatGraph (AdjList g)

//建立有n个顶点和m 条边的无向图的邻接表存储结构

{int n,m;

scanf("%d%d",&n,&m);

for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量

{scanf(&g[i].vertex); g[i].firstarc=null;}

for (k=1;k<=m;k++)//输入边信息

{scanf(&v1,&v2);//输入两个顶点

i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p;

}

}//算法CreatGraph结束

2.void CreatAdjList(AdjList g)

//建立有向图的邻接表存储结构

{int n;

scanf("%d",&n);

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

{scanf(&g[i].vertex); g[i].firstarc=null;}//输入顶点信息

scanf(&v1,.&v2);

while(v1 && v2)//题目要求两顶点之一为0表示结束

{i=GraphLocateVertex(g2,v1);

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;

scanf(&v1,&v2);

} }

3.void CreatMGraph(AdjMulist g)

//建立有n个顶点e条边的无向图的邻接多重表的存储结构

{int n,e;

scanf("%d%d",&n,&e);

for(i=1,i<=n;i++) //建立顶点向量

{ scanf(&g[i].vertex); g[i].firstedge=null;}

for(k=1;k<=e;k++) //建立边结点

{scanf(&v1,&v2);

i=GraphLocateVertex(g,v1); j=GraphLocateVertex(g,v2);

p=(ENode *)malloc(sizeof(ENode));

p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge;

g[i].firstedge=p; g[j].firstedge=p;

}

}//算法结束

4.void CreatOrthList(OrthList g)

//建立有向图的十字链表存储结构

{int i,j,v; //假定权值为整型

scanf("%d",&n);

for(i=1,i<=n;i++) //建立顶点向量

{ scanf(&g[i].vertex); g[i].firstin=null; g[i].firstout=null;}

scanf("%d%d%d",&i,&j,&v);

while (i && j && v) //当输入i,j,v之一为0时,结束算法运行 {p=(OrArcNode *)malloc(sizeof(OrArcNode)); //申请结点

p->headvex=j; p->tailvex=i; p->weight=v; //弧结点中权值域

p->headlink=g[j].firstin; g[j].firstin=p;

p->tailink=g[i].firstout; g[i].firstout=p;

scanf("%d%d%d",&i,&j,&v);

} }算法结束

[算法讨论] 本题已假定输入的i和j是顶点号,否则,顶点的信息要输入,且用顶点定位函数求出顶点在顶点向量中的下标。图建立时，若已知边数（如上面1和2题），可以用for循环；若不知边数，可用while循环（如本题），规定输入特殊数（如本题的零值）时结束运行。本题中数值设为整型，否则应以和数值类型相容的方式输入。

5．void InvertAdjList(AdjList gin,gout）

//将有向图的出度邻接表改为按入度建立的逆邻接表

{for (i=1;i<=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。

{gin[i].vertex=gout[i].vertex; gin.firstarc=null; }

for (i=1;i<=n;i++) //邻接表转为逆邻接表。

{p=gout[i].firstarc;//取指向邻接表的指针。

while (p!=null)

{ j=p->adjvex;

s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。

s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s;

p=p->next;//下一个邻接点。

}//while

}//for }

6. void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)

//将图的邻接表表示转换为邻接矩阵表示。

{for (i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。

for (j=1;j<=n;j++) gm[i][j]=0;

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

{p=gl[i].firstarc; //取第一个邻接点。

while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一个邻接点

}//for }//算法结束

7. void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )

//将图的邻接矩阵表示法转换为邻接表表示法。

{for (i=1;i<=n;i++) //邻接表表头向量初始化。

{scanf(&gl[i].vertex); gl[i].firstarc=null;}

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

for (j=1;j<=n;j++)

if (gm[i][j]==1)

{p=(ArcNode *)malloc(sizeof(ArcNode)) ;//申请结点空间。

p->adjvex=j;//顶点I的邻接点是j

p->next=gl[i].firstarc; gl[i].firstarc=p; //链入顶点i的邻接点链表中

}

}//end

[算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。

8.[题目分析] 在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs 前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag。初始化为0，若有通路，则flag=1。

算法1：int visited[]=0; //全局变量，访问数组初始化

int dfs(AdjList g , vi)

//以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无

{ visited[vi]=1; //visited是访问数组，设顶点的信息就是顶点编号。

p=g[vi].firstarc; //第一个邻接点。

while ( p!=null)

{ j=p->adjvex;

if (vj==j) { flag=1; return（1）;} //vi 和 vj 有通路。

if (visited[j]==0) dfs(g,j);

p=p->next； }//while

if (!flag) return(0);

}//结束

[算法讨论] 若顶点vi和vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。下面算法2输出vi 到 vj的路径，其思想是用一个栈存放遍历的顶点，遇到顶点vj时输出路径。

算法2：void dfs(AdjList g , int i)

//有向图g的顶点vi（编号i）和顶点vj（编号j）间是否有路径，如有，则输出。 {int top=0,stack[]; //stack是存放顶点编号的栈

visited[i]=1; //visited 数组在进入dfs前已初始化。

stack[++top]=i;

p=g[i].firstarc; /求第一个邻接点.

while (p)

{if (p->adjvex==j)

{stack[++top]=j; printf( "顶点 vi 和 vj 的路径为：\n");

for (i=1; i<=top; i++) printf( "%4d",stack[i]); exit(0);

}//if

else if(visited[p->adjvex]==0) {dfs(g,g->adjvex); top--;

p=p->next;}//else if

}//while

}//结束算法2

算法3：本题用非递归算法求解。

int Connectij (AdjList g , vertype vi , vj )

//判断n个顶点以邻接表表示的有向图g中，顶点 Vi 各Vj 是否有路径，有则返回1，否则返回0。

{ for (i=1;i<=n;i++) visited[i]=0; //访问标记数组初始化。

i=GraphLocateVertex(g,vi); //顶点定位，不考虑 vi或 vj不在图中的情况。

j=GraphLocateVertex(g,vj);

int stack[],top=0;stack[++top]=i;

while(top>0)

{k=stack[top--]; p=g[k].firstarc;

while(p!=null && visited[p->adjvex]==1) p=p->next; //查第k个链表中第一个未访问的弧结点。

if(p==null) top--;

else {i=p->adjvex;

if(i==j) return(1); //顶点vi和vj 间有路径。

else {visited[i]=1; stack[++top]=i;}//else

}//else

}while

return(0); } //顶点vi和vj 间无通路。

9. void DeletEdge(AdjList g,int i,j)

//在用邻接表方式存储的无向图g中，删除边(i,j)

{p=g[i].firstarc; pre=null; //删顶点i 的边结点(i,j),pre是前驱指针while (p)

if (p->adjvex==j)

{if(pre==null)g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。

else {pre=p; p=p->next;} //沿链表继续查找

p=g[j].firstarc; pre=null; //删顶点j 的边结点(j,i)

while (p)

if (p->adjvex==i)

{if(pre==null)g[j].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。

else {pre=p; p=p->next;} //沿链表继续查找

}// DeletEdge

[算法讨论] 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。

10. void DeleteArc（AdjList g,vertype vi,vj）

//删除以邻接表存储的有向图g的一条弧，假定顶点vi和vj存在{i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); //顶点定位

p=g[i].firstarc; pre=null;

while (p)

if (p->adjvex==j)

{if(pre==null) g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。

else { pre=p; p=p->next;}

}//结束

11. void InsertArc ( OrthList g ,vertype vi,vj)

//在以十字链表示的有向图g中插入弧

{ i=GraphLocateVertex(g,vi); //顶点定位.

j=GraphLocateVertex(g,vj);

p=(OrArcNode *)malloc(sizeof(OrArcNode));

p=headvex=j; p=tailvex=i; //填写弧结点信息并插入十字链表。

p->headlink=g[j].firstin; g[j].firstin=p;

p->taillink=g[i].firstout; g[i].firstout=p;

}//算法结束

12. [题目分析]在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。

int count (AdjList g , int k )

//在n个顶点以邻接表表示的有向图g中，求指定顶点k(1<=k<=n)的入度。

{ int count =0;

for (i=1;i<=n;i++) //求顶点k的入度要遍历整个邻接表。

if(i!=k) //顶点k的邻接链表不必计算

{p=g[i].firstarc;//取顶点 i 的邻接表。

while (p)

{if (p->adjvex==k) count++;

p=p->next;

}//while

}//if

return(count); //顶点k的入度.

}

13. [题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v 和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。

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

if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。

{printf(“%d”,v); if(i==start) printf(“\n”); else Print(i,start);break;}//if

}//Print

void dfs(int v)

{visited[v]=1;

for(j=1;j<=n;j++ )

if (g[v][j]!=0) //存在边(v,j)

if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if

else {cycle=1; Print(j,j);}

visited[v]=2;

}//dfs

void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0;

for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);

}//find_cycle

14．[题目分析]有几种方法判断有向图是否存在环路，这里使用拓扑排序法。对有向图的顶点进行拓扑排序，若拓扑排序成功，则无环路；否则，存在环路。题目已假定有向图用十字链表存储，为方便运算，在顶点结点中，再增加一个入度域indegree，存放顶点的入度。入度为零的顶点先输出。为节省空间，入度域还起栈的作用。值得注意的是，在邻接表中，顶点的邻接点非常清楚，顶点的单链表中的邻接点域都是顶点的邻接点。由于十字链表边（弧）结点个数与边（弧）个数相同（不象无向图边结点个数是边的二倍），因此，对某顶点v, 要判断其邻接点是headvex还是tailvex。

int Topsor(OrthList g)

//判断以十字链表为存储结构的有向图g是否存在环路，如是，返回1，否则，返回0。

{int top=0; //用作栈顶指针

for(i=1;i<=n;i++) //求各顶点的入度。设有向图g有n个顶点，初始时入度域均为0

{p=g[i].firstin; //设顶点信息就是顶点编号，否则，要进行顶点定位while(p)

{g[i].indegree++; //入度域增1

if (p->headvex==i) p=p->headlink; else p=p->taillink; //找顶点i的邻接点

}//while(p) }//for

for (i=1;i<=n;i++) //建立入度为0的顶点的栈

if (g[i].indegree==0) {g[i].indegree=top; top=i; }

m=0; //m为计数器，记输出顶点个数

while (top<>0)

{i=top; top=g[top].indegree; m++; //top指向下一入度为0的顶点

p=g[i].firstout;

while (p) //处理顶点i的各邻接点的入度

{if (p->tail vex==i) k=p->headvex; else k=p->tailvex;}//找顶点i的邻接点

g[k].indegree--; //邻接点入度减1

if (g[k].indegree==0) {g[k].indegree=top; top=k; } //入度为0的顶点再入栈

if (p->headvex==i) p=p->headlink; else p=p->taillink;//找顶点i的下一邻接点

}//while (p)

}// while (top<>0)

if (m

else return(0); //有向图无环路

}//算法结束

15. int FirstAdj(AdjMuList g , vertype v)

//在邻接多重表g中，求v的第一邻接点，若存在，返回第一邻接点，否则，返回0。 {i=GraphLocateVertex(g,v); //确定顶点v在邻接多重表向量中的下标，不考虑不存在v的情况。

p=g[i].firstedge; //取第一个边结点。

if (p==null ) return (0);

else {if (ivex==i) return (jvex); else return (ivex);}

//返回第一邻接点，ivex和jvex中必有一个等于i

}// FirstAdj

16. [题目分析]本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。

const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。

void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\n”,v); num=0;}//if

p=g[v].firstarc;

while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

visited[v]=0; num--; //恢复顶点v

}//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。

{static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。

{num=0; visited[1..n]=0; dfs(i); }

}// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

17. [题目分析] 使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。

void dfs ()

{visited[v]=1; printf ( “%3d”,v); //输出连通分量的顶点。

p=g[v].firstarc;

while (p!=null)

{if（visited[p->adjvex==0]） dfs(p->adjvex);

p=p->next;

}//while

}// dfs

void Count()

//求图中连通分量的个数

{int k=0 ; static AdjList g ; //设无向图g有n个结点

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

if (visited[i]==0) { printf ("\n第%d个连通分量:\n",++k); dfs(i);}//if }//Count

算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。

18. void bfs(AdjList GL，vertype v )

//从v发广度优先遍历以邻接表为存储结构的无向图GL。

{visited[v]=1;

printf( "%3d",v); //输出第一个遍历的顶点。

QueueInit(Q); QueueIn(Q ,v); //先置空队列，然后第一个顶点v入队列，设队列容量足够大

while (!QueueEmpty(Q))

{v=QueueOut(Q); p=GL[v].firstarc; //GL是全局变量， v入队列。

while (p!=null)

{if(visited[p->adjvex]==0)

{printf("%3d",p->adjvex); visited[p->adjvex]=1; QueueIn(Q,p->adjvex);}//if

p=p->next;

}//while

}// while (!QueueEmpty(Q))

}//bfs

void BFSCOM()

//广度优先搜索，求无向图Ｇ的连通分量。

{ int count=0; //记连通分量个数。

for (i=1;i<=n;i++) visited[i]=0;

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

if(visited[i]==0) {printf("\n第%d个连通分量:\n",++count); bfs(i);}//if

}//BFSCOM

19.请参见上题18。HEAD，MARK，VER，LINK相当于上题GL，visited，adjvex，next。

20. void Traver(AdjList g,vertype v)

心电图检查和意义

教案（课时计划）

一、概述 ㈠心电图的基本知识 1、心电图：心电图是心肌产生电位变化的体表记录。 心电图（Electrocardiogram）心脏在收缩之前先有生物电活动，所产生的动作电流可经体内组织传导至体表各部。如果在两个体表部位放置电极板，用导线连接至心电图机，就可描记出心脏生物电活动的曲线，此即心电图。 2、心电图功能：心电图主要反映心脏的电学活动。 ⑴对各种心律失常作出判断，明确显示心肌受损，供血和坏死现象。 ⑵观察某些药物在应用过程中对心肌的影响，及对心律失常治疗的效果。 ⑶观察某些民解质紊乱所引起的心电图变化及作为治疗的参考资料。 3、心电图缺点：对心脏功能状态及代偿情况不能直接显示。必须结合临床资料综合分析，才能更发好地发挥其辅助临床诊断作用。 ㈡心电发生的原理 现代心脏电生理学的深入发展为临床心电学的研究奠定了理论基础。心肌细胞电生理研究指出： 1、静息的心肌细胞保持于复极化状态，细胞膜外侧具正电荷，细胞膜内侧具负电荷，两侧保持平衡，不产生电位变化。 2、当心肌细胞一端的细胞膜受到一定程度的刺激（阈刺激）时，其对钾、钠、氯、钙等离子的通透性发生改变，引起膜内外正、负离子流动（主要是钠离子内流），使细胞内外正负离子的分布发生逆转，受刺激部位的细胞膜出现除极化（depolarization），使膜外侧具负电荷而膜内侧具正电荷，即产生动作电 此时若将检测电极置于体表一定位置，可测得一定的电位变化。于对向细胞除极方向的电极处，可测得正电位而描出向上的波；而于背离细胞除极方向的电极处，则可测得负电位而描出向下的波。心肌细胞完成除极后，继之出现极化状态的恢复过程称为复极化（repolarization），从而就单个心肌细胞而言，出现与除极数量相等而方向相反的电位变化。 ㈢正常心电图（ECG） 1、正常心电活动起源于窦房结，沿心脏的特殊传导系统的通道下传（窦房结、结间束、房间束、房室结、房室束或希氏束、左束支、右束支、Purkinge纤维网所构成），先后引起心房和心室的兴奋，此在心电图上可呈现一系列形，称为P、Q、R、S、T以及V波。 ⑴最早出现的是幅度最小的P波，反映心房的除极过程。 ⑵P－R段（实为P－Q段，传统称为P－R段），反映心房的复极过程及房室结和房室束的电活动，P波与P－R段合计为P－R间期。始自心房开始除极，终于心室开始除极。

《数据结构》习题汇编07 第七章 图 试题

第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。

数据结构第7章图习题

、单项选择题 1．在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的 _________ 倍 A ．l/2 B ．1 D ．4 2．在一个有向图中， 所有顶点的入度之和等于所有顶点的出度之和的 ________倍 A ．l/2 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>

点邻接表中的结点总数为_________ 。

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. 下列说法中不正确的是

数据结构第7章

数据结构第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．按层遍历

数据结构第七章图

数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题：

数据结构第7章-答案

一、单选题 C01、在一个图中，所有顶点的度数之和等于图的边数的倍。 A)1/2 B)1 C)2 D)4 B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A)1/2 B)1 C)2 D)4 B03、有8个结点的无向图最多有条边。 A)14 B)28 C)56 D)112 C04、有8个结点的无向连通图最少有条边。 A)5 B)6 C)7 D)8 C05、有8个结点的有向完全图有条边。 A)14 B)28 C)56 D)112 B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A)栈 B)队列 C)树 D)图 A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A)O(n) B)O(e) C)O(n+e) D)O(n2) C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2 B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6 D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3 A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

数据结构第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．无向图中的极大连通子图称为连通分量

数据结构习题集第章图

第7章图 一、选择题 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个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（（1））；所有邻接表 中的结点总数是（（2））。 （1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 B、E C、2E D、N+E 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出发，

《健康评估》 心电图

《健康评估》复习要点：第七章心电图检查（最好看图形象记忆） 1.目前，临床上最普遍应用的是由Einthoven（爱因托芬）创设的国际通用导联体系，称为常规12导联体系。（1）肢体导联包括标准导联Ⅰ、Ⅱ、Ⅲ和加压单极肢体导联 aVR、aVL、aVF （2）心前区导联包括 V1～V6导联。 2.Ⅰ、Ⅱ、Ⅲ导联的正极分别在左上肢、左下肢、左下肢。aVR、aVL、aVF导联的正极分别 在右上肢、左上肢、左下肢。V1～ V6导联的正极分别在胸骨右缘第4肋间、 胸骨左缘第4肋间、V2与V4连线中点、左锁骨中线平第5肋间、左腋前线与V4同一水平、左腋中线与V4同一水平。 3.P波是最早出现的振幅较小的波，反映心房除极过程的电位位变化。P波起始部代表右心房除极，终末部代表左心房除极，中间部代表右、左心房除极。 P波在Ⅰ、Ⅱ、aVF、V4～V6导联直立，在aVR导联倒置。P波时间一般＜ 0.12s（ 3小格），振幅肢导＜0.25 mv。 左心房肥大时，Ⅱ导联上P波时间一般＞0.12 s ，常呈双峰型。右心房肥大时，Ⅱ导联上P波时间一般正常，＜ 0.12 s，P波高尖。 4.QRS波群为振幅最大的波，反映心室除极过程的电位变化。QRS波群最宽不超过0.11s。V5导联的R波＜2.5 mV。左心室肥大时QRS波群振幅增高，心前区导联改变更明显，Rv5、Rv6 ＞ 2.5 mV，或Rv5+Sv1＞ 4.0 mV（男），或 3.5 mV（女）。QRS波群振幅增高是诊断左心室肥大的必备条件，在此基础上结合其它阳性指标（如心电轴左偏）即可诊断。 5.若Ⅲ导联出现较深的负向波，Ⅰ导联主波为正向波，则提示电轴左偏。 6.过渡区波形出现在V5、V6导联，提示顺钟向转位。 7.Q-T间期是自QRS波群起点至T波终点的水平距离，反映心室开始除极至心室复极完毕全过程的时间。 8.T波为ST段后一个圆钝而较大的波，反映心室快速复极过程的电位变化。 9. 心电图的特征性改变与演变规律是诊断心肌梗死和判断病情的主要依据。 如：①“缺血型”改变时，心外膜缺血，T波对称性倒置，呈“冠状T”；

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

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章 图 一、单选题 （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。 A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 （ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 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 1 3 4 2 5 6 （ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 A ． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6 （ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3

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

数据结构第七章图练习及答案 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网中从源点到汇点的最长路径

第07章 深入视图层

第 7 章深入视图层 视图(view)的作用是显示特定动作(action)的输出。在symfony里，视图由几部分组成，这些部分都很容易修改。 ?Web设计师通常会与模板(当前动作的数据的表现形式)和布局(包含所有页面都会用到的代码)打交道。这些模板由HTML加上PHP代码片段(主要是辅助函数调用)组成。 ?为了重用，开发者往往会把模板代码的片段放在局部模板(Partials)或者组件(Components)里。开发者使用槽(Slots)与组件(Components)来影响布局的多个区域。web设计师也可以修改这些模板片段。 ?开发者专注于YAML视图配置文件(用来设置回应与其他界面元素的属性)还有回应对象(response object)。处理模板里的变量的时候，跨站脚本(corss-site scripting)的风险不可忽略，这就需要在记录用户数据的时候很好的理解输出转义(output escaping)技术。 不论你是哪一个角色，你都可以发现能加快输出动作结果这件乏味的工作的工具。这一章将会介绍这些工具。 模板 例 7-1 是一个典型的symfony模板。它包含一些HTML代码和一些基本的PHP 代码，通常是显示动作(action)里定义的(通过$this->name = 'foo';)变量还有辅助函数。 例 7-1 - indexSuccess.php 模板样本

欢迎