第七章图答案

第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 .

n i d

1

2

1

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,v

0) (12)not visited[w] (13)nextadj(g,v

0,

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)，则邻接矩阵元素个数为n 2，即顶点个数的平方，与图的边数无关。 7．（1）n(n-1)， n

(2) 106

，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律） （3）使用深度优先遍历，按退出dfs 过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。 8．

（2）开始结点：（入度为0）K 1，K 2，终端结点（出度为0）K 6，K 7。（3）拓扑序列K 1，K 2，K 3，K 4，K 5，K 6，K 8，K 9，K 7 2，K 1，K 3，K 4，K 5，K 6，K 8，K 9，K 7

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 个顶点的图占用n 2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。

邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n （n ≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或

001000000000000001000000000000101001100000000000000000010000100

0001

1000000000110

删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。

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

邻接多重表是无向图的另一种存储结构，边结点至少包括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

（

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

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

图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） （1） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （2）

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

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

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

24．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列

(1)ABGFDEC (2)EACFBDG (3)

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)） 2356

14(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

2

(3)最小生成树6个顶点5条边：V(G)={Pe,N,Pa,L,T,M}

E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)} 34.(1)

enode=RECORD ivex,jvex:vtxptr; w:integer; jlink,ilink:edgeptr; END ; vexnode=RECORD data:vertertype; firstedge:edgeptr; END; adjmulist=ARRAY[vexptr] OF vexnode;

(2)深度优先遍历序列：1,4,6,5,3,2；

深度优先生成树的边集合：{(1,4),(4,6),(6,5),(5,3),(3,2)} (3)宽度优先遍历序列：143265；

宽度优先生成树的边集合：{(1,4),(1,3),(1,2),(4,6),(4,5)}： （4按Prim 构造过程只画出最小生成树的边和权植：

E(G)={(1,4,3),(4,3,4),(3,5,1),(3,2,2),(3,6,10)}

