难度系数及复杂系数说明：
难度系数从易到难分别为：N1、N2、N3、N4、N5 复杂系数从简到繁分别为：F1、F2、F3、F4、F5
数据结构第三阶段作业
第6章 树和二叉树
6.1 单项选择题
1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。（N2F1）
A. 正确 B. 错误 2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。 （N2F1）
A．15 B．16 C．17 D．47
3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。（N2F1）
A. 3 B. 4 C. 5 D. 6
4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。（N3F1）
A. 5 B. 6 C. 30 D. 32
5. 深度为5的二叉树至多有__C__个结点。（N2F1）
A. 16 B. 32 C. 31 D. 10
6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _A__。 （N3F1）
A. 2h B. 2h-1 C. 2h+1 D. h+1
7. 对一个满二叉树，m个树叶，n个结点，深度为h，则_D___ 。（N3F1）
A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1
8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。（N3F1）
A.不发生改变 B.发生改变 C.不能确定 D.以上都不对
9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_C___。（N3F1）
A. uwvts B. vwuts C. wuvts D. wutsv 6.2 简答题
1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。（N2F3）
1
2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。（N3F2）
请画出该树。
3. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度。（N3F3）
4. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少? （N3F2） 最大深度：h=N-k+1,最小深度：logkN+1
第7章 图
7.1 单项选择题
1．在一个图中，所有顶点的度数之和等于所有边数的__C__倍。（N3F1）
A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树 B 。（N3F1）
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。（N3F1）
A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有_C___条边。（N2F1）
A. n B. n(n-1) C. n(n-1)/2 D. 2n
2
5．具有4个顶点的无向完全图有__A__条边。（N2F1）
A. 6 B. 12 C. 16 D. 20
6．具有6个顶点的无向图至少应有_A___条边才能确保是一个连通图。（N3F1）
A. 5 B. 6 C. 7 D. 8
7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要_C___条边。（N3F1）
A. n B. n+1 C. n-1 D. n/2
8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_A___。（N3F1）
22
A. n B. (n-1) C. n-1 D. n
9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①_A__；所有邻接表中的接点总数是_②_C__。（N3F1）
① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e
10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为D__①_B_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。（N3F1）
① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b
a
c b e
f d
图 7.1 一个无向图 7.2 综合题
1．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （N3F3）
（1） a 16 15 11
b 15 c 15 d
14 16 12 13 21 f e
图7.6
3
（2）
2 6 12 1 4 3 9 12 7 5 图7.7 15 6 16 20 4 132 5 10
2．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。（N3F3）
图7.9
b 6 a 3 c 4 2 3 2 5 5 d 3 f e 4
3．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下： (1)请画出该AOE图。
(2)计算完成整个计划需要的时间。 (3)求出该AOE网的关键路径。（N4F4） 6 4 5 ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 9 7 ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 答：(1)该AOE图为：
(2)完成整个计划需要18天。 (3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，）
第8章 查找
8.1 单项选择题
1.顺序查找法适合于存储结构为__B__的线性表。（N2F1）
A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储
2.对线性表进行二分查找时，要求线性表必须_C___。（N2F1）
A. 以顺序方式存储 B. 以链接方式存储
5
数据结构第三次作业(12.6)
