数据库系统l试题库及答案 第6章 树和二叉树.docx

1、数据库系统l试题库及答案 第6章 树和二叉树第6章 树和二叉树6.1知识点: 树和二叉树的基本概念一、 填空题1. 高度为h，度为m的树中至少有_个结点，至多有_个结点。2. 树的结点是由 及若干指向其子树的 组成；结点拥有的子树数称为 ；度为0的结点称为 ；度不为0的结点成为 ；树中结点的最大度数称为 ；树的最大层次称为_。3. 对于一棵具有n个结点的树，该树中所有结点的度数之和为_。4. 如果结点A有3个兄弟结点，而且B是A的双亲，则B的度是_。5. 二叉树是另一种树形结构，它的特点是 。6. 一颗度数为k且有2k-1个结点的二叉树称为 。7. 深度为k，且有n个结点的二叉树，当且仅当其每

2、一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为 。8. 一棵深度为6的满二叉树有 个分支结点和 个叶子。9. 一棵具有257个结点的完全二叉树，它的深度为 。10. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。11. 由3个结点可以构成_种形态的的二叉树，可以构成 种形态的树。12. 将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第1号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为 。13. 一棵高度为5的完全二叉树中，最多包含有_个结点

3、。14. 一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1=_。15. 在高度为h（h=0）的二叉树中至多可以有_个结点，至少可以有_个结点。16. n个结点的二叉树最大高度是_,最小高度是_。二、 选择题1. ( ）不含任何结点的空树（ ）。 A.是一棵树 B.是一棵二叉树 C.是一棵树也是一棵二叉树 D.既不是树也不是二叉树2. （ ）一棵度为4的树中度为1、2、3、4的结点个数为4、3、2、1，则该树的结点总数为（ ）。 A.21 B.26 C.27 D.243. ( )具有10个叶子结点的二叉树中有 个度为2的结点。 A.8 B.9 C.10 D.114.

4、( )在一棵高度为h（假定根结点的层号为1）的完全二叉树中，所含结点个数不小于（ ）。 A B C D 5. ( )如下的4棵二叉树中，（ ）不是完全二叉树。 A B. C. D.6. ( )设树T 的度为4，其中度为1，2，3 ,4 的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）。 A5 B6 C7 D87. ( )从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在答卷的对应栏内。 树是结点的有限集合，它A 根结点，记为T。其余的结点分成为m（m0）个 B 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点 (1im）。一个

5、结点的子结点个数为该结点的 C 。 供选择的答案 A： 有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交 C： 权 维数 次数（或度） 序8. （ ）在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A2 B1 C0 D-1 三、简答题1一棵度为2的树与一棵二叉树有何区别？ 6.2知识点：遍历二叉树和线索二叉树一、填空题1. 二叉树有四种遍历方法：_、_、_、_。2. 若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。 3. 二叉树的链式存储结构有： 、 、 、 四种。

6、4. 指向前驱或后继结点的指针称为 ，加上线索的二叉链表表示的二叉树叫 ，5. 对二叉树按某种遍历次序使其变为线索二叉树的过程叫 。6. 在线索二叉树的结点中增加两个标志域LTag和RTag,若LTag=0,则lchild 域指向 ；若 LTag=1, 则lchild域指向 ；若RTag =0,则rchild域指向 ；若RTag=1, 则rchild域指向 。二、选择题1. （ ）某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ ）。 A.空树或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数2. （ ）二叉树是非线性数据结构，所以（ ）。 A.它不能用顺序存

7、储结构存储 B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 3. （ ）线索二叉树是一种( )结构A.逻辑 B. 存储 C.线性 4. 在n个结点的线索二叉树中，线索的数目为( )。 A.n-1 B. n C.n+1 D.2n三、判断题1. （ ）在先序、中序和后序序列中，叶子结点出现的相对次序是相同的。2. （ ）由一棵二叉树的先序序列和中序序列可以唯一确定这棵二叉树。3. （ ）在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。4. （ ）对于一棵具有n个结点，其高度为h的

8、二叉树，进行任一种次序遍历的时间复杂度为O（n）。5. （ ）在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向孩子结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点。6. （ ）若有一个叶子结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树中序遍历结果序列的最后一个结点。7. （ ）由一棵二叉树的先序序列和后序序列可以唯一确定这棵二叉树。四、 简答题1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。2.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchil

9、d，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：（1）对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；（2）假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。3. 若已知一棵二叉树的后序序列是FEGHDCB，中序序列是FEBGCHD，试画出这棵二叉树。4. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 5.阅读下列算法，若有错，改正之。BiTree InSucc(BiTree q)/已知q是指向中序线索二叉树上某个结点的指针，/本函数返回指向*q的后继的指针。r=q-rchild

10、; if(!r-rtag) while(!r-rtag)r=r-rchild; 五、算法设计题1.假定二叉树采用二叉链表存储结构存储，编写递归算法，计算二叉树中叶子结点的数目。2.假定二叉树采用二叉链表存储结构存储，编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。3假定二叉树采用二叉链表存储结构存储，编写按层次顺序（同一层自左至右）遍历二叉树的算法。4.假定二叉树采用二叉链表存储结构存储，设计一个算法计算一棵给定二叉树的结点总数。5.编写算法判别给定二叉树是否为完全二叉树。6.3知识点：树和森林一、填空题1. 树的孩子-兄弟表示法又称为二叉链表表示法，即以 作树的存储结构。2. 森

11、林是m（m0）棵_的树的集合。对树的每个结点而言，其子树的集合即为 。3. 遍历树的方法：一种是先根（次序）遍历树，即先访问树的 ，然后依次 遍历根的每棵子树；另一种是后根（次序）遍历，即先依次 遍历每棵子树，然后访问根结点。4. 当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历可借用二叉树的 和 来实现。5. 森林的先序遍历与其转换成的二叉树的 相同，森林的中序遍历与其转换成的二叉树的 _相同。6. 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有_个结点，根结点的右子树上有_个结点。7. 若用孩子兄弟链

12、存储结构来存储具有m个叶子结点、n个分支结点的树，则孩子兄弟链中有_个左指针域为空的结点，有_个右指针域为空的结点。二、选择题1. （ ）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A唯一的 B有多种 C有多种，但根结点都没有右孩子D有多种，但根结点都没有左孩子2. （ ）下图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有（ ）个叶子结点。 A4 B5 C6 D73. 从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在答卷的对应栏内。二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换

13、成的二叉树里，一个结点N的左孩子是N在原树里对应结点的 C ，而N的右孩子是它在原树里对应结点的 D 。供选择的答案A： 是特殊的树 不是树的特殊形式 是两棵树的总称 有是只有二个根结点的树形结构 B: 左孩子结点 右孩子结点 左孩子结点或者没有右孩子结点 兄弟CD： 最左孩子结点 最右孩子结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= D 4. ( ) 在下列存储形式中，（ ）不是树的存储形式。 A.双亲表示法 B.孩子链表表示法 C.孩子兄弟链表表示法 D.顺序存储表示法5. （ ）用双亲存储结构表示树，其优点之一是（ ）比较方便。 A.找指定结点的双亲

14、结点 B.找指定结点的孩子结点 C.找指定结点的兄弟结点 D.判断某结点是不是叶子结点6. （ ）在孩子链表存储结构中，其优点之一是（ ）比较方便。 A.判断两个指定结点是不是兄弟 B.找指定结点的双亲 C.判断指定结点在第几层 D.计算指定结点度数7. （ ）如果用孩子兄弟链表来表示一颗具有n（n1）个结点的树，则在该存储结构中（ ） A.至多有n-1个非空的右指针域 B.至少有两个空的右指针域 C.至少有两个非空的左指针域 D.至多有n-1个空的右指针域8. （ ）如果T1是由有序树T转换而来的二叉树，那么T中结点的后序遍历序列就是T1中结点的（ ）序列。 A.先序 B.中序 C.后序 D

15、.层次序三、简答题1. 把如图所示的树转化成二叉树。2. 画出和下列二叉树相应的森林。6.4知识点：哈夫曼编码一、填空题1. 假设有n个权值w1，w2，wn，试构造一棵有n个结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度为WPL最小的二叉树称为 或 。2. 用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。3. 由于赫夫曼树中没有度为1的结点，则一颗有n个叶子结点的赫夫曼树共有 个结点。二、选择题1. （ ）根据使用频率为5个字符设计的哈夫曼编码不可能是（ ）。 A111，110，10，01，00 B000，001，010，011，1 C100，

16、11，10，1，0 D001，000，01，11，102. （ ）设有13个值，用它们组成一颗哈夫曼树，该哈夫曼树共有（ ）个结点。 A13 B12 C26 D253. （ ）下述编码中哪一个不是前缀码（ ）。 A（00，01，10，11） B（0，1，00，11）C（0，10，110，111） D（1，01，000，001）3、判断题（ ）1.哈夫曼树中不存在度为1的结点。（ ）2.在哈夫曼树中，权值相同的叶子结点都在同一层。（ ）3.在哈夫曼树中，权值较大的叶子结点一般离根结点较远。（ ）4.在哈夫曼树中，当两个字符出现的频率相同时，其编码也相同。四、简答题1.假设用于通信的电文仅由8个字

17、母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点，哈夫曼编码的平均码长是等长编码的百分之几？2.假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为（5, 25, 3, 6, 10, 11, 36, 4）。（1）试构造哈夫曼树；（2）试为这8个字母设计不等长Huffman编码；（3）求其WPL值。3.已知某电文中出现了6种不同的字母，它们的出现次数

18、分别为：A为6次，B为26次，C为36次，D为17次，E为3次，F为12次。完成以下题目。 （1） 请为这些字符设计哈夫曼编码； （2）请用三位二进制数对这6各字母进行等长编码； （3）哈夫曼编码的平均码长是等长编码的百分之几？第6章 树和二叉树6.1知识点: 树和二叉树的基本概念一、 填空题1. h-1+m (mh-1)/(m-1) 2. 数据元素 分支 结点的度 叶子或终端结点 非终端结点或分支结点 树的度 树的深度 3. n-1 4.4 5. 每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒 6. 满二叉树 7. 完全二叉树 8.

19、31 32 9.9 10.500 499 1 0 11. 5 2 12.20 13.31 14.n-2n0+1 15.2h-1 h 16.n log2n+1二、 选择题1.C 2.A 3.B 4.A 5.D 6.D 7. ABC1，1，3 8.A三、简答题1度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。6.2知识点：遍历二叉树和线索二叉树一、填空题1.先序遍历 中序遍历 后序遍历 层次遍历 2. F E G H D C B 3. 二叉链表、三叉链表、双亲链表、线索链表

20、4. 线索 线索二叉树 二叉树的线索化 5. 左孩子 该结点的前驱结点 右孩子 该结点的后继结点二、选择题1.D 2.C 3.B 4.C三、判断题1. 2. 3. 4. 5. 6. 7.四、 简答题1. DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A2. 这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G3. 4.要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：55 40 25 60

21、28 08 33 54 5. r=q-rchild; 应改为r=q； while(!r-rtag)r=r-rchild; 应改为 while(!r-Ltag) r=r-Lchild;五、算法设计题1.思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。法一：核心部分为：DLR(liuyu *root) /*中序遍历 递归函数*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rch

22、ild); return(0); 法二：int LeafCount_BiTree(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; /叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 2.int Get_Sub_Depth(Bitree T,int x)/求二叉树中以值为x的结点为根的子树深度 if(T-data=x) printf

23、(%dn,Get_Depth(T); /找到了值为x的结点,求其深度 exit 1; else if(T-lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子树深度的递归算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth 3void LayerO

24、rder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 4. int Nodes(BTNode *T) int num1,num2; if (T=NULL) return 0; else if(T-lchild=NULL&T-rchild=NULL)return 1; else num1

25、=Nodes(T-lchild); num2=Nodes(T-rchild); return num1+num2+1; 5.int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); /不管孩子是否为空,都入队列 /whil

26、e return 1; /IsFull_Bitree 分析:该问题可以通过层序遍历的方法来解决.不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针. 6.3知识点：树和森林一、填空题1.二叉链表 2. 互不相交 森林 3. 根结点 先根 后根 4. 先序遍历 中序遍历 5. 先序遍历 中序遍历 6.n1-1 n2+n3+n4 7.m n+1二、选择题1.C 2.C 3. ABCDE2，1，1，3 4.D 5.A 6.D 7.B 8.B三、简答题1. 2. 画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森

27、林，而孩子结点的右子树均为兄弟。6.4知识点：哈夫曼编码一、填空题1. 最优二叉树 赫夫曼树 2.33 3.2n-1二、选择题1.C 2.D 3.B三、判断题1. 2. 3. 4.四、简答题1.先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32方案比较： 方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.0

28、2+0.03)=3结论：哈夫曼编码优于等长二进制编码哈夫曼编码的平均码长与等长编码的平均码长之比为：2.61/3=87%2.（1）61393625221771011114365C3C8C5C6C1C4C2C7000000111111（2） c1 c2 c3 c4 c5 C6 c7 c8 0110 10 0000 0111 001 010 11 0001 （3）WPL= 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 3. 1）哈夫曼编码为：A：0101 B：10 C：11 D：00 E：0100 F：011（2）等长编码为：A：000 B：001 C：010 D：011 E：100 F：101（3）哈夫曼编码的平均码长为WPL=230等长编码的平均码长为WPL=（3+6+12+17+26+36）*3=300哈夫曼编码的平均码长与等长编码的平均码长之比为：230/300=77%