第七章图试题
一、单项选择题
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(ne)
D. O(n2)
15.设有向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为
（）。
A. O(nlog2e)
B. O(n+e)
C. O(ne)
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的最短路径为（）。
, 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 (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.在一个有向图的邻接矩阵表示中，删除一条边
A. O(1)
B. O(i)
C. O(j)
D. O(i+j)
28.与邻接矩阵相比，邻接表更适合于存储（）图。
A. 无向
B.连通
C.稀疏
D. 稠密图
29.设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是
（）。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n2)
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
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的邻接矩阵为
?
?
?
?
?
?
?
?
?
?
1
1
1
，则图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 = {
对图G进行广度优先搜索所得的所有序列为__________和___________。
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 如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V0开始的广度优先搜
索的结果。
2. 设连通图G 如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V0开始的深度优先搜索
的结果。
3. 设连通图G 如图所示。试画出从顶点V0出发的深度优先生成树，指出图G 中哪几个顶点是关节点（即
万一它失效则通信网络将发生故障）。
4. 设连通图G 如图所示，
(1) 如果有关节点，请找出所有的关节点。
(2) 如果想把该连通图变成重连通图，至少在图中加几条边如何加
V 54
V 6
8
V 54
V 6
8
V 54
V 6
8⑩
①
② ③
④
⑤
⑥
⑦
⑧
⑨
Y I 1
n 0k kj
ik ij b a c -==Y
5. 对于如图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树
6. 设有向图G 如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS 生成森林和
BFS 生成森林。
7. 表示图的另一种方法是使用关联矩阵INC[ ][ ]。其中，一行对应于一个顶点，一列对应于一条边。
因此，如果边j 依附于顶点i ，则INC[i][j]=1。如果ADJ 是图G =（V, E ）的邻接矩阵，INC 是关联矩阵，试说明在什么条件下将有ADJ = INC INCT I ，其中，INCT 是矩阵INC 的转置矩阵，I 是单位矩阵。两个n n 的矩阵的乘积 C = A B 定义为
公式中的 定义为按位加， 定义为按位乘。
设无向图G 如图所示。试画出该图的邻接矩阵和关联矩阵。
8. 设有一个连通网络如图所示。试按如下格式，应用Kruskal 算法给出在构造最小生成树过程中顺序选
出的各条边。
I 1
V 2
V 3
V 4
V 7 V 6
V 0
V 5
①
②
③
④
⑤
0 1 2
3 4 5 6 7
e 0 e 1 e 2 e 3 e 4 e 5 e 7
e 6 e 8 e 9
0 1 2
3 4 5
6 6 1 8
7 5
3 4 26
( 始顶点号，终顶点号， 权值 ) ( , , ) ( , , )
( , , ) ( , , ) ( , , )
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
执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8，搜索结果不唯一。
2. 图G 对应的邻接表为：
3 1 3 2 0 3 1 0 3 5 0 1
2
6
7 6 6 2 1 3 7 8 0 V 0 1 V 1 2 V 2 3 V 3 4 V 4 5 V 5 6 V 6 7∧ ∧ ∧ ∧
∧ ∧ ∧
∧
∧
g
f
e
c
a
b
d
执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。
3. 图G 中，从V0出发的深度优先生成树为：
图G 中的关节点为：V1, V2, V3, V6。
4. (1) 关节点为 ①, ②, ③, ⑦, ⑧
(2) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从 ③ 的子孙结点⑩到③的祖先结点①引一
条边，从 ② 的子孙结点 ④ 到根 ① 的另一分支 ③ 引一条边，并将 ⑦ 的子孙结点 ⑤、⑥ 与结点 ④ 连结起来，可使其变为重连通图。（解答不唯一）
5. 以顶点 ① 为根的深度优先生成树（不唯一）：
以顶点 ② 为根的广度优先生成树：
6. 深度优先生成森林为：
V 54
V 6 8
1
V 2
V 4V 7 V 6
V 5 ⑩
①
② ③
④
⑤ ⑥
⑦
⑧
⑨ ①
②
③
④
⑤
①
②
③
④ ⑤
①
②
③
④
⑤
广度优先生成森林为：
7. 当图中的顶点个数等于边的条数时，ADJ = INC*INCT-I 成立。
图G 对应的邻接矩阵为：
7
6543
2100111100010000100100001001000001010000010
0110000100011001000001107
6543210ADJ ?
?
?
??
?
??
?
????????????????
?=
对应的关联矩阵为：
8. 应用Kruskal 算法顺序选出最小生成树的各条边为： ( 始顶点号，终顶点号， 权值 ) ( 0, 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 )
( 3, 4, 5 )
9. 采用prim 算法从顶点0开始构造最小生成树的过程：
1
V 2
V 4V 7 V 6
V 5
7
6543
2101111
1000100000010001000000100010000001000100
00001100100000001101000000001198765432
1
0INC ??
?
??
?
??
?
???
?????????
?????=
10. 最小生成树及其邻接矩阵如图所示
选 择 的 边 去 掉 的 边
（顶点, 顶
点,
权值） （顶点, 顶
点,
权值）
（ 2 ,
1 ,
16 ） （ , , ）
（ 5 ,
1 ,
14 ） （ , , ）
（ 6 ,
1 ,
21 ） （ , , ）
（ 6 ,
2 ,
19 ） （ 6 , 1 , 21 ）
（ 6 ,
4 ,
11 ） （ , , ）
（ 6 ,
5 ,
26 ） （ 6 , 5 , 26 ）
（ 5 ,
4 ,
18 ） （ 6 , 2 , 19 ）
?????
?
??
?
?
?
?--
-------
∞∞-∞∞∞=02601118060
199502114
160Edge 111465
16①
②
⑤
④
③
⑥
14
16
5
6
11
（ 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
6543
2100000000010000000010000001000000000110000
00010
00000000100001010107
6543210?
?
?
??
?
??
?
?????
???????
????
?=Edge
12. 针对下图所示的AOE 网络
A0A3 A6
A7
A0A5
A6
A7
各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：
顶点123456
Ve01915293843
Vl01915373843
各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：
边<1,2><1,3><3,2><2,5><3,5><2,4><4,6><5,6>
Ee00151915192938
El170151927273738
如果活动k的最早可能开始时间Ee(k) 与最迟允许开始时间El(k)相等，则该活动是关键活动。本题的关键活动为<1,3>, <3,2>, <2,5>, <5,6>，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。
整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。
13.带权有向图如图所示：
应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：
14. 图G 为 可能的施工顺序有： p1, p2, p4, p3, p5, p6 p1, p4, p2, p3, p5, p6
p4, p5, p1, p3, p2, p6
15. 该图的强连通分量分别为：
五、算法分析题
1. 已知有向图的邻接矩阵表示及其一个算法描述如下：
p1p6
p4
const int MaxVertices = 5;
dj; p != NULL; p = p->link ) {
};
4.已知有向图的邻接表类的表示的形式描述如下：
struct Edge { dj;
while ( (1) ) {
p = p->link;
if ( p == NULL ) break;
}
if ( p != NULL ) (2) ;
}
return deg;
}
5.已知有向图的邻接表类的表示的形式描述如下：
struct Edge { dj;
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 ata = 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 dj;
while ( p != NULL ) {
A->arr[i][p->dest] = ___ __(2)__________;
________________(3)________________;
}
}
}
8.已知图的邻接表和逆邻接表的形式描述如下：
struct Edge { ata = NodeTable[i].data;
OppositNodeTable[i].adj = NULL;
}
for ( i = 0; i < NumVertices; i++ ) {
p = NodeTable[i].adj;
while ( p != NULL ) {
q = new Edge;
q->dest = i;
q->cost = p->cost;
_________ ____(1)____ _________;
OppositNodeTable[p->dest].adj = q;
______________(2)_____________;
}
}
}
参考答案：
(1)
。dj = p->link;
ata dj
NodeTable[i].adj = NULL;
}
cin >> NumEdges;
for ( i = 0; i < NumEdges; i++ ) { dj;
NodeTable[k].adj = p;
}
}
1.算法实现如下
template
《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 识图题专题训练 1、下图表示淀粉、脂肪和蛋白质在消化道中各部位(依次A、B、C、D、F表示)被消化的程度。 (1)图中哪条曲线表示脂肪的消化过程。 (2)淀粉、脂肪和蛋白质各在消化道的哪个 部位开始被消化？ (3)D中含有哪些消化液？ 2、你和你的同龄人正步入 一生中最重要的生长发育 时期——青春期。在青春 期，男女同学的身高、生 理和心理等方面都发生着 显著的变化，你感受到这些变化了吗？请分析图六并回答下列问题。 ⑴从图六-A的曲线可知进入青春期后，青少年的身高生长速度， ⑵从图六-B的曲线可知进入青春期后，男性的和女性的卵巢迅速发育。 ⑶从图六中可知女性进入青春期的平均年龄比男性来得。 3、下图为女性生殖系统的一部分。据图回答：X Kb 1. C o m (1)精子与卵细胞结合形成受精卵是在图中数 字所示的结构内。 (2)受精卵不断地进行分裂，形成并且埋人图中数字所示的结构内。 (3)胎儿成熟后从图中数字所示的结构排出体外的过程 叫。 4、取5毫升新鲜血液，立即注入盛有5%柠檬酸钠溶液的量筒中，轻轻振荡量筒，静置数小时后，出现如图所示现象，请根据实验的方法步骤和图中所示现象回答： （1）量筒中出现了现象。w W w .x K b 1.c o M （2）量筒中1、2、3三层的物质依次是、、，2、3层的细胞总称为。 （3）本实验证实了血液的成分包括和两部分。（4）量筒里放入柠檬酸钠的目的是。 5、下图为人的消化系统关系图，椐图填空（[ ]内填序 号，横线上填名称）： （1）、[ ] 是消化系统的开始。人体的消化系统 由和组成。 （2）、人体的外消化腺中最大的消化腺是[ ] 。它 分泌的胆汁，可以有利于帮助消化。 （3）、[ ] 是消化和吸收营养物质的主要场所。 （4）、小明早餐吃了一个馒头，馒头中营养物质淀粉在[ ] 开始被消化。 6、下面右边是一滴血在显微镜视野中的示意图。已知正常人红细胞的含量为(4.2-5.0)×1012个/L，白细胞为(4-10)×109个/L，白细胞个体一般较红细胞大。请据图回答问题（“[ ]”中填写序号，“”内填写 文字。）新课标第一网 数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 2004-2005学年度第二学期单元测试题 七年级生物下册 第一单元（人体的营养/人体内的物质运输） 班级：姓名：座号：评分： 一、单项选择题（每题2分，共40分） 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、小肠长约5-6米 B、粘膜表面有许多皱襞和小肠绒毛 C、小肠绒毛中有毛细血管和毛细淋巴管 D、小肠壁内有肠腺 7、人体消化食物和吸收营养物质的主要场所是 A、食道 B、胃 C、小肠 D、大肠 8、某护士将葡萄糖针剂从病人的前臂静脉输入体内，当葡萄糖流经肺泡的毛细血管 时，所经过的途径是：a上腔静脉 b 下腔静脉 c 右心房 d 左心室 e右心室 f 左心房g肺静脉h 肺动脉 A 、a c e h B、b c f g C、a d g c D、bcef 9. 甲状腺有很强的吸碘能力,用放射性碘注入肱静脉后,首先测到放射性碘的是 A、主动脉 B、甲状腺静脉 C、肺动脉 D、肺静脉 10、将10毫升血液放入盛有少量抗量抗凝剂的试管中，静置一段时间以后，分为上、 下两部分。在上、下两部分的交界处是 A、呈暗红色的红细胞 B、呈淡黄色的血浆 C、呈白色的白细胞 D、呈白色的白细胞和血小板 11、红细胞的形态为 绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。 一、定义与术语 图：无序数据结构 基本构成：1.边集（Edge ）：a. 有向图，有向边 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 七年级下册生物识图题 1 [ 1 ] 卵巢，作用是__产生卵细胞和分泌雌性激素； ）精子和卵细胞结合的场所是输卵管。（3）胚胎发育的场所是子宫。 （4 后通过__胎盘和脐带___从母 氧。 程卵细胞从卵巢产生并排 除，输卵管中与精子细胞结合 形成受精卵 （6）胎儿发育 266 天发育成 熟，成熟的胎儿和胎盘从母体阴道排出体外的过程叫分娩 2、图中的曲线表示食物通过消化道时，糖类、蛋白质和脂肪被消化过程中数量的变化，分析并回答下列问题： （1）甲表示（脂肪）的消化曲线， 因为其到了（小肠）才开始消化。 （2）丙表示（蛋白质）的消化曲 线，因为其在（胃）就开始消化。 （3）这三种营养物质在（小肠）中 都可以被消化，而在（咽、食道和 大肠）中则都不能被消化。 内被消化成甘油和脂肪酸、 葡萄糖、氨基酸 试管编号注入浆 糊 加清 水 加入唾 液 振荡摇 匀 放在37 ℃水中恒 温 冷却后加碘 液 现象 12亳升2亳升0亳升10分钟2滴 22亳升0亳升2亳升10分钟2滴 (1)1号试管内的浆糊(淀粉)，未加唾液，淀粉未被唾液淀粉酶酶分解，所以淀粉遇碘显蓝色。 (2)2号试管内因为加了唾液，唾液淀粉酶在适宜的温度下将淀粉分解成了葡萄糖，所以，加碘液后不变蓝。 4 1.写出各部分的名称：1）口腔 2）食道 3）胃 4）胰 5）小肠 6）大肠 10）肝脏 吃下去的鸡蛋在（3 ）胃开始被消化，被 （5 ）小肠吸收。 某人因患急性阑尾炎，须开刀切除的器官是 14 阑尾 消化酶。该结构是（10 ）肝脏，分泌的消 化液为胆汁。 5.消化系统是由消化道和消化腺组成， 其中小肠是吸收的主要器官，原因是长、 皱襞和小肠绒毛、绒毛中丰富的毛细血管。营 养物质在消化道内经过消化，最终被分解成氨基 酸、葡萄糖等能被人体吸收的营养物质。 5、下图是呼吸系统的模式图，请据图回答下列问题。 （ A__鼻__；B__喉__；C_支气管___；D__肺 __；F_气管__。 ___肺泡__构成的，是__呼吸体 统___的主要器官。 容易在肺泡和___毛细血管___之间进行气 体交换。 （4）H和D内的气体经呼吸道排出体外时， 胸廓的大小变化是__变小____。 （5）鼻涕是由__鼻腔__形成的，痰液是由 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D ????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 七年级下册生物识图题 1、下图是女性生殖系统示意图，请据图回答问题：产生卵细胞和分泌雌性激11 ] ）女性的主要性器官是__[ 卵巢，作用是（素； （2）精子和卵细胞结合的场所是输卵管。 （3）胚胎发育的场所是子宫。 （）胚胎发育成胎儿后，最后通_胎盘和脐___从体中获得所需的营养物质和氧。（5）看图描述受精的大致过程卵细胞从卵巢产生并排除，输卵管中与精子细胞结合形成受精卵 （6）胎儿发育 266 天发育成熟，成熟的胎儿和胎盘从母体阴道排出体外的过程叫分娩 2、图中的曲线表示食物通过消化道时，糖类、蛋白质和脂肪被消化过程中数量的变化，分析并回答下列问题： （1）甲表示（脂肪）的消化曲线，因为其到了（小肠）才开始消化。（2）丙表示（蛋白质）的消化曲线，因为其在（胃）就开始消化。 （3）这三种营养物质在（小肠）中都可以被消化，而在（咽、食道和大肠）中则都不能被消化。 （4）甲、乙、丙三种物质在消化道内被消化成甘油和脂肪酸、 葡萄糖、氨基酸 3、根据下表列出的实验方法步骤，填写实验现象，再根据实验现象分析原因。试管编注入浆加清加入唾振荡摇放在37 ℃水中恒冷却后加碘现象号糊水 液匀温液 12亳升2亳升0亳升10分钟2滴 1． 滴2亳升20亳升2亳升10分钟2 唾液淀粉酶，淀粉未被 ((1)1号试管内的浆糊淀粉)，未加唾液蓝色。酶分解，所以淀粉遇碘显酶在适宜的温度下唾液 (2)2号试管内因为加了， 唾液淀粉 液后不变蓝。分解成了麦芽糖，所以，加碘将淀粉 、下图是消化系统的结构图，据图回答问口写出各部分的名称：1 ）食 肝大小肠 1 开始被消化，吃下去的鸡蛋在23 小吸收5 143某人因患急性阑尾炎，须开刀切除的器官阑但分泌的消化液不4对食物的消化有重要作用，，分泌的消肝脏10 ）消化酶。该结构是（胆汁。化液为组成，消化道5.消化系统是由和消化腺长、是吸收的主要器官，原因是其中小肠。营皱襞和小肠绒毛、绒毛中丰富的毛细血管氨基养物质在消化道内经过消化，最终被分解成等能被人体吸收的营养物质。酸、葡萄糖 5、下图是呼吸系统的模式图，请据图回答下列问题。 ）填写图中结构的名称：（1肺C___B____鼻；喉；支气管D_____；A__F_；气 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 2016-2017学年七年级（下）生物试卷 一、选择题（共40分，每小题一分） 1. 下列生物由细胞构成的是（） A. ①③④⑤ B. ①②③⑤ C. ②③④⑤ D. ①②④⑤ 2. 下列不属于细胞基本结构的是（） A. 细胞壁 B. 细胞膜 C. 细胞核 D. 细胞质 3. 克隆又称“体细胞的无性繁殖”．如图是克隆羊多利的身世示意图，请问多利的外貌最像谁（） A. A羊 B. B羊 C. C羊 D. A、B、C三种羊的一部分 4. 下列关于多细胞生物体细胞分裂和分化的叙述中，错误的是（） A. 细胞分裂的结果是使细胞数目增多 B. 细胞分裂过程中细胞核和细胞质都要分成两份 C. 细胞分化过程中，细胞中的遗传物质将逐渐减少 D. 细胞分化的结果产生了组织 5. 细菌的生殖方式是分裂生殖，如果1个细菌连续经过5次分裂，则可形成细菌个数是（） A. 16 B. 32 C. 24 D. 62 6. 如图①→④主要表示了变形虫细胞的分裂过程示意图，下列有关该过程说法错误的是 （） A. 细胞核先一分为二，然后细胞质再一分为二 B. 一个变形虫经过一次分裂形成两个变形虫 C. 新形成的细胞与原来细胞的遗传物质不能保持连续性和稳定性 D. 若①中染色体为a条，则它在分裂过程中的变化为： 7. 如图中属于神经组织的是（） A. B. C. D. 8. 一个成熟的西瓜是一个（） A. 胚 B. 体细胞 C. 器官 D. 生殖细胞 9. 桃树与家兔在结构层次上的不同点是桃树没有（） A. 细胞 B. 组织 C. 器官 D. 系统 10. 位于人胸腔内的器官是（） A. B. C. D. 11. 下列不属于器官的是（） A. 血液 B. 脑 C. 小肠 D. 皮肤 12. 夏天的早晨，在乡村，常常可看见养鱼人用水泵抽水，将水喷入鱼塘，其目的是（） A. 搅动水体，使饵料分散 B. 促使鱼多运动，不生病 C. 振动水面和空气，增加水体含氧量 D. 驱赶鱼群向四周散开，充分利用水体 13. 人体的八大系统中，具有调节人体生理活动功能的是（） A. 神经系统 B. 内分泌系统 C. 泌尿系统 D. A、B两项 14. 菠菜放入沸水中，水变成绿色，若放入清水中浸泡，水不会变成绿色，这是因为活细胞 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。七年级下册生物识图题专题训练
数据结构试卷带答案
数据结构模拟试题及答案
七年级生物下册第一单元测试题
数据结构考试题库
数据结构--图重点
《数据结构C》模拟试题
七年级下册生物识图题
数据结构考试题库含答案
数据结构-图习题
《数据结构》模拟试卷一及答案
人教版七年级下册生物识图题答案
数据结构试题及答案
数据结构模拟试卷(含答案)
七年级下生物试题
数据结构试题(含答案)
数据结构图习题
相关主题
文本预览