书据结构课程（本科）第八章试
题
一、单项选择题
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.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少
有（）子女。
A. 1
B. 2
C. 3
D. 0
14.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为
（）。
A. O(nlog2e)
B. O(n+e)
C. O(n e)
D. O(n2)
15.设有向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为
（）。
A. O(nlog2e)
B. O(n+e)
C. O(n e)
D. O(n2)
16.设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ? V2，E1 ? E2，则称（）。
A. G1是G2的子图
B. G2是G1的子图
C. G1是G2的连通分量
D. G2是G1的连通分量
17.有向图的一个顶点的度为该顶点的（）。
A. 入度
B. 出度
C. 入度与出度之和
D. (入度﹢出度))／2
18.一个连通图的生成树是包含图中所有顶点的一个（）子图。
A. 极小
B. 连通
C. 极小连通
D. 无环
19.n (n＞1) 个顶点的强连通图中至少含有（）条有向边。
A. n-1
B. n n(n-1)/2 D. n(n-1)
20.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。
A. 某个最小
B. 任何最小
C. 广度优先
D.深度优先
21.对于具有e条边的无向图，它的邻接表中有（）个边结点。
A. e-1
B. e
C. 2(e-1)
D. 2e
22.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。
A.1, 4, 5
B. 1, 2, 3, 5
C. 1, 4, 3, 5
D. 1, 2, 4, 3, 5
23.具有n个顶点的有向无环图最多可包含（）条有向边。
A. n-1
B. n
C. n(n-1)/2
D.n(n-1)
24.一个有n个顶点和n条边的无向图一定是（）。
A. 连通的
B. 不连通的 C . 无环的 D . 有环的
25. 在n 个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。 A. n B. n(n -1)/2 C. n(n+1)/2 D. n(n -1)
26. 对于有向图，其邻接矩阵表示比邻接表表示更易于（ ）。 A. 求一个顶点的度 B. 求一个顶点的邻接点 C. 进行图的深度优先遍历 D. 进行图的广度优先遍历
27. 在一个有向图的邻接矩阵表示中，删除一条边
28. 与邻接矩阵相比，邻接表更适合于存储（ ）图。 A. 无向 B.连通 C.稀疏 D. 稠密图
29. 设一个有n 个顶点和e 条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是
（ ）。 A. O(n) B. O(e) C. O(n+e) D. O(n 2)
30. 为了实现图的广度优先遍历，BFS 算法使用的一个辅助数据结构是（ ）。 A. 栈 B. 队列 C. 二叉树 D. 树
参考答案： 1. B 2. A 3. B 4. B 5. A
6. B
7. D
8. A
9. D 10. C 11.C 12. C 13. B 14. B 15. D 16. A 17. C 18. C 19. B 20. A 21. D 22. D 23. C 24. D 25. C 26. A 27. A 28. C 29. A 30. B
二、填空题
1. 图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷________集合。
2. 用邻接矩阵存储图，占用存储空间数与图中顶点个数________关，与边数________关。
3. n (n ﹥0) 个顶点的无向图最多有________条边，最少有________条边。
4. n (n ﹥0) 个顶点的连通无向图最少有________条边。
5. 若3个顶点的图G 的邻接矩阵为????
?
?????010001010，则图G 一定是________向图。
6. n (n ﹥0) 个顶点的连通无向图各顶点的度之和最少为________。
7.设图G = (V, E)，V = {V0, V1, V2, V3}, E = {(V0, V1), (V0, V2), (V0, V3), (V1, V3)}，则从顶点V0开始的图G
的不同深度优先序列有________种，例如______________。
8.设图G = (V, E)，V = {P, Q, R, S, T}, E = {
广度优先搜索所得的所有序列为__________和___________。
9.n (n﹥0) 个顶点的无向图中顶点的度的最大值为________。
10.在重连通图中每个顶点的度至少为________。
11.在非重连通图中进行深度优先搜索，则深度优先生成树的根为关节点的充要条件是它至少有________
个子女。
12.(n﹥0) 个顶点的连通无向图的生成树至少有________条边。
13.101个顶点的连通网络N有100条边，其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各10条，则网络N的
最小生成树各边的权值之和为_________。
14.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________
上，才有可能加入到生成树中。
15.深度优先生成树的高度比广度优先生成树的高度________。
16.求解带权连通图最小生成树的Prim算法适合于________图的情形，而Kruskal算法适合于________图
的情形。
17.求解最短路径的Dijkstra算法适用于各边上的权值________的情形。若设图的顶点数为n，则该算法的
时间复杂度为________。
18.若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则
在相应的邻接矩阵中所有________元素将集中到对角线以上。
参考答案： 1. 非空 2. 有, 无 3. n(n-1)/2, 0
4. n-1
5. 有
6. 2(n-1)
7. 4，V0V1V3V2（或V0V2V1V3, V0V2V3V1, V0V3V1V2）
8. PQRST和PRQTS 9. n-1 10. 2
11. 2 12. n-1 13. 550
14. 连通分量15. 高16. 稠密，稀疏
17. 非负，O(n2) 18. 非零（或值为1的）
三、判断题
1.一个图的子图可以是空图，顶点个数为0。
2.存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。
3.一个有1000个顶点和1000条边的有向图的邻接矩阵是一个稀疏矩阵。
4.对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。
5.有n (n≥1) 个顶点的无向连通图最少有n-1条边。
6.有n (n≥1) 个顶点的有向强连通图最少有n条边。
7.图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。
8.如果无向图中各个顶点的度都大于2，则该图中必有回路。
9.如果有向图中各个顶点的度都大于2，则该图中必有回路。
10.图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求解。
11.图的广度优先搜索（breadth first search）算法不是递归算法。
12.有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。
13.对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。
14.对一个有向图进行拓扑排序（topological sorting），一定可以将图的所有顶点按其关键码大小排列到一
个拓扑有序的序列中。
15.有回路的有向图不能完成拓扑排序。
16.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。
17.用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。
18.对于AOE网络，加速任一关键活动就能使整个工程提前完成。
19.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。
20.在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这
样的桥上的关键活动就能使整个工程提前完成。
21.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数
有关，而与图的边数无关。
22.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
23.邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平
方）
24. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。
25. 连通分量是无向图中的极小连通子图。
26. 强连通分量是有向图中的极大强连通子图。
27. 在AOE 网络中一定只有一条关键路径。
参考答案： 1. 否 2. 否 3. 是 4. 是 5. 是
6. 否
7. 是
8. 是
9. 否 10. 是 11. 是 12. 否 13. 否 14. 否 15. 是 16. 否 17. 是 18. 否 19. 是 20. 是 21. 是 22. 否 23. 是 24. 是 25. 否 26. 是 27. 否
四、运算题
1. 设连通图G 如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V 0开始的广度优先
搜索的结果。
2. 设连通图G 如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V 0开始的深度优先搜
索的结果。
3. 设连通图G 如图所示。试画出从顶点V 0出发的深度优先生成树，指出图G 中哪几个顶点是关节点（即
万一它失效则通信网络将发生故障）。
4. 设连通图G 如图所示，
V 4
6
V 4 6
V 4
6
1
n 0k kj
ik ij b a c -== (1) 如果有关节点，请找出所有的关节点。
(2) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？ 5. 对于如图所示的有向图，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树
6.
设有向图G 如图所示。试画出从顶点V 0开始进行深度优先搜索和广度优先搜索得到的DFS 生成森林和BFS 生成森林。
7. 表示图的另一种方法是使用关联矩阵INC[ ][ ]。其中，一行对应于一个顶点，一列对应于一条边。因
此，如果边j 依附于顶点i ，则INC[i][j]=1。如果ADJ 是图G =（V, E ）的邻接矩阵，INC 是关联矩阵，试说明在什么条件下将有ADJ = INC ?INC T -I ，其中，INC T 是矩阵INC 的转置矩阵，I 是单位矩阵。两个n ?n 的矩阵的乘积C = A ?B 定义为
公式中的 定义为按位加， 定义为按位乘。
设无向图G 如图所示。试画出该图的邻接矩阵和关联矩阵。
8. 设有一个连通网络如图所示。试按如下格式，应用Kruskal 算法给出在构造最小生成树过程中顺序选
出的各条边。
1 V 7 65⑩
①
② ③
④
⑥
⑦
⑧
⑨ ①
②
③
④
⑤
( 始顶点号，终顶点号， 权值 ) ( , , ) ( , , ) ( , , ) ( , , ) ( , , )
9. 设有一个连通网络如图所示。试采用prim 算法从顶点0开始构造最小生成树。（写出加入生成树顶点
集合S 和选择边Edge 的顺序）
10. 计算连通网的最小生成树的Dijkstra 算法可简述如下：将连通网所有的边以方便的次序逐条加入到初
始为空的生成树的边集合T 中。每次选择并加入一条边时，需要判断它是否会与先前加入T 中的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。如果以邻接矩阵作为连通网的存储结构（仅使用矩阵的上三角部分），并在邻接矩阵的下三角部分记录最小生成树的边信息。试以如下所示的图G 为例，画出构造出最小生成树及其邻接矩阵，并在括号内填入每次选择的边和可能去掉的边。
选 择 的
边
去 掉 的 边 （顶点, 顶点, 权值） （顶点, 顶点, 权值） （ , , ） （ , , ） （ , , ） （ , , ） （ ,
, ）
（ ,
, ）
26 21
11 ① ② ⑤ ④ ③ ⑥ 18 14 16 19
9 5 6 ????
?????
?
??------------∞∞--∞-∞∞=02601118060199502114160Edge
（ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ , , ） （ ,
, ）
（ ,
, ）
11. 有八项活动, 每项活动要求的前驱如下:
(1) 试画出相应的AOV 网络, 并给出一个拓扑排序序列。
(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。
12. 试对下图所示的
AOE 网络
(1) 这个工程最早可能在什么时间结束。
(2) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。
13. 设带权有向图如图所示。试采用Dijkstra 算法求从顶点0到其他各顶点的最短路径和最短路径长度。
14. 一项工程由六个子工程p1, p2,
, p6组成。这些子工程之间有下列关系：p1 < p2, p3 < p6, p4 < p3, p2 <
p6, p4 < p5, p1 < p3, p5 < p6。符号“<”表示“领先于”的关系。例如，p2 < p6表示p2完成后p6才能开始。试给出该工程的三种可能的施工顺序。
15. 设一有向图如下所示，请问该有向图是否为强连通图，并画出该有向图所有的强连通分量。
参考答案：
1. 图G 对应的邻接矩阵为
???
?
??
?
??
?
???
??????????????
?=001000000001001000110001000000000100000000010
011000111
000101001000011001000001110G.Edge
执行广度优先搜索的结果为V 0V 1V 3V 2V 4V 7V 6V 5V 8，搜索结果不唯一。
2. 图G 对应的邻接表为：
执行深度优先搜索的结果为：V 0V 1V 4V 3V 6V 7V 8V 2V 5，搜索结果不唯一。
3. 图G 中，从V 0出发的深度优先生成树为：
图G 中的关节点为：V 1, V 2, V 3, V 6。
4. (1) 关节点为 ①, ②, ③, ⑦, ⑧ (2) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从 ③ 的子孙结点⑩到③的祖先结点①引一条边，从 ② 的子孙结点 ④ 到根 ① 的另一分支 ③ 引一条边，并将 ⑦ 的子孙结点 ⑤、⑥ 与结点 ④ 连结起来，可使其变为重连通图。（解答不唯一）
V 4
6
5. 以顶点 ① 为根的深度优先生成树（不唯一）：
以顶点 ② 为根的广度优先生成树：
6. 深度优先生成森林为：
广度优先生成森林为：
7. 当图中的顶点个数等于边的条数时，ADJ = INC*INC T -I 成立。
图G 对应的邻接矩阵为：
7
6543210
01111000
10000100100001001000001010000010
0110000100011001000001107654321
0ADJ ????????????
??????????????=
1 V 23
V 7 6 5
1 V 23
V 7 6 5① ② ③ ④ ⑤
①
②
③
④ ⑤
①
② ③ ④ ⑤
对应的关联矩阵为：
8. 应用Kruskal 算法顺序选出最小生成树的各条边为： ( 始顶点号，终顶点号， 权值 ) ( 0, 3, 1 ) ( 2, 5, 2 )
( 1, 4, 3 )
( 3, 5, 4 )
( 3, 4, 5 )
9. 采用prim 算法从顶点0开始构造最小生成树的过程：
10. 最小生成树及其邻接矩阵如图所示
选 择 的 边
去 掉 的 边 （顶点, 顶点, 权值） （顶点, 顶点, 权值） （ 2 , 1 , 16 ） （
, , ） （
5 ,
1 ,
14 ）
（ ,
, ）
7
6543210
1111
1000100000010001000000100010000001000100
000011001000000011010000000011987654321
0INC ??
?
??
?
??
?
???
?????????
?????=?????
?
??
?
?
?
?---------
∞∞-∞∞∞=02601118060
199502114
160Edge 11146516① ② ④
③
⑥ 14 16
5
6 11
（ 6 , 1 , 21 ） （ , , ） （ 6 , 2 , 19 ） （ 6 , 1 , 21 ） （ 6 , 4 , 11 ） （ , , ）
（ 6 , 5 , 26 ） （ 6 , 5 , 26 ） （ 5 , 4 , 18 ） （ 6 , 2 , 19 ） （ 4 , 2 , 9 ） （ 5 , 4 , 18 ） （ 3 , 2 , 5 ） （ , , ）
（ 4 ,
3 ,
6 ）
（ 4 ,
2 ,
9 ）
选择顺序不唯一。
11. 相应的AOV 网络为：
一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓扑排序结果不唯一。 按拓扑有序的次序对所有顶点从新编号：
相应邻接矩阵为：
7
6543210
00
10000000010000001000000000110000
000100000000010
0001010107654321
0????????????
?????
????
?????=Edge
12. 针对下图所示的AOE 网络
A7
A7
各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：
顶点 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl
19
15
37
38
43
各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：
边 <1,2> <1,3> <3,2> <2,5> <3,5> <2,4> <4,6> <5,6> Ee 0 0 15 19 15 19 29 38 El
17
15
19
27
27
37
38
如果活动k 的最早可能开始时间Ee(k) 与最迟允许开始时间El(k)相等，则该活动是关键活动。本题的关键活动为<1,3>, <3,2>, <2,5>, <5,6>，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。 整个工程最早在43天完成。由关键活动组成的AOV 网络如图所示。
13. 带权有向图如图所示：
应用Dijkstra 算法求从顶点V 0到其他各顶点的最短路径Path 和最短路径长度Len 的步骤如下：
14. 图G 为
p2
可能的施工顺序有： p1, p2, p4, p3, p5, p6 p1, p4, p2, p3, p5, p6 p4, p5, p1, p3, p2, p6
15. 该图的强连通分量分别为：
五、算法分析题
1. 已知有向图的邻接矩阵表示及其一个算法描述如下：
const int MaxVertices = 5; struct Graph { //图的邻接矩阵表示
int Edge[MaxVertices][MaxVertices]; //有向图邻接距阵 int CurrentNode ; //有向图当前结点数 int CurrentEdges ; //当前边数
}
int unknown ( int i ) {
int d = 0;
for ( int j = 0; j < CurrentNode ; j++) { if ( Edge[i][j] != 0 ) d++; if ( Edge[j][i] != 0 ) d++; } return d ; }
(1) 若定义图的一个对象Graph G ，则执行操作G .unknown (3) 后的返回值是多少？ (2) 试说明该算法的功能及时间复杂度。
2. 已知有向图的邻接矩阵表示及其一个操作算法描述如下：
const int MaxVertices = 5;
struct Graph {//图的邻接矩阵表示
int Edge[MaxVertices][MaxVertices]; //有向图邻接距阵
int CurrentNode; //有向图当前结点数
int CurrentEdges;//当前边数
}
void unknown ( int i ) {
int d, j;
d = 0;
for ( j = 0; j < CurrentNode; j++ ) {
if ( Edge[i][j] ) { d++;Edge[i][j] = 0; }
if ( Edge[j][i] ) { d++;Edge[j][i] = 0; }
}
CurrentEdges -= d;
}
若定义图的一个对象Graph G，试写出执行操作G.unknown (3) 后该图的邻接矩阵，并说明该算法的功能。
3.已知有向图的邻接表类的表示的形式描述如下：
struct Edge {//邻接表中边结点的定义
int dest;//邻接的结点
float cost;//边的权值
Edge * link;
};
template
Type data;
Edge *adj;
};
template
Vertex
int NumVertices; //当前顶点个数
int NumEdges; //当前边数
int Degree[MaxV ertices]; //各个顶点的度的记录数组
}
//下列算法是计算有向图中各个顶点的度，并保存在数组Degree[ ]中。请在处
//填入合适的内容，使其成为一个完整的算法。
void FindDegree ( ) {
int i; Edge * p = NULL;
for ( i = 0; i < NumVertices; i++ ) Degree[i] = (1) ;
for ( i = 0; i < NumVertices; i++)
for ( p = NodeTable[i].adj; p != NULL; p = p->link ) {
(2) ;
(3) ;
}
};
4.已知有向图的邻接表类的表示的形式描述如下：
struct Edge {//邻接表中边结点的定义
int dest;//邻接的结点
float cost;//边的权值
Edge * link;
};
template
Type data;
Edge *adj;
};
template
Vertex
int NumVertices; //当前顶点个数
int NumEdges; //当前边数
int Degree[MaxV ertices]; //各个顶点的度的记录数组}
//下列算法是计算有向图G中一个顶点v i的入度。请在处填入合适的内容，//使其成为一个完整的算法。
void FindDegree ( int i ) {
int deg, j;Edge * p = NULL;
deg = 0;
for ( j = 0; j < NumVertices; j++ ) {
p = NodeTable[j].adj;
while ( (1) ) {
p = p->link;
if ( p == NULL ) break;
}
if ( p != NULL ) (2) ;
}
return deg;
}
5.已知有向图的邻接表类的表示的形式描述如下：
struct Edge {//邻接表中边结点的定义
int dest;//邻接的结点
float cost;//边的权值
Edge * link;
};
template
Type data;
Edge *adj;
};
template
Vertex
int NumVertices; //当前顶点个数
int NumEdges; //当前边数
int Degree[MaxV ertices]; //各个顶点的度的记录数组}
//下列算法是从有向图G中删除所有以v i为弧头的有向边。请在处填入合适//的内容，使其成为一个完整的算法。
void DeletEdge ( int i ) {
int de = 0, j; Edge *p, *q;
if ( i >= NumVertices )
{ cout << "错误输入" << endl; exit (1); }
for ( j = 0; j < NumVertices; j++ ) {
p = NodeTable[j].adj;
while ( (1) )
{ q = p;p = p->link; }
if ( p != NULL ) {
if ( p != NodeTable[j].adj ) q->link = p->link;
else (2) ;
delete p;
de++;
}
}
NumEdges = NumEdges - de;
}
6.已知带权图的邻接矩阵表示和邻接表类表示的形式描述分别如下：
(1)邻接矩阵的定义
#define INFINITY INT_MAX //INT_MAX为最大整数，表示∞
const int MaxVertices = 20;
template
Type * NodeTable; //顶点表定义
float arr[Maxvertices][MaxV ertices];//邻接矩阵定义
int NumVertices;//当前顶点个数
int NumEdges;//当前边数
};
(2) 邻接表定义
struct Edge {//邻接表中边结点的定义
int dest;//邻接的结点
float cost;//边的权值
Edge * link;
};
template
Type data;
Edge *adj;
};
template
Vertex
int NumVertices;//当前顶点个数
int NumEdges;//当前边数
}
//下列算法是根据一个图的邻接矩阵建立该图的邻接表，请在处填入合适//的内容，使其成为一个完整的算法。
AdjTable
//将图的邻接矩阵（用this指针指示）转换为邻接表，函数返回邻接表的地址。
AdjTable
A->NodeTable = new Vertex
A->NumEdges = NumEdges;
A->NumVertices = NumVertices;
for ( int i = 0; i < NumVertices; i++ ) {
A->NodeTable[i].data = NodeTable[i];
A->NodeTable[i].adj = (1) ;
for ( int j = 0; j < NumVertices; j++ )
if ( arr[i][j] != INFINITY && arr[i][j] != 0 ) {
e = new Edge;
e->dest = j;
e->cost= (2) ;
e->link = A->NodeTable[i].adj;
(3) ;
}
}
return A;
}
7.已知带权图的邻接矩阵表示和邻接表类表示的形式描述分别如下：
(1) 邻接矩阵的定义
#define INFINITY INT_MAX //INT_MAX为最大整数，表示∞
const int MaxVertices = 20;
template
Type * NodeTable; //顶点表定义
float arr[Maxvertices][MaxV ertices];//邻接矩阵定义
int NumVertices;//当前顶点个数
int NumEdges;//当前边数
};
(2) 邻接表定义
struct Edge {//邻接表中边结点的定义
int dest;//邻接的结点
float cost;//边的权值
Edge * link;
};
template
Type data;
Edge *adj;
};
template
Vertex
int NumVertices;//当前顶点个数
int NumEdges;//当前边数
}
//下列算法是根据一个图的邻接表存储结构建立该图的邻接矩阵存储结构，
//请在处填入合适的内容，使其成为一个完整的算法
AdjMatrix
//将图的邻接表（用this指针指示）转换为邻接矩阵，函数返回邻接矩阵的地址。
AdjMatrix
A->NodeTable = new Vertex
A->arr = new float [Maxvertices][MaxVertices];
A->NumEdges = NumEdges;
A->NumVertices = NumVertices;
for ( i = 0; i < NumVertices; i++ ) {
for ( j = 0; j < NumVertices; j++ ) A->arr[i][j] = INFINITY;
A->NodeTable[i] = _______ __(1)___ ______;
}
for ( i = 0; i < NumVertices; i++ ) {
p = NodeTable[i].adj;
while ( p != NULL ) {
A->arr[i][p->dest] = ___ __(2)__________;
________________(3)________________;
}
}
}
8.已知图的邻接表和逆邻接表的形式描述如下：
struct Edge {//结点定义
int dest;//邻接结点
float cost;//边的权值
Edge * link;
};
Political System 1. The British Monarchy is hereditary 2. The Constitutional Monarchy started at the end of the __17th __ century. 3. The __ Crown _ is used as a symbol of the whole nation and is described as the representative of the people. 4. The oldest part of British Parliament is _ the House of Lords ___. 5. The decision making organ in British Parliament is __ the Cabinet __. 6. The life of Parliament is fixed at ___ five _ years. 7. The House of Commons consists of _651___ members who are elected from the _651____ electoral districts. 8. The titles of the lords, such as Duke, Marquis, Earl, V iscount and Baron, are __ hereditary __. 9. The quorum in the House of Commons is ___ forty _ members. 10. The _ British government _ _____ is the supreme administrative institution. 11. The __ Cabinet is the core of leadership of the British government. 12. The Privy Council was established in the 15th century when __ Henry V __ was on the throne. 13. Not until ___1937 _ could the cabinet have a legal basis. 14. The number of the cabinet members varies, being generally about ___20 __. 15. The president (or head) of the House of Lords in Britain is __ Lord Chancellor __. 16. ___ The Labour Party _ was formed by the trade unions, cooperatives, the Social Democratic Federation, the Independent Labour Party and the Fabian Society in 1900. 17. It is the _ Prime Minister __ who organizes the Cabinet and presides over its meetings. 18. The Shadow Cabinet is organized by the _ Opposition ___. 19. London, because of its special location, is divided into _32____ boroughs and the city of London. 20. “The Morning Star” is the official paper of the ___ Communist Party __. 21. The following persons except ___ criminals _ have no right to vote. 22. In England and Wales, the jury consists of ___ twelve _ people in criminal and civil cases. 23. Legally any citizen aged from ___18__ to __65___ who has never been sent to prison can be a member of the jury. 24. The head of the police force of a county, etc. is called _ Chief Constable __. 25. A __ barrister ___ appointed to act for the State is called Queen’s Counsel. 26. Now the House of Lords can prevent a bill from passing into a law for __ one year _. 27. The High Court of Justice includes the following divisions except _ the Criminal Division _. 28. During the Civil War, the supporters of the King and the Church were known as _ Loyalists _. I. Fill in the Blanks 1. The present sovereign is __ Queen Elizabeth II ___ _____. 2. Elizabeth II came to the throne on Feb. 6th, _ 1952 3. The vital power lies in the ___ Prime Minister __ _____, and his/her cabinet. 4. The __ Crown ___ is the only legal and constitutional link binding the members of the Commonwealth to the home country and to one another. 5. The British Parliament consists of three elements – the _ Crown ____, the House of __ Lords ___, and the House of _ Commons ____. 6. The British legislature is _ Parliament ____.
中 国 文 化 概 论 （习题） ————张令牌 中国文化概 论 一、单项选择题（每小题1分，共25分） 在下列每小题的四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。 1．郡县帝最终得以确立时在位的皇帝是（B ）
A．汉景帝B．汉武帝C．汉高祖D．汉文帝 2．尧舜时期的都城建立在（A ） A．汾河谷地B．河套地区C．江淮地区D．胶东平原 3．京杭大运河走向衰落是在（C ） A．宋朝B．元朝C．清朝后期D．明朝前期 4．唐代被称为世界文化融会场和集散地的是（C ） A．洛阳B．上海C．长安D．开封 5．唐宋以来，中国各地出现了“状元乡”、“秀才县”，主要是由于（A ）A．典范人物的影响B．自然环境的影响 C．地理条件的影响D．区域意识的影响 6．据东汉学者郑玄解释，能走牛车的路称为（B ） A．径B．畛C．涂D．道 7．京剧脸谱的不同颜色被赋予了不同的含义，表示鲁莽豪爽的是（C）A．红色B．白色C．黑色D．紫色 8．对传统的经史文献进行大量考订、校勘、辑佚、辨伪和注解的是( C ) A．浙东学派B．桐城学派C．乾嘉学派D．扬州学派 9．制成最初的指南针——司南的朝代是（ A ） A．战国B．东汉C．北宋D．南宋 10．司马迁把现在徐州以东包括苏州、扬州一带称为（ C ） A．南楚B．北楚C．东楚D．北楚 11．避讳是中国特有的一种语言禁忌，避讳之风起源于（ D ） A．南朝B．秦朝C．唐朝D．周朝 12．旧时各行各业都有自己的祖师，伶人行的祖师是（ A ） A．唐明皇B．秦始皇C．嫘祖D．杨贵妃 13．在中国历史上，农民意识强烈的皇帝当属（ C ） A．秦始皇B．汉武帝C．朱元璋D．乾隆 14．辛亥革命推翻了清政府后，剪辫子、穿中山装的服饰标志属于（ B ）A．阶层标志B．政治标志C．职业标志D．信仰标志 15．在我国庆贺婴儿“满月”礼这天，主持“去胎发”仪式的是（ C ）A．爷爷B．爸爸C．舅父D．族长 16．全盘西化的提出者是（ D ） A．李大钊B．郭沫若C．贺麟D．胡适 17．唐代以后通行的文字字体是（ B ） A．行书B．楷书C．隶书D．草书 18．我国古代把地球围绕太阳旋转的轨道称为（ A ） A．黄道B．红道C．紫道D．白道 19．现存最早的药学专书是（ C ） A．《针灸甲乙经》B．《千金要方》C．《神农本草经》D．《千金翼方》20．元朝把统治下的人民分为四等对待，其中地位最低下的是（ D ）A．蒙古人B．色目人C．汉人D．南人 21．民间人士对中国烹饪地方差异概括正确的是（ A ） A．南甜、北咸、东辣、西酸B．南甜、北咸、东酸、西辣 C．南咸、北甜、东辣、西酸D．南辣、北咸、东甜、西酸 22．宋代文学的代表样式是（ B ）
The industrial revolution refers to the mechanization of industry and the consequent changes in social and economic organization in Britain in the late 18th and early 19th centuries. Britain was the first country to industrialize. The industrial revolution A period in the late 18th and early 19th centuries when major changes in agriculture, manufacturing, production, and transportation had a profound effect on the socioeconomic and cultural conditions in Britain. The Industrial Revolution, was a period of unprecedented technological, economic and social change that completely transformed British culture from a largely rural, static society with limited production and division of labour into the world's first modern industrial society. the Black Death It was the deadly bubonic plague who spread through Europe in the 14th century. It swept through England without warning and any cure, and sparing no victims. It killed between half and one-third of the population of England. Thus, much land was left untended and labor was short. It caused far-reaching economic consequences. The Black Death----It was one of the deadliest pandemics in human history, peaking in Europe between 1348 and 1350. It is widely thought to have been an outbreak of bubonic plague caused by the bacterium Yersinia pestisis and have started in Central Asia. It came without warning, and without any cue.The Black Death is estimated to have killed30% to 60% of Europe's population and had profound effects on the course of European history. In England, it killed almost half of the total population, causing far-reaching economic consequences. the Progressive Movement The Progressive Movement is a movement demanding government regulation of the economy and social conditions. It spread quickly with the support of large numbers of people across the country. It was not an organized campaign with clearly defined goals.(Rather, it was a number of diverse efforts at political, social, and economic reforms. In spite of limitations of the movement, it brought about changes and improvement in many fields.) Roman Britain was the part of the island of Great Britain controlled by the Roman Empire between AD 43 and about 410. Britannia already had cultural and economic links with Continental Europe, but the invaders introduced new developments in agriculture, urbanisation, industry and architecture, leaving a legacy that is still apparent today. The first Romans to campaign extensively in Britain were
2013-2014学年度第一学期 英国国家概况期末试题 （考试时间120分钟，总分100分） 班级姓名成绩 得分评卷人复查人 I. Multiple Choice Questions. (50 points, 2 point for each) Directions: In this part of the test, there are 50 unfinished statements or questions. For each of the unfinished statements or questions, four suggested answers, marked A. B, C and D are given. Choose the one that you think best completes the statement or answers the question. Write the letter of the answer you have chosen in the corresponding space on your Answer Sheet. I. Different Names for Britain and its Parts： 1.The British Isles are made up of________ A.two large islands and hundreds of small ones B. two large islands and Northern Ireland C. three large islands and hundreds of small ones D. three large islands and Northern Ireland 2. There are three political divisions on the island of Great Britain. They are_______ A.Britain，Scotland and Wales B. England，Scotland and Wales C. Britain，Scotland and Ireland D. England，Scotland and Ireland 3.The Commonwealth of Nations is an association of independent countries______ A. that have a large number of British immigrants B. that fought on the side of Britain in the two world wars C. that speak English as their native language D. that were once colonies of Britain 4. About a hundred years ago，as a result of imperialist expansion，Britain ruled an empire that had one fourth of the world's people and ______of the world's land area. A.one third B. one fifth C. one fourth D. two fifths 5.The earliest invasion of England is that by _____. A. the Iberian B. the Danes C. the Celts D. the Anglo-Saxons 6.the Celts religion was _____. A.Christianity B. Druidism C. Norman belief D. Roman Catholic 7.the Anglo-Saxons brought _____ religion to Britain.
4. The 1920s in the United States has been described as a period of .在美国20世纪20年代，被描述为一个物质和精神沮丧的成功 7. When we speak of “father of waters” or “old man river”，we are referring to . 当我们说“水”或“老人河之父”，我们指的是密西西比河
8. Celts were different groups of ancient people who came originally from . 凯尔特人是不同群体的古代人来自德国 13. The ， the backbone of the North American continent， is also known as the Continental Divide.落基山脉，北美大陆的脊梁，也被称为大陆分水岭。
14. To help the British East India Company out of difficulty，the British government allowed the company to sell at a lower price in the colonies through its own people. 为了帮助不列颠东印度公司摆脱困境，英国政府允许公司以较低的价格向殖民地通过自己的人卖茶 21. The first Puritans came to America were on the ship_______. A. Codpeed B. Susan Constant C. May Flower 五月花 D. Discovery
《中国文化概论》试题1 一、填空（每空1分，共30分） 1．儒家是中国本土文化的主干，《大学》中的、亲民、止于至善就是三纲领，而格物、正 心、、、、 、被称为八条目，为古人设计了一条人生道路。 2．宗教也是一种文化现象，佛教在不同的地域与该地区文化结合，形成了不同的民族文化，释加牟尼是在树下悟道的，因而该树为智慧的象征。四谛说是佛家的基本理论，四谛 指、、、、道，是佛家对世界的基本看法以及修养原则。 3．、先秦道家学派的代表人物，张角所创立的，张陵、张衡、张鲁所创立的 是道教的重要源头，金元时期王重阳所创立的风靡中国。 4．中国古代科技曾创造过辉煌，自成系统。《汉书·五行志》中的一段：“日出黄，有黑气，大如钱，居日中央”，是世界公认的最早的关于的记录。《》是汉代产生的著名数学著作，是南北朝著名的数学家，对推算圆周率作出重要贡献。 5．中国古代历史记载的系统性、完备性举世无双，形成了自成系列的史学巨著。《》是二十四史的开端，它是一部体通史；司马光的《》是一部体通史，与以后的续作形成了正史以外的又一系列；唐代杜佑的《》是体例制史书的第一部；宋代袁枢开创了 体系列。 6．中国学术在不同时期呈现出一定的阶段性同的特点，先秦诸子学产生，东汉、西汉学发达，魏晋风行一时，隋唐佛学达到极盛，宋明开创了儒学的新局面。 7．五行说在春秋战国时期定形，是中国古代重要的思维工具，它们之间存在着和等关系。 二、选择题（每空2分，共20分） 1．百家争鸣中对逻辑分析方法及自然科学比较注重的学派是（）。 A．儒家 B．兵家 C．道家 D．墨家名家 2．《三国演义》、《水浒传》、《西游记》（）被称为“四大奇书”，代表了当时俗文学的最高成就。 A．《金瓶梅》 B．《官场现形记》 C．《红楼梦》 D．《初刻拍案惊奇》 3．我国四大发明中（）的源头可以追溯到战国时期。 A．造纸 B．印刷术 C．火药 D．指南针 4．目前公认的中国最早的文字是（）。 A．仰韶文化的陶文 B．甲骨文 C．金文 D．石鼓文 5．“三武灭佛”之后，（）成为中国佛教最为流行的宗派，它充分体现了华夏文化的特征。
英语专业考研英美概况自测题（一） British Survey Test Part I Geography 1. The total area of the U.K. is _____. A. 211,440 B. 244,110 C. 241,410 D. 242,534 2. England occupies the _____ portion of the U.K. A. northern B. eastern C. southern 3. The most important part of the U.K. in wealth is _____. A. Northern Ireland B. England C. Scotland 4. _____ is on the western prominence between the Bristol Channel and the Dee estuary. A. Wales B. Scotland C. England 5. Wales was effectively united with England in the _____ century. A. 14th B. 15th C. 16th 6. By the Act of Union of _____ Scotland and the kingdom of England and Wales were constitutionally joined as the Kingdom of Britain. A. 1707 B. 1921 C. 1801 7. Physiographically Britain may be divided into _____ provinces. A. 13 B. 12 C. 14 8. Mt. Ben Nevis stands in _____. A. the Scottish Highlands B. Wales C. England 9. The main rivers parting in Britain runs from _____. A. north to south B. south to north C. east to west 10. Cheviot hills lie along the border between _____ and England. A. Scotland B. Wales C. Vale of Eden 11. The longest river in Britain is _____. A. Severn B. Clyde C. Bann 12. London is situated on the River of _____. A. Parret B. Thames C. Spey 13. Edinburgh is the capital of _____. A. England B. Scotland C. Wales 14. The rivers flowing into the _____ are mainly short. A. North Sea B. English Channel C. Dee estuary 15. Mt. Snowdon stands in _____. A. Scotland B. Wales C. England 16. The source of the important River Thames is in the _____. A. Cotswolds B. Oxford Clay C. Pennines 17. About _____ of the water requirements are obtained from underground sources. A. 50% B. 38% C. 42% 18. Gaelic is mainly spoken in _____. A. Scotland B. England C. Northern Ireland 19. The Bank of England was nationalized in _____. A. 1964 B. 1946 C. 1694
山东经济学院2010--2011学年第 1学期期末试题 英美文化概况（110126）试卷（5） 注意事项：所有的答案都必须写在答题纸上，答在试卷上一律无效 Ⅰ. Decide whether the following statements are true (T) or false (F). （本大题共20小题，每小题1分，共20分） 1. Britain is both a parliamentary democracy and a constitutional monarchy. 2. The divine right of the king means the sovereign derived his authority from his subjects. 3. In Britain, Grammar schools select children at the age of 11 and provide them with a general education. 4. The Prime Minister and Cabinet decide on the general direction of Britain’s foreign policy. 5. The origin of Bowling lies in the victory celebration ceremony by the ancient warriors. 6. Americans have to join a political party in order to vote or to be a candidate for public office. 7. The Clinton Administration made national security, economic prosperity and promotion of democracy the three pillars of the American foreign policy. 8.It takes at least fours years to get a bachelor’s degree from an institution of higher learning in the US. 9. In Britain, Grammar schools select children at the age of 11 and provide them with a general education. 10. The president has the authority to appoint federal judges, and all such court appointments are subject to confirmation by the House of Representatives. 11.The main duty of the Congress is to make laws, including those which levy taxes that pay for the work of the federal government. 12.Most people in Scotland speak the old Celtic language, called “Gaelic” 13. When George W. Bush became President, his foreign policy has two prominent elements: isolationism and faith in military strength. 14. Harvard College was originally founded to train government officials. 15. There are about 60 members of the Commonwealth. 16. The state of Pennsylvania used to be inhabited by the Quakers. - 1 - （共页）
1. The official full name of the United States is usually referred to as . It is often called , , , , or simply , or the “” in American spoken English. 2. National Holiday of US is . 3. Nicknames for the flag include ,,, and which is also the name of the country's official national anthem. 4. served as the political theory behind the American Revolution. 5. On July 4, 1776, the Congress adopted the Declaration of Independence drafted by a committee including and , with most of the work done by . 6. By the Declaration of Independence the United States held its separate and equal position among the powers of the earth, and also by it the United States had been founded, based on the right “.” 7. The American Civil War was in fact a conflict during 1861-1865 in the USA between the Southern or of America and the Northern or . 8. Four great empires—, , , and —had disappeared by the end of WWⅠ. 9. American Attitudes towards WWⅡ were excitedly divided into who opposed any involvement in the European war, and who urged immediate aid to the Allies. 10. The Cold War was an ideological, political, and economic state of tensions, conflicts and hostility from 1945 to 1990 between the USSR and on the one hand, and the US and on the other. 11. The Berlin blockade promoted the signing of and the founding of . 12. is the only “hot war” between the USA and the Soviet Union during the Cold War period.
《英语国家社会与文化入门》模拟试题及参考答案 Part one Fill in the blanks ( 10 points ) 1.The full name of the United Kingdom is . 2.The Good Friday Agreement, known also as , emerged on 10 April 1998. 3., the ancestor of the present queen, Elizabeth II, united England under his rule in 829. 4.written by Geoffrey Chaucer is often studied by middle school and college students today. 5.The Bonfire Night, which is celebrated in November, sometimes is also called . 6.Columbus discovered the New World in the year of . 7.The Three Faiths in the US refer to Protestant, and Jewish. 8.In 1852, a New England woman named Harriet Beecher Stowe wrote a novel titled , which intensified the political debate on slavery. 9.1968 was known in US history as a violent and tragic year in which the great leader of The Civil Rights Movement: was assassinated. 10.The Grand Canyon is carved away for nearly 6 million years by the River. Part two Read the following unfinished statements or questions carefully. For each unfinished statement or question four suggested answers A, B, C and D are given. Choose the one you think best completes the statement or answers the question: ( 20 points ) 1.Franklin Roosevelt’s program for the depression was called . a. Progressivism b. laissez faire c. New Freedom d. New Deal 2. The United States did not join the Second World War directly until in December, 1941. a. Great Depression b. Pearl Harbor incident c. the Japanese attack on China d. the German attack on Poland 3. From 1649 to 1658 England was called a Commonwealth. It was ruled first by Oliver Cromwell as . a. Lord Protector b. Lieutenant General c. Commander of the New Model Army d. President 4. Ireland is in the of Great Britain. a. east b. south c. west d. north 5. WASPs referred to . a. the mainstream Americans b. Hispanics c. Asian-Americans d. Blacks 6. Lincoln's Emancipation proclamation and the Thirteenth Amendment to the Constitution formally ended . a. the immigration movement b. the Civil War
中国文化： 中国文化，是华夏文明为基础，充分整合全国各地域和各民族文化要素而形成的文化。不同于中华文化的国际属性，可以称之为“中国的文化”（中华人民共和国的文化）。受中华文明影响较深的东方文明体系被称为“汉文化圈”，特指社会意识形态，是社会政治、经济与科学技术发展水平的反映。从旧石器时代的发明创造，到康有为梁启超的维新变法到孙中山的民主革命无一不是推动社会向前发展的动力。 中国文化，依据中国历史大系表相传经历了有巢氏、燧人氏、伏羲氏、神农氏（炎帝）、黄帝（轩辕氏）、尧、舜、禹等时代，《先秦史》载：“吾国开化之迹，可征者始于巢、燧、羲、农。”；到中国第一个国家夏朝建立。发展至今，一个拥有灿烂文化的中国，带着丰富多彩的文化元素屹立在世界东方。 中国文化不但对日本、朝鲜半岛产生过重要影响，还对越南、新加坡等东南亚、南亚国家乃至美洲地区产生了深远的影响。中国发达的造船技术和航海技术以及指南针技术首先应用于航海，才导致了人类所谓蓝色文明和环太平洋文化圈的形成（李二和《中国水运史》）；郑和七下西洋更加深了这种文化的传播和辐射，并由此形成了世所公认的以中国文化为枢纽的东亚文化圈。随着中国国力的强盛，国际地位的提高，世界各国包括亚洲、欧洲在内的一些国家都对中国文化以给予了高度的认同和重视。 中国文化概况：
《中国文化概况》是一部书籍，是从文化角度架起一座沟通中西的桥梁，用英文将中国文化的概貌展现给读者,简要概括了中国的地理、历史、传统节日、少数民族、烹饪、茶酒文化、服饰、表演艺术、建筑以及中药、武术等方方面面的知识，分析了某些表象的深层次文化内涵，展示了祖国灿烂丰富的文化。 图书导语： 本书强调以学生为主体的教学理念,课文的内容有充分的扩展空间,练习的设计有利于学生展开讨论和思考。通过学习本教材可以使学生更加了解中国的文化底蕴,并学习到如何用英文表达,从而进一步增强学生在对外交流时的自信心 《高等学校英语拓展系列教程：中国文化概况》分为国家概况、文教科技、民俗风情和旅游览胜四大部分，主要介绍了中国的哲学、宗教、文学、艺术等方面的内容。每个章节后也增设了富有针对性和启发性的练习，有助于师生展开更深入的讨论和思考。 《高等学校英语拓展系列教程：中国文化概况》图文并茂，信息量大，适用于大中专院校的英语专业低年级选修课，大学英语公共课等。
英国概况 1，英国名称：The United Kingdom of Great Britain and Northern Ireland) 2，地理位置：Great Britain is the largest island of the British Isles, the largest island in Europe and the eighth-largest island in the world. It lies to the northwest of Continental Europe, with Ireland to the west, and makes up the largest part of the territory of the state known as the United Kingdom of Great Britain and Northern Ireland. It is surrounded by over 1,000[citation needed] smaller islands and islets. 或者回答British mainland western Europe from Great Britain and Ireland, north-east and many nearby islands， She east by the North Sea, the Atlantic Ocean to the west, up to the North Atlantic off Iceland, Yugoslavia and the European continent, separated only by a strip of water, the English Channel 3, 英国首都：London 4,组成部分：England, Scotland, Wales and Northern Ireland 5,民族：England Welsh、Scotch、Irish 6, 英国国旗：the Union Flag英国国歌：God Save The Queen 天佑女7，三次外族入侵：ⅠRoman Conquest；43AD, the roman empire