数据结构自测题及解答

一、概念题（每空0.5分，共28分）

1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2．由３个结点所构成的二叉树有 种形态。

3．一棵深度为6的满二叉树有 个分支结点和 个叶子。 4．一棵具有２５７个结点的完全二叉树，它的深度为 。

5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。 6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。

8．设一棵完全二叉树有700个结点，则共有 个叶子结点。

9.设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。

10.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度为 。 11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。 12.中序遍历的递归算法平均空间复杂度为 。

13.二叉树通常有______存储结构和______存储结构两类存储结构。

14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：

（1） 若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2） 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为

______。

（3） 若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 15. 每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。

16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。

17.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。

18.二叉树有不同的链式存储结构，其中最常用的是________与________。

19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。

20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 21.树的结点数目至少为________，二叉树的结点数目至少为________。 22.树的主要遍历方法有________、________、________等三种。 23.由________转换成二叉树时，其根结点的右子树总是空的。

24.哈夫曼（Huffman）树是带权路径长度________的树，通常权值较大的结点离根________。 25.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 。 26. n个结点的线索二叉树中的线索数目为 。

27.用数组[1..n]存放d堆，对于位于i的节点项，其父节点为 ；子节点为 。

二、选择题（每空1分，共15分）

（ ）1． 不含任何结点的空树 。

（Ａ）是一棵树; （Ｂ）是一棵二叉树;

（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树

第 1 页 共 8 页

（ ）2．二叉树是非线性数据结构，所以 。

（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; （Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构

都不能使用

（ ）3. 具有n(n>0)个结点的完全二叉树的深度为 。

(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(n)+1?

（ ）4．把一棵树转换为二叉树后，这棵二叉树的形态是 。

（Ａ）唯一的 （Ｂ）有多种

（Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子

5. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m≥0）个 B 的集合T1，T2，?，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的 C 。 供选择的答案

A： ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上 B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交 C： ①权 ② 维数 ③ 次数 ④ 序 答案：A= B= C=

6. 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。 供选择的答案 A： ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构

B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟 C～D： ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟

⑤ 最左的兄弟 ⑥ 最右的兄弟

答案：A= B= C= D＝

7. 一个有n个结点的树上有多少个分支 （ ）

Ａ n个 Ｂ n-1个 Ｃ n+1个 Ｄ 不能确定

8. 一个有n个叶子结点的哈夫曼树的节点总数为 （ ）

Ａ 2n个 Ｂ 2n-1个 Ｃ 2n-2个 Ｄ 不能确定

9. 对一个森林的遍历，下列说法错误的是 （ ） A一个森林的前序遍历序列，与其对应的二叉树的前序遍历序列是一致的。 B一个森林的中序遍历序列，与其对应的二叉树的中序遍历序列是一致的 C一般对一个森林的遍历，没有后根遍历法

D一个森林的层次遍历序列，与其对应的二叉树的层次遍历序列是一致的

第 2 页 共 8 页

10. 以下说法错误的是 ( ) A一般在哈夫曼树中，权值越大的叶子离根结点越近 B哈夫曼树中没有度数为1的分支结点

C若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点

D 若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树

三、综合题（1-9每题3分，10-12每题10分,共57分） 1．给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树B。

28

25 33 2. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

40 60 08 54 55

3．试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

4. 把如图所示的树转化成二叉树。

5. 编写递归算法，计算二叉树中叶子结点的数目。

6. 写出求二叉树深度的算法。

7. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。 8．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

9. 画出一次一个地将10、12、1、14、6、5、8、15、3、9、7、4、11、13和2插入一个初始

第 3 页 共 8 页

为空的最小堆的结果。

10．改写Binary heap的insert函数，在0号数组元素中存放插入项的副本。

11.画出依序依次将关键字1到15插入初始为空的左堆的结果。

12.Suppose you have a binary tree whose data fields are single characters. When the data fields of the nodes are output in inorder, the output is ABCDEFGHIJ, and when they are output in preorder, the output is ADBCJGFEHI. Draw the binary tree showing the data in each node and the pointers between nodes.

第 4 页 共 8 页

参考答案

一、概念题（每空0.5分，共28分） 1、 分支层次、根、直接前趋 2、 5

3、 31 32 4、 9

5、 2i-1 2 k-1 6、 n2+1

7、 最大值、完全

8、 350 （[n/2]＝350） 9、 500 499 1 0 10、 n 2 11、 L R N F E G H D C B 12、 O(n) 13、 顺序、链式 14、 根、?i/2?、左孩子、右孩子、2i、右孩子、2i+1

15、 根 16、 指向该结点的一个孩子、空指针NULL 17、 2n、n-1、n+1 18、 二叉链表、三叉链表 19、 第一 20、 左子树、右子树、左子树、右子树 21、 1、0 22、 先根遍历、后根遍历、层次遍历 23、 树 24、 最短、较近 25、 33 26、 n+1

27、 父节点?i?d?2/d?；子节点(i?1)d?2、……、id?1

二、选择题（每空1分，共15分）

1. C 2. C 3. C 4. A 5. A=① B=① C=③ 6. A=② B=① C=① D=③ 7.B 8. B 9. D 10. D

三、综合题（1-9每题3分，10-12每题10分,共57分） 1．

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

D

A

C F E G

B H I

第 5 页 共 8 页

本文来源：https://www.bwwdw.com/article/hudt.html