数据结构习题第6章树

数据结构习题第6章树（1）2007-06-0314:33:26|分类：数据结构习题|标签：数据结构练习题|字号订阅第6章树6.1选择题1．一棵具有n个结点的完全二叉树的树高度（深度）是（）A）log2n+1B）log2n+1C）log2nD）log2n-1【答案】A2．有关二叉树下列说法正确的是（）A）二叉树的度为2B）一棵二叉树的度可以小于2C）二叉树中至少有一个结点的度为2D）二叉树中任何一个结点的度都为2【答案】B3．二叉树的第I层上最多含有结点数为（）A）2IB）2I-1-1C）2I-1D）2I-1【答案】C4．具有10个叶结点的二叉树中有（）个度为2的结点A）8B）9C）10D）11【答案】B5．在下述结论中，正确的是（）①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A）①②③B）②③④C）②④D）①④【答案】D6．由3个结点可以构造出多少种不同的二叉树？（）A）2B）3C）4D）5【答案】D7．引入二叉线索树的目的是（）A）加快查找结点的前驱或后继的速度B）为了能在二叉树中方便的进行插入与删除C）为了能方便的找到双亲D）使二叉树的遍历结果惟一【答案】A8．有n个叶子的哈夫曼树的结点总数为（）A）不确定B）2nC）2n+1D）2n-1【答案】D9．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A）所有的结点均无左孩子B）所有的结点均无右孩子C）只有一个叶子结点D）是任意一棵二叉树【答案】C【解析】先序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，单支树的特点是只有一个叶子结点或高度等于其结点数，故选C。10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A）250B）500C）505D）以上答案都不对【答案】D【解析】若每个结点均已经编号，则最大的编号为1001，其父亲结点的编号为500，那么从501到1001均为叶子结点。因此，叶子结点数为1001-500=501。故答案为D。11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（）A）ACBEDB）DECABC）DEABCD）CEDBA【答案】D【解析】依据后序遍历序列可确定根结点为C；再依据中序遍历序列可知其左子树由DEBA构成，右子树为空；又由左子树的后序遍历序列可知其根结点为E，由中序遍历序列可知E的左子树为D，右子树由BA构成，所以求得该二叉树的先序遍历序列为选项D）。12．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A）9B）11C）15D）不确定【答案】B13．利用二叉链表存储树时，根结点的右指针是（）A）指向最左孩子B）指向最右孩子C）空D）非空【答案】C【解析】利用二叉链表存储树时，即用孩子兄弟链表存储树，根结点的左指针指向其第一子女，根结点的右指针指向其下一兄弟，所以为空。14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）A）M1B）M1+M2C）M3D）M2+M3【答案】D【解析】当森林转化为对应的二叉树时，二叉树的根结点及其左子树是由森林的第一棵树转化而来，二叉树的右子树是由森林的其余树转化而来。15．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（）A）X的双亲B）X的右子树中最左的结点C）X的左子树中最右结点D）X的左子树中最右叶结点【答案】C16．n个结点的线索二叉树上含有的线索数为（）A）2nB）n-lC）n+lD）n【答案】C【解析】线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。17．在一棵高度为k的满二叉树中，结点总数为（）A）2k-1B）2kC）2k-1D）log2k+1【答案】C18．一棵树高为K的完全二叉树至少有（）个结点A）2k-1B）2k-1-1C）2k-1D）2k【答案】C6.2填空题1．在二叉树中，指针p所指结点为叶子结点的条件是_____________。【答案】p-lchild==NULL&&p-rchlid==NULL2．深度为H的完全二叉树至少有_____________个结点；至多有_____________个结点；H和结点总数N之间的关系是_____________。【答案】（1）2H-1（2）2H-1（3）H=log2N+13．一棵有n个结点的满二叉树有_____________个度为1的结点，有_____________个分支（非终端）结点和_____________个叶子，该满二叉树的深度为_____________。【答案】（1）0（2）(n-1）/2（3）(n+1）/2（4）log2n+14．对于一个具有n个结点的二叉树，当它为一棵_____________时，具有最小高度，当它为一棵_____________时，具有最大高度。【答案】（1）完全二叉树（2）单支树，树中任一结点（除最后一个结点是叶子外），只有左子女或只有右子女。5．在一棵二叉树中，度为0的结点的个数为N0，度为2的结点的个数为N2，则有N0=_____________【答案】N2+16．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。【答案】99【解析】在二叉树中，N0=N2+1，所以，有50个叶子结点的二叉树，有49个度为2的结点。若要使该二叉树的结点数最少，度为1的结点应为0个，即总结点数N=N0+N1+N2=99。7．具有n个结点的满二叉树，其叶结点的个数是_____________。【答案】(n+1）/28．每一棵树都能惟一的转换为它所对应的二叉树。若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_____________。设上述二叉树是由某森林转换而成，则其第一棵的先根次序序列是_____________。【答案】（1）FEGHDCB（2）BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是BEF）9．已知一棵二叉树的先序序列为ABDECFHG，中序序列为DBEAHFCG，则该二叉树的根为_____________，左子树中有_____________，右子树中有_____________。【答案】（1）A（2）DBE（3）HFCG10．先根次序周游树林正好等同于按_____________周游对应的二叉树；后根次序周游树林正好等同于_____________周游对应的二叉树。【答案】（1）先根次序（2）中根次序11．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是_____________；编号是i的结点所在的层次号是_____________（根所在的层次号规定为1层）。【答案】（1）2k-2+1（2）log2i+1【解析】第k层1个结点，总结点个数是2k-1，其双亲是2k-1/2=2k-2。12．某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____________。【答案】69【解析】在二叉树中，N0=N2+1，所以，有20个叶子结点的二叉树，有19个度为2的结点。又已知该二叉树中度为1的结点有30个，则总结点数N=N0+N1+N2=69。13．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_____________，带权路径长度WPL为_____________。【答案】（1）6（2）26114．有一份电文中共使用6个字符：a，b，c，d，e，f，它们的出现频率依次为2，3，4，7，8，9，试构造一棵哈夫曼树，则其加权路径长度WPL为_____________，字符c的编码是_____________。【答案】（1）80（2）001（不惟一）15．具有N个结点的二叉树，采用二叉链表存储，共有_____________个空链域。【答案】N+1【解析】在二叉树中，N=N0+N1+N2，N0=N2+1，空分支数为2N0+N1=N0+N1+（N2+1）=N+1。16．8层完全二叉树至少有_____________个结点，拥有100个结点的完全二叉树的最大层数为_____________。【答案】（1）128（第7层满，加第8层１个）（2）717．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_____________。【答案】21【解析】已知该树中结点数和分支数的关系分别如下：N=N0+N1+N2+N3+N4（1）N-1=N1+2N2+3N3+4N4（2）由（2）式求得N=（1+2*2+3*3+4*4）+1=31，再由（1）式求得N0=21。18．n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。【答案】（1）2（2）n-1（3）1（4）n（5）1（6）n-119．设y指向中序二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild，rchild分别代表左，右孩子)x-ltag=_____________;x-lchild=_____________;y-ltag=_____________;y-lchild=_____________;x-rtag=_____________;x-rchild=_____________;if(x-lchild!=NULL)&&(x-lchild-rtag==1)x-lchild-rchild=_____________;【答案】（1）1（2）y-lchild（3）0（4）x（5）1（6）y（7）x