数据结构试题集（包含答案 - 完整版）

4、写出下面算法的功能。

void function(Bitree *t){ if(p!=NULL){

function(p->lchild); function(p->rchild); printf(“%d”,p->data);

} }

答案：二叉树后序遍历递归算法 五、综合题

1、假设以有序对表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{,,,,,,,,,},请回答下列问题：

（1）哪个结点是根结点？ （2）哪些结点是叶子结点？ （3）哪些结点是k的祖先？ （4）哪些结点是j的兄弟？ （5）树的深度是多少？。

2、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

3、假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。

10001B 101A 00038010621C 10000170121G032301ED 1001E 11F 10001G 01H 0017A10H01116D19B50123CF答案： 4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

答案：二叉树形态

ABCEDFGH

5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答案：

301218743125116

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。 答案：(1)树形态：

321367919105523

(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79

7、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。

ABDGJEHKILCF答案：

8、一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，

1，完成问题：

（1）设计一棵哈夫曼树；（画出其树结构） （2）计算其带权路径长度WPL； 答案：(1)树形态：

6430341618995413

(2)带权路径长度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129

9、已知某森林的二叉树如下所示，试画出它所表示的森林。

ABCEDHFG ADCEGFH答案：

B

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

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

ABCDIJMNEFGKL

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

FDBEGIHACHJ 答案：先序：FDBACEGIHJ

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

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

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

if(t!=NULL)

{*n++;

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

}

第七章 图

一、选择题

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

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

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

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

A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 4、下面（ ）可以判断出一个有向图中是否有环（回路）。

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