数据结构导论真题分类整理详细 下载本文

第四章 树 真题

2.某二叉树的后根遍历序列为dabec,中根遍历序列为debac,则先根遍历序列为( ) A.acbed B.becab C.deabc D.cedba

3.含有n个结点的二叉树用二叉链表表示时,空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 12.有关树的叙述正确的是( )

A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点

C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 24.对于一棵满二叉树,若有m个叶子,则树中结点数为____________。

30.已知一棵二叉树的先根遍历序列为ABCDEGHF,中根遍历序列为CBEDAGFH,画出该二叉树。 34.二叉树按二叉链表形式存储,编写一个算法判别给定的二叉树是否为完全二叉树。

5.由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为( ) A.23 B.37 C.44 D.46 12.用n个值构造一棵二叉排序树,它的最大高度为( ) A.n/2 B. n C. n+1 D.log2n 21.若满二叉树的结点数为n,则其高度为________。

22.在一棵具有n个结点的完全二叉树中,从树根起,自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点,那么其父结点的编号为_____。 23.深度为k的二叉树,结点数最多有________个。

24.某二叉树的后根遍历为ABKCBPM,则该二叉树的根为______。

29.某通讯电文由A,B,C,D,E,F六个字符编码组成,每个字符编码在电文中出现的次数分别是6,

5,9,10,20,1,试画出这六个字符编码所用的哈夫曼树。

30.已知一棵二叉树的顺序存储结构如题30图所示,其中∧表示虚结点,试构造该二叉树。

A B G C D ∧ H ∧ ∧ E F 题30图

34.若两棵二叉树B1和B2皆为空,或者皆不空且B1的左、右子树和B2的左、右子树分别相似,则称二叉树B1和B2相似。试编写算法,判别给定两棵二叉树是否相似。

8.具有n个结点的二叉树,拥有指向孩子结点的分支数目是( ) A.n-1 B.n C.n+1 D.2n

9.对一棵有100个结点的完全二叉树按层序编号,则编号为49的结点,它的左孩子的编号为( ) A.99 B.98 C.97 D.50 10.有m个叶子结点的哈夫曼树,其结点总数是( )

A.2m-1 B.2m C.2m+1 D.2(m+1) 22.深度为k的二叉树至多有______个结点,最少有______个结点。

29.已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF。请构造出该二叉树,并给出该二叉树的后序序列。

30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。

13

8.含有n个结点的二叉树采用二叉链表存储时,空指针域的个数为( ) A.n-1 B.n C.n+1 D.n+2

9.在一棵深度为H的完全二叉树中,所含结点的个数不少于( ) A.2H-1-1 B.2H-1 C.2H-1 D.2H

19.对一棵深度为10的满二叉树按层编号,则编号为51的结点,它的双亲结点编号为_______。 21.具有n个叶子结点的哈夫曼树,其结点总数为________。

22.一棵具有n个结点的树,所有非终端结点的度均为k,则该树中叶子结点个数为________。 25.某二叉树的后根遍历序列为abd,中根遍历序列为adb,则它的先根遍历序列为________。 30.画出题30图所示的二叉树的二叉链表存储结构。

35.设二叉树的结点类型定义如下: typedef struct node{ datatype data;

struct node*lchild,*rchild; }Bitree; Bitree*t;

试编写一个计算二叉树深度的递归算法(int Depth(Bitree*t))。

8.某二叉树的先根遍历序列和后根遍历序列正好相反,则该二叉树具有的特征是( )

A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点 9.在完全二叉树中,若一个结点是叶结点,则它没有( )

A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点,右孩子结点和兄弟结点 12.若构造一棵具有n个结点的二叉排序树,最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 19.在一个具有n个结点的单链表中查找值为m的某结点,若查找成功,则需平均比较的结点数为____。 20.深度为15的满二叉树上,第11层有_______个结点。

21.对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的左孩子的编号为________。 30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA,试画出这棵二叉树。

8.除根结点外,树上每个结点( )

