2004年数据结构考研真题答案及解析

本文提供2004年数据结构考研真题答案及解析，以下为具体内容

1、下面关于二叉树的结论正确的是（ ）。

A、二叉树中，度为0的结点个数等于度为2的结点个数加1

B、二叉树中结点个数必大于0

C、完全二叉树中，任何一个结点的度或者为0，或者为2

D、二叉树的度是2

2、连通的无向图G有n个顶点，则图G的最小生成树的边数为（ ）。

A、n

B、n-1

C、n*(n-1)/2

D、n/2

3、从堆中删除一个元素的时间复杂度为（ ）。

A、

B、

C、

D、

4、对任意一棵树，设它有n个结点，这n结点的度数之和为（ ）。

A、n

B、n-2

C、n-1

D、n+1

5、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（ ）。

A、在树T中，X是其双亲的第一个孩子

B、在树T中，X一定无右边兄弟

C、在树T中，X一定是叶子结点

D、在树T中，X一定有左边兄弟

1、试题答案：A

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--二叉树的性质。
【解析】
A：树中存在这样一个等量关系：结点总数等于总度数+1。那么在二叉树中，有n0+n1+n2=n1+2n2+1，化简得n0=n2+1，度为0的结点个数等于度为2的结点个数加1。A中说法正确。
B：二叉树是一个有限的结点集合，这个集合或者为空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树构成。由二叉树的定义可知，二叉树中可以是一棵空树，即结点个数可以为0。B中说法错误。
C：完全二叉树中最多可以有1个度为1的结点。C中说法错误。
D：二叉树的度可以是0、1、2。D中说法错误。
综上所述，本题选A。

2、试题答案：B

试题解析：

【考点】本题考查数据结构--图--最小代价生成树。
【解析】最小生成树是指一个无向图的生成树中，所有边的权值和最小的生成树。对于一个有n个顶点的连通无向图，其最小生成树一定包含n-1条边，即少一条边就不能构成一棵树，多一条边就必然存在环，不符合生成树的定义。故本题选B。

3、试题答案：B

试题解析：

4、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树。
【解析】树中某个结点的子树个数的个数称为该结点的度。除了根结点以外，每一个顶点都有唯一条边和它的双亲结点相连接，所以树中n个结点的度数之和为n-1。故本题选C。

5、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--树转换为二叉树。
【解析】树转二叉树的过程遵循“左孩子右兄弟”原则，那么二叉树中某一结点是其双亲的右孩子，则说明其双亲是它的左兄弟。故本题选D。