数据结构试题集（含答案）

ABCEDHFG ADCEGFH答案：

B

10、有一分电文共使用5个字符;a,b,c,d,e，它们的出现频率依次为4、7、5、2、9，试构造哈夫曼树，并给出每个字符的哈夫曼编码。 答案：

11、画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。

ABCDIJNEFGKLMH

29

答案：

12、如下所示的二叉树，请写出先序、中序、后序遍历的序列。

FDBEGIACHJ 答案：先序：FDBACEGIHJ

中序：ABCDEFGHIJ 后序：ACBEDHJIGF 六、编程题

1、编写求一棵二叉树中结点总数的算法。 答案： （以先序遍历的方法为例）

void count_preorder(Bitree *t, int *n) {

if(t!=NULL)

{*n++;

count_preorder(t->lchild); count_preorder(t->lchild); }

}

30

第七章 图

一、选择题

1、12、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）。

A. n B. n2 C. n-1 D. (n-1)2

2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ）。

A. 完全图 B. 连通图 C. 有回路 D. 一棵树 3、关键路径是事件结点网络中（ A ）。

A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路

4、下面（ B ）可以判断出一个有向图中是否有环（回路）。

A. 广度优先遍历 B. 拓扑排序

C. 求最短路径 D. 求关键路径

5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ B ）。 A. 第i行非无穷的元素之和 B. 第i列非无穷的元素个数之和

C. 第i行非无穷且非0的元素个数

D. 第i行与第i列非无穷且非0的元素之和

6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（ B ）。

A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 7、无向图的邻接矩阵是一个（ A ）。

A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵

8、当利用大小为N的数组存储循环队列时，该队列的最大长度是（ B ）。

A. N-2 B. N-1 C. N D. N+1 9、邻接表是图的一种（ B ）。

A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构

10、下面有向图所示的拓扑排序的结果序列是（ B ）。

A. 125634 B. 516234 C. 123456 D. 521643

132564

11、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（ A ）。

A. 顶点序列 B. 边序列

31

C. 权值总和 D. 边的条数

12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ A ）邻接点。

A. 入边 B. 出边 C. 入边和出边 D. 不是出边也不是入边

13、设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1?V2,E1?E2则称（ A ）。

A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量

14、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（ B ）。

A. 将邻接矩阵的第i行删除 B. 将邻接矩阵的第i行元素全部置为0 C. 将邻接矩阵的第i列删除 D. 将邻接矩阵的第i列元素全部置为0 15、任一个有向图的拓扑序列（ D ）。

A.不存在 B. 有一个 C. 一定有多个 D. 有一个或多个

16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。

A. 1/2 B. 1 C. 2 D. 4 17、下列关于图遍历的说法不正确的是（ C ）。

A. 连通图的深度优先搜索是一个递归过程

B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法 D. 图的遍历要求每一顶点仅被访问一次

18、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中：（ D ）。

A. 第i行非?的元素之和 B. 第i列非?的元素之和

C. 第i行非?且非0的元素个数 D. 第i列非?且非0的元素个数 19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ D ）。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层次遍历

20、一个具有n个顶点的有向图最多有（ B ）条边。

A. n×(n-1)/2 B. n×(n-1) C. n×(n+1)/2 D. n2

21、已知一个有向图的邻接表存储结构如图所示，根据深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ C ）。

123452445324

A. v1,v2,v3,v5,v4

B. v1,v2,v3,v4,v5

32