数据结构非线性部分(树与二叉树)自测题及解答

1、页眉内容一、概念题(每空1分，共55分)1 .树(及一切树形结构)是一种“”结构。在树上，结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的。2 .由3个结点所构成的二叉树有种形态。3 .一棵深度为6的满二叉树有个分支结点和个叶子。4 .一棵具有257个结点的完全二叉树，它的深度为。5 .二叉树第i(i>=1)层上至多有个结点；深度为k(k>=1)的二叉树至多有个结点。6 .对任何二叉树，若度为2的节点数为n2,则叶子数no=。7 .满二叉树上各层的节点数已达到了二叉树可以容纳的。满二叉树也是二叉树,但反之不然。8 .设一棵完全二叉树有700个结点，则共有个叶子

2、结点。9 .设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。10 .一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。11 .二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按NLR次序)，后序法(即按次序)和中序法(也称对称序法，即按LNR次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是。12 .中序遍历的递归算法平均空间复杂度为。13 .二叉树通常有存储结构和

3、存储结构两类存储结构。14 .如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：(1) 若i=1,则结点X是;若i1,则X的双亲PARENT(X)的编号为。(2) 若2i>n,则结点X无且无;否则，X的左孩子LCHILD(X)的编号为若2i+1>n,则结点X无;否则，X的右孩子RCHILD(X)的编号为。15 .每个二叉链表的访问只能从结点的指针，该指针具有标识二叉链表的作用。16 .二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是的指针，或者是。17 .具有n个结点的二叉树中，一共有个指针域淇中只有个用来指向结点的左右

4、孩子，其余的个指针域为NULL。18 .二叉树有不同的链式存储结构，其中最常用的是与。19 .若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的个结点。20 .树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为和,即使在结点只有一棵子树的情况下，也要明确指出该子树是还是。21 .树的结点数目至少为,二叉树的结点数目至少为。22 .下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为：数据域data,左、右孩子域lchild、rchild和左、右标志域ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。ino

5、rdethread(thr)p=thr->lchild;while(p<>thr)/未循环结束while(14P=；printf(p->data);while(3)p=(4)_；printf(p->data);23 .由转换成二叉树时，其根结点的右子树总是空的。24 .哈夫曼(Huffman)树是带权路径长度的树，通常权值较大的结点离根25 .用5个权值3,2,4,5,1构造的哈夫曼(Huffman)树的带权路径长度是。二、选择题(每空1分，共10分)()1.不含任何结点的空树。(A)是一棵树；(C)是一棵树也是一棵二叉树()2.二叉树是非线性数据结构，所以。(A

6、)它不能用顺序存储结构存储；(C)顺序存储结构和链式存储结构都能存储都不能使用(B)是一棵二叉树；(D)既不是树也不是二叉树(B)它不能用链式存储结构存储(D)顺序存储结构和链式存储结构()3.具有n(n>0)个结点的完全二叉树的深度为。(A)log2(n)(B)log2(n)(C)log2(n)+1(D)log2(n)+1()4.把一棵树转换为二叉树后，这棵二叉树的形态是。(A)唯一的(B)有多种(C)有多种，但根结点都没有左孩子(D)有多种，但根结点都没有右孩子5 .树是结点的有PM集合，它A根结点，记为To其余的结点分成为m(m>0)jB的集合T1,T2,，Tm,每个集合又都

7、是树，此时结点T称为T的父结点，下称为T的子结点(1<i<nDo一个结点的子结点个数为该结点的C。供选择的答案A:有。个或1个有。个或多个有且只有1个有1个或1个以上B：互不相交允许相交允许叶结点相交允许树枝结点相交C:权维数次数序答案：A=B=C=6 .二叉树)。在完全的二叉树中，若一个结点没有B,则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C。供选择的答案A:是特殊的树 形结构B:左子结点C:最左子结点不是树的特殊形式是两棵树的总称有是只有二个根结点的树右子结点左子结点或者没有右子结点兄弟弟最左的兄弟最

8、右的兄弟最右子结点最邻近的右兄弟最邻近的左兄答案：A=B=C=三、综合题(1-7每题3分，8-10每题4分，共33分)1 .给定二叉树的两种遍历序列，分别是：前序遍历序列：D,A,C,E,B,H,F,G,I；中序遍历序列：D,C,B,E,H,A,QI,F,试画出二叉树B。2 .给定如图所示二叉树T,请画出与其对应的中序线索二叉树。3 .将算术表达式(a+b)+c*(d+e)+f)*(g+h)转化为二叉树。4 .试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序歹U。5 .编写递归算法，计算二叉树中叶子结点的数目。6 .写出求二叉树深度的算法。7 .编写递归算法，求二叉树中以元素值为

9、x的结点为根的子树的深度。8 .设度为m的树采用多重链表存储。每个结点有m+1个域，其中有一个数据域，m个指向孩子的指针。则空指针的数目是多少？说明这种存储方式的利弊。9 .假设用于通信白电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。10 .试编写最大堆的向上调整算法函数。要求：写成内联函数的形式，程序头已给出，已通过数组heap建堆，建堆区间由遍历器first、mid和last指向，即mid,last-

10、1)是一个堆，现自底向上将mid,last)调整为一个堆。template<classRaniter,classT>inlinevoid_fixup(Raniterfirst,Ranitermid,Raniterlast,Tt)参考答案一、概念题(每空1分，共55分)1、分支层次、根、直接前趋2、53、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、31 3292i-12 k-1n2+1最大值、完全350 (n/2 = 350)500 499 1 0n 2L R N F E G H D C BO顺序、链式根、i / 2、左孩子、右孩子