35．E1(G)={（1，2，16），（2，3，5），（2，6，6），（2，4，11），（6，5，18）}，V(G)={1,2,3,4,5,6} E2(G)={（1，2，16），（2，336．

??????

????

????????????0030700000065230084000080300764305005005010200010

?????

??????

?06

5340755106732

36（1）邻接矩阵和邻接表

36（2）深度优先搜索序列:abcdehf; 36(3) 最小生成树

宽度优先搜索序列: abfcdef

37．A 0=??????

??????∞∞∞∞∞∞0340561020A 1=?

???????????∞∞∞∞0534********A 2=???????

??

???∞06

53

4075

6108320

A 3=????????????06

5

3

407551067320

A 4= 38．

(3) (3) 顶点集合V(G)={V1,V2,V3,V4,V5,V6}

边的集合 E(G)={(V1,V2),(V2,V3),(V1,V4),(V4,V5),(V5,V6)}

(4) V1到V3最短路径为67: (V1—V4—V3)

39．注：(1).本表中DIST 中各列最下方的数字是顶点a 到顶点的最短通路，a 到z 为13。 (2)．DIST 数组的常量表达式（即下标）应为符号常量，即‘b ’，‘c ’等，为节省篇幅，用了b,c

等。

(3)．最短路径问题属于有向图，本题给出无向图，只能按有向完全图理解。

40．下面用FLOYD 算法求出任意两顶点的最短路径（如图A （6）

所示）。题目要求娱乐中心“距其它各结点的最长往返路程最短”，结点V1，V3，V5和V6最长往返路径最短都是9。按着“相同条件下总的往返路径越短越好”，选顶点V5，总的往返路径是34。

A (0)=????????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞052301101404230320A (1)=??

?

?

?

?

?

?

??

??????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞0523014103174064230320A (2)=??

?

??

?

????

??????????∞∞∞∞∞∞∞∞

0523034141063174806423034520A (3)=

????????????????????06

52863034184106317480641072307394520A (4)=????????????????????065286

303414410631

748064632303354520

A (5)=??

?

??

?

????

??

???

?????065276

303414410521

747054632303354520

A (6)=

??

?

??

?

????

?????????

?065276303414410521747054632303354520

41．顶点1到其它顶点的最短路径依次是20，31，28，10，17，25，35。按Dijkstra 算法所选顶点依次是5，6，2，7，4，3，8，其步骤原理请参见第39题，因篇幅所限，不再画出各步状态。 42．顶点a 到顶点b ，c ，d ，e ，f ，g 间的最短路径分别是15，2，11，10，6，13。

43．顶点A 到顶点B ，C ，D ，E 的最短路径依次是3，18，38，43，

按Dijkstra 所选顶点过程是B ，C ，D ，E 。支撑树的边集合为{,,,} 44．（

设一栈，将入度为零的顶点放入栈

45．（1）略 （2）

（3）关键路径有3条，长17。（各事件允许发生的最早时间和最晚时间略）

V1->V2->V4->V6->V8，V1->V3->V5->V7->V8，V1->V2->V4->V6->V5->V7->V8 （4）V1结点到其它各结点的最短距离为：2，3，6，12，10，15，16。 46．（1）对有向图，求拓扑序列步骤为：

1）在有向图中选一个没有前驱（即入度为零）的顶点并输出。

2）在图中删除该顶点及所有以它为尾的弧。

3）重复1）和2），直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

（2）这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。这里只画出从顶点1开始的所有可能的拓扑序列，从顶点3开始的拓扑序列可类似画出。

47

历，在dfs(v)成树上是V 算法

48．（1） （3）V1到V8 （4）

V1到V8的关键路径是V1----V6----V5----V3----V8，长97。 49．

（2）略

（

3）深度优先遍历序列：ABCDE 广度优先遍历序列：ABCED （4）关键路径A--B （长100） 50．AOE 网的始点是入度为零的顶点，该顶点所代表的事件无任何先决条件，可首先开始。终点是出度为零的顶点，表示一项工程的结束。正常的AOE 网只有一个始点和一个终点。 51．（1）AOE 网如右图

图中虚线表示在时间上前后工序之间仅是接 续顺序关系不存在依赖关系。顶点代表事件，弧 代表活动，弧上的权代表活动持续时间。题中顶

点1代表工程开始事件，顶点11代表工程结束事件。 （2）各事件发生的最早和最晚时间如下表

事件序列：A->C->E->G->H->L->M ，完成工程所需的最短时间为445。

52

关键路径是：

活动与顶点的对照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 53．A.0—2—6—9—11 B.20 C.1，5，7 D.各2 天 E.0

五.算法设计题

1. 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. 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. 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. 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。

{pri ntf(“%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; pri ntf ( “%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。

工程造价例题及习题

工 程 造 价 刘威

一、预算定额的简单应用 作业：1、试确定人工采筛洗堆砂联合作业，工程量为200m3堆方的预算（成品率按60%计）。 2、某路基工程用10 m3以内自行式铲运机运硬土，平均运距600米，重车上坡坡度18%，试确定该铲运机铲运土方的预算定额。 3、确定下列工程的预算定额编号 （1）、干砌片石锥坡 （2）、干砌片石护脚 （3）、浆砌片石边沟 （4）、8t以内自卸汽车配合挖掘机运土5KM （5）、8t以内自卸汽车配合装载机运粘土5KM （6）、8t以内自卸汽车运输路面混合料5KM （7）、8t载重汽车运输预制构件5KM 二、路基工程中对预算定额的应用 例1、××高速公路路基土、石方工程，计有挖土方 3000000m3,其中松土500000m3、普通土1500000m3、硬土1000000m3。利用开挖土方作填方用天然密实方松土300000m3、普通土1000000m3、硬土500000m3。开炸石方计1000000m3，利用开炸石方作填方用计天然密实方300000m3。填方计压实方4000000m3。 问题： 1、计算路基设计断面方数量 2、计算计价方数量 3、计算利用方数量（压实方） 4、计算借方数量（压实方） 5、计算弃方数量

例2：某二级公路路段挖方2000 m3，其中松土400 m3，普通土1200 m3，硬土400 m3；填方数量2400 m3，本路段挖方可利用方量为1800 m3（松土200 m3，普通土1200 m3，硬土400 m3）；远运利用方量为普通土400 m3（天然方），采用机动翻斗车运土，运距200m。试确定借方（压实方）数量；如借方运距为1.5km，采用75kw推土机推土，8t自卸汽车配合2 m3容量装载机运普通土，试确定上述分项工程的预算定额，并计算相应工程量下的人工、机械台班数量。 三、路面工程定额的应用 例1：某泥结碎石路面面层摊铺工程，厚度16cm，路面宽8.0m，路段长12km，试计算所需人工劳动量及压路机作业量。 例2：某冬五区沥青贯入式面层工程，路面宽9.0m、铺筑长度8km，设计厚度6cm，需铺8cm基层，已查得面层人工定额为17.7工日／1000m 2、石油沥青定额为6.283t／1000m 2，基层人工定额为19工日／1000m 2、石油沥青定额为7.004t／1000m2。试求其总劳动量和总用油量。 例3：某级配砾石路面，路面设计宽度为3.5m，已查得人工定额为18.3工日／l 000m 2、12t～15t光轮压路机定额为1.45台班／1000m 2。试问该两项的实用定额值应为多少? 例4：拖拉机带铧犁拌和某石灰、粉煤灰稳定碎石路面基层，设计配合比石灰：粉煤灰：碎石为6：12：82，设计厚度为17cm ，试以预算定额求各材料按设计

第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、已知建筑平面图及剖面图如图示，墙厚370 mm，部分楼层墙厚240 mm，内部隔层每层层高2.7 m，试计算其建筑面积。 解：建筑面积＝（22+0.37）×（10+0.37）+（5+0.37）×（5+0.37）＝260.81m2 2、某工程捣制钢筋混凝土独立基础，模板接触面积为50m2，查表可知一次使用模板每10m2需用板材 0.36m3，方才0.45m3，模板周转次数6次，每次周转损耗率16.6%，试计算混凝土模板一次需用量和施工定额摊销量。 解：混凝土模板摊销量计算 1）计算混凝土模板一次使用量： 模板一次使用量=50×0.36 m3／10 m2=1.8m3 2）计算周转使用量 模板周转使用量 ={一次使用量×[1+（周转次数-1）×损耗率]}/周转次数 =1.8×[1+（6-1）×16.6%] ／6 =0.549m3 3）计算回收量（模板） 模板回收量= 一次使用量×（1-损耗率）／周转次数 =1.8／6×（1-16.6%）=0.25m3 4）计算摊销量（模板） 模板摊销量=周转使用量—回收量=0.549-0.25=0.299 m3 3、依据湖北省建筑装饰工程消耗量定额及统一基价表，如图某单层建筑物，外墙顶面高度3.00米，外墙设计采用15mm厚1∶1∶6混合砂浆打底，50×230外墙砖贴面，室内外地坪高差-0.45m，设计地面做法为30mm 厚细石混凝土找平，1∶3水泥砂浆铺贴300×300mm地砖面层，踢脚为150mm高地砖。试计算楼地面工程装饰的工程量。（门、窗居墙中安装，墙厚240mm，门窗框厚90mm，每个房间的中心轴线尺寸为3300*6000mm, 窗C1、C2、M1洞口尺寸分别为：1.5×1.2m、1.5×2.0m、0.9×2.4m）。 解：楼地面工程项目和工程量分别为： ⑴30mm细石砼找平层（3.3-0.24）×（6-0.24）×4＝70.50m2 ⑵1：3水泥砂浆铺贴300×300地砖楼地面70.5+0.9×（0.24-0.15）÷2×4＝70.66m2 ⑶地砖踢脚线 （3.3-0.24+6-0.24）×2×4＝70.56m 4、某土方工程二类土，挖基槽的工程量为450m3，每天有24名工人负责施工，时间定额为0.205工日／m3，试计算完成该分项工程的施工天数。 解：（1）计算完成该分项工程所需总劳动量 总劳动量＝450×0.205＝92.25(工日) （2）计算施工天数 施工天数＝92.25/24＝3.84(取4天) 即该分项工程需4天完成。 5、有140 m3二砖混水外墙，由11人砌筑小组负责施工，产量定额为0.862m3／工日，试计算其施工天数。 解（1）计算小组每工日完成的工程量 工程量＝11×0.862＝9.48(m3) （2）计算施工天数 施工天数＝140／9.48＝14.77（取15天） 即该混水外墙需15天完成。 6、已知采用M5水泥砂浆砌筑砖基础200m3。试确定其预算价值。 解：（以某省现行预算定额为例）从建筑工程预算定额目录中，查出砖基础的定额项目3-1，通过判断可知，砌筑砖基础分项工程内容与定额规定相一致，即可直接套用定额。从定额表中查得砌筑砖基础的定额基价为1487.90元

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

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）

微观经济学课后习题答案第七章

第七章 复习思考题 参考答案 1、为什么垄断厂商的需求曲线是向右下方倾斜的？并解释相应的TR 曲线、AR 曲线和MR 曲线的特征以及相互关系。 解答：垄断厂商所面临的需求曲线是向右下方倾斜的，其理由主要有两点： 第一，垄断厂商所面临的需求曲线就是市场的需求曲线,而市场需求曲线一般是向右下方倾斜的,所以垄断厂商的需求量与价格成反方向的变化。 第二，假定厂商的销售量等于市场的需求量，那么，垄断厂商所面临的向右下方倾斜的需求曲线表示垄断厂商可以通过调整销售量来控制市场的价格,即垄断厂商可以通过减少商品的销售量来提高市场价格，也可以通过增加商品的销售量来降低市场价格。 关于垄断厂商的TR 曲线、AR 曲线和MR 曲线的特征以及相互关系，以图7—1加以说明： 第一，平均收益AR 曲线与垄断厂商的向右下方倾斜的d 需求曲线重叠。因为，在任何的销售量上，都是P=AR 。 第二,边际收益MR 曲线是向右下方倾斜的，且位置低于AR 曲线.其原因在于AR 曲线是一条下降的曲线.此外,在线性需求曲线的条件下，AR 曲线和MR 曲线的纵截距相同，而且MR 曲线的斜率的绝对值是AR 曲线的斜率的绝对值的两倍. 第三，由于MR 值是TR 曲线的斜率,即dQ dTR MR ，所以，当MR 〉0时，TR 曲线是上升的；当MR ＜0时，TR 曲线是下降的；当MR=0时，TR 曲线达极大值。 图 7-1 垄断竞争厂商的AR 与TR 之间的关系

2、根据图7—22中线性需求曲线d 和相应的边际收益曲线MR ，试求：（1）A 点所对应的MR 值；（2）B 点所对应的MR 值。 解答:(1）根据需求的价格点弹性的几何意义，可得A 点的需求的价格弹性为： 25)515(=-=d e , 或者，2)23(2=-=d e ，根据)11(d e P MR -=,则A 点的MR 值为：MR=2×（2×1/2）=1。 (2)方法同(1）。B 点所对应的MR ＝－1。 3、图7—23是某垄断厂商的长期成本曲线、需求曲线和收益曲线。试在图中标出：(1)长期均衡点及相应的均衡价格和均衡产量;（2）长期均衡时代表最优生产规模的SAC 曲线和SMC 曲线；（3）长期均衡时的利润量。 解答：本题的作图结果如图7—23所示： (1）长期均衡点为E 点,因为，在E 点有MR=LMC 。由E 点出发,均衡价格为P 0，均衡数量为Q 0 。（2）长期均衡时代表最优生产规模的SAC 曲线和SMC 曲线如图所示。在Q 0 的产量上，SAC 曲线和SMC 曲线相切；SMC 曲线和LMC 曲线相交，且同时与MR 曲线相交。(3)长期均衡时的利润量有图中阴影部分的面积表示，即л=(AR(Q 0)-SAC （Q 0)Q 0 图 7-23 4、已知某垄断厂商的短期成本函数为STC ＝0。1Q 3-6Q 2+14Q+3000,反需求函数为P=150—3。25Q 。求：该垄断厂商的短期均衡产量与均衡价格。 解答：由垄断厂商 的短期成本函数STC ＝0.1Q 3-6Q 2+140Q+3000 得边际成本140123.02+-=Q Q MC ， 厂商的总收益23.25Q -150Q 3.25Q)Q -(150Q P TR ==?=， 其边际收益Q MR 5.6150-=； 垄断厂商要实现短期均衡的条件是MC MR =,即Q Q Q 5.6150140123.02-=+-，解之得均衡产量：)(20舍去负值=Q

第7章图习题和参考答案解析

第7章习题 一、单项选择题 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.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。 A. 非零 B. 非整 C. 非负 D. 非正 12.设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ? V2，E1 ? E2，则称（）。 A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量 13.有向图的一个顶点的度为该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. (入度﹢出度))／2 14.一个连通图的生成树是包含图中所有顶点的一个（）子图。 A. 极小 B. 连通 C. 极小连通 D. 无环 15.n (n＞1) 个顶点的强连通图中至少含有（）条有向边。 A. n-1 B. n n(n-1)/2 D. n(n-1) 16.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。 A. 某个最小 B. 任何最小 C. 广度优先 D.深度优先 17.对于具有e条边的无向图，它的邻接表中有（）个结点。 A. e-1 B. e C. 2(e-1) D. 2e 18.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。 A.1, 4, 5 B. 1, 2, 3, 5 C. 1, 4, 3, 5 D. 1, 2, 4, 3, 5

造价考试典型例题汇总

造价考试典型例题汇总 招投标小例题： 多选题 1、评标的原则有（） A.竞争优选 B.公正，公平，科学管理 C.质量好，信誉高，价格合理，工期适当，施工方案先进可行 D.规范性与灵活性相结合 E.反不正当竞争 答案：A，B，C，D，E 分析：评标要遵循如下原则和程序：竞争优选、公正、公平、科学合理、质量好、信誉好、价格合理、工期适当、施工方案先进可行、反不正当竞争、规范性与灵活性相结合。 2.标底是[ ]. A.建筑安装工程造价表现形式 B.招标工程的预期价格 C.是评标的依据之一 D.由上级主管部门编制并审定的 E. 判断投标是否的依据 答案：A，B，C 分析：标底是建筑安装工程造价表现形式，是招标工程的预期价格，是判断投标价格是否合理的依据，并作为评标的依据之一。 3.招标单位在编制标底时需考虑的因素包括[ ]. A.材料价格因素 B.工程质量因素 C.工期因素 D.本招标工程资金来源因素 E.本招标工程的自然地理条件和招标工程范围等因素

答案：A，B，C，E 分析：该题系1997年试点考试试题。该题考点是标底编制的依据及考虑的因素，涉及面较宽。按培训教材规定，标底必须适应目标工期的要求，必须适应招标方的质量要求，必须适应市场价格的变化，必须合理考虑本招标工程的自然地理条件和招标工程范围等。D 有较大迷惑性。"工程的资金来源"在编标底时是不予考虑的。 预算小例题： 单选题： 1、编制施工图预算主要有单价法和（）两种方法。 A、估价法 B、扩大单价法 C、指数法 D、实物法 答案：D 分析：编制施工图预算主要有单价法和实物法两种方法。 2.工作过程是同一工人或小组所完成的在技术操作上相互有机联系的[ ]的总合体。 A.工序 B.动作 C.次序 D.工艺 答案：A 分析：施工过程根据组织上的复杂程度可分为工序、工作过程和综合工作过程。应注意把握它们之间的联系和区别。 3.多余工作时间属于[ ]. A.有效工作时间 B.损失时间 C.定额时间 D.必需损耗的时间 答案：B 分析：工人工作时间可分为定额时间和非定额时间，多余工作时间属于损失时间。 4.材料定额消耗量中的材料净耗量是指[ ]. A.材料必需消耗量 B.施工中消耗的所有材料量 C.直接用到工程上，构成工程实体的消耗量 D.在合理和节约使用材料前提下的消耗量 答案：C 分析：材料定额消耗量是材料的必需消耗量，又可分为材料净耗量和不可避免的损耗量，对有关概念应注意把握。 5.在确定人工定额消耗量的过程中，整理观察资料的方法是[ ]. A.平均修正法 B.移动加权法 C.指数平滑法 D.曲线拟合法

第7章图与网络分析练习题及答案

第七章图与网络分析 一、单项选择题 1．关于可行流，以下叙述不正确的是（） A.可行流的流量大于零而小于容量限制条件 B．在网络的任一中间点，可行流满足流人量=流出量 C．各条有向边上的流量均为零的流是一个可行流 D．可行流的流量小于或等于容量限制条件而大于或等于零 2．关于最小树，以下叙述（）正确。 A.最小树是一个网络中连通所有点而边数最少的图 B．最小树是一个网络中连通所有的点，而权数最少的图 C．一个网络中的最大权边必不包含在其最小树内 D．一个网络的最小树一般是唯一的。 3．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（） A. 边缘结点 B.未接结点 C.已接结点 D.最重要结点 4.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（） A.连接的总长度最大 B.连接的总长度最小 C.连接的总长度为0 D.计算总长度5．最小树问题就是在网络图中，找出若干条边，连接（） A.相邻结点 B.头尾结点 C.部分结点 D.所有结点 6．任一树中的边数和它的点数之间的关系是（） A.边数等于点数减1 B.边数等于点数加1 C.点数等于边数减1 D.点数等于边数加1 7．最大流问题中，对于一个可行流，V i V j有向边上的流量f ij必须满足的条件之一是（） A.0≤f ij≥c ij B.0≥f ij≤c ij C. 0≤f ij≤c ij D. 0≥f ij≥c ij 8.一个连通图中的最小树可能不唯一，其权（） A.是唯一确定的 B.可能不唯一 C.可能不存在 D.一定有多个 二、多项选择题 1.关于图论中图的概念，以下叙述正确的的（） A.图中的边可以是有向边，也可以是无向边 B.图中的各条边上可以标注权 C.结点数等于边数的连通图必含圈 D.结点数等于边数的图必连通 E.图中的边只能是有向边 2.关于最短路，以下叙述不正确的有（） A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的 B．从起点出发到终点的最短路是唯一的 C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上 3.关于增广链，以下叙述正确的有（） A．增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致 B．增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致 C．增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边 D．增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边 E．增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边4.在下图中，根据（a）生成的支撑树有（）

概算例题

1．投资项目概算的种类按工程项目划分有_投资项目总概算、单项工程综合概(预)算、单位工程概(预)算。 2．预算定额中的人工消耗指标包括_______、_______、_______、_______。3．材料预算价格是指建筑安装工程材料从_______运达_______后的出库_______。4．建筑面积包括使用面积、结构面积和辅助面积三部分。 5．建筑物当20米或6层以上时，才能计算高层建筑超高增加费。 6．我国现行建设项目工程造价的构成中，工程建设其他费用包括【】 A．基本预备费 B．税金 C．建设期贷款利息 D．与未来企业生产经营有关的其他费用7．土建工程造价中，计划利润的计费基础是【】 A．直接工程费+间接费 B．直接费+间接费C．人工费 D．直接工程费8．下列定额分类中属于按照生产因素分类

的是【】 A．材料消耗、机械消耗、器具消耗 B．劳动定额、材料消耗定额、机械台班定额 C．机械消耗定额、材料消耗定额、建筑工程定额 D．资金消耗定额、劳动消耗定额、机械消耗定额 9．建筑安装预算定额具有【】 A．利学性、统一性、灵活性 B．强制性、统一性、法令性 C．科学性、法令性、综合性 D．全国范围内统一执行 10．按照理论计算半砖厚砖墙每立方米的标准砖用量是【】 A．429块 B．510块 C．552块D．627块 11．概算定额是确定一定计量单位______的人工、材料和机械台的消耗量的一种标准。【】 A．分项工程结构构件 B．扩大分项工程和扩大结构构件

C．单位工程 D．单项工程 12．已知某施工机械耐用总台班为4000台班，大修间隔台班为800台班，一次大修理费为10000元，则该施工机械的台班大修理费为【】 A．15元／台班 B．12．5元／台班 C．10元／台班 D．75元／台班13．单层建筑物内设有部分楼层．计算建筑面积时【】 A．仅计算首层建筑面积 B．仅计算二层及以上建筑面积 C．均不计算建筑面积 D．均应计算建筑面积 14．一栋四层砖混住宅楼，勒脚以上结构外围水平面积每层为930.0M2．二层及以上每层有8个无围护结构的挑阳台，每个阳台水平投影面积 4.0M2，该住宅楼的建筑面积为【】 A．3816 M2 B. 3784 M2 C. 3768 M2 D. 3720 M2

第7章习题及参考答案

第7章习题及参考答案 命名下列化合物。 ^ OH OH OH O C H 3CH 3 Ph CHCH 2CH 2CH 3OH C 2H 5OCH 2CH 2O C 2H 5 (7) (8) (9)(10) CH 3OH NO 2 O CH 2OH CH 3O CH 2CH 3 CH 3 CH 3 H O H O CH 3(11) (12) (13) (14) 解：(1) 4-丙基-4-庚醇 (2) 2-甲基-3-戊炔-2-醇 (3) 3-氯-2-溴-1-丁醇 (4) (E )-2,3-二甲基-4-溴-2-戊烯-1-醇 (5) (2R ，3R )-3-甲基-4-戊烯-2-醇 (6) (E )-2-丁烯-1，4-二醇 (7) 4-环戊烯-1，3-二醇 (8) 3-甲基-5-甲氧基苯酚 (9) 1-苯基-1-丁醇 (10) 乙二醇二乙醚 (11) 2-硝基-1-萘酚 (12) 4-甲氧基环己基甲醇 (13) 1,2-环氧丁烷 (14) (2S ，3R )-2，3-二甲氧基丁烷 ~

写出下列化合物的结构式。 (1) 3,3-二甲基环戊醇 (2) 肉桂醇 (3) 环戊基叔丁基醚 (4) 3-环己烯基异丙基醚 (5) 顺-1,2-环己二醇 (6) 2,3-二巯基-1-丙醇 (7) 4-丁基-1,3-苯二酚 (8) 二苯并-18-冠-6 解： CH CH CH 2OH OH C H 3C H 3(1) (2) O O C(CH 3)3 CH(CH 3)2 (3) (4) ~ SH SH CH 2CH CHOH (5) (6) OH OH C(CH 3)3 O O O O O (7) (8) 将下列化合物按沸点降低的顺序排列成序。 （1）丙三醇，乙二醇二甲醚，乙二醇，乙二醇单甲醚 （2）3-己醇，正己醇，正辛醇，2-甲基-2-戊醇 解：（1）丙三醇＞乙二醇＞乙二醇单甲醚＞乙二醇二甲醚 （2）正辛醇＞正己醇＞3-己醇＞2-甲基-2-戊醇 将下列各组化合物按与卢卡斯试剂作用的速率快慢排列成序。 （1）1-丁醇，2-丁烯-1-醇，3-丁烯-2-醇，2-丁醇 , （2）叔丁醇，正丁醇，环己醇 （3）对甲氧基苄醇，对硝基苄醇，苄醇 解：（1）3-丁烯-2-醇＞2-丁烯-1-醇＞2-丁醇＞1-丁醇 （2）叔丁醇＞环己醇＞正丁醇 （3）对甲氧基苄醇＞苄醇＞对硝基苄醇

土木工程概预算练习题

一、单项选择题： 1.初步设计方案通过后，在此基础上进行施工图设计，并编制（ D ）。 A、初步设计概算 B、修正概算 C、施工预算 D、施工图预算 2.具有独立的设计文件，竣工后可独立发挥生产能力或使用效益的基本建设项目称为（B ）。 A、建设项目 B、单项工程 C、单位工程 D、分部分项工程 3.在社会主义市场经济条件下，建筑产品的价格由（A ）决定。 A、市场 B、预算定额 C、招标文件 D、清单计价规范 4.（ C）与国际上通用的工程估价方法接近。 A、单位估价法 B、实物金额法 C、分项工程完全造价计算法 D、电算估价法 5.劳动定额时间不包括（ C ）。 A、基本工作时间 B、不可避免的中断时间 C、不是故意的失误时间 D、准备结束时间 6.预算定额手册中的（D ），主要用于对预算定额的分析、换算。 A、总说明 B、分部说明 C、分布说明 D、附录 7.材料预算价格指材料的（ A ）。 A、出库价格 B、材料原价 C、材料运杂费 D 、材料包装费 8.建筑工程一般以定额（ A）为基础计算各项费用。 A、直接费 B、材料费 C、机械台班使用费 D、人工费 9.在计算实砌墙身时，应扣除单个面积在（B ）以上的孔洞所占的体积。 A、 0.1m2 B、 0.3m2 C、 0.5m2 D、 1.0m2 10.现浇构件钢筋的综合损耗率一般规定为（ B）。 A 、2% B、 3% C、 6% D、 9% 11.安装工程预算定额中，一般不包括（ A ），因而安装工程定额基价是不完全工程单价。 A、主材费 B、辅材费 C、人工费 D、机械费 12.整体楼梯的工程量分层按水平投影面积以平方米计算。不扣除宽度小于（ B）的楼梯井空隙。 A、20cm B、50cm C、70cm D、90cm 13.类似工程预算是指已经编好并用于某工程的（ D ）。 A、设计概算 B、修正概算 C、施工预算 D、施工图预算 14.（ D）主要用于工程规模较小或审查精度要求高的工程项目。 A、难点项目抽查法 B、重点项目抽查法 C、指标分析法 D、全面审查法 15.材料预算价格的合理性和（A ）是审查的主要内容。 A、准确性 B、科学性 C、权威性 D、群众性 16.竣工结算的编制单位是（A ）。 A、施工单位 B、监理单位 C、建设单位 D、中介咨询机构 17.以下哪种工程预、结算的审查形式较具有权威性。（D ） A、专家审查 B、单独审查 C、联合会审 D、委托审查 18.（B ）是在预算定额的基础上，将若干个预算定额项目综合为一个扩大结构定额。 A、概算指标 B、概算定额 C、劳动定额 D、施工定额 19.平整场地是指厚度在（B ）以内的就地挖填、找平。 A、10cm B、30cm C、40cm D、50cm 20.教育费附加以（ B ）为计税依据。 A、营业收入额 B、营业税额 C、城市维护建设税额 D、直接费额 21、竣工决算的编制单位是（ C ）。 A、施工单位 B、监理单位 C、建设单位 D、质量监督部门 22、在概预算的审查和执行过程中，各方若发生纠纷，协调不成时，可向（ D ）申请调解和仲裁。 A、建设单位 B、设计单位 C、咨询机构 D、工程造价管理部门 23、按现行国家规定，税金不包括（ A ）。 A、增值税 B、营业税 C、城市维护建设税 D、教育费附加 24、（ A ）是确定是否收取施工图包干费、计划利润率的依据。 A、施工合同 B、施工规范 C、设计规范 D、监理规范 25、目前，预算定额的人工幅度差为（ B ）。 A、5% B、10% C、15% D、20% 26、（C ）是以整个建筑物或构筑物为对象，以“m2”、“m3”，“座”等为计量单位，规定了人工、机械台班、材料消耗指标的一种标准。 A、预算定额 B、概算定额 C、概算指标 D、预算指标 27、定额测定费属间接费中的（ C ）。 A、企业管理费 B、财务费 C、其他费用 D、其他直接费 28、营业税的计税依据为（ A ）。 A、营业收入额 B、直接工程费 C、间接费 D、教育费附加 29、装饰高度在（ C ）时，执行满堂脚手架的“基本层”定额。 A、 0.6m～1.2m B、 1.2m～4.5m C、 4.5m～5.2m D、 5.2m～5.8m 30、天棚抹灰面积按主墙间的净面积以平方米计算，不扣除（ B ）以内的通风孔、灯槽等所占的面积。 A、0.1m2 B、0.3m2 C、0.5m2 D、1.0m2 31、安装工程一般以定额（ D ）为基础计算各项费用。 A、直接费 B、材料费 C、机械台班使用费 D、人工费

习题解答第7章

哈尔滨理工大学电气学院理论电工教研室 第七章(一阶电路)习题解答一、选择题 1．由于线性电路具有叠加性，所以C。 A．电路的全响应与激励成正比； B．响应的暂态分量与激励成正比； C．电路的零状态响应与激励成正比； D．初始值与激励成正比 2．动态电路在换路后出现过渡过程的原因是A。 A．储能元件中的能量不能跃变； B．电路的结构或参数发生变化； C．电路有独立电源存在； D．电路中有开关元件存在 3．图7—1所示电路中的时间常数为C。 A． ( CC 12 R1R)；B． 2 CC 12 CC 12 R； 2CC 12 C．R2(C1C2)；D．(R1R2)(C1C2) 解：图7—1中C1和C2并联的等效电容为C1C2，而将两个电容摘除后，余下一端口电路的戴维南等效电阻为R，所以此电路的时间常数为R 2(C1C2)。 2 ４．图7—2所示电路中，换路后时间常数最大的电路是A。 解：图7—2（A）、（B）、（C）、（D）所示四个电路中的等效电感L eq分别为L1L22M、

哈尔滨理工大学电气学院理论电工教研室 L 1L 、L 1L 22M 和L 1L 22M 。t0时，将图6—2（A ）、（B ）、（C ）、（D ）中 2 的电感摘除后所得一端口电路的戴维南等效电阻 R 分别为R 、R 2、R 2和R 1R 2。由于 eq2 RL 电路的时间常数等于 L eq R eq ，所以图7—2（A ）所示电路的时间常数最大。 10t 5．RC 一阶电路的全响应u (106e)V ，若初始状态不变而输入增加一倍，则 c 全响应u 变为D 。 c A ． 10t 2012e ；B ． 10t 206e ； C ． 10t 1012e ；Ｄ． 2016e 10t t 解：由求解一阶电路的三要素法 u c u()[u (0)u()]e τ 可知在原电路中 ccc u()10V ，u c (0)4V 。当初始状态不变而输入增加一倍时，有 c 10t10t u20[420]e(2016e)V c 二、填空题 1．换路前电路已处于稳态，已知U s110V ，U s 21V ，C 10.6F ，C 20.4F 。 t0时，开关由a 掷向b ，则图7—3所示电路在换路后瞬间的电容电压u6.4V ，u c2(0)6.4V 。 (0)c1 解：由t0时刻电路得： u c ，u c2(0)U s21V 1(0)U s110V 换路后，电容 C ,C 2构成纯电容的回路（两电容并联）,电容电压发生强迫跃变，此时应由 1 电荷守恒原理求解换路后瞬刻的电容电压。由KVL 得： u c (0)u 2(0)??① 1c C 1u c (0)C 2u c2(0)C 1u c1(0)C 2u c 2(0)??② 1 由以上两式解得 CUCU 1s12 (0)(0) uu c1CC c2 12 s2 6.4V 2．图7—4所示电路的时间常数τ0.1s 。

2018一建《工程经济》章节习题：建设工程项目施工图预算

，更学尔森整理“ 2018 —建《工程经济》章节习题：建设工程项目施工图预算” 多关于一级建造师模拟试题，请搜索“学尔森一级建造师考试”或访问学尔森 一级建造师考试网。 2018年一级建造师《工程经济》 1Z103000 建设工程估价 1Z103050建设工程项目施工图预算 1［单选题］施工单位在施工前组织材料、机具、设备及劳动力供应，编制进度计划、统计完成工作量、进行经济核算的参考依据是（）。 A. 设计概算 B. 施工组织设计 C. 施工图预算 D. 工程量清单 参考答案：C ??参考解析： 施工图预算是施工单位进行施工准备的依据，是施工单位在施工前组织材料、机具、设备及劳动力供应的重要参考，是施工单位编制进度计划、统计完成工作量、进行经济核算的参考依据。故选项C正确。 2［单选题］施工图预算是按照主管部门制定的预算定额、费用定额和其他取费文件等编制的单位工程或单项工程预算 价格的文件，其编制时间是（）。

A. 投资估算完成之后 B. 施工图设计完成以后 C. 设计概算完成之前 D. 施工图设计完成之前 参考答案：B ??［单选题］传统计价模式下，工程预算定额的制定者及间接费的内容和取费标准的规定者都是（）。 A. 投资人 B. 主管部门 C. 投标人 D. 咨询部门 参考答案：B ??［单选题］施工图预算的编制时间应该是（）。 A. 投资估算完成之后 B.施工图设计完成以后 C.设计概算完成之前 D.施工图设计完成之前 参考答案：B ??参考解析： 施工图预算是指在施工图设计完成以后，按照主管部门制定的预算定额、费用定额和其他取费文件等编制的单位工程或单项工程预算价格的文件。故选项B 正确。 5［单选题］施工图预算审查前准备工作不包括（）。

习题第七章图答案

第七章图 一、选择题 1．图中有关路径的定义是（ A ）。【北方交通大学 2001 一、24 （2分）】 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】 3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。【浙江大学 1999 四、4 (4分)】A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（B ）条边。【北京航空航天大学 2000 一、6(2分）】A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（D ）。【中山大学 1998 二、9 （2分）】 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 【北京邮电大学 2000 二、5 （20/8分）】 7．在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。【哈尔滨工业大学 2001 二、3 （2分）】 A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A)。【中山大学1999一、14】A．5 B．6 C．8 D．9 9．下列哪一种图的邻接矩阵是对称矩阵？（ B）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网 10. 下列说法不正确的是（ C ）。【青岛大学 2002 二、9 （2分）】 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程11．无向图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 ）。【南京理工大学 2001 一、14 （1.5分）】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 12. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 13. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1C ），下面步骤重复n-1次: a：（ 2A ）；b：（ 3B ）；最后：（ 4A ）。【南京理工大学 1997 一、11_14 （8分）】（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）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大 （3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET （4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解 14．已知有向图G=(V,E)，其中V={V 1,V 2 ,V 3 ,V 4 ,V 5 ,V 6 ,V 7 }， E={,,,,,,,,},G的拓扑序列是（A ）。 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

建筑工程概预算练习题与答案2013

《建筑工程概预算》练习题一 一、单项选择题： 1.初步设计方案通过后，在此基础上进行施工图设计，并编制（）。 A、初步设计概算 B、修正概算 C、施工预算 D、施工图预算 2.具有独立的设计文件，竣工后可独立发挥生产能力或使用效益的基本建设项目称为（）。 A、建设项目 B、单项工程 C、单位工程 D、分部分项工程 3.在社会主义市场经济条件下，建筑产品的价格由（）决定。 A、市场 B、预算定额 C、招标文件 D、清单计价规 4.（）与国际上通用的工程估价方法接近。 A、单位估价法 B、实物金额法 C、分项工程完全造价计算法 D、电算估价法 5.劳动定额时间不包括（）。 A、基本工作时间 B、不可避免的中断时间 C、不是故意的失误时间 D、准备结束时间 6.预算定额手册中的（），主要用于对预算定额的分析、换算。 A、总说明 B、分部说明 C、分布说明 D、附录 7.材料预算价格指材料的（）。 A、出库价格 B、材料原价 C、材料运杂费 D 、材料包装费 8.建筑工程一般以定额（）为基础计算各项费用。 A、直接费 B、材料费 C、机械台班使用费 D、人工费 9.在计算实砌墙身时，应扣除单个面积在（）以上的孔洞所占的体积。

A、 0.1m2 B、 0.3m2 C、 0.5m2 D、 1.0m2 10.现浇构件钢筋的综合损耗率一般规定为（）。 A 、2% B、 3% C、 6% D、 9% 11.安装工程预算定额中，一般不包括（），因而安装工程定额基价是不完全工程单价。 A、主材费 B、辅材费 C、人工费 D、机械费 12.整体楼梯的工程量分层按水平投影面积以平方米计算。不扣除宽度小于（）的楼梯井空隙。 A、20cm B、50cm C、70cm D、90cm 13.类似工程预算是指已经编好并用于某工程的（）。 A、设计概算 B、修正概算 C、施工预算 D、施工图预算 14.（）主要用于工程规模较小或审查精度要求高的工程项目。 A、难点项目抽查法 B、重点项目抽查法 C、指标分析法 D、全面审查法 15.材料预算价格的合理性和（）是审查的主要容。 A、准确性 B、科学性 C、权威性 D、群众性 16.竣工结算的编制单位是（）。 A、施工单位 B、监理单位 C、建设单位 D、中介咨询机构 17.以下哪种工程预、结算的审查形式较具有权威性。（） A、专家审查 B、单独审查 C、联合会审 D、委托审查 18.（）是在预算定额的基础上，将若干个预算定额项目综合为一个扩大结构定额。 A、概算指标 B、概算定额 C、劳动定额 D、施工定额