A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 9.题9图中树的度为( )

14

A.2 B.3 C.5 D.8

20.设F、C是二叉树中的两个结点,若F是C的祖先结点,则在采用后根遍历方法遍历该二叉树时,F和C的位置关系为:F必定在C的__________。

21.若用后根遍历法遍历题21图所示的二叉树,其输出序列为__________。

29.分别写出题29图中二叉树的先根、中根、后根遍历序列。

10.高度为h的完全二叉树中,结点数最多为( )A.2h-1 B.2h+1 C.2h-1 D.2h 11.由m棵结点数为n的树组成的森林,将其转化为一棵二叉树,则该二叉树中根结点的右子树上具有的结点个数是( )A.mn B.mn-1 C.n(m-1) D.m(n-1) 21.有4个结点且深度为4的二叉树的形态共有_______种。

22.某二叉树的先根遍历序列为IJKLMNO,中根遍历序列为JLKINMO,则该二叉树中根结点的右孩子是_______。

30.某二叉树的先根遍历序列为ABIJCDFGHE,中根遍历序列为IJBADGFHCE,试画出该二叉树,并写出它的后序遍历序列。

8.含有10个结点的二叉树中,度为0的结点数为4,则度为2的结点数为( ) A.3 B.4 C.5 D.6

9.对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的父结点的编号为( ) A.24 B.25 C.98 D.99 21.三个结点可构成________种不同形态的二叉树。

22.对于一棵具有n个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总数为2n个,其中______个用于链接孩子结点。

29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A,试画出这棵二叉树,并给出其先根序列。 7.关于二叉树性质的描述,正确的是( )

A.二叉树结点的个数可以为0 B.二叉树至少含有一个根结点 C.二叉树若存在两个结点,则必有一个为根,另一个为左孩子

15

D.二叉树若存在三个结点,则必有一个为根,另两个分别为左、右孩子 8.具有4个结点的二叉树可有( )

A.4种形态 B.7种形态 C.10种形态 D.11种形态 22.深度为k的满二叉树其叶子结点个数共有________________个。 23.二叉树通常采用________________两种存储结构表示。 29.试采用类C语言,给出二叉树的二叉链表结构描述。

35.若二叉树采用二叉链表表示,试给出二叉树先根遍历的非递归算法描述 7.树是n个结点的有穷集合,( )

A.树的结点个数可以为0,此时称该树为空树 B.树至少含有一个根结点,不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子C.2k-1个叶子 D.2k-1-1个叶子 22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。

23.若某二叉树中度为1的结点数为4,度为2的结点数为6,则该树叶子结点数为__________。 29.对于如题29图所示二叉树,分别写出其先根遍历,中根遍历,后根遍历的结点访问序列。

35.若二叉树用二叉链表表示,试编写一算法计算一棵二叉树的叶子总数(可采用递归算法描述)。 7.深度为k的二叉树最多有()个结点

22.若某二叉树的先根遍历序列为CEDBA,中根遍历序列为DEBAC,则其后根遍历序列为______。 23.具有n个结点的完全二叉树,其深度为___________。 29.已知某二叉树的顺序存储结构如图所示,试画出该二叉树。

35.二叉树是由所有度数不大于2的结点构成的一种特定树,若某结点度为2,则该结点有左 右两个孩子,请编写算法计算一二叉树所有度数为2的结点个数。 7.根据定义,树的叶子结点其度数( )

A.必大于 0 B.必等于0 C.必等于1 D.必等于2

8.二叉树若采用二叉链表结构表示,则对于n个结点的二叉树一定有( ) A.2n个指针域其中n个指针为NULL B.2n个指针域其中n+1个指针为NULL C.2n-1个指针域其中n个指针为NULL D.2n-1个指针域其中n+1个指针为NULL 22.树的遍历主要有先根遍历、后根遍历和___________三种。 23.深度为k的完全二叉树至少有___________个结点。

29.已知某二叉树如下图所示,试给出其二叉链表及顺序存储结构表示。

16