11、、根指向该结点的一个孩子、空指针2n、n-1、n+1二叉链表、三叉链表左子树、右子树、左子树、右子树1、 02i、右孩子、2i+1NULL22、(1)p->ltag=0(2)p->lchild(5)p=p->rchild(3)p->rtag=1&&p->rchild!=thr(4)p=p->rchild22、 树23、 最短、较近24、 33二、选择题(每空1分，共10分)1.C2.C3.C4.A5.A=(DB=C=®6.A=(2)B=(DC=CD三、综合题(1-9每题3分，10-11每题4分，共35分)1.解：方法是：由前序先确定

12、root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root,不断递归，则所有元素都将被唯一确定，问题得解。2.解：要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：55 40 25 60 28 08 33 542840600854553.该算术表达式转化的二叉树如图所示。LRD:JFKGDBHLMIECA5思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子,将其打印出来。法一：核心部分为：DLR(BinaryTreeNode*root)/*中序遍历递

13、归函数*/if(root!=NULL)if(root->lchild=NULL)&&(root->rchild=NULL)sum+;cout<<root->data<<endl;DLR(root->lchild);DLR(root->rchild);return(0);法二：intLeafCount_BiTree(BinaryTreeT)/求二叉树中叶子结点的数目一if(!T)return0;/空树没有叶子elseif(!T->lchild&&!T->rchild)return1;/叶子结点els

14、ereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);/左子树的叶子数加上右子树的叶子数一一LeafCount_BiTree6.解答略(参考教材)7.intGet_Sub_Depth(BinaryTreeT,intx)求二叉树中以值为x的结点为根的子树深度7if(T->data=x)cout<<Get_Depth(T)<<endl;/找到了值为x的结点，求其深度exit1;elseif(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)G

15、et_Sub_Depth(T->rchild,x);在左右子树中继续寻找/Get_Sub_DepthintGet_Depth(BinaryTreeT)求子树深度的递归算法一if(!T)return0;elsem=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;Get_Depth8 .n(n>0)个结点的m叉树共有n*m个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有n*m-(n-1)=n(m-1)+1个。这种存储结构统便于处理，但空链域造成存储效率低。9 .解：方案1;哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10,按哈夫曼规则:构造哈夫曼树如下：(100)(40)/、60)子母编P对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.1