2022年数据结构树和二叉树习题及答案 .pdf

《2022年数据结构树和二叉树习题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构树和二叉树习题及答案 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题六树和二叉树一、单项选择题1 以下说法错误的是 ( ) A树形结构的特点是一个结点可以有多个直接前趋B线性结构中的一个结点至多只有一个直接后继C树形结构可以表达( 组织 ) 更复杂的数据D树 ( 及一切树形结构) 是一种 分支层次 结构E任何只含一个结点的集合是一棵树2下列说法中正确的是 ( ) A任何一棵二叉树中至少有一个结点的度为2 B任何一棵二叉树中每个结点的度都为2 C任何一棵二叉树中的度肯定等于2 D任何一棵二叉树中的度可以小于2 3讨论树、森林和二叉树的关系，目的是为了（）A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储C将树、森林转换成二叉树

2、D体现一种技巧，没有什么实际意义4树最适合用来表示 ( ) A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据5若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点， 则度为 0 的结点个数是 （）A9 B11 C15 D不确定6设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1 ，M2和 M3 。与森林 F对应的二叉树根结点的右子树上的结点个数是（） 。AM1 BM1+M2 CM3 DM2+M3 7一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（）A 250 B 500 C254 D505 E以上答案都不对8. 设给定

3、权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-1 9二叉树的第I 层上最多含有结点数为（）A2I B 2I-1-1 C 2I-1 D2I -1 10一棵二叉树高度为h, 所有结点的度或为0，或为 2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 11. 利用二叉链表存储树，则根结点的右指针是（） 。A指向最左孩子 B指向最右孩子 C空 D非空12已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（） 。ACBEFDA B FEDCBA C CBEDFA D不定13已知某二叉树的后序遍历序

4、列是dabec, 中序遍历序列是debac , 它的前序遍历是（） 。Aacbed Bdecab Cdeabc Dcedba 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 14在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A都不相同 B完全相同C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同15在完全二叉树中，若一个结点是叶结点，则它没（） 。A左子结点 B右子结点C左子结点和右子结点

5、D左子结点，右子结点和兄弟结点16在下列情况中，可称为二叉树的是（）A每个结点至多有两棵子树的树B. 哈夫曼树C每个结点至多有两棵子树的有序树D. 每个结点只有一棵右子树E以上答案都不对17. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。A. 0 B. 1 C. 2 D. 不确定18. 引入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度 B 为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一19 n 个结点的线索二叉树上含有的线索数为（）A2n Bnl Cnl Dn 20由 3 个结点可以构造出多少种不同的二叉树？（）A2

6、B3 C4 D5 21下面几个符号串编码集合中，不是前缀编码的是（） 。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc 22. 一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中，则二叉树中第i 个结点（ i 从 1 开始用上述方法编号）的右孩子在数组A中的位置是（）AA2i(2i=n) BA2i+1(2i+1lchild=NULL)&(t-rchild=NULL)_; countleaf(t-lchild,&count); _ 13以下程序是二叉链表树中序

7、遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下： typedef struct node /*C语言 / char data; struct node *lchild,*rchild;*bitree; void vst(bitree bt) /*bt为根结点的指针*/ bitree p; p=bt; initstack(s); /*初始化栈 s 为空栈 */ while(p | !empty(s) /*栈 s 不为空 */ if(p) push (s,p); (1)_ ; /*P入栈 */ else p=pop(s); printf(“%c ”,p -data);(2)_ _

8、; /*栈顶元素出栈*/ 14二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针*/ int hl,hr; if (bt=NULL) return(1)_ _); hl=depth(bt-lchild); hr=depth(bt-rchild); if(2)_ _) (3)_ _； return(hr+1); 15 将 二 叉 树bt中 每 一 个 结 点 的 左 右 子 树 互 换 的C 语 言 算 法 如 下 ， 其 中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为

9、空的函数，请填写算法中得空白处，完成其功能。typedef struct node int data ; struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt) btnode *p, *q; if (bt)ADDQ(Q,bt); while(!EMPTY(Q) p=DELQ(Q); q=(1)_ _; p-rchild=(2)_ _; (3)_ _=q; if(p-lchild) (4)_ _; if(p-rchild) (5)_ _; / 第六章树和二叉树一、单项选择题名师资料总结 - - -精品资料欢迎下载 - - -

10、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 1.A2.D3 A4C5B6D7E 8. D9C10B11. C12A13D14 B15C16B 17. B18. A 19 C20D21B22. D23 C 二、判断题（在各题后填写“”或“”）1. 完全二叉树一定存在度为1 的结点。 2. 对于有 N个结点的二叉树，其高度为log2n。3. 二叉树的遍历只是为了在应用中找到一种线性次序。4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。

11、 5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。6中序遍历一棵二叉排序树的结点就可得到排好序的结点序列7完全二叉树中，若一个结点没有左孩子，则它必是树叶。8. 二叉树只能用二叉链表表示。9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。10. 用链表 (llink-rlink)存储包含 n 个结点的二叉树， 结点的 2n 个指针区域中有n-1 个空指针。 11树形结构中元素之间存在一个对多个的关系。12将一棵树转成二叉树，根结点没有左子树。13度为二的树就是二叉树。14. 二叉树中序线索化后，不存在空指针域。15霍夫曼树的结点个数不能是偶数。16哈夫曼树是带权路径长度最短的树，路

12、径上权值较大的结点离根较近。三、填空题1p-lchild=null & p-rchlid=null 2.(1)2k-1 (2)2k-1 364 4. 2n n-1 n+1 5 先序遍历后序遍历中序遍历6 .(1)2k-2+1 （第 k 层 1 个结点，总结点个数是2H-1， 其双亲是2H-1/2=2k-2 ） (2) log2i+1 74 8任何结点至多只有右子女的二叉树。9二叉排序树10前序11 69 12 *count+, countleaf(l-rchile,count) 13 (1) p=p-lchild / 沿左子树向下（2）p=p-rchild 14 (1)0 （ 2）hlhr (3)hr=hl 15 (1)p-rchild (2)p-lchild (3)p-lchild (4)ADDQ(Q,p-lchild) (5)ADDQ(Q,p-rchild) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -