习题精练第4和二叉树

1、单项选择题(38 题，共0.0 分) 无序的数据元数据间具有层次关系单项选择题(38 题，共0.0 分) 无序的数据元数据间具有层次关系的数数据间没有关系的数【：】2.对一棵具有n Bn-Cn-【：】3.按照二叉树的定义,3个结点的二叉树有几种形态？（不考虑数据信息的组合情况【：】 2的结点（2的二叉树4 14.B任何一棵二叉树，叶子结点数为度为2 的结点数减1C二叉树不适合用顺序结的二叉树，第i 个结点的左孩子（如果存在）的试【】A B 21；选项C D 5.设二叉树中有n22n11n00试【】110226.78 1试【】110226.78 17 26 3 54 45 3 62 7 【：】

2、n0 1 7+26+35+44+53+62=78（ni i 的结点数目m N0个叶子结点数，N11的结点，N22m 的结点，则有：N0=1+N2+2N3+(m-1)Nm7.有n（n0）：8.若某完全二叉树的深度为h：9.7 10正试【】：9.7 10正试【】727-1=64 10 548108 10.244：11.510的二叉树，数组的长度至少为：12.n 【：】n 2n n1 n1 13.T n 个结点，设按某种顺序对T 【：】n 2n n1 n1 13.T n 个结点，设按某种顺序对T ，求每个结点的 大于其左右孩子的C后序遍历序D层次遍：】对照后序遍历的先后关系（左右子树的大小关系，双亲

3、和孩子结点的相对关系【该C其分支结点无右子D其分支结点的度都为 【：】 A、B、C 试】【B其中任一结点无左孩右子树为其中任一结点无右孩：】【不会发生改右子树为其中任一结点无右孩：】【不会发生改【：】（LDR（LRD正试结构，结点数据信息的存放顺序依次为 A、B、C、D、E、F、G、H、I、J，】【正试】【（任何一个二叉树/子树的先序序列中第一个结点为根结点试【】 中序遍历也可分为 3 个部分：左子树部分、根结点、右试【】 中序遍历也可分为 3 个部分：左子树部分、根结点、右子树部分。题目给出的先序序列为 ABDCE，可知 A 为根结点，选项A 给出中序序列表示BD 是左子树部分，EC 是右子

4、树部分，和先序序列不 ，是可能的中序序列。选B BC 是左子树，DE ABDCE C D 21.n 【：】线索二叉树是利用二叉树的空链域加上线索，n n1 右孩双前驱和后【：】【：】当指定结点是叶子结点时，若指定结点是“某结点 X”的左子树中按先序遍历列出的最后一个结点，则该结点 X X 没有右孩子，则指定结点没有先序后继当指定结点是叶子结点时，若指定结点不是任何结点的左子树中按先序遍历列出的最后一个结点，则指定结试【】D 25.k 叉树，其分支结点数目为nBn-Dn（k-：试【】D 25.k 叉树，其分支结点数目为nBn-Dn（k-：】【的右指针域为空（即无右孩子n 27.X 是树T 中的一

5、个非根结点，B T 所对应的二叉树。在B 中，X 在树T 中，X 在树T 中，X 一定有右边兄弟 CT 中，X 一定是叶子结点 D在树T 中，X 【：】树转化为二叉树的过程中，若X X 正试】【h，对应由h 29.h，对应由h 29.C树的先序遍历序列与其对应的二叉树的中序遍历序列相D以上都不【：】B、C、D 中后按层【：】31.二叉树为二叉排序树的（）条件是其任一结点的值均大于其左孩子的值，小于其右孩子D既不充分也不必【：】值（当然也小于其右孩子的值。所以，该题的选项中至少应该包含必要条件，A、D 并非一个单增或单减得序列。所以正B（20，35，正试30【】352030 33.AA（20，3

