2022年树历年试题及参考答案 .pdf

《2022年树历年试题及参考答案 .pdf》由会员分享，可在线阅读，更多相关《2022年树历年试题及参考答案 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 6 章 树（2008年 1 月）8、树的先根序列等同于与该树对应的二叉树的（）A、先序序列B、中序序列C、后序序列D、层序序列21、假设一棵完全二叉树含1000个结点,则其中度为 2 的结点数为 _。27、已知二叉树的先序序列和中序序列分别为ABDEHCFI 和 DBHEACIF，(1)画出该二叉树的二叉链表存储表示;(2)写出该二叉树的后序序列。(1)(2)32、已知以二叉链表作二叉树的存储结构，阅读算法f32，并回答问题：(1)设二叉树 T 如图所示,写出执行 f32(T)的返回值;(2)简述算法 f32 的功能。int f32(BinTree T)int m,n;if(!T)retu

2、rn 0;else m=f32(Tlchild);n=f 32(Trchild);if(mn)return m+1;else return n+1;(1)(2)（2008年 10 月）7、已知一棵含 50 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为（）A、0 B、1 C、48 D、49 21、假设用 表示树的边（其中x 是 y 的双亲），已知一棵树的边集为,，该树的度是。26、由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -前序序列：后序序列：（2009年 1 月）7、高

3、度为 5 的完全二叉树中含有的结点数至少为()A、16 B、17 C、31 D、32 8、已知在一棵度为 3 的树中，度为 2 的结点数为 4，度为 3 的结点数为 3，则该树中的叶子结点数为()A、5 B、8 C、11 D、18 9、下列所示各图中是中序线索化二叉树的是()21、在含有 3 个结点 a，b，c 的二叉树中，前序序列为abc且后序序列为 cba的二叉树有 _ 棵。28、假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这 8 个字符设计哈夫曼编码。要求：(1)画出你所构造的哈夫曼树(要求树中左

4、孩子结点的权值不大于右孩子结点的权值)；(2)按左分支为 0 和右分支为 1 的规则，分别写出与每个字符对应的编码。(1)(2)31、假设以二叉链表表示二叉树，其类型定义如下：typedef struct node DataType data;struct node*lchild,*rchild;/左右孩子指针*BinTree;阅读下列算法，并回答问题：(1)已知以 T 为根指针的二叉树如图所示，写出执行 f31(T)之后的返回值；(2)简述算法 f31 的功能。int f31(BinTree T)int d;if(!T)return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 2

5、页，共 8 页 -d=f31(T-lchild)+f31(T-rchild);if(T-lchild&T-rchild)return d+1;else return d;(1)(2)（2009年 10 月）9、已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）A、FEDCBA B、ABCDEF C、FDECBA D、FBDCEA 10、已知森林 F=T1，T2，T3，T4，T5，各棵树 Ti(i=1，2，3，4，5)中所含结点的个数分别为 7，3，5，l，2，则与 F 对应的二叉树的右子树中的结点个数为（）A、2 B、3 C、8 D、11 21、任意一棵完全二叉树中，度

6、为1 的结点数最多为 _。27、由字符集 s，t，a，e，I 及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。（2010年 1 月）10、下列数据结构中，不属于二叉树的是（）A、B 树B、AVL 树C、二叉排序树D、哈夫曼树21、用 6 个权值分别为 6、13、18、30、7 和 16 的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_。26、假设二叉树的 RNL 遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；(3)遍历左子树。已知一棵二叉树如图所

7、示，请给出其RNL 遍历的结果序列。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -34、已知二叉树采用二叉链表存储，其结点结构定义如下：typedef struct Node ElmType data；struct Node*lchild，*rchild；*BiTree；请编写递归函数 SumNodes(BiTree T)，返回二叉树 T 的结点总数。（2010年 10 月）7、若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是()A、树中没有度为 2的结点B、树中只有一个根结点C、树中非叶结点均只有左子树D、树中非叶结点均只有右子树8、若根结点的层

8、数为 1，则具有 n个结点的二叉树的最大高度是()A、n B、C、+1 D、n/2 19、3个结点可以组成 _ 种不同树型的二叉树。20、用5个权值 3,2，4，5，1构造的哈夫曼(Huffman)树的带权路径长度是_。28、已知二叉树如下：请画出该二叉树对应的森林。34、已知二叉树的定义如下：typedef struct node int data;struct node*lchild,*rchild;*Bitptr；编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）；（2011年 1 月）7、若一棵具有 n(n0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉

9、树一定是（）A、结点均无左孩子的二叉树B、结点均无右孩子的二叉树名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -C、高度为 n 的二叉树D、存在度为 2 的结点的二叉树8、若一棵二叉树中度为l 的结点个数是 3，度为 2 的结点个数是 4，则该二叉树叶子结点的个数是（）A、4 B、5 C、7 D、8 21、一棵树 T 采用孩子兄弟链表存储，如果树T 中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是_。31、假设以二叉链表表示二叉树，其类型定义如下：typedef struct node char data;struct node*Ichild,*rchild

10、;左右孩子指针*BinTree；阅读下列程序。void f31(BinTree T)InitStack(S);初始化一个堆栈 S while(T|!StackEmpty(S)while(T)Push(S,T);T=T-lchild;if(!StackEmpty(S)T=Pop(S);printf(“%c”,T-data);T=T-rchild;回答下列问题：(1)已知以 T 为根指针的二叉树如图所示，请写出执行 f31(T)的输出结果：(2)简述算法 f31 的功能。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -参考答案（2008年 1 月）8、A21、499 27、

11、(1)(2)DHEBIFCA 32、(1)4(2)求二叉树的深度（高度）（2008年 10 月）7、D 21、3 26、前序序列：GHIJ 后序序列：HJIG（2009年 1 月）7、A 8、C 9、A 21、4 28、(1)A B C D E F H I root b d 54 26 28 100 46 25 e 12 a 13 5 7 c g 2 3 f h 21 10 11 0 0 0 0 0 0 0 1 1 1 1 1 1 1 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -(2)各字符的编码见下表a b c d e f g h 0101 10 01000 11

12、 011 000 01001 001 31、(1)3(2)求二叉树双孩子结点的个数。（2009年 10 月）9、A 10、D 21、1 个27、eatst（2010年 1 月）21、WPL=219 26、GCFABD 34、int SumNodes(BiTree T)if(T=NULL)/或!T return(0);else return(SumNodes(T-lchild)+SumNodes(T-rchild)+1);（2010年 10 月）7、B 8、A 19、5 20、WPL=33 28、34、int f34(Bitptr t)int leftdep,rightdep;if(t=NULL)return(0);else a b d c e f j g h k 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -leftdep=f34(t-lchild);rightdep=f34(t-rchild);if(leftdeprightdep)return(leftdep+1);else return(rightdep+1);（2011年 1 月）7、C 8、B 21、最左孩子指针域 leftmostchild=NULL 31、(1)CBEDFAGH(2)非递归中序遍历二叉树名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -