目前最完整的数据结构1800题包括完整答案 第七章 图
第七章 图
一、选择题
1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】
A ．由顶点和相邻顶点序偶构成的边所形成的序列
B ．由不同顶点所形成的序列
C ．由不同边所形成的序列
D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1
B ．n(n-1)/2
C ． n(n+1)/2
D ．0
E ．n 2
【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】
3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】
A ．n-1
B ．n
C ．n+1
D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】
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 ）
6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A ．0
B ．1
C ．n-1
D ．n 【北京邮电大学 2000 二、5 （20/8分）】
7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2分）】
A ．1/2
B ．2
C ．1
D ．4 8．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。【中山大学1999一、14】
A ．5
B ．6
C ．8
D ．9
9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。
A ．逆拓扑有序
B ．拓扑有序
C ．无序的 【中科院软件所 1998】
10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。
A ．邻接矩阵
B ．逆邻接表
C ．邻接多重表
D ．十字链表
E ．邻接表
【北京工业大学 2001 一、3 (2分)】
11．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】
A ．有向图
B ．无向图
C ．AOV 网
D ．AO
E 网
12． 从邻接矩阵????
?
?????=01
101
010A 可以看出，该图共有（①）个顶点；如果是有向图该图共有
（②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】
①．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 列的元素是否为零即可。【武汉大学 2000 二、7】
A ．mA
B ．A
C ．A m
D ．Am-1 15. 下列说法不正确的是（ ）。【青岛大学 2002 二、9 （2分）】
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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。【南京理工大学 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 17. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）
【南京理工大学 2000 一、20 （1.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出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。【中科院软件所 1999 六、2-（1）（2分）】
①．A ．1354267 B ．1347652 C ．1534276 D ．1247653 E ．以上答案均不正确
②．A ．1534267 B ．1726453 C ．l354276 D ．1247653 E ．以上答案均不正确
19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】
A ．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A. O(n)
B. O(n+e)
C. O(n 2)
D. O(n 3
) 【合肥工业大学 2001 一、2 （2分）】 21. 下面是求连通网的最小生成树的prim 算法：集合VT ，ET 分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次
: a ：（ 2 ）；b ：（ 3 ）；最后：（ 4 ）。【南京理工大学 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中无回路时，为生成树，否则无解
22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ；（图用邻接矩阵表示）
(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
上面不正确的是（）。【南京理工大学 2000 一、21 （1.5分）】
A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)
23．当各边上的权值( )时，BFS算法可用来解决单源最短路径问题。【中科院计算所2000一、3 (2分）】
A．均相等 B．均互不相等 C．不一定相等
24. 求解最短路径的Floyd算法的时间复杂度为( )。【合肥工业大学 1999 一、2 （2分）】
A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）
25．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
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分）】
26．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。
A．存在 B．不存在【中科院计算所1998 二、6 (2分）】【中国科技大学 1998二、6（2分）】
27．一个有向无环图的拓扑排序序列（）是唯一的。【北京邮电大学 2001 一、3 （2分）】
A．一定 B．不一定
28. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。
A．G中有弧
C．G中没有弧
【南京理工大学 2000 一、9 （1.5分）】
29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*n*n)
【合肥工业大学 2000 一、2 （2分）】【南京理工大学 2001 一、9 （1.5分）】
【青岛大学 2002 二、3 （2分）】
30. 关键路径是事件结点网络中（）。【西安电子科技大学 2001应用一、4 （2分）】
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
31. 下面关于求关键路径的说法不正确的是（）。【南京理工大学 1998 一、12 （2分）】 A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
32．下列关于AOE网的叙述中，不正确的是（）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
【北方交通大学 1999 一、7 （3分）】【北京工业大学 1999 一、1 (2分)】
二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）【青岛大学 2001 四、1 （1分）】
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1997一、4(1分）】
3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=∑
=
n
i
Vi
TD
1
)
(
。（）
【南京航空航天大学 1996 六、4 （1分）】
4. 有e条边的无向图，在邻接表中有e个结点。（）【南京理工大学 1998 二、5 （2分）】
5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）【合肥工业大学2001
二、7(1分）】
6．强连通图的各顶点间均可达。（）【北京邮电大学 2000 一、3 （1分）】
7．强连通分量是无向图的极大强连通子图。（）【北京邮电大学 2002 一、7 （1分）】8．连通分量指的是有向图中的极大连通子图。（）【燕山大学 1998 二、4 （2分）】9．邻接多重表是无向图和有向图的链式存储结构。（）【南京航空航天大学 1995 五、5 （1分）】
10. 十字链表是无向图的一种存储结构。（）【青岛大学 2001 四、7 （1分）】
11. 无向图的邻接矩阵可用一维数组存储。（）【青岛大学 2000 四、5 （1分）】12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）【东南大学 2001 一、4 （1分）】【中山大学 1994 一、3 （2分）】
13．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（）
【北京邮电大学 1998 一、5 （2分）】
14. 有向图的邻接矩阵是对称的。（）【青岛大学 2001 四、6 （1分）】
15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）【东南大学 2001 一、3 （1分）】【哈尔滨工业大学 1999 三、4】
16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使
用邻接表存储形式来存储它。（）【上海海运学院 1995 一、9（1分） 1997 一、8（1分）1998 一、9（1分）】
17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中
结点个数有关，而与图的边数无关。（）【上海海运学院 1996 一、8 （1分） 1999 一、9 （1分）】
18．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）【上海交通大学 1998 一、12】
19．需要借助于一个队列来实现DFS算法。（）【南京航空航天大学 1996 六、8 （1分）】20. 广度遍历生成树描述了从起点到各顶点的最短路径。（）【合肥工业大学 2001 二、
8 （1分）】
21．任何无向图都存在生成树。（）【北京邮电大学 2000 一、1 （1分）】
22. 不同的求最小生成树的方法最后得到的生成树是相同的.（）【南京理工大学 1998
二、3 （2分）】
23．带权无向图的最小生成树必是唯一的。（）【南京航空航天大学 1996 六、7 （1分）】24. 最小代价生成树是唯一的。（）【山东大学 2001 一、5 （1分）】
25．一个网（带权图）都有唯一的最小生成树。（）【大连海事大学 2001 一、14 （1分）】
26．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）【哈尔滨工业大学1999 三、3】
27．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（）【中山大学 1994
一、10（2分）】
28. 最小生成树的KRUSKAL算法是一种贪心法（GREEDY）。（）【华南理工大学 2002 一、
6（1分）】
29. 求最小生成树的普里姆(Prim)算法中边上的权可正可负。（）【南京理工大学 1998
二、2 （2分）】
30．带权的连通无向图的最小代价生成树是唯一的。（）【东南大学 2001 一、5（1分）】31. 最小生成树问题是构造连通网的最小代价生成树。（）【青岛大学 2001 四、10（1分）】
32. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（）
【合肥工业大学 2000 二、7（1分）】
33. 在用Floyd 算法求解各顶点的最短路径时，每个表示两点间路径的path k-1[I,J]一定是path k [I,J]的子集(k=1,2,3,…,n)。（）【合肥工业大学 2000 二、6 （1分）】
34．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（）【南京航空航天大学1995
五、8（1分）】
35．拓扑排序算法仅能适用于有向无环图。（）【南京航空航天大学 1997 一、7 （1分）】36. 无环有向图才能进行拓扑排序。（）【青岛大学 2002 一、7 （1分）2001 一、8 （1分）】
37. 有环图也能进行拓扑排序。（）【青岛大学 2000 四、6 （1分）】
38．拓扑排序的有向图中，最多存在一条环路。（）【大连海事大学 2001 一、6（1分）】
39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学1998 一、13】
40. 既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（）【合肥工业大学 2001
二、6（1分）】
41．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）
【中科院软件所 1997 一、5 （1分）】
42．AOV网的含义是以边表示活动的网。（）【南京航空航天大学 1995 五、7 （1分）】43．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995
五、9(1分）】
44. 关键路径是AOE网中从源点到终点的最长路径。（）【青岛大学 2000 四、10（1分）】
45. AOE网一定是有向无环图。（）【青岛大学 2001 一、9 （1分）】
46. 在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（）
【长沙铁道学院 1997 一、2 (1分)】
47．在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（）【大连海事大学 2001 一、15 （1分）】
48．在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（）
【大连海事大学 2001 一、16 （1分）】
49．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大学1998 一、14】
三、填空题
1.判断一个无向图是一棵树的条件是______。
2．有向图G的强连通分量是指______。【北京科技大学 1997 一、7】
3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】
4．具有10个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1分）】5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。【燕山大学1998 一、6（1分）】
6. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______
【福州大学 1998 二、2 (2分)】
7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
【西安电子科技大 2001软件一、8 （2分）】
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
【合肥工业大学 2000 三、8 （2分）】
9．在有n个顶点的有向图中，每个顶点的度最大可达______。【武汉大学 2000 一、3】10．设G为具有N个顶点的无向连通图，则G中至少有______条边。
【长沙铁道学院 1997 二、2 (2分)】
11．n个顶点的连通无向图，其边的条数至少为______。【哈尔滨工业大学 2000 二、2（1分）】
12．如果含n个顶点的图形形成一个环，则它有______棵生成树。
【西安电子科技大学 2001软件一、2 （2分）】
13．N个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1分）】
14．构造n个结点的强连通图，至少有______条弧。【北京轻工业学院 2000 一、4（2分）】15．有N个顶点的有向图，至少需要量______条弧
才能保证是连通的。【西南交通大学 2000 一、3】
16．右图中的强连通分量的个数为（）个。
【北京邮电大学 2001 二、5 （2分）】
17．N个顶点的连通图用邻接矩阵表示时,该矩阵
至少有_______个非零元素。【中科院计算所1998 一、6（1分）】【中国科技大学1998 一、6（15/6分）】
18．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。
【燕山大学 2001 二、5 （3分）】
19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。【青岛大学 2002
三、7 （2分）】
20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。【青岛大学 2002 三、8 （2分）】
21. 遍历图的过程实质上是______，breath-first search遍历图的时间复杂度______；depth-first search遍历图的时间复杂度______，两者不同之处在于______，反映在数据结构上的差别是______。
【厦门大学 1999 一、3】
22. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
【南京理工大学 1996 二、2 （2分）】
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）}，则采用的遍历方法是______。
【南京理工大学 1997 三、6 （1分）】
24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2分）】
25. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。
【西安电子科技大学 1998 三、6 （5分）】
26．构造连通网最小生成树的两个典型算法是______。【北京科技大学 1998 一、5】27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。
【南京理工大学 2001 二、6（2分）】
28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。【厦门大学 1999 一、4】
29．克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。【中科院计算所 1999 二、3 （2分）】
30．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______，利用Kruskal算法生成最小代价生成树其时间复杂度为______。【长沙铁道学院 1998 二、2 (4分)】
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中的边构成图的______。
【南京理工大学 1999 二、7 （4分）】
33. 有向图G可拓扑排序的判别条件是______。【长沙铁道学院 1998 二、9(2分)】
34. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。【南京理工大学 1999 二、8（4分）】
35. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。【南京理工大学 2000 二、3 （1.5分）】
36．求最短路径的Dijkstra算法的时间复杂度为______。【哈尔滨工业大学 2001 一、5 （2分）】
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>}，则
【南京理工大学 1998 从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。
三、6 （4分）】
38. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。
【南京理工大学 1998 三、7（4分）】
39．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为______。
【西安电子科技大学 1999软件一、7 （2分）】【武汉大学 2000 一、7】40．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。
【北京理工大学 2001 七、3 （2分）】
41．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。【重庆大学2000一、2】
42．在 AOV网中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。
【厦门大学 1999 一、2】
43. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。
（1）．查邻接表中入度为______的顶点，并进栈；
（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______；
（3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。
【南京理工大学 1996 二、3 （6分）】
44．已知图的邻接表结构为：
CONST vtxnum={图的顶点数}
TYPE vtxptr=1..vtxnum;
arcptr=^arcnode;
arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END;
vexnode=RECORD vexdata:{和顶点相关的信息}；firstarc:arcptr END;
adjlist=ARRAY[vtxptr]OF vexnode;
本算法是实现图的深度优先遍历的非递归算法。其中，使用一个顺序栈stack。栈顶指针为top。visited为标志数组。
PROC dfs(g:adjlist;v0:vtxptr);
top=0; write(v0); visited[v0]:=ture; p:=g[v0].firstarc;
WHILE (top<>0)OR(p<>NIL)DO
[WHILE(1)_______DO
[v:=p^.adjvex;
IF(2)_______ THEN p:=p^.nextarc
ELSE [write(v); visited[v]:=true; top:=top+1; stack[top]:=p;
(3)_______] ]
IF top<>0 THEN[p:=stack[top]; top:=top-1; (4)_______]
]
ENDP.同济大学 2000 二、2 (10分)】
45．下面的算法完成图的深度优先遍历，请填空。
PROGRAM graph_traver;
CONST nl=max_node_number;
TYPE vtxptr=1..nl; vtxptr0=0..nl;
arcptr=^arcnode;
arcnode=RECORD vexi ,vexj: vtxptr; nexti, nextj: arcptr; END;;
vexnode=RECORD vexdata: char; firstin，firstout: arcptr; END;
graph=ARRAY[vtxptr0] OF vexnode ;
VAR ga:graph; n: integer;
visited: ARRAY[vtxptr0] OF boolean ;
FUNC order (g: graph; v: char): vtxptr;
(1)_______; i:=n;
WHILE g[i].vexdata<>v DO i:=i-1;
order:=i;
ENDF；
PROC creat(var g: graph);
readln(n,e);
FOR i:= 1 TO n DO [readln(g[i].vexdata); g[i].firstin :=NIL ;
g[i].firstout:=NIL;]
FOR k:= 1 TO e DO [readln (vt,vh);
i:=order (g,vt); j:=order (g,vh); new (p); p^.vexi:=i ; p^.vexj:=j
p^.nextj:= ____(2)____; ___(3)____ :=p;
p^.nexti:=: ____(4)____; ___(5)____ :=p;]
ENDP;
FUNC firstadj(g:graph; v:char): vtxptr0;
i:=order(g,v); p:=g[i].firstout;
IF p<>NIL THEN firstadj:=(6)_______ELSE firstadj:=0;
ENDF;
FUNC nextadj(g:graph; v:char; w:char): vtxptr0;
i:=order(g,v); j:=order(g,w); p:=(7)_______;
WHILE(p<>NIL ) AND (p^.vexj<>j) DO(8)______;
IF (9)______AND(10)______THEN nextadj:=p^.nexti^.vexj ELSE nextadj:=0;
ENDF;
PROC dfs(g:graph; v0:char);
write(v0:2); visited[order(g,v0)]:=true; w:=(11)_______;
WHILE w<>0 DO
[IF (12)______ THEN dfs(g,g[w].vexdata);
w:=(13)_______;]
ENDP;
PROC traver(g:graph);
FOR i:=1 TO n DO visited[i]:=false;
FOR i:=1 TO n DO IF NOT visited[i] THEN dfs(g,g[i].vexdata);
ENDP;
BEGIN
creat(ga); traver(ga);
END. 【北方交通大学 1999 三（20分）】
46．n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。
注：（1）．图的顶点号从 0开始计；（2）．indegree 是有n个分量的一维数组，放顶点的入度；
（3）．函数 crein 用于算顶点入度；（4）．有三个函数push(data),pop( ),check( )其含义为数据 data进栈，退栈和测试栈是否空（不空返回1，否则0）。
crein( array ,indegree,n)
{ for (i=0;i for (j=0;j } topsort (array,indegree,n) { count= ((4)_______) for (i=0;i while (check( )) { vex=pop( ); printf(vex); count++; for (i=0;i { k=array(6)_______ if ((7)_______ ) { indegree[i]--; if ((8)_______ ) push(i); } } } if( count } 【南京理工大学 2000 三、4 （6分）】 47．假设给定的有向图是用邻接表表示，作为输入的是图中顶点个数n和边的个数m, 以及 图的m条边。在下面的程序中，我们用readdata程序过程输入图的信息，并建立该图的邻 接表；利用topol程序过程获得图中顶点的一个拓扑序列。 PROGRAM topol_order(input , output) ; CONST maxn=20 ; TYPE nodeptr=^nltype ; nltype=RECORD num : integer ; link : nodeptr END ; chtype=RECORD count : integer ; head : nodeptr END ; VAR ch : ARRAY [1 .. maxn] OF chtype ; m , n , top : integer ; PROCEDURE readdata ; VAR i , j , u , v : integer ; p : nodeptr ; BEGIN write (′input vertex number n= ′); readln (n) ; write (′input edge number m= ′); readln(m) ; FOR i:=1 TO n DO BEGIN ch[i].count:= 0; ch[i].head:=NIL END; writeln(′input edges :′); FOR j:= 1 TO m DO BEGIN write( j :3 , ′: ′) ; readln( u , v ) ; new( p ) ; ch[v].count:=ch[v].count+1; p^.num:=v; (1) ___ ; (2) __; END END ; PROCEDURE topol ; VAR i, j, k: integer; t: nodeptr ; BEGIN top:= 0 ; FOR i := 1 TO n DO IF ch[i].count=0 THEN BEGIN ch[i].count := top ;top := i END; i:= 0 ; WHILE (3) ___ DO BEGIN (4) __; (5) __ ; write(j : 5) ;i:= i + 1 ;t:=ch[j].head ; WHILE t<>NIL DO BEGIN k := t^.num ; ch[k].count:=ch[k].count–1 ; IF ch[k].count=0 THEN BEGIN ch[k].count:=top; top:=k END; (6) ______ ; END END ; writeln; IF i END; BEGIN readdata ; writeln (′output topol order : ′); topol END. 【复旦大学 1995 三（18分）】 48．如下为拓扑排序的C程序，Array （1）．列出对右图执行该程序后的输出结果。 （2）．在程序空白处填上适当语句。 void topsort(hdnodes graph [],int n) {int i,j,k,top; node_pointer ptr ; top=-1; for (i=0; i if (!graph[i].count){graph[i].count=top; top=i; } for (i=0; i if(1)____ {fprintf(stderr, "\ngraph has a cycle \n"); exit(1); } else {j=top;(2)_____; printf( "v%d, " ,j) ; for (ptr=graph[j].link; ptr; ptr=ptr->link) {k=ptr->vertex; graph[k].count--; if((3)_____) {graph[k].count=top; top=k; } } } } 【浙江大学 2000 六(15分)】 四、应用题 1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ （2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ （3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？ 【复旦大学 1997 一（9分）】 2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？ 【山东大学 2000 一、3 (4分)】 3．一个二部图的邻接矩阵A是一个什么类型的矩阵？【北京科技大学 1999 一、8（2分）】4．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。【东南大学 1993 四（10分）】 5．证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。【北京邮电大学 2002 三（10分）】 6．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 【西安电子科技大学 2000计应用一、6（5分）】 7．请回答下列关于图(Graph)的一些问题：（每题4分） （1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边? （2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？ （3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？【清华大学2000一(12分）】 8．解答问题。设有数据逻辑结构为： B = (K, R), K = {k1, k2, …, k9} R={ （1）．画出这个逻辑结构的图示。（3分） （2）．相对于关系r, 指出所有的开始接点和终端结点。（2分） （3）．分别对关系r中的开始结点，举出一个拓扑序列的例子。（4分） （4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。（6分）【山东工业大学 1999 三（15分）】 9．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a到顶点i的全部简单路径。【东北大学 1997 一、5 (5分)】 10．试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点：（1）．邻接矩阵表示法; （2）．邻接表表示法; （3）．其它表示法。【华中理工大学2000 三（12分）】 11．已知无向图G，V（G）={1，2，3，4}，E（G）={（1，2），（1，3），（2，3），（2，4），（3，4）}试画出G的邻接多表，并说明，若已知点I，如何根据邻接多表找到与I相邻的点j？ 【东南大学 1994 一、2 （8分） 1998 一、6（8分）】 12．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？ 【清华大学 1999 一、5 （2分）】 13．假定Ｇ＝（V，E）是有向图，V＝｛1,2，．．．,N｝，N＞＝1，G以邻接矩阵方式存储，G 的邻接矩阵为A，即Ａ是一个二维数组，如果i到j有边，则A[i,j]=1，否则A[i,j]=0，请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O(n*n)。 【吉林大学 1998 三(16分)】 14．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。【天津大学 1999 一】 15．下面的邻接表表示一个给定的无向图 （1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)) 15题图 14题图 16题图 16．给出图G ： （1）．画出G 的邻接表表示图； （2）．根据你画出的邻接表，以顶点①为根，画出G 的深度优先生成树和广度优先生成树。 【南开大学 1997 五 (14分)】 17．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。 【北京轻工业学院 1998 八 （6分）】 18．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？ 【北京航空航天大学 1998 一、7 （4分）】 19．解答下面的问题 （1）．如果每个指针需要4个字节，每个顶点的标号占2个字节，每条边的权值占2个字 19题图 20题图 （2）．写出下图从顶点1开始的DFS 树。【西安电子科技大学 2000计应用 六 （10分）】 20．如下所示的连通图，请画出： （1）．以顶点①为根的深度优先生成树；（5分） （2）．如果有关节点，请找出所有的关节点。（5分）【清华大学 1998 七 （10分）】 （1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A 出发按“广度优先搜索”算法遍历此图的元素序列. 【北京科技大学 1999 五 2000 五 （12分）】 22．已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。【燕山大学 2000 五 （5分）】 第22题图 第23题图 23．已知某图的邻接表为 （1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（2分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（2分） （6）．写出将无向图的邻接表转换成邻接矩阵的算法。（8分） 【山东大学 1998 六、 18分】 24．考虑右图： (1)从顶点A 出发，求它的深度优先生成树 (2)从顶点E 出发，求它的广度优先生成树 （3）根据普利姆(Prim) 算法， 求它的最小生成树【上海交通大学 1999 六 (12分)】 25.在什么情况下，Prim 算法与Kruskual 算法生成不同的MST ？ 【西安电子科技大学 2000计应用 一、11 （5分）】 26．下面是求无向连通图最小生成树的一种方法。 将图中所有边按权重从大到小排序为（e 1,e 2,…,e m ） i:=1 WHILE (所剩边数 >=顶点数) BEGIN 从图中删去e i 若图不再连通，则恢复e i i:=i+1 END. 试证明这个算法所得的图是原图的最小代价生成树。【北京邮电大学 1999 五 （10分）】 27．已知一个无向图如下图所示，要求分别用Prim 和Kruskal 算法生成最小树（假设以①为起点，试画出构造过程）。【哈尔滨工业大学 1999 九 （8 E A B G C D F 5 3 6 1 4 1 3 2 5 27题图 28题图 28．G=(V,E)是一个带有权的连通图,则： （1）．请回答什么是G 的最小生成树； （2）．G 为下图所示,请找出G 的所有最小生成树。【北方交通大学 1993 二 （12分）】 29．试写出用克鲁斯卡尔（Kruskal ）算法构造下图的一棵最小支撑（或生成）树的过程。 第29图 【吉林大学 2000 一、3 (3分)】 30.求出下图的最小生成树。【合肥工业大学 1999 四、2 （5分）】 第30题图 31．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。 【浙江大学 1994 五 (8分)】 第32题图 32．请看下边的无向加权图。 （1）．写出它的邻接矩阵（ 5分） （2）．按Prim 算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值（15分） 辅助数组内各分量值：【华北计算机系统工程研究所 1999 四 （20分）】 33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L) 、东京(T) 、墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 【上海海运学院1995 六（9分） 1999 五（14分）】 34．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条 边 的两个端点和其权值，共11行。请你： （1）．采用邻接多重表表示该无向网，用类PASCAL语言描述该数据结构，画出 存 储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。 （2）．分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应 的 生成树。 （3）．按prim算法列表计算，从顶点1始求最小生成树，并图示该树。 【北京工业大学 1999 四(20分)】 35．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。【东北大学2000一、4(4分)】 第36题图 36．设无向网G 如上： 第35题图 （1）． 设顶点a 、b 、c 、d 、e 、f 、h 的序号分别为1、2、3、4、5、6、7，请列出网G 的邻接矩阵、画出网G 的邻接表结构: （2）．写出从顶点a 出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G 所的到的顶点序列： 按Prim 算法求出网G 的一棵最小生成树。【北京科技大学 2001 五 (12分)】 37．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A 1，A 2 ，A 3，A 4 。 A=??????????? ?∞∞∞∞∞∞0340561020 【北京邮电大学2001四、5(5分）】 38．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求： （1）．该带权有向图的图形； （2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）； （3）．以顶点V1为起点的深度优先周游生成树； （4）．由顶点V1到顶点V3的最短路径。【中山大学 1994 四 （12分）】 39．用最短路径算法，求如下图中a 到z 的最短通路。【西南财经大学 1999 四】 40．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。 第39题图 123456(顶点边)（出边表） ??????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞052301101404230320654321V V V V V V 【北京邮电大学 2002 四、1 （10分）】 41．求出下图中顶点1到其余各顶点的最短路径。【厦门大学 2002 八、2 （5分）】 42．试利用Dijkstra 算法求下图中从顶点a 到其他个顶点间的最短路径，写出执行算法过程中各步的状态。 【东南大学 2000 四（10分）】 43．对于如下的加权有向图，给出算法Dijkstra 产生的最短路径的支撑树，设顶点A 为源 点，并写出生成过程。【吉林大学 1999 一、2 (4分)】 44．已知图的邻接矩阵为： 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。【同济大学 1998 一 (12分 )】 45．已知一图如下图所示： （1）．写出该图的邻接矩阵； （2）．写出全部拓扑排序； （3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并 第41题图 第43题图 212第42题图 给出关键路径； （4）．求V1结点到各点的最短距离。【北京邮电大学 2000 五 （15分）】 46．（1）．对于有向无环图，叙述求拓扑有序序列的步骤； （2）．对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二 (12分)】 47．有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法，若不能，请简述原因 【西北大学 2000 二、8 (5分)】 48．下图是带权的有向图G 的邻接表表示法，求： （1）．以结点V1出发深度遍历图G 所得的结点序列； （2）．以结点V1出发广度遍历图G 所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。 【青岛海洋大学 1999 四（10分）】 49．对有五个结点{ A,B, C, D, E}的图的邻接矩阵， ????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞05001020060010301000 （1）．画出逻辑图 ； （2）．画出图的十字链表存储； （3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。 【华南师范大学 1999 三 (20分)】 50．何为AOE 网的始点和终点，一个正常的AOE 网是否只有一个始点和一个终点？ 【首都经贸大学 1997 一、4 （4分）】 51．下表给出了某工程各工序之间的优先关系和各工序所需时间 2 5 4 6 1 第45题图 第46 题图 工 程 造 价 刘威 一、预算定额的简单应用 作业：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章图 一、选择题 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.像素图: 。 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.集合与它的边界的并集称集合的。 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由弧 关键路径为：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章图 一、选择题 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、为什么垄断厂商的需求曲线是向右下方倾斜的？并解释相应的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章习题 一、单项选择题 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.曲线拟合法 《电气识图》 一、判断题 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 。 （√） 第七章图与网络分析 一、单项选择题 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 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章习题及参考答案 命名下列化合物。 ^ 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、人工费 哈尔滨理工大学电气学院理论电工教研室 第七章(一阶电路)习题解答一、选择题 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 。工程造价例题及习题
第7章 图习题及答案
工程概预算自考计算题习题(含答案)
图形设计试题及答案
数据结构第七章图练习及答案
图习题及标准答案
微观经济学课后习题答案第七章
第7章图习题和参考答案解析
造价考试典型例题汇总
电气识图全套试题及答案
第7章图与网络分析练习题及答案
概算例题
PS考试试题及答案
第7章习题及参考答案
土木工程概预算练习题
习题解答第7章