数据结构习题

发布时间 : 星期日 文章数据结构习题更新完毕开始阅读

A.1234567 B.1245367 C.4251637 D.452673l

13.具有65个结点的完全二叉树的高度为( )。(根的层次号为0) A.8 B.7 C.6 D.5

14.对某二叉树进行前序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序周游的结果为( ) A.DBFEAC B.DFEBCA C.BDFECA D.BDEFAC 15.Huffman树的WPL 是指( )。

A.除根以外所有结点的权值之和 B.所有结点权值之和 C.各叶子结点的带权路径长度之和 D.根结点的值

16.在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )

A.4 B.5 C.6 D.7 17.将一棵有 100个结点的完全二叉树,从根这一层开始,每一层从左到右依次对结点编号,根据点的 编号为1,则编号为49的结点的双亲的编号为 。 A.24 B .25 C .23 D无法确定

18.深度为6(根据的层次为1)的二叉树至多有 结点。 A .64 B.63 D.31 D.32 19.设二叉树有 n个结点,则其深度为____ 。 A .n-1 B. n C .㏒2n D. 无法确定

20. 设森林T中有三棵树,第一、第二、 三棵数的活结点个数分别为n1 n2 n3 ,那么将森林转换成二叉树后,其根结点的右子树上有_______ 个结点。 A .n1-1 B.n2+n 3 C .n1 +n2+n3 D.n1

21.设森林T中有三棵树,第一,二,三棵数的结点个数分别为 n1,n2,n3,那么将森林转换成二叉树后,其根结点的左子树上有_____个结点。

A .n1-1 B.n2+n3 C.n1+n2+n3 D.n1

22. 设深度为K的二叉树上只有度为0或度为2的结点,则这类二叉树上所含结点总数至少_______。 A .K+1 B.2K C2K—1 D2K+1 23.树转换成二叉树后,以下结论正确的是_______ 。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 C. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同

29

D. 以上都不对

24.某二叉树的前序遍历结点访问顺序为ABDGCDFH,中序遍历结点访问顺序为DGBAECHE,则其后续遍历结点访问顺序为__________ 。

A. BDGCEFHA B. GDBECFHA C. BDGAECHF D. GDBDHFCA 25. 在一棵非空二叉树的中序遍历序列中,根结点的右边_______ 。 A. 只有右子树上的所有结点 B. 只有右子树砂锅内的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点

26. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_______ 。 A. 不发生变化 B. 发上变化 C. 不能确定 D. 以上都不对

二、填空题

1.在一棵树中, 结点没有前驱结点,______结点没有后继结点。

2.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) ),结点f的层数为______。假定根结点的层数为0。结点k的所有祖先的结点数为 个。 3.在二叉树的第i层上至多有 结点。

4.具有n个结点的完全二叉树的深度为 。深度为k的二叉树的总结点数至少为 ,至多为 。

5.有n个结点的二叉链表中的空链域有_____ 个。

6.二叉树的第i层上至多有 个结点;具有n个结点的完全二叉树的深度为 。

7. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树,则该二叉树中树根结点肯定没有________子女。 8.已知一颗完全二叉树中共有768结点,则该树中共有_____个叶子结点。

9. 假定一棵树的嵌套括号表示法为 A ( B ( E ), C ( F ( H , I , J ), G ), D ),则该树的度为______,树的深度为_____,终端点的个数为____,但分支结点的个数为_____,双分支结点为_____,三分支结点的个数为______, C 结点的双亲结点为_________,其孩子结点为__________和为_________结点。

10.设 F 是一个森林, B 是由 F 转换得到的二叉树, F 中有 n 个非终端结点,则 B 中右指针字段为空的结点有____________。

11.对于一个具有 n 个结点的二叉树,当它为一棵二叉树时,具有最小高度,即为________ ,但它一棵单支时具有最大高度,即为___________ 。

30

12.对于一个具有 n 个结点的二叉树,当它储存在二叉树表中时,其指针字段的总数为______ 个,其中________个用于链接孩子点,_____________个空闲,

