数据结构第6章树习题.docx

《数据结构第6章树习题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树习题1单项选择题1、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则叶子结点个数是（B）。A、9B、11C、15D、无法确定2、设给定权值总数有n个，其哈夫曼树的结点总数为(D)。A、不确定B、2nC、2n+1D、2n–13、有关二叉树下列说法正确的是（B）。A、二叉树的度为2B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为24、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点。A、2hB、2h-1C、2h+1D、h+15、对于有n个结点的二叉树,其高度为（）。A、nlog2nB、log

2、2nC、D、不确定6、利用二叉链表存储树，则根结点的右指针是（）。A、指向最左孩子B、指向最右孩子C、空D、非空7、树的后根遍历序列等同于该树对应的二叉树的()。A、先序遍历B、中序遍历C、后序遍历D、层序遍历8、在下列存储形式中，哪一个不是树的存储形式？（）A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法9、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A、CBEFDAB、FEDCBAC、CBEDFAD、不定10、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空的或只有一个结点

3、B、任一结点无左子树C、高度等于其结点数D、任一结点无右子树11、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：()。A、不确定B、0C、1D、212、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()。A、X的双亲B、X的右子树中最左的结点C、X的左子树中最右结点D、X的左子树中最右叶结点13、引入二叉线索树的目的是（）.A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入和删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一14、下述编码中哪一个不是前缀码（）。A、（00，01，10，11）B、（0，1，00，11）C

4、、（0，10，110，111）D、（1，01，000，001）15、按照二叉树的定义，具有3个结点的二叉树有（）种。A、6B、5C、4D、316、在具有n个结点的二叉链表中，空指针域的个数为（）。A、2n–1B、2n+1C、n–1D、n+117、深度为4的二叉树至多有（）个结点。A、17B、18C、15D、1318、树最适合用来表示（）。A、有序数据元素B、无序数据元素C、元素之间具有层次关系的数据D、元素之间无联系的数据19、一棵具有n个结点的树，所有结点的度之和为（）。A、nB、n–1C、n+1D、无法确定20、一棵完全二叉树上有1001个结点，其中叶子结点个数是（）。

5、A、250B、501C、254D、50521、先序序列和后序序列正好相反的二叉树是（）。A、二叉排序树B、平衡二叉树C、左斜树D、以上都不对22、在任何一棵二叉树中，如果结点a的左孩子为b，右孩子为c，则在结点的先序遍历、中序遍历和后序遍历中（）。A、结点b一定在结点a的前面B、结点a一定在结点c的前面C、结点b一定在结点c的前面D、结点a一定在结点b的前面23、下面哪个选项可以唯一地确定一棵二叉树。（）A、先序序列B、中序序列C、中序后序序列D、先序和后序序列24、判断线索二叉树上指针p所指结点有右孩子的条件是（）。A、p!=NULLB、p->rchild!=NULLC、

6、p->rtag==0D、p->rtag==125、设一棵哈夫曼树共有35个结点，则该哈夫曼树共有（）个叶子。A、18B、35C、20D、3026、对应哈夫曼树，下面说法错误的是（）。A、哈夫曼树一定是完全二叉树B、哈夫曼树中没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D、树中任一非叶子结点的权值一定不小于下一层任一结点的权值2填空题1、已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则其后序序列为（）。2、在n个结点的线索二叉链表中，有（）个线索指针。3、若一棵满三叉树中含有121个结点，则该树深度为（）。4、在有n个叶子结点的哈夫曼树中，总结点数是（）

7、。5、树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中该结点一定（）。6、在一棵高度为h的三叉树中，最多含有（）个结点。7、判断线索二叉树中某结点指针p所指结点有左孩子的条件是（）。8、在有n个结点的哈夫曼树中，度为1的结点数是（）。9、深度为n的二叉树最少有（）个结点，最多有（）个结点。10、若对一棵具有n个结点的二叉树，采用二叉链表存储时，其指针总数为（），其中（）个用于指向孩子，（）个指针是空闲的。11、若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储在一维数组A中，则：A