《数据结构 树 考试习题.doc》由会员分享，可在线阅读，更多相关《数据结构 树 考试习题.doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 树11 不含任何结点的空树( ) A）是一棵树 B）是一棵二叉树 ）既不是树也不是二叉树 D）是一棵树也是一棵二叉树12二叉树是非线性数据结构，所以( ) A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储; C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 13把一棵树转换为二叉树后，这棵二叉树的形态是( ) A）唯一的 B）有多种 C）有多种，但根结点都没有左孩子 D）有多种，但根结点都没有右孩子9. 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A) 24 B) 72 C) 48 D) 53
2、 10.一棵含18个结点的二叉树的高度至少为( )A) 3 B) 4 C) 6 D) 511.下面的二叉树中，( C )不是完全二叉树。 10. 设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在中序序列中x在y之后，则x和y的关系是（ ） A）x是y的左兄弟 B）x是y的右兄弟 C）y是x的祖先 D）y是x的孩子11.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（ ）A） 6 B） 5 C） 4 D） 37 下列陈述中正确的是（ ）A） 二叉树是度为2的有序树 B） 二叉树中结点只有一个孩子时无左右之分C） 二叉树中必有度为2的结点 D） 二叉树
3、中最多只有两棵子树，并且有左右之分8. 树最适合用来表示（ ）A） 有序数据元素 B） 无序数据元素 C） 元素之间具有分支层次关系的数据 D） 元素之间无联系的元素9. 3个结点有（ ）不同形态的二叉树A） 2 B） 3 C） 4 D） 56二叉树是非线性数据结构，( ) A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储; C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 7二叉树上叶结点数等于( )A ) 分支结点数加1 B ) 单分支结点数加1 C ) 双分支结点数加1 D ) 双分支结点数减18如将一棵有n个结点的完全二叉树按顺序存放方式，
4、存放在下标编号为0,1,n-1的一维数组中，设某结点下标为k(k0)，则其双亲结点的下标是( ) A ) (k-1)/2 B ) (k+1)/2 C ) k/2 D ) k-18. 树最适合用来表示（ ）。A有序数据元素 B无序数据元素 C. 元素之间具有分支层次关系的数据 D元素之间无联系的元素10.有64个结点的完全二叉树的深度为( ) (根的层次为第1层)。A. 8 B. 7 C. 6 D. 511.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有个，那么，该树有（ ）个叶子结点。A. 4 B. 5 C. 6 D. 79.一个二叉树按顺序方式存储在一个维数组中，
5、如图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第（ ）层。(假设树根所在层为第1层)A、2 B、3 C、4 D、510. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A 24 B 71 C 48 D 538. 二叉树上叶结点数等于（ ）。A分支结点数加1 B单分支结点数加1 C双分支结点数加1 D双分支结点数减18. 某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。 A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右
6、孩子9. 在有n个结点的二叉链表中，值为空的链域的个数为( ) A. n-1 B. 2n-1 C. n+1 D. 2n+110. 一棵含18个结点的二叉树的高度至少为()A. 8 B. 7 C. 6 D. 511. 深度优先遍历类似于二叉树的( )A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历9. 一棵124个叶结点的完全二叉树，最多应有()个结点。A.245B.246C.247D.24810. 后缀表达式“ 5 6*3 2 + -”的值为（ ）。A.15 B.25 C.30 D.3511. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权
7、路径长度为（ ） A. 24 B. 71 C. 48 D. 537. 对一个满二叉树，m个树叶, n个结点, 深度为为h, 则（ ）。A. n=2h-1 B.h+m=2n C.m=h-1 D. n=h+m8. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。A.2 B.1 C.0 D.-19. 若完全二叉树的结点总个数为100（结点编号从1开始编号，按层序编号），则第58个结点的度为（ ）A.2 B.1 C.0 D.不确定10. 已知完全二叉树的第9层有240个结点，则该完全二叉树的结点数是（）A.494 B.495 C.496 D.497二、填空题1. 一棵深度为5的二叉树，至
8、多有_个结点。316.图的存储结构有_和_，遍历图有_、_等方法。邻接矩阵 邻接表 深度优先 广度优先7.深度为的完全二叉树最多有 个结点。8.若按层序对深度为的完全二叉树中全部结点从开始编号，则叶子结点可能的最小编号为 。6.设有树如图所示，则结点的度为_，层次为_，树的度为_，树的高度为_。结点的度为， 层次为， 树的度为，高度为7.深度为的完全二叉树至少有_个结点，最多有_个结点。，7.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中_个用于链接孩子结点，_个空闲着。2n，n-1，n+12. 后缀表达式“2 10 + 5 * 6 9 /”的值为 。6
9、3.由n个权值构成的哈夫曼树共有 个结点。2n-16.在一棵树中， _ 结点没有后继结点。叶4后缀表达式“2 10 + 5 * 6 9 /”的计算结果为 。64.一棵深度为7的二叉树，最多有 个结点。1275.若一棵树的括号表示为A(B,C(E,F(G),D),该树的叶子结点个数为_ ，该树的度为_ ，该树的深度为_。4、3、46.在有n个叶子结点的哈夫曼树中，总结点数是_。2n-11. 深度为4的完全二叉树最少有_个结点，最多有_个结点。8156. 假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J),K)，则度为3、2、1、0的结点数分别为_、_、_和_个。22076. 若结
10、点A有其他三个兄弟,B是A的双亲结点,B的度是_。47. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_个。338. 一棵深度为7的二叉树，最多有 个结点。127三、应用题1、名词解释：树，子树，结点的度，叶子结点，孩子，双亲，兄弟，深度，有序树，森林，二叉树，遍历二叉树，树的带权路径长度，哈夫曼树。2、描述二叉树的性质。3、从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别。4、已知一棵树边的结点为,，试画出这棵树,并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点G
11、的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？5、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，nk个度为k 的结点，问该树中有多少个叶子结点？7、已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。8、有n个结点的二叉树，已知叶子结点个数为n0，写出求度为1的结点的个数n1的计算公式；若此树是深度为k的完全二叉树，写出n
12、为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。9、假设n 和m 为二叉树中两结点，用“1”，“0”或“”（分别表示肯定、恰恰相反或者不一定）填写下表：前序遍历时n在m前?中序遍历时n在m前?后序遍历时n在m前?n在m左方n在m右方n是m祖先n是m子孙注：如果（1）离a 和b最近的共同祖先p存在，且（2）a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。10、找出所有满足下列条件的二叉树：（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同；（b）它们在后序遍历和中序遍历时，得到的结点访问序列相同；（c）它们在先序遍历和后序遍历时，得
13、到的结点访问序列相同；11、分别画出和下列树对应的各个二叉树：12、画出和下列二叉树相应的森林：13、画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为CBEFDGAJIKLH。14、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。15、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。16、编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。17、编写递归算法，计算二叉树中叶子结点的数目。5. 用于通信的电文仅由a、b、c、d、e、f、g、h等8
14、个字母组成，字母在电文中出现的频率分别为：007、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造相应的哈夫曼树并为这些字母设计哈夫曼编码。（9分）得到的编码如下 ： a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 h:0011 此题答案不唯一。5. 设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树，并写出此二叉树的后序遍历。（10分）后序：DHFBFIGCA6. 给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算带权路径长度. （9分）答案
15、：50 92030111614 7 7 2 5带权路径长度=（9+11+16）*2+7*3+（2+5）*4=1211.已知一组关键字为25,18,46,2,53,39,32,4,74,67,60,11。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。（10分）答案：1设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树,并写出该树的后序遍历的结点次序。(6分)ABCDEFGHI1. .后序:DHEBFIGCA1已知一棵树二叉如下，请写出按前序、中序、后序和层次遍历时得到
16、的结点序列。（8分）AB CD E FG H前序：中序：后序：层次：各遍历次序如下前序：，中序：，后序：，层次：，4. 已知一棵完全二叉树共有999个结点，试求：(写出详细的分析过程) （9分）1、树的高度（深度） 2、叶子结点的数目3、度为1的结点数目深度：10 叶子节点数目：500 度为1的节点数目：01.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A.请将下图所示的森林森林转换为所对应的二叉
17、树。ABDEFCGHJIKNOMLBGDCHKEIFJLMNOA图5-164将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。答案53785365785353786517537865178753786517870953786517870981455378651787098145231.已知一棵二叉树的中序遍历序列为： dfebagc，先序遍历序列为：abdefcg，请画出这棵二叉树 2.设用于通信的电文由个字母组成，字母在电文中出现的频率分别为0.16、0.38、0.01、0.06、0.24、0.11、0.04
18、，试为这个字母设计赫夫曼编码。赫夫曼树：赫夫曼编码：（0.15）：（0.39）：（0.01）：（0.06）：（0.24）：（0.11）：（0.04）：1. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA50 92030111614 7 7 2 52. 给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算WPL.答案：wpl=（9+11+16）*2+7*3+（2+5）*4=1211.已知某二叉树的前序序列为EBADCFH
19、GI，中序序列为ABCDEFGHI，请给出二叉树的后序列。答案：后序序列:ACDBGIHFE2在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。 71 0 130 41 0 1 0 1 16 Y(14) 23 F(18) 0 1 0 1 G(9) U(7) A(12) Z(11) 哈夫曼树A：100 G：000 F：11U：001 Y：01 Z：101（或0、1 相反） （8分）注意：答案不唯一。3. 已知一棵完全二叉树共有1001个结点，试求：(写出详细的分析过程) （9分）1、树的高度（深度） 2、叶子结点的数
20、目3、度为1的结点数目深度：10 叶子节点数目：501 度为1的节点数目：04. 试给下图所示二叉树的前序、中序和后序遍历序列。若一棵二叉树的前序遍历序列为：A B D E G C F，中序遍历序列为：D B E G A C F，试画出此二叉树。（10分）前序：ABDEGHCF中序：DBGEHAFC后序：DGHEBFCA5. 一组密文原码由字符A, B, C, D, E, F, G组成，其出现的频率分别是9, 11, 5, 7, 8, 2, 3，设计相应的哈夫曼树并对7个字符编码。（8分）哈夫曼树略。编码方案：A：00 B：10 C：010 D：110 E：111 F：0110 G：0111（
21、此题答案不唯一）四、综合题2. 在二叉树的链式存储结构中，结点类型定义如下：typedef struct node ElemType data; struct node *lchild,*rchild; BTNode;以下算法是计算二叉数深度的递归算法，试补充完整。int BtreeDepth (BTreeNode *BT) /BT是根结点 if (BT=NULL) return 0；elseint dep1,dep2； /dep1、dep2分别为根结点左子树、右子树高度dep1= ；dep2= ；if (dep1dep2) return ；elsereturn ；2. BtreeDepth（
22、BT-lchild）BtreeDepth（BT-rchild）dep1+1dep2+12.编写算法求二叉树的深度（高度）。2. int BTNodeDepth(BTNode *b)/求二叉树b的深度 int lchilddep,rchilddep; if (b=NULL) return(0); /空树的高度为0 else lchilddep=BTNodeDepth(b-lchild);/求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子树的高度为rchilddepreturn (lchilddeprchilddep)? (lchildd
23、ep+1):(rchilddep+1); 1.二叉树中结点定义如下，试编写算法，求二叉树中结点的个数。typedef struct nodeElemType data;/数据元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;int Nodes(BTNode *b)/求二叉树b的结点个数int num1,num2;if (b=NULL)return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=Nodes(b-lchild); num2=Nod
24、es(b-rchild); return (num1+num2+1);2.下列递归算法实现了交换二叉树中每个结点的左孩子和右孩子，试补充完整。void exchange(BTNode *b) /初始化时b为根结点BTNode *temp; /临时结点变量tempif(b!=NULL) /if语句实现b的左右孩子交换 temp=b-lchild;b-lchild=_;b-rchild=_;exchange(_); /递归实现左子树中结点的左右孩子交换exchange(_); /递归实现右子树中结点的左右孩子交换2. b-rchild temp b-lchild b-rchild1. 二叉树中结点
25、定义如下，编写递归算法实现二叉树的先序、中序、后序遍历。typedef struct nodeElemType data;/数据元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void PreOrder(BTNode *b) /先序遍历的递归算法if (b!=NULL) printf(%c ,b-data);/访问根结点PreOrder(b-lchild);/递归访问左子树PreOrder(b-rchild);/递归访问右子树void InOrder(BTNode *b) /中序遍历的递归算法if (b!=NULL) InOrder(b-lchild);/递归访问左子树printf(%c ,b-data);/访问根结点InOrder(b-rchild);/递归访问右子树void PostOrder(BTNode *b) /后序遍历的递归算法if (b!=NULL) PostOrder(b-lchild);/递归访问左子树PostOrder(b-rchild);/递归访问右子树printf(%c ,b-data);/访问根结点