2008信息与计算科学专业数据结构习题
26. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。
27. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.
28．树形结构中元素之间存在一个对多个的关系。 29．在二叉树的第i层上至少有2i-1个结点(i>=1)。 30．必须把一般树转换成二叉树后才能进行存储。 31．完全二叉树的存储结构通常采用顺序存储结构。 32．将一棵树转成二叉树，根结点没有左子树；
33．在二叉树中插入结点，则此二叉树便不再是二叉树了。 34．二叉树是一般树的特殊情形。 35．树与二叉树是两种不同的树型结构。
36. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 37．度为二的树就是二叉树。
38．深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2k-2?+1。 39.下面二叉树的定义只有一个是正确的，请在正确的地方画―√‖。
（1）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。 （2）（a）在一株二叉树的级i上，最大结点数是2i-1（i≥1）
（b）在一棵深度为k的二叉树中，最大结点数是2k-1+1（k≥1）。 （3）二叉树是结点的集合，满足如下条件： （a）它或者是空集；
（b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。 40. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。 41. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。 42. 二叉树中序线索化后，不存在空指针域。 43．霍夫曼树的结点个数不能是偶数。
44. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。 45. 哈夫曼树无左右子树之分。
46．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。
61
2008信息与计算科学专业数据结构习题
47．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 48. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。( )
三、填空题
1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。 3．在二叉树中，指针p所指结点为叶子结点的条件是______。
4．中缀式a+b*3+4*（c-d）对应的前缀式为__(1)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2)__。
5．具有256个结点的完全二叉树的深度为______。
6．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。
7．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。 8．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支 （非 终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。
9．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。
10．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______
11．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。
12．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为______。
13．高度为K的完全二叉树至少有______个叶子结点。
14．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。
15．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__(1)_；编号是i的结点所在的层次号是_(2)__（根所在的层次号规定为1层）。
16．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数
62
2008信息与计算科学专业数据结构习题
为______。
17．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。 18．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。
19．设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。 20．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。
21．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。
22．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。 23．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。
24． n（n大于1）个结点的树中，其深度最小的那棵树的深度是_(1)__，它共有_(2)__个叶子结点和_(3)__个非叶子结点；其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。
25．二叉树的先序序列和中序序列相同的条件是______。
26．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__， 右子树中有_(3)__。
27．现有按中序遍历二叉树的结果为abc，问有_ __种不同的二叉树可以得到这一遍历结果。
28．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。
29．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。 30．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 31．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。
32．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。
33．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。
34．将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。
63
2008信息与计算科学专业数据结构习题
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)___; }
} }
35．设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node
{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)
{if (t->lchild!=NULL) if __(1) _ N2++; else NL++; else if __(2)_ NR++; else _(3)_ ; if(t->lchild!=NULL) __(4)__; if (t->rchild!=NULL) __(5)__; } /*call form :if(t!=NULL) count(t);*/
36．下面是求二叉树高度的写的递归算法，试补充完整。二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。
height(p) {if (__(1)_) {if(p->lchild==null) lh=___(2)____; else lh=___(3)____; if(p->rchild==null) rh=___(4)____; else rh=___(5)____; if (lh>rh) hi=_(6)_；else hi=___(7)____; }
64
2008信息与计算科学专业数据结构习题
else hi=___(8)____; return hi; }
37 阅读下列程序说明和程序，填充程序。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
（3）重复（2）直到堆栈为空时为止。 typedef struct node *tree; struct node{int data; tree lchild,rchild;} exchange(tree t)
{tree r,p; tree stack [500]; int tp=0; ___(1)____ while (tp>=0) {___(2)____ if(____(3)___) {r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[___(4)____]=p->lchild; stack[++tp]=p->rchild; } }}
38．设一棵二叉树的结点定义为 struct BinTreeNode{
ElemType data; BinTreeNode *leftchild,*rightchild; } 现采用输入广义表表示建立二叉树。具体规定如下： （1）树的根结点作为由子树构成的表的表名放在表的最前面；
（2）每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 （3）在整个广义表输入的结尾加上一个特殊的符号（例如―#‖）表示输入结束。
65
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章+树和二叉树(习题)(2)在线全文阅读。
相关推荐：