6、5，正试30【】352030 33.AA 的左孩子的平衡因子为-【：】B树D二叉排序【：】A对应一组权值构造出【1 的结点12：】A9：】【1 的分支结点。n n-1 n-1 树2n-1 A9：】【1 的分支结点。n n-1 n-1 树2n-1 【：】B 1010138.5个字符，根据其使用频率设计对应的正试】【编码的概念和性质。按左分支编码为 0，右分支编码为 1，A、B、CD D 1D 简答题(120.0 分39.n 个结点并且其高度为n 的二叉树的数目是多少?简答题(120.0 分39.n 个结点并且其高度为n 的二叉树的数目是多少?：n n n 2n-1 j=1，2，3 M,N i，j

7、 N M n m ：-“左根右”-N 是M N 在M N M 的右孩子，N M P M 和N 的最近公共祖先，N P 的左子树中，M P N 在M ：C JudgeComplete(BiTreebt)：C JudgeComplete(BiTreebt)BiTreep=bt,QQ if (p= =NULL) return 1; InitQueueQ)初始化队列while(!QueueEmpty(Q p=DeQueue (Q); /出队ifp-lchild&flagEnQueueQ,p-lchild左孩子入elseif(p-lchild)return0; else flag=1;if(p-rchi

8、ld&flagEnQueueQ,p-rchild右孩子入队 else if (p-rchild) return 0;elsereturn：编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度h h+1层，则可以通过遍历计算二叉树中的每个结点的层次，其中最大值即为二叉bt 的高度，则递归定义如下:bt 0bt 1：（1）二叉树的高度(深度)为二叉树中结点层次的最大值，即结点的层次自根结点起递推。设根结点为第 1（1）二叉树的高度(深度)为二叉树中结点层次的最大值，即结点的层次自根结点起递推。设根结点为第 1bt 的高度，则递归定义如下:bt 0bt 1（1）bt 的深度算法。C 语言算法描

9、述如下：Height(BiTreebt) if(bt=NULL)return0; else if(hlhr)return(hl+1); else return(hr+1);（2）求二叉树bt 的最大宽度算法。C 语言算法描述如下：Width(BiTreebtbt 的最大宽度 if (bt= =NULL) return 0; /空二叉树宽度为0 else BiTreeQQ 是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1; / front 指向队头元素,rear 指向队尾元素 Qrear=bt; /根结点入队列last=1last temp=0;maxw=0; /temp

10、记局部宽度maxwwhile(frontlchild!=NULLQ+rear=p-lchild左孩子入队 if(p-rchild!=NULLQ+rear=p-rchild右孩子入队 if (frontlast) /一层结束if(tempmaxw) maxw=temp; /last 指向下层最右元素, return进行遍历，与二叉链表类似。在顺结构下，判二叉树为空时，用结点下标大于n（完全二叉树）或0（对：C voidPreOrder(ElemType历n) /的完全二叉树bt top=0,s/top s while(i0) while (i=n)f(bti);if(2*i+10i=stop结构

11、，结点结构为(lchild, data,rchild)：C voidexchange(BiTreebt将二叉树所有结点的左右子树交换的递归算法 if (bt)BiTree s； bt-rchild=s; /左右孩子交exchange(bt-lchild)交换左子树上所有结点的左右子树 exchange(bt-rchild)：C /in t(ElemTypel1,h1,l2,h2)t 是二叉树的中序和后序序列,l1,h1,l2,h2 ; /th2; /后序遍历序列最后一个元素是根结点数foifth2)break; /在中序序列中查找根结if(il1bt-lchild=NULL; /elsebt-

12、t if(ih1bt-rchild=NULLelse bt-rchild=46.h 的二叉树以一维数组BT(1:2h-1)elsebt-t if(ih1bt-rchild=NULLelse bt-rchild=46.h 的二叉树以一维数组BT(1:2h-1)0：中对叶子结点的判定是根据其左为0。叶子和双亲结点下标间的关系满足完全C h)h len=2h-1,count=0; /BT ( if (BTi!=0) /假定二叉树结点值是整数虚结点”用0 填if(i*2)len) count+; /i elseif(BT2*i=0&2*i+1lchild）if(bt-lchild=NULL&bt-rc

13、hild=NULL叶子结点 if (head=NULL) /第一个叶子结点 head=(BiTree)malloc(sizeof(BiNode); /生成头结点head-lchild=NULL; /头结点的左链为head-rchild=bt;头结点的右链指向第一个叶子结点 bt-lchild=head; /第一个叶子结点左链指向头结点 pre=bt; /pre 指向当前叶子结点elsepre-rchild=bt当前叶子结点链入双链表 eafList(bt-rchild) /48.bt 采用二叉链表：C eafList(bt-rchild) /48.bt 采用二叉链表：C voidMax(BiTreebt) if(bt=NULL)returnif(bt-lchild=NULL&bt-rchild=NULL) return bt-data;elsem=Max(bt-lchild求左子树中的最大值 n=Max(bt-rchild); /求右子树中的最大值ifmbt-data)returnm; else return bt-data;：C KeyTypepredt=0/pr