13.一棵深度为 K 的满二叉树结点总数为___________ ,一棵深度为 K 的完全二叉树的结点总数的最小值为________,最大值为____________。

14.如果 T2 是由有序树 T 转换而来的二叉树,那么 T 中结点的前序是 T2 中结点的 _______序。 15.具有 n 个结点的完全二叉树,若按层次从上到下 、从左到右对其编号(根结点为 1号),则编号最大的分支结点序号为_______ ,编号最小的分支结点序号为_______ ,编号最大的叶子结点序号为________ ,编号最小的叶子结点序号为___________ 。

16.有 m个叶子结点的哈夫曼树,其结点总数为________________ 。 17. 由三个结点构成的二叉树,共有_____________种不同的结构。

三、判断题

1.具有n个结点的完全二叉树的高度为?log2n??1。 2.有n个结点的不同的二叉树有n!棵。

3.在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。 4.完全二叉树的某结点若无左孩子,则它必是叶子结点。

5. 在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行中序遍历和后序遍历,则具有相同的结果。

6.由树转化成二叉树,其根的右子女指针总是空的。

7.对于一棵具有n个结点,其高度为h的二叉树,进行任一种次序遍历的时间复杂度为O(h)。 8.在霍夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应当特殊处理。 9.二叉树的中序和后序遍历序列可以唯一确定一棵二叉树。

四、应用题

1.假设一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D),回答下列问题:

(1)该树的度(2)树的深度(3)终端结点的个数(4)单分支结点的个数(5)双分支结点的个数(6)三分支结点的个数(7)C结点的双亲(8)C结点的孩子结点

2. 已知一棵树边的集合为{< I , M >,< I , N >,< E , I >,< B , E >,< B , D>,< A , B>,< G , J >,< G , K>,< C , G>,< C , F>,< H , L>,< C , H>,< A , C >},画出这棵树,并回答下列问题: ? 哪个结点是根结点? ? 哪些结点是叶子结点?

31

? 哪个结点是结点 G 的双亲结点? ? 哪些结点是结点 G 的祖先结点? ? 哪些结点是结点 G 的孩子结点? ? 哪些结点是结点 E 的子孙结点?

? 哪些结点是结点 E 的兄弟结点?哪些是结点 F 的兄弟结点? ? 结点 B 和 N 的层次分别是多少? ? 树的深度是多少?

? 以结点 C 为根的子树的深度是多少? 3. 某二叉树的结点数据采用顺序存储表示如下:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B (1)试画出此二叉树的图形表示。(2)写出结点D的双亲结点及左、右子女。 (3)将此二叉树看作森林的二叉树表示,试将它还原为森林。

4.假设一棵二叉树的中序序列DCBGEAHFIJK和后序序列为DCEGBFHKJIA请画出该二叉树,并给出先序序列。 5.按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列,分别构造出二叉树。 ①先序遍历序列: EBADCFHGIKJ 中序遍历系列: ABCDEFGHIJK ②中序遍历序列: ACBGEDF 后序遍历序列: ABCDEFG

6.对上题①所得的二叉树,分别画出它的顺序存储结构和二叉链表。

7.已知一棵树的度为4,其中度为4的结点的数目为3,度为3的结点的数目为4,度为2的结点的数目为5,度为1的结点的数目为2,请求出该树中的叶子结点的数目。

8.如果已知一棵二叉树有20个叶子结点,有10个结点仅有左孩子,15个结点仅有右孩子,求出该二叉树的结点数目。

9.已知某完全二叉树有100个结点,试用三种不同的方法求出该二叉树的叶子结点数。

10.如果已知完全二叉树的第6层有5个叶子,试画出所有满足这一条件的完全二叉树,并指出结点数目最多的那棵完全二叉树的叶子结点数目。

11.在编号的完全二叉树中,判断编号为i和j的两个结点在同一层的条件是什么? 12.设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 13.分别求出下图中二叉树的三种遍历序列。

32

联系合同范文客服:xxxxx#qq.com(#替换为@)